Mathematische Logik

WS 2007/08

Aktuelles

  • Die Vorlesung richtet sich ausschließlich an Studierende im Diplomstudiengang Informatik.
  • Die für die Bachelor-Studiengänge Informatik und Mathematik konzipierte Vorlesung wird erstmalig im Sommersemester 2008 gelesen.

Klausur

Die Klausur findet am Dienstag, den 12.02.2008, statt (Beginn: 9:30 Uhr, Bearbeitungszeit 120 Minuten). Es ist keine Anmeldung erforderlich. Wer 180 Übungspunkte (gewichtet) erreicht hat, ist automatisch zur Klausur zugelassen. Im Portal ist die Verteilung auf die Hörsäle (AH II bzw. AH III) einsehbar. In der Klausur darf jeder Teilnehmer ein DIN-A4 Blatt mit eigenen Notizen benutzen. Darüber hinaus sind keine weiteren Hilfsmittel (Skripte, Bücher, Mitschriften, usw.) zugelassen.

Termine

Art Termin Ort   Veranstalter
V3 Di. 10:10 – 11:40 AH I Beginn 16. Oktober E. Grädel, D. Berwanger
Mi. 10:00 – 10:45 AH I Beginn 17. Oktober E. Grädel, D. Berwanger
Ü1 Mi. 10:45 – 11:30 AH I Zentralübung E. Grädel, D. Berwanger
Ü2 Fr. 11:45 – 13:15 AH I Gruppe A D. Fischer
Mo. 10:00 – 11:30 5055 Gruppe B M. Ummels
Mo. 11:45 – 13:15 AH II Gruppe C Ł. Kaiser

Ü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

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

Dietmar Berwanger, Diana Fischer, Tobias Ganzow, Łukasz Kaiser, Michael Ummels