CSC396 - Project 3
Logic

Assigned April 8th
Due April 22nd 9:45am


Problem 1

The salt has been stolen! Well, it was found that the culprit was either the Caterpillar, Bill the Lizard or the Cheshire Cat. The three were tried and made the following statements in court: CATERPILLAR: Bill the Lizard ate the salt. BILL THE LIZARD: That is true! CHESHIRE CAT: I never ate the salt.

As it happened, at least one of them lied and at least one told the truth. Who ate the salt?

Problem 2

Jason, Sandy, and Chris work at the circus and hold the jobs of penguin-trainer, knife-swallower, and master-of-ceremonies (not necessarily in that order). Jason owes the penquin-trainer $10. The master-of-ceremonies' spouse prohibits borrowing money. Sandy is not married. Your task is to figure out which person has which job.

Represent the facts in propositional logic. You should have nine propositional symbols to represent the possible person/job assignments. For example, you might use the symbol SM to indicate that Sandy is the master-of-ceremonies. You do not need to represent the relation between owing and borrowing, or being married and having a spouse; you can just use these to draw conclusions (e.g. from "Sandy is not married" and "the master-of-ceremonies' spouse" we know that Sandy can't be the master-of-ceremonies, which you can represent at ~SM). The conjunction of all the relevant facts forms a sentence which you can call KB. The possible answers to the problem are sentences like JP ^ SK ^ CM. There are six such combinations of person/job assignments. Solve the problem by showing that only one of them is implied by KB, and by saying what that interpretation is. You may use any sound inference procedure.

Problem 3

Write the following sentences in First-Order Logic

Problem 4

Do problem 9.4 in the text

Problem 5

Do problem 9.9 in the text, making sure that your sentences are in Horn Normal Form. Then prove that Charlie is a horse using backwards chaining. Do 9.9 again putting sentences in Conjunctive Normal Form and then prove that Charlie is a horse using Resolution by Refutation.