如何將CNF表達式重新轉換爲3-CNF？

Question

我有一個CNF表達這樣的，我希望它重鑄到3-CNF：

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

有誰知道我該怎麼做？

Answer 1

A 3-CNF是一個Conjunctive Normal Form其中所有子句有三個或更少的文字。要獲取對您表達這樣一種形式，你可以表達轉化爲一個嵌套的布爾表達式，所有運營商（和，或）有兩個操作數：

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 Transformation或Tseitin編碼。