2-SAT 问题中 CNF 转换为命令式范式的解释？

Question

所以这个问题对你们中的许多人来说可能看起来很愚蠢，但我发现有点难以理解将 CNF 子句转换为 INF 子句。

我正在浏览 this article 其中指出：

First we need to convert the problem to a different form, the so-called implicative normal form. Note that the expression a∨b is equivalent to ¬a⇒b∧¬b⇒a (if one of the two variables is false, then the other one must be true).

谁能解释一下我们是如何做到这一点的result/how这种转换有意义吗？我也不知道那个“=>”符号是什么意思。提前致谢！

更新1：如果对不同的逻辑符号有疑问，请参考wiki。

Answer 1

=>是言外之意，同理table:

A B | A => B
----+-------
F F |   T
F T |   T
T F |   F
T T |   T

事实上，你可以证明a => b等价于~a \/ b。（如实填写tables即可。）

现在，我们有：

  ~a => b 
= ~(~a) \/ b
= a \/ b

所以，它更强大：a \/ b 等同于 ~a => b。您可以类似地证明它也等同于 ~b => a；所以使用连词可能是多余的，但它不会改变等价关系。

如果有疑问，请始终画出完整的真相 tables，假设您有 4-5 个变量，这将非常有教育意义。如果您有更多变量，请使用 SAT/SMT 求解器来证明等价性。这就是他们的优势。

2-SAT 问题中 CNF 转换为命令式范式的解释？

Explanation of conversion of CNF to imperative normal form in 2-SAT problem?

algorithm

computer-science

boolean-algebra