Mathematische Logik

WS 2006/07

Termine

Art Termin Ort   Veranstalter
V3 Di. 14.00 - 15.30 Gr Beginn 17. Oktober E. Grädel
Do. 8.15 - 9.00 Gr Beginn 19. Oktober E. Grädel
Ü1 Do. 9.00 - 9.45 Gr Zentralübung E. Grädel
Ü2 Mo. 10.00 - 11.30 5055 Gruppe A Stefan Schulz
Mo. 12.00 - 13.30 AH II Gruppe B Bernd Puchala
Di. 10.00 - 11.30 AH I Gruppe C Diana Fischer
Di. 11.30 - 13.00 5055 Gruppe D Frédéric Reinhardt
Di. 16.00 - 17.30 Fo 6 Gruppe E Lukasz Kaiser
Mi. 10.00 - 11.30 AS Gruppe F Vince Bárány
Mi. 14.00 - 15.30 AH I Gruppe G Tobias Ganzow
Mi. 16.00 - 17.30 Fo 3 Gruppe H Michael Ummels

Übungsbetrieb

Jeden Donnerstag wird ein neues Aufgabenblatt auf dieser Seite herausgegeben.Die Aufgaben können in Dreiergruppen bearbeitet werden; Lösungen müssen bis zum Vorlesungsbeginn am darauffolgenden Donnerstag abgegeben werden. Hierzu steht am Lehrstuhl ein Kasten bereit. Die korrigierten Übungen werden in den Kleingruppenübungen bzw. Donnerstags, 15:00 – 16:00 Uhr am Lehrstuhl zurückgegeben.

In der Frontalübung nach der Vorlesung werden die Aufgaben vorgerechnet. Zusätzlich werden Kleingruppenübungen angeboten, in denen Fragen gestellt werden können und zusätzliche Aufgaben gerechnet werden. Die Teilnahme ist freiwillig, wird aber dringend empfohlen.

Für die Klausurzulassung sind 50% der Übungspunkte notwendig.

Übungen

Skript

  • Kapitel 1: Aussagenlogik [ps] [pdf]
  • Kapitel 2: Strukturen und Homomorphismen [ps] [pdf]
  • Kapitel 3: Syntax und Semantik der Prädikatenlogik [ps] [pdf]
  • Kapitel 4: Modallogik [ps] [pdf]
  • Kapitel 5: Definierbarkeit in der Prädikatenlogik [ps] [pdf]
  • Kapitel 6: Vollständigkeitssatz, Kompaktheitssatz und Unentscheidbarkeit in der Prädikatenlogik [ps] [pdf]

Inhalt

Einführung

In den letzten zwanzig Jahren hat sich die mathematische Logik stark verändert. Neben den klassischen Fragen nach den Grundlagen der Mathematik und Informatik ("Was ist Wahrheit?", "was ist beweisbar?", "was ist berechenbar?" etc.) stehen heute auch zahlreiche moderne Anwendungen der Logik in der Informatik (etwa in der Verifikation oder im Datenbankbereich) im Zentrum des Interesses. Von einem Grundlagenfach ist die Logik damit auch zu einem Anwendungsfach geworden (Stichwort: Logik als Technologie!)

Es werden drei logische Systeme betrachtet: Aussagenlogik, modale Logiken, und die Prädikatenlogik erster Stufe. Besonderes Gewicht wird auf algorithmische Probleme und grundlegende methodische Aspekte gelegt.

Ziele

  • zu lernen, Sachverhalte in geeigneten logischen Systemen zu formalisieren und mit diesen Formalisierungen umzugehen;
  • die grundlegenden Begriffe und Methoden der mathematischen Logik zu verstehen (Syntax und Semantik logischer Systeme, Modellbeziehung, Folgerungsbeziehung, Erfüllbarkeit, Beweiskalküle, Definierbarkeit, etc.); die Ausdrucksstärke und Grenzen logischer Systeme beurteilen zu können;
  • einige der fundamentalen Resultate der mathematischen Logik des 20. Jahrhunderts (z.B. Vollständigkeitssatz, Kompaktheitssatz, Unentscheidbarkeit der Prädikatenlogik, Gödelsche Unvollständigkeitssätze) kennenzulernen und ihre Bedeutung für Mathematik und Informatik zu verstehen.

Literatur

Einführende Literatur

[1] S. Burris. Logic for Mathematics and Computer Science. Prentice Hall, 1998.
[2] R. Cori and D. Lascar. Logique mathématique. Masson, 1993.
[3] H. Ebbinghaus, J. Flum, and W. Thomas. Einführung in die mathematische Logik. Wissenschaftliche Buchgesellschaft, Darmstadt, 1986.
[4] M. Huth and M. Ryan. Logic in Computer Science. Modelling and reasoning about systems. Cambridge University Press, 2000.
[5] B. Heinemann and K. Weihrauch. Logik für Informatiker. Teubner, 1992.
[6] H. K. Büning and T. Lettman. Aussagenlogik: Deduktion und Algorithmen. Teubner, 1994.
[7] S. Popkorn. First Steps in Modal Logic. Cambridge University Press, 1994.
[8] W. Rautenberg. Einführung in die Mathematische Logik. Vieweg, 1996.
[9] U. Schöning. Logik für Informatiker. Spektrum Verlag, 1995.
[10] D. van Dalen. Logic and Structure. Springer, Berlin, Heidelberg, 1983.

Weiterführende Literatur

[1] E. Börger, E. Grädel, and Y. Gurevich. The Classical Decision Problem. Springer Verlag, 1997.
[2] P. Blackburn, M. de Rijke, and Y. Venema. Modal Logic. Cambridge University Press, 2001.
[3] C. Chang and J. Keisler. Model Theory. North-Holland, 1990.
[4] R. Cori and D. Lascar. Logique mathématique. Masson, 1994.
[5] K. Doets. Basic Model Theory. CSLI Publications, 1996.
[6] H. Ebbinghaus and J. Flum. Finite Model Theory. Springer, 1999.
[7] H. Ebbinghaus. Einführung in die Mengenlehre. BI Wissenschaftsverlag, 1994.
[8] M. Fitting. First-order logic and automated theorem proving. Springer, 1996.
[9] O. Grumberg, E. Clarke, and D. Peled. Model Checking. MIT Press, 1999.
[10] W. Hodges. A shorter model theory. Cambridge University Press, 1997.
[11] D. Kozen, D. Harel, and J. Tiuryn. Dynamic Logic. MIT Press, 2000.
[12] R. Lassaigne and M. de Rougemont. Logique et complexité. Hermes, 1996.
[13] Y. Moses, R. Fagin, J. Halpern, and M. Vardi. Reasoning about Knowledge. MIT Press, 1995.
[14] M. Manzano. Model Theory. Clarendon Press, 1999.
[15] Y. Moschovakis. Notes on Set Theory. Springer Verlag, 1994.
[16] B. Poizat. A Course in Model Theory. Springer Verlag, 2000.
[17] P. Rothmaler. Einführung in die Modelltheorie. Spektrum Verlag, 1995.

Zuordnung

  • Informatik (D)/Grundstudium
  • Mathematik (D)/Hauptstudium/Reine Mathematik
  • Informatik (S II)
  • Mathematik (S II)/Hauptstudium/B: Algebra und Grundlagen der Mathematik

Voraussetzungen

  • Lineare Algebra

Nachfolgeveranstaltungen

  • Entscheidbarkeit und Komplexität von Logik-Problemen
  • Mathematische Logik II
  • Komplexitätstheorie
  • weitere Spezialvorlesungen zur Mathematischen Logik

Wiederholung

Ab 2008 jedes Jahr im Sommersemester

Rückfragen

Erich Grädel, Vince Bárány, Tobias Ganzow, Łukasz Kaiser, Michael Ummels