Prenex-normaalvorm

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

Een wiskundige formule uit de predicatencalculus is in de prenex-normaalvorm als ze geschreven is als een reeks kwantoren, gevolgd door een kwantorloos deel, de matrix genaamd.

Elke formule in de klassieke logica komt overeen met een formule in prenex-normaalvorm. Bijvoorbeeld, als φ(y), ψ(z), en ρ(x) kwantorloze formules zijn met vrije variabelen, dan is

\forall x \exists y \exists z (\phi \lor (\psi \rightarrow \rho))

in prenex-normaalvorm met matrix \phi \lor (\psi \rightarrow \rho), terwijl

\forall x ((\exists y \phi) \lor ((\forall z\psi ) \rightarrow \rho))

hiermee logisch equivalent is, maar niet in prenex-normaalvorm.