11.31 Translate the following sentences into the blocks language augmented with the four function

‚| symbols lm, rm, fm, and bm discussed in Section 1.5 (page 33) and further discussed in con-

nection with quanti¬ers in Section 9.7 (page 252). Tell which of these sentences are true in

Malcev™s World.

1. Every cube is to the right of the leftmost block in the same row.

2. Every block is in the same row as the leftmost block in the same row.

3. Some block is in the same row as the backmost block in the same column.

4. Given any two blocks, the ¬rst is the leftmost block in the same row as the second if

and only if there is nothing to the left of the second.

5. Given any two blocks, the ¬rst is the leftmost block in the same row as the second if

and only if there is nothing to the left of the second and the the two blocks are in the

same row.

Turn in your answers.

Chapter 11

Prenex form / 311

11.32 Using the ¬rst-order language of arithmetic described earlier, express each of the following in

fol.

1. Every number is either 0 or greater than 0.

2. The sum of any two numbers greater than 1 is smaller than the product of the same

two numbers.

3. Every number is even. [This is false, of course.]

4. If x2 = 1 then x = 1. [Hint: Don™t forget the implicit quanti¬er.]

√ √

’b+ b2 ’4ac ’b’ b2 ’4ac

2

5. For any number x, if ax +bx+c = 0 then either x = or x = .

2a 2a

In this problem use a, b, c as constant symbols, but treat x as a variable, as usual in

algebra.

Section 11.7

Prenex form

When we translate complex sentences of English into fol, it is common to

end up with sentences where the quanti¬ers and connectives are all scrambled

together. This is usually due to the way in which the translations of complex

noun phrases of English use both quanti¬ers and connectives:

∀x (P(x) ’ . . . )

∃x (P(x) § . . . )

As a result, the translation of (the most likely reading of) a sentence like

Every cube to the left of a tetrahedron is in back of a dodecahedron ends up

looking like

∀x [(Cube(x) § ∃y (Tet(y) § LeftOf(x, y))) ’ ∃y (Dodec(y) § BackOf(x, y))]

While this is the most natural translation of our sentence, there are sit-

uations where it is not the most convenient one. It is sometimes important

that we be able to rearrange sentences like this so that all the quanti¬ers are

out in front and all the connectives in back. Such a sentence is said to be in prenex form

prenex form, since all the quanti¬ers come ¬rst.

Stated more precisely, a w¬ is in prenex normal form if either it contains

no quanti¬ers at all, or else is of the form

Q1 v1 Q2 v2 . . . Qn vn P

where each Qi is either ∀ or ∃, each vi is some variable, and the w¬ P is

quanti¬er-free.

Section 11.7

312 / Multiple Quantifiers

There are several reasons one might want to put sentences into prenex

form. One is that it gives you a nice measure of the logical complexity of the

sentences. What turns out to matter is not so much the number of quanti¬ers,

as the number of times you get a ¬‚ip from ∀ to ∃ or the other way round.

The more of these so-called alternations, the more complex the sentence is,

quanti¬er alternations

logically speaking. Another reason is that this prenex form is quite analogous

to the conjunctive normal form for quanti¬er-free w¬s we studied earlier. And

like that normal form, it is used extensively in automated theorem proving.

It turns out that every sentence is logically equivalent to one (in fact many)

in prenex form. In this section we will present some rules for carrying out this

transformation. When we apply the rules to our earlier example, we will get

∀x ∀y ∃z [(Cube(x) § Tet(y) § LeftOf(x, y)) ’ (Dodec(z) § BackOf(x, z))]

To arrive at this sentence, we did not just blindly pull quanti¬ers out in

converting to

prenex form front. If we had, it would have come out all wrong. There are two problems.

One is that the ¬rst ∃y in the original sentence is, logically speaking, inside

a ¬. (To see why, replace ’ by its de¬nition in terms of ¬ and ∨.) The

DeMorgan laws for quanti¬ers tell us that it will end up being a universal

quanti¬er. Another problem is that the original sentence has two quanti¬ers

that bind the variable y. There is no problem with this, but if we pull the

quanti¬ers out front, there is suddenly a clash. So we must ¬rst change one

of the ys to some other variable, say z.

We have already seen the logical equivalences that are needed for putting

sentences in prenex form. They were summarized in a box on page 282. They

allowed us to move negations inside quanti¬ers by switching quanti¬ers, to

distribute ∀ over §, ∃ over ∨, to replace bound variables by other variables,

and to move quanti¬ers past formulas in which the variable being quanti¬ed

is not free. In order to apply these maneuvers to sentences with ’ or ”, one

needs to either replace these symbols with equivalent versions using ¬, ∨ and

§ (or else derive some similar rules for these symbols).

The basic strategy for putting sentences into prenex form is to work from

the inside out, working on parts, then putting them together. By way of

example, here is a chain of equivalences where we start with a sentence not in

prenex normal form and turn it into a logically equivalent one that is prenex

normal form, explaining why we do each step as we go.

∃x P(x) ’ ∃y Q(y)

In getting a formula into prenex form, it™s a good idea to get rid of conditionals

in favor of Boolean connectives, since these interact more straightforwardly

Chapter 11

Prenex form / 313

with the quanti¬ers in our principles. So our ¬rst step is to obtain

¬∃x P(x) ∨ ∃y Q(y)

Now we have a disjunction, but the ¬rst disjunct is no longer in prenex form.

That can be ¬xed using DeMorgan™s law:

∀x ¬P(x) ∨ ∃y Q(y)

Now we can use the Null Quanti¬cation Principle to move either of the quan-

ti¬ers. We chose to move ∃y ¬rst, for no particular reason.

∃y [∀x ¬P(x) ∨ Q(y)]

Finally, we move ∀x

∃y ∀x (¬P(x) ∨ Q(y))

If we had done it in the other order, we would have obtained the super¬cially

di¬erent

∀x ∃y (¬P(x) ∨ Q(y))

While the order of mixed quanti¬ers is usually quite important, in this case it

does not matter because of the pattern of variables within the matrix of the

w¬.

Here is another example:

(∃x P(x) ∨ R(b)) ’ ∀x (P(x) § ∀x Q(x))

Again we have a conditional, but this time neither the antecedent nor the

consequent is in prenex normal form. Following the basic strategy of working

from the inside out, let™s ¬rst put the antecedent and then the consequent

each into prenex form and then worry about what to do about the conditional.

Using the principle of null quanti¬cation on the antecedent we obtain

∃x (P(x) ∨ R(b)) ’ ∀x (P(x) § ∀x Q(x))

Next we use the principle involving the distribution of ∀ and § on the conse-

quent:

∃x (P(x) ∨ R(b)) ’ ∀x (P(x) § Q(x))

Now both the antecedent and consequent are in prenex form. Recall that it™s

a good idea to get rid of conditionals in favor of Boolean connectives. Hence,

we replace ’ by its equivalent using ¬ and ∨:

¬∃x (P(x) ∨ R(b)) ∨ ∀x (P(x) § Q(x))

Section 11.7

314 / Multiple Quantifiers

Now we have a disjunction, but one of the disjuncts is not in prenex form.

Again, that can be ¬xed using DeMorgan™s law:

∀x ¬(P(x) ∨ R(b)) ∨ ∀x (P(x) § Q(x))

Now both disjuncts are in prenex form. We need to pull the ∀™s out in front. (If

they were both ∃™s, we could do this easily, but they aren™t.) Here is probably

the least obvious step in the process: In order to get ready to pull the ∀™s out

in front, we replace the x in the second disjunct by a variable (say z) not in

the ¬rst disjunct:

∀x ¬(P(x) ∨ R(b)) ∨ ∀z (P(z) § Q(z))

We now use the principle of null quanti¬cation twice, ¬rst on ∀x:

∀x [¬(P(x) ∨ R(b)) ∨ ∀z (P(z) § Q(z))]

Finally, we use the same principle on ∀z, giving a w¬ in prenex form:

∀x ∀z [¬(P(x) ∨ R(b)) ∨ (P(z) § Q(z))]

It is at this step that things would have gone wrong if we had not ¬rst changed

the second x to a z. Do you see why? The wrong quanti¬ers would have bound

the variables in the second disjunct.

If we wanted to, for some reason, we could now go on and put the inner

part, the part following all the quanti¬ers, into one of our propositional normal

forms, CNF or DNF.

With these examples behind us, here is a step-by-step transformation of

our original sentence into the one in prenex form given above. We have ab-

breviated the predicates in order to make it easier to read.

∀x [(C(x) § ∃y (T(y) § L(x, y))) ’ ∃y (D(y) § B(x, y))] ”

∀x [¬(C(x) § ∃y (T(y) § L(x, y))) ∨ ∃y (D(y) § B(x, y))] ”

∀x [¬∃y (C(x) § T(y) § L(x, y)) ∨ ∃y (D(y) § B(x, y))] ”

∀x [∀y ¬(C(x) § T(y) § L(x, y)) ∨ ∃y (D(y) § B(x, y))] ”

∀x [∀y ¬(C(x) § T(y) § L(x, y)) ∨ ∃z (D(z) § B(x, z))] ”

∀x ∀y [¬(C(x) § T(y) § L(x, y)) ∨ ∃z (D(z) § B(x, z))] ”

∀x ∀y [∃z ¬(C(x) § T(y) § L(x, y)) ∨ ∃z (D(z) § B(x, z))] ”

∀x ∀y ∃z [¬(C(x) § T(y) § L(x, y)) ∨ (D(z) § B(x, z))] ”

∀x ∀y ∃z [(C(x) § T(y) § L(x, y)) ’ (D(z) § B(x, z))]

Remember

A sentence is in prenex form if any quanti¬ers contained in it are out in

front. Any sentence is logically equivalent to one in prenex form.

Chapter 11

Some extra translation problems / 315

Exercises

Derive the following from the principles given earlier, by replacing ’ by its de¬nition in terms of ∨

and ¬.

11.33 ∀x P ’ Q ” ∃x [P ’ Q] if x not free in Q

11.34 ∃x P ’ Q ” ∀x [P ’ Q] if x not free in Q

11.35 P ’ ∀x Q ” ∀x [P ’ Q] if x not free in P

11.36 P ’ ∃x Q ” ∃x [P ’ Q] if x not free in P

11.37 (Putting sentences in Prenex form) Open Jon Russell™s Sentences. You will ¬nd ten sentences,

‚ at the odd numbered positions. Write a prenex form of each sentence in the space below it.

Save your sentences. Open a few worlds, and make sure that your prenex form has the same

truth value as the sentence above it.

11.38 (Some invalid quanti¬er manipulations) We remarked above on the invalidity of some quanti¬er

‚ manipulations that are super¬cially similar to the valid ones. In fact, in both cases one side

is a logical consequence of the other side, but not vice versa. We will illustrate this. Build a

world in which (1) and (3) below are true, but (2) and (4) are false.

1. ∀x [Cube(x) ∨ Tet(x)]

2. ∀x Cube(x) ∨ ∀x Tet(x)

3. ∃x Cube(x) § ∃x Small(x)

4. ∃x [Cube(x) § Small(x)]

Section 11.8

Some extra translation problems

Some instructors concentrate more on translation than others. For those who

like to emphasize this skill, we present some additional challenging exercises

here.

Section 11.8

316 / Multiple Quantifiers