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

CHAP. 15] BOOLEAN ALGEBRA 387

(c) Check the squares corresponding to the five summands as in Fig. 15-20(c). As indicated by the loops,E 3 has
four prime implicants,xy,yz′,x′z′, andx′y′. However, only one of the two dashed ones, i.e., one ofyz′or
x′z′, is needed in a minimal cover ofE 3. ThusE 3 has two minimal sums:

E 3 =xy+yz′+x′y′=xy+x′z′+x′y′

EXAMPLE 15.17 Design a three-input minimal AND-OR circuitLwith the following truth table:

T=[A, B, C;L]=[ 00001111 , 00110011 , 01010101 ; 11001101 ]

From the truth table we can read off the complete sum-of-products form forL(as in Example 15.10):

L=A′B′C′+A′B′C+AB′C′+AB′C+ABC

The associated Karnaugh map is shown in Fig. 15-21(a). Observe thatLhas two prime implicants,B′andAC,
in its minimal cover; henceL=B′+ACis a minimal sum forL. Figure 15-21(b)gives the corresponding
minimal AND-OR circuit forL.

Fig. 15-21

Case of Four Variables

The Karnaugh map corresponding to Boolean expressionsE=E(x, y, z, t)with four variablesx,y,z,t
is shown in Fig. 15-22. Each of the 16 squares corresponds to one of the 16 minterms with four variables,

xyzt, xyzt′,xyz′t′,xyz′t, ...,x′yz′t

as indicated by the labels of the row and column of the square. Observe that the top line and the left side are
labeled so that adjacent products differ in precisely one literal. Again we must identify the left edge with the
right edge (as we did with three, variables) but we must also identify the top edge with the bottom edge. (These
identifications give rise to a donut-shaped surface called atorus, and we may view our map as really being a
torus.)

Fig. 15-22