370 BOOLEAN ALGEBRA [CHAP. 15
15.4Basic Theorems
Using the axioms[B 1 ]through[B 4 ], we prove (Problem 15.5) the following theorem.Theorem 15.2: Leta,b,cbe any elements 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)Theorem 15.2 and our axioms still do not contain all the properties of sets listed in Table 1-1. The next
twotheoremsgive us the remaining properties.
Theorem 15.3: Letabe any element of a Boolean algebraB.
(i) (Uniqueness of Complement) Ifa+x=1 anda∗x=0, thenx=a′.(ii) (Involution law)(a′)′=a.(iii) ( 9 a) 0 ′= 1 .( 9 b) 1 ′=0.Theorem 15.4 (DeMorgan’s laws): ( 10 a) (a+b)′=a′∗b′.( 10 b) (a∗b)′=a′+b′.
We prove these theorems in Problems 15.6 and 15.7.15.5Boolean Algebras as Lattices
By Theorem 15.2 and axiom[B 1 ], every Boolean algebraBsatisfies the associative, commutative, and
absorption laws and hence is a lattice where+and∗are the join and meet operations, respectively. With respect
to this lattice,a+ 1 =1 impliesa≤1 anda∗ 0 =0 implies 0≤a, for any elementa∈B. ThusBis a bounded
lattice. Furthermore, axioms[B 2 ]and[B 4 ]show thatBis also distributive and complemented. Conversely, every
bounded, distributive, and complemented latticeLsatisfies the axioms[B 1 ]through[B 4 ]. Accordingly, we have
the following
Alternate Definition: A Boolean algebraBis a bounded, distributive and complemented lattice.
Since a Boolean algebraBis a lattice, it has a natural partial ordering (and so its diagram can be drawn).
Recall (Chapter 14) that we definea≤bwhen the equivalent conditionsa+b=banda∗b=ahold.
Since we are in a Boolean algebra, we can actually say much more.
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
Thus in a Boolean alegbra we can writea≤bwhenever any of the above four conditions is known to be true.EXAMPLE 15.2
(a) Consider a Boolean algebra of sets. Then setAprecedes setBifAis a subset ofB. Theorem 15.4 states that
ifA⊆Bthen the following conditions hold:
( 1 )A∪B=B( 2 )A∩B=A( 3 )Ac∪B=U ( 4 )A∩Bc=