VL Ausgewählte Kapitel der Logik: klassische Resultate
Wintersemester 2024/2025
Aktuelles
- In der letzten Novemberwoche werden der Übungstermin und der Vorlesungstermin am Donnerstag getauscht. Das heißt, am Dienstag, 26.11. 15-17 Uhr, sowie am Mittwoch, 27.11. 15-17 Uhr, findet jeweils eine Vorlesungsstunde statt. Die Übungsstunde findet dafür am Donnerstag, 28.11. 15-17 Uhr, statt.
- Die Eröffnungsvorlesung findet am Dienstag, den 15.10.24, statt.
- Die erste Übungsstunde findet am Mittwoch, den 23.10.24, statt.
- Die Veranstaltung wird in Präsenz durchgeführt.
- Viele wichtige Informationen zur Veranstaltung finden Sie hier auf der Webseite, die regelmäßig aktualisiert wird. Ergänzend dazu werden manche Teile der Veranstaltung über die Moodle-Plattform durchgeführt; bitte schreiben Sie sich dort bis zum 23.10.2024 in den Moodle-Kurs ein. Der Einschreibeschlüssel wird an die über AGNES eingeschriebenen Studierenden verschickt (bis 17.10.24) und kann von den Teilnehmer*innen, die noch nicht über AGNES eingeschrieben sind, danach auch per Email an Benjamin Hauskeller erfragt werden.
- Im Logbuch finden Sie nach den Vorlesungen Informationen zum Inhalt der einzelnen Vorlesungsstunden und gelegentlich ergänzende Bemerkungen.
Einführung
Die mathematische Logik beschäftigt sich mit den grundlegenden Eigenschaften von formalen Systemen und Sprachen, insbesondere der Ausdrucksstärke von formalen Sprachen und Beweissystemen sowie den Möglichkeiten und Grenzen des automatischen Schließens.
In dieser Vorlesung werden ausgewählte Kapitel der mathematischen Logik und deren Anwendungen in der Informatik behandelt. Themen der Vorlesung sind u.a. der Vollständigkeitssatz, die Sätze von Löwenheim und Skolem und die Gödelschen Unvollständigkeitssätze.
Die Vorlesung richtet sich an fortgeschrittene Studierende in einem Masterstudiengang, die sich im Bereich der Logik spezialisieren wollen. Voraussetzung für die Teilnahme an der Veranstaltung sind Kenntnisse, die in der Veranstaltung "Logik in der Informatik" vermittelt werden.
Inhalte
Das folgende Inhaltsverzeichnis wird im Laufe der Vorlesung noch ergänzt und möglicherweise verändert.
- Kapitel 0: Einleitung
- Kapitel 1: Der Vollständigkeitssatz
- Kapitel 2: Die Sätze von Löwenheim und Skolem
- Kapitel 3: Die Grenzen der Berechenbarkeit
- Kapitel 4: Gödels Unvollständigkeitssätze
Als Literatur bis inkl. Kapitel 4 wird das Buch [EFT] empfohlen. An Stelle eines Vorlesungsskripts wird das folgende Material bereitgestellt:
- Skript-Fragmente zu Kapitel 0, 1 (ohne den Teil über nicht-abzählbare Signaturen) und 2
- Notizen zu Kapitel 1 (nicht-abzählbare Signaturen) - Seiten 1-7
Notizen zu Kapitel 1 (Exkurs: Auswahlaxiom, Wohlordnungssatz und Zornsches Lemma) - Seiten 8-19 - Notizen zu Kapitel 3 (Hinweis: In diesen Notizen müssen alle Nummern der Form "9.x" durch "3.x" ersetzt werden)
- Notizen zu Kapitel 4 (Hinweis: In diesen Notizen müssen alle Nummern der Form "10.x" durch "4.x" ersetzt werden)
Beachten Sie: In den Vorlesungs- und Übungsstunden wird hauptsächlich an der Tafel gearbeitet. Alle behandelten Inhalte sind für die Veranstaltung wesentlich und daher auch dann prüfungsrelevant, wenn sie nicht in den auf den Webseiten erhältlichen Materialien enthalten sind.
Zur Vorbereitung auf eine Prüfung wird dringend empfohlen, das gesamte, in den Vorlesungs- und Übungsstunden vermittelte Material durchzuarbeiten.
Es ist daher wichtig, dass Sie sich während der Vorlesungs- und Übungsstunden Notizen machen.
Logbuch
Im Logbuch finden Sie nach den Vorlesungen Informationen zum Inhalt der einzelnen Vorlesungsstunden und gelegentlich ergänzende Bemerkungen.
Termine
Das Modul umfasst zwei Vorlesungsblöcke und einen Übungsblock pro Woche. Die Eröffnungsvorlesung findet am Dienstag, dem 15.10.24, statt.
-
Vorlesung
- Dienstags 15:00-17:00 RUD26 1'306 und
Donnerstags 15:00-17:00 RUD26 1'306Dozentin: Prof. Dr. Nicole Schweikardt
-
Übung
- Mittwochs 15:00-17:00 RUD26 1'306
Übungsleiter: Benjamin Hauskeller
Übungsblätter
Neben den Vorlesungs- und Übungsstunden wird wöchentlich ein Übungsblatt ausgegeben und in der darauf folgenden Woche besprochen. Auf jedem Übungsblatt können bis zu 100 Punkte erreicht werden.
Das aktuelle Übungsblatt wird jeweils hier und im Moodle-Kurs zu Mittwoch 12 Uhr online bereitgestellt.
- Blatt 1 (ausgeteilt am 16.10., Abgabe bis zum 23.10., 14:45)
- Blatt 2 (ausgeteilt am 23.10., Abgabe bis zum 30.10., 14:45)
- Blatt 3 (ausgeteilt am 30.10., Abgabe bis zum 6.11., 14:45)
- Blatt 4 (ausgeteilt am 5.11., Abgabe bis zum 13.11., 14:45)
Verbindliche "Spielregeln" zum Erwerb von Übungspunkten
Sie können bei jedem Übungsblatt entscheiden, gemäß welcher der folgenden beiden Varianten A bzw. B Ihre Lösung bewertet werden soll:
-
Variante A:
Sie geben eine schriftliche, ausführlich ausgearbeitete und mathematisch präzise Lösung spätestens direkt vor Beginn der Übungsstunde am Mittwoch ab.Die Abgabe erfolgt entweder direkt zu Beginn der Übungsstunde beim Übungsleiter oder wird bis Mittwoch 14:45 Uhr in den Briefkasten am Lehrstuhl (RUD25 zwischen den Räumen 3.401 und 3.402) eingeworfen.
-
Variante B:
Sie geben keine Lösung ab. Stattdessen tragen Sie direkt vor Beginn der Übung in eine vom Übungsleiter bereitgestellte Liste ein, wie viele Übungspunkte Sie für Ihre Lösung der einzelnen Aufgaben[teile] für gerechtfertigt halten. Während der Übungsstunde werden vom Übungsleiter aus dieser Liste einzelne Teilnehmer*innen zum Vorrechnen von Aufgaben[teilen] ausgesucht. Falls sich beim Vorrechnen herausstellen sollte, dass Sie keine sinnvolle Lösung vorweisen können, obwohl Sie in der Liste Punkte für diese[n] Aufgabe[nteil] eingetragen haben, werden Ihnen für das gesamte gerade behandelte Übungsblatt keine Übungspunkte angerechnet. Eine sinnvolle Lösung muss hierbei nicht notwendigerweise vollständig und/oder korrekt sein.
Prüfung
Zur Vorbereitung auf eine Prüfung (Modulabschlussprüfung) ist es unbedingt notwendig, das gesamte, in den Vorlesungs- und Übungsstunden vermittelte Material durchzuarbeiten.
Die Modulabschlussprüfung wird durch eine mündliche Prüfung abgelegt.
Auf der Webseite des Prüfungsbüros wird im Laufe des Semesters der vollständige Prüfungsplan veröffentlicht (inkl. Prüfungszeitraum, Prüfungsterminen und Anmeldefristen und Hinweise zur Prüfungsan- und -abmeldung).
Voraussetzung für die Zulassung zur Prüfung sind:
- Erreichen von jeweils mindestens 40 Prozent der Punkte von zwei gesonderten Präsenzübungsblättern, welche in der Mitte und gegen Ende der Vorlesungszeit bearbeitet werden, und
- Erreichen von mindestens 50 Prozent aller Übungspunkte. Um dies zu gewährleisten, empfehlen wir dringend, regelmäßig und aktiv an den Übungsstunden teilzunehmen. Beachten Sie hierzu auch die "Spielregeln".
Literatur
[EFT] |
H.-D. Ebbinghaus, J. Flum, W. Thomas, Einführung in die mathematische Logik, Spektrum Akademischer Verlag, 4. Auflage, 1996 Für Angehörige der HU Berlin ist das Buch online hier erhältlich: https://link.springer.com/book/10.1007%2F978-3-662-58029-5. Loggen Sie sich dazu auf der Seite über Log In, Log in via Shibboleth or Athens, bei Or, find your institution (via Shibboleth) über Humboldt-Universität zu Berlin auf Log in via Shibboleth mit Ihrem CMS-Account ein. |
[S‑LI] | N. Schweikardt, Skript zur Vorlesung "Logik in der Informatik" im Wintersemester 2023/24, Humboldt-Universität zu Berlin. |
[E] |
H.-D. Ebbinghaus Einführung in die Mengenlehre, Spektrum Akademischer Verlag, 5. Auflage, 2021 Für Angehörige der HU Berlin ist das Buch online hier erhältlich: https://link.springer.com/book/10.1007/978-3-662-63866-8. Loggen Sie sich dazu auf der Seite über Log In, Log In via Shibboleth or Athens, bei Or, find your institution (via Shibboleth) über Humboldt-Universität zu Berlin auf Log In via Shibboleth mit Ihrem CMS-Account ein. |
[BBJ] | G. S. Boolos, J. P. Burgess, R. C. Jeffrey. Computability and Logic, 5th Edition, Cambridge University Press, 2007. |
Links
[LICS] | IEEE Symposium on Logic in Computer Science (LICS) |
[EACSL] | European Association for Computer Science Logic (EACSL) |
[Highlights] | Highlights of Logic, Games and Automata |