Hier finden Sie (nach den Vorlesungen) Informationen zum Inhalt der einzelnen Vorlesungsstunden sowie gelegentlich ergänzende Bemerkungen.

1. Di, 14.10.2008:
   Einführung ins Thema und Klärung von Organisatorischem. Beginn mit Kapitel 1: Definition der Begriffe "Signatur" und "Struktur"; viele Beispiele für Strukturen; Festlegung einiger Notationen; Definition des Begriffs "Isomorphismus".
   Material: Einführung ins Thema sowie Kapitel 1, Seiten 1–9
   Weitere Lektüre: Kapitel 1 und Kapitel 3.1 in [EFT].

2. Do, 16.10.2008:
   Beispiele für Isomorphismen; Syntax der Logik erster Stufe (Terme und Formeln); Semantik von Termen
   Material: Kapitel 1, Seiten 10–24
   Weitere Lektüre: Kapitel 2 und Kapitel 3.2 und 3.3 in [EFT].

3. Di, 21.10.2008:
   Semantik von FO-Formeln; Beispiele; das Koinzidenzlemma; das Isomorphielemma
   Material: Kapitel 1, Seiten 25-37
   Weitere Lektüre: Kapitel 3.4 bis 3.6 in [EFT].

4. Do, 23.10.2008:
   Äquivalenz und Folgerung; das Substitutionslemma; die pränexe Normalform
   Material: Kapitel 2, Seiten 38-48
   Weitere Lektüre: Kapitel 3.4, 3.8 und 8.4 in [EFT].

5. Di, 28.10.2008:
   Beweis für die pränexe Normalform; termreduzierte Formeln und relationale Signaturen; EF-Spiele.
   Material: Kapitel 2 und 3, Seiten 49-65
   Weitere Lektüre: Kapitel 8.4 in [EFT], Kapitel 3.2 in [L].

6. Do, 30.10.2008:
   Das EF-Spiel auf zwei linearen Ordnungen; der Satz von Ehrenfeucht; Folgerungen.
   Material: Kapitel 3, Seiten 66-78
   Weitere Lektüre: Kapitel 3.2 bis 3.3 in [L] sowie Kapitel 2.1 bis 2.3 in [EF].

7. Di, 04.11.2008:
   Beweis des Satzes von von Ehrenfeucht; Nicht-Ausdrückbarkeits-Resultate.
   Material: Kapitel 3, Seiten 79-87
   Weitere Lektüre: Kapitel 3.4 bis 3.6 in [L] sowie Kapitel 2.2 bis 2.4 in [EF].

8. Do, 06.11.2008:
   Logische Reduktionen; der Satz von Hanf.
   Material: Kapitel 3, Seiten 88-102
   Weitere Lektüre: Kapitel 3.6 und 4.1 bis 4.2 in [L], Kapitel 8.2 in [EFT], sowie Kapitel 2.3 bis 2.4 in [EF].

9. Di, 11.11.2008:
   Schluss des Beweises des Satzes von Hanf; Hanf-Lokalität der Logik erster Stufe; der Satz von Fraïssé.
   Material: Kapitel 3, Seiten 103-108
   Weitere Lektüre: Kapitel 3.5 und 4.2 bis 4.3 in [L] sowie Kapitel 2.3 und 2.4 in [EF].

10. Do, 13.11.2008:
    Der Satz von Fraïssé; der Satz von Gaifman.
    Material: Kapitel 3 und 4, Seiten 109-119
    Weitere Lektüre: Kapitel 2.5 in [EF]

11. Di, 18.11.2008:
    Formulierung und Beginn des Beweises des Satzes von Gaifman (bis Seite 130).
    Material: Kapitel 4, Seiten 120-137
    Weitere Lektüre: Kapitel 2.5 in [EF].

12. Do, 20.11.2008:
    Abschluss des Beweises des Satzes von Gaifman; Gaifman-Lokalität der Logik erster Stufe.
    Material: Kapitel 4, Seiten 138-143
    Weitere Lektüre: Kapitel 2.5 in [EF] sowie Kapitel 4.1 bis 4.3 in [L]

13. Di, 25.11.2008:
    Gaifman-Lokalität der Logik erster Stufe; der Satz von Seese über Klassen von Graphen von beschränktem Grad
    Material: Kapitel 4, Seiten 144-159
    Weitere Lektüre: Kapitel 4.1 bis 4.3, 4.5 und 6.6 in [L]

14. Do, 27.11.2008:
    Abschluss von Kapitel 4: eine untere Schranke für Formeln in Gaifman-Normalform.
    Kapitel 5: Der Satz von McNaughton und Papert (bis Seite 174).
    Material: Kapitel 4 und 5, Seiten 160-177
    Weitere Lektüre: Kapitel 7.5 in [L];   die Originalarbeit mit der unteren Schranke für Formeln in Gaifman-Normalform: hier (eine Vorabversion ist auch hier erhältlich).
    

15. Di, 2.12.2008:
    Abschluss des Beweises des Satzes von McNaughton und Papert.
    Beginn mit Kapitel 6: Auswertung von Formeln in endlichen Strukturen; der Satz von Trakhtenbrot (Трахтенброт).
    Material: Kapitel 6, Seiten 177-186
    Weitere Lektüre: Kapitel 6.1, 6.2 und 9.1 in [L].
    

16. Do, 4.12.2008:
    Beweis des Satzes von Trakhtenbrot (Трахтенброт).
    Material: Kapitel 6, Seiten 187-198
    Weitere Lektüre: Kapitel 9.1 in [L].
    

17. Di, 9.12.2008:
    Folgerungen aus dem Satz von Trakhtenbrot.
    Beginn mit Kapitel 7: Der Vollständigkeitssatz (heute: Beweiskalküle).
    Material: Kapitel 6 und 7, Seiten 198-212
    Weitere Lektüre: Kapitel 4 in [EFT].
    

18. Do, 11.12.2008:
    Weiter mit Kapitel 7 (heute: ein Sequenzenkalkül)
    Material: Kapitel 7, Seiten 213-225
    Weitere Lektüre: Kapitel 4 in [EFT].

19. Di, 16.12.2008:
    Weiter mit Kapitel 7 (heute: ableitbare Regeln im Sequenzenkalkül; Widerspruchsfreiheit; das syntaktische Endlichkeitslemma; Formulierung des Vollständigkeitssatzes; Beweis des Vollständigkeitssatzes unter Verwendung des Erfüllbarkeitslemmas).
    Material: Kapitel 7, Seiten 226-241
    Weitere Lektüre: Kapitel 4 und 5 in [EFT].

20. Do, 18.12.2008:
    Weiter mit Kapitel 7 (heute: Vorbereitungen zum Beweis des Erfüllbarkeitslemmas).
    Material: Kapitel 7, Seiten 241-254
    Weitere Lektüre: Kapitel 5 in [EFT].

21. Di, 13.01.2009:
    Abschluss von Kapitel 7: Erfüllbarkeitslemma.
    Beginn mit Kapitel 8: Der Kompaktheitssatz.
    Material: Kapitel 7 und 8, Seiten 255-267
    Weitere Lektüre: Kapitel 6 in [EFT].

22. Do, 15.01.2009:
    Kapitel 8: Der Satz von Löwenheim und Skolem; elementare Äquivalenz und Nichtstandardmodelle der Arithmetik.
    Material: Kapitel 8, Seiten 268-286
    Weitere Lektüre: Kapitel 6 in [EFT].

23. Di, 20.01.2009:
    Abschluss von Kapitel 8: Beweis des Satzes von Skolem.
    Beginn mit Kapitel 9: Die Gödelschen Unvollständigkeitssätze (heute: Theorien und Entscheidbarkeit).
    Material: Kapitel 9, Seiten 287-296
    Weitere Lektüre: Kapitel 15-18 in [BBJ] sowie Kapitel 10 in [EFT].

24. Do, 22.01.2009:
    Arithmetisierung der Arithmetik; Definierbarkeit der berechenbaren Funktionen.
    Material: Kapitel 9, Seiten 297-307
    Weitere Lektüre: Kapitel 15-18 in [BBJ] sowie Kapitel 10 in [EFT].

25. Di, 27.01.2009:
    FO-Definierbarkeit der berechenbaren Funktionen.
    Material: Kapitel 9, Seiten 308-318
    Weitere Lektüre: Kapitel 15-18 in [BBJ] sowie Kapitel 10 in [EFT].

26. Do, 29.01.2009:
    Unentscheidbarkeit der Arithmetik.
    Material: Kapitel 9, Seiten 318-330
    Weitere Lektüre: Kapitel 15-18 in [BBJ] sowie Kapitel 10 in [EFT].

27. Di, 03.02.2009:
    Die Minimale Arithmetik.
    Material: Kapitel 9, Seiten 331-342
    Weitere Lektüre: Kapitel 15-18 in [BBJ] sowie Kapitel 10 in [EFT].

28. Do, 05.02.2009:
    Abschluss des Beweises des Gödels ersten Unvollständigkeitssatzes: Der Fixpunktsatz, Unmöglichkeit der Selbstrepräsentierbarkeit, Satz von Tarski.
    Material: Kapitel 9, Seiten 343-358
    Weitere Lektüre: Kapitel 15-18 in [BBJ] sowie Kapitel 10 in [EFT].

29. Di, 10.02.2009:
    Gödels zweiter Unvollständigkeitssatz: Konsistenzsatz; Peano-Arithmetik.
    Material: Kapitel 9, Seiten 359-371
    Weitere Lektüre: Kapitel 15-18 in [BBJ] sowie Kapitel 10 in [EFT].

30. Do, 12.02.2009:
    Beweis des Gödels zweiten Unvollständigkeitssatzes unter Verwendung des Satzes von Löb.
    Zusammenfassung der in der Vorlesung behandelten Themen. Ausblick auf weitere Themen im Bereich Logik in der Informatik sowie einige allgemeine Hinweise für die Vorbereitung auf die Prüfung.
    Material: Kapitel 9, Seiten 372-378
    Weitere Lektüre: Kapitel 15-18 in [BBJ] sowie Kapitel 10 in [EFT].
    Eine ausführliche Erklärung des im Beweis des Satzes von Löb verwendeten Arguments finden Sie auf den Seiten 235 und 236 in [BBJ].