<<

. 43
( 107 .)



>>

class, the so-called well-formed formulas, or w¬s.
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
formula (w¬)
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).



Section 9.3
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
whole w¬.
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
the w¬:
∃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
sentences
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
of something.
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:
¬Home(max)
¬¬Home(max)
¬¬¬Home(max)
.
.
.



Chapter 9
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.

Remember

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).




Section 9.3
234 / Introduction to Quantification


Exercises


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-
o
‚ 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
your ¬le.


Section 9.4
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
satisfaction
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).



Chapter 9
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
sentence.
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
until later.
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




Section 9.4
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
bound:
∃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)


Remember

—¦ Quanti¬ed sentences make claims about some intended domain of dis-
course.

—¦ 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.




Chapter 9
Semantics for the quantifiers / 237




Table 9.1: Summary of the game rules

Form Your commitment Player to move Goal

<<

. 43
( 107 .)



>>