CS534 Artificial Intelligence 
Homework 3 - Spring 2019

PROF. CAROLINA RUIZ 

Due Date: Monday, February 18th, 2019 by 10:59 am  

Homework Instructions:

1. Read Chapters/Sections 6, 7.1-7.5, 8, 9.1, 9.2.1-9.2.2, 9.5.1-9.5.3, 9.5.6 of the textbook.

2. This is a group homework. Students *must* form groups of 2 students. Students are free to select their HW3 teammate (it doesn't need to be the same teams as in HW2). You can post on the Canvas discussion board if you are looking for a HW3 teammate.

3. Do *not* split the problems between you and your teammate. Instead, solve each and every required HW problem by yourself and then meet with your teammate to compare your solutions and work on a joint solution together. This will prepare you both for the exam.

4. Turn in your group's written solutions (hardcopy) ONLY TO THE PROBLEMS MARKED AS REQUIRED BELOW by 10:59 am right before the beginning of class when the homework is due. No late homework will be accepted, no exceptions.

5. Solve the other, non-required problems in preparation for Exam 1 but don't submit your solutions as part of HW3 submission.

6. Given class size and the number of problems required in this HW, only a subset of 5 problems will be graded in detail (for a total of 90 points) and the remaining ones will receive credit based on a quick review (for a total of 10 points). The set of 5 problems to be graded will be selected by the professor and won't be revealed until the HW has been submitted.

Homework Problems:

• Chapter 6: (pp. 230-233)
  • Required for the HW:
    • 6.4 (part c only)
    • 6.8 (show your work, not just the final coloring)
    • 6.9
    • 6.11
  • Not required for the HW but useful to study for the exam:
    • 6.2
    • 6.3
    • 6.6

• Chapter 7: (pp. 279-284)
  • Required for the HW:
    • 7.4: parts a, b, c, h, k. [All the parts of this problem are good exercises; I am picking some just to keep the hw shorter.]
    • 7.10
    • 7.12. (Note that you need to covert those sentences to clausal form first.)
    • 7.17: part a only
    • Determine whether the following sentence is valid, unsatisfiable, or neither. Justify your answer with either truth tables, equivalent rewrites of the sentence, or both.

       ( ¬ ¬ q =>  ¬ p) => (p =>  ¬ q) 

  • Not required for the HW but useful to study for the exam:
    • 7.1
    • 7.5 (remember to prove both directions of the "if and only if")
    • 7.6
    • 7.7 (Note that the models must assign truth values each propositional letter A, B, C, and D, not just to the propositional letters appearing in the sentence. Also, note that A . B . C is shortcut for (A . B) . C, which is also equivalent to A . (B . C) )
    • 7.9

• Chapter 8: (pp. 315-321)
  • Required for the HW:
    • 8.3
    • 8.4
    • 8.10
    • 8.23 (parts a and b only)
  • Not required for the HW but useful to study for the exam:
    • 8.11
    • 8.20

• Chapter 9: (pp. 360-365)
  • Not required for the HW but useful to study for the exam:
    • Problem 1:

      In this problem, we will use 1st order logic to represent and reason with knowledge about the wumpus world.

      1. Read Section 8.3.4. It provides a 1st order representation of the wumpus world. In particular, consider the following assertions in our KB:
         • (A1). ∀x,y,a,b [Adjacent([x,y],[a,b]) ⇔ [(x=a ∧ (y=b-1 ∨ y=b+1)) ∨ (y=b ∧ (x=a-1 ∨ x=a+1))]]
         • (A2). ∀s [Breezy(s) ⇔ ∃ r [Adjacent (r,s) ∧ Pit(r)]]
      2. Let's consider again the situation stated in Section 7.2:
         • (K1) ¬ Breezy([1,1])
         • (K2) ¬ Breezy([1,2])
         • (K3) Breezy([2,1])
      3. Our agent is trying to determine whether or not there is a pit in cell [3,1]. So, let's express this as:
         • (C) Pit([3,1])
      4. Let's determine whether C follows from our Knowledge Base A1, A2, K1, K2, and K3 or not. To simplify life, let assume that our inference engine will start by instantiating (that is, generating particular cases of) A2 with all the possible Adjacent relationships expressed in A1 for the cells explicitly mentioned in KD (namely, [1,1], [1,2], [2,1]). For instance, our inference engine will use A1, A2, and K1 to generate:
         • (A2.1). Breezy([1,1]) ⇔ [Pit([1,2]) ∨ Pit([2,1])]
         Here is what you need to do:
         1. (5 points) Construct all possible instantiations of A1 that follow from A2, K1, K2, and K3, as illustrated above.
         2. (20 points) Use all those instatiations of A1 together with K1,K2, and K3 to prove C using a proof by refutation using resolution. Follow the process described in Section 7.5.2 step by step. Show your work in detail.
         3. (5 points) What can you say about the presence of a pit in location [2,2] at this point? Explain.
         4. (5 points) Could you use forward chaining or backward chaining to prove C from the instations of A2 that were generated? Explain your answer.
    • Problem 2:

      In this problem, you will show that the following assertions (A1), (A2), (A3), and (A4) together entail (C) by constructing a proof by refulation using resolution.

      • (A1). Every edible mushroom or poisonous mushroom is a mushroom.
        ∀x [Edible(x) ∨ Poisonous(x) ⇒ Mushroom(x)]

      • (A2). Every mushroom is grey, white, or yellow.
        ∀y [Mushroom(y) ⇒ Grey(y) ∨ White(y) ∨ Yellow(y)]

      • (A3). No edible mushroom is yellow.
        ∀z [Edible(z) ⇒ ¬ Yellow(z)]

      • (A4). No mushroom that is organic is grey.
        ∀w [Mushroom(w) ∧ Organic(w) ⇒ ¬ Grey(w)]

      • (C). If no mushroom is white, then no edible mushroom is organic.
        [∀i [Mushroom(i) ⇒ ¬ White(i)]] ⇒ [¬∃j [Edible (j) ∧ Organic(j)]]

      1. Negate the conclusion (C).
      2. (25 points) Convert each of the sentences (A1), (A2), (A3), (A4), and ¬ (C) to Conjuctive Normal Form (CNF) following the procedure described in Section 9.5.1 of the textbook step by step. Show your work.
      3. (25 points) Apply resolution until you reach the empty clause. At each step, show which two clauses are resolved, and what clause is obtained as a result. Show your work.