Logik

i.d.R. angeboten alle 2 Semester

• Logische Notation verstehen und verwenden können; die Bedeutung von Syntax und Semantik kennen.

• Wichtige logische System wie die Aussagenlogik und die Prädikatenlogik kennen und anwenden können.

• Mathematische Beweise verstehen können und in der Lage sein, einfache Beweise selbst zu führen.

• Zum Umgang mit formalen Systemen fähig sein.

• Die Bedeutung der Logik in der Informatik verstehen und wichtige Anwendungen benennen können.

• Zentrale Resultate der Logik benennen und deren Bedeutung und Relevanz erklären können.

• Grundlagen der Aussagen- und Prädikatenlogik
• Erfüllbarkeit und Gültigkeit
• (Un)entscheidbarkeit und Komplexität
• Funktionale Vollständigkeit
• Normalformen
• Horn-Formeln
• Resolution und Einheitsresolution
• Logische Kalküle
• Kompaktheit
• Anwendungen für Datenbanken
• FO-Theorien und Axiomatisierungen
• Vollständigkeit und rekursive Aufzählbarkeit
• Ehrenfeucht-Fraïssé-Spiele
• MSO über linearen Strukturen
• Temporallogik
• Logik und Komplexitätstheorie

• Erich Grädel: Mathematische Logik I. Skript.
• Leonid Libkin: Elements of Finite Model Theory, Springer, 2004.
• Uwe Schöning: Logik für Informatiker.
Spektrum akademischer Verlag, 2000 (5. Auflage).
• Christel Baier: Advanced Logics. VL-Skript, TU Dresden.
• Heinz-Dieter Ebbinghaus, Jörg Flum, Wolfgang Thomas: Mathematical Logic. Springer Verlag, 1994 (2. Auflage).