cnf - 如何将 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 的所有行并找到覆盖所有这些行的最小术语。如果你然后反转 minterms 中的所有文字，你有一个CNF. 如果 case 子句有 3 个以上的文字，则可以通过引入中间变量将它们分解为两个或更多个较短的子句。广泛使用的程序称为Tseitin 转换或 Tseitin 编码。