Section 3.3 Boolean Algebra
At the close of the previous section, you were introduced to the notion of logical equivalence. We saw there that two logical expressions are said to be logically equivalent if they have exactly the same truth values under exactly the same conditions for their atomic statements. This affords us an opportunity to discuss "simplification" of logical expressions. Indeed, it is preferrable to use fewer atomic statements and fewer operations whenever possible. This is especially true in the context of computing, which we’ll discuss explicitly in the final two sections of this chapter.
This section of the text will introduce us to a variety of properties of Boolean Algebra which can be used to simplify logical expressions without the use of a truth table.
Subsection 3.3.1 Properties in Boolean Algebra
There are several properties which hold in Boolean Algebra. Many of those are properties which you proved in the checkpoint exercises in the previous section of this chapter. The table below summarizes several basic properties which can then be used in proving more complex properties. Let \(p\text{,}\) \(q\text{,}\) and \(r\) be atomic statements and let T denote a statement which is always true (a tautology) and F denote a statement which is always false (a contradiction). Table 3.3.1.
| Property Name | Equivalence |
|---|---|
| Double Negation | \(!\left(!p\right) \equiv p\) |
| Absorption Laws | \(p\land T \equiv p\) |
| \(p\land F \equiv F\) | |
| \(p\lor T \equiv T\) | |
| \(p\lor F \equiv p\) | |
| \(p\land p \equiv p\) | |
| \(p\lor p \equiv p\) | |
| Commutative Properties | \(p\land q \equiv q\land p\) |
| \(p\lor q \equiv q\lor p\) | |
| Associative Properties | \(p\lor\left(q\lor r\right) \equiv \left(p\lor q\right)\lor r\) |
| \(p\land\left(q\land r\right) \equiv \left(p\land q\right)\land r\) | |
| DeMorgan’s Laws | \(!\left(p\land q\right) \equiv !p\lor !q\) |
| \(!\left(p\lor q\right) \equiv !p\land q\) | |
| Distributive Laws | \(p\land \left(q\lor r\right) \equiv \left(p\land q\right)\lor \left(p\land r\right)\) |
| \(p\lor \left(q\land r\right)\equiv \left(p\lor q\right)\land \left(p\lor r\right)\) | |
| Implication Conversion | \(p\to q \equiv q\lor !p\) |
As mentioned, the properties above can be used to prove logical equivalences between statements which may look symbolically different. One advantage to simplifying these logical statements is that they may result in fewer comparison evaluations. This can be particularly important in speeding up computational routines. You’ll practice using the above properties in the checkpoint exercises that follow.
