Do, 15.10.2009: S.1-45
Organisatorisches;
Paradoxien;
Grundsätzliches zu formalen Beweisen;
Beweise in der Informatik;
Syllogismen;
Cantors naiver Mengenbegriff und das Russelsche Paradoxon
Grundbegriffe der Mengenlehre;
Mengenalgebra, Venn Diagramme
Di, 20.10.2009: S.45-60 Größe von Mengen;
Tupel, kartesische Produkte, Relationen;
Wörter und Sprachen; Funktionen
Do, 22.10.2009: S.61-68
Gleichmächtigkeit;
Abzählbare und überabzählbare Mengen; Vollständige Induktion über den natürlichen Zahlen
Di, 27.10.2009: S.69-74
Rekursive Definitionen von Funktionen auf den natürlichen Zahlen;
Rekursiv definierte Mengen; Vollständige Induktion über den Aufbau von rekursiv definierten Mengen;
Rekursiv definierte Funktionen über rekursiv definierten Mengen
Do, 29.10.2009: S.75-102
Beispiele: NAT, TAR, TARV
Syntax der WHILE-Sprache;
Semantik der WHILE-Sprache;
Existenz nicht berechenbarer Funktionen;
Syntax der Aussagenlogik;
Syntaxbäume
Di, 3.11.2009: S.103-138
Subformeln;
Rekursive Definitionen über den Aufbau von Formeln;
Semantik der Aussagenlogik
Wahrheitstafeln;
Beispiele von Formalisierungen in der Aussagenlogik;
Anwendungsbeispiel Data-Mining;
Erfüllbarkeit
Di, 10.11.2009: S.159-171
Äquivalenz;
Substitutionslemma;
Beweise per vollständiger Induktion über den Aufbau der aussagenlogischen Formeln
Do, 12.11.2009: S.172-182
Ersetzungslemma;
"Rechenregeln" für die Boolesche Algebra;
Dualitätssatz;
das algebraische Verfahren zum Testen von Äquivalenz
Di, 17.11.2009: S.183-196
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)
Do, 19.11.2009: S.197-218
Verfahren zum transformieren von Formeln in DNF;
Erfüllbarkeitstest mittels DNF;
Schaltkreisentwurf mit aussagenlogischen Schaltelementen;
Wiederholung: Folgerungen und Ableitungsregeln
Di, 24.11.2009: S.219-225
Beweisbarkeit und Widerspruchsfreiheit im Beweissystem ABS;
Korrektheit des Systems ABS;
Monotonie und Transitivität der Beweisbarkeit, Syntaktisches Endlichkeitslemma;
Deduktionslemma
Do, 26.11.2009: S.225a-229
Deduktionslemma; Ableitbare Regeln;
Maximal widerspruchsfreie Formelmengen;
Vollständigkeit des Systems ABS
Di, 1.12.2009: S.229a-240b
Kompaktheitssatz der Aussagenlogik;
Kleine erfüllbarkeitsäquivalente KNF-Formeln;
Resolution;
Korrektheit der Resolution
Do, 3.12.2009: S.241-251
Vollständigkeit der Resolution;
DP-Algorithmus;
Hornklauseln und Hornformeln;
Streichungsalgorithmus
Di, 8.12.2009: 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
Di, 15.12.2009: S.303-320
Syntax der Logik der 1. Stufe;
Freie Variablen und Sätze;
Belegungen und Interpretationen;
Semantik der Logik der 1. Stufe: Auswertung von Termen und Formeln in Interpretationen;
Beispiele
Do, 17.12.2009: S.321-333b
Erfüllbarkeit;
Koinzidenzlemma; Beispiele von Definierbarkeit in der Logik der 1.Stufe über Graphen
den natürlichen Zahlen, Ordnungen, Geometrie; Isomorphielemma
Di, 5.1.2010: S.333c-350
Isomorphielemma (Fortsetzung);
Wiederholung: Syntax und Semantik der Logik der 1. Stufe;
Anwendungsbeispiel Wissensrepräsentation: Verwandtschaftsbeziehungen;
Äquivalenz;
Ersetzungslemma;
Substitutionslemma
Do, 7.1.2010: S.350-356
Aussagenlogische Äquivalenzen in der Logik der 1. Stufe;
Vertauschbarkeit von Quantoren und Junktoren;
Di, 12.1.2010: S.357-374
Adäquatheit;
Pränexe Normalform;
die Relation φ(A);
Algorithmische Auswertung von Formeln in endlichen Strukturen
Do, 14.1.2010: S.375-399b
Relationale Datenbanken und SQL;
Folgerungen und Ableitungsregeln;
das Beweissystem σ-BS
Di, 19.1.2010: S.399c-426
Korrektheit von σ-BS;
Vollständigkeitssatz für σ-BS;
Kompaktheitssatz für die Logik der 1. Stufe;
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
Do, 21.1.2010: S.413-459
Semi-Entscheidbarkeit;
Berechenbare Funktionen;
Die Church-Turingsche These;
Syntax und Semantik von GOTO-Programmen
Di, 26.1.2010 S.460-481
G-Berechenbarkeit und G-(Semi-)Entscheidbarkeit
Do, 28.1.2010 S.482-492
Turingmaschinen;
Äquivalenz von G-Berechenbarkeit und T-Berechenbarkeit
Di, 2.2.2010 S.493-515b
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;
Gödelisierung;
Die Unentscheidbarkeit des Halteproblems;
Do, 4.2.2010 S.515c-520e
Universelle Programme;
Semi-Entscheidbarkeit des Halteproblems;
Die Unentscheidbarkeit der Logik der 1. Stufe
Di, 9.2.2010 S.520f-521
Die Unentscheidbarkeit der Logik der 1. Stufe
