Di, 16.10.2007: S.1-31
Organisatorisches;
Paradoxien;
Grundsätzliches zu formalen Beweisen;
Beweise in der Informatik;
Syllogismen;
Cantors naiver Mengenbegriff und das Russelsche Paradoxon
Do, 18.10.2007: S.31-52
Grundbegriffe der Mengenlehre;
Mengenalgebra, Venn Diagramme;
Größe von Mengen;
Tupel, kartesische Produkte, Relationen
Di, 23.10.2007: S.53-72
Wörter und Sprachen;
Funktionen;
Gleichmächtigkeit;
Abzählbare und überabzählbare Mengen
Do, 25.10.2007: S.73-91
Vollständige Induktion über den natürlichen Zahlen;
Rekursive Definitionen von Funktionen auf den natürlichen Zahlen;
Rekursiv definierte Mengen;
Vollständige Induktion über den Aufbau von rekursiv definierten Mengen
Di, 30.10.2007: S.94-116
Vollständige Induktion über den Aufbau von rekursiv definierten Mengen;
Rekursiv definierte Funktionen über rekursiv definierten Mengen;
Beispiele: NAT, TAR, TARV;
Syntax der WHILE-Sprache
Do, 1.11.2007: S.117-139
Semantik der WHILE-Sprache;
Existenz nicht berechenbarer Funktionen;
Syntax der Aussagenlogik;
Syntaxbäume, Subformeln;
Rekursive Definitionen über den Aufbau vonFormeln;
Definition der Semantik
Di, 6.11.2007: S.140-168
Semantik der Aussagenlogik;
Wahrheitstafeln;
Beispiele von Formalisierungen in der Aussagenlogik;
Anwendungsbeispiel Data-Mining;
Erfüllbarkeit;
Folgerungen
Di, 13.11.2007: S.191-217
Äquivalenz;
Substitutionslemma;
Ersetzungslemma;
"Rechenregeln" für die Boolesche Algebra
Do, 15.11.2007: S.218-236 ohne den Beweis von Satz 3.53
Der Dualitätssatz;
Das algebraische Verfahren zum Testen von Äquivalenz;
Beschreibbarkeit aller booleschen Funktionen;
Adäquate Mengen von Junktoren
Di, 20.11.2007: S.234-251
Beweis der Darstellbarkeit boolscher Funktionen durch aussagenlogische Funktionen;
adäquate und nicht adäquate Mengen von Junktoren;
Negationsnormalform (NNF);
Verfahren zum transformieren von Formeln in NNF;
Konjunktive und disjunktive Normalform (KNF und DNF)
Do, 22.11.2007: S.252-266
Verfahren zum transformieren von Formeln in DNF;
Erfüllbarkeitstest mittels DNF;
Schaltkreisentwurf mit aussagenlogischen Schaltelementen
Di, 27.11.2007: S.267-285
Beweisbarkeit und Widerspruchsfreiheit im Beweissystem ABS;
Korrektheit des Systems ABS;
Monotonie und Transitivität der Beweisbarkeit, Syntaktisches Endlichkeitslemma; Deduktionslemma
Do, 29.11.2007: S.286-309
Beweis des Deduktionslemmas;
Ableitbare Regeln;
Maximal widerspruchsfreie Formelmengen;
Vollständigkeit des Systems ABS
Di, 4.12.2007: S.310-324
Kompaktheitssatz der Aussagenlogik;
Kleine erfüllbarkeitsäquivalente KNF-Formeln;
Resolution;
Korrektheit der Resolution;
Der DP-Algorithmus
Do, 6.12.2007: S.325-335
Beweis der Korrektheit des DP-Algorithmus;
Vollständigkeit der Resolution;
Hornklauseln und Hornformeln;
Der Streichungsalgorithmus
Di, 11.12.2007: S.336-369
Korrektheit des Streichungsalgorithmusses;
Eigenschaften zweistelliger Relationen;
Äquivalenzrelationen und Partitionen;
Präordnungen, partielle Ordnungen, lineare Ordnungen;
Die reflexive transitive Hülle einer Relation;
Digraphen;
Anwendungsbeispiele;
Wege und Kreise in Graphen
Do, 13.12.2007: S.370-396
Wege in Graphen und transitive Hülle;
Gerichtete azyklische Graphen;
Ungerichtete Graphen;
Algebren: Gruppen, Körper, etc., Boolesche Algebren;
Symbolmengen;
Strukturen;
Isomorphie von Strukturen
Di, 18.12.2007: S.397-410
Beispiele isomorpher Strukturen;
Syntax der Logik der 1. Stufe;
Freie Variablen und Sätze
Do, 20.12.2007: S.411-419
σ-Interpretationen;
Semantik der Logik der 1. Stufe: Auswertung von Termen und Formeln in Interpretationen;
Erfüllbarkeit
Di, 8.1.2008: S.420-444
Wiederholung: Syntax und Semantik der Logik der 1.Stufe;
Koinzidenzlemma;
Beispiele von Definierbarkeit in der Logik der 1.Stufe über Graphen,den natürlichen Zahlen, Ordnungen;
Isomorphielemma
Di, 15.1.2008: S.445-477
Anwendungsbeispiel Wissensrepräsentation: Verwandtschaftsbeziehungen;
Äquivalenz;
Ersetzungslemma;
Substitutionslemma;
Aussagenlogische Äquivalenzen in der Logik der 1. Stufe;
Vertauschbarkeit von Quantoren und Junktoren
Do, 17.1.2008: S.477-513
Lemmata über die Vertauschbarkeit der Junktoren und Quantoren;
Adäquatheit;
Pränexe Normalform;
die Relation φ(A);
algorithmische Auswertung von Formeln in endlichen Strukturen;
Relationale Datenbanken und SQL
Di, 22.1.2008: S.514-540
Folgerungen und Ableitungsregeln;
das Beweissystem σ-BS;
Korrektheit von σ-BS;
Vollständigkeitssatz;
Kompaktheitssatz
Do, 24.1.2008: S.541-564
Das Halteproblem in Java;
Modellierung von von Algorithmischen Problemen als Mengen von Wörtern bzw. Funktionen auf Wörtern über endlichen Alphabeten;
Entscheidbarkeit;
Aufzählbarkeit;
Aufzählbarkeit der allgemeingültigen σ-Sätze
Di, 29.1.2008: S.566-599
Semi-Entscheidbarkeit;
Berechenbare Funktionen;
Die Church-Turingsche These;
Syntax und Semantik von GOTO-Programmen
Do, 31.1.2008: S.600-629
G-Berechenbarkeit und G-(Semi-)Entscheidbarkeit;
Turingmaschinen;
T-Berechenbarkeit impliziert G-Berechenbarkeit
Di, 5.2.2008: S.630-650
Äquivalenz von G-Berechenbarkeit und T-Berechenbarkeit;
Programmiertechniken für GOTO-Programme (Hintereinanderausführung,Unterprogramme);
G-Berechenbare Funktionen auf den natürlichen Zahlen
Do, 7.2.2008: S.651-667
Rekursiv definierte Funktionen auf den natürlichen Zahlen;
Gödelisierung;
Die Unentscheidbarkeit des Halteproblems;
Universelle Programme
Last Modified: Tue Nov 20 22:52:29 CEST 2007
Martin Grohe
