Lesson plan

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.

Back to article

Article summary

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.

Key claims

No claims recorded.

Discussion questions

  1. Summarise the article in your own words. Which single claim would you verify first, and why?
  2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
  3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.

Key claims and bibliography are generated from the same tracked claims and sources as the article page.