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
- All purple mushrooms are poisonous
- No purple mushroom is poisonous
- There are exactly two purple mushrooms
- A mushroom is poisonous if it has spots on the cap
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.