Syntax

Die Menge der quantifizierten booleschen Formeln kann wie folgt induktiv definiert werden:

• Jede Aussagenvariable ${\displaystyle x}$ ist eine quantifizierte boolesche Formel. ${\displaystyle x}$ tritt in der Formel ${\displaystyle x}$ frei auf.
• Sind ${\displaystyle \varphi }$ und ${\displaystyle \psi }$ quantifizierte boolesche Formeln, so auch ${\displaystyle \neg \varphi ,(\varphi \wedge \psi )}$ und ${\displaystyle (\varphi \vee \psi )}$. Eine Aussagenvariable ${\displaystyle x}$ aus ${\displaystyle \varphi }$ oder ${\displaystyle \psi }$ ist frei in den Formeln, falls ${\displaystyle x}$ in ${\displaystyle \varphi }$ oder ${\displaystyle \psi }$ frei ist.
• Ist ${\displaystyle \varphi }$ eine quantifizierte boolesche Formel und ${\displaystyle x}$ eine Aussagenvariable, so sind auch ${\displaystyle \forall x\varphi }$ und ${\displaystyle \exists x\varphi }$ quantifizierte boolesche Formeln. Der Gültigkeitsbereich von ${\displaystyle \forall x}$ beziehungsweise ${\displaystyle \exists x}$ erstreckt sich auf jedes freies Vorkommen von ${\displaystyle x}$ in ${\displaystyle \varphi }$. Jede andere nicht gebundene Aussagenvariable ist frei in ${\displaystyle \forall x\varphi }$ und ${\displaystyle \exists x\varphi }$.

Semantik

Die Semantik quantifizierter boolescher Formeln orientiert sich eng an der Semantik der Prädikatenlogik: Der Wert einer quantifizierten booleschen Formel der Form ${\displaystyle \forall x\varphi }$ wird bestimmt, indem ${\displaystyle \varphi }$ durch ${\displaystyle \varphi _{x=0}\wedge \varphi _{x=1}}$ ersetzt wird, wobei ${\displaystyle \varphi _{x=0}}$ und ${\displaystyle \varphi _{x=1}}$ dadurch entstehen, dass jedes Auftreten von ${\displaystyle x}$ durch 0 beziehungsweise 1 ersetzt wird. Analog dazu wird jedes Aufkommen von ${\displaystyle \exists x\varphi }$ durch ${\displaystyle \varphi _{x=0}\vee \varphi _{x=1}}$ ersetzt.

Eine Formel, die keine freie Variablen enthält, ist damit entweder wahr oder falsch.

Pränexe Normalform

Eine quantifizierte boolesche Formel ist in pränexer Normalform, falls sie von der Form ${\displaystyle Q_{1}x_{1}Q_{2}x_{2}\ldots Q_{n}x_{n}\varphi }$ ist, wobei ${\displaystyle Q_{1},\ldots ,Q_{n}\in \{\forall ,\exists \}}$ und ${\displaystyle x_{1},\ldots ,x_{n}}$ Variablen einer aussagenlogischen Formel ${\displaystyle \varphi }$ ohne Quantoren sind. Der Ausdruck ${\displaystyle Q_{1}x_{1}\ldots Q_{n}x_{n}}$ heißt Quantorenblock.

Da für jede quantifizierte boolesche Formel eine äquivalente Formel in pränexer Normalform existiert und diese in Polynomialzeit konstruiert werden kann, wird häufig in Beweisen von dieser Form ausgegangen.

Quantorenwechsel und Polynomialzeithierarchie

Aus der Struktur des Quantorenblocks einer quantifizierten booleschen Formel in Präfix-Normalform lassen sich Rückschlüsse auf komplexitätstheoretische Eigenschaften ziehen. Die Klassen der wahren quantifizierten booleschen Formeln in Präfix-Normalform sind je nach Anzahl der Alternationen von All- und Existenzquantoren und deren Reihenfolge vollständig für eine Stufe der Polynomialzeithierarchie. Im Folgenden ist für einen Quantor ${\displaystyle Q\in \{\forall ,\exists \}}$ ${\displaystyle QX_{i}}$ die Schreibweise für ${\displaystyle Qx_{i1},Qx_{i2},...,Qx_{ik}}$ für eine beliebige Zahl ${\displaystyle k}$.

Ist ${\displaystyle \Sigma _{k}}$ die Klasse aller wahren quantifizierten booleschen Formeln ohne freie Variablen der Form

${\displaystyle \exists X_{1}\forall X_{2}\exists X_{3},\ldots ,Q_{k}X_{k}}$ mit ${\displaystyle Q_{k}=\forall }$, falls ${\displaystyle k}$ gerade ist und andernfalls ${\displaystyle Q_{k}=\exists }$

und ${\displaystyle \Pi _{k}}$ die Klasse aller wahren quantifizierten booleschen Formeln ohne freie Variablen der Form

${\displaystyle \forall X_{1}\exists X_{2}\forall X_{3},\ldots ,Q_{k}X_{k}}$ mit ${\displaystyle Q_{k}=\exists }$, falls ${\displaystyle k}$ gerade ist und andernfalls ${\displaystyle Q_{k}=\forall }$,

so gilt für alle ${\displaystyle k\geq 0}$:

• ${\displaystyle \Sigma _{k}}$ ist ${\displaystyle \Sigma _{k}^{\rm {P}}}$-vollständig und
• ${\displaystyle \Pi _{k}}$ ist ${\displaystyle \Pi _{k}^{\rm {P}}}$-vollständig.