Formelspiel
Einfache Sprache
Das Formelspiel ist das zur Prädikatenlogische Formel in Pränexe Normalform äquivalente Spiele.
Def. Formelspiel
Sei $\phi = \exists x_1\forall x_2\exists x_3\ldots\mathsf Qx_k[\psi]$ eine Prädikatenlogische Formel in Pränexe Normalform, wobei $\mathsf Q$ entweder $\forall$ oder $\exists$ darstellt. Das Formelspiel funktioniert wie folgt: Es gibt zwei Spieler, A und E. Sie wählen abwechselnd Werte für die Variablen $x_1,\ldots,x_2$. Spieler A wählt Werte für Variablen die mit $\forall$ quantifiziert sind. Spieler E wählt Werte für die Variablen die mit $\exists$ quantifiziert sind. Die Reihenfolge des Spiel ist wie die Reihenfolge der Variablen in $\phi$. Am Ende des Spiels nutzen wir die Werte die von den Spielern gewählt wurden um den Wahrheitswert von $\psi$ zu bestimmen. Falls $\psi$ wahr ist, hat E gewonnen, sonst A.
Daraus ergibt sich folgendes Problem