# Mathematical Logic

## SS 2022

Note: This course was held in German (except for tutorial 11).

### Schedule

Type Date Location   Organizer
V3 Wed 09:00 10:00 1420|002 (Roter Hörsaal) Lecture (Start 6th April) E. Grädel
Thu 14:30 15:45 1420|002 (Roter Hörsaal) Lecture (Start 7th April) E. Grädel
Ü2 Tue 10:30 12:00 2356|050 (AH V) Tutorial 1 (Start 12th April) L. Meffert
Tue 18:30 20:00 1010|141 (IV) and online (link) Tutorial 2 (Start 12th April) J. Arpasi
Wed 10:30 12:00 1010|141 (IV) Tutorial 3 (Start 13th April) B. Pago
Wed 12:30 14:00 2356|056 (5056) Tutorial 4 (Start 13th April) E. Lüpfert
Wed 16:30 18:00 online (Zoom) Tutorial 12 (Start 13th April) L. Mrkonjić
Thu 10:30 12:00 2350|111 (AH II) Tutorial 6 (Start 14th April) D. Zilken
Thu 12:30 14:00 2356|056 (5056) Tutorial 7 (Start 14th April) M. Naaf
Thu 16:30 18:00 online (Zoom) Tutorial 13 (Start 14th April) J. Schneider
Thu 18:30 20:00 2350|314.1 (AH III) Tutorial 8 (Start 14th April) T. Becker
Fri 12:30 14:00 1010|101 (I) Tutorial 9 (Start 22nd April) M. Pakhomenko
Fri 14:30 16:00 2350|111 (AH II) Tutorial 10 (Start 22nd April) I. Hergeth
Fri 16:30 18:00 1010|141 (IV) Tutorial 11 (Start 22nd April), in English T. Novotný

### Exam

The course Mathematical Logic is completed by passing a written exam lasting 120 minutes.

For the exam admission, it suffices to obtain 50% of all homework points and 50% of all eTest points.

### Content

• Propositional logic (foundations, algorithmical questions, compactness, resolution, sequent calculus)
• Structures, syntax and semantic of first-order logic
• Introduction into other logics (modal and temporal logics, higher order logics)
• Evaluation games, model comparison games
• Proof calculi, term structures, completeness theorem
• Compactness theorem and applications
• Decidability, undecidability and complexity of logical specifications

### Literature

 [1] S. Burris. Logic for Mathematics and Computer Science. Prentice Hall, 1998. [2] R. Cori and D. Lascar. Logique mathématique. Masson, 1993. [3] H. Ebbinghaus, J. Flum, and W. Thomas. Einführung in die mathematische Logik. Wissenschaftliche Buchgesellschaft, Darmstadt, 1986. [4] M. Huth and M. Ryan. Logic in Computer Science. Modelling and reasoning about systems. Cambridge University Press, 2000. [5] B. Heinemann and K. Weihrauch. Logik für Informatiker. Teubner, 1992. [6] H. K. Büning and T. Lettman. Aussagenlogik: Deduktion und Algorithmen. Teubner, 1994. [7] S. Popkorn. First Steps in Modal Logic. Cambridge University Press, 1994. [8] W. Rautenberg. Einführung in die Mathematische Logik. Vieweg, 1996. [9] U. Schöning. Logik für Informatiker. Spektrum Verlag, 1995. [10] D. van Dalen. Logic and Structure. Springer, Berlin, Heidelberg, 1983.

### Classification

• Grundlagen der Informatik (B.Sc.) / Themenmodule / Themenmodul Wahlpflicht Mathematik
• Informatik (B.Sc.) / Modulbereich Theoretische Informatik
• Mathematik (B.Sc.) / Wahlpflichtbereich

### Prerequisites

• basic mathematical knowledge from the lectures Discrete Structures and Linear Algebra
• basic knowledge about recursion theory and complexity theory

### Successive Courses

• Mathematical Logic II
• Logic and Games
• Algorithmic Model Theory
• other specialized lectures around the topic of Mathematical Logic

### Recurrence

every year in the summer term

### Contact

Erich Grädel, Lovro Mrkonjić