CODEWITHSUNDEEP
boolean-logicboolean-expressionboolean-operationsconjunctive-normal-form
Stephen Lasky
Stephen Lasky

Reputation: 447

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)

Upvotes: 0

Views: 1500

Answers (1)

Axel Kemper
Axel Kemper

Reputation: 11332

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.

Upvotes: 0

Related Questions