CSE571 Assignment 4 Solved

Exercise 1.1

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.  Following the example that we showed in class, construct the set of possible worlds. (You should find 32 of them.)

b.  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.  Consider a vocabulary with only four propositions, A, B, C, and D. How many models are there for the following sentences?

Exercise 1.2

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

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

a.

b.

 Represent the following sentences in first-order logic, using a vocabulary which you must define:

1. There is an agent who sells policies only to people who are not insured.
2. 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.

Assume the environment in Exercise 1.3, using propositional logic, express the following sentences:

1. There is only one Wumpus in the world
2. Locations that are adjacent to the Wumpus are smelly
3. If a Breeze is detected, a Pit must be around.

c. Assume the environment in Exercise 1.3, using first-order logic, express the same sentences in b.

Exercise 1.5

a. 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.  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.