CMPT 310 -  Assignment 3

CMPT 310 - 
Assignment 3

10 marks
Important Note: Students must work individually on this, and other CMPT 310, assignments. You may not discuss the specific questions in this assignment, nor their solutions
with any other student. You may not provide or use any solution, in whole or in part, to or
by another student.
You are encouraged to discuss the general concepts involved in the questions in the context
of completely different problems. If you are in doubt as to what constitutes acceptable
discussion, please ask!
Question 1 (3 marks)
Alice, Bob, and Christine belong to the Alpine Club. Every member of the Alpine Club who
is not a skier is a mountain climber. Mountain climbers do not like rain, and anyone who
does not like snow is not a skier. Bob dislikes whatever Alice likes, and likes whatever Alice
dislikes. Alice likes rain and snow.
(a) Prove that the given sentences logically imply (entail) that there is a member of the
Alpine Club who is a mountain climber but not a skier. For this purpose, express the
statements as a set of FOL formulas KB, formulate an appropriate query α, and then
apply the Resolution method. Use answer extraction to find out who that individual
is. In your formulation, use the following vocabulary:
• C (x): Predicate. Person x is a member of the Alpine Club.
• S(x): Predicate. Person x is a skier.
• M (x): Predicate. Person x is a mountain climber.
• L(x, y): Predicate. Person x likes y.
1
• a, b, c: Constants denoting the three persons.
• r , s: Constants denoting rain and snow, respectively.
(b) Suppose we had been told that Bob likes whatever Alice dislikes, but we had not
been told that Bob dislikes whatever Alice likes. Prove that the resulting set of
sentences KB0
no longer logically implies that there is a member of the Alpine Club
who is a mountain climber but not a skier. For this purpose, present a logical
interpretation I that is a counterexample, i.e. where I |= KB0
, but I 6|= α.
1For the purpose of this assignment, we assume that “x dislikes y” means ¬L(x, y).
1
Question 2 (3 marks)
Consider the following simplified variant of the wellknown Blocks World. There are three blocks A, B, and
C, each of which is initially located on the table T. The
goal is to have A on B and B ontop of C. The robot can
perform the following two actions:
• Move(x, y, z): move block x from y onto block z.
This requires that x is on y and both x and z are
clear.
• MoveToTable(x, y): move block x from y onto the
table. This requires that x is on y and x is clear.
A C
A
B
B C
T T
(a) Present Strips operators for the two actions together with the initial state (Start)
and the goal (Finish). Use the predicates On(x, y) to denote that block x is on (block
or table) y and Clear(x) to say that there is no block on top of block x.
(b) Draw the partial plan that results from first introducing Move(B, y1, C) and then
Move(A, y2, B), each satisfying one precondition of Finish. Satisfy the remaining open
preconditions by means of Start using appropriate variable assignments where
necessary. Use solid lines for causal links and dashed lines for ordering constraints.
Since a causal link always implies an ordering, you do not have to draw both arrows
in these cases but only the one for the causal link.
(c) Indicate where the plan contains a conflict by circling the precondition/effect pair
that causes this threat. Resolve the conflict by either promotion or demotion and
draw the resulting plan. Is the plan now consistent? Is it complete?
2
Question 3 (2 marks)
In an exam a professor asks a student three questions. If the student is well-prepared she
can give the right answer to any of these questions with a probability of 95 %. Otherwise
she will have a 30 % chance to answer the first question correctly, a 50 % chance to answer
the second question correctly, and only a 10 % chance to answer the third question
correctly. If the student is (or is not) well-prepared, answering some questions correctly or
not neither increases nor decreases the chance for answering another question correctly.
Normally, 4 out of 5 students are well-prepared.
Let Qi stand for answering question i correctly, and W for being well-prepared.
(a) Which (unconditional or conditional) probabilities are directly given in the above text
with what values? [Hint: There are exactly seven.]
(b) Compute: P(W | Q1), P(Q1, Q2 | ¬W), P(Q3 | Q1, Q2, W).
(c) If the student answers the first and second question correctly but gives a wrong
answer to the third question: How probable is it that the student is well-prepared? In
other words:
Compute P(W | Q1, Q2, ¬Q3).
(d) Compute P(W | Q1, ¬Q2, ¬Q3).2
(e) Why is it important that correct or incorrect answers to some questions do not
influence the chance for answering another question correctly?
2Are you surprised by this value compared to part (c)) because of the 50 % chance of the second question?
If you like you can compute P(W |(¬)Q1,(¬)Q2,(¬)Q3) for all the other combinations of the Qi and ¬Qi
.
3
Question 4 (2 marks)
In the belief network on the right the random variables S, R, L, W stand
for “season”, “raining”, “lawn sprinkler on”, “sidewalk wet”, respectively. The CPTs (Conditional Probability Tables) for R, L, W are given
by the following tables:
S P(R | . . .)
spring 0.45
summer 0.15
autumn 0.35
winter 0.20
S P(L | . . .)
spring 0.15
summer 0.30
autumn 0.05
winter 0.00
R L P(W | . . .)
T T 0.95
T F 0.95
F T 0.90
F F 0.05
S
R L
W
The prior probability for each of the four seasons (spring, summer , autumn, winter ) is
0.25. The accuracy of your answers (to all parts of this exercise) should be at least three
decimal places.
(a) Compute P(W ∧ ¬L ∧ R ∧ S=spring).
(b) If it is not raining and the lawn sprinkler is off: how likely is winter?
(i. e.: Compute P(S=winter | ¬R ∧ ¬L).)
(c) What is the probability for rain in the summer when the sidewalk is wet? 3
(i. e.: What is P(R | W ∧ S=summer )?)
3Before computing it, try a rough guess. (Guess at least whether it is greater or less than 0.5?)
4