Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

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.
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)