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

VL Einführung in die formale Logik für IMP

Sommersemester 2025

 

Aktuelles

  • Bis auf weiteres startet die Übung donnerstags exakt 15:00 Uhr.
  • Am 07.05.25 findet anstelle einer Vorlesung eine Übung statt.
  • Am 30.04.25 findet keine Vorlesung statt.
  • Die erste Übung findet am 24.04.25 statt.
  • Am 17.04.25 findet anstelle einer Übung eine Vorlesung statt.
  • Die Eröffnungsvorlesung fand am Mittwoch, den 16.04.25, statt.
  • Im Logbuch werden wöchentlich Informationen dazu bereitgestellt, welche Lektüre von allen Teilnehmer*innen bis zum nächsten Vorlesungstermin selbständig durchgearbeitet werden soll. Die Vorlesungstermine werden in Präsenz durchgeführt und dienen dazu, das in der Lektürearbeit erarbeitete Wissen weiter zu vertiefen und Fragen zum Lektürestoff zu klären.

 

Einführung

Diese Veranstaltung vermittelt eine Einführung in die mathematische Logik und ihre Anwendungen in der Informatik; sie ist eine Pflichtveranstaltung im Rahmen des Bachelorstudiengangs Informatik, Mathematik und Physik (IMP).

Im Einzelnen umfassen die Themen der Vorlesung:

  • Aussagenlogik (Grundlagen, Endlichkeitssatz, Resolution)
  • Prädikatenlogik der 1. Stufe (Grundlagen, Beweiskalkül, Vollständigkeitssatz, Endlichkeitssatz und Anwendungen)
  • Weiterführende Themen (beispielsweise Ehrenfeucht-Fraissé Spiele und der Satz von Herbrand)

Lern- und Qualifikationsziele: Studierende erlangen die Fähigkeit, Sachverhalte in geeigneten formalen Systemen zu formalisieren und die grundlegenden Begriffe und Ergebnisse der mathematischen Logik zu verstehen und anzuwenden.

Voraussetzungen für die Teilnahme am Modul: Grundkenntnisse in Informatik und Mathematik, wie sie in den Modulen „Lineare Algebra I“, „Analysis I“ und „Grundlagen der Programmierung“ vermittelt werden.

 

Inhalt

  • Kapitel 1: Einleitung
  • Kapitel 2: Aussagenlogik
  • Kapitel 3: Logik erster Stufe
  • Kapitel 4: Grundlagen des automatischen Schließens

 

Vorlesungsskript (Version vom 22. Mai 2024)

 

Beachten Sie:
Zur Vorbereitung auf eine Prüfung wird dringend empfohlen, das gesamte, in den Vorlesungen und Übungen vermittelte sowie als Lektüreaufgabe vorgegebene Material durchzuarbeiten.

 

Logbuch

Im Logbuch werden wöchentlich Informationen dazu bereitgestellt, welche Lektüre von allen Teilnehmer*innen bis zum nächsten Vorlesungstermin selbständig durchgearbeitet werden soll. Die Vorlesungstermine werden in Präsenz durchgeführt und dienen dazu, das in der Lektürearbeit erarbeitete Wissen weiter zu vertiefen und Fragen zum Lektürestoff zu klären.

 

Termine

Vorlesung
Mittwochs 11:00-13:00 im ESZ (Rudower Chaussee 26), Raum 1'303

Dozent: Dr. André Frochaux

Die Eröffnungsvorlesung findet am 16.04.25 statt.

Übung
Donnerstags 15:00-17:00 im ESZ (Rudower Chaussee 26), Raum 1'303

Übungsleiter: Dr. André Frochaux

Die erste Übungsstunde findet am 24.04.25 statt.

Übungsblätter

Ab der zweiten Vorlesungswoche wird wöchentlich ein Übungsblatt ausgegeben und in der darauf folgenden Woche in der Übungsstunde besprochen. Auf jedem Übungsblatt können bis zu 100 Punkte erreicht werden.

Das aktuelle Übungsblatt wird jeweils hier und im Moodle-Kurs i.d.R. am Montagnachmittag online bereitgestellt.

Die Abgabe der bearbeiteten Aufgaben erfolgt jeweils am darauf folgenden Montagvormittag bis spätestens 10:00 Uhr im Moodle-Kurs; eine verspätete Abgabe ist nicht möglich.

Für die Abgabe Ihrer Lösungen finden Sie sich bitte in Kleingruppen von 2 Personen zusammen, in denen Sie die Lösungen zusammen erarbeiten und dann gemeinsam abgeben. Die Lösungen sind handschriftlich und in deutscher Sprache zu erstellen.

Für den Erwerb eines Übungs- oder Teilnahmescheins müssen insgesamt mind. 40 % der erreichbaren Übungspunkte erzielt werden und es muss mindestens einmal erfolgreich in der Übungsstunde vorgerechnet werden. Der Erwerb eines Übungsscheins ist die Voraussetzung für die Teilnahme an der Modulabschlussprüfung.

  • Blatt 1 (bereitgestellt am 24.04., Bearbeitung bis zum 05.05., 10:00 Uhr)
  • Blatt 2 (bereitgestellt am 05.05., Bearbeitung bis zum 12.05., 10:00 Uhr)
  • Blatt 3 (bereitgestellt am 12.05., Bearbeitung bis zum 19.05., 10:00 Uhr)
  • Blatt 4 (bereitgestellt am 19.05., Bearbeitung bis zum 26.05. 2.06., 10:00 Uhr)
  • Blatt 5 (bereitgestellt am 26.05., Bearbeitung bis zum 9.06., 10:00 Uhr)
  • Blatt 6 (bereitgestellt am 9.06., Bearbeitung bis zum 16.06., 10:00 Uhr)
  • Blatt 7 (bereitgestellt am 16.06., Bearbeitung bis zum 23.06., 10:00 Uhr)
  • Blatt 8 (bereitgestellt am 23.06., Bearbeitung bis zum 30.06., 10:00 Uhr)
  • Blatt 9 (bereitgestellt am 30.06., Bearbeitung bis zum 7.07., 10:00 Uhr)

 

Modulabschlussprüfung

Zur Vorbereitung auf eine Prüfung (Modulabschlussprüfung) ist es unbedingt notwendig, das gesamte, in den Vorlesungs- und Übungsstunden vermittelte, sowie das als Lektüreaufgabe vorgegebene Material, durchzuarbeiten.
Voraussetzung für die Zulassung zur Modulabschlussprüfung ist der Erwerb eines Übungsscheins.
Die Modulabschlussprüfung wird durch eine mündliche Prüfung erfolgen. Details folgen im Laufe des Semesters.
 
Die Prüfungen im Juli 2025 (22.-25.07.2025) für dieses Modul finden im Johann-von-Neumann-Haus (Rudower Chaussee 25) im Haus 3 in der 3. Etage im Raum 3'306 statt.
Die Prüfungen im Oktober 2025 (07.-9.10.) für dieses Modul finden im Johann-von-Neumann-Haus (Rudower Chaussee 25) im Haus 3 in der 4. Etage statt. Die genaue Raumnummer erhalten Sie von uns per Mail.
Hinweise zur Prüfungsanmeldung
Gehen Sie zur Prüfungsanmeldung bitte folgendermaßen vor:
  1. Melden Sie sich zunächst in AGNES für die Prüfung an – die Frist für die Anmeldung zum 1. Prüfungszeitraum endet am 30. Juni 2025! Für jeden Prüfungstag gibt es eine separaten Eintrag. Melden Sie sich nur für einen der Tage an. Sie können sich auch anmelden, falls Sie die Voraussetzung zur Zulassung zur Modulabschlussprüfung zum jetzigen Zeitpunkt noch nicht erfüllen. Sollten Sie die Zulassung bis zum 14.7.25 nicht besitzen, werden Sie automatisch wieder abgemeldet (ohne dass dadurch Nachteile für Sie entstehen). In deisem Falle werden Sie über die in Agnes hinterlegte Mailadresse darüber informiert. Umgekehrt ist der 30. Juni 2025 eine harte Frist: Danach ist für den ersten Prüfungszeitraum keine Anmeldung mehr möglich!
  2. Nach Ende der Anmeldefrist werden wir im Moodle-Kurs unter "Organisatorisches" ein Planer-Element freischalten, in dem Sie ein Zeitfenster an Ihrem Prüfungstag buchen; Sie müssen dies bis spätestens 6.7.25 tun. Klicken Sie hierfür im Planer für das gewünschte Zeitfenster auf "Zeitfenster buchen". Das von Ihnen gewählte Zeitfenster sollte dann oben auf der Seite angezeigt werden. Falls Sie sich verklickt haben, können Sie die Buchung mittels "Buchung abbrechen" rückgängig machen.
  3. Nach Ihrer Buchung schicken wir Ihnen eine Mail an die in Moodle hinterlegte Mailadresse (für gewöhnlich Ihre CMS-Adresse), in welcher wir Ihnen Prüfungstag, -zeit und -raum mitteilen. Sie können dann Ihre Buchung in Moodle nicht mehr ändern.
WICHTIG: zur ordnungsgemäßen Anmeldung zur Prüfung ist beides nötig: eine fristgerechte Anmeldung in AGNES und die Vereinbarung eines konkreten Prüfungstermins.
Wenn Sie bis zum 6.7.25 kein Zeitfenster über Moodle gebucht haben, schicken wir Ihnen eine Mail mit einem von uns festgelegten unveränderbarem Zeitfenster zu.
Die Frist zum Rücktritt von der Prüfung entnehmen Sie der Seite des Prüfungsbüros. Falls ein fristgerechter Rücktritt in AGNES nicht möglich ist, wenden Sie sich bitte ans Prüfungsbüro.
 

 

Literatur

Hauptthema der Vorlesung ist die formale Logik. Folgende Bücher werden dazu zur Vertiefung des Vorlesungsstoffes empfohlen:

[EFT] Heinz-Dieter Ebbinghaus, Jörg Flum, Wolfgang Thomas, Einführung in die Mathematische Logik. 6. Auflage, Springer Spektrum, 2018.
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.
[B] S. Burris, Logic for Mathematics and Computer Science. Prentice Hall, 1998.
[KK] M. Kreuzer, S. Kühling. Logik für Informatiker. Pearson, 2006.
[S] U. Schöning, Logik für Informatiker. 5. Auflage, Spektrum Akademischer Verlag, 2000.

Als Ergänzung seien auch noch folgende Bücher genannt:

[E] Heinz-Dieter Ebbinghaus, Einführung in die Mengenlehre. 4. Auflage, Spektrum Akademischer Verlag, 2003.
[L] Leonid Libkin, Elements of Finite Model Theory. Springer, 2004. Die für die Vorlesung relevanten Teile des Buchs sind hier unter dem mit "Download table of contents and a sample chapter" beschrifteten Link erhältlich.
[FG] Jörg Flum, Martin Grohe, Parameterized Complexity Theory. Springer, 2005.
[C] P. J. Cameron, Sets, Logic and Categories. Springer Verlag, 1998.
[vD] D. van Dalen, Logic and Structure. 4th Edition, Springer Verlag, 2004.
[HR] M. Huth and M. Ryan, Logic in Computer Science – Modelling and Reasoning About Systems . 2nd Edition, Cambridge University Press, 2004.

 

Weitere Materialien

snippets-of-logic: Die in der Vorlesung angesprochenen snippets-of-logic finden sich für Aussagenlogik hier.