Search code examples
boolean-logicboolean-expressionboolean-operationsconjunctive-normal-form

CNF Simplification Algorithm

Given that a boolean expression is in conjunctive normal form: is there a "simple" algorithm to simplify it while keeping it in CNF?

In particular, what property of the following expression causes this simplifiation?

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

simplifies to ...

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

  • The Karnaugh map of your example is:

    enter image description here

    To get a simplified DNF, '1' cells are grouped to get a cover with the minimum number of minterms.

    Similarly, one can group the '0' cells to get an inverse cover with the minimum number of terms.

    The inverse map:

    enter image description here

    The literals of the resulting terms have to be inverted to arrive at the desired minimum CNF

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

    The procedure makes use of the fact that the inverse of a minterm is a maxterm (commonly called CNF clause) with inverted literals.