a counterexample world.
Adjoins(a, b) Ôł§ Adjoins(b, c)
┬¬(Cube(b) Ôł§ b = c) ÔłĘ Cube(c)
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)
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)
Cube(b) Ôć” (Cube(a) Ôć” Cube(c)) Cube(b) Ôć” (Cube(a) Ôć” Cube(c))
Dodec(b) Ôć’ (Cube(a) Ôć” ┬¬Cube(c)) Dodec(b) Ôć’ a = b
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))
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
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
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:
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.
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
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
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
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
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.
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.
230 / Introduction to Quantification
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
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.
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
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.
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