Prenex-normaalvorm

Een wiskundige formule uit de predicatenlogica is in de prenex-normaalvorm als ze geschreven is als een reeks kwantoren, gevolgd door een deel zonder kwantoren, de matrix genoemd. Deze normaalvorm schrijft dus voor hoe de kwantoren moeten worden geplaatst.

Iedere formule in de klassieke logica is logisch equivalent met een formule in prenex-normaalvorm. Bijvoorbeeld, als $\phi (y),\ \psi (z)$ en $\rho (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.

Conversie

Het is mogelijk een willekeurige formule $H$ naar een logisch equivalente formule in prenex-normaalvorm om te schrijven. Daarvoor moeten we er eerst voor zorgen dat elke variabele in $H$ slechts één keer voorkomt, en dat er geen variabelen zijn die zowel gebonden als vrij in $H$ voorkomen. Dit kunnen we altijd doen door gebonden variabelen te hernoemen. Daarna kunnen we stapsgewijs $H$ naar prenex-normaalvorm converteren door steeds subformules waarin een kwantor in een argument van een andere bewerking voorkomt volgens de volgende tabel om te schrijven:

Formule	Prenex-normaalvorm
$\lnot \forall xF$	$\exists x\lnot F$
$(\forall xF)\land G$	$\forall x(F\land G)$
$(\forall xF)\lor G$	$\forall x(F\lor G)$
$(\forall xF)\rightarrow G$	$\exists x(F\rightarrow G)$
$G\land (\forall xF)$	$\forall x(G\land F)$
$G\lor (\forall xF)$	$\forall x(G\lor F)$
$G\rightarrow (\forall xF)$	$\forall x(G\rightarrow F)$
$\lnot \exists xF$	$\forall x\lnot F$
$(\exists xF)\land G$	$\exists x(F\land G)$
$(\exists xF)\lor G$	$\exists x(F\lor G)$
$(\exists xF)\rightarrow G$	$\forall x(F\rightarrow G)$
$G\land (\exists xF)$	$\exists x(G\land F)$
$G\lor (\exists xF)$	$\exists x(G\lor F)$
$G\rightarrow (\exists xF)$	$\exists x(G\rightarrow F)$

Voorbeeld

Gegeven de formule $H=\exists xP(x)\land \forall x{\bigl (}\exists yR(x,y)\to Q(x){\bigr )}$. We kunnen deze formule as volgt in prenex-normaalvorm omschrijven:

1. Herbenoemen van variabelen: $\exists zP(z)\land \forall x{\bigl (}\exists yR(x,y)\to Q(x){\bigr )}$
2. $\exists zP(z)\land \forall x\forall y{\bigl (}R(x,y)\to Q(x){\bigr )}$
3. $\exists z\forall x\forall y{\bigl (}P(z)\land {\bigl (}R(x,y)\to Q(x){\bigr )}{\bigr )}$