390 BOOLEAN ALGEBRA [CHAP. 15
Fig. 15-2515.4. Find the number of subalgebras ofD 210.
A subalgebra ofD 210 must contain two, four, eight or sixteen elements.(i) There can be only one two-element subalgebra which consists of the upper bound 210 and lower bound 1, i.e.,
{ 1 , 210 }.
(ii) SinceD 210 contains sixteen elements, the only sixteen-element subalgebra isD 210 itself.
(iii) Any four-element subalgebra is of the form{ 1 ,x,x′, 210 }, i.e., consists of the upper and lower bounds and a
nonbound element and its complement. There are fourteen nonbound elements inD 210 and so there are 14/ 2 = 7
pairs{x, x′}. ThusD 210 has seven four-element subalgebras.
(iv) Any eight-element subalgebraSwill itself contain three atomss 1 ,s 2 ,s 3. We can chooses 1 ands 2 to be any two
of the four atoms ofD 210 and thens 3 must be the product of the other two atoms, e.g., we can lets 1 =2,s 2 =3,
s 3 = 5 · 7 =35 (which determines the subalgebraBabove), or we can lets 1 =5,s 2 =7,s 3 = 2 · 3 =6 (which
determines the subalgebraCabove). There are( 4
2)
=6 ways to chooses 1 ands 2 from the four atoms ofD 210
and soD 210 has six eight-element subalgebras.Accordingly,D 210 has 1+ 1 + 7 + 6 =15 subalgebras.15.5. Prove Theorem 15.2: Leta,b,cbe any element in a Boolean algebraB.(i) Idempotent laws:
( 5 a) a+a=a( 5 b) a∗a=a
(ii) Boundedness laws:
( 6 a) a+ 1 = 1 ( 6 b) a∗ 0 = 0
(iii) Absorption Laws:
( 7 a) a+(a∗b)=a( 7 b) a∗(a+b)=a
(iv) Associative Laws:
( 8 a) (a+b)+c=a+(b+c) ( 8 b) (a∗b)∗c=a∗(b∗c)( 5 b) a=a∗ 1 =a∗(a+a′)=(a∗a)+(a∗a′)=(a∗a)+ 0 =a∗a
( 5 a) Follows from( 5 b)and duality.
( 6 b) a∗ 0 =(a∗ 0 )+ 0 =(a∗ 0 )+(a∗a′)=a∗( 0 +a′)=a∗(a′+ 0 )=a∗a′= 0
( 6 a) Follows from( 6 b)and duality.
( 7 b) a∗(a+b)=(a+ 0 )∗(a+b)=a+( 0 ∗b)=a+(b∗ 0 )=a+ 0 =a
( 7 a) Follows from( 7 b)and duality.( 8 b) LetL=(a∗b)∗candR=a∗(b∗c). We need to prove thatL=R. We first prove thata+L=a+R.
Using the absorption laws in the last two steps,a+L=a+((a∗b)∗c)=(a+(a∗b))∗(a+c)=a∗(a+c)=a