Homework #2

Question #1:

Scotland yard has narrowed down the suspects to the butlers of the mansion but unfortunately there are three butlers. Your task is to determine the murderer(s), the weapon and the room in which the murder is committed. The first step of this task is to convert the following clues directly to proposition logic.

a) Jeeves or Lurch or Alfred committed the murder.
b) Either the murder occured in the pantry or in the bedroom (but not both)
c) Either the gun was used or the icepick was used as the murder weapon(but not both)
d) If the murder was committed with a gun then Lurch is a murderer
e) Either Lurch was a murderer or it was committed in the bedroom (but not both)
f) if the murder was done with the gun then either Jeeves was a murderer or it was done in the bedroom(but not both)
g) Sally lied when saying "If the room is the bedroom, Alfred is a murderer"

a. Jeeves v Lurch v Alfred
b. (pantry ^ ~bedroom) v (~pantry ^ bedroom)
c. (gun ^ ~icepick) v (~gun ^ icepick)
d. gun => Lurch
e. (~Lurch ^ bedroom) v (Lurch ^ ~bedroom)
f. gun => ((Jeeves ^ ~bedroom) v (~Jeeves ^ bedroom))
g. ~(bedroom => Alfred)
note above that since the fact is untrue, we can assert its negation

Question #2: Now convert the logic statements from Question #1 to conjunctive normal form. I.e. sequences of or's that are anded together.

a. (Jeeves v Lurch v Alfred)
b. (pantry v bedroom) ^ (~pantry v ~bedroom)
c. (gun v icepick ) ^ (~gun v ~icepick)
d. (~gun v Lurch )
e. (Lurch v bedroom) ^ (~Lurch v ~bedroom)
f. (Jeeves v bedroom v ~gun) ^ (~Jeeves v ~bedroom v ~gun)
g. (bedroom) ^ (~alfred)

Question #3 (programming): Fill in the functions for the walksat framework here to get a probabilistic sat solver.

Solution here.

Question #4: Use the solver above to determine who committed the crime. Is there any one person whom the evidence does not rule out? Can you be sure that one of the other people wasn't involved? How can you use an incomplete method (like solve) to rule out an individual? Can you add an additional clause or clauses? If so, do so. If not, explain why not as succinctly as possible.

You can rule out several of the candidates using logic but you can't rule out any candidates completely using the GSAT because it is an incomplete method. You can gain evidence that someone is not guilty by adding the fact that "x is the murderer" and seeing if GSAT can solve the new formula. The more random assignments GSAT tries unsuccessfully, the higher the probability that x is not the murderer but it must try every assignment before it's known for certain if x is the murderer.

Jared Saia

Last modified: Mon Apr 13 18:37:22 PDT 1998