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

CHAP. 15] BOOLEAN ALGEBRA 389

The two-by-two squares represent the fundamental productsxzandy′z′, and the two adjacent squares (on top
and bottom) representsyzt′. Hence
E=xz+y′z′+yzt′

is a minimal sum forE.

SolvedProblems

BOOLEAN ALGEBRAS

15.1. Write the dual of each Boolean equation: (a)(a∗ 1 )∗( 0 +a′)=0; (b)a+a′b=a+b.

(a) To obtain the dual equation, interchange+and∗, and interchange 0 and 1. Thus

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

(b) First write the equation using∗to obtaina+(a′∗b)=a+b. Then the dual isa∗(a′+b)=a∗b, which can

be written as

a(a′+b)=ab

15.2. Recall (Chapter 14) that the setDmof divisors ofmis a bounded, distributive lattice with

a+b=a∨b=lcm(a, b) and a∗b=a∧b=gcd(a, b).

(a) Show thatDmis a Boolean algebra ifmis square free, i.e., ifmis a product of distinct primes.

(b) Find the atoms ofDm.

(a) We need only show thatDmis complemented. Letxbe inDmand letx′=m/x. Sincemis a product of distinct

primes,xandx′have different prime divisors. Hencex∗x′=gcd(x, x′)=1 andx+x′=1cm(x, x′)=m.

Recall that 1 is the zero element (lower bound) ofDmand thatmis the identity element (upper bound) ofDm.

Thusx′is a complement ofx, and soDmis a Boolean algebra.

(b) The atoms ofDmare the prime divisors ofm.

15.3. Consider the Boolean algebraD 210.

(a) List its elements and draw its diagram.

(b) Find the setAof atoms.

(c) Find two subalgebras with eight elements.

(d)IsX={ 1 , 2 , 6 , 210 }a sublattice ofD 210? A subalgebra?

(e)IsY={ 1 , 2 , 3 , 6 }a sublattice ofD 210? A subalgebra?

(a) The divisors of 210 are 1, 2, 3, 5, 6, 7, 10, 14, 15, 21, 30, 35, 42, 70, 105, and 210. The diagram ofD 210 appears

in Fig. 15-25.

(b) A={ 2 , 3 , 5 , 7 }, the set of prime divisors of 210.

(c) B={ 1 , 2 , 3 , 35 , 6 , 70 , 105 , 210 }andC={ 1 , 5 , 6 , 7 , 30 , 35 , 42 , 210 }are subalgebras ofD 210.

(d) Xis a sublattice since it is linearly ordered. However,Xis not a subalgebra since 35 is the complement of

2inD 210 but 35 does not belong toX. (In fact, no Boolean algebra with more than two elements is linearly

ordered.)

(e) Yis a sublattice ofD 210 since it is closed under+and∗. However,Yis not a subalgebra ofD 210 since it is not

closed under complements inD 210 , e.g., 35= 2 ′does not belong toY. (We note thatYitself is a Boolean algebra;

in fact,Y=D 6 .)