Wir haben heute zwei Themen zu fassen. Das erste sind Normalformen in Aussagenlogik.

Das verwenden wir dann gleich im zweiten Teil, wo wir das erste Mal einen vernünftigen

Algorithmus kennenlernen werden, um zu entscheiden, ob eine aussagenlogische Formel erfüllbar ist

oder nicht. Wir kennen schon einen, nicht den Wahrheitstafel Algorithmus. Wir probieren

halt einfach gnadenlos alle möglichen Kombinationen von Wahrheitswerten aus und wenn eine dabei ist,

die die Formel wahr macht, werden wir sie schon finden. Gut, das ist nicht effizient, klar,

aber man weiß ja auch, dass es vermutlich nicht durchgängig effizient geht, aber besser als

alles durchprobieren geht es eben schon. Wir werden also kennenlernen den sogenannten

Resolutionsalgorithmus. Der spielt für Aussagenlogik in der Praxis eigentlich keine ganz so zentrale

Rolle, insbesondere die kompetentiven Satzsäurer. Das sind alles keine Resolutionssäurer, sondern

die machen andere Dinge, allerdings wird zum Teil relativ eng verwandt. Aber Resolution bleibt eben

wichtig nachher insbesondere für Logikerster Stufe und in der Tat, wenn Sie sich dann die

erfolgreichen First-Order-Reasoner angucken, das sind zum großen Teil Resolutionssäurer.

Gut, wir beginnen also mit Normalform. Normalform heißt, wir fangen mal an in unseren Formeln so ein

bisschen die Konnektive zurecht zu sortieren. Im Moment kann ja eine Formel, wie sie will,

durcheinander, Konjunktion, Disjunktion, Negation, alles Mögliche anwenden und mit

dieser Anarchie soll jetzt mal Schluss sein. Wir klappen uns also jetzt die Konnektive

ein nach dem anderen vor oder eins nach dem anderen und beginnen mit der Negation. Also wir wollen die

Verwendung von Negation dahingehend normalisieren, dass Negation nur noch ganz unten verwendet werden

darf. Also nicht ganz oben in einer Formel drin, also ich kann nicht eine komplizierte Formel schreiben

und dann nicht davor setzen, sondern ich will, dass die Negation nur irgendwie so maßen ganz unten im

Parksbaum auftaucht, also sprich direkt vor den Atomen. Wenn ich das will, dann verwende ich natürlich

so so dem Morgensche Gesetz. Ja, also zum Beispiel so was hier soll ja verboten sein, nicht Fi und

Ci, das ist was, was ich nicht mehr haben will, also nicht vorne und oder oben eben und Konjunktion

drunter will ich nicht mehr, naja ich weiß natürlich wie das geht. Das ist ja logisch

äquivalent zu nicht Fi oder nicht Ci und damit haben wir also die Negation einen nach unten

gedrückt, wunderbar, wunderbar, so lange bis wir uns erinnern, dass dieses oder her ja nichts ist

als eine Abkürzung für wieder einen Haufen uns und nichts, naja einen und und einen Haufen nichts. Wir haben

also, wenn wir die Expansion jetzt hier wieder, also wenn wir diese Abkürzung wieder expandieren,

dann haben wir nichts erreicht, nicht was ist das, das ist also nicht, so, nicht, da haben wir also nur

die Formel ein bisschen komplizierter gemacht letztlich, indem wir hier Doppelnegation einführen,

nicht das hier ist die Expansion von diesem hier, wenn ich also das oder auflöse, gut und also bis

auf diese Doppelnegation an dem Fi haben wir in Wirklichkeit nichts geändert. So, das heißt also,

wenn wir damit was werden wollen, dann muss dieses Tier hier in Zukunft ein First Class Citizen sein,

ja, das heißt also, wo wir uns bisher der Einfachheit halber auf den Standpunkt gestellt

haben, es gibt überhaupt nur Negation und Konjunktion, müssen wir jetzt für Zwecke der

Normalformen, der Dysjunktion zumindest wieder ein Eigenleben zustehen, zu gestehen der, der

Implikation nicht, aber der Dysjunktion. So, wir definieren, was eine Negations-Normalform ist,

über eine Grammatik, das geht in diesem Falle sehr zwanglos, man kann es jetzt fast raten,

ja, also ich habe gesagt, okay, die Grammatik muss wieder Dysjunktion enthalten und Negation

darf jetzt nur noch ganz unten vorkommen, sprich, naja, gut, können wir uns aussuchen, ob wir nicht

falsch noch haben wollen, ob wir das lieber durch wahr ersetzen, wir entscheiden uns das nochmal

durch wahr zu ersetzen, das heißt, die Grammatik sieht folgendermaßen aus, wir fangen an mit wahr

und falsch, so, naja, also wir wollen einfach überhaupt kein Symbol mehr negieren außer den

Atomen, also auch falsch dürfen wir nicht negieren, sondern nicht falsch, da haben wir eben hier extra

ein Symbol wahr für und umgekehrt, so, dann, gut, Atome dürfen wir negieren, also A und nicht A,

das Ganze für A aus unserer festen Menge propositionaler Atome, naja, und dann kommen

noch zwei Klauseln, einmal Konjunktion behalten wir natürlich und Dysjunktion brauchen wir jetzt

auch, so, das ist also jetzt die Grammatik, die definiert, was also eine Negations-Normalform

ist, noch einmal für die absolute Klarheit, so, hier haben wir eine Formel, die ist in