PAPER CODE NO. EXAMINER : Louwe Kuijer Tel. No. COMP304/COMP521 DEPARTMENT : Computer Science 2019/2020 Master of Science: Year 1 Bachelor of Science: Year 3 Knowledge Representation and Reasoning TIME ALLOWED : 50 minutes INSTRUCTIONS TO CANDIDATES This is the first class test. You have to answer all questions. This test counts for 13% of your final grade. PAPER CODE COMP304/COMP521 page 1 of 2 Continued 1. (a) Let ϕ be a formula of propositional logic and Γ a set of formulas of propositional logic. Explain what it means for a the inference Γ |= ϕ to be valid. (5 marks) (b) Explain how we can use truth tables to determine whether the inference Γ |= ϕ is valid. (5 marks) (c) Determine whether {p→ (p∧ q)} |= ¬q → ¬p is a valid inference. If it is valid, show that it is valid using either a truth table or a formal proof in P. If it is not valid, show that it is not valid by giving a counterexample. (10 marks) 2. Let the model M = (W,R, V ) be given by W = {w1, w2, w3, w4, w5, w6}, Ra = {(w1, w2), (w3, w4), (w5, w6), (w1, w1)} Rb = {(w1, w3), (w4, w5), (w6, w1), (w6, w6)} V (p) = {w1, w2} (a) Draw the model M . (7 marks) (b) Explain whether M,w5 |= ab¬p (9 marks) (c) Explain whether M,w5 |= ♦a♦b♦b¬p (9 marks) 3. Consider the following model M : w1 w2 w3 w4 (a) Write down the formal definition of this model M (i.e. M = (W,R, V ) with W = · · · , R = · · · , V = · · · ). (6 marks) (b) Explain whether M,w1 |= ♦q. (6 marks) (c) Explain whether M,w1 |= p. (6 marks) (d) Give a formula ϕ that holds onM,w1 but not onM,w2. Explain why ϕ holds onM,w1 but not on M,w2. (7 marks) 4. Determine whether ♦p → (q → ♦(p ∧ q)) is valid. If it is valid, explain why it is valid. If it is not valid, give a counterexample and show that it is a counterexample. (15 marks) 5. The following is an attempted proof in the system K. But it contains three errors. Explain what the errors are, and write down the numbers of the lines where they occur. (15 marks) 1. p→ (q ∨ ¬q) T 2. (p→ (q ∨ ¬q) K 3. (p→ (q ∨ ¬q))→ (p→ (q ∨ ¬q)) K 4. (q ∨ ¬q) MP(2,3) 5. (q ∨ ¬q) Necc(4) 6. (q ∨ ¬q)→ (q ∨¬q) T 7. q ∨¬q MP(5,6) PAPER CODE COMP304/COMP521 page 2 of 2 End
欢迎咨询51作业君