Prenex normal form

In predicate calculus, a formula is in prenex normal form if it can be written as a string of quantifiers, followed by a quantifier-free part, referred to as the matrix. All first order formulas are logically equivalent to some formula in prenex normal form.

Related Topics:
Predicate calculus - Formula - Normal form - Quantifier - Matrix - First order - Logically equivalent

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

This can be shown using the logical equivalence of formulas under the rewritings

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:orall x ( P(x) ightarrow Q ) equiv exists x P(x) ightarrow Q

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

and

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:orall x ( P ightarrow Q(x) ) equiv P ightarrow orall x Q(x),

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

where x is free in Q, and their similar existential duals, and noting that via successive application of these rules all the quantifiers can be moved to the front of the formula.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Some proof calculi will only deal with a theory whose formulae are written in prenex normal form. The concept is essential for developing the arithmetical hierarchy and the analytical hierarchy.

Related Topics:
Arithmetical hierarchy - Analytical hierarchy

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Prenex normal forms are the main tool used by Gödel to prove his completeness theorem.

Related Topics:
Gödel - Completeness theorem

~ ~ ~ ~ ~ ~ ~ ~ ~ ~