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 4 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 4 Continued
Solution:
1. (a) An inference Γ |= ϕ is valid if whenever every premise γ ∈ Γ is true, the conclusion ϕ
is also true.
(b) Make a combined truth table for every formula γ ∈ Γ and the formula ϕ. Check every
row of the truth table where all formula γ ∈ Γ are assigned truth value 1. If ϕ is also
assigned truth value 1 in every such row then the inference is valid, otherwise it is
invalid.
(c)
p q p → (p ∧ q) ¬ q → ¬ p
0 0 0 1 0 0 0 1 0 1 1 0
0 1 0 1 0 0 1 0 1 1 1 0
1 0 1 0 1 0 0 1 0 0 0 1
1 1 1 1 1 1 1 0 1 1 0 1
In every row where the premise is assigned truth value 1 (that is, in rows 1, 2 and 4),
the conclusion is also assigned truth value 1. The inference is therefore valid.
2. (a)
w1
p
w2p
w3
w4
w5
w6
a
a
a
a
b
bb
b
(b) We have M,w1 |= p, and therefore M,w1 6|= ¬p. As w1 is a b-successor of w6, it
follows that M,w6 6|= b¬p. Because w6 is an a-successor of w5, this implies that
M,w5 6|= ab¬p.
(c) We have M,w6 6|= p, and therefore M,w6 |= ¬p. As w6 is a b-successor of w6, it
follows that M,w6 |= ♦b¬p. Once again using the fact that w6 is a b-successor of
itself, this implies that M,w6 |= ♦b♦b¬p. Finally, because w6 is an a-successor of w5
this implies that M,w5 |= ♦a♦b♦b¬p.
3. (a) M = (W,R, V ), withW = {w1, w2, w3, w4},R = {(w1, w2), (w1, w3), (w1, w4), (w2, w1),
(w2, w2), (w2, w3), (w4, w3)}.
(b) The world w3 has no successors, so M,w3 |= q. Since w3 is a successor of w1 it
follows that M,w1 |= ♦q.
(c) We have M,w2 6|= p. Since w2 is a successor of itself, this implies M,w2 6|= p. That
in turn implies that M,w2 6|= p, as w2 is still a successor of itself. Finally, w2 is a
successor of w1, so M,w1 6|= p.
(d) Take ϕ = ♦(♦¬p ∧p).
None of the worlds satisfy p and w3 is the only world without successors, so w3 is the
only world where p holds. The worlds w1 and w2 both have a successor that is not
w3, so at least one of their successors does not satisfy p. So w1 and w2 don’t satisfy
p. Meanwhile, w3 does not have any successors, so M,w3 6|= ♦¬p. It follows that
M,w1 6|= ♦¬p ∧p, M,w2 6|= ♦¬p ∧p and M,w3 6|= ♦¬p ∧p.
PAPER CODE COMP304/COMP521 page 3 of 4 Continued
The world w4, however, has at least one successor (namely w3) where ¬p is true, so
M,w4 |= ♦¬p. Furthermore, w3 is the only successor of w4 and w3 satisfies p, so
M,w4 |= p. So w4 satisfies ♦¬p ∧p, while none of the other worlds do.
Now, w1 has w4 as a successor, so M,w1 |= ♦(♦¬p ∧p). But w2 does not have w4
as a successor, which implies that M,w2 6|= ♦(♦¬p ∧ p), as w4 is the only world
where ♦¬p ∧p is true. We have now shown that ϕ holds in w1 but not in w2.
The world w4 then is the only world that (i) has a successor (where ¬p holds) and (ii)
only has successors where p holds
4. Take any pointed model M,w such that M,w |= ♦p. We distinguish two cases.
First, suppose that M,w 6|= q. Then M,w |= q → ♦(p ∧ q).
Secondly, suppose that M,w |= q. Because M,w |= ♦p there must be some successor
w′ of w such that M,w′ |= p. Furthermore, as M,w |= q and w′ is a successor of w, we
have M,w′ |= q. It follows that M,w′ |= p ∧ q and, because w′ is a successor of w, that
M,w |= ♦(p ∧ q) and therefore M,w |= q → ♦(p ∧ q).
We have now shown that for every pointed model such that M,w |= ♦p we have M,w |=
q → ♦(p ∧ q), so |= ♦p→ (q → ♦(p ∧ q)).
5. The errors are on lines 2, 4 and 6.
The formula on line 2 is not of the form(ϕ→ ψ)→ (ϕ→ ψ), so it is not an instance
of axiom K.
Using the MP rule on lines 2 and 3 yields p → (q ∨ ¬q), as opposed to the formula
(q ∨ ¬q) that is written on line 4. So line 4 is not justified by MP(2,3).
The formula on line 6 is not a substitution instance of a formula of propositional logic, so
line 6 is not justified by the axiom T.
PAPER CODE COMP304/COMP521 page 4 of 4 End

欢迎咨询51作业君