Section 12.5 Finite Boolean Algebras as n-tuples of 0's and 1's
¶permalinkFrom the previous section we know that all finite Boolean algebras are of order 2^n\text{,} 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.
permalinkThe simplest nontrivial Boolean algebra is the Boolean algebra on the set B_2=\{0, 1\}\text{.} The ordering on B_2 is the natural one, 0 \leq 0, 0\leq 1, 1\leq 1\text{.} If we treat 0 and 1 as the truth values “false” and “true,” respectively, we see that the Boolean operations \lor (\textrm{join}) and \land (\textrm{meet}) are nothing more than the logical operation with the same symbols. The Boolean operation, -\text{,} (complementation) is the logical \neg (negation). In fact, this is why these symbols were chosen as the names of the Boolean operations. The operation tables for \left[B_2;\lor ,\land, - \right] are simply those of “or,” “and,” and “not,” which we repeat here.
permalinkBy Theorem 12.4.6 and its corollaries, all Boolean algebras of order 2 are isomorphic to this one.
permalinkWe know that if we form B_2\times B_2=B_2^2 we obtain the set \{(0, 0), (0, 1), (1, 0), (1, 1)\}\text{,} a set of order 4. We define operations on B_2^2 the natural way, namely componentwise, so that (0, 1)\lor (1, 1)=(0\lor 1, 1\lor 1)=(1, 1)\text{,} (0, 1)\land (1, 1)=(0\land 1, 1\land 1)=(0, 1) and \overline{(0, 1)} = \left(\bar{0}, \bar{1}\right)=(1, 0)\text{.} We claim that B_2^2 is a Boolean algebra under the componentwise operations. Hence, \left[B_2^2; \lor , \land, \bar{}\hspace{3 pt}\right] 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.
permalinkIt is quite clear that we can describe any Boolean algebra of order 8 by considering B_2\times B_2\times B_2=B_2^3 and, more generally, any Boolean algebra of order 2^n with B_2^n=B_2\times B_2\times \cdots \times B_2 (n factors).
Exercises Exercises
¶1.
Write out the operation tables for \left[B_2^2; \lor , \land, - \right].
Draw the Hasse diagram for \left[B_2^2; \lor , \land, - \right] and compare your results with Figure 10.3.6.
Find the atoms of this Boolean algebra.
- \begin{equation*} \begin{array}{lc} \begin{array}{c|cccc} \lor & (0,0) & (0,1) & (1,0) & (1,1) \\ \hline (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) \\ \end{array} &\\ \begin{array}{c|cccc} \land & (0,0) & (0,1) & (1,0) & (1,1) \\ \hline (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) \\ \end{array} & \begin{array}{c|c} u & \overset{\pmb{\_}}{u} \\ \hline (0,0) & (1,1) \\ (0,1) &(1,0) \\ (1,0) &(0,1) \\ (1,1) &(0,0) \\ \end{array} \\ \end{array} \end{equation*}
The graphs are isomorphic.
(0, 1) and (1,0)
2.
Write out the operation tables for \left[B_2^3; \lor , \land, - \right].
Draw the Hasse diagram for \left[B_2^3; \lor , \land , - \right]
3.
List all atoms of B_2^4\text{.}
Describe the atoms of B_2^n, n \geq 1\text{.}
\((1, 0, 0, 0)\text{,}\) \((0, 1, 0, 0)\text{,}\) \((0, 0, 1, 0)\text{,}\) and \((0, 0, 0, 1)\) are the atoms.
The \(n\)-tuples of bits with exactly one 1.
4.
Theorem 12.4.6 tells us we can think of any finite Boolean algebra in terms of sets. In Chapter 4, we defined minsets 6.3.4 and minset normal form 6.3.9. Rephrase these definitions in the language of Boolean algebra. The generalization of minsets are called minterms.