Herzlich willkommen!

Wir setzen jetzt fort ein Thema, das wir uns im Bereich der Aussagenlogik bereits angesehen haben, und zwar das der Normalformen.

Wir erweitern jetzt also dieses Normalformenprinzip auf spezifische Features der First-Order-Logik.

Wir fangen an.

Hätte ich letztes Mal schon gesagt, dass wir die NNF erweitern können?

Wahrscheinlich nicht, ne? Also, ist aber ganz leicht.

Wenn ich so etwas hier habe, was ich nicht haben will in einer NNF, eine Negation oberhalb eines Operators, also jetzt oberhalb eines neuen Operators,

nehme ich hier eines Quantors, ist klar, was ich damit mache.

Ich schaufel das Ding unter den Quantor und der Quantor selber kippt dabei in einen Existenzquantor um.

Und genauso funktioniert das natürlich umgekehrt, wenn ich also hier eine Negation oberhalb eines Existenzquantors habe,

dann wird da hier bei der Normalformenbildung ein Altquantor draus.

Das bedingt natürlich, dass ich genauso wie ich im aussagenlogischen Falle für die Konstruktion der Normalformen dann annehmen musste,

dass Disjunktion tatsächlich nur Operation und nicht irgendeine Abkürzung ist, genauso muss ich hier also den Existenzquantor

als First Class Citizen in die Grammatik mit aufnehmen, damit nicht das hier klammheimlich doch noch wieder zwei Negationen enthält,

die an der falschen Stelle sitzen.

Gut, das ist weiterhin klar, dass das funktioniert.

Ja gut, zu klar, ja, Sie hatten sich beklagt, dass die NNF-Aufgabe in den Übungen, dass die relativ schwer gestellt war.

Das stimmt auch, ich habe es Ihnen noch mal angesehen, das liegt daran, dass da ein Unfall passiert war.

Und zwar hieß es ursprünglich mal, dass zu den Fehlständen auch so etwas hier gehört, Negation oberhalb von Negation.

Und das hat aber ein Problem, wenn man das Gesetz, das sich hier anguckt, zum Beispiel, indem ich eine Negation über eine Konjunktion rüberschiebe,

ja, das ist ja dann dieses hier, das ist die Operation, die wir da anwenden, wenn wir uns jetzt vorstellen, dass das in einem Kontext passiert,

also irgendwo tief in einer Formel, die womöglich weiter oben noch eine Negation enthält, dann haben wir, wenn wir das als Fehlstand zählen,

hier plötzlich aus einem Fehlstand diese Negation gegen die weiter oben, hier zwei Fehlstände gemacht, diese beiden Negationen gegen die weiter oben.

So, dadurch wird das Ganze kompliziert. Man kann sich schlauere Terminationsmaße noch da ausdenken, mit dem man das auch wieder repariert kriegt, aber nun gut.

Man muss also mit diesem Problem hier umgehen und daher die Komplikation in dieser Aufgabenstellung.

Wir sehen gleich noch ein Beispiel, deswegen sage ich das jetzt, wo das mit den Fehlständen aber wirklich klappt, weil sich eben wirklich rein gar nichts verdoppelt.

Das ist bei einer anderen Normalform.

So, gut, also damit haben wir jetzt die Negations-Normalform ausgedehnt auf prädikatenlogische Formeln.

So.

Und wir wollen jetzt mit dem Sortieren der Operatoren weitermachen. Wir hatten ja also Negations-Normalform und CNF, bedeuten ja letztlich,

ich sortiere also die Negationen alle nach unten, die Disjunktion in die Mitte und die Konjunktion nach oben.

So, jetzt haben wir noch die Quantoren da rumfliegen. Gut, wir haben es schon geschafft, die Negationen durch die Quantoren nach unten zu drücken.

Was wir jetzt mit den Quantoren machen wollen, ist, die alle nach oben schieben. So, ich definiere also formal, was wir dann an Formel haben wollen.

Also ich kürze jetzt weiter wie effektiv schon bisher Normalform mit NF ab und ich sage jetzt, was ist eine Pränexe Normalform?

Pränexe heißt, dass es also irgendwie vorne mit etwas verbunden ist, glaube ich, wenn mich jetzt mein Latein da noch richtig führt.

So, und ich gebe jetzt einmal schematisch an, was eine Pränexe Normalform für eine Art Formel ist. Und zwar besteht die aus vorne einem sogenannten Quantorenpräfix,

also es fängt an mit einem Quantor, zum Beispiel Q1X1. Dabei nehme ich jetzt also dieses Q als Platzhalter für irgendeinen Quantor, das heißt also,

jedes QI, das jetzt kommt, wird also entweder ein Allquantor oder ein Existenzquantor sein.

So, von diesen Quantoren habe ich vor der Wechst so eine Serie, ein Stück über verschiedene Variablen. Will ich das wirklich sagen, dass die verschieden sind?

Nein, ich will nicht sagen, dass die verschieden sind. Also tue ich es nicht, wenn ich nicht sagen, dass die verschieden sind, sind sie nicht verschieden.

So, also diese Quantoren, wie gesagt, sind also entweder Allquantor oder Existenzquantor. N ist größer als Null, das heißt also, kann auch sein, dass da kein Quantor steht.

Dann kommt hier so eine Restformel phi und von phi verlange ich, dass es quantorenfrei ist, also sprich keine Quantoren enthält.

Also mit anderen Worten, alle Quantoren der Formel kommen einmal ganz oben im Parksbau.

Ja, also vollständig meine ich das hier. Q1 bis Qn sind Elemente dieser Menge, können gleich sein oder verschieden.

Also gut, ich habe ja nur zwei zur Verfügung, also es werden meistens welche gleich sein müssen, ja, ich meine, sonst, es sind höchstens zwei Quantoren vorneweg.

Ja, die können sich irgendwie abwechseln. In der Tat ist das also ein wichtiges Maß der Komplexität von Formeln.

Nicht etwa wie viele Quantoren hier vorne stehen, sondern wie oft sich da Existenz- und Allquantoren abwechseln.

Das nennt sich die Alternierungstiefe der Formel. Und eine Formel ist also objektiv umso komplizierter, je größer ihre Alternierungstiefe ist.

Und da gibt es eine weit verzweichte formale Theorie. Diese Klassen haben auch alle Namen, die ich mit diesen Quantorenabwechslungen bilden kann.

Also die heißen dann Sigma oder Pi mit irgendwelchen Indizes. Der Index sagt mir, wie hoch halt die Alternierungstiefe ist.