We have already explained what an atomic w´¬Ç is: any n-ary predicate
followed by n terms, where terms can now contain either variables or individ-
ual constants. We will say that any variable that occurs in an atomic w´¬Ç is
free or unbound. Using atomic w´¬Çs as our building blocks, we can construct free variable
more complicated w´¬Çs by repeatedly applying the following rules. Note that
the last two clauses also explain how variables become bound when we apply bound variable
quanti´¬üers to w´¬Çs.
1. If P is a w´¬Ç, so is ┬¬P. well-formed
2. If P1, . . . , Pn are w´¬Çs, so is (P1 Ôł§ . . . Ôł§ Pn ).
3. If P1, . . . , Pn are w´¬Çs, so is (P1 ÔłĘ . . . ÔłĘ Pn ).
4. If P and Q are w´¬Çs, so is (P Ôć’ Q).
232 / Introduction to Quantification
5. If P and Q are w´¬Çs, so is (P Ôć” Q).
6. If P is a w´¬Ç and ╬Ż is a variable (i.e., one of t, u, v, w, x, . . . ), then
ÔłÇ╬Ż P is a w´¬Ç, and any occurrence of ╬Ż in ÔłÇ╬Ż P is said to be bound.
7. If P is a w´¬Ç and ╬Ż is a variable, then Ôłâ╬Ż P is a w´¬Ç, and any occurrence
of ╬Ż in Ôłâ╬Ż P is said to be bound.
By convention, we allow the outermost parentheses in a w´¬Ç to be dropped,
writing A Ôł§ B rather than (A Ôł§ B), but only if the parentheses enclose the
The way these grammatical rules work is pretty straightforward. For ex-
ample, starting from the atomic w´¬Çs Cube(x) and Small(x) we can apply rule
2 to get the w´¬Ç:
(Cube(x) Ôł§ Small(x))
Similarly, starting from the atomic w´¬Ç LeftOf(x, y) we can apply rule 7 to get
Ôłây LeftOf(x, y)
In this formula the variable y has been bound by the quanti´¬üer Ôłây. The variable
x, on the other hand, has not been bound; it is still free.
The rules can also be applied to complex w´¬Çs, so from the above two w´¬Çs
and rule 4 we can generate the following w´¬Ç:
((Cube(x) Ôł§ Small(x)) Ôć’ Ôłây LeftOf(x, y))
A sentence is a w´¬Ç with no unbound (free) variables. None of the w´¬Çs
displayed above are sentences, since they all contain free variables. To make
a sentence out of the last of these, we can simply apply rule 6 to produce:
ÔłÇx ((Cube(x) Ôł§ Small(x)) Ôć’ Ôłây LeftOf(x, y))
Here all occurrences of the variable x have been bound by the quanti´¬üer ÔłÇx.
So this w´¬Ç is a sentence since it has no free variables. It claims that for every
object x, if x is both a cube and small, then there is an object y such that x
is to the left of y. Or, to put it more naturally, every small cube is to the left
These rules can be applied over and over again to form more and more
complex w´¬Çs. So, for example, repeated application of the ´¬ürst rule to the w´¬Ç
Home(max) will give us all of the following w´¬Çs:
Wffs and sentences / 233
Since none of these contains any variables, and so no free variables, they are
all sentences. They claim, as you know, that Max is not home, that it is not
the case that Max is not home, that it is not the case that it is not the case
that Max is not home, and so forth.
We have said that a sentence is a w´¬Ç with no free variables. However, it
can sometimes be a bit tricky deciding whether a variable is free in a w´¬Ç. For
example, there are no free variables in the w´¬Ç,
Ôłâx (Doctor(x) Ôł§ Smart(x))
However there is a free variable in the deceptively similar w´¬Ç,
Ôłâx Doctor(x) Ôł§ Smart(x)
Here the last occurrence of the variable x is still free. We can see why this is the
case by thinking about when the existential quanti´¬üer was applied in building
up these two formulas. In the ´¬ürst one, the parentheses show that the quanti´¬üer
was applied to the conjunction (Doctor(x) Ôł§ Smart(x)). As a consequence, all
occurrences of x in the conjunction were bound by this quanti´¬üer. In contrast,
the lack of parentheses show that in building up the second formula, the
existential quanti´¬üer was applied to form Ôłâx Doctor(x), thus binding only the
occurrence of x in Doctor(x). This formula was then conjoined with Smart(x),
and so the latterÔÇ™s occurrence of x did not get bound.
Parentheses, as you can see from this example, make a big di´¬Çerence.
They are the way you can tell what the scope of a quanti´¬üer is, that is, which scope of quanti´¬üer
variables fall under its in´¬‚uence and which donÔÇ™t.
1. Complex w´¬Çs are built from atomic w´¬Çs by means of truth-functional
connectives and quanti´¬üers in accord with the rules on page 231.
2. When you append either quanti´¬üer ÔłÇx or Ôłâx to a w´¬Ç P, we say that
the quanti´¬üer binds all the free occurrences of x in P.
3. A sentence is a w´¬Ç in which no variables occur free (unbound).
234 / Introduction to Quantification
9.1 (Fixing some expressions) Open the sentence ´¬üle BernsteinÔÇ™s Sentences. The expressions in this
├‚ list are not quite well-formed sentences of our language, but they can all be made sentences by
slight modi´¬ücation. Turn them into sentences without adding or deleting any quanti´¬üer symbols.
With some of them, there is more than one way to make them a sentence. Use Verify to make
sure your results are sentences and then submit the corrected ´¬üle.
9.2 (Fixing some more expressions) Open the sentence ´¬üle Sch┬Ęn´¬ünkelÔÇ™s Sentences. Again, the ex-
├‚ pressions in this list are not well-formed sentences. Turn them into sentences, but this time,
do it only by adding quanti´¬üer symbols or variables, or both. Do not add any parentheses. Use
Verify to make sure your results are sentences and submit the corrected ´¬üle.
9.3 (Making them true) Open BozoÔÇ™s Sentences and LeibnizÔÇ™s World. Some of the expressions in this
├‚ ´¬üle are not w´¬Çs, some are w´¬Çs but not sentences, and one is a sentence but false. Read and
assess each one. See if you can adjust each one to make it a true sentence with as little change
as possible. Try to capture the intent of the original expression, if you can tell what that was
(if not, donÔÇ™t worry). Use Verify to make sure your results are true sentences and then submit
Semantics for the quanti´¬üers
When we described the meanings of our various connectives, we told you how
the truth value of a complex sentence, say ┬¬P, depends on the truth values
of its constituents, in this case P. But we have not yet given you similar rules
for determining the truth value of quanti´¬üed sentences. The reason is simple:
the expression to which we apply the quanti´¬üer in order to build a sentence is
usually not itself a sentence. We could hardly tell you how the truth value of
Ôłâx Cube(x) depends on the truth value of Cube(x), since this latter expression
is not a sentence at all: it contains a free variable. Because of this, it is neither
true nor false.
To describe when quanti´¬üed sentences are true, we need to introduce the
auxiliary notion of satisfaction. The basic idea is simple, and can be illustrated
with a few examples. We say that an object satis´¬ües the atomic w´¬Ç Cube(x)
if and only if the object is a cube. Similarly, we say an object satis´¬ües the
complex w´¬Ç Cube(x) Ôł§ Small(x) if and only if it is both a cube and small. As
a ´¬ünal example, an object satis´¬ües the w´¬Ç Cube(x) ÔłĘ ┬¬Large(x) if and only if
it is either a cube or not large (or both).
Semantics for the quantifiers / 235
Di´¬Çerent logic books treat satisfaction in somewhat di´¬Çerent ways. We
will describe the one that is built into the way that TarskiÔÇ™s World checks
the truth of quanti´¬üed sentences. Suppose S(x) is a w´¬Ç containing x as its
only free variable, and suppose we wanted to know whether a given object
satis´¬ües S(x). If this object has a name, say b, then form a new sentence S(b)
by replacing all free occurrences of x by the individual constant b. If the new
sentence S(b) is true, then the object satis´¬ües the formula S(x); if the sentence
is not true, then the object does not satisfy the formula.
This works ´¬üne as long as the given object has a name. But ´¬ürst-order logic
doesnÔÇ™t require that every object have a name. How can we de´¬üne satisfaction
for objects that donÔÇ™t have names? It is for this reason that TarskiÔÇ™s World
has, in addition to the individual constants a, b, c, d, e, and f, a further list
n1 , n2, n3 , . . . of individual constants. If we want to know whether a certain
object without a name satis´¬ües the formula S(x), we choose the ´¬ürst of these
individual constants not in use, say n6, temporarily name the given object
with this symbol, and then check to see whether the sentence S(n6 ) is true.
Thus, any small cube satis´¬ües Cube(x) Ôł§ Small(x), because if we were to use
n6 as a name of such a small cube, then Cube(n6 ) Ôł§ Small(n6 ) would be a true
Once we have the notion of satisfaction, we can easily describe when a
sentence of the form Ôłâx S(x) is true. It will be true if and only if there is at least semantics of Ôłâ
one object that satis´¬ües the constituent w´¬Ç S(x). So Ôłâx (Cube(x) Ôł§ Small(x))
is true if there is at least one object that satis´¬ües Cube(x) Ôł§ Small(x), that is,
if there is at least one small cube. Similarly, a sentence of the form ÔłÇx S(x)
is true if and only if every object satis´¬ües the constituent w´¬Ç S(x). Thus semantics of ÔłÇ
ÔłÇx (Cube(x) Ôć’ Small(x)) is true if every object satis´¬ües Cube(x) Ôć’ Small(x),
that is, if every object either isnÔÇ™t a cube or is small.
This approach to satisfaction is conceptually simpler than some. A more
common approach is to avoid the introduction of new names by de´¬üning sat-
isfaction for w´¬Çs with an arbitrary number of free variables. We will not need
this for specifying the meaning of quanti´¬üers, but we will need it in some of the
more advanced sections. For this reason, we postpone the general discussion
In giving the semantics for the quanti´¬üers, we have implicitly assumed
that there is a relatively clear collection of objects that we are talking about.
For example, if we encounter the sentence ÔłÇx Cube(x) in TarskiÔÇ™s World, we
interpret this to be a claim about the objects depicted in the world window.
We do not judge it to be false just because the moon is not a cube. Similarly,
if we encounter the sentence ÔłÇx (Even(x2) Ôć’ Even(x)), we interpret this as a
claim about the natural numbers. It is true because every object in the domain
236 / Introduction to Quantification
we are talking about, natural numbers, satis´¬ües the constituent w´¬Ç.
In general, sentences containing quanti´¬üers are only true or false relative to
some domain of discourse or domain of quanti´¬ücation. Sometimes the intended
domain of discourse
domain contains all objects there are. Usually, though, the intended domain
is a much more restricted collection of things, say the people in the room,
or some particular set of physical objects, or some collection of numbers. In
this book, we will specify the domain explicitly unless it is clear from context
what domain is intended.
In the above discussion, we introduced some notation that we will use a
lot. Just as we often used P or Q to stand for a possibly complex sentence of
propositional logic, so too we will often use S(x) or P(y) to stand for a possibly
complex w´¬Ç of ´¬ürst-order logic. Thus, P(y) may stand for a w´¬Ç like:
Ôłâx (LeftOf(x, y) ÔłĘ RightOf(x, y))
When we then write, say, P(b), this stands for the result of replacing all the
free occurrences of y by the individual constant b:
Ôłâx (LeftOf(x, b) ÔłĘ RightOf(x, b))
It is important to understand that the variable displayed in parentheses
only stands for the free occurrences of the variable. For example, if S(x) is
used to refer to the w´¬Ç we looked at earlier, where x appeared both free and
Ôłâx Doctor(x) Ôł§ Smart(x)
then S(c) would indicate the following substitution instance, where c is sub-
stituted for the free occurrence of x:
Ôłâx Doctor(x) Ôł§ Smart(c)
Ô—¦ Quanti´¬üed sentences make claims about some intended domain of dis-
Ô—¦ A sentence of the form ÔłÇx S(x) is true if and only if the w´¬Ç S(x) is
satis´¬üed by every object in the domain of discourse.
Ô—¦ A sentence of the form Ôłâx S(x) is true if and only if the w´¬Ç S(x) is
satis´¬üed by some object in the domain of discourse.
Semantics for the quantifiers / 237
Table 9.1: Summary of the game rules
Form Your commitment Player to move Goal