CNF简化算法

Question

假设一个布尔表达式是合取范式：是否有"simple"算法来简化它，同时将它保留在 CNF 中？

特别是以下表达式的 属性 导致了这种简化？

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

简化为...

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

Answer 1

你的例子的Karnaugh map是：

得到一个简化的DNF, '1' cells are grouped to get a cover with the minimum number of minterms。

类似地，可以将“0”单元格分组以获得具有最少项数的逆覆盖。

逆向图：

结果项的文字必须反转才能达到所需的最小值CNF

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

该过程利用了一个事实，即 minterm is a maxterm (commonly called CNF clause) 的逆向文字。