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

392 BOOLEAN ALGEBRA [CHAP. 15

15.8. Prove Theorem 15.5: The following are equivalent in a Boolean algebra:

( 1 )a+b=b; ( 2 )a∗b=a; ( 3 )a′+b= 1 ; ( 4 )a∗b′= 0.

By Theorem 14.4, ( 1 ) and ( 2 ) are equivalent. We show that ( 1 ) and ( 3 ) are equivalent. Suppose ( 1 ) holds. Then

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

Now suppose( 3 )holds. Then

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

Thus( 1 )and( 3 )are equivalent.

We next show that( 3 )and( 4 )are equivalent. Suppose( 3 )holds. By DeMorgan’s law and involution,

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

Conversely, if( 4 )holds then

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

Thus( 3 )and( 4 )are equivalent. Accordingly, all four are equivalent.

15.9. Prove Theorem 15.6: The mappingf:B→P (A)is an isomorphism whereBis a Boolean algebra,P (A)

is the power set of the setAof atoms, and

f(x)={a 1 ,a 2 ,...,an}

wherex=a 1 +···+anis the unique representation ofaas a sum of atoms.

Recall (Chapter 14) that if thea’s are atoms thena^2 i=aibutaiaj=0 forai=aj. Supposex,yare inBand

suppose

x=a 1 +···+ar+b 1 +···+bs

y=b 1 +···+bs+c 1 +···+ct

where

A={a 1 ,...,ar,b 1 ,...,bs,c 1 ,...,ct,d 1 ,...,dk}

is the set of atoms ofB. Then

x+y=a 1 +···+ar+b 1 +···+bs+c 1 +···+ct

xy=b 1 +···bs

Hence

f(x+y)={a 1 ,...,ar,b 1 ,...,bs,c 1 ,...,ct}

={a 1 ,...,ar,b 1 ,...,bs}∪{b 1 ,...,bs,c 1 ,...,ct}

=f(x)∪f(y)

f(xy)={b 1 ,...,bs}

={a 1 ,...,ar,b 1 ,...,bs}∩{b 1 ,...,bs,c 1 ,...,ct}

=f(x)∩f(y)

Let

y=c 1 +···+ct+d 1 +···+dk.Thenx+y=1 andxy= 0 ,and soy=x′

Thus

f(x′)={c 1 ,...,ct,d 1 ,...,dk}={a 1 ,...,ar,b 1 ,...,bs}c=(f (x))c

Since the representation is unique,fis one-to-one and onto. Hencefis a Boolean algebra isomorphism.