INTRODUCTION TO MODAL LOGIC 2014 HOMEWORK 5 • • • • Deadline: November 11 — at the beginning of class. Electronic submissions can be sent to Giovanni Cina [email protected] Grading is from 0 to 10 points. Success! (1) (2pt) Use the Sahlqvist algorithm to compute the first-order correspondent of the formula: (♦p ∧ ♦q) → (♦(p ∧ ♦q) ∨ ♦(p ∧ q) ∨ ♦(q ∧ ♦p)). (2) (2pt) Prove (a) `K ϕ → (ψ → ϕ) (b) `K (♦ϕ ∧ (ϕ → ψ)) → ♦ψ You may find it helpful to note that the following are propositional tautologies: • • • • • ϕ → (ψ → ϕ) ϕ → (ϕ ∨ ψ) (ϕ → ψ) → (¬ψ → ¬ϕ) (ϕ → (ψ → χ)) ↔ ((ϕ ∧ ψ) → χ) ϕ → (ψ → (ϕ ∧ ψ)) You can also use Proposition 10 from the notes. (3) (2pt) Recall that S5 = K + (p → p) + (p → p) + (p → ♦p). Show that `S5 ♦p → ♦p You can use Proposition 10 from the notes. (4) (2pt) (a) Show that if a frame F is a bounded morphic image of a frame G, then Log(G) ⊆ Log(F). (b) Let C be a non-empty class of frames. Prove that Log(C) is contained in the logic of a single reflexive point or Log(C) is contained in the logic of a single irreflexive point. (c) Let Call be the class of all frames. Prove that for each frame class C its logic Log(C) contains Log(Call ). 1 2 INTRODUCTION TO MODAL LOGIC 2014 HOMEWORK 5 (5) (2pt) Show that S5 is sound with respect to the class of frames (W, R), where R is an equivalence relation. (6) (2pt) (BONUS!) The exercise is only for readers who like syntactical manipulations (and have a lot of time to spare, this is Exercise 1.6.5 from Blackburn et al.). GL = K + ((p → p) → p). Prove that `GL p → p. We already discussed in class how to do this semantically.
© Copyright 2019