Einen schönen guten Morgen.
Ja, herzlich willkommen.
Heute geht es um die zwei Themen, die Sie sehen.
Also wir haben den ersten Begriff kennengelernt, was nicht direkt nur
mathematisch klingt, wie Relationen, Abbildungen und Mengen, sondern
wir haben jetzt damit angefangen, mit was wirklich in der Informatik
direkten Nutzen, man kann sich vorstellen, dass das direkten Nutzen
hat.
Das ist der Begriff der Wörter.
Nebenbei ist wieder binäre Operation vorgekommen, das ist wieder
Mathematik, aber ja, so ist es halt.
So, und dann hatten Sie noch nebenbei sofort kennengelernt, was ein
Alphabet ist.
Das ist ja eine ähnliche Menge von Zeichen und bitte schon auch nicht
leer.
Und dann mit diesen Zeichen können wir Wörter schreiben, so wie es in
der normalen Sprache auch ist.
Und dann können wir diese Folge von Zeichen eigentlich definieren,
mathematisch gesehen.
Ich habe schon letzte Woche gesagt, wir möchten alles präzise genug
definieren, damit wir mathematische Argumente auf diese Objekte
loslassen können.
Und dann, was Sie machen, ist einfach,
also dieses Fort hat eine bestimmte Länge.
Ich schreibe so viele Zeichen hin und diese Zeichen bekommen dann
gewisse Stellen.
Und dann in den Stellen von 0 bis 10-1 kann ich ein Zeichen schreiben.
Und dann jede von solchen Stellen bekommt ein Zeichen.
Und dann diese Bekommen-Geschichte übersetze ich in mathematische
Denkweise als eine Abbildung.
Und damit das Ganze auch Sinn macht, das muss auch subjektiv sein,
damit ich jedes Zeichen hier zumindest einmal verwende.
Zum Beispiel das Wort GBI, also wir schreiben einfach diese Wörter wie
Zeichen ganz normal nacheinander.
Und gemeint ist aber diese Abbildung, die dahinter steckt.
Das ist auch gerechtfertigt, dass wir etwas sauber definieren und dann
eine kürze Schreibweise dafür haben.
Ich will nicht jetzt für jedes Wort, das ich schreibe, immer noch
sagen, das ist eine Abbildung, das hat so einen Definitionsbereich und
so weiter und so fort, sondern ich habe diese kürze Schreibweise und
wir wissen, ja, dahinter steckt was formal definiert ist, es ist alles
okay.
Und das kann ich aber leider nicht mit einem besonderen Wort machen,
nämlich weil es kein Zeichen enthält.
Also ich kann nicht Zeichen nacheinander schreiben, weil es eben keine
Zeichen zum Schreiben gibt.
Und das haben wir dann mit einem besonderen Sonderzeichen
gekennzeichnet.
Jetzt habe ich Zeichen nacheinander dreimal.
Das haben wir durch dieses Epsilon gekennzeichnet.
Und es ist auch ein interessantes Wort,
nämlich weil sie zuerst eindeutig ist, egal über welches Alphabet ich
rede, das ist zurückzuführen auf solche Eigenschaften hier zum
Beispiel, nicht zum Beispiel, sondern das ist einfach so, also ich
habe eine Abbildung, ich habe als Definitionsbereich die leere Menge,
weil ich keine Zeichen habe, dann habe ich auch keine Stellen, das ist
alles leer.
Und dann muss sie noch subjektiv sein.
Das heißt, diese Menge B muss Elemente enthalten, die die Urbilder
besitzen bezüglich dieser Abbildung.
Und dann kann ich nur die leere Menge wiederhaben.
Und in der letzten Übung haben wir auch gesehen, es gibt nur eine
einzige Abbildung, die die leere Menge auf Faser abbildet.
Das ist wieder die leere Relation, das ist wieder gleich die leere
Menge selber.
Ja, damit kann ich sagen, das ist das leere Wort und es ist egal über
welches Alphabet ich spreche.
Und so wie die leere Menge, das ist nicht nur ein komisches Objekt,
sondern das ist auch nützlich, werden wir nochmal später sehen, warum
das so ist, das taucht auch wieder in verschiedenen Definitionen für
Abbildungen über Wörter auf, das haben Sie bestimmt auch gemerkt.
Dann, wenn ich Wörter habe, ich möchte ja auch Mengen von Wörtern
betrachten, natürlich betrachten wir Mengen von allem Möglichen, ich
schreibe dann A hoch N, wenn ich die Wörter der Länge N meine, über
das Alphabet A.
Und das ergibt sich eigentlich aus der Konkatenation der Wörter, das
kommt jetzt später in einer anderen Folie.
Und wenn ich jetzt die Menge aller Wörter betrachten will, dann kann
ich dieses A hoch Stern nehmen.
Dieses Stern nennt sich klinischer Abschluss, das werden wir noch,
wenn wir von formalen Sprachen zur Rede kommen, noch sehen, wie das
vielleicht ein bisschen genauer definiert ist.
Hier, das ist einfach die Vereinigung über alle A hoch Ns, die ich
habe.
Und insbesondere habe ich das A hoch 0 drin, dann habe ich Wörter der
Länge 0, das heißt, ich habe das leere Wort auch drin in meinem A hoch
Stern.
Und wenn ich jetzt schreiben will, es sei wie ein Wort, dann kann ich
einfach kurz und knapp, wie aus A Stern zum Beispiel, schreiben.
Das ist ganz nützlich, wenn ich zum Beispiel eine Funktion definieren
will, und dann will ich über alle Ws irgendwas definieren, und dann
will ich nicht eine Definition haben, die ein ganzes Paragraph lang
ist.
Es hilft auch, diese Schreibweisen zu haben.
Und interessant hier, also ich habe noch das A hoch Plus, dann lasse
ich das leere Wort weg, dann habe ich alle Wörter der positiven Länge.
Das ist auch nützlich, wenn man das leere Wort ausschließen will.
Und interessant hier ist, das Alphabet war ja ähnlich, nicht leer,
aber ähnlich, und jetzt diese zwei Mengen sind immer unendlich.
Es gibt immer unendlich viele Wörter, egal über welches Alphabet ich
gerade rede.
Zum Beispiel eben das kleinste Alphabet überhaupt, das ist eine Menge
mit einem Zeichen, und ich kann dieses Zeichen beliebig oft
nacheinander schreiben, so kann ich unendlich viele Wörter erzeugen.
Und jetzt können Sie das zum Beispiel vergleichen, mit was ich in
Übung 1, das war nicht die letzte Übung, sondern die letzte Übung
letzten Mittwoch, da haben wir auch gesehen, es gibt diese, habe ich
auch gesprochen, von ähnlichen Mengen von Zahlen, die jetzt mit dieser
unendlichen Vereinigung dann zu den ganzen Zahlen werden, also da gibt
es eine unendliche Menge, und hier, die A hoch N sind eigentlich alle
ähnliche Mengen, also ich habe nur ähnlich viele Möglichkeiten für N
-Zeichen, wenn ich nur ähnlich viele Zeichen habe, aber was rauskommt
aus dieser Vereinigung, ist wieder etwas Unendliches.
Also das ist kein Problem hier.
Können Sie mit dem Argument von Übung 1 vergleichen.
Noch vielleicht eine interessante Bemerkung, ja, ich habe auch Wörter
der Linie 1, dann ist das ein Wort mit einem Zeichen, ich habe auch
wieder Zeichen,
ja, also ich hatte gesagt, wir haben diese Schreibweise für Wörter, wo
wir eigentlich nur die Zeichen schreiben, anstatt die ganze Abbildung
formal zu schreiben, und hier merkt man das Problem.
Kann denn ein Wort oder ein Zeichen gleich sein?
Also formal gesehen, das kann nicht sein.
Also ich hatte ein Element, von dem Alphabet war das X, und dann W war
eine Abbildung, die irgendwie auf diese Elemente von A Zahlen
abbildet, diese Stellen, dann bildet sie die Null auf das X, es ist
aber nicht wieder das X selber, es ist eine Abbildung.
Aber ich meine, hier ist es noch schwer zu unterscheiden, die
Formalität sagt irgendwas, aber intuitiv, wir möchten nicht jetzt
darüber reden, ob wir jetzt Wörter, immer wenn wir ein Zeichen
schreiben, ob gemeint ist, ist es ein Wort der Länge 1, oder ist das
ein Zeichen selber.
Also für praktisches Nutzen hier, dass wir meistens keinen Unterschied
ausmachen.
Im schlimmsten Fall haben wir immer sauber definiert, was zum Beispiel
ein Zeichen und ein Wort ist, zum Beispiel hier das X aus A und das W
aus A Stern, und dann wissen wir, das ist ein Wort, das ist ein
Zeichen.
Und wenn wir jetzt Sachen konkatenieren, Sie haben auch die
Konkatenation gelernt, dann wird es sowieso egal, wenn ich jetzt ein
Wort mit einem Zeichen konkateniere, oder was ich eigentlich mache,
ich konkateniere mit einem Wort der Länge 1, weil ich nur auf Wörter
konkatenieren kann, nicht auf Zeichen selber, aber was sich
herausgibt, ist alles gleich hier für uns, also ist das auch kein
Problem.
Konkatenation, das ist einfach Wörter nacheinander schreiben.
Es gibt auch Leerzeichen, zumindest in den normalen Sprachen.
Es gibt Sprachen, die keine Leerzeichen haben, zum Beispiel Japanisch
ist auch eine, aber Sie können auch Leerzeichen als Zeichen selber
sehen, und dann, wenn Sie ein ganzes Paragraf, zum Beispiel Text
haben, das ist ein einziges Wort für uns.
Jedes Zeichen ist ein Zeichen im Wort, und die Leerzeichen sind eben
auch Zeichen.
Formal kann man das auch präzise genug definieren, was die
Konkatenation macht, wenn ich jetzt die Wörter nacheinander schreibe.
Und der Fakt ist, dass die Längen der Wörter sich addieren.
Also ich hatte ein Wort der Länge m und ein Wort der Länge n, und es
ergibt sich ein Wort der Länge m plus n.
Die Stellen aber von dem...
Also die Stellen von dem W1, die sind einfach wörtlich abgeschrieben.
Das ist das gleiche Bild.
Also wenn ich das i kleiner m war, dann ist das dasselbe Bild wie bei
W1.
Und die Stellen von W2 sind aber um m-Zeichen nach links verschoben.
Nachdem, wie man sieht, nach links verschoben.
Deswegen haben wir dieses i-m in der Definition stehen.
Ja, so kann man allgemein Abbildungen schieben über einen
Definitionsbereich.
Das ist vielleicht hilfreich bei einer bestimmten Teilaufgabe in
Aufgabe 2.2.
Ja, und dann haben Sie auch ein Beispiel unten.
Also von 0 bis 2 habe ich wieder die Zeichen, wie bei dem Wort gbi.
Und wenn ich Übungen nacheinander nachschreibe, dann verschiebt sich
alles.
Bei W2 würde das Zeichen an der Stelle 0 das u sein.
Hier ist es aber an der Stelle 3 gelandet.
Also ich habe diese Länge m von dem W1 darauf addiert.
Dann, ich hatte auch gesagt, dass das leere Wort Y nützlich ist.
Zuerst, weil es ja auch das neutrale Element dieser Kontradination
ist.
So wie bei Addition haben Sie ja die 0.
Und die 0 ist auch, obwohl das in einer gewissen Weise leer ist.
Wir können Objekte zählen.
1, 2, 3.
0 ist aber kein Objekt.
Hier haben Sie auch, was für diese Operation nützlich ist, wie die 0
für die Addition nützlich ist.
Das nennt sich neutrales Element.
Nämlich, wenn ich das leere Wort mit einem Wort konkateniere, dann
kommt wieder dieses Wort W raus.
Die Länge addiert sich.
Das habe ich schon erwähnt in der vorigen Folie.
Sie können auch, wie bei der Multiplikation, also es ist kein Wunder,
dass wir jetzt für die Konkatenation das mit einem Punkt notieren, Sie
können auch Potenzen von Wörtern betrachten.
Zum Beispiel, ich kann das W einmal nacheinander schreiben.
Das ergibt sich dann W hoch N.
Und wenn ich W hoch 0 nehme, dann soll das auch vernünftig definiert
sein.
Und damit sich alles im Exponenten addieren soll, wie bei der
Multiplikation und Potenzieren, wenn ich 2 hoch 0 zum Beispiel nehme,
dann soll 1 kommen.
Warum?
Wenn 2 hoch 0 mit 2 hoch N multipliziert wird, dann ergibt sich 2 hoch
N.
Also 2 hoch 0 ist 1, weil 1 das neutrale Element der Multiplikation
ist.
Und hier das neutrale Element der Konkatenation ist eben das Epsilon.
Deswegen haben wir W hoch 0 das Epsilon definiert.
Wenn ich W habe mit W hoch 0 Konkatenieren, dann soll wieder W
rauskommen, das muss dann Epsilon sein.
Es gibt keine andere Möglichkeit.
Und dann, wenn Sie das potenzieren, was ergibt sich dann für die
Länge?
Dann haben Sie ein Wort, das einmal so lang ist.
Zum Beispiel, wenn Sie dieses Wort quadrieren, dann ergibt sich ein
Wort mit doppelter Länge.
Und wenn Sie dieses Wort, dann die Länge des Wortes, viele Male
nehmen, dann haben Sie die Wortlänge quadriert.
Es ist auch vernünftig definiert, ich habe ein Wort schon gegeben,
dann hat dieses Wort eine Länge.
Deswegen kann ich W hoch Länge von W schreiben, weil die Länge fest
definiert ist.
Jetzt die mathematische Seite.
Diese Konkatenation ist eine binäre Operation auf die Menge der
Wörter.
Was heißt das?
Das ist eine Abbildung, das bekommt zwei Argumente
und das bildet dann die zwei Wörter auf wieder ein Wort ab.
Das ist das, was sie macht, das ist einfach so.
Und es gibt gewisse Eigenschaften, die diese binäre Operation erfüllen
können, wieder aus der Mathematik natürlich, zum Beispiel, bei der
Addition haben Sie die Kommutativität, also Sie können die Operanden
vertauschen und das Ergebnis bleibt dasselbe.
Und die Addition ist ja kommutativ, das Subtraieren ist aber nicht,
also 5 minus 2 ist 3, aber andersherum ergibt sich minus 3, was nicht
das gleiche ist.
Die Konkatenation ist aber auch ebenfalls nicht kommutativ.
Also wenn Sie ein Wort schreiben, dann das andere, es ist nicht
unbedingt dasselbe Wort, wenn Sie jetzt dieses andere Wort vorne
schreiben.
Es ergibt sich etwas anderes.
Die andere Eigenschaft von binären Operationen ist die Assoziativität.
Es gibt noch eine dritte wichtige Eigenschaft, aber das kommt jetzt in
einem späteren Kapitel.
Die Assoziativität ist ein bisschen...
Was das eigentlich sagt, ist, dass ich Klammern bei einem Ausdruck
weglassen kann.
Es ist egal, in welchen Reihenfolge ich jetzt einen Ausdruck mit
dieser binären Operation bearbeite.
Das ist zum Beispiel mit Addition so, das ist mit Multiplikation auch
so.
Mit dem Subtrahieren ist das aber nicht so.
Es ist doch wichtig, wo ich die Klammern setze.
Wenn ich zuerst zwei von vier subtrahiere und dann eins, dann ist das
ein anderes Ergebnis, als wenn ich es andersrum mache.
Bei der Konkatenation ist die aber assoziativ.
Es ist egal, wo ich die Klammern setze für das Nacheinanderschreiben.
Es werden am Ende alle Wörter einfach nacheinander geschrieben.
Und jetzt haben Sie Beispiele für binäre Operationen, die assoziativ
und kommutativ sind, zum Beispiel das Plus.
Einige, die weder noch sind, zum Beispiel das Minus.
Und die Konkatenation ist eines, aber nicht das andere.
Ein bisschen besonders.
Ich habe noch ein paar Beispiele zu binären Operationen jetzt mit
Mengen.
Sie haben zum Beispiel die Vereinigung und Durchschnitt usw.
können wir alles als binäre Operationen ansehen.
Das sind wieder Abbildungen, die zwei Mengen als Argumente bekommen
und diese zwei Mengen auf einer Menge abbilden.
Und die Vereinigung und den Durchschnitt sind kommutativ.
Sie sind beide kommutativ und assoziativ.
Es ist egal, in welche Reihenfolge ich jetzt die Mengen vereinige.
Es ist egal, in welche Reihenfolge ich die Klammern bei einer längeren
Vereinigung setze.
Es gibt natürlich auch Operationen mit Mengen, die weder noch sind,
zum Beispiel das im Allgemeinen zumindest, diese Mengendifferenz.
Also wenn ich die leere Menge von einer Menge B wegnehme, dann bleibt
B immer noch, weil ich keine Elemente weggenommen habe.
Wenn ich aber mit der leeren Menge anfange, dann muss es leer sein,
was rauskommt.
Assoziativ, da gibt es auch ein Beispiel unten.
Aber ich habe eigentlich etwas hier vorausgesetzt, das geht nur, wenn
das B eigentlich nicht die leere Menge selber ist.
Also wenn ich für das B nur die leere Menge als Möglichkeit habe, dann
ist das alles doch gleich.
Also die leere Menge ist B und B ist die leere Menge, da gibt es
keinen Widerspruch.
Dann gibt es diesen Randfall.
Also wenn die Basismenge hier, das A, leer ist, dann haben sie nur
eine Menge, die rauskommen soll.
Sie können nur mit der leeren Menge was machen und dann gibt es nur
eine binäre Operation darauf und sie muss dann automatisch komputativ
und assoziativ sein.
Das ist gleich, jede mögliche Operation, die für eine Mundur steht und
Mengendifferenz, das ist alles gleich, wenn sie nur die leere Menge
haben.
Jetzt kommt immer nur wieder die leere Menge raus.
Randfall.
Ich habe noch ein kleines Beispiel am Ende.
Ich weiß nicht, wie das Zeitalter sieht.
Schauen wir einfach mal.
Ich habe Wörter definieren.
Wir können auch Abbildungen auf Wörtern betrachten.
Vielleicht will ich jetzt diese Wörter umspiegeln, also umdrehen.
Wie kann ich jetzt das definieren, sauber, mathematisch präzise?
Ich kann nicht jetzt einfach schreiben, das Wort sei einfach
gespiegelt geschrieben.
Ich muss das irgendwie präzise definieren.
Sie können mit dem Indizis was machen.
Sie können zum Beispiel mit einem Wort mit beliebiger Länge anfangen
und dann sagen, das erste Zeichen wird dann das letzte Zeichen sein.
Da müssen Sie sich Gedanken machen, wie die Indizis aussehen müssen,
damit das alles klappt.
Es gibt auch eine andere einfache Möglichkeit.
Sie können das alles induktiv definieren.
Das heißt, ich kann einen Basisfall haben, zum Beispiel ein Zeichen,
ein Wort Länge 1 muss wieder dieses Wort selber sein, gespiegelt
bleibt sie einfach dasselbe.
Und wenn ich jetzt ein Wort mit mehreren Zeichen habe, dann kann ich
dieses Wort unterteilen.
Also ich habe ein Wort W in beliebiger Länge vorne und ein Zeichen am
Ende X und dann nehme ich dieses Zeichen und setze das vorne.
Da habe ich sozusagen Schritt für Schritt beschrieben, wie man von
einem Wort ausgehend zu diesem Spiegelbild kommt.
Ich fange einfach mit dem Wort an, dann nehme ich das rechte Zeichen,
setze es vorne, dann mache ich weiter mit diesem Wort, das ich da
vorne war, dieses W.
Das nennt man dann Rekursion in der Informatik, wenn man das so macht.
Und diese Definitionsart ist eigentlich interessant, weil sie können
zum Beispiel induktive Beweise darauf gut verwenden.
Das haben sie in der vollständigen Induktion.
Das kommt auch in der nächsten Übung.
Da bringe ich noch ein Beispiel, warum diese Art von Definition gut
damit zusammenpasst.
Und das sind ganz einfache Beweise, die gar nicht sind, ganz
übersichtlich.
Und dann muss ich auch mir keine Gedanken machen über Indizis und so
weiter und so fort.
Natürlich habe ich noch vergessen, das leere Wort muss noch ein Bild
haben und wenn ich kein Zeichen zum Umdrehen habe, dann muss ich auch
wieder nichts umdrehen, deswegen bleibt das alles gleich.
Dann kann ich diese Abbildung wie folgt berechnen.
Ich fange mit dem Wort an, dann nehme ich das letzte Zeichen, setze
sich vorne und so weiter und so fort, sich das ganze Wort umdrehen.
Dann können sie auch das vielleicht mit einer binären Operation
mitdefinieren.
Sie nehmen zum Beispiel zwei Wörter und das erste schreiben sie ab und
das andere drehen sie um.
Einfach so als Beispiel kann das komputativ sein.
Es kommt darauf an, welche Wörter ich habe.
Im Allgemeinen, wenn ich zwei Zeichen oder mehr habe, dann wird das
nicht komputativ sein, weil mein Gemein ist dieses Wort W2 umgedreht
und nicht dasselbe Wort.
Und dann, wenn sie noch ungleich W1 ist, dann geht das alles kaputt
sozusagen.
Man kann sich Beispiele überlegen, wenn ich mindestens zwei Zeichen
habe.
Und associativ, das kann auch nicht sein.
Wenn ich die Klammern andersrum setze, dann werde ich verschiedene
Wörter umdrehen und an anderen Stellen setzen.
Deswegen, das klappt auch nicht.
Das wäre es dann für die Übung.
Ich bedanke mich für die Aufmerksamkeit und wünsche ich noch eine
schöne Vorlesung.
Ja, schönen guten Tag.
Wir sind in dem Kapitel.
Da geht es um Aussagenlogik Das machen wir heute nicht ganz fertig,
aber so weit, wie ich kommen will und ein kleines Stückchen schieben
wir und Dann kommen wir zu vollständiger Induktion, die Herr Modany
gerade schon angesprochen hat.
Also was sind aussagenlogische Formeln?
Das hatten wir irgendwie so induktiv definiert.
Also erstens, es gibt Aussagevariablen.
Dann schreiben wir immer sowas wie groß P, groß Q, groß R oder sowas
oder P1, P2, P3, P4.
Wenn man eine solche Aussagevariable hinschreibt, ist das eine
aussagenlogische Formel.
Und dann darf man aus kleineren Formeln größere zusammensetzen, indem
man einfach zum Beispiel eine Formel hinschreibt und noch so ein
Negationszeichen davor setzt und runde Klammern außenrum erst mal oder
zwei Formeln hinschreibt und dazwischen so ein logisches Und-Zeichen
oder ein Oder-Zeichen oder so ein Implikationspfeil und runde Klammern
außenrum.
Und dann machen wir noch eine kleine Abkürzung, so ein Doppelpfeil für
Implikation in der einen Richtung und Implikation in der anderen
Richtung.
So sind die Dinger definiert und das sind erst mal syntaktische
Gebilde, die bedeuten gar nichts.
Wir haben gesagt, also solche Zeichenfolgen, wie man sie hier auf der
Folie sieht, die sind legal.
Das sind per Definition im Aussagen logische Formeln und das war's.
Das ist noch nicht interessant.
Also worum es einem ja dann vermutlich geht, wenn es um Aussagenlogik
geht, ist irgendwie Dinge auszudrücken über wahre und falsche
Aussagen.
So, da kommen wir jetzt gleich hin.
Noch kurz mal zur Erinnerung, also die vielen Klammern, also im
Zweifelsfalle sind sie notwendig in manchen Fällen, aber ansonsten, um
weniger tippen zu müssen und tatsächlich mit weniger Klammern doch
vielleicht sogar ein bisschen besser erfassen zu können, definieren
wir so ein paar Regeln, dass man Klammern sparen darf.
Und wenn da also so mehrere Aussage variablen durch Konjektive
verknüpft irgendwo stehen, wie hier in der letzten Zeile, dann muss
man eben, wenn man rekonstruieren will, wo gehören die Klammern
eigentlich hin, eben beachten, dass das Negationszeichen am stärksten
bindet.
Also zum Beispiel dieses Negationszeichen vor dem Q in der Formel ohne
Klammern.
Das bezieht sich wirklich nur auf das Q.
Also wenn man dann anfängt, Klammern wieder einzuführen, dann muss man
um das nicht Q erst mal Klammern machen.
Nicht bindet am stärksten und am zweitstärksten oder Implikation und
dieser Pfeil, den wir nur als Abkürzung eingeführt haben.
So und jetzt zu Wahrheitswerten.
Und bevor wir jetzt anfangen, dann irgendwie Wahrheitswerte in
aussagenlogischen Formeln einzusetzen oder so was in Anführungszeichen
kurz so ein paar allgemeine Bemerkungen.
Es gab Herrn im so welches Jahrhundert war das?
Das neunzehnte Jahrhundert?
Ja, Herrn Buhl, der unter anderem dieses Buch geschrieben hat, dessen
Titel hier steht.
Das lese ich jetzt nicht alles vor.
Da taucht also Logik auf als Wort.
Auch noch Wahrscheinlichkeiten.
Damit beschäftigen wir uns hier jetzt gerade überhaupt nicht.
Also in dem Buch steht natürlich mehr.
Wo es ihm darum ging, eben so ein bisschen das, was man so
umgangssprachlich mit wahr und falsch macht, so Händewedel
rumhantiert, so ein bisschen zu formalisieren.
Und deswegen heißen die wohl die Funktionen, mit denen man sie zu tun
hat, dann auch gerne mal Buhl Funktionen.
Und Grundlage ist, dass man sich vorstellt, man hat zwei so
Wahrheitswerte, wahr und falsch.
Ich schreibe dafür kleines W und kleines F.
Sie können auch T und F für True und False nehmen oder 1 und 0.
Das macht man dann immer mal gerne, wie es einem gerade so am besten
passt.
Und diese Menge, die diese beiden Wahrheitswerte enthält, die nenne
ich groß B, damit ich nicht so viel schreiben muss.
Und per Definition eine Buhl Funktion, das ist einfach eine Abbildung,
die nimmt als Argument K solche Wahrheitswerte und liefert als
Funktionswert einen neuen solchen Wert.
Könnte man natürlich noch verallgemeinern.
Der Funktionswert sind auch wieder mehrere Werte, aber das hilft uns
jetzt ja auch nicht weiter.
Naja, und hier sind ein paar Beispiele.
Also hier habe ich jetzt mal in so einer Tabelle für zwei Variablen,
also für die Argumente von einer Buhl Funktion.
X1 und X2 habe ich die mal genannt, ist ja ganz egal.
Hier so hingeschrieben, welche Kombinationen können denn passieren?
Welchen Wert hat X1?
Welchen Wert hat X2?
Für jede Variable, wir haben nur zwei Werte.
Also für jedes Paar X1, X2 haben wir dann vier Werte.
Beide falsch, nur X1 falsch, nur X2 falsch oder beide wahr.
Und also sozusagen hier die ersten beiden Spalten geben Ihnen alle
Möglichkeiten, welches Paar an Argumenten stecken Sie in eine Buhl
Funktion mit zwei Variablen rein.
Und dann kann man natürlich in einer Spalte für eine Funktion dann
eben für jede Kombination hinschreiben, was ist denn dann der
Funktionswert?
Und ja, als erstes habe ich hier meine Buhl Funktion hingeschrieben in
der dritten Spalte, die hat nur ein Argument.
Also X2 kommt da gar nicht vor und dann na ja, also immer in den
beiden Zeilen, wo X1 den gleichen Wert hat, kommt natürlich auch der
gleiche Funktionswert raus.
Und die Buhl Funktion, die ich B mit Index, dieses Negationszeichen
geschrieben habe, erst mal dreht immer einfach den Wahrheitswert um,
als wenn das Argument falsch ist, der Funktionswert war und umgekehrt.
So und dann gibt es eben so diverse Funktionen.
Sie können ja schon mal anfangen, darüber nachzudenken, wie viele mit
zwei Variablen.
Und dann gibt es eine Buhl Funktion, für die schreibe ich erst mal.
Wir machen dann gleich noch Abkürzungen, aber um klarzumachen, was
hier abgeht, schreiben wir für die Funktion erst mal B mit Index und
und die Definition dieser Buhl Funktion soll sein, die ist nur dann
wahr, genau dann, wenn beide Argumente wahr sind, hier in der letzten
Zeile.
In allen anderen Fällen, wenn mindestens ein Argument falsch ist, ist
der Funktionswert auch falsch.
Und die Buhl Funktion fürs Oder ist dann und nur dann falsch, wenn
beide Argumente falsch sind.
Und wenn mindestens ein Argument wahr ist, ist der Funktionswert wahr.
Das haben Sie vielleicht auch schon mal irgendwo gesehen.
Und für die Buhl Funktion B Index Pfeil ist einfach die Definition.
Diese Funktion liefert in genau einem Fall den Funktionswert falsch
und das passiert genau dann, wenn das erste Argument wahr und das
zweite falsch ist.
Also wenn X1 wahr ist und X2 falsch, dann die Funktion liefert falsch
und in allen anderen drei Fällen liefert sie wahr.
Also wenn das erste Argument falsch ist, die Funktion liefert wahr.
Und man kann es auch so sagen, wenn das zweite Argument wahr ist, hier
in der zweiten und vierten Zeile, der Funktionswert ist auch wahr und
nur in dem einen Fall eben falsch.
Also jede Spalte haben Sie dann auf diese Art und Weise irgendwie die
ein oder andere Buhl Funktion festgelegt.
Und beim und kommt also wahr nur dann raus, wenn beide Argumente wahr
sind und beim oder, wenn mindestens eins war, ist.
Gut.
Jetzt diverse Leute schreiben für diese Funktionen irgendwelche
anderen Abkürzungen hin.
Also was noch relativ harmlos ist, z.B.
B und von X und Y schreibt man öfter mal sieht man X und Y auch wieder
so ein Dach, das so ähnlich aussieht wie das Konnektiv, das wir in
Aussagen logischen Variablen erlaubt haben.
Analog fürs oder und fürs nicht auch für den Implikationsfall eine
Infix Schreibweise.
Habe ich auch schon mal gesehen, aber das lassen wir mal einfach weg.
So und dann kann es Ihnen auch noch passieren, dass Sie was sehen.
Da steht statt eines uns ein Multiplikation Punkt und statt eines
oders ein Plus.
Vorsicht.
Und bei Negationen machen die dann manchmal so ein Querstrich über
eine Variable.
Und die Leute, die das schreiben, benutzen dann meistens auch 0 und 1
als.
Wahrheitswerte in Anführungszeichen und passen sie auf also das
Produkt, das liefert Ihnen genau dann eine 1, wenn beide Argumente 1
sind, so wie das mit dem war gerade definiert war.
Aber das Plus müssen Sie ein bisschen großzügig interpretieren.
Also 1 plus 1 ist dann auch nur 1.
Gut.
Und ich also tendenziell eher schreibe ich irgendwie Buche Funktion
mit noch im Index, um welches Konnektiv geht es und dann zum Teil auch
noch das, was hier in der mittleren Spalte angedeutet ist.
Das mit Plus und Mal, das lasse ich lieber weg.
So das letzte Mal.
Nach der Vorlesung hat schon jemand gefragt, wie ist das denn
eigentlich?
Wie kann ich mir klarmachen?
Aus welchen einfachen, also sinngemäß aus welchen einfachen Funktionen
kann ich kompliziertere zusammensetzen?
Wie kann ich verstehen, dass womöglich gewisse Funktionen ausreichen?
Einfache, wenige einfache, eine oder zwei oder so, um alle Funktionen
irgendwie hinzuschreiben?
Naja, das machen wir jetzt hier noch nicht im Detail, aber dass Sie
schon mal so ein bisschen was in der Richtung sehen.
Also stellen Sie sich vor, wir haben zwei Variablen X und Y.
Und hier wieder in den ersten beiden Spalten alle Kombinationen,
welche Funktionen, welche Wahrheitswerte sind für X und Y möglich.
Und dann habe ich erst mal für nicht X die Spalte hingeschrieben, dass
also genau, wenn hier vorne bei X ein F steht, steht hier ein W und
umgekehrt.
Vorne W, hinten F.
Und dann mal und dann benutze ich jetzt nicht mehr dieses B unten
nicht, sondern schreibe einfach mal nicht X hingeschrieben.
Und dann diese nächst kompliziertere bulsche Funktion nicht X oder Y.
Wie geht das?
Also das oder ja, da kommt als Funktionswert war raus, wenn das erste
Argument wahr ist.
Das ist also hier in den ersten beiden Zeilen, wo nicht X wahr ist.
Und es kommt wahr aus, wenn Y wahr ist.
Das ist in der zweiten und in der vierten Zeile.
Und der einzige Fall, wo hier falsch rauskommt, ist dann, wenn nicht X
falsch ist und Y falsch ist.
Und wenn Sie also hier haben Sie nicht X oder Y, das ist irgendwie so
ein Ausdruck aus burschen Funktionen.
Gibt diese Tabelle von Funktionswerten wie von oben nach unten WWFW,
wenn Sie die Paare der Argumente in der gleichen Reihenfolge
hinschreiben, wie ich es gemacht habe.
Und wenn Sie das jetzt mal vergleichen mit der burschen Funktion, so
wie sie gerade definiert war für die Implikationen, da war auch, hieß
es auch, naja, bursche Funktion für Implikationen, für X und Y ist
wahr, wenn X falsch ist, hier in den beiden Zeilen und wahr, wenn Y
wahr ist, in Zeile zwei und vier.
Und da sehen Sie, diese Spalte von Funktionswerten für die
verschiedenen Möglichkeiten ist genau die gleiche wie bei nicht X oder
Y.
Das heißt, Sie können diese bursche Funktion für Implikationen auch
äquivalent so hinschreiben, indem Sie nur nicht und oder benutzen.
Das ist genau so, wie Sie, was weiß ich, so eine Funktion zweimal X
auch einfach hinschreiben können als X plus X.
Sie brauchen in dem einfachen Fall keine Multiplikation.
So, also die gleiche bursche Funktion kann man unter Umständen
unterschiedlich hinschreiben, sozusagen.
Gut.
Und ich habe jetzt hier genau dieses Beispiel genommen, weil einem das
vielleicht noch mal ein bisschen hilft, zu verstehen, warum die
bursche Funktion für die Implikation gerade so definiert ist, wie sie
definiert ist und nicht irgendwie anders.
Also was einen vielleicht ein bisschen am Anfang wundert, insbesondere
ist, dass man sagt, die Implikation ist wahr, wenn die Voraussetzung,
dass X falsch ist.
Wenn 0 gleich 1, dann irgendetwas ist eine wahre Aussage.
Immer.
Egal, was das etwas ist.
Ach so, ja, also da kann man hier die Fälle alle durchgehen.
Na gut.
Ja, also das sind bursche Funktionen.
Einfach sie stecken ein paar Wahrheitswerte rein, es kommt ein
Wahrheitswert raus.
Und wenn Sie n Variablen haben, dann haben Sie zwei hoch n
Möglichkeiten, welche n Tupel von Argumenten Sie reinstecken und
bursche Funktionen.
Da können Sie sich jetzt für verschiedene bursche Funktionen für jedes
von den zwei hoch n n Tupeln unabhängig aussuchen.
Was soll der Wahrheitswert sein?
Da gibt es viele bursche Funktionen mit n Veränderlichen.
Gut.
Ja, und solche burschen Funktionen, die nehmen wir jetzt im
Wesentlichen, um festzulegen, was bedeuten denn so aussagenlogische
Formen, so syntaktische Gebilde, Klammer auf P, Pfeil, Q, Klammer zu.
So.
Also das Ziel ist jetzt, jeder aussagenlogischen Formel zuzuordnen als
Bedeutung eine bursche Funktion.
Wie geht das?
Ach so.
Ja, also das ist erst mal noch relativ harmlos alles.
Und das trete ich ein bisschen breit und benutze ein bisschen viel an
Begriffen, die zwei, drei hätte man sich vielleicht sparen können,
weil genau das gleiche Programm, das wir hier jetzt anfangen
durchzuziehen, wir in einem späteren Kapitel im Zusammenhang mit
Prädikaten Logik nochmal durchziehen werden.
Aber da ist alles ja doch ein bisschen komplizierter, aufwendiger.
Und deswegen ist es sinnvoll, wenn man hier das schon mal im einfachen
Fall sieht und denkt Ja, ist ja alles gar nicht so schwierig.
Und dann geht es auch etwas entspannter an die Prädikaten Logik ran.
Ja, also was macht man hier?
Also stellen Sie sich vor, wir haben irgendeine Menge V von
Aussagevariablen und wir interessieren uns jetzt dann für die
aussagenlogischen Formen, in denen diese Aussagevariablen vorkommen
können.
Dann wollen wir eine Abbildung, die jeder Aussagevariablen in Groß V
einen Wahrheitswert zuordnet, eine Interpretation nennen.
Also Sie legen dann sowas fest wie P ist wahr, Q ist falsch, S ist
auch falsch oder so.
Und stellen Sie sich ruhig vor, V ist eine endliche Menge von
Aussagevariablen.
Wir haben nur zwei oder drei oder 17 oder so.
Also jede Abbildung, die jede Aussagevariablen einen Wahrheitswert
zuordnet, wollen wir eine Interpretation nennen, also so eine
Abbildung Groß I.
Und das heißt, anders gesagt, jede Interpretation ist Element dieser
Menge B hoch V aller Interpretationen, Menge aller Abbildungen von V
in B.
Und wenn Sie zum Beispiel drei Aussagevariablen P1, P2, P3 haben, wenn
Sie da eben jetzt dann systematisch alle Kombinationen, welche Werte
sind da möglich, hinschreiben untereinander, dann haben Sie sozusagen
durch jede Zeile eine Interpretation für diese Aussagevariablen
festgelegt.
Also erste Zeile P1 ist falsch, P2 ist falsch, P3 ist falsch.
Drittletzte Zeile P1 ist wahr, P2 ist falsch, P3 ist wahr.
Hier stehen alle möglichen Interpretationen.
Für diese drei Variablen kein Hexenwerk.
Das ist auch gerade der Plan, dass das alles ganz harmlos ist.
Aber also solche Dinge nennen wir Interpretationen, eine Festlegung
für jede Variable, was ist ihr Wahrheitswert?
So und jetzt, na ja, Aussagevariablen waren die einfachsten
aussagenlogischen Formeln und größere Formeln haben wir definiert,
indem wir sie aus kleineren zusammengesetzt haben, syntaktisch,
Formeln hinschreiben, Konnektiv dazwischen, Klammern außenrum machen.
Und so wie man also so nach und nach sich bei den syntaktischen
Gebilden von kleineren zu größeren vorwärts gehangelt hat, so hangelt
man sich jetzt auch bei der Definition für was ist die Bedeutung, der
Wahrheitswert einer Formel eben weiter, fängt an bei den Variablen.
Also angenommen, man hat jetzt irgendeine Interpretation für
aussagenlogische Variablen, dann definiert man jetzt, was es bedeuten
soll, sozusagen, wenn Sie irgendeine beliebig komplizierte, aber halt
endlich große aussagenlogische Formel F haben, die auszuwerten mit
dieser Interpretation I und dafür schreiben wir dann mal I von F.
Und das gibt dann also.
Am Ende auch wieder immer einen Wahrheitswert, null, wahr oder falsch.
Naja, und da steht jetzt hier erst mal wieder was, dass das alles
überhaupt sinnvoll ist.
Darauf kommen wir dann in einer späteren Vorlesung nochmal zurück.
Also wie wertet man eine aussagenlogische Formel aus, wenn man eine
Interpretation hat?
Einfachster Fall.
Die aussagenlogische Formel ist einfach eine Aussagevariable.
Dann guckt man einfach in der Interpretation nach.
Was legt die denn fest für diese aussagenlogische Variable?
Also die Auswertung einer Variable X ist einfach das, was die
Interpretation sagt.
I von X ist wahr oder falsch, was auch immer.
So, wenn es eine kompliziertere Formel ist, dann gibt es vier
Möglichkeiten, wie die aufgebaut ist.
Negation von einer kleineren Formel oder das und von zwei kleineren
Formeln oder das oder von zwei kleineren Formeln oder so eine
Implikation aus zwei kleineren Formeln.
Und hier steht, was man tut.
Auswertung einer Formel, die von der Bauart ist.
Negation von irgendetwas.
Da wertet man irgendeiner Formel G.
Da wertet man innen sozusagen erst mal die Formel G, die ist kleiner
als nicht G, weniger Zeichen, wertet die aus.
Und das, was da als Wahrheitswert rauskommt, das steckt man noch in
die Buhlsche Funktion, die es genau umdreht, die das wahr falsch macht
und das falsch war.
Und Auswertung von der Formel der Form G und H, da wenden Sie die
Buhlsche Funktion fürs logische Und an auf die Ergebnisse der
Auswertungen von G und H.
Analog fürs oder und analog für Implikationen.
Deswegen habe ich die Funktionen so genannt, weil man die jeweils in
einem entsprechenden Fall anwendet.
Sie können natürlich auch die hier mit Infix Notationen die Buhlsche
Funktionen hinschreiben.
Das ist genau das Gleiche.
Also zum Beispiel hier mittlere Zeile Auswertung von G und H ist
Auswertung von G.
Buhlsche Und Funktion mit Auswertung von H.
Also das sieht jetzt sehr schön aus, passt alles schön zusammen.
Gleichartige Struktur.
Und auf beiden Seiten steht ein Dach sozusagen, so ein Und-Ding.
Und man hat das natürlich alles so gewählt, damit das so schön
aussieht und plausibel aussieht.
Aber beachten Sie bitte meinetwegen hier in der rechten Spalte, in der
mittleren Zeile.
Also auf der linken Seite dieses Dach, das ist so ein Symbol aus dem
Alphabet, dessen wir uns bedienen, wenn wir Aussagen logische Formeln
zusammenbauen.
Und diese Symbole mache ich ja immer einfach hier noch blau.
Also einfach so ein syntaktisches Gebilde bedeutet gar nichts.
Und auf der rechten Seite dieses Dach, das ist die Buhlsche Funktion,
die zwei Wahrheitswerte nimmt und einen neuen liefert, und zwar genau
dann wahr, wenn beide Argumente wahr sind.
Also das sind verschiedene Dächer links und rechts.
So, also so wertet man, wenn man eine Interpretation hat, wenn man
weiß, für jede Aussagenvariable, was ist die Wahrheitswerte?
Wie kriegt man raus, was die ganze Formel als Wahrheitswert liefert?
Behauptung, an dieser Stelle behaupte ich das einfach nur, teile es
Ihnen mit.
Durch diese fünf Zeilen wird tatsächlich vollständig definiert,
vollständig, widerspruchsfrei, richtig sauber.
Diese Abbildung, weil i.
Also gegeben, eine Menge von Aussagevariablen, eine Interpretation,
diese Abbildung, weil i, Formeln auswerten in dieser Interpretation,
wird durch diese fünf Zeilen eindeutig rastrein definiert.
Dass das so ist, kann man auch noch beweisen.
Aber noch nicht jetzt.
Also das ist auch kein Hexenwerk.
Wenn man es ein paar mal an zwei Beispielformeln gemacht hat, merkt
man ja, dass Offensichtliches klappt immer.
Aber eigentlich muss man darüber nachdenken.
Ja, und deswegen irgendwann tun wir das nochmal kurz.
So ein einfaches Beispiel, also nehmen Sie eine Interpretation, wo
meinetwegen die Variable P wahr ist und die Variable Q falsch.
Und weil wir keine anderen Aussagevariablen haben, können wir uns auch
vorstellen, für andere ist gar nichts festgelegt.
Wir haben nur diese beiden in unserer Menge Groß V.
Und wenn Sie dann auswerten wollen, die Formel nicht P und Q, dann
sagt die Definition, wenn das so eine Negation von etwas ist, dann
muss man die Negationsfunktion anwenden auf die Auswertung von P und
Q.
Auswertung von P und Q, da sagt die Definition, ich gehe nochmal
zurück.
Hier stehen nochmal diese Definitionen.
Also für uns dann irgendwie komponentenweise, also Auswertung von P
und Q ist Auswertung von P und Auswertung von Q und Bullisches Und
drauf angewendet.
Und wie wertet man einzelne Aussagevariablen aus?
Man guckt einfach in der Interpretation nach.
Welche Werte haben Sie denn?
Und P ist wahr, Q ist falsch und dann logisches Und von wahr und
falsch ist falsch und Negation von falsch ist wahr.
Fertig.
Und da Formeln nur mit und oder nicht Implikationen zusammengebaut
sein können, diese fünf Zeilen hier spezifizieren wirklich komplett,
was passiert, egal, was die Interpretation ist.
Gut.
Und so kann man das mit jeder Formel und jeder Interpretation machen.
Und das heißt also, sozusagen, wenn Sie eine Formel haben, eine Formel
liegt Ihnen jetzt fest, für jede Interpretation, was ist der
zugehörige Wahrheitswert für die ganze Formel?
Und ach so, hier habe ich das jetzt noch mal mit den anderen Dingern
hingeschrieben.
Naja, also nicht von Interpretation von P und Interpretation von Q,
nicht W und F, nicht F, W, ja.
Das ist genau das Gleiche, ja, nur andere Notationen für die gleiche
bursche Funktion, sonst ist da nichts.
Und wenn Sie es machen müssen, nehmen Sie, was Ihnen besser gefällt.
Also ist mir im Prinzip egal, ja.
Na ja, und jetzt will man halt vielleicht nicht nur für eine, sondern
für alle Interpretationen wissen, was macht die Formel?
Also wenn ich für jede Interpretation, die plausibel ist, wenn ich die
Formel auswerte, was kommt raus?
Da macht man dann halt immer so große Tabellen, ja, vorne in den
ersten Spalten die möglichen Interpretationen für die
Aussagewahrhabenden, die vorkommen.
Also hier P und Q, beide falsch, falsch, wahr, wahr, falsch, wahr,
wahr.
Und dann vielleicht für irgendwelche Bausteine, die in der
Gesamtformel vorkommen.
Irgendwie, was ist das?
Also nicht P ist dann, wenn P falsch, falsch, wahr, wahr ist.
Nicht P ist wahr, wahr, falsch, falsch.
Nicht P oder nicht, also für nicht Q habe ich es auch noch mal
hingeschrieben.
Nicht P oder nicht Q gibt dann, da sehen Sie wahr, wahr, wahr und nur
am Ende falsch.
P und Q gibt falsch, falsch, falsch, wahr.
Und die Negation davon ist auch wieder wahr, wahr, wahr, falsch.
Und wenn Sie sich da jetzt die allerletzte Spalte und die dritte von
rechts angucken, dann sehen Sie in den Spalten also hier hinten für
Negationen von P und Q und hier vorne für Negation von P oder Negation
von Q.
Das sind syntaktisch verschiedene Aussagen, logische Formeln.
In der einen Formel kommt nur ein Negationszeichen vor, in der anderen
kommen zwei Negationszeichen vor.
Das sind verschiedene Aussagen, logische Formeln.
Aber wenn Sie sich angucken, wenn man die interpretiert, egal welche
Interpretation man nimmt, bei beiden Formeln kommt immer das Gleiche
raus.
Also man kann durchaus verschiedene Formeln haben und auch ganz kurze
und ganz lange, beliebig lange im Zweifelsfall.
Die sehen ganz unterschiedlich aus, aber egal wie Sie es
interpretieren, der Funktionswert, also der Wahrheitswert am Ende bei
der Auswertung ist immer der gleiche.
So was gibt es.
Und wenn zwei Formeln G und H diese Eigenschaft haben, also in jeder
Interpretation Auswertung in der einen Formel gibt immer den gleichen
Funktionswert wie Auswertung der anderen Formel.
Wenn das für jede Interpretation gilt, dann wollen wir sagen, die
Formeln G und H sind äquivalent und schreiben so G und H mit so drei
Strichen dazwischen.
Und das ist also eine Aussage, also da geht es um Wahrheitswerte, um
Interpretation.
Das ist was Semantisches, sozusagen.
Was bedeuten die beiden Formeln?
Für alle Interpretationen das Gleiche.
Die heißen äquivalent.
Obwohl sie womöglich syntaktisch ganz unterschiedlich aussehen.
Eine mit wenig Negationszeichen, eine mit vielen und viele Klammern,
wenig Klammern, was auch immer.
Also dass die Formeln nicht P oder nicht Q und nicht P und Q
äquivalent sind, das war gerade hier auf der Folie vorher hier, die
beiden Spalten in jeder Interpretation.
Es kommt das Gleiche raus.
Die beiden sind äquivalent.
Sie können das Spielchen auch zum Beispiel für nicht nicht P und P
machen.
Egal wie sie P interpretieren bei beiden, es kommt immer das Gleiche
raus.
Und hier das dritte Beispiel, das ist jetzt noch mal ein das, was ich
vorhin schon mal angedeutet habe.
Wenn Sie die Formel P Pfeil Q angucken und die Formel nicht P oder Q,
dann malen Sie sich für die beiden Formeln hin, also für jede
Interpretation.
Was gibt die Auswertung?
Dann stellen Sie fest, da kommt immer das Gleiche raus.
Wahr, wahr, falsch, wahr.
Wenn Sie die Interpretationen in der Reihenfolge hinschreiben, wie ich
es immer gemacht habe gerade.
Und also die Behauptung ist, so eine Implikation aus P Pfeil Q ist
genau dann wahr, wenn nicht P oder Q wahr ist, das heißt genau dann,
wenn P falsch ist oder Q wahr.
Und das ist die Stelle, die wahrscheinlich am ehesten noch etwas
gewöhnungsbedürftig ist.
Aber das macht man so und es hat sich einfach bewährt in ein paar
tausend Jahren.
Das macht man einfach weiter so.
Aber wenn man es noch mal ein bisschen anders anguckt, kann man auch
noch ein bisschen ein Gefühl dafür kriegen, warum das vielleicht
schlau ist.
Also die Behauptung ist, die Implikation P Pfeil Q ist wahr, wenn P
falsch ist oder Q wahr.
Warum soll das so sein?
Na ja, versuchen Sie mal, wenn Sie mal versuchen, das Gegenteil
auszudrücken von aus P Pfeil Q.
Wenn das nicht der Fall sein soll, was heißt denn das?
Dann kann es irgendwie passieren, dass P wahr ist und Q falsch.
Dann würden Sie nichts sagen aus P Pfeil Q.
Also man hat das Gefühl, das Gegenteil jetzt so ein bisschen Hände
wedelnd.
Das Gegenteil von aus P Pfeil Q ist P und nicht Q.
Und das heißt, P impliziert Q ist äquivalent zur Negation davon.
Also dann eben das Gegenteil vom Gegenteil sozusagen.
Und nicht P und nicht Q ist nach dem, wo haben wir es denn?
Nach dem ersten Beispiel hier oben.
Negation von dem und ist oder von den Negationen.
Also nicht P und nicht Q ist äquivalent zu nicht P oder nicht nicht Q.
Und nicht nicht Q ist nach dem zweiten Beispiel, also das habe ich
behauptet.
Machen Sie es sich klar, schreiben Sie die Tabellen auf.
Nicht nicht Q ist äquivalent zu Q.
Und dann sind Sie durch harmlose Umformungen dahin gekommen, dass P
Pfeil Q äquivalent ist zu nicht P oder Q.
Das ist halt so.
Und so handhaben wir das immer.
So handhaben das alle immer.
Also wir auch.
Also äquivalente Formeln sind welche, die für alle Interpretationen
den gleichen Wahrheitswert liefern.
Und jetzt möchte man eigentlich gerne,
eigentlich möchte man noch ein bisschen mehr.
Also stellen Sie sich vor, man hat zwei Formeln, die eine ganz
aufregend P0 und P0 und die andere P2 und P2.
Das sind jetzt formal nicht äquivalente Formeln, weil Sie ja eine
Interpretation angucken können, wo P0 wahr ist und P2 falsch und dann
ist G wahr und H ist falsch.
Aber irgendwie, man hat da ja nur die Variablen umbenannt.
Das ist ja irgendwie ziemlich willkürlich.
Und wenn ich in H nicht P2, sondern P0 geschrieben hätte, dann wäre es
eine andere Formel gewesen syntaktisch.
Dann hätte ich auf einmal eine gehabt, die ist äquivalent.
Das würde man natürlich gerne am liebsten noch weg definieren.
Und das kann man auch, indem man sagt, also vergessen wir mal einfach,
dass das hier P0 und hier P2 hat, sondern kümmern wir uns nur darum,
es gibt in beiden Formeln eine Aussagevariable mit dem kleinsten Index
und eine mit dem zweitkleinsten Index und eine mit dem drittkleinsten
Index.
Also Sie zählen nur, wieviel der Index ist das von allen, die
vorkommen.
Und sozusagen, Sie prügeln alle Indizes zurück auf 0 bis
Anzahlvariablen minus 1, die vorkommen.
Und weil es aber nicht wichtig ist, will ich da auch gar nicht groß
drüber reden.
Also hier Sie sortieren dann sozusagen die Aussagevariablen und ich
schreibe Pünktchen, aber das darf nur ich.
Und I1 ist der kleinste Index von der Aussagevariable, I2 der
zweitkleinste bis IK.
Und dann können Sie einfach für jedes Tuple X1 bis XK aus B hoch K auf
die naheliegende Weise die Interpretation definieren.
Und wenn Sie das so machen, dann kommt für diese Formeln G und H halt
das Gleiche sozusagen raus, weil Sie nur noch gucken, was ist der
kleinste Index in beiden Formeln und nicht mehr ist das 0 oder 2.
Gut.
So, was noch wichtig ist.
Ja, wenn Sie eine Formel haben, dann kommt es durchaus vor, dass in
einer Interpretation eine Formel mal wahr ist.
Beispiele haben wir gesehen.
Es gibt auch Formeln, die sind in keiner Interpretation wahr.
Können Sie auch mal überlegen.
Und wir wollen sagen, eine Formel ist ein... Quatsch, eine
Interpretation ist ein Modell für eine Formel, wenn die Auswertung der
Formel in dieser Interpretation wahr ergibt.
Und hier sind wir jetzt an einer Stelle, das wird ein bisschen
aufwendiger, aber ganz analog in Prädikaten logisch wieder vorkommen.
Da werden Sie jetzt sagen, ja, was soll der Aufwand?
Aber das macht man halt so.
Und wenn man nicht nur eine Formel G hat, sondern eine ganze Menge
Großgamma von Formeln, dann sagt man, eine Interpretation ist ein
Modell für die ganze Menge von Formeln, wenn sie für jede Formel aus
der Formelmenge ein Modell ist.
Also dann in dieser Interpretation, welche Formel auch immer Sie
nehmen, alle liefern wahr.
Und wenn Sie eine Formelmenge Gamma haben und eine Formel G und Sie
stellen fest, jedes Modell, jede Interpretation, die alle Formeln in
Gamma wahrmacht, macht auch automatisch immer die Formel G wahr.
Warum auch immer.
Dann schreiben wir sowas hier, also die Formelmenge Gamma und dann so
ein Zeichen.
Das wird typischerweise geschrieben, ein senkrechter Strich und zwei
waagrechte Striche, die da dran kleben nach rechts.
Und das bedeutet also, jedes Modell von Gamma ist auch ein Modell von
G.
Und wenn die Formelmenge nur eine Formel enthält, dann lässt man die
geschweiften Klammern von dieser Formelmenge auch weg.
Jede Interpretation, jedes Modell von H ist ein Modell von G.
Und wenn Sie gar keine Formel brauchen, wenn Sie die leere Formelmenge
haben auf der linken Seite, dann schreiben Sie da gar nichts mehr hin,
steht das so.
Und die Bedeutung ist dann, diese Formel G ist in allen
Interpretationen wahr.
Das gibt es auch, Formeln, da können Sie die Variablen interpretieren,
wie Sie wollen, es kommt immer wahr raus.
Solche Formeln nennt man Tautologien oder allgemeingültige Formeln.
Jetzt erstmal in der Aussagenlogik.
Also das sind Formeln, da können Sie interpretieren, wie Sie wollen,
immer es kommt wahr raus.
Zum Beispiel P oder nicht P. Da können Sie für P wahr einsetzen, da
können Sie falsch einsetzen, das ganze Ding ist immer wahr.
Denn entweder ist P wahr oder nicht P. Und dann das Oder ist auf jeden
Fall auch wahr.
Oder sowas hier, P-Pfeil, Q-Pfeil, P ist auch immer wahr.
Da können Sie für P und Q wahr und falsch einsetzen, wie Sie wollen,
es kommt immer wahr raus.
Denn entweder ist P falsch, dann ist sowieso alles wahr.
Oder P ist wahr, dann ist hier vorne wahr und hier hinten, wenn P wahr
ist, das Q-Pfeil P ist dann auch wahr, haben Sie Pfeil wahr, ist immer
wahr.
Also dieser Begriff der Tautologie, der Allgemeingültigkeit, das ist
was Inhaltliches, das hängt an Interpretationen.
Das ist mit Syntax zu tun.
So, das ist also die eine Sorte von Formeln, die wichtig ist, wie sich
herausstellt.
Es gibt noch eine andere Eigenschaft, die eine Formel haben kann, die
auch ganz wichtig ist, nämlich die erfüllbar zu sein.
Eine Formel heißt erfüllbar, wenn es wenigstens in einer
Interpretation wahr wird.
Also wenn es mindestens eine Interpretation gibt, weil I von G ist
wahr.
Und das ist etwas, erfüllbare Formeln, also die Aufgabe für eine
Formel herauszufinden, eine aussagenlogische Formel, ist sie erfüllbar
oder nicht?
Das ist tatsächlich etwas, das will man manchmal in der Praxis.
Also es gibt allerlei Probleme, die kann man darauf zurück prügeln,
dass man Erfüllbarkeit überprüfen muss.
Und da gibt es jetzt leider eine schlechte Nachricht.
Also herauszufinden, ob eine Formel erfüllbar ist, ist im Prinzip kein
Hexenwerk.
Man macht sich die große Tabelle, so ich es bisher auch gemacht habe,
schreibt sich alle Interpretationen hin und guckt halt, rechnet alles
aus.
Das Problem ist, es gibt so viele Interpretationen, das dauert
manchmal sehr lange.
Und eigentlich würde man ja gerne das Ganze viel schneller überprüfen.
Und es kommt so ein bisschen darauf an, wie die Formel aussieht.
Wenn Sie so eine Formel haben wie hier in der drittletzten Zeile, so
zum Beispiel jetzt hier einfach ein oder von zwei Klammer ausdrücken,
die heißen dann Klauseln.
Und da steht immer ein und drin.
Ob das erfüllbar ist, ist ganz einfach.
Wenn dann oder von irgendetwas, es reicht ja, wenn eins von beiden
erfüllt wird.
Einmal war reicht fürs oder.
Und dann gucken Sie sich die erste Klausel an, da sehen Sie ja, da
mache ich P war und Q falsch, dann ist P und nicht Q war Formel
erfüllt.
Wenn Sie eine Formel haben von der Bauart hier in der vorletzten
Zeile, da ist ein logisches und und in den Klammern steht oder.
Da sieht man das nicht mehr so schnell.
Solange Sie in den Klammern immer nur zwei Aussage variablen haben,
Mitteilungen, gibt es noch Algorithmen, die das in halbwegs
vernünftiger Laufzeit für große Formeln hinkriegen?
Aber wenn Sie da manchmal mindestens drei Aussage variablen stehen
haben, wird es hässlich.
Wie hässlich lernen Sie in theoretische Grundlagen der Informatik?
Das Problem ist, man weiß noch gar nicht mal genau, wie hässlich es
ist.
Die Beobachtung ist nur, es macht Ärger.
Gut.
Jetzt.
Was wollen wir noch?
Ach so.
Wir hatten ja diese Abkürzung G Doppelpfeil H eingeführt.
Für G impliziert H und H impliziert G.
Und stellen Sie sich vor und wenn Sie das auswerten, da wenden Sie
halt die Regeln an.
Da kommt irgendwas raus, bis Sie an der Stelle sind, wo Sie halt
wissen wollen, was gibt die Auswertung der Formeln G und H.
Und jetzt stellen Sie sich mal vor, G und H sind äquivalente Formeln.
Also für jede Interpretation, die Auswertung liefert immer das
Gleiche.
Dann können Sie also hier oben überall statt Auswertung von H können
Sie Auswertung von G hinschreiben, denn die beiden Formeln liefern ja
immer das Gleiche bei allen Auswertungen.
Und dann sieht man sofort, dass hier wahr rauskommt.
Immer.
Also wenn G und H äquivalente Formeln sind, also für jede
Interpretation, sie liefern den gleichen Wahrheitswert, dann diese
Formel hier, G impliziert H und H impliziert G, ist immer wahr, also
eine Tautologie.
Also wenn G und H äquivalent sind, dann ist G Doppelpfeil H eine
Tautologie.
Und das gibt einem sozusagen eine Möglichkeit, schnell irgendwelche
Tautologien hinzuschreiben.
Und hier steht, wenn dann, wenn sowas irgendwo steht, dann denken Sie
immer auch mal kurz drüber nach, was ist denn eigentlich, wenn man das
vertauscht?
Also was ist mit der umgekehrten Aussage, wenn G Doppelpfeil H eine
Tautologie ist, dann sind G und H äquivalent.
Stimmt das auch?
Ja oder nein?
Und in diesem Fall, ja, das ist so.
Der Beweis hilft uns aber jetzt in dieser Vorlesung nicht groß weiter,
deswegen lassen wir ihn.
Und auf diese Art und Weise können Sie leicht viele Tautologien
hinschreiben.
Nehmen einfach zwei äquivalente Formeln, schreiben einen Doppelpfeil
dazwischen.
Aber es gibt auch Tautologien, die nicht so aufgebaut sind.
Hier habe ich welche hingeschrieben aus G Pfeil G.
Für jede Formel, also das ist nicht nur eine Tautologie.
Sie können eine beliebige aussagenlogische Formel G nehmen,
irgendeine, hinschreiben, Pfeil, nochmal die gleiche Formel
hinschreiben.
Das Ding wird immer wahr sein.
Denn wenn Sie es auswerten, vor und hinter dem Pfeil taucht entweder
in beiden zweimal wahr auf oder zweimal falsch.
Nie einmal wahr, einmal falsch.
Das kann nicht passieren, ist ja die gleiche Formel.
Also das ist immer wahr.
Und insbesondere hier in der vierten Zeile, weil wir es gleich noch
brauchen werden.
G und H impliziert G ist eine Tautologie.
Immer.
Also wenn Sie wissen, G und H sind wahr, dann G ist wahr.
Ja, natürlich.
Wenn man es so formuliert, denkt man, ist ja klar.
Soll es ja auch sein, so ist es gebaut.
Okay, gut.
Also, was wir uns bis hierher merken, also es gibt politische
Funktionen.
Und wenn Sie Aussage variablen, Wahrheitswerte zuordnen, dann können
Sie größere Formeln auch auswerten.
Da kommt dann wahr oder falsch raus.
Und es ist irgendwie plausibel definiert.
Gut.
Und wir haben gerade über Tautologien geredet, also Formeln, die sind
immer wahr, egal wie Sie es interpretieren.
Das sind natürlich schöne Aussagen, gelten immer.
Immer wahr.
Schöne Sache.
Interessiert einen.
Aber also Tautologie ist ein inhaltlicher Begriff.
Auswertung lebt immer wahr.
Und dem kann man jetzt noch einen syntaktischen Begriff
gegenüberstellen, so eine Formalisierung von beweisbar.
Aber da mir vollständige Induktion wichtiger ist, schieben wir diesen
Abschnitt Beweisbarkeit und gehen jetzt erstmal zu dem ersten Teil von
Kapitel 6.
Vollständige Induktion.
Hier stehen Steine hintereinander.
Und jemand hat den ersten umgeworfen.
Und dann einer nach dem anderen kippt um.
So was haben Sie vielleicht selber auch schon mal gemacht, so mit
kleinen Dominosteinen.
Wer hat sowas schon mal gemacht?
Hand hoch.
Okay.
Und im Hinterkopf lassen wir jetzt mal die Frage ein bisschen
schlummern.
Was passiert am Ende?
Und am Ende der Vorlesung zeige ich Ihnen, wie es weitergeht.
Ja, Sie müssen bis zum Ende da bleiben.
Gut.
Also, vollständige Induktion.
Und zwar erstmal sozusagen die Standard-Vorgehensweise, die einem
schon in vielen Fällen hilft.
Insbesondere dann auch bei induktiven Definitionen.
Zum Beispiel, um einzusehen, wenn man da so eine induktive Definition
hinschreibt, wieso wird hier überhaupt komplett für alle Möglichkeiten
was definiert?
Hinschreiben kann man viel, wenn der Tag lang ist.
Und manchmal braucht man dann aber auch noch so Varianten, die sind
rein äußerlich so ein bisschen anders.
Man macht ein bisschen was anderes, aber inhaltlich ist das Gleiche.
Gut.
Potenzen von Wörtern kamen, glaube ich, gerade in der Übung auch schon
noch mal vor.
Also wir hatten definiert für jedes Wort, W hoch 0 ist immer das
nähere Wort und W hoch N plus 1 ist W hoch N konkateniert mit W.
Und ich hatte letzte Woche schon mal drüber geredet, man kann sich
überlegen, es sieht plausibel aus.
Die Länge von W hoch N ist N mal die Länge von W.
Und da hatte ich schon so ein bisschen, probieren wir das mal
nachzurechnen für N gleich 0, für N gleich 1, für N gleich 2.
Aber wie beweist man, dass das für jedes N aus N 0 gilt?
Und das allereinfachste Beweisprinzip, in Anführungszeichen, wenn Sie
so wollen, habe ich Ihnen ja schon immer gesagt, wenn da steht, für
jedes irgendetwas gilt eine Aussage, man kann einfach sagen, dann
nehme ich halt ein beliebiges irgendetwas her und rede darüber und
wenn der Beweis dann immer funktioniert, egal welches Ding ich
genommen habe, dann gilt es halt offensichtlich für jedes.
Also man könnte jetzt einfach sagen, dann nehme ich halt irgendein
beliebiges N her, irgendeine Anzahl Wiederholungen, ich lege nicht
genau fest, welche, und wenn ich für dieses beliebige N das beweisen
kann, ist ja alles gut.
Ja, aber da hat man dann hier in dem Fall einfach Probleme, einen
Beweis zu finden.
Gut, also was anderes.
Also man kann sich überlegen, die Aussage wird wohl stimmen.
Also erstmal für N gleich 0, ach so, das waren die Potenzen, für N
gleich 0 rechnet man nach, die Länge von W hoch 0, das ist ja die
Länge von dem leeren Wort, laut Definition von W hoch 0, Länge des
leeren Wortes ist 0, das ist 0 mal die Länge von W, alles gut.
Für W hoch 1 analog, die Länge von W hoch 1 ist per Definition die
Länge von W hoch 0 plus 1, das ist Länge von W hoch 0 konkret mit W.
Also man benutzt hier, dass man für Länge 0 weiß und findet heraus,
man nutzt, dass es für 0 Wiederholungen gilt und zeigt dann, für eine
gilt es auch.
Und wenn man weiß, es gilt für eine, dann kann man auch nachrechnen,
dass es für 2 gilt und so weiter.
Also man kann sich da immer so weiterhangeln und wenn man es genau
macht und irgendwie ordentlich definiert, was sind eigentlich die
nicht negativen ganzen Zahlen, dann ist tatsächlich Bestandteil der
Definition, also das muss man da nicht weiter hinterfragen, das ist
dann garantiert so, die folgende Aussage, wenn Sie eine Menge M haben,
da sind nur Zahlen aus N 0 drin, nicht noch irgendwas anderes.
Und diese Menge hat noch zwei Eigenschaften, nämlich erstens die 0 ist
drin und zweitens für jedes N gilt, wenn N drin ist, dann N plus 1 ist
auch drin.
Wenn eine Menge diese Eigenschaften hat, dann garantiert die Menge,
ist genau die Menge aller nicht negativen ganzen Zahlen.
Da fehlt keine und da ist auch nichts zusätzlich oder so.
Und dass das so ist, das ist Bestandteil offiziell der Definition
sozusagen von nicht negativen ganzen Zahlen, das kann man einfach
benutzen.
Wir hinterfragen nicht die Definition von nicht negativen ganzen
Zahlen.
Also wenn eine Menge 0 enthält und für jedes N auch N plus 1 und nicht
noch irgendwas Krummes, Wurzel 2, dann ist M gleich N 0.
Und das Prinzip von vollständiger Induktion ist jetzt einfach, also
Sie haben für jedes N aus N 0 so eine Aussage, wie zum Beispiel gerade
eben die Länge von W hoch N ist N mal die Länge von W.
Und Sie möchten gerne beweisen, für jedes N aus N 0 die Aussage A N
ist wahr.
Und dann eine Möglichkeit, das eben mit vollständiger Induktion zu
machen, ist die folgende, Sie definieren die Menge groß M, jetzt um
bei der Notation zu bleiben erstmal, nämlich zu sagen, groß M, das
soll die Menge aller N sein mit der Eigenschaft, die Aussage A N ist
wahr.
Also die natürlichen Zahlen, für die A N wahr ist.
So, das ist die Definition von M und dann wollen Sie zeigen, naja, M
soll halt N 0 sein, alle sollen drin sein.
Und wie beweist man, dass M gleich N 0 ist?
Ja, das, was wir gerade gesehen haben.
Also man beweist, 0 ist in M drin und für jedes N gilt, wenn N in M
drin ist, dann auch N plus 1.
Ja,
das ist der Plan, also um zu zeigen, für jedes N die Aussage A N gilt.
Man zeigt, die Menge der natürlichen Zahlen, für die A N das wahr ist,
enthält 0 und mit jedem N auch N plus 1.
So, und 0 in M heißt A 0 ist wahr.
Und für jedes N, N aus M impliziert N plus 1 aus M heißt, für jedes N
gilt, wenn A N wahr ist, dann ist ja N in M, dann A N plus 1 ist wahr,
denn dann soll ja auch N plus 1 in M sein.
Und das ist das, was man leisten muss.
Also man muss zeigen, A 0 ist wahr.
Wenn ich beweisen will, alle A 0, A 1, A 2, alle sind wahr.
Man beweist, A 0 ist wahr, einfach ganz explizit und das ist halt
typischerweise ein harmloser Fall.
Und man beweist, für jedes N gilt, wenn A N wahr ist, dann auch A N
plus 1.
Da hat man jetzt natürlich wieder eine Aufgabe zu zeigen, etwas, das
steht wieder davor, für jedes N aus N 0 gilt.
Das ist wieder von der gleichen Bauart, wie das, was man eigentlich
will, für jedes N aus N 0 gilt.
Aber das, was man dann für jedes N zeigen muss, ist halt was anderes.
Also nicht mehr A N gilt, sondern wenn A N wahr ist, dann ist auch A N
plus 1 wahr.
Und das ist halt dann manchmal einfacher.
Also wir haben für jedes N aus N 0 eine Aussage A N.
Ich trete das jetzt gerade sehr breit, damit ich sicher bin, dass Sie
das alle wirklich garantiert mitnehmen.
Und dann haben wir also die Aufgabe zu zeigen, A 0 ist wahr.
Das nennt man dann typischerweise den Induktionsanfang.
Das muss man dann halt machen, irgendwie.
Das ist meistens einfach.
Manchmal ist auch der Induktionsanfang etwas komplizierter oder
braucht eine Seite oder was auch immer.
Und man muss zeigen, für jedes N, wenn A N wahr ist, dann A N plus 1.
Und wie beweist man, für jedes N etwas gilt?
Eine Möglichkeit ist zu sagen, wir nehmen uns irgendein N her...
und zeigen, naja, wenn dieses A N für dieses N, das A N war, ist dann
auch A N plus 1.
Und da das N ja beliebig war, ich mache keine weiteren Annahmen, wenn
es für ein beliebiges N gilt, das hier zu zeigen, dann gilt es halt
für jedes.
Dann habe ich das erledigt.
Und das nennt man dann typischerweise den Induktionsschritt.
Also man sagt, hier, jetzt habe ich ein beliebiges N und jetzt muss
ich für dieses beliebige N zeigen, wenn A N wahr ist, dann auch A N
plus 1.
Und dieses A N, also jetzt muss man eine Implikation beweisen.
Was ist das Problem?
Wenn A N falsch ist, muss man gar nichts tun.
Dann ist die Implikation automatisch wahr.
Das interessiert keinen.
Also der interessante Fall ist, das A N, und das heißt dann,
Induktionsvoraussetzung ist wahr.
Und man muss beweisen, A N plus 1 ist jetzt dann aber auch wahr.
Das ist dann sozusagen die Induktionsbehauptung.
So, das ist die Struktur von Induktionsbeweisen, grob gesagt.
Also machen wir das für dieses Länge von W hoch N ist N mal Länge von
W.
Das ist sozusagen die Aussage A N, Länge von W hoch N ist N mal Länge
von W.
Und W ist irgendein beliebiges Wort über irgendein beliebigen
Alphabet.
So, Induktionsanfang N gleich Null.
Das heißt, was muss man zeigen?
A Null, also Länge von W hoch Null ist Null mal Länge von W.
Wie beweist, haben Sie hier eine Gleichheit?
Die Behauptung, zwei arithmetische Ausdrücke sind gleich.
Wie macht man das?
Habe ich Ihnen auch schon in der letzten Woche mal gesagt.
Fangen Sie mit einer Seite an, formen Sie systematisch um und
irgendwann enden Sie bei der anderen Seite.
Also fangen Sie an mit Länge von W hoch Null.
Linke Seite, was ist das?
W hoch Null ist das leere Wort.
Das leere Wort hat Länge Null und das ist offensichtlich Null mal
Länge von W.
Und dann haben wir die rechte Seite.
Und das andere ist der Induktionsschritt.
Wir müssen uns weiter hangeln von N nach N plus 1.
Und müssen also zeigen, wenn A N wahr ist, also wenn die Länge von W
hoch N N mal Länge von W ist, ist dann die Aussage A N plus 1 ist auch
wahr.
Und A N plus 1 ist die Aussage, Länge von W hoch N plus 1 ist N plus 1
mal Länge von W.
Das muss man natürlich richtig hinschreiben.
Gut.
Also wie zeigt man das für jedes N?
Nehmen wir ein beliebiges her und zeigen jetzt also, wenn A N war,
dann A N plus 1.
So, und Induktionsvoraussetzung ist also, A N ist wahr.
Also die Länge von W hoch N ist N mal Länge von W.
Das ist Voraussetzung und uns interessiert nur der Fall, das ist eine
wahre Aussage.
Und dann können wir das auch benutzen im Beweis.
Es ist halt so.
Das ist der Fall, der interessant ist.
Und was muss man dann zeigen?
Ja, die Induktionsbehauptung, also A N plus 1.
Also man muss jetzt zeigen, die Länge von W hoch N plus 1 ist N plus 1
mal Länge von W.
Und meine Empfehlung, ich schreibe hier ziemlich viel hin.
Solange Sie noch nicht viel Erfahrung und Übung haben, schreiben Sie
lieber auch zwei Wörter mehr hin.
Und dafür steht alles auf dem Papier und Sie müssen nicht so viel im
Kopf haben.
Also schreiben Sie hin, wir müssen jetzt zeigen, A N plus 1 ist wahr.
Also schreiben Sie mindestens hin, zu zeigen ist jetzt Länge von W
hoch N plus 1 ist N plus 1 mal Länge von W.
Und hier auch wieder.
Sie haben links und rechts zwei arithmetische Ausdrücke und Sie wollen
zeigen, die sind gleich.
Fangen Sie mit einem an, formen Sie halt so lange um, bis Sie beim
anderen angekommen sind.
Und das ist typischerweise kein Hexenwerk.
Also nehmen Sie die linke Seite, Länge von W hoch N plus 1.
Was wollen Sie groß machen?
Im Zweifelsfall schreibt man halt mal hin, wie das Zeug definiert ist.
Also was ist Länge von W hoch N plus 1?
Laut Definition von diesen Potenzen, das ist W hoch N konkateniert mit
W.
Was ist Länge von Konkatenation zweier Wörter?
Das haben wir als Bemerkung schon bei der Definition von Konkatenation
stehen.
Das ist Summe der Längen der beteiligten Wörter, also Länge von W hoch
N und Länge von W.
Und dann auch bei Großteil der vollständigen Induktionen irgendwo
erweist es sich als hilfreich, dass man die Induktionsvoraussetzung
hat, dass man weiß, irgendetwas ist schon wahr.
Und hier die Induktionsvoraussetzung ist Länge von W hoch N ist N mal
Länge von W.
Und hier steht Länge von W hoch N, das darf ich dann also ersetzen
durch N mal Länge von W.
Das ist das Gleiche.
Und dann steht da N mal Länge von W plus W.
Und an der Stelle, wo Sie die Induktionsvoraussetzung benutzen, bitte
schreiben Sie wenigstens das noch irgendwie dazu.
Dahinter oder über das Gleichheitszeichen, dass der Leser wenigstens
weiß, aha, an der Stelle, da ist es passiert.
N mal Länge von W plus W, da muss man dann noch sehen, dass man da die
Länge von W ausklammern kann.
Und dann steht da N plus 1 mal Länge von W und das ist die rechte
Seite, zu der wir kommen wollten.
Hier die Länge von W ausklammern ist völlig banal, wenn man in Ruhe
hier so sitzt und sich die Folien auf der Leinwand anguckt.
Aber ich habe es nicht nur einmal erlebt, wenn jemals in der
Stresssituation mündliche Prüfung ist, man sieht das nicht mehr.
Also versuchen Sie, entspannt zu bleiben, auch wenn es schwerfällt.
So, ja, und damit haben wir jetzt also bewiesen, wenn a N wahr ist,
das haben wir auch benutzt, dann a N plus 1 ist wahr.
Und das war für ein beliebiges N.
Und jetzt gehe ich nochmal zurück.
Das heißt, wir haben jetzt tatsächlich den Induktionsschritt fertig,
den Induktionsanfang hatten wir auch.
Alles gut, wir haben es wirklich komplett bewiesen.
So, und weiter wollte ich mit vollständiger Induktion heute auch nicht
machen.
Aber die Frage ist jetzt noch, wie geht es weiter mit den Steinen, die
hier der Reihe nach umfallen?
Na, ich gehe nochmal ein kleines bisschen, ja so.
Achtung.
So, Hausaufgabe, was ist hier los?
Dankeschön.