Prenex Normal Form Algorithm

 

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)