Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

384 BOOLEAN ALGEBRA [CHAP. 15

EXAMPLE 15.14 Find the sum of adjacent productsP 1 andP 2 where:

(a) P=xyz′andP 2 =xy′z′.

P 1 +P 2 =xyz′+xy′z′=xz′(y+y′)=xz′( 1 )=xz′

(b)P 1 =x′yztandP 2 =x′yz′t.

P 1 +P 2 =x′yzt+x′yz′t=x′yt(z+z′)=x′yt( 1 )=x′yt

(c) P 1 =x′yztandP 2 =xyz′t.

HereP 1 andP 2 are not adjacent since they differ in two literals. In particular,

P 1 +P 2 =x′yzt+xyz′t=(x′+x)y(z+z′)t=( 1 )y( 1 )t=yt

(d)P 1 =xyz′andP 2 =xyzt.

HereP 1 andP 2 are not adjacent since they have different variables. Thus, in particular, they will not appear

as squares in the same Karnaugh map.

Case of Two Variables

The Karnaugh map corresponding to Boolean expressionsE=E(x, y)with two variablesxandyis shown
in Fig. 15-16(a). The Karnaugh map may be viewed as a Venn diagram wherexis represented by the points in
the upper half of the map, shaded in Fig. 15-16(b), andyis represented by the points in the left half of the map,
shaded in Fig. 15-16(c). Thusx′is represented by the points in the lower half of the map, andy′is represented
by the points in the right half of the map. Accordingly, the four possible minterms with two literals,

xy, xy′,x′y, x′y′

are represented by the four squares in the map, as labeled in Fig. 15-16(d). Note that two such squares are adjacent,
as defined above, if and only if the squares are geometrically adjacent (have a side in common).

Fig. 15-16

Any complete sum-of-products Boolean expressionE(x, y)is a sum of minterms and hence can be repre-
sented in the Karnaugh map by placing checks in the appropriate squares. A prime implicant ofE(x, y)will be
either a pair of adjacent squares inEor anisolatedsquare, i.e., a square which is not adjacent to any other square
ofE(x, y). A minimal sum-of-products form forE(x, y)will consist of a minimal number of prime implicants
which cover all the squares ofE(x, y)as illustrated in the next example.

EXAMPLE 15.15 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 =xy+xy′; (b) E 2 =xy+x′y+x′y′; (c) E 3 =xy+x′y′