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

VL Logik in der Informatik (WS 21/22)

 

 


Aktuelles

  • 21.01.2022: Im Abschnitt Modulabschlussprüfung finden Sie nun eine Zusammenstellung von Hinweisen zur Klausur (inkl. Beispiele früherer Klausuraufgaben sowie Details zum organisatorischen Ablauf der Klausur). Bitte lesen Sie sich die dort erhältlichen Informationen und Regelungen sorgfältig durch!
  • Krankheitsbedingt muss die Prolog-Übung  am 13. Januar leider ausfallen; die Bearbeitung und Abgabe der Aufgabe 4 von Blatt 10 wird auf das Blatt 11 verschoben.
  • Die Termine für die Klausur stehen nun fest. Details zu den Terminen und Ablauf der Klausur finden Sie hier.
  • Aufgrund der anhaltenden Corona-Lage werden weiterhin bis Ende Januar 2022 die Logik-Übungen  in digitalter Form stattfinden (Zugangsdaten zu den Zoom-Meetings sind über Moodle erhältlich). Wir werden die Entwicklung weiter beobachten und rechtzeitig bekanntgeben, in welcher Form die Übungen im Februar durchgeführt werden.
  • 16.11.21: Krankheitsbedingt muss das heutige Online-Treffen zur Vorlesung leider ausfallen. Die eigentlich fürs heutige Treffen geplanten Seiten 83-93 des Vorlesungsskripts werden im Online-Treffen zur Vorlesung am Donnerstag (18.11.21) besprochen.
  • Aufgrund der aktuellen Corona-Lage werden ab sofort (16.11.21) bis zum 03.12.21 die Logik-Übungen nicht mehr "in Präsenz", sondern in digitalter Form stattfinden (Zugangsdaten zu den Zoom-Meetings sind über Moodle erhältlich). Wir werden die Entwicklung weiter beobachten und rechtzeitig vor dem 3.12.21 bekanntgeben, in welcher Form die Übungen in der Zeit ab 4.12.21 dann durchgeführt werden.
  • Pandemiebedingt findet die Veranstaltung in diesem Semester in einer Kombination aus digitalen und vor-Ort-Terminen statt: Die Vorlesungen sowie die Prolog-Übung werden in rein digitaler Form per Zoom durchgeführt; für die Übungsgruppen gibt es Gruppen, die "in Präsenz" stattfinden (montags und mittwochs) und Gruppen, die per Zoom durchgeführt werden (freitags). Die Eröffnungsvorlesung fand am Dienstag, den 19.10.21 ab 11:15 Uhr statt. Der Übungsbetrieb (inkl. Prolog-Übung) startet in der zweiten Woche der Vorlesungszeit, also in der Woche vom 25.-29.10.21.
  • Falls Sie am Modul "Logik in der Informatik" teilnehmen wollen, melden Sie sich bitte für eine Übungsgruppe bis zum 13.10.21 (Nachfrist: bis 21.10.21) in AGNES an.
  • 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 20.10.2021 in den Kurs unter Moodle-Kurs ein. Der Einschreibeschlüssel wird an die über AGNES eingeschriebenen Studierenden verschickt (bis 15.10.21) und kann von Teilnehmer*innen, die noch nicht über AGNES eingeschrieben sind, auch per Mail an Benjamin Hauskeller erfragt werden.
  • Im Logbuch werden regelmäßig Lektüreaufgaben zum Selbststudium bekannt gegeben. Zum Zeitpunkt der Vorlesungstermine (Di+Do 11-13 Uhr) finden Online-Treffen mittels Zoom statt, in denen Fragen der Teilnehmer*innen zum Lektürestoff beantwortet werden und das durch die Lektüre angeeignete Wissen vertieft wird. Das erste solche Online-Treffen findet am Donnerstag, den 21.10.2021 statt; Zugangsdaten erhalten Sie über Moodle.

 


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 und Handout zu den in der Vorlesung verwendeten Folien:

 

Beachten Sie:
Zur Vorbereitung auf eine Prüfung wird dringend empfohlen, das gesamte in den Vorlesungs- und Übungsstunden sowie der Prolog-Übung vermittelte Material durchzuarbeiten.

 


Logbuch

Im Logbuch werden regelmäßig Lektüreaufgaben zum Selbststudium bekannt gegeben. Zum Zeitpunkt der Vorlesungstermine (Di+Do 11-13 Uhr) finden Online-Treffen mittels Zoom statt, in denen Fragen der Teilnehmer*innen zum Lektürestoff beantwortet werden und das durch die Lektüre angeeignete Wissen vertieft wird. Das erste solche Online-Treffen findet am Donnerstag, den 21.10.2021 statt; Zugangsdaten erhalten Sie über den Moodle-Kurs.

 


Informationen zum Vorlesungsbetrieb

Es finden regelmäßig Online-Treffen statt, in denen Fragen der Teilnehmer*innen zum Lektürestoff beantwortet werden und das durch die Lektüre angeeignete Wissen vertieft wird:

Dienstags 11:15-13:00 und
Donnerstags 11:15-13:00
über Zoom. Die Eröffnungsvorlesung fand am Dienstag, den 19.10.21 ab 11:15 Uhr statt. Die Zugangsdaten zu den nachfolgenden Online-Treffen zur Vorlesung ab dem 21.10.21 sind über Moodle erhältlich.
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 25.-29.10.21.

 

Übungsgruppenleiter:
Dr. André Frochaux
Benjamin Hauskeller
Tutoren:
Leonid Antipov
Johannes F. Lange
Benjamin Scheidt
Zeiten und Räume der Übungsgruppen (Zugangsdaten zu den jeweiligen Zoom-Meetingräumen sind über Moodle erhältlich):
Gruppe 1 (Präsenz digital):   Montags 15-17, RUD26 1.306  bei Benjamin Hauskeller
Gruppe 2 (Präsenz digital):   Montags 15-17, RUD26 1.303 bei Dr. André Frochaux
Gruppe 3 (Präsenz digital):   Mittwochs 11-13, RUD26 1.306 bei Benjamin Hauskeller
Gruppe 4 (Präsenz digital):   Mittwochs 11-13, RUD26 1.303 bei Dr. André Frochaux.
Gruppe 5 (digital):   Freitags 09-11, digital bei Benjamin Hauskeller
Gruppe 6 (digital):   Freitags 09-11, digital bei Dr. André Frochaux

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

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

 

Hinweise zum Präsenzbetrieb

Falls Sie sich mit COVID-19 infiziert haben:

Melden Sie umgehend die von Ihnen besuchten Präsenzveranstaltungen an anwesende (at) hu-berlin.de. Für unsere Veranstaltungen geben Sie hierfür den Tag und die Uhrzeit sowie den jeweiligen Übungsleiter mitsamt Emailadresse an, also
 
André Frochaux   andre.frochaux (at) informatik.hu-berlin.de
                        oder
Benjamin Hauskeller  hauskeller (at) hu-berlin.de
 
Dieselben Daten geben Sie bitte auch dem Gesundheitsamt an. Bitte informieren Sie auch den jeweiligen Übungsleiter direkt über die Infektion; selbstverständlich werden wir ihre personenbezogenen Daten vertraulich behandeln.
 

Falls eine (vermutlich) infizierte Person an einer Übung teilgenommen hat

In diesem Fall muss die entsprechende Übung für mindestens eine Woche in den digitalen Modus wechseln. Die Übungsleiter informieren Sie hierüber per Moodle-Direktnachricht. Standardmäßig erhalten sie diese Nachricht auf die Mailadresse, die für Sie bei Moodle hinterlegt ist. Prüfen Sie daher dieses Mailkonto regelmäßig auf neue Nachrichten.

 


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 zweite Woche der Vorlesungszeit statt, also am 28.10.21.

 

Zeiten und Räume
Donnerstags 09:00-11:00 digital (Zugangsdaten zum Zoom-Meetingraum sind über Moodle erhältlich)
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 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 19.10.21 bereitgestellt und muss bis zum 25.10.21, 13:00 Uhr bearbeitet werden.

  • Blatt 0 (ausgeteilt am 19.10., Abgabe bis zum 25.10., 13:00)
  • Blatt 1 (ausgeteilt am 22.10., Abgabe bis zum 1.11., 13:00)
  • Blatt 2 (ausgeteilt am 29.10., Abgabe bis zum 8.11., 13:00)
  • Blatt 3 (ausgeteilt am 5.11., Abgabe bis zum 15.11., 13:00)
  • Blatt 4 (ausgeteilt am 12.11., Abgabe bis zum 22.11., 13:00)
  • Blatt 5 (ausgeteilt am 19.11., Abgabe bis zum 29.11., 13:00)
  • Blatt 6 (ausgeteilt am 26.11., Abgabe bis zum 6.12., 13:00)
  • Blatt 7 (ausgeteilt am 3.12., Abgabe bis zum 13.12., 13:00)
  • Blatt 8 (ausgeteilt am 10.12., Abgabe bis zum 03.01.22, 13:00) [update 13.12.: Kleiner Typo in 3a (ii). ]
  • Blatt 9 (ausgeteilt am 17.12., Abgabe bis zum 10.01.22, 13:00)
  • Blatt 10 (ausgeteilt am 7.1., Abgabe bis zum 17.01.22, 13:00) [update 12.1: Die Aufgabe 4 wird ersatzlos auf Blatt 11 verschoben]
  • Blatt 11 (ausgeteilt am 14.1., Abgabe bis zum 24.01.22, 13:00)
  • Blatt 12 (ausgeteilt am 21.1., Abgabe bis zum 31.01.22, 13:00)


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 Kommilitonen*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 Tutoren*innen korrigiert. 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 jede der folgenden Bedingungen erfüllt sein:

  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 23.02.2022 um 11:40 Uhr (Einlass ab 11:15 Uhr) statt. Achtung: Anmeldung endet bereits am 21.01.2022!
  • Die Wiederholungsklausur findet am 11.04.2022 um 09:40 Uhr (Einlass ab 09:15 Uhr) statt. Achtung: Anmeldung endet bereits am 18.03.2022!

Den vollständigen Prüfungsplan sowie Hinweise zur An- und Abmeldung finden Sie auf der Seite des Prüfungsbüros.

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

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. Online version.
[SS] Ehud Shapiro, Leon Sterling, The Art of PROLOG: Advanced Programming Techniques. 2nd Edition, MIT Press, 1994.

Weitere Materialien

Programmierresourcen: Wir verwenden in der Vorlesung SWI-Prolog. Ein Kurzanleitung für den Einstieg in SWI-Prolog finden Sie hier.

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