Editing Prenex normal form (section)

{{Short description|Formalism of first-order logic}}
A [[formula (mathematical logic)|formula]] of the [[predicate calculus]] is in '''prenex<ref>The term 'prenex' comes from the [[Latin]] ''praenexus'' "tied or bound up in front", past participle of ''praenectere'' [http://cs.nyu.edu/pipermail/fom/2007-November/012328.html] (archived as of May 27, 2011 at [https://web.archive.org/web/20110527102347/http://cs.nyu.edu/pipermail/fom/2007-November/012328.html])</ref> [[Normal form (abstract rewriting)|normal form]]''' ('''PNF''') if it is [[Rewriting#Logic|written]] as a string of [[quantifier (logic)|quantifiers]] and [[bound variable|bound variables]], called the '''prefix''', followed by a quantifier-free part, called the '''matrix'''.<ref>Hinman, P. (2005), p. 110</ref> Together with the normal forms in [[Propositional calculus|propositional logic]] (e.g. [[disjunctive normal form]] or [[conjunctive normal form]]), it provides a [[canonical normal form]] useful in [[automated theorem proving]]. 

Every formula in [[classical logic]] is [[logically equivalent]] to a formula in prenex normal form. For example, if <math>\phi(y)</math>, <math>\psi(z)</math>, and <math>\rho(x)</math> are quantifier-free formulas with the free variables shown then
:<math>\forall x \exists y \forall z (\phi(y) \lor (\psi(z) \rightarrow \rho(x)))</math>
is in prenex normal form with matrix <math>\phi(y) \lor (\psi(z) \rightarrow \rho(x))</math>, while
:<math>\forall x ((\exists y \phi(y)) \lor ((\exists z \psi(z) ) \rightarrow \rho(x)))</math>
is logically equivalent but not in prenex normal form.