PHYS345 Electricity and Electronics

Example of Karnaugh Mapping

Boxing Zeroes for Product of Sums:

Consider again the following truth table for three inputs:
 A   B   C     O 
0 0 0   0
0 0 1   0
0 1 0   1
0 1 1   1
1 0 0   1
1 0 1   0
1 1 0   1
1 1 1   0

The truth table expressed in a form suitable for Karnaugh mapping:

 BC 00  01  11  10 
A\  
 0     0   0   1   1 
 1     1   0   0   1 

Boxing the zeroes:

 BC 00  01  11  10 
A\  
 0     0   0   1   1 
 1     1   0   0   1 

The red cells form a 1x2 supercell represented by A'.B'.
The green cells form a 1x2 supercell represented by A.C.
The resulting Boolean expression for this truth table is the complement of the sum of these cells, (A'.B' + A.C)'.
This still looks like a sum of products, just NOTted!

Several applications of De Morgan's theorems will yield the desired product of sums:

(A'.B' + A.C)'  = (A'.B')' . (A.C)' by one application of De Morgan's theorem.
   = (A+B) . (A.C)' by application of the other De Morgan's theorem.
   = (A+B) . (A'+C') again by application of De Morgan's theorem.
    Thus results the product of sums!

This realization again requires five gates as shown below:

POS example

NOTE: The minimum realization requires only three gates.
This results from the next to last line in the application of De Morgan's theorems above.

Minimum gate count

Back to PHYS345 Home Page.
Comments, suggestions, or requests to ghw@udel.edu.

"http://www.physics.udel.edu/~watson/phys345/class/17-pos-example.html"
Last updated Nov. 4, 1999.
Copyright George Watson, Univ. of Delaware, 1999.