提问人：Utkarsh 提问时间：4/8/2020 最后编辑：Utkarsh 更新时间：6/14/2020 访问量：216
2-SAT问题中CNF转换为命令性正态形式的解释？
Explanation of conversion of CNF to imperative normal form in 2-SAT problem?
问：
所以这个问题对你们中的许多人来说可能看起来很愚蠢，但我发现很难理解将 CNF 条款转换为 INF 条款。
我正在浏览这篇文章，其中指出：
首先，我们需要将问题转换为不同的形式，即所谓的隐含正态形式。请注意，表达式 a∨b 等价于 ¬a⇒b∧¬b⇒a（如果两个变量中的一个为 false，则另一个变量必须为 true）。
有人可以解释一下我们如何得到这个结果/这种转换如何有意义？我也不知道那个“ => ”符号是什么意思。提前致谢！
更新 1：如果对不同的逻辑符号有疑问，请参阅此 wiki。
答：
1赞
alias
4/8/2020
#1
=>是暗示，与真值表：
A B | A => B
----+-------
F F | T
F T | T
T F | F
T T | T
事实上，你可以证明它等价于 .（只需填写真值表即可。a => b~a \/ b
现在，我们有：
~a => b
= ~(~a) \/ b
= a \/ b
所以，它更强：相当于.你同样可以证明它也等价于 ;因此，采用连词可能是多余的，但它不会改变等价性。a \/ b~a => b~b => a
如果有疑问，请始终绘制完整的真值表，假设您有 4-5 个变量，这将非常有教育意义。如果您有更多变量，请使用 SAT/SMT 求解器来证明等价性。这就是他们的好处。
评论
0赞
Utkarsh
4/10/2020
同样来自 wiki en.wikipedia.org/wiki/Material_conditional 它只是意味着“如果 p 为真，那么 q 也是真的”，因此只有当 p 为真而 q 为假时，→ q 的陈述 p 才是假的。
评论