<< Предыдущая стр. 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
In this section we present more problems to help you solidify your understand-
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
More about Quantification / 365

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
366 / More about Quantification

theoretical level. For example, weвЂ™ll soon see that the determiners that can
replace Many in the second argument and still yield a valid argument are the
monotone increasing determiners.
There are two rather diп¬Ђerent approaches to studying quantiп¬Ѓcation. One
approaches to
quantiп¬Ѓcation approach studies determiners that can be expressed using the existing re-
sources of fol. In the п¬Ѓrst three sections, we look at several important English
determiners that can be deп¬Ѓned in terms of в€Ђ, в€ѓ, =, and the truth-functional
 << Предыдущая стр. 66(из 107 стр.)ОГЛАВЛЕНИЕ Следующая >>