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.
January 2019
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
Question 1
(a) Translate the following sentence into Propositional Logic:
• I go shopping on Mondays and Tuesdays. [2 marks]
(b) TranslatethefollowingsentencesintoFirst-OrderPredicateLogic(usingequalitywhere necessary):
(i) Some yellow frogs are poisonous. (ii) All Helen’s rabbits are white or grey.
(iii) No dog ate more than one biscuit.
(iv) Edward hates everyone except himself.
[2 marks] [2 marks] [2 marks] [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 of M 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?
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)]
[4 marks]
Page 2 of 5 TURN OVER FOR QUESTIONS
(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 β,Γ⊢∆[∨⊢] (α ∨ β), Γ ⊢ ∆
Γ ⊢ α, ∆ [¬⊢] ¬α, Γ ⊢ ∆
Γ, ¬α∨β ⊢ α, ∆[→ ⊢r.w.] Γ, α → β ⊢ ∆
Γ⊢α,∆ and Γ⊢β,∆[⊢∧] Γ ⊢(α∧β), ∆
Γ⊢α,β,∆ [⊢∨] Γ ⊢ (α ∨ β), ∆
Γ, α ⊢ ∆ [ ⊢ ¬] Γ ⊢ ¬α, ∆
Γ ⊢ ¬α∨β, ∆[⊢ →r.w.] Γ ⊢ α → β, ∆
Γ ⊢ Φ(k),∆ [⊢∀]† Γ ⊢ ∀x[Φ(x)], ∆
† where κ cannot occur any- where in the lower sequent.
[Question 1 total: 20 marks]
∀x[Φ(x)], Φ(k), Γ ⊢ ∆ ∀x[Φ(x)], Γ ⊢ ∆
[∀⊢]
Page 3 of 5
TURN OVER
Question 2
(a)
(b)
(c)
(i) Give the set of clausal formulae (i.e. formulae in disjunctive normal form) 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.
Translate the following sentence into Propositional Tense Logic: If I win the lottery I will be rich forever after that.
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)
[4 marks]
[2 marks]
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(locked(door1), s0)
Holds(on floor(key,lounge),s0)
Holds(connects(door2, hall, study), s0) Holds(locked(door2), 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] TURN OVER Page 4 of 5
Question 3
(a) For each of the following Prolog queries, give the value of the variable X after the query has been executed:
Page 5 of 5
END
(i) ?- X = 7/2.
(ii) ?- [1, [2, 3], 4] = [ | [X | ]]
(iii) ?- A = [1,2,3,4,5], setof( I, (member(I,A), I>2), X). (iv) ?- append( [X], [2,3], [1,2,3] ).
[1 mark] [1 mark] [1 mark] [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)
(ii) TPP(a, b) ∧ TPP(b, c) ∧ TPP(a, c)
(iii) DC(a, b) ∧ TPP(a, conv(b))
[2marks] [2 marks] [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.
(ii) Leo is very very large and quite fierce.
[2 marks]
[2 marks] [Question 3 total: 20 marks]
[Grand total: 60 marks]