Skip to main content
\(\newcommand{\identity}{\mathrm{id}} \newcommand{\notdivide}{{\not{\mid}}} \newcommand{\notsubset}{\not\subset} \newcommand{\lcm}{\operatorname{lcm}} \newcommand{\gf}{\operatorname{GF}} \newcommand{\inn}{\operatorname{Inn}} \newcommand{\aut}{\operatorname{Aut}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\cis}{\operatorname{cis}} \newcommand{\chr}{\operatorname{char}} \newcommand{\Null}{\operatorname{Null}} \newcommand{\lt}{ < } \newcommand{\gt}{ > } \newcommand{\amp}{ & } \)

Section19.2Boolean Algebras

Let us investigate the example of the power set, \({\mathcal 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 \({\mathcal P}(X)\) is \(X\) itself and the smallest element is \(\emptyset\), the empty set. For any set \(A\) in \({\mathcal P}(X)\), we know that \(A \cap X = A\) and \(A \cup \emptyset = A\). This suggests the following definition for lattices. An element \(I\) in a poset \(X\) is a largest element if \(a \preceq I\) for all \(a \in X\). An element \(O\) is a smallest element of \(X\) if \(O \preceq a\) for all \(a \in X\).

Let \(A\) be in \({\mathcal P}(X)\). Recall that the complement of \(A\) is \begin{equation*}A' = X \setminus A = \{ x : x \in X \text{ and } x \notin A \}.\end{equation*} We know that \(A \cup A' = X\) and \(A \cap A' = \emptyset\). 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 \(a \in X\), there exists an \(a'\) such that \(a \vee a' = I\) and \(a \wedge a' = O\).

In a lattice \(L\), the binary operations \(\vee\) and \(\wedge\) satisfy commutative and associative laws; however, they need not satisfy the distributive law \begin{equation*}a \wedge ( b \vee c ) = (a \wedge b ) \vee ( a \wedge c );\end{equation*} however, in \({\mathcal P}(X)\) the distributive law is satisfied since \begin{equation*}A \cap ( B \cup C ) = (A \cap B ) \cup ( A \cap C )\end{equation*} for \(A, B, C \in {\mathcal P}(X)\). We will say that a lattice \(L\) is distributive if the following distributive law holds: \begin{equation*}a \wedge ( b \vee c ) = (a \wedge b ) \vee ( a \wedge c )\end{equation*} for all \(a, b, c \in L\).

Proof

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\), \({\mathcal 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 \(\vee\) and \(\wedge\) without mention of the fact that a Boolean algebra is a poset.

Proof

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

Proof

SubsectionFinite 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 \(\phi : B \rightarrow C\) is an isomorphism of Boolean algebras if \begin{align*} \phi( a \vee b ) & = \phi(a) \vee \phi(b)\\ \phi( a \wedge b ) & = \phi(a) \wedge \phi(b) \end{align*} 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 \(a \in B\) is an atom of \(B\) if \(a \neq O\) and \(a \wedge b = a\) for all nonzero \(b \in B\). Equivalently, \(a\) is an atom of \(B\) if there is no nonzero \(b \in B\) distinct from \(a\) such that \(O \preceq b \preceq a\).

Proof

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