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