Discrete Mathematics for Computer Science

Section 12.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 \(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.

The 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.

By Theorem 12.4.6 and its corollaries, all Boolean algebras of order 2 are isomorphic to this one.

We 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.

It 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).