<<

. 57
( 107 .)



>>

quanti¬cation to be the people mentioned in the table. Turn in your answers.

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

<<

. 57
( 107 .)



>>