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

CHAP. 15] BOOLEAN ALGEBRA 395

15.19. Prove Lemma 15.10: SupposeQis the consensus ofP 1 andP 2. ThenP 1 +P 2 +Q=P 1 +P 2.

Since the literals commute, we can assume without loss of generality that

P 1 =a 1 a 2 ···ar,t, P 2 =b 1 b 2 ···bst′,Q=a 1 a 2 ···arb 1 b 2 ···bs

Now,Q=Q(t+t′)=Qt+Qt′. BecauseQtcontainsP 1 ,P 1 +Qt=P 1 ; and becauseQt′containsP 2 ,P 2 +Qt′=P 2.

Hence

P 1 +P 2 +Q=P 1 +P 2 +Qt+Qt′=(P 1 +Qt)+(P 2 +Qt′)=P 1 +P 2

15.20. LetE=xy′+xyz′+x′yz′. Find: (a) the prime implicants ofE;(b) a minimal sum forE.

(a) Apply Algorithm 15.3 (consensus method) as follows:

E=xy′+xyz′+x′yz′+xz′ (consensus ofxy′andxyz′)

=xy′+x′yz′+xz′ (xyz′includesxz′)

=xy′+x′yz′+xz′+yz′ (consensus ofx′yz′andxz′)

=xy′+xz′+yz′ (x′yz′includesyz′)

Neither step in the consensus method can now be applied. Hencexy′,xz′, andyz′are the prime implicants ofE.

(b) Apply Algorithm 15.4 write each prime implicant ofEin complete sum-of-products form obtaining:

xy′=xy′(z+z′)=xy′z+xy′z′

xz′=xz′(y+y′)=xyz′+xy′z′

yz′=yz′(x+x′)=xyz′+x′yz′

Only the summandsxyz′andxy′z′ofxz′appear among the other summands and hencexz′can be eliminated

as superfluous. ThusE=xy′+yz′is a minimal sum forE.

15.21. LetE=xy+y′t+x′yz′+xy′zt′. Find: (a) prime implicants ofE;(b) minimal sum forE.

(a) Apply Algorithm 15.3 (consensus method) as follows:

E=xy+y′t+x′yz′+xy′zt′+xzt′ (consensus ofxyandxy′zt′)

=xy+y′t+x′yz′+xzt′ (xy′zt′includesxzt′)

=xy+y′t+x′yz′+xzt′+yz′ (consensus ofxyandx′yz′)

=xy+y′t+xzt′+yz′ (x′yz′includesyz′)

=xy+y′t+xzt′+yz′+xt (consensus ofxyandy′t)

=xy+y′t+xzt′+yz′+xt+xz (consensus ofxzt′andxt)

=xy+y′t+yz′+xt+xz (xzt′includesxz)

=xy+y′t+yz′+xt+xz+z′ (consensus ofy′tandyz′)

Neither step in the consensus method can now be applied. Hence the prime implicants ofEarexy,y′t,yz′,xt,

xz, andz′t.

(b) Apply Algorithm 15.4 that is, write each prime implicant in complete sum-of-products form and then delete one

by one those which are superfluous, i.e. those whose summands appear among the other summands. This finally

yields

E=y′t+xz+yz′

as a minimal sum forE.

LOGIC GATES

15.22. Express the outputYas a Boolean expression in the inputsA,B,Cfor the logic circuit in:

(a) Fig. 15-26(a);(b) Fig. 15-26(b).

(a) The inputs to the first AND gate areAandB′and to the second AND gate areB′andC. ThusY=AB′+B′C.

(b) The inputs to the first AND gate areAandB′and to the second AND gate areA′andC. ThusY=AB′+A′C.