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)
The Karnaugh map of your example is:
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:
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.