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

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

Aktuelles

  • Die Modulabschlussprüfung findet — coronabedingt — als diditale mündliche Prüfung statt, die unter Verwendung von Zoom durchgeführt wird. Details dazu finden sich weiter unten im Punkt Modulabschlussprüfung.
  • Am Mittwoch, den 17.06.20 wurde das Online-Treffen zur Vorlesung ausnahmsweise verschoben: statt 11h15-12h45 fand es 17h15-18h45 statt.
  • Die Veranstaltung findet statt, bei Interesse melden Sie sich bitte über 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 24.04.2020 in den Kurs unter https://moodle.hu-berlin.de/enrol/index.php?id=95688 ein. Der Einschreibeschlüssel wurde an die über AGNES eingeschriebenen Studierenden verschickt und kann von Teilnehmer*innen, die noch nicht über AGNES eingeschrieben sind, auch per Mail an Dr. Markus Schmid erfragt werden.
  • Auf Grund der aktuellen Situation wird die Veranstaltung z.Zt. online durchgeführt: Im Logbuch werden wöchentlich Lektüreaufgaben zum Selbststudium bekannt gegeben. Zum Zeitpunkt der Vorlesungstermine (Mi 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 fand am Mittwoch, den 29.04.2020 statt. Zugangsdaten erhalten Sie über Moodle.

Einführung

Diese Veranstaltung vermittelt eine Einführung in die mathematische Logik und ihre Anwendungen in der Informatik.

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 von Folien:

 

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

 


Logbuch

Im Logbuch werden wöchentlich Lektüreaufgaben zum Selbststudium bekannt gegeben. Zum Zeitpunkt der Vorlesungstermine (Mi 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 fand am Mittwoch, den 29.04.2020 statt. Zugangsdaten erhalten Sie über Moodle.


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:
 
Mittwochs 11:00-13:00 Uhr über Zoom (Zugangsdaten sind über moodle erhältlich)
Dozentin
Prof. Dr. Nicole Schweikardt

Informationen zum Übungsbetrieb

Ergänzend zur Vorlesung findet ein Übungsbetrieb statt, der hauptsächlich über Moodle durchgeführt wird.

Dozent:
Dr. Markus Schmid

Melden Sie sich bitte für den Übungsbetrieb bis zum 24.04.20 in AGNES an.
Bitte schreiben Sie sich außerdem zusätzlich bis zum 24.04.20 in den Moodle-Kurs ein. Der Einschreibeschlüssel wurde an die über AGNES eingeschriebenen Studierenden verschickt und kann von Teilnehmer*innen, die noch nicht über AGNES eingeschrieben sind, auch per Mail an Dr. Markus Schmid erfragt werden.

Der Übungsbetrieb setzt sich aus folgenden drei Teilen zusammen:

  1. Freiwillige Übungen:
    Wir werden Übungsmaterialien verschiedenster Art zur Verfügung stellen, die Ihnen helfen sollen, die Inhalte der Vorlesung zu vertiefen und Ihre Lernfortschritte zu überprüfen. Diese Übungen werden von Ihnen nicht abgegeben und von uns nicht bewertet. Die Bereitstellung, Umfang und Art dieser Übungsaufgaben wird voraussichtlich relativ stark varieren.
  2. Bepunktete Übungen:
    Es wird Übungsaufgaben geben, die sie abgeben sollen und welche wir korrigieren werden. Durch diese Aufgaben können Sie Übungspunkte sammeln, und sie müssen insgesamt 40% der erreichbaren Punkte bekommen, um die Zulassung zur Abschlussprüfung zu erlangen.
    Diese Übungen werden Sie regelmäßig alle zwei Wochen in Form von Übungsblättern auf Moodle erhalten. Die Art der Abgabe und die Anzahl der zu erreichenden Übungspunkte wird jedesmal explizit auf den Übungsblättern vermerkt sein.
    Wichtiger Hinweis: Wir verlangen für die Prüfungszulassung nur, dass Sie 40% aller Übungspunkte erreichen, nicht jedoch, dass sie für jedes Übungsblatt mindestens 40% erreichen. Es ist totzdem ratsam jedes Übungsblatt zu bearbeiten.
  3. Fragen zur Vorlesung, Feedback zu den Übungen:
    Über Moodle werden Sie die Möglichkeit haben Fragen zur Vorlesung und zu den Übungsaufgaben zu stellen (zu den bepunkteten Übungen werden sie feedback durch unsere Korrekturen erhalten, die freiwilligen Übungen können bei Bedarf näher besprochen werden).

Modulabschlussprüfung

Die Modulabschlussprüfung wird - soweit das z.Zt. angesichts der aktuellen durch Covid-19 bedingten Situation absehbar ist - am Ende des Semesters in Form einer Klausur stattfinden.

Hinweise zur Durchführung von Prüfungen und zur An- und Abmeldung zur Prüfung werden gegen Ende des Semesters auf der Seite des Prüfungsbüros zu finden sein.

Die Modulabschlussprüfung findet — coronabedingt — als digitale mündliche Prüfung statt, dauert ca. 30 Minuten und wird mittels Zoom durchgeführt. Bitte kontaktieren Sie Frau Pergl, um einen Termin für die mündliche Prüfung zu reservieren. Zur Zeit stehen Termine im Juli am 20.7.20, 21.7.20 und 22.7.20 zur Verfügung und im Oktober am 6.10.20, 7.10.20 und 8.10.20. Nachdem Sie bei Frau Pergl einen Termin gebucht haben, müssen Sie sich noch über Agnes formal für die Prüfung anmelden. Es gelten die üblichen für Ihre Studiengang relevanten Fristen; Informationen dazu finden Sie auf der Webseite des Prüfungsbüros.


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.