Introduction to Modal Logic

6 EC

Semester 1, period 1, 2

5122INML6Y

Owner Bachelor Wiskunde
Coordinator N. Bezhanishvili
Part of Master Logic, Minor Logic and Computation, year 1Master Computer Science (joint degree), track Foundations of Computing and Concurrency, Exchange Programme Faculty of Science, specialisation BSc Mathematics, year 1Bachelor Wiskunde, year 3Dubbele bachelor Wiskunde en Informatica, year 3

Course manual 2019/2020

Course content

Het vak behandelt de basisbegrippen van de modale logica: syntax, relationele semantiek, modellen en frames, bisimulaties, model- en frametheoretische constructies, volledigheid.

The course covers the basic notions of modal logic: syntax, relational semantics, models and frames, bisimulations, model theoretic and frame theoretic constructions, completeness. More advanced topics include expressive power and neighbourhood frames.

Study materials

Literature

  • De Rijke en Venema, 'Modal Logic', Blackburn, Cambridge University Press, 2001.

Objectives

  • Students should be able to point out when a modal formula is satisfied/valid on a given Kripke model/frame.
  • Students should be able to compute standard translations of modal formulas and first-order correspondents of Sahlqvist formulas.
  • Students are expected to produce a completeness proof via the canonical model construction for some basic systems of modal logic.
  • Students should also be able to derive finite model property of such systems via the method of filtration.
  • Students should be able to argue about decidability of simple systems of modal logic by combining finite axiomatization and the finite model property of these systems.
  • Students are also expected to solve basic problems involving more complex modal systems such as PDL.

Teaching methods

  • Lecture
  • Seminar

Hoorcollege en werkcollege.
Lectures and tutorials.

Learning activities

Activiteit

Aantal uur

Hoorcollege

28

Tentamen

3

Tussentoets

2
   

Werkcollege

28

Zelfstudie

83

Attendance

Programme's requirements concerning attendance (OER-B):

  • Each student is expected to actively participate in the course for which he/she is registered.
  • If a student can not be present due to personal circumstances with a compulsory part of the programme, he / she must report this as quickly as possible in writing to the relevant lecturer and study advisor.
  • It is not allowed to miss obligatory parts of the programme's component if there is no case of circumstances beyond one's control.
  • In case of participating qualitatively or quantitatively insufficiently, the examiner can expel a student from further participation in the programme's component or a part of that component. Conditions for sufficient participation are stated in advance in the course manual and on Canvas.
  • In the first and second year, a student should be present in at least 80% of the seminars and tutor groups. Moreover, participation to midterm tests and obligatory homework is required. If the student does not comply with these obligations, the student is expelled from the resit of this course. In case of personal circumstances, as described in OER-A Article 6.4, an other arrangement will be proposed in consultation with the study advisor.

Assessment

Item and weight Details

Final grade

1 (100%)

Tussentoets

There will be 6 Homework sheets. There will be a midterm exam and also a final exam. The final grade consists 50% of the homework grade, 10% of the grade of the midterm exam and 40% of the grade of the final exam. The homework grade is split into 6 homework sheets weighing 100 points each.

Fraud and plagiarism

The 'Regulations governing fraud and plagiarism for UvA students' applies to this course. This will be monitored carefully. Upon suspicion of fraud or plagiarism the Examinations Board of the programme will be informed. For the 'Regulations governing fraud and plagiarism for UvA students' see: www.student.uva.nl

Course structure

Weeknummer Onderwerpen Studiestof
1  Syntax, relational semantics  Sections 1.1 - 1.3
2  Models and frames, bisimulations  Sections 2.1 - 2.2
3  Filtrations Section 2.3
4 Standard translation, van Benthem's bisimulation characterisation theorem Sections 2.4 & 2.6
5  First-order correspondence Sections3.1-3.2 and 3.5
6 Sahlqvist algorithm Section 3.6
7 Sahlqvist algorithm: Examples Section 3.6
8 Norrmal modal logics, soundness Sections 1.6 & 4.2 
9 Completeness via canonical models I Section 4.2
10 Completeness via canonical models II Section 4.2
11 Finite model property and decidability Section 4.3 and 6.2
12 General frames, incomplete logics Section 4.4
13 Propositional Dynamic Logic PDL: semantics Section 4.8
14 Propositional Dynamic Logic PDL: completeness Section 4.8
15 N/A  
16 N/A   

Timetable

The schedule for this course is published on DataNose.

Honours information

Op dit vak is geen honoursuitbreiding mogelijk.

Additional information

Aanbevolen voorkennis: Kennis van de eerste orde logica (syntax en semantiek), en elementaire wiskundige kennis en vaardigheden.

Recommended prior knowledge: Knowledge of first order logic (syntax and semantics) and elementary mathematical knowledge and skills.

Processed course evaluations

Below you will find the adjustments in the course design in response to the course evaluations.

Contact information

Coordinator

  • N. Bezhanishvili

Instructors: Nick Bezhanishvili  email: N.Bezhanishvili[at]uva.nl

Teaching assistants: Frederik Lauridsen , email: F.M.Lauridsen[at]uva.nl ; Kaibo Xie, email: xiekaibozju[at]gmail.com.

Staff

Staff