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

CHAP. 15] BOOLEAN ALGEBRA 403

SupplementaryProblems

BOOLEAN ALGEBRAS

15.43. Write the dual of each Boolean expression:

(a) a(a′+b)=ab (b) (a+ 1 )(a+ 0 )=a (c)(a+b)(b+c)=ac+b

15.44. Consider the latticesDmof divisors ofm(wherem>1).

(a) Show thatDmis a Boolean algebra if and only ifmissquare-free, that is, ifmis a product of distinct primes.

(b) IfDmis a Boolean algebra, show that the atoms are the distinct prime divisors ofm.

15.45. Consider the following lattices: (a)D 20 ; (b)D 55 ; (c)D 99 ; (d)D 130. Which of them are Boolean algebras, and what are

their atoms?

15.46. Consider the Boolean algebraD 110

(a) List its elements and draw its diagram.

(b) Find all its subalgebras.

(c) Find the number of sublattices with four elements.

(d) Find the setAof atoms ofD 110.

(e) Give the isomorphic mappingf:D 110 →P (A)as defined in Theorem 15.6.

15.47. LetBbe a Boolean algebra. Show that:

(a) For anyxinB,0≤x≤1. (b)a<bif and only ifb′<a′.

15.48. An elementxin a Boolean algebra is called amaxtermif the identity 1 is its only successor. Find the maxterms in

the Boolean algebraD 210 pictured in Fig. 15-25.

15.49. LetBbe a Boolean algebra.

(a) Show that complements of the atoms ofBare the maxterms.

(b) Show that any elementxinBcan be expressed uniquely as a product of maxterms.

15.50. LetBbe a 16-element Boolean algebra and letSbe an 8-element subalgebra ofB. Show that two of the atoms ofS

must be atoms ofB.

15.51. LetB=(B,+,∗,′, 0 , 1 )be a Boolean algebra. Define an operation
onB(called thesymmetric difference)by

x
y=(x∗y′)+(x′∗y)

Prove thatR=(B, 
,∗)is a commutative Boolean ring. (See Section B.6 and Problem B.72.)

15.52. LetR=(R,⊕,·)be a Boolean ring with identity 1=0. Define

x′= 1 ⊕x, x+y=x⊗y⊕x·y, x∗y=x·y

Prove thatB=(R,+,∗,′, 0 , 1 )is a Boolean algebra.

BOOLEAN EXPRESSIONS, PRIME IMPLICANTS

15.53. Reduce the following Boolean products to either 0 or a fundamental product:

(a)xy′zxy′; (b)xyz′sy′ts; (c)xy′xz′ty′; (d)xyz′ty′t.

15.54. Express each Boolean expressionE(x, y, z)as a sum-of-products and then in its complete sum-of-products form:

(a)E=x(xy′+x′y+y′z); (b)E=(x+y′z)(y+z′); (c)E=(x′+y)′+y′z.

15.55. Express each Boolean expressionE(x, y, z)as a sum-of-products and then in its complete sum-of-products form:

(a)E=(x′y)′(x′+xyz′); (b)E=(x+y)′(xy′)′; (c)E=y(x+yz)′.