Modulcode:	Inf-LogInf
Englische Bezeichnung:	Logic in Computer Science
Modulverantwortliche(r):	Prof. Dr. Thomas Wilke
Turnus:	jedes Jahr (SS11 SS12 SS13 SS14 SS15 SS16 WS17/18 WS18/19 WS19/20 WS20/21 WS21/22 WS22/23)
Präsenzzeiten:	4V 2Ü
ECTS:	8
Workload:	60 Std. Vorlesung, 30 Std. Präsenzübung, 150 Std. Selbststudium
Dauer:	ein Semester
Modulkategorien:	A (BSc Inf (15)) A (BSc Inf) WI (MSc WInf (15)) GU (MSc WInf)
Lehrsprache:	Deutsch
Voraussetzungen:	Inf-ADS Inf-Math-A Inf-TGIE

Kurzfassung:

Eine Einführung in die mathematische Logik und deren Anwendung sowie Bezüge zur Informatik.

Lernziele:

Die Studentinnen und Studenten ...

• interpretieren Formeln und Formelmengen der Aussagen- und der Prädikatenlogik,
• modellieren und lösen informatische Problemstellungen in der Aussagen- und der Prädikatenlogik,
• erläutern die grundlegenden Begriffe der Aussagen- und der Prädikatenlogik,
• erklären die fundamentalen Zusammenhänge der Aussagen- und der Prädikatenlogik,
• definieren einfache Begriffe fachgerecht,
• beweisen einfache Sachverhalte.

Zusätzlich erläutern Sie den Zusammenhang zwischen Erfüllbarkeit der Aussagenlogik und NP-Vollständigkeit einerseits und den Zusammenhang zwischen dem Gütligkeitsproblem (Folgerungsproblem) der Prädikatenlogik und Entscheidbarkeit sowie Aufzählbarkeit.

Lehrinhalte:

Es werden die Aussagen- und die Prädikatenlogik behandelt. Die wichtigen Begriffe sind: Syntax, Semantik, Formeln, Strukturen, Interpretationen, Erfüllbarkeit, Konsistenz, Erfüllbarkeitstests, Folgerungstests, Schlussverfahren, Kalküle.

Der Bezug zur Informatik wird insbesondere herstellt durch:

• die Reduktion algorithmischer Probleme auf Erfüllbarkeit,
• konkrete Erfüllbarkeitstests,
• die Verwendung von Kalkülen für die Folgerungsbeziehung in der Aussagen- wie der Prädikatenlogik,
• die Illustration von Theorembeweisern.

Weitere Voraussetzungen:

Grundkenntnisse in Mathematik, algorithmisches Grundverständnis, Grundverständnis von relationalen Datenbanken und Graphen.

Prüfungsleistung:

Prüfungsvorleistungen Es müssen keine Prüfungsvorleistungen erbracht werden.

Berücksichtigung positiver Studienleistungen In Anschluss an den ersten Teil des Moduls (zur Aussagenlogik) wird ein Test angeboten. Das Ergebnis wird auf die Abschlussklausuren angerechnet.

Lehr- und Lernmethoden:

Vorlesung, Arbeits- und Fragestunden, Selbststudium.

Verwendbarkeit:

Literatur:

• Michael Huth, Mark Ryan, Logic in Computer Science: Modelling and Reasoning about Systems, Cambridge University Press, 2004. Zu natürlichen Beweissystemen.
• Uwe Schöning, Logik für Informatiker, Spektrum Akademischer Verlag, 2000. Zu Aussagenlogik und Resolution.
• Mordechai Ben Ari, Mathematical Logic for Computer Science, Springer-Verlag, 2012. Allgemeine Referenz.
• Heinz-Dieter Ebbinghaus, Jörg Flum, Wolfgang Thomas, Mathematical Logic, Springer-Verlag, 2018. Allgemeine Referenz.

Verweise:

Kommentar: