3.4: The Algebra of Propositions

Propositions in Normal Form

Every propositional formula is equivalent to a “sum-of-products” or disjunctive form. More precisely, a disjunctive form is simply an OR of \(\text{AND}\)-terms, where each \(\text{AND}\)-terms is an \(\text{AND}\) of variables or negations of variables, for example,

\[\label{3.4.1} (A \text{ AND } B) \text{ OR } (A \text{ AND } C).\]

You can read a disjunctive form for any propositional formula directly from its truth table. For example, the formula

\[\label{3.4.2} A \text{ AND } (B \text{ OR } C)\]

has truth table:

\[\nonumber \begin{array}{c|c|c|cc}
A & B & C & A & \text { AND } & (B \text { OR } C) \\
\hline \mathbf{T} & \mathbf{T} & \mathbf{T} & & \mathbf{T} & \\
\mathbf{T} & \mathbf{T} & \mathbf{F} & & \mathbf{T} & \\
\mathbf{T} & \mathbf{F} & \mathbf{T} & & \mathbf{T} & \\
\mathbf{T} & \mathbf{F} & \mathbf{F} & & \mathbf{F} & \\
\mathbf{F} & \mathbf{T} & \mathbf{T} & & \mathbf{F} & \\
\mathbf{F} & \mathbf{T} & \mathbf{F} & & \mathbf{F} & \\
\mathbf{F} & \mathbf{F} & \mathbf{T} & & \mathbf{F} & \\
\mathbf{F} & \mathbf{F} & \mathbf{F} & & \mathbf{F} &
\end{array}\]

The formula (\ref{3.4.2}) is true in the first row when \(A, B, \text{and } C\) are all true, that is, where \(A \text{ AND } B \text{ AND } C\) is true. It is also true in the second row where \(A \text{ AND } B \text{ AND } \overline{C}\) is true, and in the third row when \(A \text{ AND } \overline{B} \text{ AND } C\) is true, and that’s all. So (\ref{3.4.2}) is true exactly when

\[\label{3.4.3} (A \text{ AND } B \text{ AND } C) \text{ OR } (A \text{ AND } B \text{ AND } \overline{C}) \text{ OR } (A \text{ AND } \overline{B} \text{ AND } C)\]

is true.

Theorem \(\PageIndex{1}\)

[Distributive Law of \(\text{AND}\) over \(\text{OR}\)]

\(A \text{ AND } (B \text{ OR } C\)) is equivalent to (\(A \text{ AND } B) \text{ OR } (A \text{ AND }C\)).

Theorem 3.4.1 is called a distributive law because of its resemblance to the distributivity of products over sums in arithmetic.

Similarly, we have (Problem 3.10):

Theorem \(\PageIndex{2}\)

[Distributive Law of \(\text{OR}\) over \(\text{AND}\)]

\(A \text{ OR } (B \text{ AND } C\)) is equivalent to (\(A \text{ OR } B) \text{ AND } (A \text{ OR }C\)).

Note the contrast between Theorem 3.4.2 and arithmetic, where sums do not distribute over products.

The expression (\ref{3.4.3}) is a disjunctive form where each \(\text{AND}\)-term is an \(\text{AND}\) of every one of the variables or their negations in turn. An expression of this form is called a disjunctive normal form (DNF). A DNF formula can often be simplified into a smaller disjunctive form. For example, the DNF (\ref{3.4.3}) further simplifies to the equivalent disjunctive form (\ref{3.4.1}) above.

Applying the same reasoning to the \(\textbf{F}\) entries of a truth table yields a conjunctive form for any formula—an \(\text{AND}\) of \(\text{OR}\)-terms in which the \(\text{OR}\)-terms are \(\text{OR}\)’s only of variables or their negations. For example, formula (\ref{3.4.2}) is false in the fourth row of its truth table (3.4.1) where \(A\) is \(\textbf{T}\), \(B\) is \(\textbf{F}\) and \(C\) is \(\textbf{F}\). But this is exactly the one row where (\(\overline{A} \text{ OR } B \text{ OR } C\)) is \(\textbf{F}\)! Likewise, the (\ref{3.4.2}) is false in the fifth row which is exactly where (\(A \text{ OR } \overline{B} \text{ OR } \overline{C}\)) is \(\textbf{F}\). This means that (\ref{3.4.2}) will be \(\textbf{F}\) whenever the \(\text{AND}\) of these two \(\text{OR}\)-terms is false. Continuing in this way with the \(\text{OR}\)-terms corresponding to the remaining three rows where (\ref{3.4.2}) is false, we get a conjunctive normal form (CNF) that is equivalent to (\ref{3.4.2}), namely,

\[\nonumber (\overline{A} \text{ OR } B \text{ OR } C) \text{ AND } (A \text{ OR } \overline{B} \text{ OR } \overline{C}) \text{ AND } (A \text{ OR } \overline{B} \text{ OR } C) \text{ AND } (A \text{ OR } B \text{ OR } \overline{C}) \text{ AND } (A \text{ OR } B \text{ OR } C)\]

The methods above can be applied to any truth table, which implies

Theorem \(\PageIndex{3}\)

Every propositional formula is equivalent to both a disjunctive normal form and a conjunctive normal form.

Proving Equivalences

A check of equivalence or validity by truth table runs out of steam pretty quickly: a proposition with \(n\) variables has a truth table with \(2^n\) lines, so the effort required to check a proposition grows exponentially with the number of variables. For a proposition with just 30 variables, that’s already over a billion lines to check!

An alternative approach that sometimes helps is to use algebra to prove equivalence. A lot of different operators may appear in a propositional formula, so a useful first step is to get rid of all but three: \(\text{AND, OR, and NOT}\). This is easy because each of the operators is equivalent to a simple formula using only these three. For example, \(A \text{ IMPLIES } B\) is equivalent to \(\text{NOT }(A) \text{ OR } B\). Formulas using only \(\text{AND, OR, and NOT}\) for the remaining operators are left to Problem 3.13.

We list below a bunch of equivalence axioms with the symbol “\(\longleftrightarrow\)” between equivalent formulas. These axioms are important because they are all that’s needed to prove every possible equivalence. We’ll start with some equivalences for \(\text{AND}\)’s that look like the familiar ones for multiplication of numbers:

\[\begin{align} \label{3.4.4} A \text{ AND } B &\longleftrightarrow B \text{ AND } A & (\text{commutativity of AND}) \\  \label{3.4.5} (A \text{ AND } B) \text{ AND } C &\longleftrightarrow A \text{ AND } (B \text{ AND } C) & (\text{associativity of AND}) \\ \nonumber \textbf{T} \text{ AND } A &\longleftrightarrow A & (\text{identity of AND}) \\ \nonumber \textbf{F} \text{ AND } A &\longleftrightarrow \textbf{F} & \text{(zero for AND)} \end{align}\]

Three axioms that don’t directly correspond to number properties are

\[\begin{align} \nonumber A \text{ AND } A &\longleftrightarrow A & (\text{idempotence for AND}) \\  \label{3.4.6} A \text{ AND } \overline{A} &\longleftrightarrow \textbf{F} & (\text{contradiction for AND}) \\  \label{3.4.7} \text{NOT }(\overline{A}) &\longleftrightarrow A & (\text{double negation}) \end{align}\]

It is associativity (\ref{3.4.5}) that justifies writing \(A \text{ AND } B \text{ AND } C\) without specifying whether it is parenthesized as \(A \text{ AND } (B \text{ AND } C) \text{ or } (A \text{ AND } B) \text{ AND } C\). Both ways of inserting parentheses yield equivalent formulas.

There are a corresponding set of equivalences for \(\text{OR}\) which we won’t bother to list, except for the \(\text{OR}\) rule corresponding to contradiction for \(\text{AND}\) (\ref{3.4.6}):

\[\begin{aligned} A \text{ OR } \overline{A} &\longleftrightarrow \textbf{T} & (\text{validity for OR}) \end{aligned}\]

Finally, there are DeMorgan’s Laws which explain how to distribute \(\text{NOT}\)'s over \(\text{AND}\)’s and \(\text{OR}\)’s:

\[\begin{align} \label{3.4.8} \text{NOT}(A \text{ AND } B) &\longleftrightarrow \overline{A} \text{ OR } \overline{B} & (\text{DeMorgan for AND}) \\  \label{3.4.9} \text{NOT}(A \text{ OR } B) &\longleftrightarrow \overline{A} \text{ AND } \overline{B} & (\text{DeMorgan for OR}) \end{align}\]

All of these axioms can be verified easily with truth tables.

These axioms are all that’s needed to convert any formula to a disjunctive normal form. We can illustrate how they work by applying them to turn the negation of formula (\ref{3.4.2}),

\[\label{3.4.10} \text{NOT}((A \text { AND } B) \text { OR }(A \text { AND } C)).\]

into disjunctive normal form.

We start by applying DeMorgan’s Law for \(\text{OR}\) (\ref{3.4.9}) to (\ref{3.4.10}) in order to move the \(\text{NOT}\) deeper into the formula. This gives

\[\nonumber \text{NOT}(A \text { AND } B) \text { AND NOT }(A \text { AND } C).\]

Now applying Demorgan’s Law for AND (\ref{3.4.8}) to the two innermost AND-terms, gives

\[\label{3.4.11} (\overline{A} \text { OR } \overline{B}) \text { AND }(\overline{A} \text { OR } \overline{C}).\]

At this point \(\text{NOT}\) only applies to variables, and we won’t need Demorgan’s Laws any further.

Now we will repeatedly apply The Distributivity of \(\text{AND}\) over \(\text{OR}\) (Theorem 3.4.1) to turn (\ref{3.4.11}) into a disjunctive form. To start, we’ll distribute (\(\overline{A} \text{ OR } \overline{B}\)) over \(\text{AND}\) to get

\[\nonumber ((\overline{A} \text { OR } \overline{B}) \text { AND } \overline{A}) \text{ OR } ((\overline{A} \text { OR } \overline{B}) \text { AND } \overline{C}).\]

Using distributivity over both AND’s we get

\[\nonumber ((\overline{A} \text { AND } \overline{A}) \text { OR } (\overline{B} \text { AND } \overline{A})) \text{ OR } ((\overline{A} \text { AND } \overline{C}) \text { OR } (\overline{B} \text { AND } \overline{C})).\]

By the way, we’ve implicitly used commutativity (3.7) here to justify distributing over an AND from the right. Now applying idempotence to remove the duplicate occurrence of A we get

\[\nonumber (\overline{A} \text { OR } (\overline{B} \text { AND } \overline{A})) \text{ OR } ((\overline{A} \text { AND } \overline{C}) \text { OR } (\overline{B} \text { AND } \overline{C})).\]

Associativity now allows dropping the parentheses around the terms being \(\text{OR}\)’d to yield the following disjunctive form for (\ref{3.4.10}):

\[\label{3.4.12} \overline{A} \text { OR } (\overline{B} \text { AND } \overline{A}) \text{ OR } (\overline{A} \text { AND } \overline{C}) \text { OR } (\overline{B} \text { AND } \overline{C}).\]

The last step is to turn each of these \(\text{AND}\)-terms into a disjunctive normal form with all three variables \(A, B, \text{ and } C\). We’ll illustrate how to do this for the second \(\text{AND}\)-term \((\overline{B} \text{ AND } \overline{A})\). This term needs to mention \(C\) to be in normal form. To introduce \(C\), we use validity for \(\text{OR}\) and identity for \(\text{AND}\) to conclude that

\[\nonumber (\overline{B} \text{ AND } \overline{A}) \longleftrightarrow (\overline{B} \text { AND } \overline{A}) \text { AND } (C \text { OR } \overline{C}).\]

Now distributing \((\overline{B} \text{ AND } \overline{A})\) over the \(\text{OR}\) yields the disjunctive normal form

\[\nonumber (\overline{B} \text{ AND } \overline{A} \text{ AND } C) \text{ OR } (\overline{B} \text{ AND } \overline{A} \text{ AND } \overline{C}).\]

Doing the same thing to the other AND-terms in (\ref{3.4.12}) finally gives a disjunctive normal form for (\ref{3.4.2}):

\[\begin{aligned} (\overline{A} \text{ AND } B \text{ AND } C) &\text{ OR } (\overline{A} \text{ AND } B \text{ AND } \overline{C}) \text{ OR} \\ (\overline{A} \text{ AND } \overline{B} \text{ AND } C) &\text{ OR } (\overline{A} \text{ AND } \overline{B} \text{ AND } \overline{C}) \text{ OR}\\ (\overline{B} \text{ AND } \overline{A} \text{ AND } C) &\text{ OR } (\overline{B} \text{ AND } \overline{A} \text{ AND } \overline{C}) \text{ OR} \\ (\overline{A} \text{ AND } \overline{C} \text{ AND } B) &\text{ OR } (\overline{A} \text{ AND } \overline{C} \text{ AND } \overline{B}) \text{ OR }\\ (\overline{B} \text{ AND } \overline{C} \text{ AND } A) &\text{ OR } (\overline{B} \text{ AND } \overline{C} \text{ AND } \overline{A}). \end{aligned}\]

Using commutativity to sort the term and \(\text{OR}\)-idempotence to remove duplicates, finally yields a unique sorted \(\text{DNF}\):

\[\begin{aligned} (A \text{ AND } \overline{B} \text{ AND } \overline{C}) &\text{ OR } \\ (\overline{A} \text{ AND } B \text{ AND } C) &\text{ OR } \\ (\overline{A} \text{ AND } B \text{ AND } \overline{C}) &\text{ OR } \\ (\overline{A} \text{ AND } \overline{B} \text{ AND } C) &\text{ OR } \\ (\overline{A} \text{ AND } \overline{B} \text{ AND } \overline{C}) &. \end{aligned}\]

This example illustrates a strategy for applying these equivalences to convert any formula into disjunctive normal form, and conversion to conjunctive normal form works similarly, which explains:

Theorem \(\PageIndex{4}\)

Any propositional formula can be transformed into disjunctive normal form or a conjunctive normal form using the equivalences listed above.

What has this got to do with equivalence? That’s easy: to prove that two formulas are equivalent, convert them both to disjunctive normal form over the set of variables that appear in the terms. Then use commutativity to sort the variables and \(\text{AND}\)-terms so they all appear in some standard order. We claim the formulas are equivalent iff they have the same sorted disjunctive normal form. This is obvious if they do have the same disjunctive normal form. But conversely, the way we read off a disjunctive normal form from a truth table shows that two different sorted \(\text{DNF}\)’s over the same set of variables correspond to different truth tables and hence to inequivalent formulas. This proves

Theorem \(\PageIndex{5}\)

(Completeness of the propositional equivalence axioms). Two propositional formula are equivalent iff they can be proved equivalent using the equivalence axioms listed above.

The benefit of the axioms is that they leave room for ingeniously applying them to prove equivalences with less effort than the truth table method. Theorem 3.4.5 then adds the reassurance that the axioms are guaranteed to prove every equivalence, which is a great punchline for this section. But we don’t want to mislead you: it’s important to realize that using the strategy we gave for applying the axioms involves essentially the same effort it would take to construct truth tables, and there is no guarantee that applying the axioms will generally be any easier than using truth tables.