Skip to main content
Logo image

Applied Discrete Structures

Al Doerr, Ken Levasseur

🔗

Section 13.5 Finite Boolean Algebras as n-tuples of 0’s and 1’s

🔗
From the previous section we know that all finite Boolean algebras are of order 2n, where n is the number of atoms in the algebra. We can therefore completely describe every finite Boolean algebra by the algebra of power sets. Is there a more convenient, or at least an alternate way, of defining finite Boolean algebras? In Chapter 11 we found that we could produce new groups by taking Cartesian products of previously known groups. We imitate this process for Boolean algebras.
🔗
🔗
The simplest nontrivial Boolean algebra is the Boolean algebra on the set B2={0,1}. The ordering on B2 is the natural one, 0≤0,0≤1,1≤1. If we treat 0 and 1 as the truth values “false” and “true,” respectively, we see that the Boolean operations ∨(join) and ∧(meet) are nothing more than the logical operation with the same symbols. The Boolean operation, −, (complementation) is the logical ¬ (negation). In fact, this is why these symbols were chosen as the names of the Boolean operations. The operation tables for [B2;∨,∧,−] are simply those of “or,” “and,” and “not,” which we repeat here.
∨01001111∧01000101uu−0110
🔗
By Theorem 13.4.6 and its corollaries, all Boolean algebras of order 2 are isomorphic to this one.
🔗
We know that if we form B2×B2=B22 we obtain the set {(0,0),(0,1),(1,0),(1,1)}, a set of order 4. We define operations on B22 the natural way, namely componentwise, so that (0,1)∨(1,1)=(0∨1,1∨1)=(1,1), (0,1)∧(1,1)=(0∧1,1∧1)=(0,1) and (0,1)―=(0¯,1¯)=(1,0). We claim that B22 is a Boolean algebra under the componentwise operations. Hence, [B22;∨,∧,¯] is a Boolean algebra of order 4. Since all Boolean algebras of order 4 are isomorphic to one other, we have found a simple way of describing all Boolean algebras of order 4.
🔗
It is quite clear that we can describe any Boolean algebra of order 8 by considering B2×B2×B2=B23 and, more generally, any Boolean algebra of order 2n with B2n=B2×B2×⋯×B2 (n factors).
🔗

Exercises Exercises

🔗

1.

🔗
  1. Write out the operation tables for [B22;∨,∧,−].
  2. Draw the Hasse diagram for [B22;∨,∧,−] and compare your results with Figure 6.3.6.
  3. Find the atoms of this Boolean algebra.
Answer.
  1. ∨(0,0)(0,1)(1,0)(1,1)(0,0)(0,0)(0,1)(1,0)(1,1)(0,1)(0,1)(0,1)(1,1)(1,1)(1,0)(1,0)(1,1)(1,0)(1,1)(1,1)(1,1)(1,1)(1,1)(1,1)∧(0,0)(0,1)(1,0)(1,1)(0,0)(0,0)(0,0)(0,0)(0,0)(0,1)(0,0)(0,1)(0,0)(0,1)(1,0)(0,0)(0,0)(1,0)(1,0)(1,1)(0,0)(0,1)(1,0)(1,1)uu__(0,0)(1,1)(0,1)(1,0)(1,0)(0,1)(1,1)(0,0)
  2. The graphs are isomorphic.
  3. (0, 1) and (1,0)
🔗

2.

🔗
  1. Write out the operation tables for [B23;∨,∧,−].
  2. Draw the Hasse diagram for [B23;∨,∧,−]
🔗

3.

🔗
  1. List all atoms of B24.
  2. Describe the atoms of B2n,n≥1.
Answer.
  1. (1,0,0,0), (0,1,0,0), (0,0,1,0), and (0,0,0,1) are the atoms.
  2. The n-tuples of bits with exactly one 1.
You have attempted 1 of 1 activities on this page.
PrevTopNext