Assignment 5 for CSE 415 (Autumn 2011)

Assignment 5: Propositional and Predicate Logic

CSE 415: Introduction to Artificial Intelligence
The University of Washington, Seattle, Autumn 2011

Due Monday, November 7 through Catalyst CollectIt at 2:00 PM.

You should turn in a file A5.pdf containing your answers.

Reading material for this assignment comes from Chapters 4 and 6 of Introduction to Artificial Intelligence Using Python.

Problems (Total: 100 points).

(10 points) Make a truth table for the contrapositive rule. Your table should have five columns: one each for P, Q, ~P, ~Q, and ~Q -> ~P
(10 points) Apply Wang's algorithm to prove the inference rule known as "hypothetical syllogism". Given p -> Q, Q ->R, Therefore, P -> R
(5 points) Find the resolvent for the two clauses:
```
     P v ~Q v R
     P v ~R v S
```
(35 points) Consider the following logic puzzle, which is one of many created by Lewis Carroll, the author of Alice in Wonderland.
```
  No birds, except ostriches, are 9 feet high.
  There are no birds in this aviary that belong to anyone but me.
  No ostrich lives on mince pies.
  I have no birds less than 9 feet high.
```
Prove that these premises imply the following conclusion:
```
  Any bird in this aviary does not live on mince pies.
```
In your proof, use the following symbols to represent statements.
```
H:  Height of the bird is not less than nine feet.
O:  The bird is an ostrich.
M:  The bird lives on mince pies.
I:  I own the bird.
A:  The bird is in this aviary.
```
1. (10 points) Show the premises as logical formulas represented using these symbols. As you encode each premise, you may translate it from being a generalization (e.g., "no birds...") to a statement about a particular bird ("the bird"). For example, the first premise can be translated to "If the bird is an ostrich, then the height of the bird is not less than nine feet."
2. (3 points) Show the conclusion as a logical formula represented using these symbols.
3. (2 points) Show the negation of the conclusion using these symbols.
4. (10 points) Show all premises and the negation of the conclusion as a set of clauses.
5. (10 points) Finally use the resolution method for your proof, and show for each resolution step which formulas are involved as parents and what the resolvent is.
Chapter 6 exercise 7a. (5 points)
Chapter 6 exercise 8. (10 points)
Chapter 6 exercise 10. (25 points)

Updates and Corrections If necessary, updates and corrections will be posted here and mentioned in class or on the mailing list. This page was last updated Oct. 31, 2011.