Logik in der Informatik Prof. Dr. Martin Grohe

Das folgende Inhaltsverzeichnis wird im Laufe der Vorlesung noch ergänzt und verfeinert.

Die Folien werden vor der jeweiligen Vorlesungsstunde hier zur Verfügung gestellt. Durch Anklicken des entsprechenden Paragraphen erhalten Sie die Folien, manchmal mit einigen Ergänzungen, im PDF-Format. Denken Sie daran, dass der Vorlesungstoff nicht nur aus den Folien besteht, sondern auch das an der Tafel präsentierte Material umfasst.

Kapitel 1: Einführung

Kapitel 2: Mathematische Grundlagen

§2.1. Mengen, Relationen und Funktionen

§2.2. Induktion und Rekursion

§2.3. Beispiele: Arithmetische Terme und eine einfache Programmiersprache

Kapitel 3: Aussagenlogik

§3.1. Grundbegriffe

§3.2. Anwendung: Data Mining

§3.3. Erfüllbarkeit

§3.4. Folgerungen und Formale Argumente

§3.5. Anwendung: Planungsprobleme in der künstlichen Intelligenz

§3.6. Anwendung: Schaltkreisverifikation

§3.7. Äquivalenz

§3.8. Boolesche Algebra

§3.9. Die Adäquatheit der Junktoren

§3.10. Normalformen

§3.11. Anwendung: Schaltkreisentwurf

Kapitel 4: Aussagenlogische Deduktion

§4.1. Ein aussagenlogisches Beweissystem

§4.2. Resolution

§4.3. Hornformeln

Kapitel 5: Strukturen

§5.1. Zweistellige Relationen

§5.2. Graphen

§5.3. Algebren

§5.4. Strukturen

Kapitel 6: Die Logik der ersten Stufe

§6.1. Syntax

§6.2. Semantik

§6.3. Anwendung: Wissensrepräsentation

§6.4. Äquivalenz und Normalformen

§6.5. Auswertung von Formeln in endlichen Strukturen

§6.6. Anwendung: Relationale Datenbanken

§6.7. Folgerungen und Beweise

Kapitel 7: Berechenbarkeit

§7.1. Das Halteproblem in JAVA

§7.2. Entscheidbarkeit und Aufzählbarkeit

§7.3. GOTO-Programme (dazu ein GOTO Interpreter)

§7.4. Turingmaschinen (dazu ein Turingmaschinensimulator)

§7.5. Berechenbare Funktionen auf den natürlichen Zahlen

§7.6. Das Halteproblem für GOTO-Programme

§7.7. Unentscheidbarkeit der Logik der ersten Stufe