我如何将CNF的表达重铸为3-CNF？

Question

我有一个像这样的CNF表达式，我想把它改写成3-CNF：

(a+b+c+d)(~a)(~b+d)(a+b+~d)

有人知道我是怎么做到的吗？

Answer 1

3-CNF是一个合合范式，其中所有子句都有三个或更少的文本。要获得表达式的这种形式，可以将表达式转换为嵌套的布尔表达式，其中所有运算符(和，或)都有两个操作数：

t1a = (a+b)
t1b = (c+d)
t1 = t1a + t1b
t2 = (~a)
t3 = (~b+d)
t4a = (a+b)
t4 = t4a + ~d
t5a = t1 t2
t5b = t3 t4
t5 = t5a t5b

您可以直接将这个嵌套表达式转换为一组3-CNF子句。

最小化解：

(~a)(~b + d)(b + ~d)(c + d)  

正如WolframAlpha所建议的，它是表达式的3-CNF，因为它不包含更长的子句。

对于小案件，你可以填写一个真值表。查看输出为0的所有行，并查找涵盖所有这些行的中间部分。然后，如果您将所有文本倒置到中间层，那么您就有了一个CNF。如果子句有3个以上的文本，则可以通过引入中间变量将它们分解为两个或多个较短的子句。广泛使用的程序称为将军澳变换或将军澳编码。