Processing math: 100%
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

19.2: Boolean Algebras

( \newcommand{\kernel}{\mathrm{null}\,}\)

Let us investigate the example of the power set, P(X), of a set X more closely. The power set is a lattice that is ordered by inclusion. By the definition of the power set, the largest element in P(X) is X itself and the smallest element is , the empty set. For any set A in P(X), we know that AX=A and A=A. This suggests the following definition for lattices. An element I in a poset X is a largest element if aI for all aX. An element O is a smallest element of X if Oa for all aX.

Let A be in P(X). Recall that the complement of A is

A=XA={x:xX and xA}.

We know that AA=X and AA=. We can generalize this example for lattices. A lattice L with a largest element I and a smallest element O is complemented if for each aL, there exists an a such that aa=I and aa=O.

In a lattice L, the binary operations and satisfy commutative and associative laws; however, they need not satisfy the distributive law

a(bc)=(ab)(ac);

however, in P(X) the distributive law is satisfied since

A(BC)=(AB)(AC)

for A,B,CP(X). We will say that a lattice L is distributive if the following distributive law holds:

a(bc)=(ab)(ac)

for all a,b,cL.

Theorem 19.15

A lattice L is distributive if and only if

a(bc)=(ab)(ac)

for all a,b,cL.

Proof

Let us assume that L is a distributive lattice.

a(bc)=[a(ac)](bc)=a[(ac)(bc)]=a[(ca)(cb)]=a[c(ab)]=a[(ab)c]=[(ab)a][(ab)c]=(ab)(ac).

The converse follows directly from the Duality Principle.

A Boolean algebra is a lattice B with a greatest element I and a smallest element O such that B is both distributive and complemented. The power set of X, P(X), is our prototype for a Boolean algebra. As it turns out, it is also one of the most important Boolean algebras. The following theorem allows us to characterize Boolean algebras in terms of the binary relations and without mention of the fact that a Boolean algebra is a poset.

Theorem 19.16

A set B is a Boolean algebra if and only if there exist binary operations and on B satisfying the following axioms.

  1. ab=ba and ab=ba for a,bB.
  2. a(bc)=(ab)c and a(bc)=(ab)c for a,b,cB.

  3. a(bc)=(ab)(ac) and a(bc)=(ab)(ac) for a,b,cB.

  4. There exist elements I and O such that aO=a and aI=a for all aB.
  5. For every aB there exists an aB such that aa=I and aa=O.
Proof

Let B be a set satisfying (1)–(5) in the theorem. One of the idempotent laws is satisfied since

a=aO=a(aa)=(aa)(aa)=(aa)I=aa.

Observe that

Ib=(bb)b=(bb)b=b(bb)=bb=I.

Consequently, the first of the two absorption laws holds, since

a(ab)=(aI)(ab)=a(Ib)=aI=a.

The other idempotent and absorption laws are proven similarly. Since B also satisfies (1)–(3), the conditions of Theorem 19.14 are met; therefore, B must be a lattice. Condition (4) tells us that B is a distributive lattice.

For aB, Oa=a; hence, Oa and O is the smallest element in B. To show that I is the largest element in B, we will first show that ab=b is equivalent to ab=a. Since aI=a for all aB, using the absorption laws we can determine that

aI=(aI)I=I(Ia)=I

or aI for all a in B. Finally, since we know that B is complemented by (5), B must be a Boolean algebra.

Conversely, suppose that B is a Boolean algebra. Let I and O be the greatest and least elements in B, respectively. If we define ab and ab as least upper and greatest lower bounds of {a,b}, then B is a Boolean algebra by Theorem 19.14, Theorem 19.15, and our hypothesis.

Many other identities hold in Boolean algebras. Some of these identities are listed in the following theorem.

Theorem 19.17

Let B be a Boolean algebra. Then

  1. aI=I and aO=O for all aB.
  2. If ab=ac and ab=ac for a,b,cB, then b=c.

  3. If ab=I and ab=O, then b=a.
  4. (a)=a for all aB.
  5. I=O and O=I.
  6. (ab)=ab and (ab)=ab (De Morgan's Laws).
Proof

We will prove only (2). The rest of the identities are left as exercises. For ab=ac and ab=ac, we have

b=b(ba)=b(ab)=b(ac)=(ba)(bc)=(ab)(bc)=(ac)(bc)=(ca)(cb)=c(ab)=c(ac)=c(ca)=c.

Finite Boolean Algebras

A Boolean algebra is a finite Boolean algebra if it contains a finite number of elements as a set. Finite Boolean algebras are particularly nice since we can classify them up to isomorphism.

Let B and C be Boolean algebras. A bijective map ϕ:BC is an isomorphism of Boolean algebras if

ϕ(ab)=ϕ(a)ϕ(b)ϕ(ab)=ϕ(a)ϕ(b)

for all a and b in B.

We will show that any finite Boolean algebra is isomorphic to the Boolean algebra obtained by taking the power set of some finite set X. We will need a few lemmas and definitions before we prove this result. Let B be a finite Boolean algebra. An element aB is an atom of B if aO and ab=a for all bB with bO. Equivalently, a is an atom of B if there is no bB with bO distinct from a such that Oba.

Lemma 19.18

Let B be a finite Boolean algebra. If b is a element of B with bO, then there is an atom a in B such that ab.

Proof

If b is an atom, let a=b. Otherwise, choose an element b1, not equal to O or b, such that b1b. We are guaranteed that this is possible since b is not an atom. If b1 is an atom, then we are done. If not, choose b2, not equal to O or b1, such that b2b1. Again, if b2 is an atom, let a=b2. Continuing this process, we can obtain a chain

Ob3b2b1b.

Since B is a finite Boolean algebra, this chain must be finite. That is, for some k, bk is an atom. Let a=bk.

Lemma 19.19

Let a and b be atoms in a finite Boolean algebra B such that ab. Then ab=O.

Proof

Since ab is the greatest lower bound of a and b, we know that aba. Hence, either ab=a or ab=O. However, if ab=a, then either ab or a=O. In either case we have a contradiction because a and b are both atoms; therefore, ab=O.

Lemma 19.20

Let B be a Boolean algebra and a,bB. The following statements are equivalent.

  1. ab.
  2. ab=O.
  3. ab=I.
Proof

(1) (2). If ab, then ab=b. Therefore,

ab=a(ab)=a(ab)=(aa)b=Ob=O.

(2) (3). If ab=O, then ab=(ab)=O=I.

(3) (1). If ab=I, then

a=a(ab)=(aa)(ab)=O(ab)=ab.

Thus, ab.

Lemma 19.21

Let B be a Boolean algebra and b and c be elements in B such that b⪯̸c. Then there exists an atom aB such that ab and a⪯̸c.

Proof

By Lemma 19.20, bcO. Hence, there exists an atom a such that abc. Consequently, ab and a⪯̸c.

Lemma 19.22

Let bB and a1,,an be the atoms of B such that aib. Then b=a1an. Furthermore, if a,a1,,an are atoms of B such that ab, aib, and b=aa1an, then a=ai for some i=1,,n.

Proof

Let b1=a1an. Since aib for each i, we know that b1b. If we can show that bb1, then the lemma is true by antisymmetry. Assume b⪯̸b1. Then there exists an atom a such that ab and a⪯̸b1. Since a is an atom and ab, we can deduce that a=ai for some ai. However, this is impossible since ab1. Therefore, bb1.

Now suppose that b=a1an. If a is an atom less than b,

a=ab=a(a1an)=(aa1)(aan).

But each term is O or a with aai occurring for only one ai. Hence, by Lemma 19.19, a=ai for some i.

Theorem 19.23

Let B be a finite Boolean algebra. Then there exists a set X such that B is isomorphic to P(X).

Proof

We will show that B is isomorphic to P(X), where X is the set of atoms of B. Let aB. By Lemma 19.22, we can write a uniquely as a=a1an for a1,,anX. Consequently, we can define a map ϕ:BP(X) by

ϕ(a)=ϕ(a1an)={a1,,an}.

Clearly, ϕ is onto.

Now let a=a1an and b=b1bm be elements in B, where each ai and each bi is an atom. If ϕ(a)=ϕ(b), then {a1,,an}={b1,,bm} and a=b. Consequently, ϕ is injective.

The join of a and b is preserved by ϕ since

ϕ(ab)=ϕ(a1anb1bm)={a1,,an,b1,,bm}={a1,,an}{b1,,bm}=ϕ(a1an)ϕ(b1bm)=ϕ(a)ϕ(b).

Similarly, ϕ(ab)=ϕ(a)ϕ(b).

We leave the proof of the following corollary as an exercise.

Corollary 19.24

The order of any finite Boolean algebra must be 2n for some positive integer n.

 


This page titled 19.2: Boolean Algebras is shared under a GNU Free Documentation License 1.3 license and was authored, remixed, and/or curated by Thomas W. Judson (Abstract Algebra: Theory and Applications) via source content that was edited to the style and standards of the LibreTexts platform.

Support Center

How can we help?