PAPER CODE NO. EXAMINER : Louwe Kuijer Tel. No.
COMP304 DEPARTMENT : Computer Science
First Semester Examinations 2018/19 – Model Solution
Bachelor of Science: Year 3
Knowledge Representation and Reasoning
TIME ALLOWED : Two and a Half Hours
INSTRUCTIONS TO CANDIDATES
This is model solution for the exam, which counts for 75% of the final grade.
Students are expected to answer four questions.
PAPER CODE COMP304 page 1 of 11 Continued
1. (Propositional Logic and Single Agent Modal Logic) (Total: 25 marks)
(a) Use a truth table to show whether |= (p ∨ q)→ ((p ∧ r) ∨ (q ∧ ¬r)). Clearly indicate
how your answer follows from the truth table. (6 marks)
(b) Determine whether (♦p ∧♦q) → ♦♦q is valid. If it is valid, explain why it is valid.
If it is not valid, provide a counterexample and show that it is a counterexample.
(6 marks)
(c) Let M = (W,R, V ) be given by W = {w1, w2, w3}, R = {(w1, w2), (w2, w1),
(w2, w3), (w3, w2), (w1, w3)}, V (p) = w2, V (q) = w3. Draw this model. (5 marks)
(d) For the model described in (c), explain whether M,w3 |= ♦(p ∨ q). (6 marks)
(e) Consider the formula ♦p∨¬p of modal logic. Is it a substitution instance of a formula
of propositional logic? You do not need to explain your answer. (2 marks)
Solution.
(a)
p q r (p ∨ q) → ((p ∧ r) ∨ (q ∧ ¬ r))
0 0 0 0 0 0 1 0 0 0 0 0 0 1 0
0 0 1 0 0 0 1 0 0 1 0 0 0 0 1
0 1 0 0 1 1 1 0 0 0 1 1 1 1 0
0 1 1 0 1 1 0 0 0 1 0 1 0 0 1
1 0 0 1 1 0 0 1 0 0 0 0 0 1 0
1 0 1 1 1 0 1 1 1 1 1 0 0 0 1
1 1 0 1 1 1 1 1 0 0 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1 1 1 0 0 1
On the fourth and fifth rows, the formula is assigned truth value 0. So the formula is
not valid. In other words, 6|= (p ∨ q)→ ((p ∧ r) ∨ (q ∧ ¬r)).
(b) The formula is valid.
Take any pointed model M,w such that M,w |= ♦p ∧ ♦q. Then M,w |= ♦p, so w
has at least one successor w2. Furthermore, M,w |= ♦q, so M,w2 |= ♦q. Since w2
is a successor of w, it follows that M,w |= ♦♦q.
We have shown that M,w |= ♦p ∧ ♦q implies M,w |= ♦♦q. So M,w |= (♦p ∧
♦q) → ♦♦q. Since this is true for every pointed model M,w, we have |= (♦p ∧
♦q)→ ♦♦q.
(c)
w1 w2
p
w3 q
PAPER CODE COMP304 page 2 of 11 Continued
(d) We have w3 ∈ V (q) and w2 ∈ V (p), so M,w3 |= q and M,w2 |= p. This implies that
M,w2 |= p∨ q and M,w3 |= p∨ q. Since w2 is the only successor of w3, we then have
M,w3 |= (p ∨ q). Likewise, since w2 and w3 are the only successors of w1, we have
M,w1 |= (p ∨ q).
Then, because w1 and w3 are the only successors of w2, we have M,w2 |= (p ∨ q).
Finally, because w2 is a successor of w3, we have M,w3 |= ♦(p ∨ q).
(e) Yes.
PAPER CODE COMP304 page 3 of 11 Continued
2. (Multi Agent Modal Logic) (Total: 25 marks)
Consider the following drawing of a model M
w3q
w1
q
w4p
w2
p
b
a
b
a a, b
a
(a) Give the formal description of this model M , i.e. M = (W,R, V ), where W = · · · ,
Ra = · · · , Rb = · · · and V = · · · . (5 marks)
(b) Explain whether M,w4 |= ap ∧bp. (5 marks)
(c) Explain whether M,w1 |= a(p→ b♦bp). (5 marks)
(d) Give a formula that holds on w1 and w4 but not on w2 and w3. (You do not need to
explain your formula.) (3 marks)
(e) Determine whether the formula (ab¬p ∧ ab¬q) ∨ ♦a♦b(p ∨ q) is valid. If it is
valid, explain why it is valid. If it is not valid, provide a counterexample and show that
it is a counterexample. (7 marks)
Solution.
(a)
• W = {w1, w2, w3, w4},
• Ra = {(w1, w1), (w1, w2), (w2, w1), (w2, w2), (w3, w3)},
• Rb = {(w1, w3), (w3, w1), (w4, w2), (w2, w2)},
• V (p) = {w2, w4} and
• V (q) = {w1, w3}
(b) We have w2 ∈ V (p), so M,w2 |= p. Since w2 is the only b-successor of w4, we
have M,w4 |= bp. Furthermore, w4 has no a-successors, so every a-successor of w4
satisfies p, and therefore M,w4 |= ap. It follows that M,w4 |= ap ∧bp.
(c) We have w2 ∈ V (p), so M,w2 |= p. Since w2 is a b-successor of itself, this implies
that M,w2 |= ♦bp. Because w2 is also the only b-successor of itself, we then get
M,w2 |= b♦bp. This implies that M,w2 |= p→ b♦bp.
We also have w1 6∈ V (p), so M,w1 6|= p and therefore M,w1 |= p→ b♦bp.
Because w1 and w2 are the only a-successors of w1, we get M,w1 |= a(p→ b♦bp).
(d) ap ∨baq.
(e) The formula is valid. Take any pointed model M,w. Suppose that the second disjunct
is not satisfied in M,w, so M,w 6|= ♦a♦b(p ∨ q). Then for every a-successor w1 of w,
we have M,w1 6|= ♦b(p ∨ q). That means that for every b-successor w2 of w1, we have
M,w2 6|= p ∨ q. As a result, M,w2 |= ¬p and M,w2 |= ¬q.
PAPER CODE COMP304 page 4 of 11 Continued
Since this is true for every b-successor w2 of w1, we have M,w1 |= b¬p and M,w1 |=
b¬q. That, in turn, is true for every a-successor w1 of w, so M,w |= ab¬p and
M,w |= ab¬q. So M,w |= ab¬p ∧ab¬q.
We have shown that whenever the second disjunct is not satisfied, then the first disjunct
is satisfied. So M,w |= (ab¬p ∧ ab¬q) ∨ ♦a♦b(p ∨ q). Since this is true for
every pointed model M,w, we have |= (ab¬p ∧ab¬q) ∨ ♦a♦b(p ∨ q).
PAPER CODE COMP304 page 5 of 11 Continued
3. (Description Logic) (Total: 25 marks)
Consider the ABox A given by
• o1 : A
• o2 : E
• o1 : ¬∀R.¬C
• (o1, o2) : R
and the TBox T given by
• A v B u ∀R.D
• B ≡ ∃R.¬E
• E v C
and let K = (A, T ).
Use the tableaux-based 6-step method to show whether K is consistent. That is,
(a) Eliminate v from the TBox, (3 marks)
(b) Expand the TBox, (3 marks)
(c) Eliminate defined concepts from the ABox, (3 marks)
(d) Put the ABox in negation normal form, (3 marks)
(e) Apply the completion rules to the ABox and (10 marks)
(f) Check the leaves of the tree that you made in (e) for contradictions, and explain whether
K is consistent. (3 marks)
Solution.
(a) The new TBox is given by
• A ≡ B u ∀R.D u A∗
• B ≡ ∃R.¬E
• E ≡ C u E∗
(b) The new TBox is given by
• A ≡ ∃R.¬(C u E∗) u ∀R.D u A∗
• B ≡ ∃R.¬(C u E∗)
• E ≡ C u E∗
(c) The new ABox is given by
• o1 : ∃R.¬(C u E∗) u ∀R.D u A∗
• o2 : C u E∗
• o1 : ¬∀R.¬C
• (o1, o2) : R
(d) The new ABox is given by
• o1 : ∃R.(¬C unionsq ¬E∗) u ∀R.D u A∗
• o2 : C u E∗
PAPER CODE COMP304 page 6 of 11 Continued
• o1 : ∃R.C
• (o1, o2) : R
(e)
o1 : ∃R.(¬C unionsq ¬E∗) u ∀R.D u A∗
o2 : C u E∗
o1 : ∃R.C
(o1, o2) : R
o1 : ∃R.(¬C unionsq ¬E∗) u ∀R.D u A∗ o1 : ∃R(¬C unionsq ¬E∗)
o2 : C u E∗ o1 : ∀R.D
o1 : ∃R.C o1 : A∗
(o1, o2) : R
o1 : ∃R.(¬C unionsq ¬E∗) u ∀R.D u A∗ o1 : ∃R(¬C unionsq ¬E∗)
o2 : C u E∗ o1 : ∀R.D
o1 : ∃R.C o1 : A∗
(o1, o2) : R o2 : C
o2 : E
∗
o1 : ∃R.(¬C unionsq ¬E∗) u ∀R.D u A∗ o1 : ∃R(¬C unionsq ¬E∗)
o2 : C u E∗ o1 : ∀R.D
o1 : ∃R.C o1 : A∗
(o1, o2) : R o2 : C
o2 : E
∗ o2 : D
o1 : ∃R.(¬C unionsq ¬E∗) u ∀R.D u A∗ o1 : ∃R(¬C unionsq ¬E∗)
o2 : C u E∗ o1 : ∀R.D
o1 : ∃R.C o1 : A∗
(o1, o2) : R o2 : C
o2 : E
∗ o2 : D
(o1, x) : R x : ¬C unionsq ¬E∗
o1 : ∃R.(¬C unionsq ¬E∗) u ∀R.D u A∗ o1 : ∃R(¬C unionsq ¬E∗)
o2 : C u E∗ o1 : ∀R.D
o1 : ∃R.C o1 : A∗
(o1, o2) : R o2 : C
o2 : E
∗ o2 : D
(o1, x) : R x : ¬C unionsq ¬E∗
x : D
o1 : ∃R.(¬C unionsq ¬E∗) u ∀R.D u A∗ o1 : ∃R(¬C unionsq ¬E∗)
o2 : C u E∗ o1 : ∀R.D
o1 : ∃R.C o1 : A∗
(o1, o2) : R o2 : C
o2 : E
∗ o2 : D
(o1, x) : R x : ¬C unionsq ¬E∗
x : D x : ¬C
o1 : ∃R.(¬C unionsq ¬E∗) u ∀R.D u A∗ o1 : ∃R(¬C unionsq ¬E∗)
o2 : C u E∗ o1 : ∀R.D
o1 : ∃R.C o1 : A∗
(o1, o2) : R o2 : C
o2 : E
∗ o2 : D
(o1, x) : R x : ¬C unionsq ¬E∗
x : D x : ¬E∗
u
u
∀
∃
∀
u
(f) Neither of the leaves contain a contradiction, so in particular there is at least one con-
sistent leaf. The knowledge base K is therefore consistent.
PAPER CODE COMP304 page 7 of 11 Continued
4. (Epistemic Logic) (Total: 25 marks)
In epistemic logic, we only consider those models that are reflexive, transitive and eu-
clidean.
(a) Which axiom of S5 corresponds to the fact that we only use Euclidean models? (3 marks)
(Note: S5 has axioms for all agents. It suffices for you to give the axiom for agent a.)
(b) What property of knowledge is represented by the fact that we only use Euclidean
models? (3 marks)
Now, consider the following situation: agents a and b are both given a natural number
between 0 and 4. Furthermore, they are told that their numbers are exactly 1 apart. These
things are common knowledge among the agents.
Let us use 0a, 1a, 2a, 3a and 4a to represent a having number 0, 1, 2, 3 and 4, respectively,
and 0b, 1b, 2b, 3b, 4b for agent b having those numbers.
(c) Draw a model M that represents the situation described above. Give the name w23 to
the world where a has 2 and b has 3. (6 marks)
(d) Explain whether M,w23 |= Ka3b. (3 marks)
Suppose now that agent b says to agent a: “I know that you do not have number 0”.
(e) This event can be seen as a public announcement. What is the formula ϕb that is being
announced? (3 marks)
(f) The announcement ϕb changes the situation. Draw the model M ∗ ϕb that represents
the new situation. (4 marks)
(g) Explain whether M ∗ ϕb, w23 |= Ka3b. (3 marks)
Solution.
(a) ¬Kaϕ→ Ka¬Kaϕ.
(b) Negative introspection (i.e., if you don’t know something then you know that you don’t
know it).
(c)
PAPER CODE COMP304 page 8 of 11 Continued
w01
0a, 1b
w21
2a, 1b
w23
2a, 3b
w43
4a, 3b
w10
1a, 0b
w12
1a, 2b
w32
3a, 2b
w34
3a, 4b
b
a
b
a
b
a
(d) The world w21 is an a-successor of w23, and M,w21 6|= 3b. So M,w23 6|= Ka3b.
(e) ϕb = Kb¬0a
(f)
w23
2a, 3b
w43
4a, 3b
w10
1a, 0b
w12
1a, 2b
w32
3a, 2b
w34
3a, 4b
b
a
b
a
(g) In the updated model, the only a-successor of w23 is w23 itself. Since M ∗ϕb, w23 |= 3b,
it follows that M ∗ ϕb, w23 |= Ka3b.
PAPER CODE COMP304 page 9 of 11 Continued
5. (Translations and the Proof System K) (Total: 25 marks)
(a) Translate the following concepts from English to the language ALC of description
logic: (6 marks)
• A person whose every child is a dog.
• A bone that is located in the leg and that is not connected to the femur.
• An object that is neither a person nor has a child that is a person.
(b) Translate the following concepts from ALC to English. (6 marks)
• person u ∃hasChild.∃hasChild.>
• professor u ∀hasPet(dog unionsq cat)
• ∀hasPet.⊥
(c) Translate the following statements from English to modal logic, using the relevant
meaning of and ♦. (5 marks)
Alethic “ϕ is necessarily true.”
Temporal “at some point in the future, ϕ will be true.”
Epistemic “the agent knows that ϕ is true.”
Deontic “ϕ should be true.”
Legal “ϕ is legally allowed to be true.”
(d) Below you will find one correct proof in K and one incorrect proof. Write down which
proof is correct, and all line numbers of the lines where the incorrect proof contains
errors. (8 marks)
Proof 1:
1. p→ (q → (p ∧ q)) T
2. (p→ (q → (p ∧ q)) Necc(1)
3. (p→ (q → (p ∧ q))→ (p→ (q → (p ∧ q))) K
4. p→ (q → (p ∧ q)) MP(2,3)
5. (p→ (p ∧ q))→ (p→ (p ∧ q)) K
6. (4)→ ((5)→ (p→ (q → (p ∧ q)))) T
7. (5)→ (p→ (q → (p ∧ q))) MP(6,4)
8. p→ (q → (p ∧ q)) MP(7,5)
Proof 2:
1. (p→ (q ∨ p))→ (p→ (q ∨ p)) T
2. p→ (q ∨ p) T
3. p→ (q ∨ p) MP(1,2)
4. (p→ (q ∨ p))→ (♦(q ∨ p)→ ♦p) T
5. ♦(q ∨ p)→ ♦p MP(3,4)
Solution.
(a) • person u ∀hasChild.dog
• bone u ∃locatedIn.leg u ¬∃connectedTo.femur
• ¬person u ¬∃hasChild.person
PAPER CODE COMP304 page 10 of 11 Continued
(b) • A person who has at least one child that itself has a child.
• A professor who only has pets that are cats or dogs.
• An object that does not have a pet.
(c) Alethic ϕ
Temporal ♦ϕ
Epistemic ϕ
Deontic ϕ
Legal ♦ϕ
(d) Proof 1 is correct. Proof 2 contains errors in lines 1, 3 and 4.
PAPER CODE COMP304 page 11 of 11 End

欢迎咨询51作业君