CHAP. 15] BOOLEAN ALGEBRA 371
(b) Consider the Boolean algebraD 70. Thenaprecedesbifadividesb. In such a case, lcm(a, b)=band
gcd(a, b)=a. For example, leta=2 andb=14. Then the following conditions hold:
( 1 ) lcm( 2 , 14 )= 14 .( 3 ) lcm( 2 ′, 14 )=lcm( 35 , 14 )= 70.
( 2 ) gcd( 2 , 14 )= 2 .( 4 ) gcd( 2 , 14 ′)=gcd( 2 , 5 )= 1.15.6Representation Theorem
LetBbe a finite Boolean algebra. Recall (Section 14.10) that an elementainBis an atom ifaimmediately
succeeds 0, that is if 0/a. LetAbe the set of atoms ofBand letP (A)be the Boolean algebra of all subsets of
the setAof atoms. By Theorem 14.8, eachx=0inBcan be expressed uniquely (except for order) as the sum
( join) of atoms, i.e., elements ofA. Say,
x=a 1 +a 2 +···+aris such a representation. Consider the functionf:B→P (A)defined by
f(x)={a 1 ,a 2 ,...,ar}The mapping is well defined since the representation is unique.
Theorem 15.6: The above mappingf:B→P (A)is an isomorphism.
Thus we see the intimate relationship between set theory and abstract Boolean algebras in the sense that
every finite Boolean algebra is structurally the same as a Boolean algebra of sets.
If a setAhasnelements, then its power setP (A)has 2nelements. Thus the above theorem gives us our
next result.
Corollary 15.7: A finite Boolean algebra has 2nelements for some positive integern.
EXAMPLE 15.3 Consider the Boolean algebraD 70 ={ 1 , 2 , 5 ,..., 70 }whose diagram is given in Fig. 15-2(a).
Note thatA={ 2 , 5 , 7 }is the set of atoms ofD 70. The following is the unique representation of each nonatom
by atoms:
10 = 2 ∨ 5 , 14 = 2 ∨ 7 , 35 = 5 ∨ 7 , 70 = 2 ∨ 5 ∨ 7
Figure 15-2(b)gives the diagram of the Boolean algebra of the power setP (A)of the setAof atoms. Observe
that the two diagrams are structurally the same.
Fig. 15-215.7Sum-of-Products Form for Sets
This section motivates the concept of the sum-of-products form in Boolean algebra by an example of set
theory. Consider the Venn diagram in Fig. 15-3 of three setsA,B, andC. Observe that these sets partition the