Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Logik in der Informatik

Wintersemester 2024/2025

Aktuelles

• Der Übungstermin am Mittwoch, den 29.1.25, fällt aus. Ebenso der Vorlesungstermin am Donnerstag, den 30.1.25.
• Die Eröffnungsvorlesung fand am Dienstag, den 15.10.24, statt.
• Die erste Übungsstunde fand 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
• Kapitel 5: Ordnungsinvarianz

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)
• Literatur zu Kapitel 5; Folien zu Kapitel 5

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'306

Dozentin: 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)
• Blatt 5 (ausgeteilt am 13.11., Abgabe bis zum 20.11., 14:45)
• Blatt 6 (ausgeteilt am 20.11., Abgabe bis zum 28.11., 14:45)
• Blatt 7 (ausgeteilt am 27.11., Abgabe bis zum 4.12. 11.12., 14:45)
• Blatt 8 (ausgeteilt am 11.12., Abgabe bis zum 18.12., 14:45)
• Blatt 9 (ausgeteilt am 18.12., Abgabe bis zum 8.1.25, 14:45)
• Blatt 10 (ausgeteilt am 8.1., Abgabe bis zum 15.1.25, 14:45)
• Blatt 11 (ausgeteilt am 15.1., Abgabe bis zum 22.1.25, 14:45)
• Blatt 12 (ausgeteilt am 22.1., Abgabe bis zum 5.2.25, 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 finden Sie den vollständigen Prüfungsplan (inkl. Prüfungszeitraum, Prüfungsterminen und Anmeldefristen und Hinweise zur Prüfungsan- und -abmeldung).

Die Prüfungen im Februar 2025 (20.+21.2.) und am 9.4.2025 für dieses Modul finden im Johann-von-Neumann-Haus (Rudower Chaussee 25) im Haus 3 in der 4. Etage im Raum 3.408 statt.

Hinweise zur Prüfungsanmeldung

Voraussetzung für die Zulassung zur Prüfung sind:

1. 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, WAHR und
2. 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

Links