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

394 BOOLEAN ALGEBRA [CHAP. 15

15.15. LetE=xy′+xyz′+x′yz′. Prove that(a) xz′+E=E;(b) x+E=E;(c)z′+E=E.

Since the complete sum-of-products form is unique,A+E=E, whereA=0, if and only if the summands

in the complete sum-of-products form forAare among the summands in the complete sum-of products form forE.

Hence, first find the complete sum-of-products form forE:

E=xy′(z+z′)+xyz′+x′yz′=xy′z+xy′z′+xyz′+x′yz′

(a) Expressxz′in complete sum-of-products form:

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

Since the summands ofxz′are among those ofE, we havexz′+E=E.

(b) Expressxin complete sum-of-products form:

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

The summandxyzofxis not a summand ofE; hencex+E=E.

(c) Expressz′in complete sum-of-products form:

z′=z′(x+x′)(y+y′)=xyz′+xy′z′+x′yz′+x′y′z′

The summandx′y′z′ofz′is not a summand ofE; hencez′+E=E.

MINIMAL BOOLEAN EXPRESSIONS, PRIME IMPLICANTS

15.16. For any Boolean sum-of-products expressionE,weletELdenote the number of literals inE(counting
multiplicity) andESdenote the number of summands inE. FindELandESfor each of the following:
(a) E=xy′z+x′z′+yz′+x(c)E=xyt′+x′y′zt+xz′t
(b) E=x′y′z+xyz+y+yz′+x′z(d)E=(xy′+z)′+xy′

Simply add up the number of literals and the number of summands in each expression:

(a) EL= 3 + 2 + 2 + 1 = 8 ,ES=4.

(b) EL= 3 + 3 + 1 + 2 + 2 = 11 ,ES=5.

(c) EL= 3 + 4 + 3 = 10 ,ES=3.

(d) BecauseEis not written as a sum of products,ELandESare not defined.

15.17. Given thatEandFare equivalent Boolean sum-of-products, define:

(a)Eis simpler thanF;(b)Eis minimal.

(a) Eis simpler thanFifEL<FLandES≤FS,orifEL≤FLandES<FS.

(b) Eis minimal if there is no equivalent sum-of-products expression which is simpler thanE.

15.18. Find the consensusQof the fundamental productsP 1 andP 2 where:

(a) P 1 =xy′z′,P 2 =xyt (c) P 1 =xy′z′,P 2 =x′y′zt

(b) P 1 =xyz′t,P 2 =xzt (d) P 1 =xyz′,P 2 =xz′t

The consensusQofP 1 andP 2 exists if there is exactly one variable, sayxk, which is complemented in one of

P 1 andP 2 and uncomplemented in the other. ThenQis the product (without repetition) of the literals inP 1 andP 2

afterxkandx′khave been deleted:

(a) Deletey′andyand then multiply the literals ofP 1 andP 2 (without repetition) to obtainQ=xz′t.

(b) Deletingz′andzyieldsQ=xyt.

(c) They have no consensus since bothxandzappear complemented in one of the products and uncomplemented

in the other.

(d) They have no consensus since no variable appears complemented in one of the products and uncomplemented

in the other.