<<

. 51
( 107 .)



>>


As before, a full proof of the substitution principle requires the method of
proof by induction, which we will get to in Chapter 16. But in the meantime,
our current observations should make it clear why the principle still applies.
Once we see that substitution of equivalents applies to quanti¬ed sentences,
the principles we have already learned yield a large number of new equiva-
lences. For example, we can show that the sentence ∀x (Cube(x) ’ Small(x))
is logically equivalent to ∀x ¬(Cube(x) § ¬Small(x)) by means of the following
chain of equivalences:

∀x (Cube(x) ’ Small(x)) ” ∀x (¬Cube(x) ∨ Small(x))
” ∀x (¬Cube(x) ∨ ¬¬Small(x))
” ∀x ¬(Cube(x) § ¬Small(x))
Again, these sentences are not tautologically equivalent, because we are
applying our principles inside a quanti¬ed sentence. But other than extending
the principle of substitution, no new principles are involved. There are, how-
ever, several important logical equivalences that involve quanti¬ers in essential
ways. Let™s turn to these now.

DeMorgan laws for quanti¬ers

In propositional logic, the DeMorgan laws describe important relations be-
tween negation, conjunction, and disjunction. If you think about the mean-
ings of our quanti¬ers, you will see that there is a strong analogy between ∀
and §, on the one hand, and between ∃ and ∨, on the other. For example,
suppose we are talking about a world consisting of four named blocks, say
a, b, c, and d. Then the sentence ∀x Cube(x) will be true if and only if the
following conjunction is true:

Cube(a) § Cube(b) § Cube(c) § Cube(d)

Likewise, ∃x Cube(x) will be true if and only if this disjunction is true:

Cube(a) ∨ Cube(b) ∨ Cube(c) ∨ Cube(d)

This analogy suggests that the quanti¬ers may interact with negation in a
way similar to conjunction and disjunction. Indeed, in our four-block world,
the sentence
¬∀x Small(x)
will be true if and only if the following negation is true:

¬(Small(a) § Small(b) § Small(c) § Small(d))




Section 10.3
278 / The Logic of Quantifiers


which, by DeMorgan, will hold just in case the following disjunction is true:

¬Small(a) ∨ ¬Small(b) ∨ ¬Small(c) ∨ ¬Small(d)

which in turn will be true if and only if the following holds:

∃x ¬Small(x)

The DeMorgan laws for the quanti¬ers allow you to push a negation sign
DeMorgan laws for
quanti¬ers past a quanti¬er by switching the quanti¬er from ∀ to ∃ or from ∃ to ∀. So, for
example, if we know that not everything has some property (¬∀x P(x)), then
we know that something does not have the property (∃x ¬P(x)), and vice versa.
Similarly, if we know that it is not the case that something has some property
(¬∃x P(x)), then we know that everything must fail to have it (∀x ¬P(x)), and
vice versa. We call these the DeMorgan laws for quanti¬ers, due to the analogy
described above; they are also known as the quanti¬er/negation equivalences:

¬∀x P(x) ” ∃x ¬P(x)
¬∃x P(x) ” ∀x ¬P(x)
By applying these laws along with some earlier equivalences, we can see
that there is a close relationship between certain pairs of Aristotelian sen-
tences. In particular, the negation of All P™s are Q™s is logically equivalent to
Some P™s are not Q™s. To demonstrate this equivalence, we note the following
chain of equivalences. The ¬rst is the translation of It is not true that all P™s
are Q™s while the last is the translation of Some P™s are not Q™s.

¬∀x (P(x) ’ Q(x)) ” ¬∀x (¬P(x) ∨ Q(x))
” ∃x ¬(¬P(x) ∨ Q(x))
” ∃x (¬¬P(x) § ¬Q(x))
” ∃x (P(x) § ¬Q(x))

The ¬rst step uses the equivalence of P(x) ’ Q(x) and ¬P(x) ∨ Q(x). The sec-
ond and third steps use DeMorgan™s laws, ¬rst one of the quanti¬er versions,
and then one of the Boolean versions. The last step uses the double negation
law applied to ¬¬P(x).
A similar chain of equivalences shows that the negation of Some P™s are
Q™s is equivalent to No P™s are Q™s:

¬∃x (P(x) § Q(x)) ” ∀x (P(x) ’ ¬Q(x))

We leave the demonstration of this as an exercise.




Chapter 10
First-order equivalence and DeMorgan™s laws / 279



Remember

(DeMorgan laws for quanti¬ers) For any w¬ P(x):

1. ¬∀x P(x) ” ∃x ¬P(x)

2. ¬∃x P(x) ” ∀x ¬P(x)




Exercises


10.20 Give a chain of equivalences showing that the negation of Some P™s are Q™s (¬∃x (P(x) § Q(x)))
 is equivalent to No P™s are Q™s (∀x (P(x) ’ ¬Q(x))).

10.21 Open DeMorgan™s Sentences 2. This ¬le contains six sentences, but each of sentences 4, 5, and
 6 is logically equivalent to one of the ¬rst three. Without looking at what the sentences say, see
if you can ¬gure out which is equivalent to which by opening various world ¬les and evaluating
the sentences. (You should be able to ¬gure this out from Ackermann™s, Bolzano™s, and Claire™s
Worlds, plus what we™ve told you.) Once you think you™ve ¬gured out which are equivalent to
which, write out three equivalence chains to prove you™re right. Turn these in to your instructor.

10.22 (∀ versus §) We pointed out the similarity between ∀ and §, as well as that between ∃ and
‚ ∨. But we were careful not to claim that the universally quanti¬ed sentence was logically
equivalent to the analogous conjunction. This problem will show you why we did not make this
claim.
—¦ Open Church™s Sentences and Ramsey™s World. Evaluate the sentences in this world. You
will notice that the ¬rst two sentences have the same truth value, as do the second two.

—¦ Modify Ramsey™s World in any way you like, but do not add or delete objects, and do not
change the names used. Verify that the ¬rst two sentences always have the same truth
values, as do the last two.

—¦ Now add one object to the world. Adjust the objects so that the ¬rst sentence is false, the
second and third true, and the last false. Submit your work as World 10.22. This world
shows that the ¬rst two sentences are not logically equivalent. Neither are the last two.




Section 10.3
280 / The Logic of Quantifiers


Section 10.4
Other quanti¬er equivalences
The quanti¬er DeMorgan laws tell us how quanti¬ers interact with negation.
Equally important is the question of how quanti¬ers interact with conjunction
and disjunction. The laws governing this interaction, though less interesting
than DeMorgan™s, are harder to remember, so you need to pay attention!
First of all, notice that ∀x (P(x) § Q(x)), which says that everything is
both P and Q, is logically equivalent to ∀x P(x) § ∀x Q(x), which says that
quanti¬ers and Boolean
connectives everything is P and everything is Q. These are just two di¬erent ways of saying
that every object in the domain of discourse has both properties P and Q. By
contrast, ∀x (P(x) ∨ Q(x)) is not logically equivalent to ∀x P(x) ∨ ∀x Q(x). For
example, the sentence ∀x (Cube(x) ∨ Tet(x)) says that everything is either a
cube or a tetrahedron, but the sentence ∀x Cube(x) ∨ ∀x Tet(x) says that either
everything is a cube or everything is a tetrahedron, clearly a very di¬erent
kettle of ¬sh. We summarize these two observations, positive and negative, as
follows:
∀x (P(x) § Q(x)) ” ∀x P(x) § ∀x Q(x)
∀x (P(x) ∨ Q(x)) ”
/ ∀x P(x) ∨ ∀x Q(x)
Similar observations hold with ∃, ∨, and §, except that it works the
other way around. The claim that there is some object that is either P or
Q, ∃x (P(x) ∨ Q(x)), is logically equivalent to the claim that something is
P or something is Q: ∃x P(x) ∨ ∃x Q(x). But this equivalence fails the mo-
ment we replace ∨ with §. The fact that there is a cube and a tetrahedron,
∃x Cube(x) § ∃x Tet(x), hardly means that there is something which is both
a cube and a tetrahedron: ∃x (Cube(x) § Tet(x))! Again, we summarize both
positive and negative observations together:
∃x (P(x) ∨ Q(x)) ” ∃x P(x) ∨ ∃x Q(x)
∃x (P(x) § Q(x)) ”
/ ∃x P(x) § ∃x Q(x)
There is one circumstance when you can push a universal quanti¬er in past
a disjunction, or move an existential quanti¬er out from inside a conjunction.
But to explain this circumstance, we ¬rst have to talk a bit about a degenerate
form of quanti¬cation. In de¬ning the class of w¬s, we did not insist that the
variable being quanti¬ed actually occur free (or at all) in the w¬ to which the
quanti¬er is applied. Thus, for example, the expression ∀x Cube(b) is a w¬,
even though Cube(b) does not contain the variable x. Similarly, the sentence
∃y Small(y) doesn™t contain any free variables. Still, we could form the sen-
tences ∀x ∃y Small(y) or even ∀y ∃y Small(y). We call this sort of quanti¬cation
null quanti¬cation




Chapter 10
Other quantifier equivalences / 281



null quanti¬cation. Let™s think for a moment about what it might mean.
Consider the case of the sentence ∀x Cube(b). This sentence is true in
a world if and only if every object in the domain of discourse satis¬es the
w¬ Cube(b). But what does that mean, since this w¬ does not contain any
free variables? Or, to put it another way, what does it mean to substitute a
name for the (nonexistent) free variable in Cube(b)? Well, if you replace every
occurrence of x in Cube(b) with the name n1 , the result is simply Cube(b).
So, in a rather degenerate way, the question of whether an object satis¬es
Cube(b) simply boils down to the question of whether Cube(b) is true. Thus,
∀x Cube(b) and Cube(b) are true in the same exactly the same worlds, and so
are logically equivalent. The same holds of ∃x Cube(b), which is also equivalent
to Cube(b). More generally, if the variable x is not free in w¬ P, then we have
the following equivalences:
∀x P ” P
∃x P ” P
If null quanti¬cation seems counterintuitive to you, take a moment to do
Exercise 10.23 now.
What does this have to do with conjunctions and disjunctions? Well, there
is a more general observation we can make about null quanti¬cation. Suppose
we have the sentence ∀x (Cube(b) ∨ Small(x)), where x does not occur free in
the ¬rst disjunct. This sentence will be true if Cube(b) is true (in which case,
every object will satisfy the disjunctive w¬ trivially), or if every object is small
(in which case, they will all satisfy the disjunctive w¬ by satisfying the second
disjunct), or both. That is, this sentence imposes the same conditions on a
world as the sentence Cube(b) ∨ ∀x Small(x). Indeed, when the variable x is
not free in a w¬ P, we have both of the following:
∀x (P ∨ Q(x)) ” P ∨ ∀x Q(x)
∃x (P § Q(x)) ” P § ∃x Q(x)
Compare these two equivalences to the non-equivalences highlighted a mo-
ment ago, and make sure you understand the di¬erences. The equivalences in-
volving null quanti¬cation, surprisingly enough, will become very useful later,
when we learn how to put sentences into what is called prenex form, where
all the quanti¬ers are out in front.
The last principles we mention are so basic they are easily overlooked.
When you are translating from English to fol and ¬nd a quanti¬ed noun replacing bound
variables
phrase, you must pick some variable to use in your translation. But we have
given you no guidelines as to which one is “right.” This is because it doesn™t
matter which variable you use, as long as you don™t end up with two quanti-



Section 10.4
282 / The Logic of Quantifiers


¬ers whose scope overlaps but which bind the same variable. In general, the
variable itself makes no di¬erence whatsoever. For example, these sentences
are logically equivalent:

∃x (Dodec(x) § Larger(x, b)) ” ∃y (Dodec(y) § Larger(y, b))

We codify this by means of the following: For any w¬ P(x) and variable y that
does not occur in P(x)

∀x P(x) ” ∀y P(y)
∃x P(x) ” ∃y P(y)


Remember


1. (Pushing quanti¬ers past § and ∨) For any w¬s P(x) and Q(x):

(a) ∀x (P(x) § Q(x)) ” ∀x P(x) § ∀x Q(x)
(b) ∃x (P(x) ∨ Q(x)) ” ∃x P(x) ∨ ∃x Q(x)

2. (Null quanti¬cation) For any w¬ P in which x is not free:

(a) ∀x P ” P
(b) ∃x P ” P
(c) ∀x (P ∨ Q(x)) ” P ∨ ∀x Q(x)
(d) ∃x (P § Q(x)) ” P § ∃x Q(x)

<<

. 51
( 107 .)



>>