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

Sommersemester 2022

Aktuelles

• 21.07.22: Die mündlichen Prüfungen (im Juli 2022 und im Oktober 2022) zum Modul "Ausgewählte Kapitel der Logik: klassische Resultate" werden alle in Raum 3.408 im Johann von Neumann-Haus stattfinden.
• 18.07.22: Am Dienstag, den 19.07., wird die Vorlesung über Zoom stattfinden.
  Der Zoom-Raum sowie das benötigte Passwort wird über Moodle bereitgestellt.
  Zusätzlich wird das Meeting aber auch im üblichen Vorlesungraum 1.303 übertragen.
• 11.07.22: Krankheitsbedingt finden diese Woche (also am 12.07. und 14.07.) keine Vorlesungsstunden statt. Die Übungsstunde am Dienstag wird 2 Stunden früher gehalten (also von 13 - 15 Uhr).
• 30.06.22: Der für den 07.07.22 angekündigte Test entfällt;stattdessen findet am 07.07.22 die Vorlesung statt. Die Voraussetzungen für die Zulassung zur Modulabschlussprüfung wurden entsprechend modifiziert.
• 24.06.22: Unter Prüfung gibt es neue Hinweise zu der Modulabschlussprüfung und zur Prüfungsanmeldung
• 30.05.22: Am Dienstag, den 07.06.22, wird der sich an die Vorlesung anschließende Übungstermin für eine weitere Vorlesungsstunde genutzt. Blatt 6 verschiebt sich deshalb um eine Woche
• 25.05.22: Unter Prüfung gibt es neue Hinweise zu der Modulabschlussprüfung und zu den Voraussetzungen für die Zulassung zur Prüfung
• 06.05.22: neue Version der Skript-Fragmente (Beweis von Lemma 1.41 geändert)
• 03.05.22: neue Version der Skript-Fragmente (Kapitelsturktur in Kapitel 1 bereinigt und einige Tippfehler korrigiert)
• 28.04.22: neue Version der Skript-Fragmente (kleiner Fehler in Definition 1.10)
• 25.04.22: neue Version der Skript-Fragmente (kleiner Fehler in Definition 0.39)
• 21.04.22: Es steht eine neue Version der Skript-Fragmente zur Verfügung in der Details zur Definition 0.39 angepasst worden sind
• Die Eröffnungsvorlesung findet am Donnerstag, den 21.04.22, statt.
• Am Dienstag, den 26.04.22 wird der sich an die Vorlesung anschließende Übungstermin für eine weitere Vorlesungsstunde genutzt. Die erste wirkliche Übungsstunde findet am Dienstag, den 03.05.22 statt.
• Die Veranstaltung wird in Präsenz durchgeführt.
• 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 Donnerstag, den 21.04.22, statt. Am 19.04.22 findet keine Vorlesung oder Übung statt.

Vorlesung

Dienstags 13:00-15:00 im Erwin-Schrödinger-Zentrum (Rudower Chaussee 26), Raum 1'303 und
Donnerstags 09:00-11:00 im Erwin-Schrödinger-Zentrum (Rudower Chaussee 26), Raum 1'305

Dozentin: Prof. Dr. Nicole Schweikardt

Übung

Dienstags 15:00-17:00 im Erwin-Schrödinger-Zentrum (Rudower Chaussee 26), Raum 1'303

Übungsleiter: Benjamin Hauskeller

Am Dienstag, den 26.04., findet abweichend statt der Übung ein weiterer Vorlesungstermin statt.

Übungsblätter

Ab der zweiten Vorlesungswoche 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 Dienstag 12 Uhr online bereit gestellt.

• Blatt 1 (ausgeteilt am 26.04., Abgabe bis zum 03.05., 15:00) [update 2.5.: Klammer-Typo in 1(b). ]
• Blatt 2 (ausgeteilt am 03.05., Abgabe bis zum 10.05., 15:00)
• Blatt 3 (ausgeteilt am 10.05., Abgabe bis zum 17.05., 15:00)
• Blatt 4 (ausgeteilt am 17.05., Abgabe bis zum 24.05., 15:00)
• Blatt 5 (ausgeteilt am 24.05., Abgabe bis zum 31.05., 15:00)
• Blatt 6 (ausgeteilt am 07.06., Abgabe bis zum 14.06., 15:00)
• Blatt 7 (ausgeteilt am 14.06., Abgabe bis zum 21.06., 15:00)
• Blatt 8 (ausgeteilt am 21.06., Abgabe bis zum 28.06., 15:00)
• Blatt 9 (ausgeteilt am 28.06., Abgabe bis zum 05.07., 15:00) - update: 01.07 -- Aufgabe 2 ist auf Blatt 10 verschoben
• Blatt 10 (ausgeteilt am 25.07., Abgabe bis zum 12.07., 15:00)

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 Dienstag im Moodle-Kurs ab.

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 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 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 Juli 2022 und Oktober 2022 für dieses Modul finden in Raum 3.408 (JvN-Haus) statt.

Hinweise zur Prüfungsanmeldung:

1. Die Modulabschlussprüfung (kurz: MAP) wird als mündliche Prüfung durchgeführt. Dafür müssen Sie sich in AGNES anmelden – die Frist dafür endet am 3. Juli 2022! Direkt daran anschließend müssen Sie einen konkreten Prüfungstermin über das Sekretariat vereinbaren (per Email an Gesine Pergel mit Petra Kämpfer im CC). Nennen Sie dabei bitte Ihren Namen, Matrikelnummer und das Modul ("Ausgewählte Kapitel der Logik: klassische Resultate") und bitten Sie darum, einen konkreten Prüfungstermin (Tag und Uhrzeit) zugeteilt zu bekommen. Wichtig: zur ordnungsgemäßen Anmeldung zur MAP ist beides nötig: fristgerechte Anmeldung in AGNES und Vereinbarung eines konkreten Prüfungstermins.
2. In AGNES melden Sie sich zwar für den Montag, den 25.7.22 an, der Termin kann aber an einem beliebigen Tag innerhalb des Prüfungszeitraumes 25.-28.07.22 liegen.
3. Sie können sich auch anmelden, falls Sie die Voraussetzung zur Zulassung zur MAP zum jetzigen Zeitpunkt noch nicht erfüllen. Sollten Sie die Zulassung bis zum Ende des Semesters nicht besitzen, werden Sie automatisch wieder abgemeldet (ohne dass für Nachteile für Sie entstehen). Umgekehrt ist der 3. Juli 2022 eine harte Frist: Danach ist keine Anmeldung mehr möglich!
4. Die Frist zum Rücktritt von der Prüfung entnehmen Sie der Webseite des Prüfungsbüros. Sollten Sie vor Ablauf der Frist zurücktreten wollen, AGNES Ihnen den Rücktritt jedoch nicht mehr ermöglichen (bspw. weil in AGNES der 25.7. als Prüfungsdatum steht, Ihre Prüfung jedoch erst am 28.7. stattfindet), melden sie sich per Mail an das Prüfungsbüro (mit Prof. Schweikardt im CC) von der Prüfung ab.

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

1. Bestehen der beiden jeweils 90-minütigen schriftlichen Tests, die in der Mitte und gegen Ende der Vorlesungszeit geschrieben werden Bestehen des 90-minütigen schriftlichen Tests, der am 07.07.22 innerhalb des Zeitslots der Vorlesung (also von 9.00-11.00 Uhr) geschrieben wird, TRUE 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