Prenex normal form
A formula of the predicate calculus is in prenex normal form (PNF) if it is written as a string of quantifiers and bound variables, called the prefix, followed by a quantifier-free part, called the matrix.
≈ 4 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
A formula of the predicate calculus is in prenex normal form (PNF) if it is written as a string of quantifiers and bound variables, called the prefix, followed by a quantifier-free part, called the matrix. Together with the normal forms in 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 \phi(y) , \psi(z) , and \rho(x) are quantifier-free formulas with the free variables shown then : \forall x \exists y \forall z (\phi(y) \lor (\psi(z) \rightarrow \rho(x))) is in prenex normal form with matrix \phi(y) \lor (\psi(z) \rightarrow \rho(x)) , while : \forall x ((\exists y \phi(y)) \lor ((\exists z \psi(z) ) \rightarrow \rho(x))) is logically equivalent but not in prenex normal form.
A formula of the predicate calculus is in prenex normal form (PNF) if it is written as a string of quantifiers and bound variables, called the prefix, followed by a quantifier-free part, called the matrix. Together with the normal forms in 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 \phi(y) , \psi(z) , and \rho(x) are quantifier-free formulas with the free variables shown then \forall x \exists y \forall z (\phi(y) \lor (\psi(z) \rightarrow \rho(x))) is in prenex normal form with matrix \phi(y) \lor (\psi(z) \rightarrow \rho(x)) , while \forall x ((\exists y \phi(y)) \lor ((\exists z \psi(z) ) \rightarrow \rho(x))) is logically equivalent but not in prenex normal form.
(\exists x (x^2 = 1)) \land (0 = y) is equivalent to \exists x ( x^2 = 1 \land 0 = y) , but (\exists x (x^2 = 1)) \land (0 = x) is not equivalent to \exists x ( x^2 = 1 \land 0 = x) because the formula on the left is true in any ring when the free variable x is equal to 0, while the formula on the right has no free variables and is false in any nontrivial ring. So (\exists x (x^2 = 1)) \land (0 = x) will be first rewritten as (\exists x' (x'^2 = 1)) \land (0 = x) and then put in prenex normal form \exists x' ( x'^2 = 1 \land 0 = x) . The former statement says that if x is less than any natural number, then x is less than zero.
The latter statement says that there exists some natural number n such that if x is less than n, then x is less than zero. Both statements are true. The former statement is true because if x is less than any natural number, it must be less than the smallest natural number (zero).
The latter statement is true because n=0 makes the implication a tautology. Note that the placement of brackets implies the scope of the quantification, which is very important for the meaning of the formula.
Consider the following two statements: \forall n\in \mathbb{N} [(x and its logically equivalent statement [\exists n\in \mathbb{N} (x The former statement says that for any natural number n, if x is less than n then x is less than zero. The latter statement says that if there exists some natural number n such that x is less than n, then x is less than zero. Both statements are false.
The former statement doesn't hold for n=2, because x=1 is less than n, but not less than zero. The latter statement doesn't hold for x=1, because the natural number n=2 satisfies x<n, but x=1 is not less than zero.
See also
Arithmetical hierarchy Herbrandization Skolemization
Text derived from https://en.wikipedia.org/w/index.php?oldid=1325155371 under CC BY-SA 4.0; modifications have been made.