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)