我有一个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页以上的文字，它们可以通过引入中间变量被分解成两个或更多个较短的条款。 对于广泛使用的过程被称为Tseitin转型或Tseitin编码。
文章来源: How can I recast a CNF expression to 3-CNF?
