Pränexe Normalform

Einfache Sprache

Def. Pränexe Normalform

Die Menge der prädikatenlogische Formeln in pränexer Normalform ($\mathbf{PNF}$) ist induktiv definiert durch

Basiselemente: Jede quantorenfreie prädikatenlogische Formel ist in $\mathbf{PNF}$.

Konstruktionsregel: Für jede Formel $\varphi\in \mathbf{PNF}$ ist auch $\exists x_i\varphi$ und $\forall x_i\varphi$ für alle $i\in\mathbb N$ in $\mathbf{PNF}$.

Bemerke: Der quantorenfreie Teil einer Formel in $\mathbf{PNF}$ wird Matrix genannt und die Quantoren werden als Quantorenblock zusammengefasst.

Eine Prädikatenlogische Formel kann durch Satz prädikatenlogische Formel äquivalent zu PNF in eine Formel in $\mathbf{PNF}$ überführt werden.