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

CHAP. 15] BOOLEAN ALGEBRA 391

Also, using the absorption law in the last step,

a+R=a+(a∗(b∗c))=(a+a)∗(a+(b∗c))=a∗(a+(b∗c))=a

Thusa+L=a+R. Next we show that a′+L=a′+R. We have,

a′+L=a′+((a∗b)∗c)=(a′+(a∗b))∗(a′+c)

=((a′+a)∗(a′+b))∗(a′+c)=( 1 ∗(a′+b))∗(a′+c)

=(a′+b)∗(a′+c)=a′+(b∗c)

Also,

a′+R=a′+(a∗(b∗c))=(a′+a)∗(a′+(b∗c))

= 1 ∗(a′+(b∗c))=a′+(b∗c)

Thusa′+L=a′+R. Consequently,

L= 0 +L=(a∗a′)+L=(a+L)∗(a′+L)=(a+R)∗(a′+R)

=(a∗a′)+R= 0 +R=R

( 8 a)Follows from( 8 b)and duality.

15.6. Prove Theorem 15.3: Letabe any element of a Boolean algebraB.

(i) (Uniqueness of Complement) Ifa+x=1 anda∗x=0, thenx=a′.

(ii) (Involution Law)(a′)′=a

(iii) ( 9 a) 0 ′=1;( 9 b) 1 ′=0.

(i) We have:

a′=a′+ 0 =a′+(a∗x)=(a′+a)∗(a′+x)= 1 ∗(a′+x)=a′+x

Also,

x=x+ 0 =x+(a∗a′)=(x+a)∗(x+a′)= 1 ∗(x+a′)=x+a′

Hencex=x+a′=a′+x=a′.

(ii) By definition of complement,a+a′=1 anda∗a′=0. By commutativity,a′+a=1 anda′∗a=0.

By uniqueness of complement,ais the complement ofa′, that is,a=(a′)′.

(iii) By boundedness law( 6 a),0+ 1 =1, and by identity axiom( 3 b),0∗ 1 =0. By uniqueness of complement,

1 is the complement of 0, that is, 1= 0 ′. By duality, 0= 1 ′.

15.7. Prove Theorem 15.4: (DeMorgan’s laws):( 10 a) (a+b)′=a′∗b′.( 10 b) (a∗b)′=a′+b′.

( 10 a)We need to show that(a+b)+(a′∗b′)=1 and(a+b)∗(a′∗b′)=0; then by uniqueness of complement,

a′∗b′=(a+b′). We have:

(a+b)+(a′∗b′)=b+a+(a′∗b′)=b+(a+a′)∗(a+b′)

=b+ 1 ∗(a+b′)=b+a+b′=b+b′+a= 1 +a= 1

Also,

(a+b)∗(a′∗b′)=((a+b)∗a′)∗b′

=((a∗a′)+(b∗a′))∗b′=( 0 +(b∗a′))∗b′

=(b∗a′)∗b′=(b∗b′)∗a′= 0 ∗a′= 0

Thusa′∗b′=(a+b)′.

( 10 b) Principle of duality (Theorem 15.1).