algorithm - 将并非全部相等的 2-SAT Pr0blem 转换为等效的 2-SAT pr0blem

Question

我正在查看以前的试卷，并且遇到了这个让我感到困惑的问题。

问题：

将子句给出的 Not-All-Equal 2-SAT 问题转换{x1, x2}, {x2, x3}, {x3, x4}, {x4, x5}, {x5, x1}为等效的 2-SAT 问题。（提示：2-SAT 问题包含 10 个子句）。

根据我的理解，这是否只是在每个子句中找到每个文字的否定？例如，{x1, x2} = {-x1, -x2}, 并且这是为每个子句完成的？这个对吗？

Answer 1

那是对的。具体来说，将所有子句替换(x ∨ y)为(x ∨ y) ∧ (~x ∨ ~y). 字面意思是“x 或 y 必须为真，而 x 或 y 必须为假”，或者等效地“(x ∨ y)在确保xand之一y为假的同时满足”。

为了证明等价性，我们首先假设 NAE 2-SAT 问题是可满足的。令 A 为一个令人满意的赋值，令其{x, y}为一个任意子句。由于 和 中的一个x是y真的，这意味着它(x ∨ y) ∧ (~x ∨ ~y)是真的。因此，满足 2-SAT 公式中相应的两个子句。由于{x, y}是任意选择的，因此我们得出结论 A 满足 2-SAT 公式中的所有子句。

相反，让我们假设 NAE 2-SAT 是不可满足的。也就是说，对于任何赋值，都存在一些子句{x, y}，其中xandy要么都为真，要么都为假。令 A 为任意选择的赋值，令{x, y}为 A 不满足的子句（在 NAE 2-SAT 中）。因为x = y，这意味着那(x ∨ y) ∧ (~x ∨ ~y)是假的（因为连词的一半是假的）。因此，A 不满足 2-SAT 公式。由于 A 是任意选择的，因此我们得出结论，没有任何作业满足 2-SAT 公式。