CNF简化算法

Question

假设一个布尔表达式是联合范式:是否有一个“简单”算法来简化它，同时又将它保持在CNF中？

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

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

简化成。

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

Answer 1

您的示例的卡诺图是：

​

​

为了得到一个简化的DNF，'1‘单元格被分组，以得到一个最小数量的腹肌覆盖。

类似地，可以对'0‘单元格进行分组，以得到具有最小项数的逆覆盖。

逆图：

​

​

产生的术语的文字必须倒置，才能达到所需的最小CNF。

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

该过程利用了一个事实，即腹地的逆是一个带有倒文字的最大项 (通常称为CNF条款)。