Main Page | See live article | Alphabetical index 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. This can be shown using the logical equivalence of formulas under the rewritings , and ,where is free in , 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. Prenex normal forms are the main tool used by Gödel to prove of his completeness theorem. This article is from Wikipedia. All text is available under the terms of the GNU Free Documentation License.