In the
propositional calculus we know that any wff is
equivalent to a wff in conjunctive normal form and to
a wff in disjunctive normal form. Let's see whether
we can do something similar with the wffs of the
predicate calculus. We'll start with a definition. A wff
W is in prenex normal form if all its quantifiers are on the left of the
expression. In other words, a prenex normal form looks
like the following:
Qlхl ... Qnxn M,
where each Q, is either " or $, each xi is distinct, and M is a wff
without quantifiers. For example, the following wffs
are in prenex normal form:
$ x p(x),
"x p(x,y),
"x $y (p(x, y),
" x $y " z (p(x)
Ú q(y)
Ù r(x,
z)).
Is any wff equivalent to some wff in prenex normal form? Yes. In fact there's an easy algorithm
to obtain the desired form. The idea is to make sure that variables have
distinct names and then apply equivalences that send all quantifiers to the
left end of the wff. Here's the algorithm:
Any wff W has an equivalent prenex
normal form, which can be constructed as follows:
1. Rename the
variables of W so that no quantifiers
use the same variable name and such that the quantified variable names are
distinct from the free variable names.
2.
Move quantifiers to the left by using equivalences G.2), G.7), G.8), and G.9).
The renaming of
variables is important to the success of the algorithm. For example, we can't
replace p(x) v Vx q(x) by Vx
(p(x) v q(x)) because they aren't equivalent. But we can rename variables to
obtain the following equivalence:
p(x) Ú "х q(x) = p(x)
Ú "y q(y)