<<

. 42
( 107 .)



>>

derive ⊥ from atomic sentences. If the argument is invalid, you should use Tarski™s World to construct
a counterexample world.

8.44 8.45
Adjoins(a, b) § Adjoins(b, c)
‚ ‚
SameRow(a, c)
¬(Cube(b) § b = c) ∨ Cube(c)
a=c

8.46 8.47
Cube(a) ∨ (Cube(b) ’ Tet(c)) Small(a) § (Medium(b) ∨ Large(c))
‚ ‚
Tet(c) ’ Small(c) Medium(b) ’ FrontOf(a, b)
(Cube(b) ’ Small(c)) ’ Small(b) Large(c) ’ Tet(c)
¬Cube(a) ’ Small(b) ¬Tet(c) ’ FrontOf(c, b)

8.48 8.49
Small(a) § (Medium(b) ∨ Large(c)) (Dodec(a) § Dodec(b))
‚ ‚
Medium(b) ’ FrontOf(a, b) ’ (SameCol(a, c) ’ Small(a))
Large(c) ’ Tet(c) (¬SameCol(b, c) § ¬Small(b))
’ (Dodec(b) § ¬Small(a))
¬Tet(c) ’ FrontOf(a, b)
SameCol(a, c) § ¬SameCol(b, c)
Dodec(a) ’ Small(b)

8.50 8.51
Cube(b) ” (Cube(a) ” Cube(c)) Cube(b) ” (Cube(a) ” Cube(c))
‚ ‚
Dodec(b) ’ (Cube(a) ” ¬Cube(c)) Dodec(b) ’ a = b

8.52 8.53
Cube(b) ” (Cube(a) ” Cube(c)) Small(a) ’ Small(b)
‚ ‚ Small(b) ’ (SameSize(b, c) ’ Small(c))
Dodec(b) ’ a = c
¬Small(a) ’ (Large(a) § Large(c))
SameSize(b, c) ’ (Large(c) ∨ Small(c))




Section 8.4
224
Part II
Quanti¬ers




225
226
Chapter 9

Introduction to Quanti¬cation

In English and other natural languages, basic sentences are made by combining
noun phrases and verb phrases. The simplest noun phrases are names, like Max
and Claire, which correspond to the constant symbols of fol. More complex
noun phrases are formed by combining common nouns with words known as
determiners, such as every, some, most, the, three, and no, giving us noun determiners
phrases like every cube, some man from Indiana, most children in the class,
the dodecahedron in the corner, three blind mice, and no student of logic.
Logicians call noun phrases of this sort quanti¬ed expressions, and sen-
tences containing them quanti¬ed sentences. They are so called because they quanti¬ed sentences
allow us to talk about quantities of things”every cube, most children, and so
forth.
The logical properties of quanti¬ed sentences are highly dependent on
which determiner is used. Compare, for example, the following arguments:

Every rich actor is a good actor.
Brad Pitt is a rich actor.
Brad Pitt is a good actor.

Many rich actors are good actors.
Brad Pitt is a rich actor.
Brad Pitt is a good actor.

No rich actor is a good actor.
Brad Pitt is a rich actor.
Brad Pitt is a good actor.

What a di¬erence a determiner makes! The ¬rst of these arguments is obvi-
ously valid. The second is not logically valid, though the premises do make the
conclusion at least plausible. The third argument is just plain dumb: in fact
the premises logically imply the negation of the conclusion. You can hardly
get a worse argument than that.
Quanti¬cation takes us out of the realm of truth-functional connectives.
Notice that we can™t determine the truth of quanti¬ed sentences by looking
at the truth values of constituent sentences. Indeed, sentences like Every rich



227
228 / Introduction to Quantification


actor is a good actor and No rich actor is a good actor really aren™t made up
of simpler sentences, at least not in any obvious way. Their truth values are
determined by the relationship between the collection of rich actors and the
collection of good actors: by whether all of the former or none of the former
are members of the latter.
Various non-truth-functional constructions that we™ve already looked at
are, in fact, hidden forms of quanti¬cation. Recall, for example, the sentence:
hidden quanti¬cation

Max is home whenever Claire is at the library.
You saw in Exercise 7.31 that the truth of this sentence at a particular time is
not a truth function of its parts at that time. The reason is that whenever is
an implicit form of quanti¬cation, meaning at every time that. The sentence
means something like:
Every time when Claire is at the library is a time when Max is at home.
Another example of a non-truth-functional connective that involves implicit
quanti¬cation is logically implies. You can™t tell whether P logically implies
Q just by looking at the truth values of P and Q. This is because the claim
means that every logically possible circumstance that makes P true makes Q
true. The claim implicitly quanti¬es over possible circumstances.
While there are many forms of quanti¬cation in English, only two are built
explicitly into fol. This language has two quanti¬er symbols, ∀ and ∃, mean-
quanti¬ers of fol
ing everything and something respectively. This may seem like a very small
number of quanti¬ers, but surprisingly many other forms of quanti¬cation can
be de¬ned from ∀ and ∃ using predicates and truth-functional connectives, in-
cluding phrases like every cube, three blind mice, no tall student, and whenever.
Some quanti¬ed expressions are outside the scope of fol, however, including
most students, many cubes, and in¬nitely many prime numbers. We™ll discuss
these issues in Chapter 14.


Section 9.1
Variables and atomic w¬s
Before we can show you how fol™s quanti¬er symbols work, we need to intro-
duce a new type of term, called a variable. Variables are a kind of auxiliary
variables
symbol. In some ways they behave like individual constants, since they can
appear in the list of arguments immediately following a predicate or function
symbol. But in other ways they are very di¬erent from individual constants. In
particular, their semantic function is not to refer to objects. Rather, they are



Chapter 9
Variables and atomic wffs / 229



placeholders that indicate relationships between quanti¬ers and the argument
positions of various predicates. This will become clearer with our discussion
of quanti¬ers.
First-order logic assumes an in¬nite list of variables so that we will never
run out of them, no matter how complex a sentence may get. We take these
variables to be any of the letters t, u, v, w, x, y, and z, with or without
subscripts. So, for example, x, u23, and z6 are all variables in our dialect
of fol. Fitch understands all of these variables, but Tarski™s World does not.
Tarski™s World uses only the six variables u, v, w, x, y, and z without subscripts.
This imposes an expressive limitation on the language used in Tarski™s World,
though in actual practice you™ll seldom have call for more than four or ¬ve
variables.
Adding variables expands the set of terms of the language. Up until now, terms with variables
individual constants (names) were the only basic terms. If the language con-
tained function symbols, we built additional terms by repeated application of
these function symbols. Now we have two types of basic terms, variables and
individual constants, and can form complex terms by applying function sym-
bols to either type of basic term. So in addition to the term father(max), we will
have the term father(x), and in addition to (0 + 1) — 1, we have (y + z) — z.
These new terms allow us to produce expressions that look like atomic
sentences, except that there are variables in place of some individual con-
stants. For example, Home(x), Taller(max, y), and Taller(father(z), z) are such
expressions. We call these expressions atomic well-formed formulas, or atomic atomic w¬s
w¬s. They are not sentences, but will be used in conjunction with quanti¬er
symbols to build sentences. The term sentence is reserved for well-formed for-
mulas in which any variables that do occur are used together with quanti¬ers
that bind them. We will give the de¬nitions of sentence and bound variable
in due course.

Remember

1. The language fol has an in¬nite number of variables, any of t, u, v,
w, x, y, and z, with or without numerical subscripts.

2. The program Fitch understands all of these variables; Tarski™s World
only understands variables u through z without subscripts.

3. Variables can occur in atomic w¬s in any position normally occupied
by a name.




Section 9.1
230 / Introduction to Quantification


Section 9.2
The quanti¬er symbols: ∀, ∃
The quanti¬er symbols ∀ and ∃ let us express certain rudimentary claims
about the number (or quantity) of things that satisfy some condition. Specif-
ically, they allow us to say that all objects satisfy some condition, or that
at least one object satis¬es some condition. When used in conjunction with
identity (=), they can also be used to express more complex numerical claims,
for instance, that there are exactly three things that satisfy some condition.

Universal quanti¬er (∀)
The symbol ∀ is used to express universal claims, those we express in English
using quanti¬ed phrases like everything, each thing, all things, and anything.
everything, each thing,
all things, anything It is always used in connection with a variable, and so is said to be a variable
binding operator. The combination ∀x is read “for every object x,” or (some-
what misleadingly) “for all x.”1 If we wanted to translate the (rather unlikely)
English sentence Everything is at home into ¬rst-order logic, we would use the
fol sentence
∀x Home(x)
This says that every object x meets the following condition: x is at home. Or,
to put it more naturally, it says that everything whatsoever is at home.
Of course, we rarely make such unconditional claims about absolutely ev-
erything. More common are restricted universal claims like Every doctor is
smart. This sentence would be translated as

∀x (Doctor(x) ’ Smart(x))

This fol sentence claims that given any object at all”call it x”if x is a
doctor, then x is smart. To put it another way, the sentence says that if you
pick anything at all, you™ll ¬nd either that it is not a doctor or that it is smart
(or perhaps both).

Existential quanti¬er (∃)
The symbol ∃ is used to express existential claims, those we express in English
something, at least one
thing, a, an using such phrases as something, at least one thing, a, and an. It too is always
1 We encourage students to use the ¬rst locution when reading formulas, at least for a
few weeks, since we have seen many students who have misunderstood the basic function
of variables as a result of reading them the second way.




Chapter 9
Wffs and sentences / 231



used in connection with a variable, and so is a variable binding operator. The
combination ∃x is read “for some object x,” or (somewhat misleadingly) “for
some x.” If we wanted to translate the English sentence Something is at
home into ¬rst-order logic, we would use the fol sentence

∃x Home(x)

This says that some object x meets the following condition: x is at home.
While it is possible to make such claims, it is more common to assert
that something of a particular kind meets some condition, say, Some doctor
is smart. This sentence would be translated as

∃x (Doctor(x) § Smart(x))

This sentence claims that some object, call it x, meets the complex condition:
x is both a doctor and smart. Or, more colloquially, it says that there is at
least one smart doctor.


Section 9.3
W¬s and sentences

Notice that in some of the above examples, we formed sentences out of complex
expressions that were not themselves sentences, expressions like

Doctor(x) § Smart(x)

that contain variables not bound by any quanti¬er. Thus, to systematically
describe all the sentences of ¬rst-order logic, we ¬rst need to describe a larger

<<

. 42
( 107 .)



>>