# 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

  S. Burris. Logic for Mathematics and Computer Science. Prentice Hall, 1998.  R. Cori and D. Lascar. Logique mathématique. Masson, 1993.  H. Ebbinghaus, J. Flum, and W. Thomas. Einführung in die mathematische Logik. Wissenschaftliche Buchgesellschaft, Darmstadt, 1986.  M. Huth and M. Ryan. Logic in Computer Science. Modelling and reasoning about systems. Cambridge University Press, 2000.  B. Heinemann and K. Weihrauch. Logik für Informatiker. Teubner, 1992.  H. K. Büning and T. Lettman. Aussagenlogik: Deduktion und Algorithmen. Teubner, 1994.  S. Popkorn. First Steps in Modal Logic. Cambridge University Press, 1994.  W. Rautenberg. Einführung in die Mathematische Logik. Vieweg, 1996.  U. Schöning. Logik für Informatiker. Spektrum Verlag, 1995.  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ć