Seminar über "Mathematische Logik"

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

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

Einordnung: B/D

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

Literatur

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

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

Termine

Blockveranstaltung: 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.