section-boolean-algebras.ipynb

Kernel:

%%html
<link href="http://mathbook.pugetsound.edu/beta/mathbook-content.css" rel="stylesheet" type="text/css" />
<link href="https://aimath.org/mathbook/mathbook-add-on.css" rel="stylesheet" type="text/css" />
<style>.subtitle {font-size:medium; display:block}</style>
<link href="https://fonts.googleapis.com/css?family=Open+Sans:400,400italic,600,600italic" rel="stylesheet" type="text/css" />
<link href="https://fonts.googleapis.com/css?family=Inconsolata:400,700&subset=latin,latin-ext" rel="stylesheet" type="text/css" /><!-- Hide this cell. -->
<script>
var cell = $(".container .cell").eq(0), ia = cell.find(".input_area")
if (cell.find(".toggle-button").length == 0) {
ia.after(
    $('<button class="toggle-button">Toggle hidden code</button>').click(
        function (){ ia.toggle() }
        )
    )
ia.hide()
}
</script>

Important: to view this notebook properly you will need to execute the cell above, which assumes you have an Internet connection. It should already be selected, or place your cursor anywhere above to select. Then press the "Run" button in the menu bar above (the right-pointing arrowhead), or press Shift-Enter on your keyboard.

ParseError: KaTeX parse error: \newcommand{\lt} attempting to redefine \lt; use \renewcommand

Section19.2Boolean Algebras

¶

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

Let $A$ be in ${\mathcal P}(X)\text{.}$ 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\text{.}$ We can generalize this example for lattices. A lattice $L$ with a largest element $I$ and a smallest element $O$ is if for each $a \in L\text{,}$ there exists an $a'$ such that $a \vee a' = I$ and $a \wedge a' = O\text{.}$

In a lattice $L\text{,}$ 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)\text{.}$ We will say that a lattice $L$ is 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\text{.}$

Theorem19.15

A lattice $L$ is distributive if and only if

$$\begin{equation*} a \vee ( b \wedge c ) = ( a \vee b ) \wedge ( a \vee c ) \end{equation*}$$

for all $a, b, c \in L\text{.}$

Proof

Let us assume that $L$ is a distributive lattice.

$$\begin{align*} a \vee ( b \wedge c ) & = [a \vee (a \wedge c) ] \vee ( b \wedge c )\\ & = a \vee [(a \wedge c) \vee ( b \wedge c )]\\ & = a \vee [(c \wedge a) \vee ( c \wedge b )]\\ & = a \vee [c \wedge ( a \vee b )]\\ & = a \vee [( a \vee b ) \wedge c ]\\ & = [( a \vee b ) \wedge a ] \vee [(a \vee b) \wedge c ]\\ & = ( a \vee b ) \wedge ( a \vee c ). \end{align*}$$

The converse follows directly from the Duality Principle.

A 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\text{,}$ ${\mathcal P}(X)\text{,}$ 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.

Theorem19.16

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

1. $a \vee b = b \vee a$ and $a \wedge b = b \wedge a$ for $a, b \in B\text{.}$

2. $a \vee ( b \vee c) = (a \vee b) \vee c$ and $a \wedge ( b \wedge c) = (a \wedge b) \wedge c$ for $a, b, c \in B\text{.}$

3. $a \wedge ( b \vee c ) = (a \wedge b ) \vee ( a \wedge c )$ and $a \vee ( b \wedge c ) = (a \vee b ) \wedge ( a \vee c )$ for $a, b, c \in B\text{.}$

4. There exist elements $I$ and $O$ such that $a \vee O = a$ and $a \wedge I = a$ for all $a \in B\text{.}$

5. For every $a \in B$ there exists an $a' \in B$ such that $a \vee a' = I$ and $a \wedge a' = O\text{.}$

Proof

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

$$\begin{align*} a & = a \vee O\\ & = a \vee (a \wedge a')\\ & = (a \vee a) \wedge (a \vee a')\\ & = (a \vee a ) \wedge I\\ & = a \vee a. \end{align*}$$

Observe that

$$\begin{equation*} I \vee b = (b \vee b' ) \vee b = (b' \vee b ) \vee b = b' \vee (b \vee b) = b' \vee b = I. \end{equation*}$$

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

$$\begin{align*} a \vee (a \wedge b) & = (a \wedge I) \vee (a \wedge b)\\ & = a \wedge (I \vee b)\\ & = a \wedge I\\ & = a. \end{align*}$$

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 $a \in B\text{,}$ $O \vee a = a\text{;}$ hence, $O \preceq a$ and $O$ is the smallest element in $B\text{.}$ To show that $I$ is the largest element in $B\text{,}$ we will first show that $a \vee b = b$ is equivalent to $a \wedge b = a\text{.}$ Since $a \vee I = a$ for all $a \in B\text{,}$ using the absorption laws we can determine that

$$\begin{equation*} a \vee I =(a \wedge I) \vee I = I \vee ( I \wedge a) = I \end{equation*}$$

or $a \preceq I$ for all $a$ in $B\text{.}$ 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\text{,}$ respectively. If we define $a \vee b$ and $a \wedge b$ as least upper and greatest lower bounds of $\{ a, b\}\text{,}$ 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.

Theorem19.17

Let $B$ be a Boolean algebra. Then

1. $a \vee I = I$ and $a \wedge O = O$ for all $a \in B\text{.}$

2. If $a \vee b = a \vee c$ and $a \wedge b = a \wedge c$ for $a, b, c \in B\text{,}$ then $b = c\text{.}$

3. If $a \vee b = I$ and $a \wedge b = O\text{,}$ then $b = a'\text{.}$

4. $(a')'=a$ for all $a \in B\text{.}$

5. $I' = O$ and $O' = I\text{.}$

6. $(a \vee b)' = a' \wedge b'$ and $(a \wedge b)' = a' \vee b'$ (De Morgan's Laws).

Proof

We will prove only (2). The rest of the identities are left as exercises. For $a \vee b = a \vee c$ and $a \wedge b = a \wedge c\text{,}$ we have

$$\begin{align*} b & = b \vee (b \wedge a) \\ & = b \vee (a \wedge b) \\ & = b \vee (a \wedge c) \\ & = ( b \vee a) \wedge ( b \vee c) \\ & = ( a \vee b) \wedge ( b \vee c) \\ & = ( a \vee c) \wedge ( b \vee c) \\ & = ( c \vee a ) \wedge ( c\vee b ) \\ & = c \vee (a \wedge b)\\ & = c \vee ( a \wedge c )\\ & = c \vee ( c \wedge a )\\ & = c. \end{align*}$$

SubsectionFinite Boolean Algebras

¶

A Boolean algebra is a 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 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\text{.}$

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\text{.}$ 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 of $B$ if $a \neq O$ and $a \wedge b = a$ for all nonzero $b \in B\text{.}$ 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\text{.}$

Lemma19.18

Let $B$ be a finite Boolean algebra. If $b$ is a nonzero element of $B\text{,}$ then there is an atom $a$ in $B$ such that $a \preceq b\text{.}$

Proof

If $b$ is an atom, let $a =b\text{.}$ Otherwise, choose an element $b_1\text{,}$ not equal to $O$ or $b\text{,}$ such that $b_1 \preceq b\text{.}$ We are guaranteed that this is possible since $b$ is not an atom. If $b_1$ is an atom, then we are done. If not, choose $b_2\text{,}$ not equal to $O$ or $b_1\text{,}$ such that $b_2 \preceq b_1\text{.}$ Again, if $b_2$ is an atom, let $a = b_2\text{.}$ Continuing this process, we can obtain a chain

$$\begin{equation*} O \preceq \cdots \preceq b_3 \preceq b_2 \preceq b_1 \preceq b. \end{equation*}$$

Since $B$ is a finite Boolean algebra, this chain must be finite. That is, for some $k\text{,}$ $b_k$ is an atom. Let $a = b_k\text{.}$

Lemma19.19

Let $a$ and $b$ be atoms in a finite Boolean algebra $B$ such that $a \neq b\text{.}$ Then $a \wedge b = O\text{.}$

Proof

Since $a \wedge b$ is the greatest lower bound of $a$ and $b\text{,}$ we know that $a \wedge b \preceq a\text{.}$ Hence, either $a \wedge b = a$ or $a \wedge b = O\text{.}$ However, if $a \wedge b = a\text{,}$ then either $a \preceq b$ or $a = O\text{.}$ In either case we have a contradiction because $a$ and $b$ are both atoms; therefore, $a \wedge b = O\text{.}$

Lemma19.20

Let $B$ be a Boolean algebra and $a, b \in B\text{.}$ The following statements are equivalent.

1. $a \preceq b\text{.}$

2. $a \wedge b' = O\text{.}$

3. $a' \vee b = I\text{.}$

Proof

(1) $\Rightarrow$ (2). If $a \preceq b\text{,}$ then $a \vee b = b\text{.}$ Therefore,

$$\begin{align*} a \wedge b' & = a \wedge (a \vee b)'\\ & = a \wedge ( a' \wedge b')\\ & = ( a \wedge a') \wedge b'\\ & = O \wedge b'\\ & = O. \end{align*}$$

(2) $\Rightarrow$ (3). If $a \wedge b' = O\text{,}$ then $a' \vee b = (a \wedge b')' = O' = I\text{.}$

(3) $\Rightarrow$ (1). If $a' \vee b = I\text{,}$ then

$$\begin{align*} a & = a \wedge (a' \vee b) \\ & = (a \wedge a') \vee (a \wedge b)\\ & = O \vee (a \wedge b)\\ & = a \wedge b. \end{align*}$$

Thus, $a \preceq b\text{.}$

Lemma19.21

Let $B$ be a Boolean algebra and $b$ and $c$ be elements in $B$ such that $b \not\preceq c\text{.}$ Then there exists an atom $a \in B$ such that $a \preceq b$ and $a \not\preceq c\text{.}$

Proof

By Lemma 19.20, $b \wedge c' \neq O\text{.}$ Hence, there exists an atom $a$ such that $a \preceq b \wedge c'\text{.}$ Consequently, $a \preceq b$ and $a \not\preceq c\text{.}$

Lemma19.22

Let $b \in B$ and $a_1, \ldots, a_n$ be the atoms of $B$ such that $a_i \preceq b\text{.}$ Then $b = a_1 \vee \cdots \vee a_n\text{.}$ Furthermore, if $a, a_1, \ldots, a_n$ are atoms of $B$ such that $a \preceq b\text{,}$ $a_i \preceq b\text{,}$ and $b = a \vee a_1 \vee \cdots \vee a_n\text{,}$ then $a = a_i$ for some $i = 1, \ldots, n\text{.}$

Proof

Let $b_1 = a_1 \vee \cdots \vee a_n\text{.}$ Since $a_i \preceq b$ for each $i\text{,}$ we know that $b_1 \preceq b\text{.}$ If we can show that $b \preceq b_1\text{,}$ then the lemma is true by antisymmetry. Assume $b \not\preceq b_1\text{.}$ Then there exists an atom $a$ such that $a \preceq b$ and $a \not\preceq b_1\text{.}$ Since $a$ is an atom and $a \preceq b\text{,}$ we can deduce that $a = a_i$ for some $a_i\text{.}$ However, this is impossible since $a \preceq b_1\text{.}$ Therefore, $b \preceq b_1\text{.}$

Now suppose that $b = a_1 \vee \cdots \vee a_n\text{.}$ If $a$ is an atom less than $b\text{,}$

$$\begin{equation*} a = a \wedge b = a \wedge( a_1 \vee \cdots \vee a_n ) = (a \wedge a_1) \vee \cdots \vee ( a \wedge a_n ). \end{equation*}$$

But each term is $O$ or $a$ with $a \wedge a_i$ occurring for only one $a_i\text{.}$ Hence, by Lemma 19.19, $a = a_i$ for some $i\text{.}$

Theorem19.23

Let $B$ be a finite Boolean algebra. Then there exists a set $X$ such that $B$ is isomorphic to ${\mathcal P}(X)\text{.}$

Proof

We will show that $B$ is isomorphic to ${\mathcal P}(X)\text{,}$ where $X$ is the set of atoms of $B\text{.}$ Let $a \in B\text{.}$ By Lemma 19.22, we can write $a$ uniquely as $a = a_1 \vee \cdots \vee a_n$ for $a_1, \ldots, a_n \in X\text{.}$ Consequently, we can define a map $\phi : B \rightarrow {\mathcal P}(X)$ by

$$\begin{equation*} \phi(a) = \phi( a_1 \vee \cdots \vee a_n ) = \{a_1, \ldots, a_n \}. \end{equation*}$$

Clearly, $\phi$ is onto.

Now let $a = a_1 \vee \cdots \vee a_n$ and $b = b_1 \vee \cdots \vee b_m$ be elements in $B\text{,}$ where each $a_i$ and each $b_i$ is an atom. If $\phi(a) = \phi(b)\text{,}$ then $\{a_1, \ldots, a_n \} = \{b_1, \ldots, b_m \}$ and $a = b\text{.}$ Consequently, $\phi$ is injective.

The join of $a$ and $b$ is preserved by $\phi$ since

$$\begin{align*} \phi(a \vee b) & = \phi( a_1 \vee \cdots \vee a_n \vee b_1 \vee \cdots \vee b_m )\\ & = \{ a_1, \ldots, a_n, b_1, \ldots, b_m \}\\ & = \{ a_1, \ldots, a_n \} \cup \{ b_1, \ldots, b_m \}\\ & = \phi( a_1 \vee \cdots \vee a_n ) \cup \phi( b_1 \wedge \cdots \vee b_m )\\ & = \phi(a) \cup \phi(b). \end{align*}$$

Similarly, $\phi( a \wedge b ) = \phi(a) \cap \phi(b)\text{.}$

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

Corollary19.24

The order of any finite Boolean algebra must be $2^n$ for some positive integer $n\text{.}$