zum Inhalt springen

Seminar über Mathematische Logik

Anhand einzelner Textbuchkapitel und Originalarbeiten sollen Inhalte der Vorlesung im SS07 vertieft und weiterführende Fragestellungen behandelt werden.

Einige mögliche Grob-Themen sind:

  • Algorithmik/Komplexität des KNF-SAT Problems
  • Prolog und Wissensbasierte Systeme
  • Model Checking
  • nichtklassisache Logiken: modale Logik; temporale Logik
  • Polynomiale Zeithierarchie
  • Historie/Beweisideen der Gödel Resultate
  • Zum klassischen Entscheidungproblem
  • Peano-Arithmetik
  • Axiomatik der Mengenlehre etc.
  • NP-vollst. Erfüllbarkeitsprobleme struktureller und parameterisierter Komplexitätsklassen

Termine: Ende des Semesters nach Vereinbarung, Raum 616, Pohligstr. 1. Vorbesprechung am 22. Februar 2008, 11.00 - 12.00 Uhr, Pohligstr. 1, Raum 616. In diesem Rahmen werden auch die Themen vergeben.

Voraussetzung (sinnvoll, nicht zwingend): Teilnahme an der Vorlesung im Wintersemester 07/08

Scheinbedingung: Ausarbeitung eines Referats samt Vortrag von ca. 60 min Länge

Literatur:

  • Ebbinghaus, H.; Flum, J.; Thomas, W.: Einführung in die mathematische Logik. Wissenschaftliche Buchgesellschaft, Darmstadt, 1986.
  • Büning, H. K.; Lettman, T.: Aussagenlogik: Deduktion und Algorithmen. Teubner, 1994.
  • Ebbinghaus, H.; Flum, J.: Finite Model Theory. Springer, 1999.
  • Papadimitriou, C. H.: Computational Complexity. Addison-Wesley, 1994.
  • Downey, R. G.; Fellows, M. R.: Parameterized Complexity. Springer, 1999.
  • Flum, J.; Grohe, M.: Parameterized Complexity Theory. Springer, 2006.
  • Schöning, U.: Logik für Informatiker. Spektrum Verlag, 1995.

Weitere spezielle Literatur insbesondere Originalarbeiten werden im Rahmen der Vorbesprechung (s.u.) angegeben werden.