Skip to main content

Section 12.3 Boolean Algebras

In order to define a Boolean algebra, we need the additional concept of complementation. A lattice must have both a greatest element and a least element in order for complementation to take place. The following definition will save us some words in the rest of this section.

Definition 12.3.1. Bounded Lattice.

A bounded lattice is a lattice that contains both a least element and a greatest element.

We use the symbols \(\pmb{0}\) and \(\pmb{1}\) for the least and greatest elements of a bounded lattice in the remainder of this section.

Definition 12.3.2. The Complement of a Lattice Element.

Let \([L; \lor ,\land ]\) be a bounded lattice. If \(a \in L\text{,}\) then \(a\) has a complement if there exists \(b \in L\) such that

\begin{equation*} \begin{array}{c} a \lor b = \pmb{1}\\ \textrm{and}\\ a \land b =\pmb{0}\\ \end{array} \end{equation*}

Notice that by the commutative laws for lattices, if \(b\) complements \(a\text{,}\) then \(a\) complements \(b\text{.}\)

Definition 12.3.3. Complemented Lattice.

Let \(\mathcal{L}=[L; \lor ,\land ]\) be a bounded lattice. \(\mathcal{L}\) is a complemented lattice if every element of \(L\) has a complement in \(L\text{.}\)

In Chapter 1, we defined the complement of a subset of any universe. This turns out to be a concrete example of the general concept we have just defined, but we will reason through why this is the case here. Let \(L = \mathcal{P}(A)\text{,}\) where \(A = \{a, b, c\}\text{.}\) Then \([L; \cup , \cap ]\) is a bounded lattice with \(0 = \emptyset\) and \(1 = A\text{.}\) To find the complement, if it exists, of \(B = \{a, b\} \in L\text{,}\) for example, we want \(D\) such that

\begin{equation*} \begin{array}{c} \{a,b\} \cap D = \emptyset\\ and\\ \{a,b\} \cup D = A\\ \end{array} \end{equation*}

It's not too difficult to see that \(D = \{c\}\text{,}\) since we need to include \(c\) to make the first condition true and can't include \(a\) or \(b\) if the second condition is to be true. Of course this is precisely how we defined \(A^c\) in Chapter 1. Since it can be shown that each element of \(L\) has a complement (see Exercise 1), \([L; \cup , \cap ]\) is a complemented lattice. Note that if \(A\) is any set and \(L = \mathcal{P}(A)\text{,}\) then \([L; \cup , \cap ]\) is a complemented lattice where the complement of \(B \in L\) is \(B ^c = A - B\text{.}\)

In Example 12.3.4, we observed that the complement of each element of \(L\) is unique. Is this always true in a complemented lattice? The answer is no. Consider the following.

Let \(L = \{1, 2, 3, 5, 30\}\) and consider the lattice \([L; \lor, \land ]\) (under “divides”). The least element of \(L\) is 1 and the greatest element is 30. Let us compute the complement of the element \(a = 2\text{.}\) We want to determine \(\bar{a}\) such that \(2 \land \bar{a} = 1\) and \(2 \lor \bar{a} = 30\text{.}\) Certainly, \(\bar{a} = 3\) works, but so does \(\bar{a} = 5\text{,}\) so the complement of \(a = 2\) in this lattice is not unique. However, \([L; \lor , \land ]\) is still a complemented lattice since each element does have at least one complement.

Definition 12.3.6. Complementation as an operation.

If a complemented lattice has the property that the complement of every element is unique, then we consider complementation to be a unary operation. The usual notation for the complement of \(a\) is \(\bar{a}\text{.}\)

The following theorem gives us an insight into when uniqueness of complements occurs.

Let \(a \in L\) and assume to the contrary that \(a\) has two complements, namely \(a_1\) and \(a_2\text{.}\) Then by the definition of complement,

\begin{equation*} \begin{array}{c} a \land a_1 = 0\textrm{ and }a \lor a_1 = 1, \\ and\\ a \land a_2 = 0\textrm{ and }a \lor a_2 = 1, \\ \end{array}\text{.} \end{equation*}

Then

\begin{equation*} \begin{split} a_1 & =a_1 \land \pmb{1} = a_1 \land \left(a \lor a_2\right)\\ &=\left(a_1 \land a\right) \lor \left(a_1 \land a_2\right)\\ &=\pmb{0} \lor \left(a_1 \land a_2\right)\\ &=a_1 \land a_2\\ \\ \end{split} \end{equation*}

On the other hand,

\begin{equation*} \begin{split} a_2 &= a_2 \land \pmb{1} = a_2 \land \left(a \lor a_1\right)\\ &= \left(a_2 \land a\right) \lor \left(a_2 \land a_1\right)\\ &= \pmb{0} \lor \left(a_2 \land a_1\right)\\ &= a_2 \land a_1\\ &= a_1 \land a_2\\ \\ \end{split} \end{equation*}

Hence \(a_1 = a_2\text{,}\) which contradicts the assumption that \(a\) has two different complements.

Definition 12.3.8. Boolean Algebra.

A Boolean algebra is a lattice that contains a least element and a greatest element and that is both complemented and distributive. The notation \([B; \lor , \land, \bar{\hspace{5 mm}}]\) is used to denote the Boolean algebra with operations disjunction, conjunction and complementation.

Since the complement of each element in a Boolean algebra is unique (by Theorem 12.3.7), complementation is a valid unary operation over the set under discussion, which is why we will list it together with the other two operations to emphasize that we are discussing a set together with three operations. Also, to help emphasize the distinction between lattices and lattices that are Boolean algebras, we will use the letter \(B\) as the generic symbol for the set of a Boolean algebra; that is, \([B; \lor , \land, \bar{\hspace{5 mm}} ]\) will stand for a general Boolean algebra.

Let \(A\) be any set, and let \(B = \mathcal{P}(A)\text{.}\) Then \([B; \cup, \cap, {}^c]\) is a Boolean algebra. Here, \({}^c\) stands for the complement of an element of \(B\) with respect to \(A\text{,}\) \(A-B\text{.}\)

This is a key example for us since all finite Boolean algebras and many infinite Boolean algebras look like this example for some \(A\text{.}\) In fact, a glance at the basic Boolean algebra laws in Table 12.3.11, in comparison with the set laws of Chapter 4 and the basic laws of logic of Chapter 3, indicates that all three systems behave the same; that is, they are isomorphic.

A somewhat less standard example of a Boolean algebra is derived from the lattice of divisors of 30 under the relation “divides”. If you examine the ordering diagram for this lattice, you see that it is structurally the same as the Boolean algebra of subsets of a three element set. Therefore, the join, meet and complementation operations act the same as union, intersection and set complementation. We might conjecture that the lattice of divisors of any integer will produce a Boolean algebra, but it is only the case of certain integers. Try out a few integers to see if you can identify what is necessary to produce a Boolean algebra.

Commutative Laws \(a\lor b = b\lor a\) \(a \land b = b \land a \)
Associative Laws \(a \lor (b \lor c) = (a \lor b) \lor c \) \(a \land (b \land c) = (a \land b) \land c\)
Distributive Laws \(a \land (b \lor c) = (a \land b) \lor (a \land c)\) \(a \lor (b \land c) = (a \lor b) \land (a \lor c)\)
Identity Laws \(a \lor 0 = 0 \lor a = a\) \(a \land 1= 1 \land a = a\)
Complement Laws \(a \lor \bar{a} = 1 \) \(a \land \bar{a}= 0\)
Idempotent Laws \(a \lor a = a\) \(a \land a = a\)
Null Laws \(a \lor 1 = 1\) \(a \land 0 = 0 \)
Absorption Laws \(a \lor (a \land b) = a\) \(a \land (a \lor b) = a \)
DeMorgan's Laws \(\overline{a \lor b} = \bar{a} \land \bar{b}\) \(\overline{a \land b} = \bar{a} \lor \bar{b} \)
Involution Law \(\overline{\bar{a}} = a\) \(\quad\)
Table 12.3.11. Basic Boolean Algebra Laws

The “pairings” of the Boolean algebra laws reminds us of the principle of duality, which we state for a Boolean algebra.

Definition 12.3.12. Principle of Duality for Boolean Algebras.

Let \(\mathcal{B}=[B; \lor, \land, \hspace{1 mm}^c]\) be a Boolean algebra under \(\preceq\text{,}\) and let \(S\) be a true statement for \(\mathcal{B}\text{.}\) If \(S^*\) is obtained from \(S\) by replacing \(\preceq\) with \(\succeq\) (this is equivalent to turning the graph upside down), \(\lor\) with \(\land\text{,}\) \(\land\) with \(\lor\text{,}\) \(\pmb{0}\) with \(\pmb{1}\text{,}\) and \(\pmb{1}\) with \(\pmb{0}\text{,}\) then \(S^*\) is also a true statement in \(\mathcal{B}\text{.}\)

We close this section with some comments on notation. The notation for operations in a Boolean algebra is derived from the algebra of logic. However, other notational systems are used. These are summarized in the following chart.

Generic/Logic Set Theory Arithmetic Verbal
\(\lor\) \(\cup\) \(+\) Join
\(\land\) \(\cap\) \(\cdot\) Meet
\(\bar{\hspace{5 mm}}\) \(\hspace{1 mm}^c\) - or \(\bar{\hspace{5 mm}}\) Complement
\(\preceq\) \(\subseteq\) \(\leq\) partial ordering
Table 12.3.13. Contrasting Notational Systems for Boolean Algebra

Mathematicians most frequently use the generic or logic notation, and, on occasion, use set notation for Boolean algebras. Thinking in terms of sets may be easier for some people. Computer designers traditionally use the arithmetic notation. In this latter notation, DeMorgan's Laws become:

\begin{equation*} \begin{array}{ccc} \overline{a + b} = \bar{a} \cdot \bar{b} & \textrm{ and }& \overline{a \cdot b} = \bar{a} + \bar{b}\\ \end{array} \end{equation*}

Exercises Exercises

1.

Determine the complement of each element \(B \in L\) in Example 12.3.4. Is this lattice a Boolean algebra? Why?

Answer

\(\begin{array}{cc} B & \textrm{ Complement of } B \\ \hline \begin{array}{c} \emptyset \\ \{a\} \\ \{b\} \\ \{c\} \\ \{a,b\} \\ \{a,c\} \\ \{b,c\} \\ A \\ \end{array} & \begin{array}{c} A \\ \{b,c\} \\ \{a,c\} \\ \{a,b\} \\ \{c\} \\ \{b\} \\ \{a\} \\ \emptyset \\ \end{array} \\ \end{array}\)

This lattice is a Boolean algebra since it is a distributive complemented lattice.

2.

  1. Determine the complement of each element of \(D_6\) in \(\left[D_6; \lor , \land \right]\text{.}\)

  2. Repeat part a using the lattice in Example 12.2.5.

  3. Repeat part a using the lattice in Exercise 12.1.1.

  4. Are the lattices in parts a, b, and c Boolean algebras? Why?

4.

Let \(A = \{a, b\}\) and \(B = \mathcal{P}(A)\text{.}\)

  1. Prove that \([B; \cup, \cap, \hspace{1 mm}^c ]\) is a Boolean algebra.

  2. Write out the operation tables for the Boolean algebra.

5.

It can be shown that the following statement, \(S\text{,}\) holds for any Boolean algebra \([B; \lor , \land, -]\) : \((a \land b) = a\) if and only if \(a \leq b\text{.}\)

  1. Write the dual, \(S^*\text{,}\) of the statement \(S\text{.}\)

  2. Write the statement \(S\) and its dual, \(S^*\text{,}\) in the language of sets.

  3. Are the statements in part b true for all sets?

  4. Write the statement \(S\) and its dual, \(S^*\text{,}\) in the language of logic.

  5. Are the statements in part d true for all propositions?

Answer

  1. \(S^*:a \lor b= a \textrm{ if } a \geq b\)

  2. The dual of \(S:A\cap B = A\textrm{ if }A \subseteq B\) is \(S^*:A \cup B = A\textrm{ if } A \supseteq B\)

  3. Yes

  4. The dual of \(S:p \land q\Leftrightarrow p\textrm{ }\textrm{ if } p\Rightarrow q\) is \(S^*:p \lor q\Leftrightarrow p \textrm{ if } q\Rightarrow p\)

  5. Yes

6.

State the dual of:

  1. \(a \lor (b \land a) = a\text{.}\)

  2. \(a \lor \left(\overline{\left(\bar{b} \lor a\right) \land b}\right) = 1\text{.}\)

  3. \(\left(\overline{a \land \bar{b}}\right) \land b = a\lor b\text{.}\)

7.

Formulate a definition for isomorphic Boolean algebras.

Answer

\([B; \land, \lor, -]\) is isomorphic to \([B';\land, \lor, \tilde{}]\) if and only if there exists a function \(T:B \to B'\) such that

  1. \(T\) is a bijection;

  2. \(T(a\land b)=T(a)\land T(b)\quad \textrm{ for} \textrm{ all } a,b\in B\)

  3. \(T(a\lor b)=T(a)\lor T(b)\quad \textrm{ for} \textrm{ all } a, b \in B\)

  4. \(T(\bar{a})=\tilde{T(a)}\quad \textrm{ for all } a\in B\text{.}\)

8.

For what positive integers, \(n\text{,}\) does the lattice \([D_n,\mid]\) produce a Boolean algebra?

login