Chapter 45 Normal forms

Sometimes it is useful to consider sentences of a particularly simple form. For instance, we might consider sentences in which $\neg$ only attaches to atomic sentences, or those which are combinations of atomic sentences and negated atomic sentences using only $\wedge$. A relatively general but still simple form is that where a sentence is a disjunction of conjunctions of atomic or negated atomic sentences. When such a sentence is constructed, we start with atomic sentences, then (perhaps) attach negations, then (perhaps) combine using $\wedge$, and finally (perhaps) combine using $\vee$.

Let’s say that a sentence is in disjunctive normal form if⁠f it meets all of the following conditions:

1. (dnf1)
   ​

   No connectives occur in the sentence other than negations, conjunctions and disjunctions;

2. (dnf2)
   ​

   Every occurrence of negation has minimal scope (i.e., any ‘$\neg$’ is immediately followed by an atomic sentence);

3. (dnf3)
   ​

   No disjunction occurs within the scope of any conjunction.

So, here are are some sentences in disjunctive normal form:

Note that we have here broken one of the maxims of this book and temporarily allowed ourselves to employ the relaxed bracketing-conventions that allow conjunctions and disjunctions to be of arbitrary length. These conventions make it easier to see when a sentence is in disjunctive normal form. We will continue to help ourselves to these relaxed conventions, without further comment.

To further illustrate the idea of disjunctive normal form, we will introduce some more notation. We write ‘$\pm 𝒜$’ to indicate that $𝒜$ is an atomic sentence which may or may not be prefaced with an occurrence of negation. Then a sentence in disjunctive normal form has the following shape:

We now know what it is for a sentence to be in disjunctive normal form. The result that we are aiming at is:

Henceforth, we will abbreviate ‘Disjunctive Normal Form’ by ‘DNF’.

Our first proof of the DNF Theorem employs truth tables. We will first illustrate the technique for finding an equivalent sentence in DNF, and then turn this illustration into a rigorous proof.

Let’s suppose we have some sentence, $𝒮$, which contains three atomic sentences, ‘$A$’, ‘$B$’ and ‘$C$’. The very first thing to do is fill out a complete truth table for $𝒮$. Maybe we end up with this:

As it happens, $𝒮$ is true on four lines of its truth table, namely lines 1, 3, 7 and 8. Corresponding to each of those lines, we will write down four sentences, whose only connectives are negations and conjunctions, where every negation has minimal scope:

1. 1.
   ​

   ‘$A\wedge B\wedge C$’ which is true on line 1 (and only then)

2. 2.
   ​

   ‘$A\wedge \neg B\wedge C$’ which is true on line 3 (and only then)

3. 3.
   ​

   ‘$\neg A\wedge \neg B\wedge C$’ which is true on line 7 (and only then)

4. 4.
   ​

   ‘$\neg A\wedge \neg B\wedge \neg C$’ which is true on line 8 (and only then)

We now combine all of these conjunctions using $\vee$, like so:

This gives us a sentence in DNF which is true on exactly those lines where one of the disjuncts is true, i.e., it is true on (and only on) lines 1, 3, 7, and 8. So this sentence has exactly the same truth table as $𝒮$. So we have a sentence in DNF that is logically equivalent to $𝒮$, which is exactly what we wanted!

Now, the strategy that we just adopted did not depend on the specifics of $𝒮$; it is perfectly general. Consequently, we can use it to obtain a simple proof of the DNF Theorem.

Pick any arbitrary sentence, $𝒮$, and let ${𝒜}_1,\mathrm{\dots },{𝒜}_n$ be the atomic sentences that occur in $𝒮$. To obtain a sentence in DNF that is logically equivalent $𝒮$, we consider $𝒮$’s truth table. There are two cases to consider:

1. 1.
   ​

   $𝒮$ is false on every line of its truth table. Then, $𝒮$ is a contradiction. In that case, the contradiction $({𝒜}_1\wedge \neg {𝒜}_1)$ is in DNF and logically equivalent to $𝒮$.

2. 2.
   ​

   $𝒮$ is true on at least one line of its truth table. For each line $i$ of the truth table, let ${ℬ}_i$ be a conjunction of the form

   $$(\pm {𝒜}_1\wedge \mathrm{\dots }\wedge \pm {𝒜}_n)$$

   where the following rules determine whether or not to include a negation in front of each atomic sentence:

   • ‣
     ​

     ${𝒜}_m$ is a conjunct of ${ℬ}_i$ if⁠f ${𝒜}_m$ is true on line $i$.

   • ‣
     ​

     $\neg {𝒜}_m$ is a conjunct of ${ℬ}_i$ if⁠f ${𝒜}_m$ is false on line $i$.

   Given these rules, ${ℬ}_{𝒾}$ is true on (and only on) line $i$ of the truth table which considers all possible valuations of ${𝒜}_1$, …, ${𝒜}_n$ (i.e., $𝒮$’s truth table).

   Next, let $i_1$, $i_2$, …, $i_m$ be the numbers of the lines of the truth table where $𝒮$ is true. Now let $𝒟$ be the sentence:

   $${ℬ}_{i_1}\vee {ℬ}_{i_2}\vee \mathrm{\dots }\vee {ℬ}_{i_m}$$

   Since $𝒮$ is true on at least one line of its truth table, $𝒟$ is indeed well-defined; and in the limiting case where $𝒮$ is true on exactly one line of its truth table, $𝒟$ is just ${ℬ}_{i_1}$, for some $i_1$.

   By construction, $𝒟$ is in DNF. Moreover, by construction, for each line $i$ of the truth table: $𝒮$ is true on line $i$ of the truth table if⁠f one of $𝒟$’s disjuncts (namely, ${ℬ}_{𝒾}$) is true on, and only on, line $i$. Hence $𝒮$ and $𝒟$ have the same truth table, and so are logically equivalent.

These two cases are exhaustive and, either way, we have a sentence in DNF that is logically equivalent to $𝒮$.

So we have proved the DNF Theorem. Before we say any more, though, we should immediately flag that we are hereby returning to the austere definition of a (TFL) sentence, according to which we can assume that any conjunction has exactly two conjuncts, and any disjunction has exactly two disjuncts.

So far in this chapter, we have discussed disjunctive normal form. It may not come as a surprise to hear that there is also such a thing as conjunctive normal form (CNF).

The definition of CNF is exactly analogous to the definition of DNF. So, a sentence is in CNF if⁠f it meets all of the following conditions:

1. (cnf1)
   ​

   No connectives occur in the sentence other than negations, conjunctions and disjunctions;

2. (cnf2)
   ​

   Every occurrence of negation has minimal scope;

3. (cnf3)
   ​

   No conjunction occurs within the scope of any disjunction.

Generally, then, a sentence in CNF looks like this

where each ${𝒜}_k$ is an atomic sentence.

We can now prove another normal form theorem:

Given a TFL sentence, $𝒮$, we begin by writing down the complete truth table for $𝒮$.

If $𝒮$ is true on every line of the truth table, then $𝒮$ and $({𝒜}_1\vee \neg {𝒜}_1)$ are logically equivalent.

If $𝒮$ is false on at least one line of the truth table then, for every line on the truth table where $𝒮$ is false, write down a disjunction $(\pm {𝒜}_1\vee \mathrm{\dots }\vee \pm {𝒜}_n)$ which is false on (and only on) that line. Let $𝒞$ be the conjunction of all of these disjuncts; by construction, $𝒞$ is in CNF and $𝒮$ and $𝒞$ are logically equivalent.