Mathematische Logik

SS 2008

Aktuelles

  • Das Skript steht nun (in einer vorläufigen Fassung) vollständig zum Herunterladen bereit.
  • Bitte bearbeiten Sie die Übungen in Gruppen von zwei bis (vorzugsweise) drei Studenten.
  • Für die Übungsgruppen stehen nur die auf dieser Seite angegebenen Termine zur Verfügung.

Termine

ArtTerminOrt Veranstalter
V3Di. 11:45 – 12:30GrBeginn 8. AprilE. Grädel
Do. 11:45 – 13:15Gr E. Grädel
Ü2Fr. 8:15 – 9:45SE 001Gruppe AR. Rabinovich
Fr. 10:00 – 11:305054Gruppe BS. Leßenich
Fr. 11:45 – 13.155054Gruppe CM. Ummels
Mo. 11:45 – 13:15SE 001Gruppe DW. Pakusa
Di. 8:15 – 9:455055Gruppe EL. Berthold
Di. 15:30 – 17:005055Gruppe FŁ. Kaiser
Mi. 13:30 – 15:005054Gruppe GB. Puchala

Skript

  • Alle Kapitel [A5] [A4]
  • Kapitel 1: Aussagenlogik [A5] [A4]
  • Kapitel 2: Syntax und Semantik der Prädikatenlogik [A5] [A4]
  • Kapitel 3: Modallogik, temporale Logiken und monadische Logik [A5] [A4]
  • Kapitel 4: Definierbarkeit in der Prädikatenlogik [A5] [A4]
  • Kapitel 5: Vollständigkeitssatz, Kompaktheitssatz und Unentscheidbarkeit der Prädikatenlogik [A5] [A4]

Übungen

Inhalt

  • Aussagenlogik (Grundlagen, algorithmische Fragen, Kompaktheit, Resolution, Sequenzenkalkül)
  • Strukturen, Syntax und Semantik der Prädikatenlogik
  • Einführung in weitere Logiken (modale und temporale Logiken, Logiken höherer Stufe)
  • Auswertungsspiele, Modellvergleichsspiele
  • Beweiskalküle, Termstrukturen, Vollständigkeitssatz
  • Kompaktheitssatz und Anwendungen
  • Entscheidbarkeit, Unentscheidbarkeit und Komplexität von logischen Spezifikationen

Lernziele

Die Studierenden sollen Sachverhalte in geeigneten logischen Systemen formalisieren und mit diesen Formalisierungen umgehen, Grundlegende Begriffe und Methoden der mathematischen Logik verstehen (Syntax und Semantik logischer Systeme, Folgerungsbeziehung, Erfüllbarkeit, Beweiskalküle, Definierbarkeit, etc.), die Ausdrucksstärke und Grenzen logischer Systeme beurteilen können sowie einige der fundamentalen Resultate der mathematischen Logik des 20. Jahrhunderts (z.B. Vollständigkeitssatz, Kompaktheitssatz, Unentscheidbarkeit der Prädikatenlogik) kennenlernen und ihre Bedeutung für Mathematik und Informatik verstehen.

Ü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 darauffolgenden Donnerstag um 15:00 Uhr abgegeben werden. Hierzu steht am Lehrstuhl ein Kasten bereit. Die korrigierten Übungen werden in den Kleingruppenübungen zurückgegeben.

In den Kleingruppenübungen werden die meisten Aufgaben des jeweils zuletzt abgegebenen Übungsblattes vorgerechnet. Außerdem werden dort zusätzliche Aufgaben vorgerechnet, die als Vorbereitung auf das jeweils nächste Übungsblatt dienen. Die Teilnahme an den Kleingruppenübungen ist freiwillig, wird aber dringend empfohlen.

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

Prüfungsleistung

In der Klausur darf jeder Teilnehmer ein (beidseitig beschriebenes) DIN-A4-Blatt mit eigenen Notizen benutzen. Darüber hinaus sind keine weiteren Hilfsmittel (Skripte, Bücher, Mitschriften etc.) zugelassen.

Zur Einsicht dürfen keine Schreibgeräte oder andere Materialien mitgenommen werden. Sollten Sie Einwände gegen die Bewertung Ihrer Klausur vorbringen, so können Sie diese während der Einsicht schriftlich vorbringen. In diesem Fall werden die betroffen Aufgaben noch einmal korrigiert. Bitte bedenken Sie, dass dies auch zu einer Verschlechterung des Ergebnisses führen kann.

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.

Zuordnung

  • Informatik (B.Sc.)/4. Semester
  • Mathematik (B.Sc.)/Mathematik (WS)/4. Semester
  • Mathematik (B.Sc.)/Mathematik (WS)/6. Semester
  • Mathematik (B.Sc.)/Mathematik (SS)/5. Semester
  • Informatik (D)/Grundstudium
  • Mathematik (D)/Hauptstudium/Reine Mathematik
  • Informatik (S II)
  • Mathematik (S II)/Hauptstudium/B: Algebra und Grundlagen der Mathematik

Voraussetzungen

  • Mathematische Grundkenntnisse aus den Vorlesungen Diskrete Strukturen und Lineare Algebra
  • Grundkenntnisse über Berechenbarkeit und Komplexität

Nachfolgeveranstaltungen

  • Algorithmische Modelltheorie
  • Mathematische Logik II
  • Komplexitätstheorie und Quantum Computing
  • Logik und Spiele
  • weitere Spezialvorlesungen zur Mathematischen Logik

Wiederholung

Jedes Jahr im Sommersemester

Rückfragen

Erich Grädel, Łukasz Kaiser, Michael Ummels