Einführung | Inhalt | Änderungen  

Skript zur Vorlesung 'Logik in der Informatik'

Einführung

Begleitend zur Vorlesung wird ein Vorlesungsskript erstellt, das nach und nach hier erhältlich sein wird.

Sollten Sie Fehler entdecken oder Anregungen haben wenden Sie sich gern per mail an Frederik Harwath.

Inhalt

  1. Einleitung (Skript)
  2. Syntax und Semantik der Logik erster Stufe (Skript, handschriftlich)
  3. Normalformen (Skript, handschriftlich)
  4. Die Auswertungskomplexität von FO in endlichen Strukturen (Skript, handschriftlich)
  5. Ehrenfeucht-Fraïssé Spiele (handschriftlich)
  6. Der Satz von Gaifman (handschriftlich)
  7. Der Satz von McNaughton und Papert (Skript, handschriftlich)
  8. Der Vollständigkeitssatz (Skript, handschriftlich)
  9. Der Kompaktheitssatz und der Satz von Löwenheim und Skolem (Skript, handschriftlich)
  10. Die Grenzen der Berechenbarkeit (handschriftlich)
  11. Gödels Unvollständigkeitssätze (handschriftlich)
  12. Literaturverzeichnis (Skript)

Änderungen

25.10.2013 Neue Version von "Kapitel 0", "Kapitel 1" und "Kapitel 2" online gestellt. Änderungen im Vergleich zur vorherigen Version: kleine Tippfehler korrigiert; Beispiel 1.10(e) ergänzt; Details in Beweis von Satz 2.4 - Behauptung 2 korrigiert
17.10.2013 Neue Version von "Kapitel 1: Syntax und Semantik der Logik erster Stufe" online gestellt. Änderungen im Vergleich zur vorherigen Version: Umstellung der Reihenfolge in Abschnitt "1.6: Das Substitutionslemma"
03.02.2012 Die Skript-Version von Kapitel 8 online gestellt; das Literaturverzeichnis aktualisiert.
28.12.2011 Die Skript-Version von Kapitel 7 online gestellt.
09.12.2011 Die Skript-Version von Kapitel 6 online gestellt.
28.10.2011 Einige Tippfehler in den Kapiteln 0 und 1 korrigiert. Die Skript-Versionen von Kapitel 2, Kapitel 3 und vom Literaturverzeichnis online gestellt. Den Abschnitt über Substitutionen (vorher: Abschnitt 2.2 in Kapitel 2) ans Ende von Kapitel 1 verschoben. Dadurch ändern sich die Nummerierungen in Kapitel 2 und am Ende von Kapitel 1. Einige Übungsaufgaben am Ende von Kapitel 1 ergänzt.