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

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

Sommersemester 2022

 

Aktuelles

  • 21.07.22: Die mündlichen Prüfungen (im Juli 2022 und im Oktober 2022) zum Modul "Einführung in die formale Logik für IMP" werden alle in Raum 3.408 im Johann von Neumann-Haus stattfinden.
  • 23.06.22: Unter Prüfung gibt es neue Hinweise zu der Modulabschlussprüfung
  • 31.05.22: Unter Prüfung gibt es neue Hinweise zu der Modulabschlussprüfung
  • 20.05.22: Heute wurde eine neue Version des Skripts hochgeladen. Auf den Seiten 75-77 wurden Details zum Thema Graphen und Färbungen eingearbeitet, die in der Vorlesungsstunde vom 18.05.22 an der Tafel behandelt wurden.
  • 18.05.22: Die Aufgaben 2b) und 2c) wurden von Blatt 4 auf Blatt 5 verschoben.
  • 21.04.22: Heute wurde eine neue Version von Skript und Handout hochgeladen (es wurden einige Details in Kapitel 2 geändert).
  • Im Logbuch werden wöchentlich Informationen dazu bereit gestellt, 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.
  • Die Eröffnungsvorlesung fand am Mittwoch, den 20.04.22 statt. Die erste Übungsstunde findet am Donnerstag, den 28.04.22 statt.

 

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 und Handout zu den in der Vorlesung verwendeten Folien (werden im Laufe des Semesters aktualisiert):

 

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 bereit gestellt, 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 Erwin-Schrödinger-Zentrum (Rudower Chaussee 26), Raum 1'303

Dozentin: Prof. Dr. Nicole Schweikardt

Die Eröffnungsvorlesung fand am 20.04.22 statt.

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

Übungsleiter: Benjamin Scheidt

Die erste Übungsstunde fand am 28.04.22 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 Montag Mittag online bereit gestellt.

Die Abgabe der bearbeiteten Aufgaben erfolgt jeweils am darauf folgenden Montag Vormittag 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.

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.

 

Modulabschlussprüfung

Zur Vorbereitung auf eine Prüfung (Modulabschlussprüfung) ist es unbedingt notwendig, das gesamte in den Vorlesungs- und Übungsstunden vermittelte sowie 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 abgelegt. Auf der Seite des Prüfungsbüros finden Sie den vollständigen Prüfungsplan (inkl. Prüfungszeitraum, Anmeldefristen). Die Prüfungen im Juli 2022 und Oktober 2022 für dieses Modul finden in Raum 3.408 statt.

Hinweise zur Prüfungsanmeldung

  1. Die MAP wird als mündliche Prüfung durchgeführt. Dafür müsst ihr euch in Agnes angemeldet haben – die Frist dafür endet am 3. Juli! Direkt daran anschließend vereinbart ihr einen konkreten Termin über das Sekretariat (an Gesine Pergel mit  Petra Kämpfer im CC). Nennt dabei bitte euren Namen, eure Matrikelnummer und das Modul (Einführung in die formale Logik für IMP) und bittet darum, einen konkreten Prüfungstermin (Tag und Uhrzeit) zugeteilt zu bekommen. Wichtig: zur ordnungsgemäßen Anmeldung zur MAP ist beides nötig: Anmeldung in Agnes und Vereinbarung eines konkreten Prüfungstermins
  2. In Agnes meldet ihr euch zwar für den Montag, den 25.7. an, der Termin kann aber an einem beliebigen Tag innerhalb des Prüfungszeitraumes (25.-28.07.22) liegen.
  3. Ihr könnt euch auch anmelden, falls ihr den Übungsschein (und damit die Zulassung zur MAP) zum jetzigen Zeitpunkt noch nicht besitzt. Solltet ihr ihn bis zum Ende des Semesters nicht besitzen, werdet ihr automatisch wieder abgemeldet (ohne dass für euch Nachteile entstehen). Umgekehrt ist der 3. Juli eine harte Frist: Danach ist keine Anmeldung mehr möglich!
  4. Die Frist zum Rücktritt von der Prüfung entnehmt ihr den Seiten des Prüfungsbüros. Solltet ihr vor Ablauf der Frist zurücktreten wollen, Agnes euch den Rücktritt jedoch nicht mehr ermöglichen (bspw. weil in Agnes der 25.7. als Prüfungsdatum steht, eure Prüfung jedoch erst am 28.7. stattfindet), meldet ihr euch per Mail an das Prüfungsbüro (mit Prof. Schweikardt im CC) von der Prüfung ab.

 

Literatur

Haupthema der Vorlesung ist die formale Logik. Folgende Bücher werden dazu zur Vertiefung des Vorlesungstoffes 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.