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}} \renewcommand{\vec}[1]{\mathbf{#1}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

Section13.3Boolean 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 definiton will save us some words in the rest of this section.

Definition13.3.1Bounded 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.

Definition13.3.2The Complement of a Lattice Element

Let \([L; \lor ,\land ]\) be a bounded lattice. If \(a \in L\), then \(a\) has a complement if there exists \(b \in L\) such that \begin{equation*} \begin{array}{c} a \lor b = \pmb{1}\\ and\\ a \land b =\pmb{0}\\ \end{array} \end{equation*}

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

Definition13.3.3Complemented 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\).

Example13.3.4Set Complement is a Complement

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)\), where \(A = \{a, b, c\}\). Then \([L; \cup , \cap ]\) is a bounded lattice with \(0 = \emptyset\) and \(1 = A\). To find the complement, if it exists, of \(B = \{a, b\} \in L\), 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\}\), 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)\), then \([L; \cup , \cap ]\) is a complemented lattice where the complement of \(B \in L\) is \(B ^c = A - B\).

In Example 13.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.

Example13.3.5A Lattice for which complements are not unique

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\). We want to determine \(\bar{a}\) such that \(2 \land \bar{a} = 1\) and \(2 \lor \bar{a} = 30\). Certainly, \(\bar{a} = 3\) works, but so does \(\bar{a} = 5\), 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.

Definition13.3.6Complementation 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}\).

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

Proof
Definition13.3.8Boolean 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, conjuction and complementation.

Since the complement of each element in a Boolean algebra is unique (by Theorem 13.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.

Example13.3.9Boolean Algebra of Sets

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

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

Example13.3.10Divisors of 30

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 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\)
Table13.3.11Basic Boolean Algebra Laws

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

Definition13.3.12Principle of Duality for Boolean Algebras

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

Subsection13.3.1Exercises for Section 13.3

1

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

Answer
2

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

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

  3. Repeat part a using the lattice in Exercise 13.1.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)\).

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

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

  2. Write the statement \(S\) and its dual, \(S^*\), 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^*\), in the language of logic.

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

Answer
6

State the dual of:

  1. \(a \lor (b \land a) = a\).

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

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

7

Formulate a definition for isomorphic Boolean algebras.

Answer
8

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