Di, 14.10.2008: S.1-29
Organisatorisches;
Paradoxien;
Grundsätzliches zu formalen Beweisen;
Beweise in der Informatik;
Syllogismen;
Cantors naiver Mengenbegriff und das Russelsche Paradoxon
Do, 16.10.2008: S.30-55
Grundbegriffe der Mengenlehre;
Mengenalgebra, Venn Diagramme;
Größe von Mengen;
Tupel, kartesische Produkte, Relationen;
Wörter und Sprachen
Di, 21.10.2008: S.56-64
Funktionen;
Gleichmächtigkeit;
Abzählbare und überabzählbare Mengen
Do, 23.10.2008: S.65-72
Vollständige Induktion über den natürlichen Zahlen;
Rekursive Definitionen von Funktionen auf den natürlichen Zahlen;
Rekursiv definierte Mengen
Di, 28.10.2008: S.73-84
Vollständige Induktion über den Aufbau von rekursiv definierten Mengen;
Rekursiv definierte Funktionen über rekursiv definierten Mengen;
Beispiele: NAT, TAR, TARV
Do, 30.10.2008: S.85-112
Syntax der WHILE-Sprache;
Semantik der WHILE-Sprache;
Existenz nicht berechenbarer Funktionen;
Syntax der Aussagenlogik;
Syntaxbäume, Subformeln;
Rekursive Definitionen über den Aufbau vonFormeln;
Semantik der Aussagenlogik
Di, 4.11.2008: S.113-152
Wahrheitstafeln;
Beispiele von Formalisierungen in der Aussagenlogik;
Anwendungsbeispiel Data-Mining;
Erfüllbarkeit;
Folgerungen;
Korrektheit formaler Argumente;
Anwendung Planungsprobleme (Minesweeper)
Do, 6.11.2008: S.153-171
Anwendung Schaltkreisverifikation;
Äquivalenz;
Substitutionslemma;
Beweise per vollständiger Induktion über den Aufbau der aussagenlogischen Formeln
Di, 11.11.2008: S.172-180
Ersetzungslemma;
"Rechenregeln" für die Boolesche Algebra;
Dualitätssatz;
das algebraische Verfahren zum Testen von Äquivalenz
Do, 13.11.2008: S.181-192
Beschreibbarkeit aller booleschen Funktionen;
Adäquate Mengen von Junktoren;
Beweis der Darstellbarkeit boolscher Funktionen durchaussagenlogische Formeln;
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)
Di, 18.11.2008: S.198-218
Verfahren zum transformieren von Formeln in DNF;
Erfüllbarkeitstest mittels DNF;
Schaltkreisentwurf mit aussagenlogischen Schaltelementen;
Wiederholung: Folgerungen und Ableitungsregeln
Do, 20.11.2008: S.219-225
Beweisbarkeit und Widerspruchsfreiheit im Beweissystem ABS;
Korrektheit des Systems ABS;
Monotonie und Transitivität der Beweisbarkeit, Syntaktisches Endlichkeitslemma;
Deduktionslemma
Di, 25.11.2008: S.225d-229
Ableitbare Regeln;
Maximal widerspruchsfreie Formelmengen;
Vollständigkeit des Systems ABS
Do, 27.11.2008: S.230-241
Kompaktheitssatz der Aussagenlogik;
Kleine erfüllbarkeitsäquivalente KNF-Formeln;
Resolution;
Korrektheit und Vollständigkeit der Resolution
Di, 2.12.2008: S.242-251
DP-Algorithmus;
Hornklauseln und Hornformeln;
Streichungsalgorithmus
Do, 4.12.2008: S.252-275
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;
Wege in Graphen und transitive Hülle
Do, 11.12.2008: S.298-317
Isomorphie;
Beispiele isomorpher Strukturen;
Syntax der Logik der 1. Stufe;
Freie Variablen und Sätze;
Belegungen und Interpretationen
Di, 16.12.2008: S.318-323
Semantik der Logik der 1. Stufe: Auswertung von Termen und Formeln in Interpretationen;
Beispiele;
Erfüllbarkeit;
Koinzidenzlemma
Do, 18.12.2008: S.324-333
Beispiele von Definierbarkeit in der Logik der 1.Stufe über Graphen,den natürlichen Zahlen, Ordnungen, Geometrie;
Isomorphielemma
Di, 6.1.2009: S.334-350
Wiederholung: Syntax und Semantik der Logik der 1. Stufe;
Anwendungsbeispiel Wissensrepräsentation: Verwandtschaftsbeziehungen;
Äquivalenz;
Ersetzungslemma;
Substitutionslemma
Do, 8.1.2009: S.350-356
Aussagenlogische Äquivalenzen in der Logik der 1. Stufe;
Vertauschbarkeit von Quantoren und Junktoren;
Adäquatheit
Di, 13.1.2009: S.357-374
Pränexe Normalform;
die Relation φ(A);
Algorithmische Auswertung von Formeln in endlichen Strukturen
Do, 15.1.2009: S.375-399
Relationale Datenbanken und SQL;
Folgerungen und Ableitungsregeln;
das Beweissystem σ-BS
Di, 20.1.2009: S.399a-412
Korrektheit von σ-BS;
Vollständigkeitssatz für σ-BS;
Kompaktheitssatz für die Logik der 1. Stufe;
Das Halteproblem in Java
Do, 22.1.2009: S.413-431
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;
Semi-Entscheidbarkeit
Di, 27.1.2009: S.432-470
Berechenbare Funktionen;
Die Church-Turingsche These;
Syntax und Semantik von GOTO-Programmen;
G-Berechenbarkeit und G-(Semi-)Entscheidbarkeit
Do, 29.1.2009: S.471-492
Turingmaschinen;
Äquivalenz von G-Berechenbarkeit und T-Berechenbarkeit
Di, 3.2.2009: S.493-507
Mehrband- und nichdeterministische Turingmaschinen;
Programmiertechniken für GOTO-Programme (Hintereinanderausführung,Unterprogramme);
G-Berechenbare Funktionen auf den natürlichen Zahlen;
Rekursiv definierte Funktionen auf den natürlichen Zahlen
Do, 5.2.2009: S.508-517
Gödelisierung;
Die Unentscheidbarkeit des Halteproblems;
Universelle Programme;
Semi-Entscheidbarkeit des Halteproblems
Di, 10.2.2009: S.518-521
Die Unentscheidbarkeit der Logik der 1. Stufe
Do, 12.2.2009:
Kurze Wiederholung der gesamten Vorlesung
Last Modified: Mi 28. Jan 11:18:39 CET 2009
Martin Grohe
