Modal logic assignment

1

PHI134 Assignment # 1

Validity,Derivations,andFrame Definability

Question1: [7marks] Consider the following modal formula:

(α) (�p ∧ q) → �(p ∧ ♦q)

(i) Show that (α) is not valid in the class of all frames.1 1 1 for model. 2 for explanation.

(ii) Show that (α) is valid in the class of all symmetric and transitive frames.2 2 4 for explanation.

Answer to Question 1

(i) 3marksWe need to give a model which (�p ∧ q) → �(p ∧ ♦q) is not true in. Consider the following model:

wq u p

M = 〈W,R,V〉 where: W = {w,u},R = {〈w,u〉},V(p) = {u}, V(q) = {w}

In this model we have M,w �p ∧ q, asw ∈ V(q), and as the only accessible world fromw isu, and M,w pasu ∈ V(p). Moreover, atu ♦q is false, as there are no accessible worlds fromu,

and so no accessibleq-worlds. So we have M,u 6 p ∧ ♦qand so M,w 6 �(p ∧ ♦q), as desired.

(ii) For this case we reason by reductio: showing that if a model

does not validateα then it cannot be symmetric and transi-

tive (in particular symmetric) on pain of contradiction. So

suppose that M = 〈W,R,V〉 is a symmetric and transitive model, and further suppose that for somew ∈ W we have that M,w 6 (�p ∧ q) → �(p ∧ ♦q). �en in particular this means that we have (i) M,w �p ∧ q, and (ii) M,w 6 �(p ∧ ♦q). From (i) it follows that (ia) M,w �pand (ib) M,w q. From (ii) it follows

that there must be some worldu ∈ W such that (iia)Rwuand (iib) M,u 6 p ∧ ♦q. From (ia) and (iia) it follows that M,u p, and so we must have (iic)M,u 6 ♦q. Now from (iia) and the fact thatR is symmetric it follows that (iii)Ruw, and so by (iic) that M,w 6 q. But this contradicts (i)! So if M is symmetric it follows thatαmust

be valid.

2

Question2[6marks] -2 foreachderivation Give derivations demonstrating that

1. K ` ♦(p → q) → (�p → ♦q)3 3 �e DeMorgan laws, and the principle of contraposition (=(p → q) → (¬q → ¬p)) may be helpful here.2. KD ` (♦p → �q) → (♦p → ♦q)

3. KD5 ` (♦�(♦p → �p)) → (�♦p → ♦�p)4 4 You may find it helpful to use the results of the previous questions here.

Answer to Question 3

1. 1) (p → q) → (¬q → ¬p) Taut.

2) ¬(¬q → ¬p) → ¬(p → q) 1, Contraposition

3) �¬(¬q → ¬p) → �¬(p → q) 2, RK

4) ¬�¬(p → q) → ¬�¬(¬q → ¬p) 3, Contraposition

5) ♦(p → q) → ¬�¬(¬q → ¬p) 4, Repl (Dual)

6) ♦(p → q) → ¬�(¬q ∧ ¬¬p) 5, Repl (¬(A → B) ↔ (A ∧ ¬B))

7) ♦(p → q) → ¬(�¬q ∧ �¬p) 6, Repl (�(A ∧ B) ↔ (�A ∧ �B) (�isequivalencewouldneedtobeproved. I’llassumeithereforbrevity, though))

8) ♦(p → q) → (¬�¬q ∨ ¬�¬¬p) 7, PL (A → ¬(B ∧ C) |= A → (¬B ∨ ¬C))

9) ♦(p → q) → (�¬¬p → ¬�¬q) 8, PL (A → (C ∨ ¬B) → A → (B → C))

10) ♦(p → q) → (�p → ♦q) 9, Repl (Dual, ¬¬)

2. 1) �q → ♦q, D

2) (♦p → �q) → (♦p → ♦q) 1, PL (A → B |= (C → A) → (C → B))

3. 1) ♦�(♦p → �p) → �(♦p → �p), Dual of 5[♦p → �p/p]

2) (♦�(♦p → �p) → �(♦p → �p)) → (♦�(♦p → �p) → ♦(♦p → �p)), Question2[(�(♦p → �p))/p,(♦p → �p)/q]

3) ♦�(♦p → �p) → ♦(♦p → �p) 1, 2 MP

4) ♦(♦p → �p) → (�♦p → ♦�p), Question1 [♦p/p,�p/q]

5) (♦�(♦p → �p)) → (�♦p → ♦�p) 3,4 PL (A → B,B → C |= A → C)

Question3[7marks] Consider the following modal formula

(U) : �(�p → p)

What I want you to do in this question is to show that (U) defines the class of

all frames which meet the following condition.

(shift − reflexivity) ∀w∀x(Rwx → Rxx)

To do this I want you to prove the following:

3

(i) Show that if a model M is a model on a frame which is shift-reflexive,

then we have M |= �(�p → p).5 5 3 marks

(ii) Show that if we have a frame F which is not shift-reflexive, then we

can define a model M on that frame and a pointw in that model where

M,w 6 �(�p → p).6 6 4 marks

Answer to Question 3

(i) Suppose that M = 〈W,R,V〉 is a model on a frame which is shift-reflexive, and suppose for a contradiction that we have

M 6|= �(�p → p). �en we must have some worldw ∈ W such that

M,w 6 �(�p → p)

So there must be some worldusuch thatRwuand

M,u 6 �p → p

So by our truth conditions for → this means that

(i)M,u �p and (ii)M,u 6 p

But asR is shift-reflexive it follows from that fact thatRwu that

Ruu. So by (i) it follows that M,u p, which contradicts (ii). So U is true in any model on a frame which is shift reflexive.

Suppose that F = 〈W,R〉 is a frame which is not shift-reflexive. �at is to say we have pointsw,u ∈ W for whichRwuwhile notRuu. We want to give a model M = 〈W,R,V〉 on F for which we have M,w 6 �(�p → p) (from which it follows that U is not valid on F). Suppose that we defineV(p) as follows:

V(p) = {x ∈ W : Rux}

i.e. we makep true at all those worlds which are accessible fromu.

�is will mean the following:

1. M,u �p: as every world which is accessible fromu is a world

which, by our definition ofV(p) is a world wherep is true.

2. M,u 6 p: as in order to havep true atuwe would have to have Ruu, which as was stipulated above is not the case.

From the above two facts we can conclude that M,u 6 �p → p, and so as we haveRwu, we can conclude that M,w 6 �(�p → p), as desired.