将 Unrestricted SAT (USAT) 减少为 3-SAT

Question

我通过将每个子句 l1 ∨ ⋯ ∨ ln 转换为 n − 2 个子句的合取来简单地知道过程。

我尝试用 Z3 显示满足原始公式和最终公式的值，以表明它们与 SMT 文件一样可满足。

为了澄清，你能举出关于这个过程的任何例子吗？谢谢。

Answer 1

通过询问求解器是否存在可以区分两个公式的赋值来完成等价性检查。如果没有这样的赋值，那么您可以得出结论，公式是等价的，或者在 SAT 上下文中，等价可满足。

这是一个简单的例子：

from z3 import *

a, b, c = Bools('a b c')

fml1 = Or(And(a, b), And(a, c))
fml2 = And(a, Or(b, c))

s = Solver()
s.add(Distinct(fml1, fml2))
print(s.check())

现在如果 fml1 是一个任意的 SAT 公式，而 fml2 是一个 3-SAT 转换版本（我不是说上面是 SAT 和 3-SAT 转换，而是替换你的算法的结果在这里），那么我们预计 SAT 求解器无法区分它们，即公式 Distinct(fml1, fml2) 将无法满足。事实上，我们得到：

unsat

确定它们是相同的。

如果您只使用 SMTLib，则要使用的模板是：

(declare-fun a () Bool)
(declare-fun b () Bool)
(declare-fun c () Bool)

(assert (distinct (or (and a b) (and a c))
                  (and a (or b c))))
(check-sat)

将 Unrestricted SAT (USAT) 减少为 3-SAT

Reducing Unrestricted SAT (USAT) into 3-SAT

z3

sat