666
Boolean Algebra and Computer Logic
Maps for Three and Four Variables
The array forms for functions of three and four variables are shown in Figure 8.22.
In these arrays, adjacent squares also differ by only one variable. However, in
Figure 8.22a, the leftmost and rightmost squares in a row also differ by one variable, so we consider them adjacent. (They would in fact be adjacent if we wrapped
the map around a cylinder and glued the left and right edges together.) In Figure
8.22b, the leftmost and rightmost squares in a row are adjacent (differ by exactly
one variable), and also the top and bottom squares in a column are adjacent.
(a)
(b)
x 1 x 2
x 1 x 2
x 3 x 4
x 3
x 1 xЈ 2
x 1 xЈ 2
x 3 xЈ 4
xЈ 3
xЈ 1 xЈ 2
xЈ 1 xЈ 2
xЈ 3 xЈ 4
xЈ 1 x 2
xЈ 1 x 2
xЈ 3 x 4
figure 8.22
In three-variable maps, when two adjacent squares are marked with 1, one variable can be eliminated; when four adjacent squares are marked with 1 (either in a
single row or arranged in a square), two variables can be eliminated.
The labelings for two-, three-, and four-variable maps can be done in various
ways, but they must be done so that adjacent squares differ by one variable. It’s
probably best to just memorize the labeling schemes we’ve used here.
ReminDeR
It is crucial to label the
Karnaugh map so that
adjacent squares differ by
one variable.
example 21
In the map of Figure 8.23, the squares that combine for a reduction are shown as a
block. These four adjacent squares reduce to x 3 (eliminate the changing variables
x 1 and x 2 ). The reduction uses our basic reduction rule more than once:
x 1 x 2 x 3 + x 1 x 2 ′x 3 + x 1 ′x 2 ′x 3 + x 1 ′x 2 x 3 = x 1 x 3 (x 2 + x 2 ′) + x 1 ′x 3 (x 2 ′ + x 2 )
= x 1 x 3 + x 1 ′x 3
= x 3 (x 1 + x 1 ′)
= x 3
But, again, you don’t have to go through this process; you can just look at the
Karnaugh map in Figure 8.23.
1
1
1
1
x 1 x 2
x 3
x 1 xЈ 2
xЈ 3
xЈ 1 xЈ 2 xЈ 1 x 2
figure 8.23