Einen schönen guten Morgen und herzlich willkommen meinerseits zu
unserer vierten Übung.
Heute erzähle ich mal über Aussagenlogik und wir haben wieder viele
Folien.
Sie haben ja in der Vorlesung gesehen, dass wir dieses Argumentieren
mit den Beweisen ein bisschen mehr präzisieren wollten.
Und uns anschauen wollten, wie sind diese Aussagen, die ich in den
Beweisen schreibe, dann besser...
so besser anschauen, wie diese aufgebaut sind.
Wie ist ein Argument aufgebaut überhaupt?
Wie setzen sich Aussagen zusammen zu einem Argument?
Zu einer Formel in dem Fall.
Und was haben wir gemacht?
Wir haben gesehen, wir haben zugelassen eine beliebige Anzahl von
Aussagevariablen.
Und dann von diesen unendlich vielen möglichen Variablen haben wir
eine ähnliche Teilmenge genommen.
Das haben wir dann unser Alphabet, das Aussagenlogische Variablen
genannt.
Insbesondere ist das eine ähnliche Teilmenge.
Alphabet, das haben wir ja so definiert.
Und dann, wenn wir diese Aussagevariablen haben, können wir die
zusammen verbinden mit sogenannten Konnektiven.
Das ist dann die Verunung, Verurderung, Implikation, aber auch die
Negation haben wir auch konnektiv genannt.
Das negiert ein Symbol oder eine Formel, das verbindet nicht viel,
aber so ist es eben.
Und dann, wie diese ganzen Formeln aufgebaut sind, auch beliebiges
Verbinden von...
Also ich kann nicht nur Variablen verundern und verurdern, ich kann
auch ganze Formeln verundern.
Und dann, wie können wir das alles formalisieren?
Wir haben alles induktiv eigentlich definiert, weil ich mit diesen
Variablen anfange und dann kann ich aus den Variablen mehrere Formeln
basteln und dann kann ich wieder diese Formeln mit diesen Konnektiven
miteinander verbinden und dann so kann ich beliebige Formeln erzeugen.
Und dann, das ist sowas, wie Sie unten da in der Folie sehen.
Ja, ich habe Formeln, ich kann die Formeln negieren, ich kann die zwei
Formeln miteinander verbinden und so weiter und so fort.
Und damit kann ich alle Formeln, die ich will, erzeugen.
Und später in der Vorlesung werden Sie auch sehen, wie wir diese Art,
was induktiv ist zu definieren, ein bisschen formalisieren und besser
unter die Lupe nehmen.
Was später...
So, wie gesagt, ich kann Formeln in dieser Art und Weise dann
erzeugen.
Insbesondere zum Beispiel sowas wie dieses Vieh da.
Ich fange mit Variablen an, ich kann diese Variablen miteinander
verbinden mit dieser Verunderung.
Dann kann ich diese Formeln negieren und dann kann ich eine
Implikation dran nehmen.
Und so kann ich diese Formeln erzeugen.
Das kann ich mit jeder Formel machen, die ich jetzt als gültige Formel
betrachte.
Und wir haben auch...
Ja, es wird immer diese Klammern drumherum sein und damit man nicht
viele, viele, viele Klammern hat und dann die Übersicht verliert,
haben wir auch zugelassen, dass man die Klammer weglässt, sobald man
eine Reihenfolge festgelegt hat, in welcher Reihenfolge entstehen dann
die Konnektiven.
Also zum Beispiel hier kann die Implikation beziehen sich auf die zwei
Formeln Q und an die Negierung von diesen P und Q und nicht, dass die
Implikation jetzt die Negierung mit Q verbindet oder so.
Das ist ganz eindeutig, was damit gemeint ist.
Ich brauche nicht die extra Klammer drumherum.
Dann zurück eigentlich zur letzten Übung.
Diese Fs sind eigentlich auch binäre Operationen.
Das habe ich letztes Mal erzählt, was die sind.
Also die nehmen zwei Formeln als Argumente und geben mir wieder eine
Formel zurück.
Jetzt kann man sich fragen, ist das ganze Kommutativ?
Eigentlich nicht, weil wenn ich mit P und Q anfange und die in dieser
Reihenfolge verundern, dann kommt eine andere Formel, als wenn ich mit
Q anfange und das mit P verundern.
Warum ist das so?
Sie sehen ganz ähnlich aus und sie denken, ja, das sind gleiche
Formeln in einem gewissen Sinne.
Aber sehen sie nicht diese als Formel noch, sehen sie diese als
Wörter.
In der ersten Stelle haben sie einen Klammer auf.
In der zweiten Stelle haben sie bei der einen Formel ein P stehen, bei
der anderen Formel haben sie ein Q stehen.
Die können nicht gleiche Wörter sein.
Deswegen sehen die Formeln ähnlich aus, aber sind taktisch als Wörter
gesehen.
Das heißt, sie sind anders.
Sie sind nicht das gleiche Wort.
Und mit der Assoziativität klappt das auch nicht.
Jetzt hier wegen der Klammerung klappt das nicht, aber man kann auch
andere Beispiele konstruieren.
Mit anderen Formeln, die nicht nur auf Arabien sind zum Beispiel.
Dann diese ganze Formeln sind eigentlich eine formale Sprache.
Das ist einfach eine Teilmenge von Wörtern über dieses Alphabet, der
aussagenlogische Formeln.
Und hier sehen sie ja, wir haben diese ganze Sprache von Formeln
definiert.
Und damit haben wir ausgedrückt, was denn syntaktisch korrekt ist für
eine Formel.
Eine Formel ist syntaktisch korrekt, wenn sie eben ein Element von
dieser Sprache ist.
Das können sie nicht nur mit Formeln machen, das können sie auch mit
Programmiersprachen machen.
Sie können die Sprache a la korrekt syntaktischen Java Programmen zum
Beispiel auch als eine Sprache definieren.
Das können sie auch machen.
Später, wenn wir über diese Systeme zur Rede kommen, die induktiv was
aufbauen und definieren, Wörter usw.
Dann werde ich noch ein Beispiel bringen, wie das aussehen kann für
eine Programmiersprache.
Das ist wieder Zukunftsmusik.
Deswegen versuchen wir zuerst mal über etwas anderes zu reden.
Ich versuche jetzt anzustoßen, ich hatte diese zwei Wörter gezeichnet,
p und q und q und p.
Und gesagt, ich hatte sie nicht gleich als Formel.
Die können nicht gleich sein, das sind verschiedene Wörter.
Aber ich kann noch annähern, diese ganze Idee, die wir haben, dass
diese Formeln doch in einem gewissen Sinne gleich sein sollten.
Für ein gewisses Konzept von Gleichheit, sagen wir mal so.
Und damit ich das genauer ausdrücken kann, muss ich mir zuerst
überlegen, was eine Formel als Bedeutung haben kann.
Dann gehe ich in die sogenannte semantische Ebene.
Und in der semantischen Ebene können Verabeln und Formeln
Wahrheitswerte annehmen.
Hier haben wir binäre Logik, sozusagen, wir haben zwei Wahrheitswerte.
Also entweder war falsch, wie man es ganz gewohnt ist, bei einem
Argument.
Das ist ja, falls die Aussagenlogik zu formalisieren versucht, wie ich
ein Argument formalisieren kann.
Aus der Kette von Aussagen, die irgendwas aussagen sollten.
Dann haben wir diese Konnektive jetzt auch besetzt in dieser
semantischen Ebene.
Wir haben zum Beispiel Verabeln x1 und x2, die können Werte annehmen.
Und wenn ich diese zwei Verabeln mit diesen Konnektiven verbinde, dann
kriege ich wieder Wahrheitswerte.
Wieder binäre Operationen, nur jetzt hier nicht über die Formeln,
sondern über die Menge der Wahrheitswerte.
Und wenn ich mehrere Verabeln habe, sagen wir mal N-Verabeln, dann
habe ich eine boolische Funktion, sozusagen.
So sind die Dinge genannt.
Und es gibt eigentlich sehr, sehr viele boolische Funktionen, wenn ich
N -Verabeln habe.
Wir können das auch ausrechnen mit dieser ganz nützlichen Notation.
Ich habe einmal gesagt, wenn Sie sich das merken, dass die Funktionen
von hier B hoch N nach B gehen, dann schreiben Sie das so und dann
haben Sie automatisch einen Ausdruck, was die Anzahl von Funktionen
ist.
In diesem Fall haben Sie zwei hoch N viele Funktionen.
Weiter in der semantischen Ebene haben wir also diese
aussagenlogischen Verabeln.
Wir können die dann interpretieren, das heißt wir können diese
Verabeln Wahrheitswerte zuweisen.
Und dann anhand von diesen boolischen Funktionen von Ebenen, also wie
wir diese Konnektive auch als binäre Operationen auf diesen Werten
definieren, oder dann können wir auch eine Auswertung induzieren.
Das heißt, ich nehme einfach die Formel und wenn ein N-Verabel da
steht, dann schreibe ich den Wahrheitswert drin und wenn zwei
Wahrheitswerte nebeneinander stehen und ein Konnektiv dazwischen, dann
kann ich die zwei verbinden, wie diese boolische Funktion mir sagt,
dass sie verbunden werden sollten.
Und wenn ich das Ganze weiter und weiter mache, zum Beispiel wenn ich
nur ein P habe und P soll wahr sein, dann muss die Formel P dann den
Wahrheitswert wahrnehmen.
Wenn ich nicht P habe, dann muss ich diesen Wahrheitswert negieren,
dann kann ich auch Dinge verundern und so weiter und so fort.
Und dann kommt immer wieder genau ein Wahrheitswert raus für die
Formel und das ist auch eindeutig festgelegt, welcher das ist, anhand
der Interpretation.
Das hängt immer von der Interpretation ab.
Es kann sein, dass eine Formel für eine gewisse Interpretation einen
Wahrheitswert wahr nimmt, für eine andere aber falsch wird.
Also Sie können nicht sagen, ohne eine Interpretation zu haben, dass
die Formel wahr ist oder so.
Das macht keinen Sinn überhaupt.
Dann kommen wir zurück zu diesem Konzept von Gleichheit.
Die Formeln können gleich als Wörter sein, dann müssen sie ja gleich
sein.
Es kann aber auch sein, dass die verschiedene Wörter sind, aber gleich
in diesem gewissen Sinne sind, dass egal, für welche Interpretation
ich nehme, dann immer der gleiche Wahrheitswert kommt, wenn ich das
Ganze auswerte.
Dann haben Sie das Syntaktische Gleichheit eigentlich stärker als die
Äquivalenz ist, natürlich, weil wenn die Wörter gleich sind, dann
müssen die auch gleiche Wahrheitswerte liefern, egal, welche
Interpretation ich habe.
Aber das muss nicht umgekehrt sein.
Dieses P oder K oder P, die sind nicht das gleiche Wort, weil das
erste Zeichen unterschiedlich ist, die sind aber äquivalent.
Ich kann auch sagen, egal, welche Interpretation ich habe, ich werde
immer den gleichen Wahrheitswert zurückgeliefert bekommen.
In diesem Sinne sind sie gleich, sozusagen.
Eigentlich in der Mathematik kommt es viel vor, dass man ungleiche
Objekte hat, aber dass die eigentlich dieselbe Sache in einem gewissen
Sinne sind.
Und dann haben wir diese Äquivalenzen.
Immer wenn Sie Äquivalent hören, das ist irgendwas wie, das sollte
gleich sein, ist aber nicht, ganz formal gesehen vielleicht nicht,
aber es sollte doch gleich sein.
Wie in diesem Sinne bei den Formeln.
Und dann noch eine Anmerkung, weil ich hier diese syntaktische Ebene
gesehen habe und die semantische Ebene.
Also die Syntaxis, wie diese Formen ganz aufgebaut sind, wie diese
Wörter entstehen, das sind einfach Wörter, viele Symbole, ich habe
keine Ahnung, was das bedeuten sollte.
Und die Bedeutung kommt erst, wenn ich jetzt diesen ganzen Variablen
in den Formeln dann auch Wahrheitswerte zuweise und sage, was diese
Variablen sind.
Und dann kann ich das Ganze interpretieren und auswerten und dann zu
einer Bedeutung für die Formel kommen.
Also diese Interpretation ist dann das Kontext für die Formel,
sozusagen.
Und die letzte Bemerkung habe ich eigentlich schon vorher gesagt.
Jetzt was vom praktischen Nutzen für das Aufgabenblatt.
Wenn Sie eine Formel haben und jetzt für alle mögliche
Interpretationen betrachten möchten, was könnte die Wahrheitswerte
denn sein, dann können Sie das Ganze in eine Tabelle aufführen und
dann einfach diese ganze Wahrheitswerte ausrechnen für alle möglichen
Interpretationen.
Wenn Sie viele, viele Variablen haben, dann wird das sehr
unpraktikabel.
Immer wenn Sie eine Variable mehr haben, dann verdoppelt sich das.
Und hier haben Sie schon vier Zeilen, wenn Sie nur zwei Variablen
haben.
Wenn Sie drei Variablen haben, dann haben Sie acht Zeilen.
Und dann bei vier haben Sie 16 und bei fünf haben Sie 32.
Und das wird einfach explodieren.
Aber wenn Sie ganz kleine Formeln haben, dann taugt das noch, um das
Ganze zu analysieren.
Und Sie können das auch nutzen, um zu zeigen, dass Formeln zum
Beispiel äquivalent sind.
Ich schöpfe eigentlich alle Interpretationen aus, sage, was die
Wahrheitswerte für diese Formeln sind in diesen Interpretationen und
dann, wenn diese Wahrheitswerte alle gleich sind, dann müssen die
Formeln eben äquivalent sein.
So war das definiert.
Und wie können Sie das sauber aufbauen?
Wie gesagt, Sie haben eine Zeile pro jeder Interpretation, die Sie
haben.
Und dann für jedes Konnektiv in der Formel bauen Sie dann sukzessiv
die Wahrheitswerte von den Formeln, die sich mit diesem Konnektiv zu
tun haben.
Für jedes Konnektiv sozusagen haben Sie einen Wahrheitswert.
Das macht nicht so viel Sinn, ganz formal gesehen.
Aber intuitiv ist das, was Sie machen.
Wenn ich jetzt zum Beispiel P und Q habe und für die Verordnung von P
und Q habe ich auch einen Wahrheitswert.
Dann habe ich auch eine Spalte da.
Und wenn ich das P negiere, dann habe ich auch eine Spalte da, weil
das die Negation im Konnektiv war.
Und so mache ich weiter und so fort.
Das ist das.
Das ist ganz intuitiv, denke ich mal.
Wieder etwas Formales.
Wenn Sie eine Interpretation haben und diese Interpretation eine
Formel wahr macht, wenn die Formel unter dieser Interpretation zu wahr
ausgewertet wird, dann wird diese Interpretation ein Modell für diese
Formel genannt.
Wenn Sie einen Kontext I haben, dann gilt G.
Wenn Sie sich in einem Feld befinden, wo I Ihr Feld ist, dann ist G
wahr.
Deswegen ein Modell.
Dieses Feld als Kontext um die Formel herum.
Und dann gibt es hier die Formalisierung für was man sagt, wenn man
sagen will, dass die Formel wahr ist.
Was eigentlich nicht stimmt.
Die Formel kann nicht wahr sein.
Die kann unter einer bestimmten Interpretation zu wahr ausgewertet
werden.
Aber wenn Sie eine Interpretation finden, für die die Formel wahr
wird, dann heißt diese Formel erfüllbar.
Es gibt eine Welt, in der diese Formel gilt.
Und egal in welcher Welt Sie sich befinden, sollte G wahr sein, dann
ist G eine allgemein gültige Formel.
Das gilt überall wo.
Wird auch Tautologie genannt.
Ich glaube, das haben wir auch in der Vorlesung eingeführt.
Das sind eigentlich nur Eigenschaften, die Formel haben können.
Und wenn Sie zeigen möchten, die Formel ist eine Tautologie, zum
Beispiel können Sie eine Wahrheitstabelle aufbauen und dann schauen,
ist diese Spalte für G alles wahr, dann muss die Formel eben eine
Tautologie sein.
Für jede Interpretation ist die Formel wahr.
Das war ja die Definition.
Diese Allgemeingültigkeit hilft uns auch, eine gewisse Sichtweise auf
den Formeln zu haben.
Ich habe zwei äquivalente Formeln.
Ich kann das auch so mit diesem Gleichheitszeichen notieren.
Und ich kann jetzt diese eigentlich semantische Eigenschaft, das gilt
nur für Wahrheitswert und so weiter, ich kann das wieder auf die
syntaktische Ebene zurückführen.
Und dann kann ich diese Äquivalenz auf eine Formel zurückführen und
sagen, diese Äquivalenz gilt nur dann, wenn diese andere Formel, was
ein syntaktisches Konstrukt ist, dann eine Tautologie ist.
Dann habe ich die zwei Ebenen hier verbunden, sozusagen.
Wofür kann das nützlich sein?
Das kann nützlich sein, wenn ich z.B.
zeigen will,
dass Formeln äquivalent sind.
Ich glaube, das Beispiel war nicht für das gedacht.
Wenn Sie zeigen wollen, es sind zwei Formeln äquivalent, dann können
Sie auch diese andere Formel betrachten.
Anstatt dieses ganze Beweis mit Äquivalenz durchzuführen, können Sie
auch eine einzelne Formel betrachten und sagen, ja, diese Formel ist
eine Tautologie.
Dann haben Sie das gezeigt.
Weil z.B.
Äquivalenzbeweise sind eigentlich gruselig.
Ich muss von Äquivalenten, Paaren von Formeln anfangen und dann z.B.
hier will ich zeigen, dass G und H äquivalent sind, dann muss ich das
weiter umformen, umformen, umformen.
Das kann auch kompliziert werden.
Und hier habe ich nur zwei Rahmen.
Ich kann noch eine Wahrheitstabelle dafür basteln, dass wir nur vier
Zeilen haben.
Es sollte doch nicht so kompliziert sein, wie z.B.
sich sowas zu überlegen.
Dann bin ich am Ende der Übung.
Ich bedanke mich für die Aufmerksamkeit und wünsche Ihnen auch eine
schöne Vorlesung.
Jetzt Mikrofon funktioniert, ja, klingt so.
Okay, ja, schönen guten Tag.
Wir haben in der letzten Vorlesung fast alles zu Aussagen-Logik
gemacht, außer einem Abschnitt, zu dem sage ich jetzt gleich noch was.
Und danach haben wir dann vollständige Induktion gemacht.
Dazu sage ich dann auch noch was, geht auch noch ein bisschen weiter.
Und dann bleibt wahrscheinlich noch Zeit, um mit dem siebten Kapitel
anzufangen.
So, wo habe ich hier die richtigen Folien?
Ah ja, Tautologien, genau.
Also es leuchtet Ihnen ja wahrscheinlich ein, dass man interessiert
ist an Formeln, an Aussagen, die immer wahr sind, nicht wahr.
Und der einfachste Fall sind also solche aussagenlogischen
Tautologien, wo man noch gar nicht mal darüber Auskunft geben muss,
die einzelnen elementaren Aussagen.
Ist das jetzt sowas wie a plus b mal a minus b ist a Quadrat minus b
Quadrat oder sowas, sondern einfach nur hier habe ich wahr, hier habe
ich falsch.
Und dann einfach aufgrund der Struktur der Formel, die es immer war,
immer.
Solche Formeln haben wir Tautologien genannt.
Also für jede...
Ich suche noch, warten Sie mal.
Na, doch hier.
Für jede Bewertung mit Wahrheitswerten, die Formel ist immer wahr.
Das waren Tautologien und einige haben Sie gerade in der Übung
gesehen, wenn Sie zwei äquivalente Formeln nehmen und beide
Implikationen nehmen mit und verbinden, haben Sie eine Tautologie.
Es gibt aber auch Tautologien, die nicht von dieser Bauart sind.
Zum Beispiel hier in der vierten Zeile, in der dritten von unten g und
h impliziert g. Da können Sie für g und h beliebige Formeln einsetzen.
Sie können sich der Einfachheit halber auch einfach Aussagevariablen
vorstellen.
Das hat den gleichen Effekt.
Diese Formel g und h impliziert g ist immer wahr.
Anschaulich leuchtet einem das ein.
Und wenn man sich überlegt, wie ist das mit den Wahrheitswerten?
Also wenn hier die Voraussetzung g und h falsch ist, ist die
Implikation sowieso wahr.
Und wenn die Voraussetzung wahr ist, dann muss g wahr sein.
Und dann steht hinten auch wahr.
Und dann ist die große Implikation wahr.
So, das erwähne ich nochmal, weil das was ist, was wir dann gleich so
nebenbei benutzen werden.
Nur dass es explizit gesagt wurde.
So jetzt Tautologie.
Wann ist eine Formel eine Tautologie?
Da geht es also um Semantik, um Bewertung der Variablen mit
Wahrheitswerten und kommt immer wahr raus.
Und ich habe jetzt nicht die ganze Übung zugehört.
Aber ich denke, Herr Modernese hat auch nochmal gesagt, so
Wahrheitstabellen werden halt schnell groß.
Wenn Sie Aussagevariablen haben, haben Sie zwei Hochk-Zeilen in der
Tabelle.
Das ist vielleicht nicht so schön.
Das kann man zwar schön automatisieren, aber naja, gibt es nicht
vielleicht auch noch andere Möglichkeiten.
Und insbesondere, worauf wir jetzt dann im letzten Abschnitt noch
hinaus wollen, ist irgendwie eine Charakterisierung von Tautologien,
also der Formeln, aussagelogischen Formeln, die immer wahr sind, ohne
über Wahrheitswerte zu reden.
Einfach rein syntaktisch irgendwie so ein Spielchen machen mit
Legosteinen.
Das Ganze funktioniert besser, wenn man es richtig benutzt.
Und das führt uns zu Beweisbarkeit.
Und das, was also jetzt kommt, da geht es überhaupt nicht mehr um wahr
und falsch und so im Vordergrund.
Also die Wahrheitswerte tauchen jetzt überhaupt nicht mehr auf.
Es geht jetzt nur noch um so ein Rummachen mit syntaktischen Gebilden,
also so etwas wie aussagenlogischen Formeln zum Beispiel und eine
geeignete Definition von Rummachen damit.
Wir haben schon mal gesagt, also wir wissen, was Wörter sind.
Wir haben auch schon mal gesagt, eine formale Sprache ist einfach eine
Menge von Wörtern.
Und alle aussagenlogischen Formeln überhaupt sind auch eine formale
Sprache.
Haben wir auch irgendwie definiert.
Wir mussten ja sagen, was sind aussagenlogische Formeln.
Und Sie können ja natürlich jetzt auch einschränken und sagen, ja, wie
ist das denn mit der formalen Sprache aller Tautologien, also aller
aussagenlogischen Formeln, die immer wahr sind.
Ist auch eine formale Sprache.
Manche aussagenlogischen Formen sind so, andere nicht.
Und kann man das auch noch irgendwie charakterisieren sozusagen.
Und da kommen wir jetzt eben zu sowas, das hat einer der Professoren,
bei denen ich gelernt habe, immer als Spiel mit Blauklötzchen
bezeichnet.
Also wir legen jetzt Regeln fest, wieder um aus einfachen Formen
kompliziertere Formeln zu machen in Anführungszeichen oder andere.
Und zwar auf eine solche Art und Weise, dass alle Formeln, die man
basteln kann, erstens mal alle werden Tautologien sein.
Und zweitens, man wird auch alle Tautologien basteln können.
Also man hat irgendwie so Regeln, wie man aus Gebilden andere Gebilde
macht, aus aussagenlogischen Formen andere, so dass genau alle
Tautologien, alle aussagenlogischen Formeln, die immer wahr sind,
rauskommen und nichts anderes.
Und was man damit auch so ein bisschen formalisiert nach Amt ist so,
man führt einen Beweis.
Was ist ein Beweis?
Der gleiche Professor, der das mit dem Spiel mit Bauklötzchen gesagt
hat, hat immer gesagt, ein Beweis ist eine Gedankenführung, die
überzeugt.
Ja, aber das reicht nicht immer aus.
Und die Formalisierung, die wir hier nehmen wollen, ist also ganz
plump erst mal, aber halt nicht zu plump.
Und die geht so, erstens, wenn man einen Beweis führt, zu jedem
Zeitpunkt gewisse Formeln darf man einfach hinschreiben und man muss
sich nicht dafür rechtfertigen, dass man jetzt so etwas hier
behauptet.
Wenn Sie irgendwas beweisen, wenn Sie zu irgendeinem Zeitpunkt sagen,
ja, 0 gleich 0, dann wird das keiner hinterfragen.
Jeder wird sagen, ja, natürlich, 0 gleich 0, das darf man behaupten,
muss man nicht mehr beweisen, ist sowieso klar.
Jetzt hier haben wir noch keine arithmetischen Ausdrücke und 0 gleich
0 und sowas.
Das kommt bei Prädikatenlogik in ein paar Wochen.
Aber es gibt immer so Formeln, die darf man einfach hinschreiben in
einem Beweis.
Diese Dinger heißen Axiome.
Und also worauf es hinauslaufen wird gleich, ein Beweis ist einfach
eine Folge von Formeln.
Und wann immer man ein Axiom hinschreibt, man muss sich nicht
rechtfertigen, man darf es einfach.
Deswegen bei einem sogenannten Kalkül, also man hat erst mal
definiert, was sind syntaktisch korrekte Formeln und da gibt es so
eine Teilmenge von Formeln, die sind Axiome und die darf man in seinen
Beweisen einfach benutzen.
Punkt.
Und dann die einzige weitere Zutat, die man noch hat, ist, wenn man so
einen Beweis führen heißt, dann einfach eine Formel nach der nächsten
hinschreiben.
Und solange man nur Axiome hinschreibt, muss man nichts weiter tun.
Man sagt einfach, hier ist ein Axiom, ich brauche mich nicht
rechtfertigen.
Es gibt nur einen Fall, wo man ein bisschen mehr sagen muss.
Und dafür gibt es dann sogenannte Schlussregeln, die einem sagen, wenn
ich schon K-1 Formeln hier stehen habe, also zwei oder drei, bei
Aussagenlogik wir brauchen nur zwei, wann immer ich zwei Formeln hier
stehen habe, wenn die von einer gewissen Bauart sind, dann ich darf
eine dritte Formel unten dran schreiben in meinen Beweis und kann als
Rechtfertigung sagen, die Schlussregel hat es mir erlaubt.
Und die einzige Schlussregel, die man bei Aussagenlogik braucht, für
den...
das...
das Kalkül?
Der Kalkül?
Oh, jetzt weiß ich es selber nicht mehr.
Also das Einzige, was wir hier brauchen, ist die sogenannte
Schlussregel Modus ponens.
Wer hatte Latein in der Schule?
Wer hatte nicht Latein in der Schule?
Ja, macht nichts.
Die Regel ist ganz einfach.
So, und jetzt also für dieses Aussagenkalkül, die Axiome sind ganz
einfach und die Schlussregeln sind ganz einfach.
Also Axiome, hier gibt es drei Mengen von Formeln, die dürfen Sie
immer hinschreiben und als Rechtfertigung können Sie immer einfach
sagen, ist doch ein Axiom, darf ich einfach.
Und das sind drei unendliche Mengen, also G, H und K hier, das sind
beliebige Aussagenlogische Formeln, nur wenn in so einem Ding zweimal
G vorkommt, müssen Sie natürlich zweimal die gleiche Formel einsetzen.
Also zum Beispiel jede Formel der Bauart G impliziert H impliziert G,
dürfen Sie einfach hinschreiben, egal was G und H für Formeln sind.
Und dieses G impliziert H impliziert G ist übrigens äquivalent zu G
und H impliziert G.
Das, was wir gerade hatten, das ist also immer eine Tautologie.
Und die anderen Gebilde hier sind auch alle Tautologien.
Setzen Sie mal ein paar Wahrheitswerte ein oder gucken Sie sich das
ein bisschen an, denken Sie darüber nach, dann sehen Sie, ja, das muss
immer wahr sein, immer.
Also die Axiome, die man hier erlaubt, sind alles Tautologien.
Das ist schlau, man will ja am Ende nur Tautologien rausbekommen, das
heißt, die Axiome, die man sowieso hinschreiben darf, die sollten alle
Tautologien sein.
Sonst wäre alles Unfug.
Also das hier per Definition in diese drei Mengen von Formeln sind die
Axiome.
Und dann gibt es nur eine Schlussregel, den Modus Ponens, und die
erlaubt Ihnen das folgende zu tun.
Das schreibt man halt auf die ein oder andere Weise hin.
Und was es bedeutet ist, wenn Sie schon in Ihrem Beweis, in Ihrer
Liste von Formeln, eine Formel stehen haben, die ist von der Bauart G
impliziert H, für irgendwelche Formeln G und H.
Also wenn Sie das schon in Ihrem Beweis stehen haben, also sozusagen
bewiesen haben, aus G impliziert H, ist wahr, oder ist bewiesen.
Und wenn Sie woanders stehen haben, die Formel G in Ihrer Liste, also
das haben Sie auch schon bewiesen.
Also wenn Sie bewiesen haben, aus G impliziert H, und wenn Sie
bewiesen haben G, dann dürfen Sie mit der Begründung, ja, Modus Ponens
erlaubt mir das, auch die Formel H hinschreiben und sagen, die ist
jetzt auch bewiesen.
Das ist alles.
Und was man hier macht, ist auch nicht absurd.
Das klingt irgendwie plausibel, wenn man bewiesen hat, aus G folgt H,
und man hat bewiesen, G gilt, dann H halt auch.
Also das ist tatsächlich die einzige Schlussregel, die man in diesem
Kalkül hier für die Aussagenlogik benutzt.
Bei Prädikatenlogik kommt dann noch eine zweite Schlussregel dazu, die
ist auch ganz harmlos.
Und was ist dann eine Ableitung?
Also im Allgemeinen jetzt sagt man doch, ach und jetzt zusätzlich hat
man vielleicht noch irgendwelche Hypothesen.
Man will nur beweisen, wenn die Hypothesen bewiesen sind, dann etwas
anderes auch.
Und da taucht wieder dieses, hier in der zweiten Zeile, das erste
Zeichen direkt nach dem blauen Kästchen.
Das ist ein großes griechisches Gamma.
Das ist kein zu groß geratenes kleines R oder sowas.
Das ist ein großes griechisches Gamma.
Gucken Sie sich vielleicht mal die griechischen Buchstaben an, die
großen und die kleinen, über kurz oder lang werden Ihnen die immer
wieder irgendwo über den Weg laufen.
Es ist halt so, also manche Leute schreiben halt, nehmen halt diese
Abkürzung für eine Menge von Formeln.
Also im Allgemeinen bei Ableitungen, man hat so eine Menge von
Hypothesen oder Prämissen, das ist einfach so eine Menge von Formeln,
wo man sagen will, angenommen, die habe ich schon bewiesen, was kann
ich denn jetzt noch beweisen?
Und dann eine Ableitung einer neuen, einer Formel Groß G, aus einer
Formel Menge Gamma, ist einfach, also jetzt ein Beweis mit den
zusätzlichen Hypothesen aus Gamma, das ist einfach eine Liste von
Formeln, Formel G1, Formel G2 bis Formel Gn, mit der Eigenschaft, also
man möchte G abgeleitet haben, also G soll in der Liste vorkommen und
typischerweise halt am Ende, weil man dann aufhört, wenn man nur G
ableiten will.
Und jede Formel in der Liste darf man aber nicht einfach willkürlich
hinschreiben, sondern was man hinschreiben darf in so eine Liste von
Formeln, sind erstens die Aktionen.
Jedes Aktionen dürfen Sie einfach hinschreiben, zweitens jede Prämisse
dürfen Sie einfach hinschreiben und drittens, Sie dürfen eine Formel
hinschreiben an einer Stelle I, wenn es weiter vorne in der Liste zwei
andere Formeln gibt, sodass mit Modus ponens aus den Formeln an den
Stellen I1 und I2 sich die Formel an Stelle I ergibt.
Also an der Stelle I1 muss stehen, etwas von der Bauart G impliziert H
und an der Stelle I2 etwas von der Bauart G und dann dürfen Sie an der
Stelle I hinschreiben H.
Das ist alles.
So und wenn Sie keine Hypothesen brauchen, wenn die Prämissenmenge
leer ist, dann schreibt man einfach dieses Zeichen hier mit einem
senkrechten und einem kleinen senkrechten und einem waagrechten
Strich, nicht zwei waagrechte, wie bei Istautologie, alle Bewertungen
erfüllen das.
Und dann heißt diese Formel Theorem dieses Kalküls, also alles, was
Sie mit Hilfe von Modus ponens beliebig oft angewendet auf irgendwas,
was Sie letzten Endes aus den Axiomen ableiten können.
Das sind die sogenannten Theoreme.
Hier ist einer und wirklich der einzige komplette Beweis dafür, dass
man irgendeine Formel ableiten kann.
Also P impliziert P, ist ja eine Tautologie.
Und wenn unser Kalkül vernünftig ist, dann sollten wir das jetzt
ableiten können als Formel.
Und Sie sehen schon, das wird auch schnell unhandlich.
In der ersten Zeile habe ich eine Formel hingeschrieben und meine
Behauptung ist, dass es ein Axiom, das ist von der Bauart der Axiome
in dieser zweiten Teilmenge aller Axiome.
Gucken Sie mal, für welche Formel Sie da was einsetzen müssen.
Also das ist ein Axiom, darf ich einfach hinschreiben.
In der zweiten Zeile steht etwas, das ist auch von der Bauart Axiom
aus der ersten Teilmenge von Axiomen.
Darf ich einfach hinschreiben.
So und wenn Sie sich das angucken, dann steht hier in der ersten, in
der zweiten Zeile eine Formel G und in der ersten Zeile steht eine
Formel von der Bauart G impliziert eine andere Formel H.
Und dann sind wir in der Situation, dass wir Modus ponens anwenden
dürfen auf die beiden Formeln, die in den Zeilen 1 und 2 stehen.
Das ist hier mit MP 1, 2 gemeint.
Und Modus ponens sagt einem, na dann darf ich das, was hier hinten in
der ersten Zeile steht, hinter dem Implikationsverhältnis, das darf
ich auch einfach hinschreiben und das gilt dann auch als bewiesen.
Also dann haben wir die Formel in Zeile 3 bewiesen.
Dann schreibe ich in Zeile 4 nochmal ein Axiom hin.
Das passt wieder zu dieser Struktur Teilmenge 1.
Und dann wieder in Zeile 4 eine Formel G und in Zeile 3 eine Formel,
da steht vorne G und hinten eine andere Formel H.
Und dann dürfen Sie wieder Modus ponens anwenden und folgern ja das,
was hier hinten als H steht in der dritten Zeile.
Das dürfen Sie einfach hinschreiben.
Und dann haben Sie das auch bewiesen in diesem Kalkül.
Und das war es.
So und was hier rausgekommen ist, ist wieder eine Tautologie.
Und das kann man für andere Beispiele auch machen.
So und warum ist das alles so nett?
Beobachtung 1 Wenn G impliziert H und G beides Tautologien sind, dann
ist H auch eine Tautologie.
Und das heißt mit anderen Worten, wenn Sie Modus ponens auf zwei
Tautologien anwenden, dann kommt wieder eine Tautologie raus.
Das ist das, was da steht.
Modus ponens macht aus zwei Tautologien eine dritte Tautologie.
Und dass das so ist, da guckt man sich einfach an, wenn G Tautologie
ist, heißt das für jede Interpretation Auswertung von G ist immer
wahr.
Und das hat zur Folge, dass wenn G impliziert H auch immer wahr ist,
dann muss auch H immer wahr sein.
Und das heißt dann H ist Tautologie.
Eine ganz einfache Überlegung.
Also Modus ponens macht aus Tautologien Tautologien.
Und die Axiome, habe ich gesagt, sind auch alle Tautologien.
Und deswegen alles, was Sie in diesem Kalkül ableiten können, alle
Theoreme, die Sie ableiten können aus den Axiomen mit Modus ponens,
das werden garantiert alles Tautologien sein.
Das ist der leichte Teil.
Tatsächlich gilt auch die Umkehrung, wenn Sie irgendeine
aussagenlogische Formel haben, egal wie gebaut, egal wie kompliziert,
wenn das eine Tautologie ist, dann immer gibt es einen mehr oder
weniger langen Beweis in diesem Kalkül.
Sie müssen nur Axiome hinschreiben, ab und zu mal Modus ponens
anwenden, noch ein paar Axiome, nochmal Modus ponens.
Sie werden diese Tautologie beweisen können in dem Kalkül.
Das ist Mehrarbeit, die wir hier nicht machen, weil wir hier bei
Grundbegriffen sind und nicht in formale Systeme.
Aber also zusammen mit dem vorher, was leicht zu sehen war, folgt.
Also eine Formel ist Tautologie genau dann, wenn sie in diesem Kalkül
beweisbar ist.
Und solche Äquivalenz-Aussagen sind immer nett, insbesondere, wenn das
nicht so ganz offensichtlich äquivalente Dinge sind, denn naja, je
nachdem, was man zu tun hat, manchmal ist vielleicht der eine Zugang
leichter.
Also Sie haben was und Sie wollen beweisen, es ist eine Tautologie.
Manchmal ist es vielleicht einfacher, alle Bewertungen, alle
Interpretationen anzugucken.
Manchmal ist es vielleicht einfacher, einen Beweis in dem Kalkül zu
suchen.
Das ist nicht ganz naheliegend, wie Sie an diesem Ding hier gesehen
haben.
Ich meine, warum schreibe ich jetzt gerade diese Axiome hin?
Das fällt völlig vom Himmel her.
Nicht nur für Sie, auch für mich.
Da müssen Sie schon viele Übungen haben, um zu sehen, ja, da ist ja
klar, wie ich diese Formel beweise.
So, aber eine Maschine tut sich da ja vielleicht manchmal, manchmal,
manchmal leichter.
So, also das ist ganz nett.
So, und dann gibt es drei Formeln noch.
Quatsch, drei Folien in diesem Kapitel, wo Sie nachlesen können, wenn
Sie Lust dazu haben, zumindest eine Andeutung, warum sowas nützlich
ist, so ein Kalkül zu haben.
Und die lassen wir hier aber einfach weg.
Das wird ein bisschen sehr technisch.
Es ist kein Hexenwerk.
Gucken Sie es sich mal an, wenn Sie Lust haben.
Aber das ist jetzt nichts, worauf wir in den Übungsaufgaben oder in
der Klausur irgendwie groß rumreiten werden.
Was wirklich wichtig ist, also erstens, Sie wissen, was Aussagen
logische Formeln sind.
Wie sind sie aufgebaut?
Und das ist so ein syntaktischer Begriff.
Und wie ist das mit Interpretationen?
Wann sind sie wahr, wann sind sie falsch?
Das ist ein semantischer Begriff.
Sie haben gesehen, wie man sozusagen Beweise führen, formalisieren
kann.
Und Sie werden es dann später sehen in dem Kapitel über
Prädikatenlogik.
Das kann man noch verallgemeinern.
Da wird dann alles ein bisschen schwieriger.
Also manches wird viel schwieriger.
Aber was Sie jedenfalls üben sollten, ist irgendwie so mit Bullshit
-Funktionen rummachen.
Sie sollten wissen, was bedeutet es, eine Formel ist erfüllbar, eine
Formel ist Tautologie.
Und Sie sollten üben, jetzt nicht in so einem Kalkülenbeweis unbedingt
zu führen, aber so allgemein präzise zu formulieren, präzise zu
argumentieren, Beweise zu führen.
Da werden Sie dann am Freitag in der großen Übung auch noch wieder
Beispiele sehen.
Und diese Beispiele werden zu tun haben mit vollständiger Induktion.
Also jetzt haben wir Aussagenlogik fertig gemacht.
Machen wir als nächstes vollständige Induktion soweit fertig, dass wir
es dann in Zukunft in einigen Varianten bequem anwenden können.
Gut.
Grob, die Beweisstruktur für einen Standardbeweis, vollständige
Induktion sieht also so aus.
Man hat so eine Aussage zum Beispiel für jede nicht negative ganze
Zahl, klein n, hat man so eine Aussage a n.
Und man möchte gerne beweisen, für jedes n die Aussage a n ist wahr.
Dann ist eine Möglichkeit das zu tun, eben vollständige Induktion,
indem man in der harmlosen Variante beweist, erstens, wenn ich den
Fall n gleich 0 angucke, die Aussage a 0, dann kann ich mich davon
überzeugen, die Aussage ist wahr.
Das muss man dann halt erstmal tun.
Das heißt dann Induktionsanfang.
Und das zweite, was man immer hat, ist so ein Induktionsschritt.
Was muss man da tun?
Da muss man für jedes n beweisen a n impliziert a n plus 1.
Das heißt dann Induktionsschritt.
Und Sie erinnern sich an dieses Video da, wenn Sie so Steinchen
nebeneinander, Dominosteine hinstellen und einer nach dem anderen
fällt um, weil einer den nächsten umschmeißt.
Der Induktionsanfang ist sozusagen explizit, Sie werfen den ersten
Stein um.
Und der Induktionsschritt ist sozusagen, Sie beweisen an jeder Stelle
zwei aufeinanderfolgende Steinchen stehen so.
Wenn einer umfällt, dann kippt er so, dass er den nächsten umschmeißt.
Die Abstände passen überall.
So.
Und wie beweist man für jedes n a n impliziert a n plus 1?
Sie nehmen jetzt nicht für jedes n das Beweis, in dem ich irgendein
beliebiges n hernehme, nichts weiter weiß und beweise a n impliziert a
n plus 1.
Und wie beweise ich, dass die Implikation gilt?
Na, der einzige Fall, wo man was tun muss ist, a n ist wahr.
Das ist dann die Induktionsvoraussetzung.
Von der nimmt man jetzt an, a n ist wahr.
Für irgendein beliebiges n.
Und da muss man beweisen, a n plus 1 ist jetzt dann auch wahr.
Das ist vollständige Induktion.
Haben wir an mindestens einem Beispiel durchgeführt.
In der Übung sehen Sie ein weiteres.
Und jetzt gibt es aber noch so ein paar Varianten, mehr oder weniger
harmlos.
Also eigentlich sind sie alle harmlos.
Und manchmal ist es bequem, so ein kleines bisschen, also sich schon
mal klar gemacht zu haben, von diesem strikten Schema, man kann ein
kleines bisschen abweichen und immer noch alles ist gut.
Zum Beispiel, einfachster Fall, man hat nicht für ab n gleich 0
irgendeine Aussage, sondern nur ab n gleich 1.
Dann darf man auch vollständige Induktion machen und dann fängt man
halt mit dem Induktionsanfang nicht bei 0 an, sondern bei 1.
Also dann zeigen Sie, a 1 ist wahr und dann für jedes n größer gleich
1, a n impliziert a n plus 1.
Das können Sie auf den Originalfall zurück prügeln, indem Sie einfach
die Aussagen anders durchnummerieren.
Und die Aussage für n gleich 1, die Aussage a 1 ist b 0 und die
Aussage a 2 ist b 1 und so und dann passt das einfach ins Schema.
Also manchmal geht es halt nicht bei 0 los, sondern später.
Ansonsten alles gleich.
Dann manchmal, wenn man den Induktionsschritt macht, ist es nett, wenn
man für den Beweis von a n plus 1 als Induktionsvoraussetzung
sozusagen nicht nur a n hat, sondern mehr.
Also vielleicht noch a n minus 1, aber wenn Sie das so aufschreiben,
passen Sie auf, für kleine n könnte der Index negativ werden und dann
ist das alles Quatsch wahrscheinlich.
Da muss man dann also ein bisschen vorsichtig sein beim Formulieren,
dass das alles sauber ist, wie beim Programmieren.
Wenn Sie ein Array indizieren, waren im Programmieren schon Arrays
dran?
Nein, kommt aber bald.
Da müssen Sie auch aufpassen.
Und das führt auch manchmal dazu, dass Sie nicht mehr nur einen
Induktionsanfang haben für n gleich 0, sondern Sie müssen vielleicht
explizit für 0 und 1 und 2 irgendwie so 3 oder 4 oder wie viel auch
immer Induktionsanfänge machen, so die ganz kleinen Werte, so mehrere
explizit abhandeln und dann erst ab, was weiß ich, 5 oder wo auch
immer, können Sie dann immer sich so weiterhangeln und Bezug nehmen
auf frühere Aussagen, die wahr sind.
Typischerweise Induktionsanfänge sind meistens ganz leicht.
Also ich glaube nicht, dass wir Ihnen einen Induktionsbeweis
unterjubeln, jedenfalls nicht bewusst, wo der Induktionsanfang richtig
schwer ist.
Wo man manchmal Probleme hat, ist beim Induktionsschritt.
Also stellen Sie sich vor, Sie haben Aussagen b0, b1, b2 und wollen
halt durch Induktion beweisen, für alle n, bn ist wahr und dann stehen
Sie also im Induktionsschritt vor der Aufgabe, für ein beliebiges n zu
zeigen.
Aus bn folgt bn plus 1 und es klappt irgendwie nicht.
Es sieht irgendwie zu schwer aus und es ist vielleicht tatsächlich
auch einfach zu schwer in einem präzisen Sinne.
Was kann man da tun?
Ganz naiv, wie wird das leichter, einzusehen, dass bn plus 1 doch
gilt?
Was wäre hilfreich?
Wie wird es leichter, diese Implikation zu beweisen?
Was würden Sie ändern, gerne ändern wollen?
Würden Sie gerne bn plus 1 schwerer machen?
Nicht.
Wer würde gerne bn aussagekräftiger machen?
Auch keiner?
Einer?
2, 3, 4, 5, 10?
Ja, also diese Implikation zu beweisen, wird leichter, wenn in bn mehr
drinsteht, was Sie verwenden können, was alles wahr ist.
Und jetzt Mitteilungen, nur so am Rande, das geht jetzt hier nicht auf
den Folien.
Es kommt tatsächlich vor, also Sie können natürlich nicht einfach nur
in eine Formel bn zusätzlich was reinschreiben.
Das geht nicht.
Aber manchmal hilft es tatsächlich, Sie sollen etwas beweisen durch
vollständige Induktion und diese Aussage und Sie kriegen es nicht hin.
Und was dann manchmal hilft, ist die Aussage, was Sie beweisen müssen,
aussagekräftiger zu machen für alle n, also da zusätzliche Dinge
reinzuschreiben, die Sie dann auch noch beweisen müssen.
Aber manchmal hilft das, denn Induktionsanfänge bleiben meistens
leicht.
Und bei der Implikation steht dann in bn, da steht nämlich nicht das
Original bn, sondern zusätzliche Information und die hilft Ihnen dann,
um bn plus 1 zu beweisen.
Da müssen Sie natürlich, haben Sie jetzt auch nicht mehr nur bn,
sondern da auch für n plus 1 die zusätzlichen Dinge, die Sie auch noch
beweisen müssen.
Aber wenn Sie Glück haben, ist das kein Problem.
Also indem Sie die Aussagen kräftiger machen, wird hier die
Induktionsvoraussetzung so viel stärker, dass Sie erstens das beweisen
können, was Sie sowieso beweisen wollen und das, was Sie zusätzlich
beweisen müssen, geht auch noch.
Das kommt vor.
Mehr hinschreiben, was man beweisen muss, dann wird die Induktion
leichter.
Kommt vor.
Mehrfach.
Der andere Ausweg ist, also wenn Sie sich die Steinchen vorstellen,
einer schmeißt den anderen um.
Naja, Stein Nummer 17 wird umfallen, aber warum sollen Sie dafür nur
argumentieren dürfen, dass Stein Nummer 16 umgefallen ist?
Die anderen vorher sind auch schon alle umgefallen, salopp gesagt.
Warum kann man das nicht auch mit verwenden?
Antwort, ja, man kann es mit verwenden.
Also
stellen Sie sich vor, also für die BN-Induktion klappt nicht.
Stellen Sie sich vor, Sie machen neue Aussagen AN und zwar so, also A0
ist einfach B0, salopp gesagt.
A1 ist B0 und B1.
A2 ist B0 und B1 und B2.
A3 ist B0 und B1 und B2 und B3 und, und, und, und.
Kriegen Sie neue Formeln A0, A1, A2.
Also im Allgemeinen AN plus 1 ist äquivalent zu AN und BN plus 1.
Oder anders gesagt, AN ist die Aussage für jedes i, nicht negative
ganze Zahlen, mit i kleiner gleich N ist BI wahr.
Da haben Sie neue Aussagen und dann können Sie versuchen, die mit
vollständiger Induktion zu beweisen.
Also und stellen Sie sich vor, das gelingt.
Also wenn Sie wissen, A0 ist wahr, A1 ist wahr, A2 ist wahr.
Dann offensichtlich die Formeln, für die Sie sich eigentlich
interessieren, sind auch wahr.
B0 muss dann wahr sein, wenn A0 wahr ist.
Das ist das Äquivalent.
B1 muss auch wahr sein, wenn A1 wahr ist.
B2 muss wahr sein, wenn A2 wahr ist und, und, und, und.
Also wenn es Ihnen gelingt zu beweisen, die AN sind alle wahr, dann
die BN sind auch alle wahr.
Sie haben ihr Ziel erreicht.
Und es ist aber auch nicht schwerer, inhaltlich, denn wenn die BI alle
wahr sind, dann sind die AI auch schon alle wahr.
Also das wird auch nicht, das kann nicht schwerer sein.
Also machen wir das.
Also die Aussage AN ist jetzt für jedes i aus N0, für i kleiner gleich
N, BI ist wahr.
Und jetzt wollen wir das mit vollständiger Induktion, wollen wir
beweisen, die AN sind wahr.
Was muss man da tun?
Man muss beweisen, A0 ist wahr, A0 ist aber einfach B0.
Also im Induktionsanfang müssen Sie sagen, B0 ist wahr.
Das ist genauso wenig, als würden Sie einfach Induktion über die BN
machen.
Das wird nicht schwerer.
Und was ist im Induktionsschritt?
Da müssen Sie zeigen, wenn AN wahr ist, dann ist auch AN plus 1 wahr.
AN sagt, B0 bis BN sind alle wahr.
AN plus 1 sagt, B0 bis BN und BN plus 1 sind alle wahr.
Also Sie müssen jetzt zeigen,
Voraussetzung, B0 bis BN sind wahr.
Sie müssen beweisen, B0 bis BN plus 1 sind wahr.
Um das zu beweisen, da müssen Sie also beweisen, immer noch B0 bis BN
sind wahr und außerdem BN plus 1.
Dass B0 bis BN wahr sind, das ist exakt das, was in der
Induktionsvoraussetzung steht.
Da muss man nichts weiter machen.
Das einzige, was man wirklich tun muss, ist BN plus 1 beweisen.
Das ist also genau das, wo man im Originalbeweis gescheitert ist.
Aber was ist jetzt die Induktionsvoraussetzung?
Die Induktionsvoraussetzung ist, B0, B1 bis BN sind alle wahr.
Also Sie dürfen jetzt im Induktionsschritt ausnutzen, nicht nur BN ist
wahr, sondern Sie dürfen B0 bis BN alle benutzen.
Und dann haben Sie es vielleicht einfacher.
Und Sie werden in der großen Übung am Freitag ein Beispiel sehen.
Da kommen Sie nur so ans Ziel sozusagen.
Was heißt nur so?
Wir haben jetzt den allgemeinen Fall auf den speziellen Fall
zurückgeprüft.
Es ist nicht wirklich allgemeiner, aber in der Praxis manchmal ist es
einfach bequemer.
Also ab sofort.
Wenn Sie einen Induktionsbeweis führen und Sie wollen für N plus 1 die
Aussage zeigen, dann dürfen Sie nicht nur die Aussage für N benutzen,
sondern auch für alle kleineren Werte ab Null.
Wenn es Ihnen hilft, nehmen Sie es einfach.
Es ist legal.
Gut.
Achso, und habe ich das gesagt?
Das nennt man manchmal auch starke Induktion.
Steht gar nicht auf den Folien.
Gut.
Und jetzt noch mal kurz ein paar Worte zu einer ersten naheliegenden
Anwendung von vollständiger Induktion.
Wo wir eigentlich einiges nachholen müssten.
Nämlich induktive Definitionen.
Haben wir ja schon öfter mal hingeschrieben.
So nach dem Motto hier zum Beispiel Potenzen von Wörtern.
W hoch 0 ist das leere Wort und für jedes N, W hoch N plus 1 ist W
hoch N.
Konkateniert mit W.
Wieso ist denn das überhaupt erlaubt?
Wieso wird denn hier vernünftig etwas festgelegt?
Also für die Definition hier bei N plus 1, man braucht schon die
Definition für N und so.
Naja, man beweist durch vollständige Induktion im Zweifelsfalle, also
macht man dann nicht, weil es ist irgendwie klar, dass das vernünftig
ist.
Behauptung für jedes N aus N0, W hoch N wird ordentlich definiert.
Da haben Sie eine Aussage für jedes N und die können Sie beweisen
durch vollständige Induktion.
Induktionsanfang für N gleich 0.
W hoch N wird festgelegt.
Ja, in der Tat.
W hoch 0 wird hier explizit eindeutig festgelegt.
Alles gut.
Und Induktionsschritt...
Induktionsschritt wäre angenommen, W hoch N ist schon eindeutig
präzise definiert.
Man zeige, W hoch N plus 1 ist dann auch eindeutig ordentlich
definiert.
Ja, das ist dann genau die zweite Zeile, die das sicherstellt.
Und deswegen per vollständiger Induktion, man weiß dann für alle N, W
hoch N wird eindeutig präzise definiert.
Widerspruchsfrei.
Also immer wenn man sowas hinschreibt, die Tatsache, dass da die
Definition sinnvoll ist, von der kann man sich überzeugen, indem man
noch mal im Gedanken durchgeht, vollständige Induktion.
Und bei so einer induktiven Definition ist es dann irgendwie
offensichtlich.
Induktionsanfang und Induktionsschritt, alles kein Problem.
Damit Sie nicht glauben, alles wäre so banal, gucken wir uns noch eine
andere induktiv definierte Funktion an.
Das ist die sogenannte Ackermann-Funktion.
Da gibt es verschiedene, leicht verschiedene Varianten.
Das hier ist die Definition von Peter.
Also die Ackermann-Funktion ist eine Funktion, die hat zwei Argumente
aus N0 und liefert einen Funktionswert in N0.
Und die ist so festgelegt, wenn das erste Argument 0 ist, dann der
Funktionswert ist in Abhängigkeit vom zweiten Argument Y, einfach Y
plus 1.
Also A von 0 und 3 ist einfach 4.
Wenn das erste Argument nicht 0 ist, also irgendwie von der Form X
plus 1 für irgendein X aus N0, aber das zweite Argument ist 0, dann
steht hier, A von X plus 1 und 0 ist das gleiche wie A von X und 1.
Also A von 1 und 0 ist das gleiche wie A von 0 und 1 und das 2 zum
Beispiel.
So, damit hat man also den Fall, erstes Argument 0 hat man was
hingeschrieben, für den Fall zweites Argument 0 hat man was
hingeschrieben, aber man begibt sich hier so ein bisschen auf
erstmal...
man muss vorsichtig sein, denn hier hinten, da stehen jetzt bei A, X,
1, das sind zwei Argumente und wenn X groß ist, hat man jetzt hier
hinten zwei Argumente, die nicht 0 sind.
So, und wenn zwei Argumente nicht 0 sind, dann sagt einem hier die
dritte Zeile, was zu tun ist.
A von X plus 1 und Y plus 1 ist A von erstes Argument X, 1 kleiner,
und zweites Argument ist A von X plus 1 und Y.
Hinschreiben kann man viel, wenn der Tag lang ist.
Die Frage ist, ist das eine vernünftige Definition?
Naja, wenn das Ding Ackermannfunktion heißt und Ihnen wieder über den
Weg laufen wird, zum Beispiel in...
Also eine Art Umkehrfunktion der Ackermannfunktion läuft Ihnen im
nächsten Semester über den Weg in Algorithmen 1 wahrscheinlich.
So, was ist das für eine Funktion?
Also erstens, das merken Sie auch schnell selber, seien Sie ein
bisschen vorsichtig, also versuchen Sie das nicht allzu oft für...
mit Papier und Bleistift.
Wenn Sie zum Beispiel A von 2 und 2 ausrechnen, was ist das?
Also A von 2, 2, da muss man hier die dritte Zeile anwenden, das ist
also A von 1, das X dann.
2 ist X plus 1, A von 1 und A von X plus 1 ist 2 und Y 1.
Und dann hat man hier A von 2 und 1 stehen, was ist das?
Da muss man auch wieder die zweite Zeile anwenden, das ist A von 1 und
A von 2 und 0.
A von 2 und 0 ist A von 1 und 1.
A von 1 und 1 ist A von 0 und A von 1 und 0.
Und irgendwann ist man bei A von 1 und 5 und dann geht es noch eine
Zeit lang weiter und irgendwas kommt raus.
Achso.
Also A von 2 und 2 ist noch harmlos.
Ist das groß genug?
Schauen wir mal.
Hier ist ein kleines Programmchen.
Da können Sie zwei Argumente X und Y hinschreiben und dieses ganze A
von A von A von das habe ich da alles in der Ausgabe mal weggemacht,
immer nur die Listen von Argumenten irgendwie.
Und dann, also A von 2 und 2 ist A von 1 und A von 2 und 1 und A von 2
und 1 ist A von 1 und 2 und und das geht, rechnen Sie und rechnen Sie
und rechnen Sie und rechnen Sie.
Nach 27 Schritten kommt 7 raus.
Und wir können auch mal A von 2 und 5 ausrechnen.
Das dauert 90 Schritte.
90 Mal werten Sie irgendwas aus und am Ende kommt 13 raus.
Sehr schön, ja.
12 traue ich mich glaube ich auch noch.
377 Schritte und es kommt 27 raus.
Na gut.
Nehmen wir mal erst das Argument 3.
A von 3 und 0.
Das dauert schon eine Zeit, da kommt 5 raus.
A von 3 und 1 dauert 106 Schritte, da kommt 13 raus.
Und wir können jetzt mal, warten Sie mal, wo habe ich denn das?
Nirgends?
Doch, da.
Jetzt wenn man die ganzen Ausgaben zwischendurch mal weglässt.
Also wenn das erste Argument 2 ist, dann für 0 kommt 3 raus, für 1
kommt 5 raus, für 2 kommen 7 raus, dann 9, dann 11, dann 13, dann 15,
dann 17.
Das dauert eine ganze Zeit, aber die Funktionswerte, die rauskommen,
wenn das erste Argument 2 ist, sind jetzt noch nicht so aufregend.
Dann nehmen wir mal als erstes Argument 3 und gucken, was da für 0, 1,
2 als zweites Argument rauskommt.
Da merkt man, das dauert schon ein bisschen.
Und also die Werte, die rauskommen sind 5, 13, 29, 61, 125, 253, 509,
1021.
Sieht jemand was?
Ja, genau.
Das sind immer drei weniger als eine Zweierpotenz.
2 hoch 3 minus 3, 2 hoch 4 minus 3, 2 hoch 5 minus 3, 2 hoch 6 minus
3.
Das sind im Wesentlichen die Zweierpotenzen minus 3.
Das sieht man auch noch und das kann man auch beweisen durch
vollständige Induktion.
Vorausgesetzt, man weiß auch Formeln für den Fall, erstes Argument ist
2 und 1, aber die sieht man leicht und beweist sie auch durch
vollständige Induktion.
Ja, und dann versuchen wir doch mal Ackermann von 4 und 0.
107 Schritte, es kommt 13 raus.
Und dann versuchen wir mal Ackermann von 4 und 1.
Das sieht irgendwie nicht schön aus.
Was ist denn hier los?
Ich habe hier noch ein anderes Programm.
Das gibt nicht diese ganzen Listen immer zu aus, sondern sagt nur alle
100.000 Schritte.
Ich mache übrigens immer noch was.
Und das ist hier diese erste Zahl, jetzt sind wir schon bei über einer
Million.
Und die Liste von Argumenten, da sind wir schon gleich bei 2.000.
Also ich konnte mich nicht mehr erinnern, mal bis 7,5 Millionen
Schritte laufen lassen, da kommt noch kein Funktionswert raus.
Ich kann Ihnen aber versichern, wenn man genügend Geduld hat, am Ende
kommt ein Funktionswert raus.
Die Ackermann-Funktion ist ganz vernünftig definiert.
Für jedes Paar X und Y es gibt einen Funktionswert, eindeutig
festgelegt, aber Sie wollen die nicht ausrechnen.
Also das ist so das, was Sie bitte mitnehmen.
Die Ackermann-Funktion wächst absurd schnell, also mal abgesehen da,
außer wenn das erste Argument 1 oder 2 oder 3 ist oder so.
Aber für größere erste Argumente oder 1.
und 2.
Argument gleich, sehr schnell absurd große Funktionswerte.
Die können Sie sich nicht vorstellen.
Das wächst extrem schnell.
Und die Umkehrfunktion wächst ganz extrem langsam, also Umkehrfunktion
in Anführungszeichen.
Und das kommt im zweiten Semester.
Ja, aber man wartet eine Million Schritte, man wartet 10 Millionen
Schritte, es ist immer noch nichts passiert.
Dann stellt man sich doch mal die Frage, ist hier wirklich immer ein
Funktionswert definiert?
Und die Antwort ist ja.
Beweist durch vollständige Induktion.
Und wenn Sie sich noch mal diese...
wo habe ich die Tabelle?
Ah, da habe ich die Tabelle.
Wenn Sie sich jetzt für jedes X eine Zeile und für jedes Y eine
Spalte, wenn Sie sich so eine große Tabelle vorstellen, dann die erste
Zeile der Definition sagt ja, die erste Zeile der Tabelle, das ist
alles eindeutig definiert.
Ja, das ist einfach Y plus 1, da muss man nicht groß drüber
nachdenken.
Alles klar.
Also für Zeile 0 ist alles gut.
Und das kann man als Induktionsanfang nehmen und zeigen, für alle
Zeilen, für jede Zeilennummer X gilt in Zeile X alle Funktionswerte A,
X, Y sind definiert.
Und dass in Zeile 0 alles gut ist, das ist der Induktionsanfang.
Und da müssen Sie sich von Zeile 1 zu Zeile 2 weiterhangeln.
Also Annahme in irgendeiner Zeile X, alles ist in Ordnung, alles ist
definiert.
Beweise auch in Zeile X plus 1, alles ist definiert.
Und wie beweist man in Zeile X plus 1, für alle Y ist alles definiert?
Man macht im Induktionsschritt für X eine vollständige Induktion über
das Y und zeigt also erstens in jeder Zeile ganz vorne, das ist
definiert.
Das ist die zweite Zeile der Definition der Ackermann-Funktion.
Der erste Eintrag ist immer in Ordnung.
Und dann jetzt die Induktion über Y in der Zeile X plus 1 nach hinten,
müssen Sie halt machen.
Und Sie haben halt die Induktionsvoraussetzung in der Zeile drüber,
alles ist in Ordnung.
Und dann haben Sie also zwei vollständige Induktionen
ineinandergeschachtet, wenn man sauber hinschreibt.
Und es kommt aber tatsächlich raus, alle Funktionswerte glasklar
definiert, alles ist gut.
Gut, also die Ackermann-Funktion wächst schnell.
Versuchen Sie nie A44 auszurechnen, Sie werden es nicht erleben.
Also und das ist wörtlich zu nehmen.
Man kann natürlich so Abschätzungen machen, wie schnell die Dinger
wachsen und A44 ist so absurd groß, das würden Sie nicht erleben.
Also wahrscheinlich, selbst wenn man beim Urknall angefangen hätte,
wäre man immer noch nicht fertig oder so.
Gut, also Ackermann-Funktion wächst schnell, ja, mitnehmen.
So, und da sehen Sie schon bei manchen Induktionen, also das war jetzt
so eine induktive Definition, da ist nicht mehr ganz so klar, was man
da tut und dass man wirklich immer das immer alles in Ordnung ist und
deswegen, also ganz so schlimme Definitionen werden wir jetzt im Laufe
der weiteren Vorlesungen nicht sehen, aber manchmal ist es schon
sinnvoll, sich Gedanken zu machen, dass das alles in Ordnung ist.
So, da ist eine Frage.
Ich habe keine Ahnung, was bei Ackermann-44 rauskommt.
Der Funktionswert ist so absurd groß, also das ist auch nicht so was
wie 10 hoch 100 oder so, das ist viel, viel, viel, viel, viel, viel
größer.
Das will man auch nicht.
Also es gibt da noch, können Sie mal nachlesen, auch wie heißt denn
das so, so eine verallgemeinerte Notation, wo Sie Exponentiation
verallgemeinern und iterieren und das dann nochmal iterieren und so.
Also es gibt dann schon Notationen, um auf kleinem Raum unvorstellbar
große Zahlen zu notieren, aber also man kann nicht sagen, das ist so
und so viel, das ist einfach eine absurd große Zahl in
Dezimaldarstellung.
Da reichen dann wieder nicht die Elementarteilchen im Universum, um
das hinzuschreiben oder so.
Und das können Sie ruhig wörtlich nehmen.
Die Zahl ist wirklich absurd groß.
Absurd.
Gut, also Induktion ist manchmal nützlich.
Gut.
Und damit haben wir dann das Kapitel Vollständige Induktion auch
abgeschlossen.
Aber das ist sowas wie Rechnen mit natürlichen Zahlen.
Das wird Sie immer wieder einholen in dieser Vorlesung, in anderen
Vorlesungen.
Im nächsten Semester in Algorithmen 1 in der letzten Klausur war ein
Beweis mit vollständiger Induktion und so.
Und bevor wir jetzt zu dem nächsten, also das übernächste Kapitel 8
ist ein längeres.
Ich weiß gar nicht, ob ich da schon einen Satz Folien mal hochgeladen
habe nach Ilyas.
Na gut, dann demnächst.
Vorneweg noch ein kleines bisschen was zu formalen Sprachen, damit wir
uns dann in Zukunft noch leichter tun, um irgendwelche Dinge
hinzuschreiben.
Und wenn wir das haben, dann haben wir, glaube ich, im Wesentlichen
alles, was wir so an grundlegenden Begriffen und Notationen brauchen.
Und dann können wir uns ein bisschen mehr dann auch Inhalten widmen.
Also im nächsten Kapitel dann so Dinge wie Darstellung von Zahlen,
Huffman -Codierung, was auch immer das sein mag und so weiter.
Zu formalen Sprachen.
Also Sie erinnern sich, eine formale Sprache ist einfach eine Menge
von Wörtern.
Und Wörter kann man konkatenieren, hintereinander schreiben.
Und jetzt, wenn Sie zwei formale Sprachen haben, dann können Sie
einfach jedes Wort aus der einen und jedes Wort aus der anderen
Sprache nehmen, alles kombinieren, die hintereinander schreiben, hat
man wieder eine Menge von Wörtern.
Und das nennt man dann das Produkt von formalen Sprachen.
Also formale Definition L1 konkateniert mit L2 und den Punkt lässt man
wieder gerne weg, ist die Menge aller Wörter W1, W2, die Sie kriegen,
indem Sie eben ein Wort W1 aus L1 und ein Wort W2 aus L2
konkatenieren.
Das ist alles.
Und weil Konkatenation von Wörtern assoziativ ist, ist es dann hier
für formale Sprachen auch assoziativ, ganz harmlos.
Also meinetwegen, wenn L1 die Wörter a und a2 enthält und L2 die
Wörter b und ab, dann das Produkt enthält also alle Wörter, die Sie
kriegen können, indem Sie irgendein Wort aus L1 und irgendein Wort aus
L2 konkatenieren.
Und wenn die beiden endlich sind, dann kann man alles hinschreiben.
Also a konkateniert mit b, a konkateniert mit dem zweiten aus L2 ab
oder eben a a konkateniert mit b oder das mit ab.
Und da sehen Sie, im Ergebnis, Sie kriegen hier drei Wörter, nicht
vier, weil es halt sein kann, dass Sie ein Wort auf verschiedene Arten
und Weisen als Produkt von zwei Wörtern kriegen.
Jetzt, das ist jetzt ein ganz vager Anfang zu etwas, was wir später
noch vertiefen werden.
Stellen Sie sich mal vor, Sie haben eine formale Sprache, da sind hier
diese Zeichenfolgen drin.
Sie ahnen schon, was das sein soll.
B, das Alphabet B enthaltet die kleinen Buchstaben a bis z, das
Alphabet Z, diese Ziffern 0 bis 9.
Dann können wir jetzt, weil wir Produkt von formalen Sprachen haben,
sowas hier hinschreiben.
S, also ja, S konkateniert mit der formalen Sprache, die nur das
Leerzeichen enthält, konkateniert mit der formalen Sprache, die nur
einzelne Zeichen enthält, konkateniert mit
etwas, was aus B stammt oder aus Z oder das leere Wort ist,
konkateniert mit einem Semikolon.
Und diese formale Sprache enthält dann also alles, was Sie kriegen,
indem Sie was aus S und ein Leerzeichen und was aus B konkatenieren.
Also zum Beispiel sowas wie int Leerzeichen x2 Semikolon.
int stammt aus S, das Leerzeichen steht hier, x stammt aus B, 2 stammt
aus Z, Semikolon stammt aus Semikolon.
Sowas können Sie hinschreiben.
Also das sieht dann zumindest mal so ähnlich aus wie Deklarationen in
Java, sagen wir mal.
Aber
natürlich rein theoretisch jedenfalls zwischen dem Typ und dem
variablen Namen in Java, da können Sie Leerzeichen hinschreiben, so
viel Sie wollen.
Das muss nicht genau 1 sein.
Das können auch 2 oder 3 oder 97 sein.
Sie werden keinem einen Gefallen damit tun, dass Sie da 97 Leerzeichen
einfügen.
Aber es ist legal.
Genauso vor dem Semikolon dürfen Leerzeichen stehen.
Und also was einem noch fehlt, um sich etwas mehr dem anzunähern, was
erlaubt ist in Java meinetwegen, wäre jetzt zu sagen sowas wie ja,
hier möchte ich jetzt beliebig viele von etwas.
Und das kriegen wir dann gleich.
Das kommt dann im zweiten Abschnitt wahrscheinlich nicht mehr heute.
Jetzt erstmal für das Produkt von formalen Sprachen.
Also da das leere Wort neutrales Element ist für Konkatenation bei
Wörtern, sieht man leicht die Menge, die formale Sprache, die nur das
leere Wort enthält, ist das neutrale Element bezüglich Produkt von
formalen Sprachen.
Beweis durch hinschreiben.
Also L konkateniert mit der Sprache, die nur Y enthält, einfach nach
Definition.
Sind also alle W1, W2 mit W1 aus L und W2 aus Y.
Also W2 muss Y sein.
Also hier steht einfach W1Y, das ist einfach W1 und die Menge aller W1
mit W1 aus L ist L.
Was sonst?
Gut.
Und natürlich andersrum genauso.
Bei Wörtern hat man dann als nächstes Potenzen definiert.
W hoch 0, W hoch 1, W hoch 2.
Das will man jetzt bei formalen Sprachen auch veranstalten.
Dann stellt sich wieder die Frage, was ist L hoch 0?
Was haben wir bei Potenzen von Wörtern genommen?
Wort hoch 0 haben wir gesagt, es weist sich als nützlich da, das
neutrale Element zu nehmen, das leere Wort.
Und das macht man dann hier analog.
L hoch 0 ist das neutrale Element für Produkt von formalen Sprachen.
Also L hoch 0 ist immer die formale Sprache, die das leere Wort
enthält und sonst nichts.
Und L hoch N plus 1 ist also Produkt von L und L hoch N.
Oder andersrum L hoch N und L.
Assoziativität.
Also hier haben wir wieder eine induktive Definition und wenn Sie Spaß
haben, können Sie sich mal überlegen, vollständige Induktion.
Hier wird für alle N vernünftig eindeutig definiert, was ist L hoch N.
Deswegen darf man das.
Und Sie können wieder wie bei Wörtern nachrechnen.
L hoch 1 ist L, L hoch 2 ist L mal L, L hoch 3 ist L mal L mal L.
Nichts Neues.
Und wenn Sie das für dieses L mit A Quadrat und B nehmen, dann L hoch
0 enthält nur Epsilon, L hoch 1 ist L, L hoch 2 enthält diese Wörter.
AA konkateniert mit AA, AA konkateniert mit BB mal A Quadrat und BB.
L hoch 3 müssen Sie halt drei Faktoren nehmen.
Jeder Faktor aus L, aber es dürfen unterschiedliche sein.
Alle Möglichkeiten.
L hoch 4 müssen Sie vier Faktoren nehmen.
Jeder aus L, alle Kombinationen, alles was rauskommt, gehört zu L hoch
4.
Und so weiter.
Noch ein Beispiel.
Nehmen Sie die formale Sprache aller Wörter der Bauart.
A hoch N, B hoch N.
Vorne sind N As und dahinter kommen dann N Bs.
Genauso viele Bs hinten wie vorne As.
Für jedes N aus N Plus.
Da gehört dann A hoch 1, B hoch 1 dazu, A Quadrat, B Quadrat, A hoch
3, B hoch 3 und so weiter.
Wenn Sie von dieser Sprache das Quadrat nehmen, also ein Produkt von L
mit sich selber, dann müssen Sie also alle Paare von Wörtern nehmen,
die beide aus L sind und die konkatenieren.
Also meinetwegen A B konkateniert mit A B oder A B konkateniert mit A
Quadrat, B Quadrat.
Oder der erste Faktor ist A Quadrat, B Quadrat oder A hoch 3, B hoch 3
und so weiter.
Dann kriegen Sie halt einen Haufen Wörter.
Fertig.
Sie haben immer vorne so ein Wort der Form A hoch N, B hoch N für
irgendein Exponent.
Also sagen wir N1 und dahinter noch so ein Wort aus der gleichen
Sprache.
Aber der Exponent kann natürlich ein anderer sein.
Sie haben da alle Wörter der Form A hoch N1, B hoch N1.
Das ist aus L.
Und dahinter ein Wort A hoch N2, B hoch N2 auch aus L.
Aber N1 und N2 müssen nicht gleich sein.
Das können ja unterschiedliche Wörter aus L sein.
So.
Und jetzt haben wir etwas doppelt definiert, weil wir ein bisschen
großzügiger sind als zum Beispiel Java.
Wenn Sie ein Alphabet haben, also sagen wir klein A, klein B, das
können Sie als Alphabet auffassen.
Und dann haben wir gesagt, ach ja, wenn ich ein Alphabet habe, A hoch
I, das sind alle Wörter der Länge I.
Sie können aber auch das Alphabet als eine formale Sprache auffassen.
Und dann haben wir jetzt hier für formale Sprachen A hoch I definiert.
Da muss man natürlich aufpassen, dass das immer noch das Gleiche ist.
Und hurra, es ist das Gleiche, wenn man hinreichend großzügig darüber
hinweg sieht und keinen Unterschied macht zwischen einem Zeichen und
einem Wort der Länge 1.
Also das ist einfach das Gleiche.
So.
Konkretinationsabschluss sind nochmal mehrere Folien.
Das prügeln wir jetzt heute nicht mehr durch, würde ich sagen.
Dann soll es das für heute gewesen sein.
Schönen Dank.