Mathematische Logik

SS 2020

Aktuelles

  • Die Vorlesung beginnt (in digitaler Form) bereits am 6. April.
  • Bitte melden Sie sich in RWTHonline zur Übung an, um Zugriff auf den Lernraum zu erhalten.
  • Es gibt Probleme bei der Anmeldung als Auflage im Master. Falls Sie sich aus diesem oder einem anderen Grund nicht anmelden können, melden Sie sich bitte unter Angabe Ihres Studiengangs und Ihrer Matrikelnummer bei Matthias Naaf, um angemeldet zu werden.
  • Vorlesung und Übung werden bis auf weiteres online über den Lernraum organisiert.
  • Bitte melden Sie sich zusätzlich im MaLo-Portal an.

→ MaLo-Portal ←

Im MaLo-Portal können Sie Ihre Übungspunkte und später die vorläufigen Klausurergebnisse einsehen.

Informationen zum Übungsbetrieb

Aufgrund der aktuellen Einschränkungen in Bezug auf das Coronavirus werden die Vorlesungen und der Übungsbetrieb bis auf weiteres online über den Lernraum ausgetragen. Der Ablauf wird wie folgt aussehen: Ab Beginn des Semesters stellen wir Ihnen das Skript der Vorlesung sowie Aufnahmen der Vorlesungen aus einem vergangenen Semester zur Verfügung (diese sind immer noch aktuell). Beginnend voraussichtlich am 06.04. werden wir jeden Montag ein Übungsblatt hochladen und Sie darüber informieren, auf welche Vorlesungseinheiten es sich bezieht. Das Übungsblatt ist jeweils zum darauffolgenden Montag, 10 Uhr, abzugeben. Die Abgabe erfolgt digital über das Moodle Lernportal. Mit der Anmeldung in RWTHonline werden Sie automatisch im Moodle-Lernraum angemeldet (mit zeitlicher Verzögerung). Bitte stellen Sie sicher, dass Sie Zugriff auf den Lernraum haben und melden Sie sich andernfalls bei Matthias Naaf, um angemeldet zu werden. Sobald Sie Zugang zum Moodle-Lernraum haben, suchen Sie sich bitte eine Abgabegruppe. Es sind nur Gruppenabgaben von 3 bis 4 Studierenden erlaubt.

Bezüglich des Formates der Abgabe gelten folgende Regeln: Die Lösung muss eine zusammenhängende pdf-Datei sein, die Ihre Namen, Matrikelnummern und die Nummer der Übung enthält. Wir empfehlen, Ihre Lösung mit LaTeX zu erstellen. Auch wenn Sie mit LaTeX noch nicht vertraut sein sollten, lohnt es sich, sich darin einzuarbeiten, da Sie im Verlauf Ihres Studiums höchstwahrscheinlich LaTeX-Kenntnisse brauchen werden. Wir stellen Ihnen dazu ein einfaches Template im Lernraum zur Verfügung. Sollte Ihnen die Verwendung von LaTeX nicht möglich sein, können Sie Office-Programme wie LibreOffice Writer, Pages oder Word verwenden. Bitte verwenden Sie zum Erstellen mathematischer Ausdrücke unbedingt den jeweiligen Formel-Editor. Abgaben, deren mathematische Zeichen aus Pseudocode (‚umgedrehtes A’, 7^3, A|=phi) bestehen, werden nicht akzeptiert.

Termine

Vorlesung und Übung finden in digitaler Form statt. Bitte besuchen Sie den Moodle-Lernraum der Veranstaltung.

Skript und Übungen

Alle Lernmaterialien sind im Moodle-Lernraum verfügbar.

Prüfungsleistung

Die Prüfung für das Modul Mathematische Logik findet in Form einer Klausur statt (Bearbeitungszeit 120 Minuten).

Für die Zulassung zur Klausur genügen 50% der Übungspunkte.

Erster Prüfungstermin: Freitag, 28.08.2020, 16:30 Uhr.

Zweiter Prüfungstermin: Montag, 29.09.2020, 14:30 Uhr.

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.

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 (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
  • Quantum Computing
  • Logik und Spiele
  • weitere Spezialvorlesungen zur Mathematischen Logik

Wiederholung

Jedes Jahr im Sommersemester

Rückfragen

Matthias Naaf, Erich Grädel