<< Ļšåäūäółą’ ńņš. 66(čē 107 ńņš.)ĪĆĖĄĀĖÅĶČÅ Ńėåäóžłą’ >>
ā’ Larger(x, y))) ā’ Larger(x, y)))
āx (Dodec(x) ā’ āy (Tet(y) ā’ Larger(x, y))) āx (Dodec(x) ā’ āy (Tet(y)
āx Dodec(x) ā’ Larger(x, y)))
āx Dodec(x)
āx (Cube(x) ā’ āy (Tet(y) ā’ Larger(x, y)))
āx āy āz ((Larger(x, y) ā§ Larger(y, z))
(Compare this with Exercise 13.9. The ā’ Larger(x, z))
crucial diļ¬erence is the presence of the
āx (Cube(x) ā’ āy (Tet(y)
third premise, not the diļ¬erence in form
ā’ Larger(x, y)))
of the ļ¬rst two premises.)

Chapter 13
Some review exercises / 361

Section 13.4
Soundness and completeness
In Chapter 8 we raised the question of whether the deductive system FT was
sound and complete with respect to tautological consequence. The same issues
arise with the full system F , which contains the rules for the quantiļ¬ers and
identity, in addition to the rules for the truth-functional connectives. Here,
the target consequence relation is the notion of ļ¬rst-order consequence, rather
than tautological consequence.
The soundness question asks whether anything we can prove in F from soundness of F
premises P1 , . . . , Pn is indeed a ļ¬rst-order consequence of the premises. The
completeness question asks the converse: whether every ļ¬rst-order consequence completeness of F
of a set of sentences can be proven from that set using the rules of F .
It turns out that both of these questions can be answered in the aļ¬rma-
tive. Before actually proving this, however, we need to add more precision
to the notion of ļ¬rst-order consequence, and this presupposes tools from set
theory that we will introduce in Chapters 15 and 16. We state and prove
the soundness theorem for ļ¬rst-order logic in Chapter 18. The completeness
theorem for ļ¬rst-order logic is the main topic of Chapter 19.

Section 13.5
Some review exercises
ing of the methods of reasoning involving quantiļ¬ers. We also present some
more interesting problems from a theoretical point of view.

Exercises

Some of the following arguments are valid, some are not. For each, either use Fitch to give a formal
proof or use Tarskiā™s World to construct a counterexample. In giving proofs, feel free to use Taut Con
if it helps.

13.40 13.41
āx Cube(x) ā§ Small(d) āx (Cube(x) āØ Small(x))
Ć‚ Ć‚
āx (Cube(x) ā§ Small(d)) āx Cube(x) āØ āx Small(x)

Section 13.5
362 / Formal Proofs and Quantifiers

13.42 āx Cube(x) āØ āx Small(x)
Ć‚
āx (Cube(x) āØ Small(x))

Each of the following is a valid argument of a type discussed in Section 10.3. Use Fitch to give a proof
of its validity. You may use Taut Con freely in these proofs.

13.43 13.44
Ā¬āx Cube(x) Ā¬āx Cube(x)
Ć‚ Ć‚
āx Ā¬Cube(x) āx Ā¬Cube(x)

13.45 13.46 (Change of bound variables)
āx Ā¬Cube(x)
Ć‚ Ć‚ āx Cube(x)
Ā¬āx Cube(x)
āy Cube(y)

13.47 (Change of bound variables) 13.48 (Null quantiļ¬cation)
Ć‚ Ć‚
āx Tet(x)
āy Tet(y) Cube(b) ā” āx Cube(b)

13.49 13.50
āx P(x) āx (P(x) ā§ āy (P(y) ā’ y = x))
Ć‚ Ć‚
āx āy ((P(x) ā§ P(y)) ā’ x = y)
āx āy ((P(x) ā§ P(y)) ā’ x = y)
āx (P(x) ā§ āy (P(y) ā’ y = x))

13.51 13.52
Ć‚ Ć‚
āx (P(x) ā’ āy P(y)) Ā¬āx āy [E(x, y) ā” Ā¬E(y, y)]
This result might be called Russellā™s
Theorem. It is connected with the fa-
cise 12.22 where you should have given
mous result known as Russellā™s Paradox,
an informal proof of something of this
which is discussed in Section 15.8. In
form.]
fact, it was upon discovering this that
Russell invented the Barber Paradox, to
explain his result to a general public.

13.53 Is āx āy Ā¬LeftOf(x, y) a ļ¬rst-order consequence of āx Ā¬LeftOf(x, x)? If so, give a formal proof.
Ć‚| If not, give a reinterpretation of LeftOf and an example where the premise is true and the
conclusion is false.

Chapter 13
Some review exercises / 363

The next exercises are intended to help you review the diļ¬erence between ļ¬rst-order satisļ¬ability and
true logical possibility. All involve the four sentences in the ļ¬le Padoaā™s Sentences. Open that ļ¬le now.

13.54 Any three of the sentences in Padoaā™s Sentences form a satisļ¬able set. There are four sets of three
Ć‚ sentences, so to show this, build four worlds, World 13.54.123, World 13.54.124, World 13.54.134,
and World 13.54.234,where the four sets are true. (Thus, for example, sentences 1, 2 and 4 should
be true in World 13.54.124.)

13.55 Give an informal proof that the four sentences in Padoaā™s Sentences taken together are incon-
 sistent.

13.56 Is the set of sentences in Padoaā™s Sentences ļ¬rst-order satisļ¬able, that is, satisļ¬able with some
 reinterpretation of the predicates other than identity? [Hint: Imagine a world where one of the
blocks is a sphere.]

13.57 Reinterpret the predicates Tet and Dodec in such a way that sentence 3 of Padoaā™s Sentences
 comes out true in World 13.57.124. Since this is the only sentence that uses these predicates,
it follows that all four sentences would, with this reinterpretation, be true in this world. (This
shows that the set is ļ¬rst-order satisļ¬able.)

13.58 (Logical truth versus non-logical truth in all worlds) A distinction Tarskiā™s World helps us to
Ć‚| understand is the diļ¬erence between sentences that are logically true and sentences that are,
for reasons that have nothing to do with logic, true in all worlds. The notion of logical truth
has to do with a sentence being true simply in virtue of the meaning of the sentence, and so
no matter how the world is. However, some sentences are true in all worlds, not because of
the meaning of the sentence or its parts, but because of, say, laws governing the world. We
can think of the constraints imposed by the innards of Tarskiā™s World as analogues of physical
laws governing how the world can be. For example, the sentence which asserts that there are at
most 12 objects happens to hold in all the worlds that we can construct with Tarskiā™s World.
However, it is not a logical truth.
Open Postā™s Sentences. Classify each sentence in one of the following ways: (A) a logical
truth, (B) true in all worlds that can be depicted using Tarskiā™s World, but not a logical truth,
or (C) falsiļ¬able in some world that can be depicted by Tarskiā™s World. For each sentence of
type (C), build a world in which it is false, and save it as World 13.58.x, where x is the number
of the sentence. For each sentence of type (B), use a pencil and paper to depict a world in
which it is false. (In doing this exercise, assume that Medium simply means neither small nor
large, which seems plausible. However, it is not plausible to assume that Cube means neither a
dodecahedron nor tetrahedron, so you should not assume anything like this.)

Section 13.5
Chapter 14

Many English sentences take the form

QAB

where Q is a determiner expression like every, some, the, more than half the,
at least three, no, many, Maxā™s, etc.; A is a common noun phrase like cube,
student of logic, thing, etc.; and B is a verb phrase like sits in the corner or
is small.
Such sentences are used to express quantitative relationships between the
set of objects satisfying the common noun phrase and the set of objects satis-
fying the verb phrase. Here are some examples, with the determiner in bold:

Every cube is small.
Some cube is small.
More than half the cubes are small.
At least three cubes are small.
No cube is small.
Many cubes are small.
Maxā™s cube is small.

These sentences say of the set A of cubes in the domain of discourse and
the set B of small things in the domain of discourse that

every A is a B,
some A is a B,
more than half the Aā™s are Bā™s,
at least three Aā™s are Bā™s,
no A is a B,
many Aā™s are Bā™s, and
Maxā™s A is a B.

Each of these can be thought of as expressing a kind of binary relation between
A and B.
Linguistically, these words and phrases are known as determiners. The
determiners and
quantiļ¬ers relation expressed by a determiner is usually, though not always, a quantita-
tive relation between A and B. Sometimes this quantitative relation can be
captured using the fol quantiļ¬ers ā and ā, though sometimes it canā™t. For

364

example, to express more than half the Aā™s are Bā™s, it turns out that we need
to supplement fol to include new expressions that behave something like ā
and ā. When we add such expressions to the formal language, we call them
generalized quantiļ¬ers, since they extend the kinds of quantiļ¬cation we can generalized quantiļ¬ers
express in the language.
In this chapter, we will look at the logic of some English determiners
beyond some and all. We will consider not only determiners that can be ex-
pressed using the usual quantiļ¬ers of fol, but also determiners whose mean-
ings can only be captured by adding new quantiļ¬ers to fol.
In English, there are ways of expressing quantiļ¬cation other than deter-
miners. For example, the sentences
Max always eats pizza.
Max usually eats pizza.
Max often eats pizza.
Max seldom eats pizza.
Max sometimes eats pizza.
Max never eats pizza.
each express a quantitative relation between the set of times when Max eats
and the set of times when he eats pizza. But in these sentences it is the adverb
that is expressing quantiļ¬cation, not a determiner. While we are going to
discuss the logic only of determiners, much of what we say can be extended to adverbial quantiļ¬cation
other forms of quantiļ¬cation, including this kind of adverbial quantiļ¬cation.
In a sentence of the form Q A B, diļ¬erent determiners express very diļ¬erent
relations between A and B and so have very diļ¬erent logical properties. A valid
argument typically becomes invalid if we change any of the determiners. For
instance, while

No cube is small
d is a cube
d is not small

is a valid argument, it would become invalid if we replaced no by any of the
other determiners listed above. On the other hand, the valid argument

Many cubes are small
Every small block is left of d
Many cubes are left of d

remains valid if many is replaced by any of the above determiners other than
no. These are clearly logical facts, things weā™d like to understand at a more

Chapter 14