Chapter 47 Proving equivalences
47.1 Substitutability of equivalents
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 and may always have the same truth value, but the first starts with the ‘’ 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 and . The second results from the first by replacing ‘’ by ‘’. 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 ‘’, we first compute the truth value of ‘’, 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 ‘’ and the truth table for ‘’). But since ‘’ are equivalent, they always have the same truth value in a given valuation—hence, replacing ‘’ by ‘’ cannot change the truth value of the overall sentence. The same of course is true for any other sentence equivalent to ‘’, say, ‘’.
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 ‘’, is the sentence ‘’, and is ‘’, then is ‘’.
If and are equivalent, then so are and .
It follows from this fact that any sentence of the form , 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 ‘’ in both ‘’ and ‘’ by, say, ‘’, you get ‘’ and ‘’, and those are equivalent. We can record this, too:
Equivalence is preserved under replacement of sentence letters, i.e., if and both contain the sentence letter ‘’ and are equivalent, then the sentences and (resulting by replacing ‘’ by in both) are also equivalent.
This means that once we have shown that two sentence are equivalent (e.g., ‘’ and ‘’, or ‘’ and ‘’) 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 ‘’ and ‘’ are equivalent does not also show that ‘’ and ‘’ are equivalent: the former needs just 2 lines, the latter 4.
47.2 Chains of equivalences
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, and are equivalent (for any sentence ), then replacing in a sentence by results in an equivalent sentence. The second fact tells us that and are always equivalent, for any sentence . (A simple truth table shows that ‘’ and ‘’ are equivalent.) By the second fact we know that whenever we replace ‘’ in both ‘’ and ‘’ by some sentence , we get equivalent results. In other words, from the fact that ‘’ and ‘’ are equivalent and the second fact, we can conclude that, for any sentence , 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 ‘’. We will find an equivalent sentence in which all ‘’ signs attach directly to sentence letters. In the first step, we consider this as a sentence of the form —then is the sentence ‘’ and is ‘’. Since is equivalent to (by the second of De Morgan’s Laws) we can replace the entire sentence by . In this case (where is ‘’ and is ‘’) we obtain ‘’. This new sentence contains as a part the sentence ‘’. It is of the form , except now is the sentence letter ‘’ and is ‘’. By De Morgan’s Law (the first one this time), this is equivalent to , or in this specific case, to ‘’. So we can replace the part ‘’ by ‘’. This now results in the sentence ‘’, in which the ‘’ 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).
47.3 Finding equivalent normal forms
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 sentence letters has 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:
No connectives occur in the sentence other than negations, conjunctions and disjunctions;
Every occurrence of negation has minimal scope (i.e., any ‘’ is immediately followed by an atomic sentence);
No disjunction occurs within the scope of any conjunction.
Condition (dnf1) says that we must remove all ‘’ and ‘’ symbols from a sentence. This is what the basic equivalences (Cond) and (Bicond) are good for. For instance, suppose we start with the sentence
|We can get rid of the ‘’ by using (Cond). In this case is ‘’ and is ‘’. We get:|
|The double negation can be removed, since ‘’ is equivalent to ‘’:|
|Now condition (dnf1) is satisfied: our sentence contains only ‘’, ‘’, and ‘’. Condition (dnf2) says that we must find a way to have all ‘’s apply immediately to sentence letters. But in the first conjunct it doesn’t. To ensure (dnf2) is satisfied, we use De Morgan’s Laws and the double negation (DN) law as many times as needed.|
|The resulting sentence is now in CNF—it is a conjunction of disjunctions of sentence letters and negated sentence letters. But we want a sentence in DNF, i.e., a sentence in which (dnf3) is satisfied: no ‘’ occurs in the scope of an ‘’. We use the distributive laws (Dist) to ensure this. The last sentence is of the form , where is ‘’, is ‘’, and is ‘’. By applying (Dist) once we get:|
|This looks worse, but if we keep going, it’s going to look better! The two disjuncts almost look like we can apply (Dist) again, except the ‘’ is on the wrong side. This is what commutativity (Comm) is good for. let’s apply it to ‘’:|
|We can apply (Dist) again to the resulting part, ‘’:|
|Now in the left half, no ‘’ is in the scope of an ‘’. Let’s apply the same principles to the right half:|
|Our sentence is now in DNF! But we can simplify it a bit: ‘’ is a contradiction in TFL, i.e., it is always false. And if you combine something that’s always false using ‘’ with a sentence , you get something equivalent to just . This is the second of the simplification (Simp) rules.|
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):
A. Consider the following sentences:
For each sentence, find an equivalent sentence in DNF and one in CNF by giving a chain of equivalences. Use (Id), (Abs), and (Simp) to simplify your sentences as much as possible.