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

Vorlesung Logik in der Informatik (WS 23/24)

 

 


Aktuelles

  • 13.2.24: am Donnerstag, den 15.2., findet keine Vorlesung statt; eine Fragestunde fand bereits heute statt. Wir wünschen allen viel Erfolg bei der Prüfung.
  • 8.2.24: Im Abschnitt Modulabschlussprüfung finden Sie nun eine Zusammenstellung von Hinweisen zur Klausur (inkl. Beispiele früherer Klausuraufgaben; Details zum organisatorischen Ablauf der Klausur folgen demnächst). Bitte lesen Sie sich die dort erhältlichen Informationen und Regelungen sorgfältig durch!
  • 25.1.24: neue Version des Vorlesungsskripts hochgeladen (Änderungen im Vergleich zur vorherigen Version: Beispiel 2.9, Beispiel direkt nach Beispiel 3.18, Beispiel 5.2, Beispiel direkt vor Beispiel 5.13, Beispiel 5.13, Beispiel 5.18)
  • 17.1.24: Die Vorlesung am Donnerstag, den 18.1.24, findet statt.
  • 16.1.24: Krankheitsbedingt wird die Prolog-Übung am Donnerstag, den 18.1.24, leider nicht stattfinden. Die Aufgabe 4 von Blatt 11 (also die aktuelle Prolog-Aufgabe) wird auf Blatt 12 verschoben.
  • 15.1.24: Krankheitsbedingt wird die Vorlesung, wie auch die Prolog-Übung am Dienstag, den 16.1.24, leider nicht stattfinden.
  • 15.11.23: Krankheitsbedingt wird die Vorlesung am Donnerstag, den 16.11.23, nicht stattfinden. Die Prolog-Übung findet -wie geplant- statt.
  • In Blatt 3 wurde ein Fehler in Aufgabe 3c) korrigiert. Bitte nutzen Sie die neue Version des Blattes.
  • Krankheitsbedingt finden am Mittwoch, dem 8.11 die Übungsgruppen 2 und 5 gleichzeitig in Raum 1.305 statt.
  • Die Eröffnungsvorlesung fand am Dienstag, den 17.10.23 um 11:00 Uhr im Hörsaal 0'115 im ESZ (Rudower Chaussee 26) statt.
  • Die Übungen beginnen in der Woche 23.-27.10.23. Falls Sie am Modul "Logik in der Informatik" teilnehmen wollen, melden Sie sich bitte in AGNES für eine Übungsgruppe an (Ende der Nachfrist: 19.10.23).
  • 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 17.10.2023 (Nachfrist: 19.10.23) in den Moodle-Kurs ein. Der Einschreibeschlüssel wurde an die über AGNES eingeschriebenen Studierenden verschickt (am 13.10.23) und kann von den Teilnehmer*innen, die noch nicht über AGNES eingeschrieben sind, danach auch per Emial an Benjamin Hauskeller erfragt werden.
  • Im Logbuch finden Sie (nach den Vorlesungen) Informationen zum Inhalt der einzelnen Vorlesungsstunden, Teile des Vorlesungsskripts und gelegentlich auch Korrekturen und sonstige ergänzende Bemerkungen.

 


Einführung

Logik spielt eine grundlegende Rolle in vielen Bereichen der Informatik, etwa dem Schaltkreisentwurf, dem Software-Engineering, der künstlichen Intelligenz, der Datenbanken und der theoretischen Informatik. Die Logik in der Informatik baut auf der mathematischen Logik auf, die sich etwa seit Ende des 19. Jahrhunderts herausgebildet hat. In den letzten 30 Jahren hat sich die Logik in der Informatik aber in eine eigenständige, von den Anwendungen bestimmte Richtung entwickelt.

Die Vorlesung ist eine Einführung in die Logik und ihre Anwendungen in der Informatik. Darüber hinaus wird die logikbasierte Programmiersprache Prolog eingeführt.

 


Inhalt

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

 

Vorlesungsskript (Version vom 25. Januar 2024)

 

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 oder in Moodle 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, Teile des Vorlesungsskripts und gelegentlich auch Korrekturen und sonstige ergänzende Bemerkungen.

 


Informationen zum Vorlesungsbetrieb

Vorlesungen

Dienstags 11:00-13:00 RUD26 0.115 und
Donnerstags 11:00-13:00 RUD26 0.115
Die Eröffnungsvorlesung findet am Dienstag, dem 17.10.23, ab 11:00 Uhr statt.
Dozentin
Prof. Dr. Nicole Schweikardt

 


Informationen zum Übungsbetrieb

Ergänzend zu den Vorlesungen finden 2-stündige Übungen in kleinen Gruppen statt, in denen Fragen zur Vorlesung diskutiert und die Übungsaufgaben besprochen werden. Die Übungsgruppen treffen sich erstmalig in der zweiten Woche der Vorlesungszeit, also in der Woche vom 23. bis 27.10.23.

 

Übungsgruppenleiter
Dr. André Frochaux
M.Sc. Benjamin Hauskeller
M.Sc. Benjamin Scheidt
Tutor*innen
Dorian Gutschenreiter
Cecilia Lange
Johannes F. Lange
Zeiten und Räume der Übungsgruppen
Gruppe 1:   Montags 15-17, RUD26 1.305 bei M.Sc. Benjamin Scheidt
Gruppe 4:   Montags 15-17, RUD26 1.306 bei Dr. André Frochaux
Gruppe 2:   Mittwochs 11-13, RUD26 1.305 bei M.Sc. Benjamin Scheidt
Gruppe 5:   Mittwochs 11-13, RUD26 1.306 bei M.Sc. Benjamin Hauskeller
Gruppe 3:   Freitags 09-11, RUD26 1.305 bei M.Sc. Benjamin Scheidt
Gruppe 6:   Freitags 09-11, RUD26 1.306 bei M.Sc. Benjamin Hauskeller

Melden Sie sich bitte für eine Übungsgruppe bis zum 11.10.23 (Nachfrist: bis 19.10.23) in AGNES an.

Bitte schreiben Sie sich außerdem zusätzlich bis zum 17.10.23 in den Moodle-Kurs ein. Der Einschreibeschlüssel wird an die über AGNES eingeschriebenen Studierenden verschickt (bis 13.10.23) und kann danach von Teilnehmer*innen, die noch nicht über AGNES eingeschrieben sind, auch per Mail an Benjamin Hauskeller erfragt werden.

 


Informationen zur Prolog-Übung

Ergänzend zu den Vorlesungen und Übungen findet jede Woche eine 2-stündige Prolog-Übung statt, in denen Sie darin unterstützt werden, sich in die Programmiersprache Prolog einzuarbeiten. In der Prolog-Übung werden zusätzliche Programmierbeispiele behandelt und Anleitungen zur Lösung der Prolog-bezogenen Übungsaufgaben gegeben. Die Teilnahme an der Prolog-Übung ist freiwillig und bedarf keiner Anmeldung. Auf der Seite zur Prolog-Übung finden Sie weitere Informationen und (zu gegebener Zeit) den Quellcode der in der Prolog-Übung verwendeten Beispiele.

Die Prolog-Übung findet erstmalig in der zweiten Woche der Vorlesungszeit statt, also am 24.10.23.

 

Zeiten und Räume
Dienstags 09:00-11:00, RUD25 3.213
Donnerstags 09:00-11:00, RUD25 3.213
Dozent
Dr. André Frochaux

Übungsaufgaben

 

Es wird wöchentlich ein Übungsblatt ausgegeben. In der Regel enthält ein Übungsblatt vier Aufgaben:

  1. Aufgabe: wird elektronisch als Moodle-Quiz organisiert
  2. Aufgabe: dient in der zugehörigen Übungsstunde als Präsenzaufgabe
  3. Aufgabe: die handschriftlich und in deutscher Sprache formulierte Lösung soll eingescannt und über Moodle abgegeben werden
  4. Aufgabe: behandelt das Thema "Prolog"; die Lösung soll über Moodle abgegeben werden

 

Davon abweichend wird das Übungsblatt 0 nur eine "1. Aufgabe" haben. Das Übungsblatt 0 wird Ihnen hier am 17.10.23 bereitgestellt und muss bis zum 23.10.23, 13:00 Uhr bearbeitet werden.

  • Blatt 0 (wird bereitgestellt am 17.10., Bearbeitung bis zum 23.10., 13:00 Uhr)
  • Blatt 1 (wird bereitgestellt am 20.10., Bearbeitung bis zum 30.10., 13:00 Uhr)
  • Blatt 2 (wird bereitgestellt am 27.10., Bearbeitung bis zum 6.11., 13:00 Uhr)
  • Blatt 3v2 (wird bereitgestellt am 3.11., Bearbeitung bis zum 13.11., 13:00 Uhr) Beachten Sie die Korrektur in Aufgabe 3c)!
  • Blatt 4 (wird bereitgestellt am 10.11., Bearbeitung bis zum 20.11., 13:00 Uhr)
  • Blatt 5 (wird bereitgestellt am 17.11., Bearbeitung bis zum 27.11., 13:00 Uhr)
  • Blatt 6 (wird bereitgestellt am 24.11., Bearbeitung bis zum 4.12., 13:00 Uhr)
  • Blatt 7 (wird bereitgestellt am 1.12., Bearbeitung bis zum 11.12., 13:00 Uhr)
  • Blatt 8 (wird bereitgestellt am 8.12., Bearbeitung bis zum 18.12., 13:00 Uhr)
  • Blatt 9 (wird bereitgestellt am 15.12., Bearbeitung bis zum 8.1.24, 13:00 Uhr)
  • Blatt 10 (wird bereitgestellt am 5.1., Bearbeitung bis zum 15.1., 13:00 Uhr)
  • Blatt 11 (wird bereitgestellt am 12.1., Bearbeitung bis zum 22.1., 13:00 Uhr) (Aufgabe 4 wird auf Blatt 12 verschoben)
  • Blatt 12 (wird bereitgestellt am 19.1., Bearbeitung bis zum 29.1., 13:00 Uhr)
  • Blatt 13 (wird bereitgestellt am 26.1., Bearbeitung bis zum 5.2., 13:00 Uhr)
  • Blatt 14 (wird bereitgestellt am 2.2., Präsenzblatt für die letzte Übung)

Jedes weitere Übungsblatt wird jeweils freitags an dieser Stelle bereitgestellt.

Die Lösungen der Aufgaben 1, 3 und 4 müssen dann bis zur übernächsten Woche montags um 13:00 Uhr über Moodle eingereicht werden. Geben Sie auf jeder Abgabe bitte Ihre Matrikelnummer an.
Eine verspätete Abgabe ist nicht möglich.

Wir raten Ihnen, über die Aufgaben mit Kommiliton*innen gemeinsam zu reden und nachzudenken. Aber zur Abgabe der Lösungen muss jede*r Student*in seine*ihre Lösung selbst aufschreiben und abgeben.

Die von Ihnen abgegebenen Lösungen werden in der Woche der Abgabe in den Übungsstunden besprochen und von unseren Tutor*innen korrigiert und bewertet. Die Aufgaben 1-3 werden in den Übungsstunden besprochen; die Prolog-basierte Aufgabe 4 wird in der Prolog-Übung besprochen.

 


Voraussetzung für die Zulassung zur Modulabschlussprüfung

 

Um die Zulassung zur Modulabschlussprüfung zu erhalten, muss der Übungsschein erarbeitet werden; um den Übungsschein zu bekommen, muss jede der folgenden Bedingungen erfüllt werden:

  1. Für jedes Übungsblatt bis auf max. 2 Stück muss das zur Aufgabe 1 gehörende Moodle-Quiz bestanden werden, und
  2. mindestens 40 % der während des Semesters insgesamt in den Aufgaben 3 und 4 maximal erreichbaren Punkte müssen tatsächlich erreicht werden.

 


Modulabschlussprüfung

Die Klausur dauert 2 Stunden. Sie wird in Präsenz stattfinden.

  • Die erste Klausur findet am 21.02.2024 um 11:40 Uhr (Einlass ab 11:15 Uhr) in den Räumen 0'115, 0'110 und 0'307 im ESZ statt.
    • Teilnehmer:innen, deren Nachname mit einem Buchstaben von A bis P beginnt, schreiben im Raum 0'115 im ESZ
    • Teilnehmer:innen, deren Nachname mit einem Buchstaben von R bis Z beginnt, schreiben im Raum 0'110 im ESZ
  • Die zweite Klausur findet am 12.04.2024 um 09:40 Uhr (Einlass ab 09:15 Uhr) in den Räumen 0'115 und 0'110 im ESZ statt.

Den vollständigen Prüfungsplan sowie Hinweise zur An- und Abmeldung finden Sie auf der Seite des Prüfungsbüros. Eine Anmeldung ist auch möglich, falls Sie die Zulassung zur Prüfung noch nicht erhalten haben.

Auf der folgenden verlinkten Seite finden Sie weitere Hinweise zur Klausur.

 


Literatur

Haupthema der Vorlesung ist die Logik. Folgende Bücher seien dazu zur Vertiefung des Vorlesungstoffes empfohlen:

[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:

 

[EFT] Heinz-Dieter Ebbinghaus, Jörg Flum, Wolfgang Thomas, Einführung in die Mathematische Logik. 5. Auflage, Spektrum Akademischer Verlag, 2007. Online ist die 6. Auflage verfügbar.
[E] Heinz-Dieter Ebbinghaus, Einführung in die Mengenlehre. 4. Auflage, Spektrum Akademischer Verlag, 2003. Online ist die 5. Auflage verfügbar.
[L] Leonid Libkin, Elements of Finite Model Theory. Springer, 2004. Über den Link sind die für die Vorlesung relevanten Teile des Buchs unter "Download table of contents and a sample chapter" 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, 2003.

Im praktischen Teil der Veranstaltung beschäftigen wir uns mit der Programmiersprache Prolog. Hier basiert die Vorlesung auf den folgenden beiden Büchern:

[BBS] Patrick Blackburn, Johan Bos, Kristina Striegnitz, Learn PROLOG Now!. Kings College Publications, 2006.
[SS]

Ehud Shapiro, Leon Sterling, The Art of PROLOG: Advanced Programming Techniques. 2nd Edition, MIT Press, 1994.

Zugang zur Online-Literatur

Einige der Bücher sind für Angehörige der HU Berlin online erhältlich (siehe Verlinkung). Loggen Sie sich dazu auf der Springerlink-Seite via Shibboleth mit ihrem CMS-Account ein (über Log In, Access via your institution bzw. Shibboleth-Login, Find your institution: Humboldt-Universität zu Berlin). Alternativ können Sie ggf. über eine VPN-Verbindung über das HU-Netz direkt darauf zugreifen. Zur Einrichtung eines VPN-Zugangs siehe die Anleitung des CMS.


Weitere Materialien

Programmierresourcen: Wir verwenden in der Vorlesung SWI-Prolog. Für den Einstieg steht Ihnen folgende Kurzanleitung zur Verfügung.

snippets-of-logic: Dort finden Sie u.a. einen Formelchecker für Aussagenlogik.