COS3761 Assignment 3 (DETAILED ANSWERS) 2025 - DISTINCTION GUARANTEED

COS3761 Assignment 3 (DETAILED ANSWERS) 2025 - DISTINCTION GUARANTEED - DISTINCTION GUARANTEED - DISTINCTION GUARANTEED Answers, guidelines, workings and references ,... QUESTION 1 In which world of the Kripke model in Figure 1 is the formula ◊ p  □ q true? Option 1: world x₁ Option 2: world x₂ Option 3: world x₃, Option 4: Option 1 and Option 3 are true. UESTION 2 Which of the following does not hold in the Kripke model in Figure 1? Option 1: x₁ ╟ ◊ ◊ p .Option 2: x₂ ╟ □ p .Option 3: x₃ ╟ □ p  □ q .Option 4: x₄ ╟ □□ p QUESTION 3 Which of the following holds in the Kripke model given in Figure 1? Option 1: x₁ ╟ □ p .Option 2: x₂ ╟ ◊ ( p  q) .Option 3: x₃ ╟ ◊ p  □ ¬ q q p, q q p q x₁ x₄ x₃ q Downloaded by Vusi Xhumalo () lOMoARcPSD| COS3761/103/2025 20 Option 4: x₄ ╟ □ (p  q) . QUESTION 4 Which of the following formulas is true in the Kripke model given in Figure 1? Option 1: ◊ p Option 2: □ q Option 3: □ ◊ q Option 4: □ p QUESTION 5 Which of the following formulas is false in the Kripke model given in Figure 1? Option 1: p  q Option 2: □ ◊ p Option 3: □ (p  q) Option 4: p  ◊ q QUESTION 6 If we interpret □  as "It ought to be that  ", which of the following formulas correctly expresses the English sentence It ought to be the case that if it rains outside then it is permitted to take leave from work. : p stands for the declarative sentence "It rains outside" and q stands for "take leave from work"? Option 1: □ (p ¬ □ ¬ q) Option 2: □( p ¬ ◊ q) Option 3: □ p  ◊ ¬ q Option 4: □ p  □ q .QUESTION 7 Downloaded by Vusi Xhumalo () lOMoARcPSD| COS3761/103/2025 21 If we interpret □  as "It is necessarily true that  ", why should the formula scheme □   □ □  hold in this modality? Option 1: Because for all formulas , it is necessarily true that if  then . Option 2:Because for all formulas , if  is necessarily true, then it is necessary that it is necessarily true. Option 3:Because for all formulas , if  is not possibly true, then it is true. Option 4: Because for all formulas ,  is necessarily true if it is true. QUESTION 8 If we interpret □  as "the agent knows  ", why should the formula scheme □   □ □  hold in this modality? Option 1: If the agent knows something he knows that he knows it. Option 2: the agent knows something it doesn’t mean that he knows. Option 3: If the agent does not know something, he again knows that he knows it. Option 4: If the agent knows something, he knows that he does not know it. QUESTION 9 If we interpret □  as "it is necessarily true", which of the following formulas is not valid? Option 1: □ p  p Option 2: □ p  □¬ p Option 3: □ p  ◊ p Option 4: ◊ p  □ ◊ p Downloaded by Vusi Xhumalo () lOMoARcPSD| COS3761/103/2025 22 QUESTION 10 If we interpret □  as "agent A believes  ", what is the modal translation of the English sentence If agent A believes p then he believes that agent A does not believe q. Option 1: □ p □ q Option 2: □ p  ¬□ q Option 3: □ p  ¬□¬ q Option 4: □ p  □¬ q QUESTION 11 If we interpret □  as "Agent A believes  ", English translation of the formula □ p  □ ¬ q ? Option 1: If Agent A believes  then Agent A believes not . Option 2 : If Agent A believes  then Agent A does not believe . Option 3: If Agent A believes  then Agent A believes . Option 4: If Agent A believes  then Agent A does not believe not . QUESTION 12 If we interpret Kᵢ as “agent 1 knows ”, the formula scheme ¬  K₁ ¬ K₁  means Option 1: If  is true then agent 1 knows that he does not know  Option 2: If  is false then agent 1 knows that he does not know  Option 3: If  is true then agent 1 knows that he knows  Option 4: If  is false then agent 1 knows that he knows  The following natural deduction proof (without reasons) is referred to in Questions 13, 14 and 15: 1 ¬ □ ¬ (p  q) Downloaded by Vusi Xhumalo () lOMoARcPSD| COS3761/103/2025 23 2 □ p 3 □ ¬ q 4 p  q assumption 5 p □ e 2 6 q  e 4, 5 7 ¬ q □ e 3 8  ¬ e 6, 7 9 ¬ (p  q) ¬ i 4 - 8 10 □ ¬ (p  q) □ i 4 - 9 11  ¬ e 10, 1 12 ¬ □ ¬ q ¬ i 3 - 11 13 □ p  ¬ □ ¬ q  i 2 – 12 QUESTION 13 How many times are □ elimination and introduction rules used in the above proof? Option 1: None Option 2: □ elimination and □ introduction once are both used only once. Option 3: □ elimination is used only once but □ introduction twice. Option 4: □ elimination is used twice but □ introduction only once. QUESTION 14 What are the correct reasons for steps 1, 2 and 3 of the above proof? Option 1: 1 premise 2 assumption 3 assumption Downloaded by Vusi Xhumalo () lOMoARcPSD| COS3761/103/2025 24 Option 2: 1 premise 2 ¬e 1 3 ¬i 2 Option 3: 1 assumption 2 ¬e 1 3 □e 4 Option 4: 1 assumption 2 □i 2 3 assumption QUESTION 15 What sequent is proved by the above proof? Option 1: □ p  ◊ p Option 2: □ p  ¬ □ ¬ q Option 3: ¬ □ ¬ q Option 4: No proof The following incomplete natural deduction proof is referred to in Questions 16 and 17: 1 2 3 4 5 6 7 8 □ (p  q) →□ p □ q □ (p  q) assumption □p □ i3 □q □ i4 □p  □ q p  q p  e2 q e2 Downloaded by Vusi Xhumalo () lOMoARcPSD| COS3761/103/2025 25 QUESTION 16 What formulas and their reasons are missing in steps 2 and 7 of the above proof? Option 1: 2 p  q □ e1 7 □p□ q  I 5,6 Option 2: 2 p  q assumption 7 □p□ q →i 5,6 Option 3: 2 p  q □ e1 7 □p□ q  i 2 Option 4: 2 p  q assumption 7 □p  □ q  i 5,6 QUESTION 17 What rule is used in line 8? Option 1:  e Option 2: ¬e Option 3:  i Option 4:  i QUESTION 18 What proof strategy would you use to prove the following sequent: □ (p  q) KT4 □ □ p  □ □ q Option 1: Open a solid box and start with □ (p  q) as an assumption Use axiom T to remove the □ to get p  q. Use  elimination twice to obtain the separate atomic formulas. Use axiom 4 twice, i.e. once on each atomic formula, to add a □ to each. Use axiom 4 twice, i.e. once on □ p and once on □ q, to get □ □ p and □ □ q. Combine □ □ p and □ □ q using  introduction. Close the solid box to get the result. Downloaded by Vusi Xhumalo () lOMoARcPSD| COS3761/103/2025 26 Option 2: Start with □ (p  q) as a premise. Use axiom T to remove the □ to get p  q. Open a dashed box and use  elimination twice to obtain the separate atomic formulas. Use axiom 4 twice, i.e. once on each atomic formula, to add a □ to each. Close the dashed box and use □ introduction twice, i.e. once on □ p and once on □ q, to get □ □ p and □ □ q. Combine □ □ p and □ □ q using  introduction. Option 3: Start with □ (p  q) as a premise. Open a dashed box and use □ elimination to get p  q. Use  elimination twice to obtain the separate atomic formulas. Close the dashed box and use □ introduction twice, i.e. once on each atomic formula. Use axiom 4 twice, once on □ p and once on □ q, to get □ □ p and □ □ q. Combine □ □ p and □ □ q using  introduction. Option 4: Open a solid box and start with □ (p  q) as an assumption. Open a dashed box and use □ elimination to get p  q. Use  elimination twice to obtain the separate atomic formulas. Use axiom 4 twice, i.e. once on each atomic formula, to add a □ to each. Close the dashed box and use □ introduction twice, i.e. once on □ p and once on □ q, to get □ □ p and □ □ q. Close the solid box to get the result. QUESTION 19 If we interpret Ki  as "Agent i knows  ", what is the English translation of the formula ¬K1 K2 (p  q) Option 1: Agent 1 knows that agent 2 doesn't know that p and q. Option 2: Agent 1 doesn't know that agent 2 knows p and q. Option 3: If agent 1 knows that agent 2 doesn't know p and q. Option 4: If agent 1 doesn't know that agent 2 knows p and q. QUESTION 20 If we interpret Ki  as "Agent i knows  ", what formula of modal logic is correctly translated to English as Downloaded by Vusi Xhumalo () lOMoARcPSD| COS3761/103/2025 27 If agent 1 knows p then agent 2 doesn't know q. Option 1: K1 p  K2 ¬ q Option 2: ¬ (K1 p  K2 q) Option 3: K1 (p  ¬ K2 q) Option 4: K1 ¬ K2 (p  q)