Chapter 3 Logical Formulas76
which more clearly shows that the separate occurrences of 8 xin (3.28) are unre-
lated.
Renaming variables in this way allows every predicate formula to be converted
into an equivalent formula in which every variable name is used in only one way.
Specifically, a predicate formula satisfies theunique variable conventionif
for every variablex, there is at most one quantified occurrence ofx, that is, at
most one occurrence of either “ 8 x” or “ 9 x,” and moreover, “ 8 x” and “ 9 x”
don’t both occur, and if there is a subformula of the form 8 x:F or the form 9 x:F, then all the
occurrences ofxthat appear anywhere in the whole formula are within the
formulaF.So formula (3.28) violates the unique variable convention because “ 8 x” occurs
twice, but formula (3.29) is OK.
A further example is the formula
Œ 8 x 9 y:P.x/ANDQ.x;y/ç IMPLIES (3.30). 9 x:R.x;z//OR 9 x 8 z:S.x;y;w;z/:
Formula (3.30) violates the unique variable convention because there are three
quantified occurrences ofxin the formula, namely, the initial “ 8 x” and then two
occurrences of “ 9 x” later. It violates the convention in others ways as well. For
instance, there is an occurrence ofythat is not inside the subformula 9 y:P.x/AND
Q.y/.
It turns out thateverypredicate formula can be changed into an equivalent for-
mula that satisfies the unique variable convention—just by renaming some of the
occurrences of its variables, as we did this when we renamed the first two occur-
rences ofxin (3.28) intoy’s to obtain the equivalent formula (3.29).
(a)Rename occurrences of variables in (3.30) to obtain an equivalent formula
that satisfies the unique variable convention. Try to rename as few occurrences as
posible.
(b)Describe a general procedure for renaming variables in any predicate formula
to obtain an equivalent formula satisfying the unique variable convention.
Homework Problems
Problem 3.29.
Express each of the following predicates and propositions in formal logic notation.
The domain of discourse is the nonnegative integers,N. Moreover, in addition to