COMP5450M01
This question paper consists
of 5 printed pages, each
of which is identified by the
Code Number COMP5450M.
A non-programmable calculator may be used.
Answer All Questions.
This is an open book examination.
Any written or printed material is permitted.
c© UNIVERSITY OF LEEDS
School of Computing
January 2019
COMP5450M
KNOWLEDGE REPRESENTATION AND REASONING (MSc)
Time allowed: 2 hours
PLEASE DO NOT REMOVE THIS PAPER FROM THE EXAM ROOM
Answer ALL THREE questions
The marks available for each part of each question are clearly indicated.
Page 1 of 5 TURN OVER FOR QUESTIONS
COMP5450M01
Question 1
(a) Translate the following sentence into Propositional Logic:
• I go shopping on Mondays and Tuesdays. [2 marks]
(b) Translate the following sentences into First-Order Predicate Logic (using equality where
necessary):
(i) Some yellow frogs are poisonous. [2 marks]
(ii) All Helen’s rabbits are white or grey. [2 marks]
(iii) No dog ate more than one biscuit. [2 marks]
(iv) Edward hates everyone except himself. [2 marks]
(c) M = 〈D, δ〉 is a model for a first-order language with two unary predicates P and Q
and a binary relation predicate R. The domain ofM is the set {a, b, c, d, e, f}, and the
denotation of the predicates is:
• δ(P ) = {a, b, c}
• δ(Q) = {d, e, f}
• δ(R) = {〈a, f〉, 〈b, e〉, 〈c, d〉, 〈f, f〉}
Which of the following formulae are satisfied by this model? [4 marks]
F1. ∀x[P (x) ∨ Q(x)]
F2. ∃w[P (w) ∧ Q(w)]
F3. ∀x[P (x)→ ∃y[R(x, y) ∧ Q(y)]]
F4. ¬∃x∃y[Q(x) ∧ Q(y) ∧ R(x, y)]
Page 2 of 5 TURN OVER FOR QUESTIONS
COMP5450M01
(d) Use the Sequent Calculus to show that the following sequent is valid: [6 marks]
∀x[P (x)], ∀x[P (x)→ Q(x)] ` ∀x[Q(x)]
You should only use rules from the following rule set, which was presented in the lecture
slides, to construct your proof:
Axiom
α, Γ ` α, ∆
α, β, Γ ` ∆
[∧` ]
(α ∧ β), Γ ` ∆
Γ ` α, ∆ and Γ `β,∆
[`∧]
Γ ` (α ∧ β), ∆
α,Γ ` ∆ and β,Γ ` ∆
[∨ ]`
(α ∨ β), Γ ` ∆
Γ ` α, β, ∆
[ ` ∨ ]
Γ ` (α ∨ β), ∆
Γ ` α, ∆
[¬` ]¬α, Γ ` ∆
Γ, α ` ∆
[ ` ¬]
Γ ` ¬α, ∆
Γ, ¬α ∨ β ` α, ∆
[→ ` r.w.]
Γ, α → β ` ∆
Γ ` ¬α ∨ β, ∆
[ ` → r.w.]
Γ ` α → β, ∆
∀x[Φ(x)], Φ(k), Γ ` ∆
[∀` ]∀x[Φ(x)], Γ ` ∆
Γ ` Φ(k),∆
[ ` ∀]
Γ ` ∀x[Φ(x)], ∆
†
† where κ cannot occur any-
where in the lower sequent.
[Question 1 total: 20 marks]
Page 3 of 5 TURN OVER
COMP5450M01
Question 2
(a) (i) Give the set of clausal formulae (i.e. formulae in disjunctive normal form)1 corre-
sponding to the following propositional formulae: [4 marks]
¬¬A ∨ S, (¬S ∧ T ), (A ∨ B)→ Q, (Q ∧ T )→ (R ∧ S)
(ii) Give a proof that these formulae are inconsistent using binary propositional reso-
lution. [4 marks]
(b) Translate the following sentence into Propositional Tense Logic: [2 marks]
If I win the lottery I will be rich forever after that.
(c) A Situation Calculus theory makes use of fluents of the forms:
robot has(item) on floor(item, room) locked(door)
robot location(room) connects(door, room1, room2)
The theory includes constants referring to items, one of which is key.
The theory also describes the behaviour of a robot in terms of the following actions:
pick up(object) unlock(door) move to(room)
An initial situation, s0, is described as follows:
Holds(connects(door1, hall, lounge), s0) Holds(connects(door2, hall, study), s0)
¬Holds(locked(door1), s0) Holds(locked(door2), s0)
Holds(on floor(key, lounge), s0) Holds(robot location(hall), s0)
(i) Assuming that the initial situation is so, give a sequence of actions that will result
in the goal robot location(study) being satisfied. [2 marks]
(ii) For each of the actions pick up and move to specify a precondition axiom stating
the conditions under which the action is possible. [4 marks]
(iii) Give an effect axiom specifying the results of carrying out the action unlock.
[2 marks]
(iv) Write down a frame axiom stating that the move to action does not affect the
locked fluent.
[2 marks]
[Question 2 total: 20 marks]
1This was an error in the exam script. A set of clausal formulae is more like conjunctive normal form, except
that we give it as a set of clauses rather than a conjunction (the conjunction is implicit rather than explicitly written
with a ‘∧’ symbol). Each clause is either a literal or a disjunction of literals. A literal is either an atomic proposition
or a negated atomic proposition.
TURN OVER Page 4 of 5
COMP5450M01
Question 3
(a) For each of the following Prolog queries, give the value of the variable X after the query
has been executed:
(i) ?- X = 7/2. [1 mark]
(ii) ?- [1, [2, 3], 4] = [ | [X | ]] [1 mark]
(iii) ?- A = [1,2,3,4,5], setof( I, (member(I,A), I>2), X). [1 mark]
(iv) ?- append( [X], [2,3], [1,2,3] ). [1 mark]
(b) Consider the following formulae involving topological relations of the Region Connec-
tion Calculus (RCC) and the convex hull function, conv. The constants (a, b and c) refer
to particular spatial regions. In each case, draw a configuration of the regions referred
to by these constants that satisfies the formula, labelling your diagram to indicate which
region is which:
(i) DC(a, b) ∧ NTPP(sum(a, b), c) [2 marks]
(ii) TPP(a, b) ∧ TPP(b, c) ∧ TPP(a, c) [2 marks]
(iii) DC(a, b) ∧ TPP(a, conv(b)) [2 marks]
(c) A liger is an animal whose parents are a male lion and a female tiger. Use Description
Logic to give a definition of the concept Liger in terms of the concepts Lion, Tiger,
Male, Female and the relation hasParent. [4 marks]
(d) Write a Default Logic rule that formally represents the reasoning principle expressed
in the following statement: [2 marks]
“British people typically drink tea, except for children and those who drink coffee.”
(e) This question concerns a Fuzzy Logic in which the following definitions of linguistic
modifiers are specified:
quite(φ) = φ1/2 very(φ) = φ2
The logic is used to describe Leo the lion, who possesses certain characteristics to the
following degrees:
Large(leo) = 0.5 Fierce(leo) = 0.09 Clever(leo) = 0.4
Translate the following sentences into fuzzy logic and also give the fuzzy truth value of
each proposition (under the standard fuzzy interpretation of the Boolean connectives):
(i) Leo is not very clever. [2 marks]
(ii) Leo is very very large and quite fierce. [2 marks]
[Question 3 total: 20 marks]
[Grand total: 60 marks]
Page 5 of 5 END

欢迎咨询51作业君