Chapter 47 Proving equivalences

Recall from section 12.2 that $𝒫$ and $𝒬$ are equivalent (in TFL) iff, for every valuation, their truth values agree. We have seen many examples of this and used both truth tables and natural dedcution proofs to establish such equivalences. In chapter 45 we’ve even proved that ever sentence of TFL is equivalent to one in conjunctive and one in disjunctive normal form. If $𝒫$ and $𝒬$ are equivalent, they always have the same truth value, either one entails the other, and from either one you can prove the other.

Equivalent sentences are not the same, of course: the sentences $\neg \neg A$ and $A$ may always have the same truth value, but the first starts with the ‘$\neg$’ symbol while the second doesn’t. But you may wonder if it’s always true that we can replace one of a pair of equivalent sentences by the other, and the results will be equivalent, too. For instance, consider $\neg \neg A\to B$ and $A\to B$. The second results from the first by replacing ‘$\neg \neg A$’ by ‘$A$’. And these two sentences are also equivalent.

This is a general fact, and it is not hard to see why it is true. In any valuation, we compute the truth value of a sentence “from the inside out.” So when it comes to determining the truth value of ‘$\neg \neg A\to B$’, we first compute the truth value of ‘$\neg \neg A$’, and the truth value of the overall sentence then just depends on that truth value (true or false, as the case may be) and the rest of the sentence (the truth value of ‘$B$’ and the truth table for ‘$\to$’). But since ‘$\neg \neg A$’ are equivalent, they always have the same truth value in a given valuation—hence, replacing ‘$\neg \neg A$’ by ‘$A$’ cannot change the truth value of the overall sentence. The same of course is true for any other sentence equivalent to ‘$\neg \neg A$’, say, ‘$A\wedge (A\vee A)$’.

To state the result in general, let’s use the notation $ℛ(𝒫)$ to mean a sentence which contains the sentence $𝒫$ as a part. Then by $ℛ(𝒬)$ we mean the result of replacing the occurrence of $𝒫$ by the sentence $𝒬$. For instance, if $𝒫$ is the sentence letter ‘$A$’, $𝒬$ is the sentence ‘$\neg \neg A$’, and $ℛ(𝒫)$ is ‘$A\to B$’, then $ℛ(𝒬)$ is ‘$\neg \neg A\to B$’.

It follows from this fact that any sentence of the form $ℛ(𝒫)\leftrightarrow ℛ(𝒬)$, where $𝒫$ and $𝒬$ are equivalent, is a tautology. However, the proofs in natural deduction will be wildly different for different $ℛ$. (As an exercise, give proofs that show that

and compare the two.)

Here is another fact: if two sentences $𝒫$ and $𝒬$ are equivalent, and you replace some sentence letter in both $𝒫$ and $𝒬$ by the same sentence $ℛ$, the results are also equivalent. For instance, if you replace ‘$A$’ in both ‘$A\wedge B$’ and ‘$B\wedge A$’ by, say, ‘$\neg C$’, you get ‘$\neg C\wedge B$’ and ‘$B\wedge \neg C$’, and those are equivalent. We can record this, too:

This means that once we have shown that two sentence are equivalent (e.g., ‘$\neg \neg A$’ and ‘$A$’, or ‘$A\wedge B$’ and ‘$B\wedge A$’) we know that all their common “instances” are also equivalent. Note that we do not immediately get this from a truth table or a natural deduction proof. E.g., a truth table that shows that ‘$\neg \neg A$’ and ‘$A$’ are equivalent does not also show that ‘$\neg \neg (B\to C)$’ and ‘$B\to C$’ are equivalent: the former needs just 2 lines, the latter 4.

When you want to verify that two sentences are equivalent, you can of course do a truth table, or look for a formal proof. But there is a simpler method, based on the principle of substitutability of equivalents we just discussed: Armed with a small catalog of simple equivalences, replace parts of your first sentence by equivalent parts, and repeat until you reach your second sentence.

This method of showing sentences equivalent is underwritten by the two facts from the previous section. The first fact tells us that if, say, $\neg \neg 𝒫$ and $𝒫$ are equivalent (for any sentence $𝒫$), then replacing $\neg \neg 𝒫$ in a sentence by $𝒫$ results in an equivalent sentence. The second fact tells us that $\neg \neg 𝒫$ and $𝒫$ are always equivalent, for any sentence $𝒫$. (A simple truth table shows that ‘$\neg \neg A$’ and ‘$A$’ are equivalent.) By the second fact we know that whenever we replace ‘$A$’ in both ‘$\neg \neg A$’ and ‘$A$’ by some sentence $𝒫$, we get equivalent results. In other words, from the fact that ‘$\neg \neg A$’ and ‘$A$’ are equivalent and the second fact, we can conclude that, for any sentence $𝒫$, $\neg \neg 𝒫$ and $𝒫$ are equivalent.

Let’s give an example. By De Morgan’s Laws, the following pairs of sentences are equivalent:

This can be verified by constructing two truth tables, or four natural deduction proofs that show:

By the second fact, any pairs of sentences of the following forms are equivalent:

Now consider the sentence ‘$\neg (R\vee (S\wedge T))$’. We will find an equivalent sentence in which all ‘$\neg$’ signs attach directly to sentence letters. In the first step, we consider this as a sentence of the form $\neg (𝒫\vee 𝒬)$—then $𝒫$ is the sentence ‘$R$’ and $𝒬$ is ‘$(S\wedge T)$’. Since $\neg (𝒫\vee 𝒬)$ is equivalent to $(\neg 𝒫\wedge \neg 𝒬)$ (by the second of De Morgan’s Laws) we can replace the entire sentence by $(\neg 𝒫\wedge \neg 𝒬)$. In this case (where $𝒫$ is ‘$R$’ and $𝒬$ is ‘$(S\wedge T)$’) we obtain ‘$(\neg R\wedge \neg (S\wedge T))$’. This new sentence contains as a part the sentence ‘$\neg (S\wedge T)$’. It is of the form $\neg (𝒫\wedge 𝒬)$, except now $𝒫$ is the sentence letter ‘$S$’ and $𝒬$ is ‘$T$’. By De Morgan’s Law (the first one this time), this is equivalent to $(\neg 𝒫\vee \neg 𝒬)$, or in this specific case, to ‘$(\neg S\vee \neg T)$’. So we can replace the part ‘$\neg (S\wedge T)$’ by ‘$(\neg S\vee \neg T)$’. This now results in the sentence ‘$(\neg R\wedge (\neg S\vee \neg T))$’, in which the ‘$\neg$’ symbols all attach directly to sentence letters. We’ve “pushed” the negations inwards as far as possible. We can record such a chain of equivalences by listing the individual steps, and recording, just as we do in natural deduction, which basic equivalence we use in each case:

We’ve highlighted the sentence replaced, and those matching the $𝒫$ and $𝒬$ in De Morgan’s Laws for clarity, but this is not necessary, and we won’t keep doing it.

In table 47.1 we’ve given a list of basic equivalences you can use for such chains of equivalences. The labels abbreviate the customary name for the respective logical laws: double negation (DN), De Morgan (DeM), commutativity (Comm), distributivity (Dist), associativity (Assoc), idempotence (Id), and absorption (Abs).

In chapter 45 we showed that every sentence of TFL is equivalent to one in disjunctive normal form (DNF) and to one in conjunctive normal form (CNF). We did this by giving a method to construct a sentences in DNF or CNF equivalent to the original sentence by first constructing a truth table, and then “reading off” a sentence in DNF or CNF from the truth table. This method has two drawbacks. The first one is that the resulting sentences in DNF or CNF are not always the shortest ones. The second one is that the method itself becomes hard to apply when the sentence you start with contains more than a handful of sentence letters (since the truth table for a sentence with $n$ sentence letters has $2^n$ lines).

We can use chains of equivalences as an alternative method: To find a sentence in DNF, we can successively apply basic equivalences until we have found an equivalent sentence that is in DNF. Recall the conditions a sentence in DNF must satisfy:

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.

Condition (dnf1) says that we must remove all ‘$\to$’ and ‘$\leftrightarrow$’ symbols from a sentence. This is what the basic equivalences (Cond) and (Bicond) are good for. For instance, suppose we start with the sentence

The final result is still in DNF, but a bit simpler still. It is also much simpler than the DNF we would have obtained by the method of chapter 45. In fact, the sentence we started with could have been the $𝒮$ of section 45.2—it has exactly the truth table used as an example there. The DNF we found there (in section section 45.2), was (with all necessary brackets):