Bei der Aussagenlogik waren wir letztes Mal stehen geblieben bei der
Semantik aussagenlogischer Formeln.
Wir hatten also definiert, wie man Formeln zusammensetzt, wie man
syntaktisch korrekte Formeln zusammensetzt aus diesen Operatoren, die
wir da definiert hatten.
Wir hatten sie Konnektive genannt.
Wir hatten denen auch schon Namen gegeben, die denen so ein bisschen
die semantische Bedeutung auch schon zuordnen.
Wir hatten diesen konnektiven Funktionen zugewiesen, dass wir also,
wenn wir zwei Werte in so einen Konnektiv reingeben, dass wir da eine
Funktion, eine Abbildung definiert haben, was dieses Konnektiv macht.
Wir hatten uns das ein bisschen angeschaut anhand von einfacher
Wahrheitstafeln, einfachen Wahrheitstafeln.
Jetzt müssen wir den wieder den Schritt zurück machen von diesen
formal Abbildungen, die wir definiert hatten, hin zur eigentlichen
Auswertung der Formel.
Das heißt, wir müssen jetzt noch definieren, wie wir eine Formel, so
etwas syntaktisch Hingeschriebenes aus Variablen und Konnektiven, die
geklammert sind, wie wir da jetzt diese auswerten können für eine
bestimmte Belegung der Variablen.
Und dafür hatten wir uns definiert eine Interpretation.
Und wir hatten gesagt, eine Interpretation selber ist erst mal wieder
eine Abbildung, die aus dem Vokabular der Variablen abbildet, auf die
Werte wahr oder falsch.
Also wenn ich diese drei Variablen hätte, in meiner Menge der
Variablen P1, P2, P3, wäre jede Zeile eine mögliche Interpretation.
Und wenn wir jetzt mit B hoch V notieren, die Menge aller möglichen
Interpretationen, das heißt die Menge aller möglichen Abbildungen von
dem Alphabet der aussagenlogischen Variablen auf die Werte wahr oder
falsch.
Dann könnte man das so als Tabelle hinschreiben.
Da stehen alle möglichen Belegungen, alle möglichen Abbildungen drin.
Jetzt kam nach der letzten Vorlesung ein Student und fragte, gibt es
irgendeine feste Vorschrift, wie man das hinschreibt, in welcher
Reihenfolge?
Nein, gibt es nicht.
Warum nicht?
Naja, wir haben eine Abbildung, die bildet oder wir haben sogar eine
Menge aller Interpretationen.
Das heißt also eine Menge aller Abbildungen und Mengen sind nicht in
irgendeiner Folge geordnet, in irgendeiner Weise geordnet.
Es gibt keine Reihenfolge der Mengenvariablen.
Natürlich ist es trotzdem sinnvoll, sich etwas zu überlegen, wie man
das systematisch hinschreibt, damit man nicht irgendwas vergisst,
damit man einen leichten Überblick behält.
Hier sieht man sofort, ist die relativ einfache Vorgehensweise
gewesen.
Man hat erst mal alle hingeschrieben, die in P1 falsch haben können.
Danach kommt alle, die in P1 wahrhaben können.
Und allen denen, die P1 falsch haben können, kommen danach erst mal
alle die, die bei P2 falsch haben können und dann zum Schluss die, die
beim P3 falsch haben können.
Und dann geht man wieder zurück und schreibt alle die hin, die dann
bei P3 wahrhaben können, dann alle die, die bei P2 wahrhaben können
und dann alle die, die bei P1 wahrhaben können.
Aber es ist nicht zwingend vorgeschrieben.
Es ist eine Menge aller Interpretationen.
Die Elemente der Menge sind nicht geordnet.
Wenn wir jetzt also eine Formel auswerten wollen, dann nehmen wir uns
wieder eine Interpretation her und definieren uns jetzt eine
Abbildung, die heißt Value of I, der Wert der Interpretation I.
Und diese Definition ist in einer gewissen Art und Weise wieder, naja,
induktiv nicht direkt, aber sie ist so, dass man beliebig komplex
aufgebaute Formeln durch wiederholte Anwendung dieser Funktion VAL
auswerten kann.
Dazu definieren wir erst mal ganz primitiv.
Habe ich irgendeine Variable X aus dem Alphabet aller
aussageslogischen Variablen, dann sei gerade VAL I von X die I von X.
Können wir machen, weil die Interpretation I bildet ja ab von den
Variablen auf die Werte wahr oder falsch.
Das heißt insbesondere bildet die Interpretation auch jede Variable
aus dem Alphabet X auf einen Wert wahr oder falsch ab.
Das heißt, auf die Art und Weise kann ich, wenn ich nur eine einzelne
Variable habe, ganz klar sagen, was ist der Wert der Interpretation
dieser Variable, wird mir durch die Interpretation direkt vorgegeben.
Wenn ich jetzt komplexere Sachen habe, sei G irgendeine beliebige
Formel, dann definiere ich mir, dass der Wert von nicht G sei eben
gerade der Wert der Funktion nicht, B nicht, von dem Wert von der
Formel G.
Und jetzt hängt es davon ab.
Entweder kann ich den Wert von Formel G direkt ausrechnen, zum
Beispiel eine Variable, oder der setzt sich aus irgendwas anderem
zusammen.
Dann brauche ich halt entsprechend die anderen Definitionen.
Der Wert von G und H ist eben gerade der Funktionswert von dieser
Abbildung und die wir uns definiert haben von Wert von G und Wert von
H.
Das gleiche für oder, das gleiche entsprechend für den Folgoperator.
Das heißt, was man da formell macht, ist, dass man einfach den Wert zu
einer zusammengesetzten Formel reinzieht in die Parameter der vorher
definierten Abbildung für die einzelnen Konnektive und dann den Wert
der einzelnen Bestandteile der durch dieses Konnektiv zusammengefügten
Formel in die Funktion, die für die Auswertung reintut und vorher halt
diese Wahlfunktion anwendet.
Und dann kann ich durch wiederholte Anwendung jede beliebige
aussagenlogische Formel, die ich mir durch die vorgegebene Syntax
aufbauen kann, entsprechend auswerten und für jede gegeben eine
Interpretation kann ich für jede aussagenlogische Formel dann
berechnen, mit dieser Interpretation ist diese Formel wahr oder
falsch.
Also einfaches Beispiel.
Hätten wir eine Interpretation, so dass die Variable p mit wahr belegt
wird und die Variable q mit falsch und wir hätten die Formel nicht p
und q.
Dann muss man eben einfach schrittweise diese Wahl anwenden.
Also der Wert von nicht p und q ist gleich b von nicht des Wertes von
p und q.
Wert von p und q ist gerade der Funktionswert von und von wal p und
wal q.
Gut, wal p und wal q ist laut Definition gerade die Interpretation von
p und q, also die Belegung der Variablen p und q mit wahr und falsch.
Also ist das diese b-Funktion von nicht von der b-Funktion von und von
wahr und falsch.
b-Funktion von und von wahr und falsch ist gerade falsch und b nicht
von falsch ist wahr, so dass sich also der Wert der Formel bei der
Interpretation p gleich wahr und q gleich falsch zu wahr berechnet.
Wie ich schon sagte, oft kann man das auch in Tabellenform machen,
dass man einfach sich die Sachen sukzessive zusammensetzt.
Also ich schreibe hin die Interpretation, die Belegung und dann
schreibe ich hin die einzelnen
die einzelnen Werte, die einzelnen Walze, einzelne Komponenten und
setze mir das dann stückweise wieder zusammen zu komplexeren Formeln,
die ich mit den gegebenen Konnektiven zusammensetzen kann.
Jetzt heißt es hier, man soll die drittletzte und die letzte Spalte
vergleichen.
Man könnte auch sagen, man vergleicht die erste und die letzte Spalte
und wird dann feststellen, dass die immer entsprechend das Negative
voneinander sind.
Also die letzte Spalte und die letzte Spalte.
Erst mal gucken, hier kann ich das nicht.
Also die Spalte nicht p oder nicht q, sondern vergleichen mit nicht
von p und q.
Man stellt halt fest, dass diese Spalten zum Beispiel immer gleich
sind.
Das heißt, nicht p oder nicht q wird immer für jede Interpretation zum
gleichen Wert ausgewertet wie nicht p und q.
Das heißt, da scheint es irgendwie so eine Rechenregel zu geben, die
mir sagt, dass ich so ein Nicht-Zeichen, wenn ich das in p und q
reinziehe, das nicht dann also nicht vor den gesamten Ausdruck setze,
sondern vor die einzelnen Variablen innerhalb dieses Ausdrucks oder
auch Formeln innerhalb dieses Ausdrucks, kann es auch sein, dann muss
ich aus dem und ein oder machen.
Es scheint irgendwie so eine Rechenregel zu geben, die das möglich
macht.
Und wenn man dann also sieht, dass es durchaus Formeln gibt, die für
alle Interpretationen, die ich reingebe, immer den gleichen Wert
evaluieren, die sich immer zum gleichen Wert ausrechnen, dann komme
ich eben zu dem Begriff der Äquivalenz von aussagenlogischen Formeln.
Wenn also für jede Interpretation gilt, dass der Wert der Formel g
gleich dem Wert der Formel h ist, dann sage ich, dass g und h
äquivalent sind.
Also hier drittletzte Spalte, letzte Spalte, nicht p oder nicht q ist
äquivalent zu nicht p und q.
Schreibe ich mit so einem Dreierstrich, einem verstärkten
Gleichheitszeichen.
Und wenn man guckt, findet man sehr viele Formeln, die miteinander
äquivalent sind, also nicht p oder nicht q ist äquivalent zu nicht p
und q.
Aber genauso kann man sich relativ leicht eine Tabelle aufschreiben,
die sagt nicht, nicht p ist äquivalent zu p.
Oder interessanterweise, wenn ich sage aus p folgt q, dann ist das das
Gleiche wie nicht p oder q.
Das ist dann etwas, das sieht man dann schon nicht mehr so oft im
ersten Blick.
Bei den ersten beiden Formeln kann man sich das noch ein bisschen
leicht überlegen.
Das bei einem nicht aus einem unten oder wird, hat vielleicht jeder
schon mal gehört.
Bei der folgt wird es dann schon ein bisschen komplizierter.
Also aus p folgt q.
Wenn ich jetzt nicht p oder q habe und die Rechenregel ansetze, wie da
oben, dass ich dieses nicht reinziehen kann oder rausziehen kann, dann
weiß ich, das Gegenteil von nicht p oder q ist p und nicht q.
Also aus p folgt q ist genau das Gegenteil von p und nicht q.
Also muss p aus p folgt q äquivalent sein zu nicht p und nicht q, weil
es halt das Gegenteil ist, macht ja das nicht.
Da kann ich wieder das nicht reinziehen, komme ich hin, das ist
äquivalent zu nicht p oder nicht nicht q.
Und dann weiß ich nicht nicht q, habe ich oben im Beispiel schon
gesehen, ist gleich q, äquivalent zu q.
Also ist das Ganze äquivalent zu nicht p oder q.
Das heißt, was man hier machen kann, ist durch so eine Folge von
Äquivalenzumformungen kann man bestimmte Äquivalenzen von Formeln
nachweisen, indem man auf vorher schon bestätigte Äquivalenzen
zurückgreift.
Man kann also durch solche Äquivalenzumformungen entweder neue
Äquivalenzen herleiten oder zeigen, wenn man eine Vermutung hat, dass
es irgendeine Äquivalenz zwischen zwei Formeln gibt, kann ich zeigen,
dass die Äquivalenz sind, indem ich so eine Herleitung durchführe.
Bei der Art und Weise, wie wir jetzt diese Auswertung von Formeln
definiert haben, haben wir noch eine kleine Unschönheit, über die wir
so nonchalant hinausgegangen sind.
Diese Auswertung g ist definiert für jedes i und jedes g. Das heißt,
wir bilden ab aus der Menge aller möglichen Abbildungen, aller
möglichen Interpretationen, sprich aller möglichen Abbildungen von v
nach b, bilden wir eine Interpretation ab auf den Wert der
Interpretation von einer beliebigen Formel g. Und wir hatten schon
gesagt, sowas wie p0 und p0, das ist eine andere Formel als p2 und p2.
Diese beiden Formeln sind verschieden, hatten wir bei der Definition
so festgelegt.
Es ist wichtig, wie die Variablen konkret benannt sind.
Und daraus folgt, wenn die beiden unterschiedlich sind, zwei
unterschiedliche Formeln sein sollen, dass p0 und p0 und p2 und p2
nicht miteinander äquivalent sind.
Weil ich kann relativ leicht eine Interpretation finden, so dass der
Wert von dieser einfachen Formel g und dieser einfachen Formel h nicht
gleich sind.
Ich kann einfach sagen, p von 0 sei gleich wahr und p von 2 sei gleich
falsch.
Dann ist der Wert dieser einen Interpretation von p0 und p0 wahr und
der Wert dieser Interpretation von p2 und p2 ist falsch.
Das heißt, die Werte dieser beiden Formeln sind nicht für alle
Interpretationen gleich und damit sind diese beiden Formeln nicht
zueinander äquivalent.
Das ist natürlich unschön, da würde jeder sagen, das ist ja Quatsch.
Wenn ich so zwei Formeln habe, dann habe ich ja eigentlich gefühlt
schon die Intuition, dass die äquivalent sein sollen.
Dass es also eigentlich keinen Unterschied machen soll, ob ich die
Variable a oder b nenne, solange ich sie konsistent und konsequent
immer anders benenne in den beiden Formeln.
Das heißt, wir müssen irgendwie jetzt diesen Namen der
Aussagenvariablen vergessen.
Dazu gibt es zwei Möglichkeiten.
Die erste Möglichkeit ist, dass wir die Syntax verändern, dass wir
also immer eine strikte Nummerierung erfordern und nicht mehr
Variablen haben, als wir wirklich brauchen in der Formel.
Dass man also sowas wie p2 und p2 eben nicht hat, sondern dass das in
der Syntax automatisch zu p0 und p0 werden muss, weil halt die Menge
der Variablen, die vorkommen in dieser Formel eben nur eins ist.
Oder man hat halt die andere Möglichkeit, dass man nochmal eine
Abbildung einführt, die die Variablen in so eine Abbildung
umnummeriert.
Das heißt, wenn jetzt b hoch k, also die Tupel aller Wahrheitswerte
sind, die, wo das Tupel letztendlich mindestens so viele Werte
enthält, wie wir Variablen in einer Formel haben, dann würden wir
jetzt gerne das x abbilden auf eine durchnummerierte, dann soll diese
Interpretation abgebildet werden auf den Wert dieser Interpretation x
von g. Das heißt, angenommen wir hätten insgesamt die Menge pI1 bis
pIk an Variablen.
Und diese I1 bis Ik, die seien entsprechend irgendwie geordnet,
entsprechend ihrer Ordnung in den natürlichen Zahlen.
Dann definieren wir für jeden Vektor, für jedes Tupel x1 bis xk eben
eine Umordnung so, dass wir die Variablen mit ihren Indizes
entsprechend durchnummerieren, entsprechend anordnen.
Das heißt, wir machen genau das, wir benennen die Variablen so um,
dass, wenn ich drei Variablen habe, die genau die Namen p1, p2, p3
bekommen oder p0, p1, p2 bekommen oder wenn ich nur eine Variable
habe, egal ob ich die jetzt p3 genannt hatte oder so, wenn nur eine
Variable in der Formel vorkommt, dann benenne ich die um auf p0.
Und die zweite Variable, die vorkommt in der Formel, wird dann
entsprechend auf p1 umbenannt.
Und wenn ich mir diese Abbildung Ix entsprechend so definiere, und
dabei ist es egal, ob ich genauso viele Abbildungen habe, wie ich
Variablen in meiner Formel habe, das Wichtigste ist nur, dass ich
mindestens so viele Umbenennungsvorschriften in meiner Abbildung Ix
habe, wie ich Variablen habe in der aussagenlogischen Formel.
Wenn ich also mindestens alle Variablen, die in der Formel vorkommen,
umbenennen kann, sodass sie aufsteigend nummeriert sind.
Wenn das der Fall ist, kann ich mit dieser Abbildung Ix gerade diese
Umnummerierung vornehmen, sodass die Variablen Namen völlig egal sind,
sondern eine Formel dann den Namen so bekommt, zum Beispiel in der
Reihenfolge, wie die Variablen vorkommen in der Formel.
Und dann wird nämlich eben aus diesem p2 und p2, wird automatisch dann
p0 und p0.
Und p0 und p0 bleibt sozusagen p0 und p0.
Ich ersetze die Namen durch sowas wie die erste Variable, die in der
Formel vorkommt, die zweite Variable, die in der Formel vorkommt, die
dritte Variable, die in der Formel vorkommt.
Das ist die Bedeutung und der Sinn dieser Umnummerierung, dieser
Umbenennung.
Für unsere Zwecke machen wir das eigentlich intuitiv und implizit und
wir machen das alles dann nicht mehr entsprechend explizit, wir gehen
einfach davon aus, dass wir das so entsprechend immer gemacht haben.
Dann brauchen wir noch den Begriff des Modells.
Wir sagen, dass eine Interpretation ein Modell einer Formel ist, wenn
der Wert der Interpretation von der Formel wahr ist.
Und jetzt können Sie sich ein bisschen zurückerinnern an das, was
Ihnen der Herr Breusner in der Einführungsveranstaltung, in der
Erstsemesterbegrüßung gesagt hat, wir modellieren viel in der
Informatik.
Und dies ist eben eine besondere Form des Modells, das ist eine Form
des Modells, die mit der Aussagenlogik arbeitet.
Wir haben also ein Modell, eine Belegung von Variablen, eine
Parametrisierung einer Formel, sodass diese Formel wahr wird.
Das kann man sich so vorstellen, dass wir haben eine Formel aufgebaut,
die irgendetwas beschreibt, irgendeinen Zusammenhang beschreibt.
Und wir würden jetzt gerne in der Parametersatz lernen, sodass diese
Formel korrekt ausgewertet wird, sodass sie etwas korrekt beschreibt,
was wir in der Wirklichkeit vorfinden.
Das ist so eine Möglichkeit, wie wir jetzt ein Modell interpretieren
können.
Rein formell, ein Modell einer Formel ist eine Interpretation, also
eine Belegung der Variablen mit Wahrheitswerten, sodass am Ende die
Formel wahr wird.
Und genauso gut können wir das erweitern auf eine Menge von Formeln.
Eine Interpretation I ist eben ein Modell einer Menge von Formeln,
wenn ich halt mehrere verschiedene komplexe zusammenhängende
Sachverhalte aussagenlogisch beschreibe.
Also eine Interpretation I ist ein Modell einer Formelmenge, wenn
diese Interpretation auch ein Modell jeder Formel aus der Menge der
Formelmengen ist.
Das heißt mit anderen Worten, wenn jede Formel aus dieser Formelmenge
zu wahr ausgewertet wird, wenn ich die Interpretation I einsetze.
Wenn jedes Modell für eine Formel in dieser Menge von Formeln auch ein
Modell ist von einer Formel G, dann hat man diese Notation, G folgt
aus der Formelmenge.
Das soll heißen, diese Formel ist immer dann wahr, wenn auch jede
Formel in dieser Ausgangsmenge Gamma wahr ist.
Man könnte sagen, diese Formeln, die in dieser Formelmenge Gamma sind,
sind so etwas wie eine Art Prämisse, eine Art Voraussetzung.
Und wenn die wahr sind, dann muss daraus folgern, dass auch G wahr
ist.
Wir können sozusagen G aus dieser Formelmenge Gamma ableiten.
Und wenn diese Formelmenge nur eine einzige Formel enthält, dann sagen
wir, G folgt aus H, statt diese Menge, die nur H enthält, aus der
folgt G.
Wenn jetzt diese Voraussetzung, diese Menge aus Formeln, aus denen ich
folgere, wenn die leer ist, dann ist automatisch G für alle
Interpretationen wahr.
Warum?
Naja, eine Interpretation muss wahr sein für alle Formeln aus der
Prämisse, aus dieser Gamma.
Es gibt keine Formeln da drin, also ist jede Interpretation
automatisch wahr für alle Formeln, die da drin sind, weil es eben
keine Formeln gibt, die da drin sind.
Und somit ist dann logischerweise auch G für alle Interpretationen,
die es gibt, wahr.
Und so eine Formel, aussagenlogische Formel G, die für alle
Interpretationen wahr ist, die kriegt einen speziellen Namen.
Sowas nennen wir eine Tautologie.
Eine Tautologie ist eine Formel, die allgemein gültig ist.
Die also immer wahr ist, egal wie ich die Variablen in der Formel mit
Werten belege.
Einfaches Beispiel ist z.B.
P oder Nicht-P.
Wenn P 0 ist, dann ist logischerweise Nicht-P 1.
Dementsprechend ist immer einer der beiden Variablen in dieser Formel
1.
Und wenn ich das mit oder verknüpfe, kommt logischerweise immer 1
raus.
Aber z.B.
auch sowas wie Kompliziertes, wie aus P folgt aus Q folgt P. Wenn ich
das schachtel, ist auch immer etwas, das wahr ist.
Das kann man z.B.
anhand der Wahrheitstafel relativ einfach sehen.
Außerdem sagen wir noch, dass eine Formel erfüllbar ist, wenn ich eine
Interpretation finde, für die diese Formel wahr ist.
Wenn es also mindestens eine Interpretation gibt, für die die Formel G
wahr ist.
Das ist in einigen Anwendungen wichtig, dass man nachweisen möchte,
dass man eine Formel hat, die erfüllbar ist.
Das ist manchmal relativ einfach nachzuweisen.
Im einfachsten Fall setze ich einfach alle Interpretationen ein,
solange bis ich eine finde, die wahr ist.
Oder wenn ich durch alle durch bin und ich habe keine gefunden, die
wahr ist, dann ist die Formel offensichtlich nicht erfüllbar.
Bei einigen Formeln ist das einfach, aber es gibt auch durchaus andere
Formeln, für die das nicht so einfach ist, aus denen man das nicht so
leicht sieht.
Zum Beispiel, wenn man sich nicht auf eine feste Anzahl an Variablen
festlegt, sondern allgemeingültig zum Beispiel beliebig endlich große
Formeln fordert und die irgendwie zusammensetzt nach einem bestimmten
Schema und sich jetzt fragt, ist diese Formel erfüllbar oder nicht.
Das machen Sie aber dann in aller Ausführlichkeit später noch in der
Vorlesung Grundlagen der theoretischen Informatik.
Darum kümmern wir uns jetzt hier nicht weiter.
Es gibt ein paar interessante Beispiele für Tautologien.
Nehmen wir zum Beispiel an diese G-Doppelfeil H.
Ich hatte schon gesagt, dieses G-Doppelfeil sprechen wir äquivalent.
Jetzt ist die Frage, warum ist das äquivalent?
G-Doppelfeil H war nochmal die Abkürzung aus G folgt H und aus H folgt
G.
Wenn wir jetzt eine beliebige Interpretation in diese Formel aus G
folgt H und aus H folgt G einsetzen,
dann, also die Wallfunktion immer weiter reinziehen, dann kommen wir
am Ende dabei raus, dass da steht aus G folgt H und dann jeweils die
Werte eingesetzt.
Dann kann man zeigen, dass wenn G und H äquivalent sind, also der Wert
von G, der immer da reingesetzt wurde, dem Wert von H entspricht, dann
kann man das da oben in diese Auswertung reinsetzen.
Also nochmal, wir haben hier normal, so wie wir das Auswerten von
Interpretationen definiert haben, diese Wallfunktion einfach
reingezogen in diese Formel.
Erster Schritt, Anwendung zweiter Schritt, sodass am Ende da steht,
das ist die Auswertung der Unfunktion von der Auswertung der folgenden
Ausfunktion, von dem Wert der Formel G und dem Wert der Formel H, das
Ganze mit Un verknüpft von dem Wert der Formel A und dem Wert der
Formel G.
Und die Definition von G und H sind äquivalent, weil eben gerade, dass
der Wert jeder Interpretation von G auch dem Wert jeder Interpretation
von H entspricht.
Das ist die Definition von Äquivalenz.
Das heißt, überall da oben, wo Wall I von H vorkommt, können wir auch
schreiben Wall I von G, weil wir voraussetzen, dass G und H äquivalent
sind.
Und wenn man das einsetzt, dann hat man am Ende da eben stehen, das
muss wahr und wahr sein.
Das heißt, wenn G und H als Formeln miteinander äquivalent sind, dann
heißt das, dass diese Auswertung des Doppelfeiles, der die Abkürzung
war aus H folgt G und aus G folgt H, immer wahr ist.
Und das ist die Begründung dafür, warum wir lesen G Doppelfeil H ist
gleich G Äquivalent H.
Äquivalent hatten wir ja eigentlich definiert für Formeln, und das da
ist eigentlich erstmal nur eine aussagenlogische zusammengesetzte
Formel.
Aber daraus eben, dass wenn G Äquivalent H ist, dann muss auch dieser
Ausdruck mit dem Doppelfeil zu wahr ausgewertet werden.
Deshalb sprechen wir diesen Doppelfeil eben als den Äquivalentoperator
aus.
Das heißt, lemma, wenn G Äquivalent H ist, dann ist logischerweise G
Doppelfeil H eine Tautologie, ist also immer wahr.
Haben wir gerade eben gezeigt.
Man kann auch die umgekehrte Richtung zeigen.
Man kann auch zeigen, wenn G Doppelfeil H eine Tautologie ist, dann
muss auch folgen G Äquivalent H.
Das heißt, wenn man es jetzt ganz verwirrend sprechen will, könnte man
sagen, G Äquivalent H ist eben Äquivalent zu G Äquivalent H.
Da muss man halt aufpassen.
Hat man jetzt einmal den Äquivalenzbegriff genommen als
Äquivalenzbegriff zwischen Formeln?
Hat man den Äquivalenzbegriff jetzt genommen als diesen Doppelfeil?
Oder hat man den Äquivalenzbegriff dafür genommen, dass man dieses
genau dann, wenn beschrieben hat?
Deswegen ist es ganz hilfreich, dass wir eben dieses wenn und dann und
genau dann wenn sagen, genau wenn dann sagen, weil sonst hätte man da
dreimal Äquivalent dann hinter stehen.
Also einige konkrete Beispiele von Tautologien.
Nicht, nicht G, Äquivalent G ist eine Tautologie.
Aus G folgt H ist Äquivalent zu Nicht G oder H.
Haben wir schon gezeigt.
Aus G folgt H ist Äquivalent zu Aus Nicht H folgt Nicht G.
G und H ist zum Beispiel Äquivalent zu Nicht, Nicht G oder Nicht H.
Und G oder H ist Äquivalent zu Nicht, Nicht G und Nicht H.
Man kann sich das jetzt alles überlegen, indem wir die Äquivalenzen,
die wir vorher schon mal festgelegt haben, da einfach anwendet und
guckt, welche oder auch die Tautologien, die wir vorher schon gezeigt
haben, halt immer sukzessive da entsprechend einsetzt.
Und dann G und G ist halt Äquivalent zu G und G oder G ist auch
Äquivalent zu G.
G und H ist Äquivalent zu H und G.
Das ist interessant.
Das heißt, G und H ist Äquivalent zu H und G und genauso ist G oder H
ist Äquivalent zu H oder G.
Was bedeutet das?
Das bedeutet nichts anderes, als dass wir damit zeigen, dass dieses
Konnektiv UND und dieses Konnektiv ODER kommutativ sind.
Das es also keine Rolle spielt, in welcher Reihenfolge wir G oder H
mit dem Konnektiv UND oder mit dem Konnektiv ODER verbinden.
Es kommen äquivalente Formeln heraus.
Macht keinen Unterschied bei der Interpretation.
Alle Interpretationen für G und H haben auch immer den gleichen Wert
wie alle Interpretationen für G oder H.
Und dann die letzte Zeile.
G und H geklammert und dann mit K ist eben Äquivalent zu G und H
geklammert G und in Klammern H und K.
Und das gleiche mit ODER.
Wenn ich erst G oder H rechne und dann ODER K draufrechne, dann ist
das Äquivalent dazu, als wenn ich erst G, ODER und vorher H oder K
miteinander verknüpfe.
Und das ist eben gerade das Assoziativgesetz für die Konnektive UND
und für die Konnektive ODER.
Es gibt auch andere Tautologien.
Das hier sind weitere Beispiele von Tautologien aus G folgt G, nicht G
oder G.
Aus G folgt H folgt G, hatten wir alle schon gesehen.
Sind alles Tautologien.
Die sehen jetzt erstmal nicht sonderlich sinnvoll aus.
Die brauchen wir gleich aber.
Wir brauchen gleich das Wissen, dass einige von diesen Dingern
Tautologien sind.
Warum?
Weil wir wollen uns jetzt anschauen, wie man formell Beweise aufbauen
kann.
Bisher, wenn Sie Beweise durchgeführt haben, dann sind Sie immer
irgendwie intuitiv vorgegangen.
Sie hatten so ein paar Schemata und haben dann mit logischen Schlüssen
operiert.
Sie haben mit Voraussetzungen operiert und dann gezeigt, das kann ich
voraussetzen.
Dann habe ich irgendwelche bestimmten Operatoren, die ich vorher schon
mal gezeigt hatte oder irgendwelche Aktionen, die kann ich anwenden
und dann könnte man sagen, ja, dann ist das ein logischer Schluss.
Wenn das ist, dann muss auch das folgen.
Und das hatte immer noch so ein paar, ja, nicht Doppeldeutigkeiten,
aber so ein paar natürlich sprachliche, weiche, diskussionsartige
Schlussfolgerungen in den Beweisen.
Und eine Möglichkeit, die man jetzt machen kann, ist, dass man Beweise
und die Art und Weise, Sachen Aussagen zu beweisen, formalisieren
kann.
Jetzt können Sie sagen, ja, warum denn?
Ich kann doch den Beweis um Gottes Willen so hinschreiben.
Warum muss ich mir jetzt das antun und da jetzt auch nochmal eine
Mathematik für erfinden?
Ich habe doch die natürliche Sprache, Herrschaftszeiten, kann man da
mal nicht mit aufhören.
Es gibt einen einfachen Grund.
Wenn Sie beweisen, können Sie das so machen und jeder vernünftige
Mensch wird den Beweis nachvollziehen können.
Aber wir sind Informatiker.
Wir wollen nicht selber was machen.
Wir wollen, dass der Computer das macht.
Für mich als Informatiker ist das das Schönste, wenn ich nicht mir
überlegen muss, hier eine Aussage, ist die jetzt wahr oder falsch?
Das Schönste für mich als Informatiker ist, wenn ich dem Computer
sagen kann, hier ist eine Aussage, guck mal, ob du es beweisen kannst.
Oder hier ist eine Aussage, der eine behauptet, dass es wahr ist, guck
mal, ob du einen Beweis findest.
Und damit der Computer hinterher in der Lage ist, einen Beweis zu
finden, muss man halt diese Art und Weise, wie man Beweise durchführt,
irgendwie so formalisieren, dass man hinterher Algorithmen schreiben
kann, die bestimmte Beweistechniken einfach anwenden oder auch
systematisch nach Beweisen für irgendwelche Aussagen suchen.
Und das machen wir mit dem Formalismus eines Kalküls.
Ein Kalkül ist ein System für Beweise.
Und das System ist halt so gestrickt, dass man das hinterher auch gut
in Algorithmen im Computer kodieren kann.
Und das sind durchaus Sachen, die haben in den letzten Jahrzehnten an
Bedeutung gewonnen.
Zum Beispiel so etwas wie das Vier-Farben-Problem in der Topologie.
Also die Behauptung, wenn ich eine Landkarte habe mit so
aneinandergrenzenden Ländern oder aneinandergrenzenden Flächen, dann
reichen mir vier Farben aus, um alles so durchzufärben, dass nie zwei
gleichgefärbte Flächen aneinanderstoßen.
Das war ein Beweis, den hat man als Mensch, hat kein einzelner Mensch
mal alleine hingeschrieben.
Das war etwas, das hat man vermutet, dass das richtig ist, aber es
hatte nie ein Mensch sich hingesetzt und das beweisen können.
Der Grund war, weil der Beweis zu aufwendig war.
Und erst später irgendwann konnte man mit Hilfe eines
Computerprogrammes einen Beweis für diese Aussage konstruieren, einen
Beweis finden.
Und das hat durchaus zu großen Diskussionen geführt.
Es gibt durchaus Mathematiker, die auch heute noch auf dem Standpunkt
stehen und sagen, das ist kein Beweis, da ist irgendwas aus dem
Rechner rausgekommen, das kann ich nicht nachvollziehen.
Und wenn ich das nicht nachvollziehen kann, ist es nicht überprüfbar,
ob der Beweis richtig oder falsch ist, das ist kein gültiger Beweis.
Das könnte ja zum Beispiel auch ein Fehler im Computerprogramm sein.
Wenn ich als Mensch nicht nachvollziehen kann, welche Beweisschritte
dieses Computerprogramm gemacht hat, dann ist es falsch.
Das hat zwei Aspekte.
Der erste Aspekt ist, ist dieses Kalkül, mit dem der Computer
gearbeitet hat, ist das richtig?
Das ist etwas, was kann man beweisen, das könnte man auch zeigen.
Dann haben sich halt die Kritiker darauf zurückgezogen, ja aber
vielleicht ist das Computerprogramm, das in diesem Kalkül nach dem
Beweis gesucht hat, falsch.
Und da muss man dann mit den Kollegen rechnen, die sich eben mit
Zuverlässigkeit von Software und Softwareverifikation befassen.
Die sagen dann wiederum, ja Sie können das verifizieren.
Und dann kommt man zum Zirkelschluss, weil die verifizieren wieder das
Computerprogramm durch ein Computerprogramm und so hat man halt die
Kritiker nie wirklich befriedigt.
Also ein Kalkül als ein System für Beweise ist gerade für uns
Informatiker interessant, weil wir dann anfangen lassen können, den
Computer Beweise zu finden, finden zu lassen.
Allgemein ist ein Kalkül aufgebaut aus einem Alphabet A.
Dann braucht man eine Syntax für Formeln und eine Menge von
syntaktisch korrekten Formeln, die über diesem Alphabet A aufgebaut
sind.
Das heißt, so wie bei der Außenlagenlogik, wo ich mir dieses Alphabet
am Anfang zusammengestückelt hatte, aus der Menge aller Variablen, aus
der Menge aller Konnektive, habe ich hier jetzt allgemein Alphabet A,
bestimme die Menge aller möglichen Wörter aus diesem Alphabet und
nehme mir irgendeine Syntax her, die ich mir definiere und das ist
halt dann die Menge aller Formeln, die dann eine Teilmenge aller
Wörter über dem Alphabet sind.
Dann brauche ich Axiome.
Axiome sind Formeln und wenn sie Formeln sind, eine Menge von Formeln
sind, dann ist es wiederum eine Teilmenge der syntaktisch korrekten
Formeln.
Axiome sind eine Menge von Formeln, von denen ich ausgehe, dass sie
wahr sind, sind die Voraussetzungen.
Axiome sind nicht beweisbar, aber Axiome sind wahr.
Und dann brauche ich einen Mechanismus, um Schlüsse zu ziehen.
Um aus Axiomen neue Formeln schließen zu können, brauche ich irgendwie
einen Mechanismus, um also etwas aus den Axiomen ableiten zu können.
Und diese Schlussregeln sind eine Teilmenge aller Relationen, wo ich K
-lange Formeln habe, die über einem Alphabet aufgebaut sind.
Also ich nehme sozusagen die K-zeichenlangen Formeln aus dieser Formel
der Aussagenlogik her, also es müssen aussagenlogische Schlüsse sein.
Und das ist eine Relation, die bildet halt ab, indem sie neue Formeln
findet.
Jetzt kann man auch ein Aussagenkalkül bilden für die Aussagenlogik.
Als Alphabet nehmen wir einfach das Alphabet der Aussagenlogik, wie
wir es uns konstruiert haben.
Syntaktisch korrekte Formeln hatten wir uns auch schon definiert, das
sind alle aussagenlogischen Formeln.
Jetzt brauchen wir eine Menge an Axiomen, von denen wir ausgehen, dass
sie wahr sind.
Diese Menge der Axiome muss eine Teilmenge der aussagenlogischen
Formeln sein.
Und jetzt muss man mal scharf nachdenken.
Also wir haben Axiome, das sind Formeln, von denen gehen wir aus, dass
diese Formeln wahr sind.
Was bietet sich da an, an Axiomen?
Wie könnte man seine Axiome da aufbauen?
Was bietet sich an, für Formeln zu nehmen, von denen wir ausgehen,
dass die wahr sind?
Genau, wenn wir also Formeln haben, von denen wir wissen, dass sie
Tautologien sind, dann bieten sie sich ja gerade eben an, weil
Tautologien sind immer wahr für jede Interpretation.
Das heißt, da braucht man nicht was zu beweisen, wir haben irgendwie
gezeigt, dass die immer wahr sind.
Also bieten die sich als Axiome an.
Dann brauchen wir also irgendwelche Axiome, die bestehen aus
Tautologien, und jetzt brauchen wir eine Schlussregel.
Und für die Schlussregel, beim aussagenlogischen Kalkül, reicht eine
einzige Schlussregel aus.
Und diese Schlussregel nennt sich Modus ponens.
Das ist eine Teilmenge der Relationen von Formeln aus drei Tupeln
aufgebaut, also aus Triepeln von Formeln.
Das hier sind unsere Axiome.
Das sind alles Tautologien, die wir vorhin schon mal auf der Formel
stehen hatten.
Das erste hatten wir als Tautologie gesehen, das zweite hatten wir als
Tautologie gesehen, und das dritte hatten wir als Tautologie gesehen.
Das sei die Menge unserer Axiome.
Und jetzt ist die Frage, was hat es mit diesem Modus ponens auf sich?
Was soll der bedeuten?
Das finde ich, persönlich finde ich ein bisschen schwierig zu lesen.
Also der Modus ponens ist eine Teilmenge der Triepeln aus den
aussagenlogischen Formeln, und zwar der Gestalt, dass ich alle Triepel
hernehme, wo an der ersten Stelle steht, aus G folgt H, an der zweiten
Stelle steht G, und aus der dritten Stelle folgt H.
Und dann schreibt man das entsprechend so hin.
Was will ich damit machen?
Was ist die Idee hinter diesem Modus ponens?
Die Idee hinter dem Modus ponens ist, angenommen ich weiß, dass aus G
H folgt, und angenommen ich habe irgendwie gezeigt, dass G wahr ist.
Daraus möchte ich dann den Schluss vollziehen, dass auch H wahr ist.
Das heißt, nichts anderes ausgedrückt als,
also ich habe irgendwie Formeln hingeschrieben, hergeleitet, von denen
ich weiß, ich habe als erstes gezeigt, aus G folgt H.
Dann habe ich gezeigt, es gilt G.
Und dann sagt mir der Modus ponens nichts anderes, dass auch H wahr
ist, dass H als Formel wahr ist, unter der Prämisse.
Die Prämisse kann sein, dass irgendwelche anderen Formeln wahr sind,
aber es hat mir gezeigt, dass das wahr ist.
Das heißt, wenn ich so einen Beweis habe, und Sie haben das schon
häufig gemacht, dass Sie Beweise so in Zeilen aufgebaut haben, dass
Sie irgendwelche Formeln, die eine Äquivalenz umgeformt haben, wenn
immer Sie die Folge irgendwo sehen, und die müssen nicht direkt
aufeinander folgen, aber wenn immer Sie drei Zeilen sehen, oder zwei
Zeilen sehen, in der einen Zeile steht, aus G folgt H, und in der
anderen Zeile steht G, dann können Sie eine dritte Zeile hinschreiben,
die sagt einfach H, weil Sie dann wissen, aus Erstens und Zweitens
muss logischerweise folgern, dass H wahr ist.
Und damit kann man jetzt beweisen.
Und dieses Beweisen, einen Beweis nennen wir eine Ableitung.
Die Ableitung nutzt die Prämissen aus, die Voraussetzungen eines
Satzes.
Ein Satz hat in der Regel immer Voraussetzungen und eine Behauptung.
Hier nutzen wir als erstes aus die Prämisse, dann unsere Aktionen, die
immer wahr sind, die also gar keine Prämisse haben, und danach die
Schlussregel.
Angenommen, wir haben jetzt so eine Menge von Formeln, die die
Prämissen sind, und in dieser Menge von Formeln ist die Prämisse und
die Hypothese drin.
Wir wollen jetzt zeigen, dass wenn diese Prämissen gelten, dass dann
in der Aussagenlogik auch eine bestimmte andere Formel, G, gilt.
Dann müssen wir G aus dieser Prämisse ableiten.
Und wir definieren uns, eine Ableitung, als eine Folge von Formeln.
Eine endliche Folge von Formeln.
Und die schreiben wir eben genauso hin.
Die schreiben wir zeilenweise hin.
Erstens ist eine Formel die erste Formel in der Folge von Formeln.
Zweitens G ist die zweite Formel in der Menge von Formeln.
Und dann haben wir schon durch die Schlussregel drittens hinschreiben
können, als das dritte Element der Menge von Formeln.
Also wir haben diese Folge von Formeln, G1 bis Gn.
Und wenn wir G ableiten wollen, dann muss spätestens Gn gleich G sein.
Also sobald ich irgendwie in dieser Folge von Formeln, die ich
hinschreibe in diesen Zeilen, wenn ich da irgendwann nur G einzeln auf
der Zeile stehen habe, dann habe ich G aus den Prämissen abgeleitet.
Und in dieser Folge von Formeln, die ich hinschreiben darf, die darf
ich nicht irgendwas beliebiges hinschreiben, sondern da darf ich nur
eins von drei Dingern hinschreiben.
Ich darf in so eine Zeile entweder eine Aktion schreiben, oder ich
darf in die Zeile eine Formel aus der Menge der Prämissen schreiben,
oder ich darf eine Zeile hinschreiben, so dass ich weiter vorne in
meinen Zeilen irgendwo die Voraussetzungen, die ersten beiden Elemente
des Modus ponens gesehen habe.
Das heißt, wenn ich dann Gi ganz ans Ende schreiben möchte, während
ich die Ableitung aufbaue, muss ich irgendwo vorher in der Folge mal
gesehen haben, dass Gi aus irgendeinem H folgt, und dass irgendwo in
irgendeiner Zeile das H alleine stand.
Und das alles, bevor ich dieses neue Gi hinschreibe.
Und wenn ich so eine Folge finde, in der dann ganz am Ende das G
vorkommt, danach kann ich aufwenden, ich kann natürlich noch weiterhin
schreiben, aber wenn ich irgendwie auf diese Art und Weise, ich
schreibe Aktionen hin, ich schreibe Prämissen hin, oder ich wende den
Modus ponens auf die Aktionen und Prämissen an, die ich bisher
hingeschrieben habe, um eine neue Formel hinzuschreiben.
Wenn irgendwann die neue Formel, die ich hinschreibe, G ist, dann habe
ich G aus Gamma abgeleitet, und wir schreiben das mit diesem G
abgeleitet aus Gammasymbol.
Angenommen, ich mache keine Prämissen, angenommen, ich nehme mir nur
die Aktionen her, und kann aus den Aktionen eine Formel G herleiten.
Das heißt, unter den Aktionen ist diese Formel G allgemeingültig.
So ein G nennen wir dann ein Theorem innerhalb dieses Kalküls.
Das heißt, die Aktionen und die Ableitungsregeln bestimmen hier
vollständig das Kalkül, und alles, was ohne weiteren Voraussetzungen
wahr ist, ableitbar ist, heißt dann ein Theorem des Kalküls.
Machen wir ein erstes Beispiel, und damit das nicht einfach nur so da
steht, machen wir das schön langsam in der Reihe nach, damit man in
Ruhe mitdenken kann.
Also, die Behauptung sei aus P folgt P. Das wollen wir beweisen, das
sei die Behauptung.
Was ich jetzt machen muss, ich habe nur Prämissen oder Aktionen.
Und ich behaupte, das hier sei sogar ein Theorem.
Das heißt, ich habe keine Prämissen, ich habe nur noch meine Aktionen.
Das heißt, am Anfang kann ich nichts anderes hinschreiben als
Aktionen.
Jetzt könnte ich mir alle Aktionen hinschreiben, aber als Mathematiker
ist man natürlich dann hinterher sparsam.
Ich schreibe dann nur noch die Aktionen hin, die ich hinterher auch
anwenden möchte.
Insbesondere habe ich ja unendlich viele Aktionen, weil in diesen
Aktionen, wie ich gesehen habe, in diese Tautologien, kann ich ja
beliebige Formeln reinsetzen.
Ein Aktion, das ich hatte, war aus P folgt P, daraus folgt P und
daraus folgt dann wieder P.
Das sieht jetzt erstmal kompliziert hin.
Wenn man jetzt auf ein paar Folien zurückgeht, dann wird man
feststellen, das hier ist gerade das Aussagen logischer Aktion Nr.
2.
Dann schreibe ich mir ein zweites Aktion hin.
Das ist jetzt nicht mehr ganz so wild.
Das war das Aktion Nr.
1 der Aussagenlogik.
Und jetzt muss ich mal scharf hingucken und mal schauen, ob ich den
Modus Pronens anwenden kann.
Ich habe hier diese Formel, nennen wir sie mal G stehen.
Und wenn ich jetzt diese Formel irgendwo finden kann,
als Voraussetzung, dann kann ich mit ein bisschen Glück den Modus
Pronens anwenden.
Jetzt muss ich selber nochmal gucken.
Und jetzt habe ich Glück, kann das hier nochmal klammern.
Wir hatten uns gemerkt, äußere Klammern weglassen.
Das ist einfach nur eine verkürzte Schreibweise.
Und dann steht hier genau das Gleiche.
Also hier steht links von dem Pfeil genau das, was im Aktion 1 steht.
Wenn ich G und jetzt hatten wir G, A kann ich ersetzen, kann ich dann
H einfügen.
Das war der Modus Pronens.
Das heißt, das hier wäre mein H im Modus Pronens.
Das heißt, das hier darf ich einfach nach Modus Pronens alleine in
eine Zeile schreiben.
Ohne dieses, was da vorne steht.
Weil das, was da vorne steht, eben gerade eine Aktion ist.
Also schreibe ich nur noch hin.
Das ist die rechte Seite von dem Pfeil.
Plus ich habe wieder diese Verkürzungsregel angewendet, dass ich
äußere Klammern weglassen kann.
Jetzt nehme ich mir noch eine Aktion her.
Aus P folgt, aus P folgt P. Das ist wieder das Aussagen logischer
Aktion 1.
Und jetzt muss ich gucken, habe Glück.
Das ist ja gerade gleich eben da.
Also kann ich eine fünfte Zeile hinschreiben mit Anwendung des Modus
Pronens aus 3 und 4.
Und brauche nur noch das rechte hinzuschreiben.
Aus P folgt P. Und das ist ja gerade das, was ich hier oben behauptet
habe.
Das heißt, ich habe also eine Folge von Formeln gefunden, wo ich mir
entweder Aktionen hingeschrieben habe, oder eine neue Zeile, bei der
ich den Modus Pronens auf irgendwelche Dinge, die ich vorher schon
hingeschrieben hatte, also entweder eine Aktion sind oder mit Hilfe
des Modus Pronens hergeleitet habe, habe diese Folge gefunden.
Und ganz am Ende steht aus P folgt P. Und da ich sonst keine anderen
Prämissen verwendet habe und nur Aktionen angewendet habe, ist dieses
P von P abgeleitet aus der leeren Menge der Prämissen und damit gemäß
Definition ein Theorem des aussagenlogischen Kalküls.
Und dabei ist es jetzt völlig egal, ob ich das P, G, H, K oder sonst
was nenne, ob P eine Variable ist oder ob P eine weitere
zusammengesetzte komplexe Formel ist.
Ich kann dieses aus P folgt P für jede beliebige Formel herleiten.
Das heißt, das hier ist so eine Art Beweisschema.
Und dann bin ich natürlich faul.
Angenommen, ich habe ein zweites Theorem, aus nicht voll P folgt P,
daraus folgt P. Dann kann ich mir wieder erstmal eine Aktion
hinschreiben, diesmal das Aktion Nummer 3.
Und da entsprechend dieses nicht P folgt nicht P und so weiter
einsetzen.
Und jetzt kann ich von hier nach da gehen.
Weil das ist gerade eben das Beispiel von eben.
Ich habe ja eben gezeigt,
aus P folgt P.
Diese Zeile hier, die schreibe ich hin, weil ich weiß, aus P folgt P,
das ist ein Theorem.
Und P folgt P, P ist völlig egal, wie P als Formel ist, es kann jede
beliebige Formel sein, also kann P insbesondere auch nicht P als
Formel sein.
Also gilt das Theorem auch aus nicht P folgt nicht P. Und das kann man
halt als Kurzschreibweise machen, das Wiederverwenden von Formeln, die
man bereits abgeleitet hat, das Wiederverwenden von Theoremen, die man
bereits gezeigt hat.
Da muss ich jetzt nicht wieder alle fünf Schritte vom letzten Mal neu
hinschreiben, sondern ich kann sagen, siehe vorherigen Beweis, das
hier ist ein Theorem, das gilt, oder das hier ist eine Formel, die
gilt unter der gleichen Prämisse.
Wenn ich das schon mal bewiesen habe, kann ich es wiederverwenden und
da einsetzen.
Und dann kann ich wieder den Modus Ponens anwenden auf diese beiden
Zeilen und komme dann eben gerade zu der Behauptung aus nicht P folgt
P folgt P.
Das heißt, damit man es lesen kann, strukturiert man und damit man den
Überblick behält über die Beweise, fängt man eben an, gezeigtes,
abgeleitetes wiederzuverwenden.
Des Weiteren gilt, dass dieser Modus Ponens die sogenannte
Allgemeingültigkeit erhält.
Und das bedeutet, wenn aus G folgt H, wenn das eine Tautologie sei,
wenn halt G und H entsprechend strukturiert sind, und wenn G selber
auch eine Tautologie ist, dann muss auch H eine Tautologie sein.
Das kann man jetzt, wenn man will, beweisen.
Und der Beweis geht so.
Also, Annahme war, aus G folgt H ist eine Tautologie.
Das bedeutet gemäß der Definition für Tautologie, dass für jede
Interpretation diese Formel ausgewertet wahr sein muss.
Und damit... und weiter gilt ja auch, dass G eine Tautologie ist.
Das heißt, der Wert von G bei jeder Auswertung, jeder Interpretation
muss wahr sein.
Das heißt, wo immer ich da oben in der Auswertung von aus G folgt H
hinterher den Wert von G hingeschrieben habe bei der Umformung, kann
ich das einfach durch den Wert wahr ersetzen, weil ja G eine
Tautologie ist.
Und daraus wird dann eben gerade aus wahr folgt der Wert von H und das
soll gerade sein der Wert von H.
Und warum?
Weil das eben die Definition dieser Funktion folgt ist.
Wenn G wahr ist, dann muss gemäß dieser Wahrheitstabelle, die wir
niedergeschrieben haben, so wie diese Folgtfunktion, diese Bullshit
-Funktion definiert ist, der Wert von H rauskommen.
Also gilt für jede Interpretation, die ich habe, wahr ist gleich dem
Wert von H.
Und damit ist H dann entsprechend eine Tautologie.
Und genauso kann man zeigen, dass jedes Theorem des Aussagen-Kalküls
eine Tautologie sind.
Denn alle Aktionen, die ich habe, sind Tautologien in meinem Kalkül
der Aussagenlogik.
Und wenn ich auf Tautologien den Modus Pronens anwende, also wenn ich
aus Tautologien etwas Schlussfolgere, dann ist das, was ich aus dieser
Tautologie abgeleitet habe, mit Hilfe des Modus Pronens ist nach wie
vor eine Tautologie.
Und wenn ich halt Theoreme ableiten will, dann kann ich ja nur aus
Aktionen ableiten, weil Theorem ist die Menge der Prämissen leer.
Das heißt, ich wende den Modus Pronens in irgendeiner geeigneten Form
sukzessive an und habe anfangs mal mit Tautologien angefangen und
alles, was ich neu hinschreibe, ist nach wie vor eine Tautologie.
Also muss auch das, was ganz am Ende steht, das Theorem, das ich mit
der Ableitung gezeigt habe, auch eine Tautologie sein.
Umgekehrt wird es jetzt schwieriger.
Man kann auch zeigen, dass jede Tautologie im Aussagen-Kalkül auch
beweisbar ist.
Und wenn man das zeigt, kommt man eben gerade hin zu der Definition
des Theorems.
Für jede Formel G aus der Formel der aussagenlogischen Formeln gilt,
dass G ein Theorem ist, genau dann, wenn ich G ableiten kann.
Ich kann also beide Richtungen machen.
Ich kann zeigen, dass jedes Theorem eine Tautologie ist und ich kann
zeigen, dass jede Tautologie im Aussagen-Kalkül auch beweisbar ist.
Folglich muss jedes Theorem ableitbar sein.
Jetzt zum Schluss noch der Aussagenlogik, noch ein nützliches Theorem.
Und das Theorem lautet, für jede Formel der Aussagenlogik gilt, wenn
ich zwei Formeln der Aussagenlogik hernehme, dann gilt, dass ich H aus
G genau dann ableiten kann, wenn aus G folgt H ein Theorem ist.
Muss ich halt jetzt zwei Richtungen zeigen.
Das ist wieder eine genau dann, wenn.
Das sind zwei Richtungen, die ich zeigen muss.
Die einfache Richtung.
Angenommen, es gilt, aus G folgt H ist ein Theorem, ist aus nichts
ableitbar.
Daraus will ich zeigen, damit will ich zeigen, dass dann gilt, dass
aus G H folgt.
Angenommen, es ist so, aus G folgt H ist ableitbar aus den Aktionen
des Theorems, dann muss es ja einen Beweis geben, der so aussieht,
dass ich so eine Folge von Formeln habe, G1 bis Gn und das am Ende Gn
eben gerade lautet aus G folgt H.
Das ist ja gerade die Ableitung von aus G folgt H im Aussagen-Kalkül.
Jetzt muss ich daraus ja auch weiter Schlussfolgern können, dass wenn
ich mal gezeigt habe, aus G folgt H, dass ich dann auch eine Ableitung
erleben muss für H ist ableitbar aus G.
Das heißt, ich muss das, was ich hingeschrieben habe, so weiter
verlängern können, dass am Ende nur noch H dasteht.
Ich muss also diese Kette von Ableitungen, die ich gemacht habe, um
aus G folgt H zu kommen, die muss ich jetzt um weitere Ableitungen, um
weitere Zeilen verlängern, sodass ganz am Ende nur noch H alleine auf
einer Zeile steht.
Und das ist in diesem Fall relativ einfach.
Ich kann einfach um zwei Zeilen verlängern.
Die erste Zeile, um die ich verlängere, ist G.
G gilt, weil G eben die Prämisse ist.
Und dann kann ich hinschreiben direkt H, weil ich kann dann den Modus
Pronens anwenden aus G folgt H.
Das war ja gerade das, was am Ende der ursprünglichen Ableitung Gn
lag.
Und kann dann dieses zweite G, das ich verwendet habe, hernehmen, um
Gn und Gn plus 1 durch den Modus Pronens zu reduzieren auf H.
Das ist die einfache Richtung.
Dann gibt es die umgekehrte Richtung.
Also angenommen, ich kann H aus G ableiten, dann muss gelten, aus G
folgt H.
Also angenommen, ich habe wieder eine Ableitung von H aus G, das heißt
ich habe eine Folge von Formeln G1 bis Gn, sodass Gn lautet H.
Jetzt müssen wir daraus einen neuen Beweis konstruieren.
Der besteht jetzt aus Folgen H1 bis Hm, so dass ich aus nichts Ableite
aus G folgt H.
Und das mache ich so, dass ich mir das so vorstelle, dass ich für
jedes Hi in dieser Folge H1 bis Hn mir etwas hinschreiben kann, das
die Form hat, aus G folgt Gi.
Das heißt, ich muss irgendwie zeigen können, dass ich für jedes Gi,
das ich in der ursprünglichen Ableitung hatte, die da lautete, die da
gezeigt hatte, aus G folgt H, dass ich dafür in der neuen Ableitung
etwas hinschreiben kann, das heißt aus G folgt Gi.
Und da muss ich jetzt Fallunterscheidung machen bei der Art der
Formeln Gi, die ich in der ursprünglichen Ableitung stehen hatte.
Die erste Möglichkeit ist, in dieser ursprünglichen Ableitung ist das
Gi ein Aktion.
Laut dem Kalkül darf ich immer Aktionen hinschreiben, Aktionen
hinschreiben.
Wenn Gi ein Aktion ist, muss ich jetzt drei Formeln hinschreiben in
meinem Beweis A.
Und zwar schreibe ich einmal ein Aktion hin, das lautet aus Gi folgt
Gi.
Das ist ein Aktion, darf ich in meinem neuen Beweis H hinschreiben.
Dann schreibe ich Gi hin.
Ist da auch ein Aktion, ist die Voraussetzung.
Und dann, also Gi ist ja ein Aktion, meine Voraussetzung in dieser
Fallunterscheidung war Gi ist ein Aktion, das setze ich ein in ein
anderes Aktion, das ich habe.
Und dann habe ich da zwei Aktionen stehen, das ursprüngliche Aktion
Gi, das ich hinschreiben darf, und dieses Aktion 1, in dem ich das
Aktion Gi eingesetzt habe.
Und die beiden kann ich wieder mithilfe des Modus Ponens
zusammenfassen und kann die zusammenfassen zu aus Gi folgt Gi.
Weil hier Gi ist ein Aktion, steht hier links von diesem neuen Aktion
und rechts von diesem Aktion, von dem Erfolgsfall, steht gerade eben
Gi, aus Gi folgt Gi.
Also ist aus Gi folgt Gi hinschreibbar gemäß diesem Modus Ponens und
das ist eben gerade mein Hi'.
Also für alle Aktionen Gi, die ich habe in dem Beweis Gi, kann ich
jetzt so ein Hi' hinschreiben, wo drinsteht aus Gi folgt Gi.
Gut, was kann das Gi noch sein?
Gi kann eine Formel sein für einen Beweis einer Tautologie.
Also wenn Gi eine Formel, andersrum, wenn Gi, G ist, also Gi könnte G
sein, dann kann ich Formeln für den Beweis der Tautologie anwenden.
Also angenommen hier, dass G3 sei gerade G gewesen.
Dann kann ich die Tautologie Gi folgt Gi hinschreiben, das habe ich
schon mal bewiesen, dass ich das machen darf.
Aus Gi folgt automatisch aus Gi folgt Gi.
Das heißt, mein Hi' wäre in diesem Fall einfach aus Gi folgt Gi.
Und der dritte Fall ist, dass dieses Gi eben nicht einfach nur Gi war,
also die Prämisse von meinem ursprünglichen Beweis Gi, und es ist auch
keine Aktion, sondern es ist irgendwie aus dem Modus ponens
hergeleitet worden.
Also Gi ist irgendeine beliebige Formel K2, die durch den Modus ponens
hergeleitet wurde.
Und wenn sie durch den Modus ponens hergeleitet wurde, muss es
irgendwo weiter oben, oberhalb von diesem Gi in dem ursprünglichen
Beweis, Zeilen geben, von denen die eine lautet aus K folgt K2 und die
andere lautet K1.
Nur wenn ich zwei solche Zeilen weiter oben finde in dem Beweis, dann
konnte ich überhaupt K2 herleiten.
Gut, also ich weiß, wenn Gi gleich K2 ist, dann gibt es irgendwo
weiter oben Formeln, wo einmal steht aus K1 folgt K2 und einmal steht
K1.
Dann habe ich schon irgendwie abgeleitet, dass aus Gi K1 folgt, weil
K1 muss da irgendwie hingekommen sein.
Es kann sein, dass K1 eine Aktion war, es kann sein, dass K1 Gi war
oder es kann sein, dass ich K1 echt hergeleitet habe aus Gi in meinem
Beweis.
Genauso habe ich K1 folgt K2 schon genauso hergeleitet.
Muss auch entweder eine Aktion sein oder es muss irgendwie Prämisse
gewesen sein, also Gi gewesen sein oder ich habe es durch Modus ponens
hergeleitet.
Das heißt, diese beiden Zeilen kann ich auch problemlos hinschreiben,
aus Gi folgt Gi1 und aus Gi folgt Gi2.
Dann kann ich das Ganze entsprechend in eine Aktion, in das Aktion
Nummer 3 einsetzen.
Kann dann in das Aktion Nummer 3 einsetzen, auf der linken Seite
dieses aus Gi folgt aus K1 folgt K2, das ist gerade die Anwendung des
Modus ponens und rechts dieses, das aus Gi folgt K1, das hatte ich
schon und aus Gi folgt K2 hatte ich gezeigt, dass das irgendwie
hergeleitet sein muss.
Also kann ich das auch in das Aktion Nummer 3 an der Stelle einsetzen.
Dann forme ich das Ganze entsprechend noch um in diese Form und kann
jetzt zweimal den Modus ponens anwenden.
Ich habe also einmal hier aus Gi folgt Gi1 habe ich das stehen und die
linke Seite habe ich das stehen und dann kann ich logischerweise durch
den Modus ponens einfach hier die rechte Seite stehen lassen.
Aus Gi folgt Gi2 habe ich das stehen, dann kann ich die rechte Seite
aus Gi folgt Gi stehen lassen, das heißt durch zweimalige Anwendung
habe ich dann eben hergezeigt, dass Gi aus G abgeleitet wurde.
Und damit habe ich wieder ein HI gefunden, das ich in meinen Beweis H
reinschreiben kann und damit habe ich diesen ursprünglichen Beweis
hier oben zusammengestückelt.
Soviel zum Thema Auslagenlogik.
Was Sie jetzt also mitnehmen sollten ist, Auslagenlogische Formeln
haben zum einen die Syntax, die mir einfach definieren, welche Zeichen
darf ich zusammenstückeln aus meinem ursprünglichen Alphabet, um eine
syntaktisch korrekte Formel zu bekommen.
Und durch die Anwendung zum Beispiel dieser Bulschen Formeln kann ich
einer Formel, durch diese Bulschen Funktion kann ich der Formel eine
Bedeutung zuordnen.
Ich kann sie also abbilden auf einen Wert, eine Semantik.
In der Auslagenlogik machen wir das über die Bulschen Funktionen.
Insgesamt könnte man sich natürlich jetzt auch andere Logiken
vorstellen, wo man das anders macht.
Und dann kann ich das Ganze rein strukturieren in das Konzept des
Kalküls, mit dessen Hilfe ich Beweise führen kann, mit dessen Hilfe
ich aus Aktionen, aus Prämissen Formeln ableiten kann.
Das heißt, beweisen kann.
Und dadurch, dass der Modus ponens, die einzige
Schlussfolgerungsformel, die ich habe im Aussagenkalkül, die
Allgemeingültigkeit erhält, ist alles, was ich auch ableite, wenn das,
von wo ich ausgegangen bin, allgemeingültig war, logischerweise dann
auch allgemeingültig.
Und Sie müssen jetzt halt in der Lage sein und üben, mit Bulschen
Funktionen zu rechnen, also so Bulsche Ausdrücke ausrechnen zu können.
Sie müssen in der Lage sein, Formeln zu überprüfen, sind sie
erfüllbar, also einfache Formeln, sind sie erfüllbar, sind sie
allgemeingültig und Sie müssen im Prinzip solche Ableitungen, solche
Beweise durchführen können.
So, damit hätten wir das Kapitel Aussagenlogik abgeschlossen und man
würde jetzt noch übergehen zu dem Kapitel Induktives Vorgehen.
Mein Vorschlag wäre aber, auch wenn wir jetzt ein bisschen früher
fertig sind, dass wir uns das für nächste Woche vorbehalten.