Dieser Audiobeitrag wird von der Universität Erlangen-Nürnberg präsentiert.

Uns fehlt ein Nachtrag zum Thema Induktion. Ich hatte Ihnen ja in der letzten Sitzung in

dieser Reihenfolge erklärt, die übliche Induktion auf natürlichen Zahlen, die

Course of Values Induktion auf natürlichen Zahlen und dann etwas, was völlig anders aussah,

nämlich Induktion über Grammatik. Das schreibe ich jetzt nicht nochmal an, weil es doch ein

bisschen länglich ist. Steht ja in den Notizen von letztem Mal drin. Nochmal zur Erinnerung,

Course Quatsch. Induktion über Grammatiken heißt, ich sehe mir so eine Grammatik an,

wie die für Aussagenlogik, die wir letztes Mal gesehen haben, und gewinne aus dieser Grammatik

ein Induktionsprinzip, das mir sagt, wenn ich etwas für alle Instanzen der Grammatik beweisen

will, in diesem Fall also für alle Formeln, dann habe ich so viele Klauseln in meinem

Induktionsprinzip wie in meiner Grammatik und für jede Klausel der Grammatik muss ich zeigen, wann

immer jede Instanz eines Nichtterminalen, was hier vorkommt, also hier keine, hier keine,

hier das eine Phi und einmal hier das Phi und das Psi, wann immer die meine Induktionsbehauptung

erfüllen, dann erfüllt auch die entsprechend abgeleitete Instanz hier also nicht Phi, hier

Phi und Phi, hier einfach nur a, ohne weitere Annahmen, hier Botte. Also ich habe nicht bewiesen,

dass das ein korrektes Prinzip ist. Ich habe Ihnen Induktion über natürliche Zahlen angeschrieben

und Ihnen erklärt, gut, das kann ich nicht beweisen, das ist eine Aktion. Ich habe anschließend

Cores of Values Induktion erklärt und die aber bewiesen und diese hier, das lässt sich auch

beweisen, je nachdem, wie man das jetzt alles genau definiert auf unterschiedliche Arten. Das

einfachste ist und ich führe das jetzt nicht durch, ich sage Ihnen nur, wie es geht. Das

einfache ist, man macht eine Cores of Values Induktion. Ja gut, was hat man zu zeigen? Man

hat zu zeigen, gut, ich habe alles getan, was ich laut Induktionsprinzip machen muss und will jetzt

schließen, dass für alle Formeln etwas gilt. Ich muss also jetzt etwas für alle Formeln zeigen und

behaupte, ich mache Cores of Values Induktion. Nun, man kann Induktionen ja auch über Größen

führen, die irgendwie an dem, worüber ich was beweisen will, dranhängen und in diesem Falle

über die Länge der Herleitung von Phi. Wer Lust hat, kann es mal probieren, es ist nicht schwer.

Also ich zeige praktisch, wenn ich annehme, dass alle kürzeren Herleitungen es schon tun,

dann tut es auch die Herleitung eines gegebenen Phi. So, das nur als Nachtrag. Was wir heute

eigentlich tun wollen, ist eine systematische Einführung in die Aussagenlogik, mit der wir

in der ersten Sitzung nur informell rumgespielt haben. Wer einen Tipp hat, kann sich bei mir

melden. Ich verfolge heute mal oder versuche mich dran zu halten ein System, nachdem ich die Tafeln

von vorne nach hinten beschreibe. Zwei Tafeln beschreibt man eher von hinten nach vorne. Wenn

jemand eine ganz tolle Idee hat, wie das besser geht, der sage es mir. Die sicherste Art, sich bei

Studenten beliebt zu machen, auf alle Tafeln gleichzeitig schreiben. Also Aussagenlogik. Ja,

ich hatte ja eingangs gesagt, zur Definition einer Logik gehören drei Dinge. Erstens, man

definiert die Syntax, was darf ich hinschreiben? Zweitens, die Semantik, was heißt das? Drittens,

man muss ein Beweissystem sich entwickeln. Wir fangen an mit der Syntax. Die kennen wir ja schon,

ja ich erinnere. Recall heißt, kennen wir schon. So, die Grammatik war sehr kurz. Sie besteht also

aus diesen vier Klauseln. Ich kann Phasum hinschreiben, ich kann Atome hinschreiben,

aus einem gegebenen Vorrat, Skript A von Atomen. Ich kann Formeln negieren und ich kann aus zwei

Formeln ihre Konjunktion bilden. So, dann brauchen wir ein bisschen Notation.

Erstens, die Frage ist, welche Klammern setze ich? Es gibt Leute, die sagen, und bindet stärker als

oder. Ich kann mir das nie merken. Aber das eine, was man schon sagen sollte, ist, Negation bindet am

stärksten. Also die Negation bezieht sich immer nur auf das, was direkt dahinter besteht. Ja,

dann fehlen uns ja viele vermutlich bekannte buhlische Operatoren. Also zum Beispiel können

wir ja noch nicht mal True hinschreiben, nur falsch. Das ist ein bisschen subversiv. Naja,

True ist schlicht und einfach not false. Also wahr ist nicht falsch. Dann Disjunktion. Führen wir

auch einfach als Abkürzung ein mit ganz vielen Negationen. Das ist praktisch das bekannte

De Morgan'che Gesetz. Also wir definieren Phi oder Psi als nicht, nicht Phi und nicht Psi. Also es

ist von Phi und Psi ist eins der Fall genau dann, wenn nicht beides nicht der Fall ist. Gut, wenn