Script | Literature | Links  

Logik in der Informatik

Lecture

Introduction

Die mathematische Logik beschäftigt sich mit den grundlegenden Eigenschaften von formalen Systemen und Sprachen. Wichtige Themen der Logik in der Informatik sind die Ausdrucksstärke formaler Sprachen und die Grenzen und Möglichkeiten des automatischen Schließens. Anwendungen der Logik finden sich in unterschiedlichen Bereichen der Informatik, beispielsweise Rechnerarchitektur, Softwaretechnik, Programmiersprachen, Datenbanken, künstliche Intelligenz, Komplexitäts- und Berechenbarkeitstheorie. In dieser Vorlesung werden klassische Resultate der mathematischen Logik und deren Anwendungen in verschiedenen Bereichen der Informatik vorgestellt. Themen sind beispielsweise: Ausdrucksstärke und Auswertungskomplexität der Logik erster Stufe (Prädikatenlogik), Ehrenfeucht-Fraïssé Spiele, der Satz von Hanf, der Satz von Gaifman, der Satz von Trakhtenbrot, der Vollständigkeitssatz der Logik erster Stufe, die Gödelschen Unvollständigkeitssätze.

Ziel dieser Veranstaltung ist, grundlegende Resultate der mathematischen Logik sowie deren Anwendungen in der Informatik zu verstehen.

Kürzel laut Studienordnung: B-LI, M-LI.  Creditpoints: 9.  SWS: 4 V, 2 Ü.

Script

Literature

[S] N. Schweikardt. Skript zur Vorlesung "Logik in der Informatik", Goethe-Universität Frankfurt am Main, 2011. Link
[EFT] H.-D. Ebbinghaus, J. Flum, W. Thomas. Einführung in die Mathematische Logik. 5. Auflage, Spektrum Akademischer Verlag, 2007.
[FG] J. Flum, M. Grohe. Parameterized Complexity Theory. Springer-Verlag, 2006.
[EF] H.-D. Ebbinghaus und J. Flum. Finite Model Theory. Springer-Verlag, 2te Auflage, 1999.
[L] L. Libkin. Elements of Finite Model Theory. Springer-Verlag, 2004.
[G] E. Grädel, P. Kolaitis, L. Libkin, M. Marx, J. Spencer, M. Vardi, Y. Venema und S. Weinstein. Finite Model Theory and Its Applications. Springer-Verlag, 2007.
[KK] M. Kreuzer und S. Kühling. Logik für Informatiker. Pearson Studium, 2006.
[S-Logik] U. Schöning. Logik für Informatiker. Springer, 2000
[HR] M. Huth and M. Ryan. Logic in Computer Science - Modelling and Reasoning About Systems. 2nd Edition, Cambridge University Press, 2004.
[BBJ] G. S. Boolos, J. P. Burgess, R. C. Jeffrey. Computability and Logic. 5th Edition, Cambridge University Press, 2007.
[HHIKVV] J. Y. Halpern, R. Harper, N. Immerman, P. G. Kolaitis, M. Y. Vardi, V. Vianu. On the unusual effectiveness of logic in computer science. The Bulletin of Symbolic Logic. Volume 7, Number 2, June 2001 :  Der Artikel ist online hier verfügbar.
[Gaifman] H. Gaifman. On local and non-local properties. Proceedings of the Herbrand Symposium, Logic Colloqium'81, J.Stearn (editor), pp.105-135. North-Holland Publishing Company, 1982.
[Logicomix] A. Doxiaidis, C.H. Papadimitriou, A. Papadatos, A. Di Donna. Logicomix: An Epic Search for Truth. Bloomsbury USA, 2009 :  Informationen zu diesem Comic sind hier erhältlich.

Links

[LICS] IEEE Symposium on Logic in Computer Science (LICS)
[EACSL] European Association for Computer Science Logic (EACSL)