boolean-logic - CNF 简化算法

Question

鉴于布尔表达式是合取范式：是否有一个“简单”的算法来简化它，同时保持它在 CNF 中？

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

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

简化为...

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

Answer 1

您的示例的卡诺图是：

为了得到一个简化的DNF，“1”个单元被分组以获得最小数量的minterms的覆盖。

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

逆映射：

结果项的文字必须倒置以达到所需的最小CNF

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

该过程利用了这样一个事实，即 minterm 的逆是带有反转文字的maxterm（通常称为CNF 子句）。