CSE 571  Homework 4

CSE 571 
Homework 4

Only typed answers will be accepted.
Be precise and concise in your answers. You may add hand-drawn figures when necessary.
Exercise 1.1 (10pt)
Suppose the agent has progressed to the point shown below, having perceived nothing in [1,1], a breeze in
[2,1], and a stench in [1,2], and is now concerned only with the contents of [1,3], [2,2], and [3,1]. Each of
these can contain a pit, and at most one can contain a wumpus.
a. (4pt) Following the example that we showed in class, construct the set of possible worlds. (You should
find 32 of them.)
b. (3pt) Mark the worlds in which the KB is true and those in which each of the following sentences is
true:
α2 = “There is no pit in [2,2].”
α3 = “There is a wumpus in [1,3].” Hence show that KB ⊨ α2 and KB ⊨ α3.
c. (3pt) Consider a vocabulary with only four propositions, A, B, C, and D. How many models are there
for the following sentences?
Exercise 1.2 (12pt)
Prove the validity of the following sequents, assuming the binding priority of the connectives covered in
class and using ONLY the basic natural deduction rules. Hint: all of them have disjunction
elimination as a key block.
(a) p → q, r → s ⊢ p ∨ r → q ∨ s
(b) (p ∨ (q → p)) ∧ q ⊢ p
(c) p → (q ∨ r), q → s, r → s ⊢ p → s
Exercise 1.3 (12pt)
Given the Wumpus world, that the following actions of the agents [1, 1] ®[1, 2](up) ®[1, 1] ®[2, 1],
and the sensor readings as shown in the figure (B for Breeze, S for Stench, and G for Glitter). Use natural
deduction, similar to that shown in our lecture, to show that W3,1 (Wumpus is at location [3, 1]) is true.
Clearly write out the (necessary) premises first and then the proof steps. Hint: this will be very similar
to what we discussed in lectures.
Exercise 1.4 (10pt)
a. (4pt) Represent the following sentences in first-order logic, using a vocabulary which you must
define:
I. There is an agent who sells policies only to people who are not insured.
II. Politicians can fool some of the people all of the time, and they can fool all of the people
some of the time, but they can’t fool all of the people all of the time.
b. (3pt) Assume the environment in Exercise 1.3, using propositional logic, express the following
sentences:
I. There is only one Wumpus in the world
II. Locations that are adjacent to the Wumpus are smelly
III. If a Breeze is detected, a Pit must be around. 
c. (3pt) Assume the environment in Exercise 1.3, using first-order logic, express the same sentences
in b.
Exercise 1.5 (6pt)
a. (3pt) In the Forward Chaining algorithm, after the algorithm stops, prove that for those atoms that
are not assigned to true during the inference process, there exists a model in the KB in which the atom
is true and there exists a model in the KB in which the atom is false.
b. (3pt) Prove that the resolution process discussed in the lecture (also attached below) is correct
using entailment (semantics of propositional logic), or that the top entails the bottom.