668
Boolean Algebra and Computer Logic
Using the Karnaugh Map
How do we find a minimal sum-of-products form from a Karnaugh map (or from
a truth function or a canonical sum-of-products form)? We must use every marked
square of the map, and we want to include every marked square in the largest combination of marked squares possible, since doing so will reduce the expression as
much as possible. Surprisingly, we cannot begin by simply looking for the largest
blocks of marked squares on the map.
ExamplE 22
In the map of Figure 8.27, the four outside corners reduce to x 2 x 4 and the inside
square reduces to x 2 ′x 4 ′.
1
1
1
1
1
1
1
1
x 1 x 2
x 3 x 4
x 1 xЈ 2
x 3 xЈ 4
xЈ 1 xЈ 2
xЈ 3 xЈ 4
xЈ 1 x 2
xЈ 3 x 4
Figure 8.27
■
Practice 17 Find the two terms represented by the map in Figure 8.28.
1
1
1
1
1
1
x 1 x 2
x 3 x 4
x 1 xЈ 2
x 3 xЈ 4
xЈ 1 xЈ 2
xЈ 3 xЈ 4
xЈ 1 x 2
xЈ 3 x 4
Figure 8.28
ExamplE 23
In the Karnaugh map of Figure 8.29, if we simply looked for the largest block of
marked squares, we would use the column of 1s and reduce it to x 1 ′x 2 ′. However,
we would still have four marked squares unaccounted for. Each of these marked
squares can be combined into a two-square block in only one way (Figure 8.30),
and each of these blocks has to be included. But when this adjustment is made,
every square in the column of 1s is used, and the term x 1 ′x 2 ′ is superfluous. The
minimal sum-of-products form for this map becomes
x 2 ′x 3 x 4 + x 1 ′x 3 x 4 ′ + x 2 ′x 3 ′x 4 ′ + x 1 ′x 3 ′x 4