prenex form

A formula in first order logic is said to be in prenex form if all quantifiers occur in the front of the formula, before any occurrences of predicates and connectives. Schematically, a proposition in prenex form will appear as follows

 $(Q_{1}x_{1})(Q_{1}x_{1})\ldots\langle\hbox{matrix}\rangle$

where each “$Q$” stands for either “$\forall$” or “$\exists$” and “$\langle\hbox{matrix}\rangle$” is constructed from predicates and connectives. For example, the proposition

 $(\forall x)(\exists y)(\forall z)\,(x>z\rightarrow y>z)$

is in prenex form whilst the statement

 $(\forall x)\,(x>0\rightarrow(\exists y)(x=y^{2}))$

is not in prenex form, but is equivalent to the statement

 $(\forall x)(\exists y)\,(x>0\rightarrow x=y^{2})$

which is in prenex form.

This requirement that the statement be expressed in prenex form puts no real restriction on the statements which we may consider because it is possible to systematically express any statement in prenex form by a systematic use of the several equivalences:

Title prenex form PrenexForm 2013-03-22 15:06:55 2013-03-22 15:06:55 rspuzio (6075) rspuzio (6075) 7 rspuzio (6075) Definition msc 03B10 msc 03C07