386 BOOLEAN ALGEBRA [CHAP. 15
Fig. 15-19the map, as shaded in Fig. 15-19(c). Thusx′,y′, andz′are represented, respectively, by points in the lower half,
right half, and middle two quarters of the map.
By abasic rectanglein the Karnaugh map with three variables, we mean a square, two adjacent squares, or four
squares which form a one-by-four or a two-by-two rectangle. These basic rectangles correspond to fundamental
products of three, two, and one literal, respectively. Moreover, the fundamental product represented by a basic
rectangle is the product of just those literals that appear in every square of the rectangle.
Suppose a complete sum-of-products Boolean expressionE=E(x, y, z)is represented in the Karnaugh
map by placing checks in the appropriate squares.Aprime implicant ofEwill be amaximal basic rectangleofE,
i.e., a basic rectangle contained inEwhich is not contained in any larger basic rectangle inE. A minimal sum-of-
products form forEwill consist of aminimal coverofE, that is, a minimal number of maximal basic rectangles
ofEwhich together include all the squares ofE.
EXAMPLE 15.16 Find the prime implicants and a minimal sum-of-products form for each of the following
complete sum-of-products Boolean expressions:
(a) E 1 =xyz+xyz′+x′yz′+x′y′z.
(b)E 2 =xyz+xyz′+xy′z+x′yz+x′y′z.
(c) E 3 =xyz+xyz′+x′yz′+x′y′z′+x′y′z.
This can be solved by using Karnaugh maps as follows:
(a) Check the squares corresponding to the four summands as in Fig. 15-20(a). Observe thatE 1 has three prime
implicants (maximal basic rectangles), which are circled; these arexy,yz′, andx′y′z. All three are needed
to coverE 1 ; hence the minimal sum forE 1 is
E 1 =xy+yz′+x′y′z(b) Check the squares corresponding to the five summands as in Fig. 15-20(b). Note thatE 2 has two prime
implicants, which are circled. One is the two adjacent squares which representsxy, and the other is the
two-by-two square (spanning the identified edges) which representsz. Both are needed to coverE 2 ,sothe
minimal sum forE 2 is
E 2 =xy+zFig. 15-20