ic
Section 8.3 Minimization
665
sum-of-products form for a truth function of, say, four variables might be quite
long and require some searching to locate two product terms differing by only one
factor. To help us in this search, we can use the Karnaugh map. The Karnaugh
map is a visual representation of the truth function so that terms in the canonical
sum-of-products form that differ by only one factor can be matched quickly.
Karnaugh Map
In the canonical sum-of-products form for a truth function, we are interested in
values of the input variables that produce outputs of 1. The Karnaugh map records
the 1s of the function in an array that forces products of inputs
differing by only one factor to be adjacent. The array form for
a two-variable function is given in Figure 8.20. Notice that the
square corresponding to x 1 x 2 , the upper left-hand square, is adjacent to squares x 1 ′x 2 and x 1 x 2 ′, which differ in one factor from
x 1 x 2 ; however, it is not adjacent to the x 1 ′x 2 ′ square, which differs
in two factors from x 1 x 2 .
xЈ 2
x 2
xЈ 1
x 1
Figure 8.20
ExamplE 20
The truth function of Table 8.10 is represented by the Karnaugh map of Figure
8.21. At once we can observe 1s in two adjacent squares, so there are two terms in
the canonical sum-of-products form differing by one variable; again from the map,
we see that the variable that changes is x 1 . It can be eliminated. We conclude that
the function can be represented by x 2 . Indeed, the canonical sum-of-products form
for the function is x 1 x 2 + x 1 ′x 2 , which, by our basic reduction rule, reduces to x 2 .
However, we did not have to write the canonical form—we only had to look at the
map.
TablE 8.10
x 1
x 2
f( x 1 , x 2 )
1
1
1
1
0
0
0
1
1
0
0
0
1 1
x 1 xЈ 1
x 2
xЈ 2
Figure 8.21
■
Practice 16 Draw the Karnaugh map and use it to find a reduced expression for the function in
Table 8.11.
TablE 8.11
x 1
x 2
f( x 1 , x 2 )
1
1
0
1
0
0
0
1
1
0
0
1