Lehrinhalte
Aufbauend auf der Vorlesung TheGI3 behandelt dieses Modul weiterführende Themen der Logik in der Informatik.
Es werden zunächst verschiedene Anwendungsgebiete der Logik eingeführt, besonders Anwendungen in der Datenbanktheorie, der Algorithmik und Komplexitätstheorie, sowie der automatischen Verifikation.
Im Zentrum des ersten Teils der Vorlesung stehen Fragen zur Ausdrucksstärke verschiedener Logiken und Datnbankabfragesprachen. Es werden Methoden eingeführt um nachzuweisen, dass bestimmte Abfragen nicht in der Prädikatenlogik definiert werden
können. Aufbauend darauf werden dann sogenannte "Lokalitätssätze" bewiesen, die die Ausdrucksstärke der Prädikatenlogik auf sehr überraschende Weise charakterisieren.
Thema des zweiten Teils der Vorlesung ist der Zusammenhang zwischen Logik und Komplexität. Hier steht zunächst die Frage im Vordergrund, wie schwierig es ist, Formeln einer gegebenen Logik in einer Struktur auszuwerten. Vor allem aber werden wir den
Bereich der "deskriptiven Komplexitätstheorie" behandeln, in dem algorithmische Probleme nicht anhand der zu ihrer Lösung benötigten Ressourcen wie Speicherplatz und Laufzeit klassifiziert werden, sondern der zu ihrer Beschreibung nötigen Art und
Zahl logischer Quantoren und Operatoren. Es stellt sich heraus, dass es einen erstaunlich engen Zusammenhang zwischen diesen beiden Arten der Beschreibung von Problemen gibt, in dem Sinne, dass Probleme, die in natürlichen Komplexitätsklassen wie
PTIME oder NP berechnet werden können, auch Beschreibungen in natürlichen Logiken haben. Die Logik bietet demnach einen alternativen und sehr eleganten Zugang zur Komplexitätstheorie, den wir in diesem Teil der Vorlesung behandeln werden.