Modal Logic

Technische Universität Dresden Institut für Theoretische Informatik Lehrstuhl für Automatentheorie

Dr. Carsten Lutz

Course Description

Modal logics are an important tool for talking about relational structures and have many applications, for example, in computer science, philosophy, and lingustics. This course is an introduction to "pure" modal logic covering many fundamental topics such as modal expressivity, completeness theory, and computational complexity.

Prerequisites: an acquaintance with the basics of propositional and first-order logic is expected. Some knowledge in complexity theory will also be helpful.

Organization

On June, 23rd and June, 30th, the lecture will take place in Room GRU 370

The lecture takes place once a week in room GRU 350: Monday 13:00-14:30.

There is no exercise group, though some (voluntary) exercises are given in the lecture.

Course Material

Some slides used in the lecture are available here:

• Table of contents
• Semantics of modal logics
• Disjoint Unions
• Bisimulation
• Logics of Knowledge and Belief
• (Normal) Modal Logic and Consistency
• Axioms and Logics
• Proof of Lemma 3.14
• (Partial) proof of Lemma 3.15
• Lemma 3.34 with corrected proof
• The Logic KvB
• Complexity Classes
• Formulas used in Theorem 4.14 and Theorem 4.17
• The PSpace algorithm for K

Credits / Examinations

Computational logic students can earn 3 credits by attending this lecture. In order to get the credits, CL students have to pass a short oral examination at the end of the term.

The oral examinations will take place on July, 29th in Room GRU 433.

Reference

• Sally Popkorn. First Steps in Modal Logic. 314 pages, Cambridge University Press, 1994.

• Patrick Blackburn, Maarten de Rijke, Yde Venema. Modal Logic. 554 pages, Cambridge University Press, 2001.

• Alexander Chagrov and Michael Zakharyaschev. Modal Logic. 605 pages, Oxford University Press, 1997.