# 3.4: Some Logical Equivalences

The idea of logical equivalence transfers from sentence logic to predicate logic in the obvious way. In sentence logic two sentences are logically equivalent if and only if in all possible cases the sentences have the same truth value, where a possible case is just a line of the truth table for the sentence, that is, an assignment of truth values to sentence letters. All we have to do is to redescribe possible cases as interpretations:

Two closed predicate logic sentences are Logically Equivalent if and only if in each of their interpretations the two sentences are either both true or both false.

Notice that I have stated the definition only for closed sentences. Indeed, the definition would not make any sense for open sentences because open sentences don't have truth values in interpretations. Nonetheless, one can extend the idea of logical equivalence to apply to open sentences. That's a good thing, because otherwise the law of substitution of logical equivalents would break down in predicate logic. We won't be making much use of these further ideas in this book, so I won't hold things up with the details. But you might amuse yourself by trying to extend the definition of logical equivalence to open sentences in a way which will make the law of substitution of logical equivalents work in just the way you would expect.

Let us immediately take note of two equivalences which will prove very useful later on. By way of example, consider the sentence, 'No one loves Eve', which we transcribe as '~(Ǝx)Lxe', that is, as 'It is not the case that someone loves Eve'. How could this unromantic situation arise? Only if everyone didn't love Eve. In fact, saying '~(Ǝx)Lxe' comes to the same thing as saying '(Vx)~Lxe'. If there is not a single person who does love Eve, then it has to be that everyone does not love Eve. And conversely, if positively everyone does not love Eve, then not even one person does love Eve.

There is nothing special about the example I have chosen. If our sentence is of the form ~(Ǝu)(. . . u . . .), this says that there is not a single u such that so on and so forth about u. But this comes to the same as saying about each and every u that so on and so forth is not true about u, that is, that (Vu)~(. . . u . . .).

We can easily prove the equivalence of ~(Ǝu)(. . . u . . .) and (Vu)~(. . . u . . .) by appealing to De Morgan's laws. We have to prove that these two sentences have the same truth value in each and every interpretation. In any one interpretation, ~(Ǝu)(. . . u . . .) is true just in case the negation of the disjunction of the instances

~[(. . . a . . .) v (. . . b . . .) v (. . . c . . .) v . . .]

is true in the interpretation, where we have included in the disjunction all the instances formed using names which name things in the interpretation. By De Morgan's laws, this is equivalent to the conjunction of the negation of the instances

~(. . . a . . .) & ~(. . . b . . .) & ~(. . . c . . .) & . . .

which is true in the interpretation just in case (Vu)~(. . . u . . .) is true in the interpretation. Because this is true in all interpretations, we see that

Rule ~Ǝ: ~(Ǝu)(. . . u . . .) is logically equivalent to (Vu)~(. . . u . . .).

Now consider the sentence 'Not everyone loves Eve,' which we transcribe as '~(Vx)Lxe'. If not everyone loves Eve, then there must be someone who does not love Eve. And if there is someone who does not love Eve, then not everyone loves Eve. So '~(Vx)Lxe' is logically equivalent to '(Ǝx)~Lxe'.

Pretty clearly, again there is nothing special about the example. ~(Vu)(. . . u . . .) is logically equivalent to (Ǝu)~(. . . u . . .). If it is not the case that, for all u, so on and so forth about u, then there must be some u such that not so on and so forth about u. And, conversely, if there is some u such that not so on and so forth about u, then it is not the case that for all u, so on and so forth about u. In summary

Rule ~V: ~(Vu)(. . . u . . .) is logically equivalent to (Ǝu)~(. . . u . . .).

You can easily give a proof of this rule by imitating the proof of the rule ~Ǝ. But I will let you write out the new proof as an exercise.

Exercise

3-5. a) Give a proof of the rule of logical equivalence, ~V. Your proof will be very similar to the proof given in the text for the rule ~Ǝ.

b) The proof for the rule ~Ǝ is flawed! It assumes that all interpretations have finitely many things in their domain. But not all interpretations are finite in this way. (Exercise 2-5 gives an example of an infinite interpretation.) The problem is that the proof tries to talk about the disjunction of all the substitution instances of a quantified sentence. But if an interpretation is infinite, there are infinitely many substitution instances, and no sentence can be infinitely long. Since I instructed you, in part (a) of this problem, to imitate the proof in the text, probably your proof has the same problem as mine.

Your task is to correct this mistake in the proofs. Give informal arguments for the rules ~Ǝ and ~V which take account of the fact that some interpretations have infinitely many things in their domain.

3-6. In the text I defined logical equivalence for closed sentences of predicate logic. However, this definition is not broad enough to enable us to state a sensible law of substitution of logical equivalents for predicate logic. Let me explain the problem with an example. The following two sentences are logically equivalent:

(1) ~(Vx)(Vy)Lxy
(2) (Ǝx)(Ǝy)~Lxy

But we cannot prove that (1) and (2) are logically equivalent with the rule ~V as I have stated it. Here is the difficulty. The rule ~V tells us that (1) is logically equivalent to

(3) (Ǝx)~(Vy)Lxy

What we would like to say is that ~(Vy)Lxy is logically equivalent to (Ǝy)~Lxy, again by the rule ~V. But the rule ~V does not license this because I have defined logical equivalence only for closed sentences and '~(Vy)Lxy' and '(Ǝy)~Lxy' are open sentences. (Strictly speaking, I should have restricted the ~V and ~Ǝ rules to closed sentences. I didn't because I anticipated the results of this exercise.) Since open sentences are never true or false, the idea of logical equivalence for open sentences does not make any sense, at least not on the basis of the definitions I have so far introduced.

a) Extend the definition of logical equivalence for predicate logic sentences so that it applies to open as well as closed sentences. Do this in such a way that the law of substitution of logical equivalents will be correct when one open sentence is substituted for another when the two open sentences are logically equivalent according to your extended definition.

b) Show that the law of substitution of logical equivalents works when used with open sentences which are logically equivalent according to your extended definition.

chapter summary Exercise

Here are this chapter's important terms. Check your understanding by writing short explanations for each, saving your results in your notebook for reference and review.

a) Bound Variables
b) Free Variables
c) Scope
d) Closed Sentence
e) Open Sentence
f) Truth of a Sentence in an Interpretation
g) Rule ~Ǝ
h) Rule ~V