Section 11.1 Boolean algebras
A long time ago, we learned about sets and statements. In both cases, there were operations we could perform on the objects to yield new objects. It may have struck you at the time that there was something eerily similar between the two different settings. In this chapter, we will finally put a name to that similarity.
It is fitting that we have this discussion now, at the beginning of the fourth part of this book. Part IV is all about relations between mathematical objects, and in this part we will scratch the surface of the powerful idea of equivalence. We will see that many of the different objects we have studied are in some sort of sense “the same” object. The ability to see past superficial differences and find the core structure underneath is one of the most important abilities in the mathematician's kit.
Definition 11.1.1.
A bit is a member of the set \(\{0,1\}\) endowed with the binary operations \(\wedge\) (called meet), \(\vee\) (join), and the unary operation \(\neg\) (complement) such that for all \(x \in \{0,1\}\text{:}\)
\(\displaystyle 0 \vee x = x\)
\(\displaystyle 0 \wedge x = 0\)
\(\displaystyle 1 \vee x = 1\)
\(\displaystyle 1 \wedge x = x\)
and, \(\neg 0 = 1\) and \(\neg 1 = 0\text{.}\)
The above definition is easier to understand if you pretend that \(\vee\text{,}\) \(\wedge\text{,}\) and \(\neg\) are their logical counterparts disjunction, conjunction, and negation; that \(0\) is the contradiction \(F\text{,}\) and that \(1\) is the tautology \(T\text{.}\)
The set \(\{0,1\}\) of bits is the smallest “non-degenerate” Boolean algebra. There are many others. Before we go any further, you may be confused by the talk of “an algebra”. Isn't there just “algebra”, the study of solving equations using the operations of real numbers? In general, the study of algebra is the study of operations on a set of elements. However, an algebra is a specific sort of mathematical structure where (basically) there are two operations that interact with one another. In the case of a Boolean algebra those two operations are meet and join.
Definition 11.1.2.
A Boolean algebra \(\mathscr{A}\) is a set of objects including the bits \(\{0,1\}\) together with the binary operations meet, join, and the unary operation complement, such that for all \(a,b,c \in \mathscr{A}\) the following six axioms hold:
| Associativity | \(a \vee (b \vee c) = (a \vee b) \vee c\) | \(a \wedge (b \wedge c) = (a \wedge b) \wedge c\) |
| Commutativity | \(a \vee b = b \vee a\) | \(a \wedge b = b \wedge a\) |
| Absorption | \(a \wedge 0 = 0\) | \(a \vee 1 = 1\) |
| Identity | \(a \vee 0 = a\) | \(a \wedge 1 = a\) |
| Inverse | \(a \vee \neg a = 1\) | \(a \wedge \neg a = 0\) |
| Distributivity | \(a \vee (b \wedge c) = (a \vee b) \wedge (a \vee c)\) | \(a \wedge (b \vee c) = (a \wedge b) \vee (a \wedge c)\) |
Sometimes \(0\) is called the “bottom” element and \(1\) is called the “top” element.
Once again, it may help if you recall that these six axioms are all laws of logic that we encountered back in Chapter 2.
Example 11.1.3.
Let \(\Omega\) be a non-empty set. Then the power set \(\mathscr{P}(\Omega)\) is a Boolean algebra where \(\cup\) is the join operator, \(\cap\) is the meet, and \(\overline{A}\) is the complement of the element \(A\) if \(A \in \mathscr{P}(\Omega)\text{.}\) The “top” element playing the role of \(1\) is \(\Omega\) itself and the “bottom” element playing the role of \(0\) is \(\varnothing\text{.}\)
Example 11.1.4.
Fix a positive integer \(n\) and consider the collection \(\mathscr{S}_n\) of all the statements up to equivalence that can be made from the set of statements \(\{p_1, p_2, \ldots, p_n\}\text{.}\) In other words, since \(p_1 \to p_2\) and \(\neg p_1 \vee p_2\) are equivalent to each other, only one is chosen to “represent” those equivalent statements (more on this in a few chapters).
Anyway, the collection \(\mathscr{S}_n\) of such statements is a Boolean algebra, where meet, join, and complement are replaced by the logical operations of conjunction, disjunction, and negation; and \(T\) is the top element and \(F\) is the bottom element. The tautology \(T\) can be represented by the statement \(p_1 \vee \neg p_1\) and \(F\) can be represented by its complement.