Homework 4 -- due Tuesday March 30

Written questions

1. [20 points]
   You are given the following set of sentences in propositional calculus:
   1. Humid implies not (Hot and not Sticky)
   2. not Hot and Sunny implies Pleasant
   3. Sunny and Humid
   4. Sunny or not Pleasant
   1. convert them to CNF,
   2. prove by resolution "Sticky or Pleasant",
   3. Try to prove "Sticky and Pleasant". Can you prove it? if not, what can you conclude?
2. [10 points] Show that every CNF clause can be rewritten in the form (P1 and .. Pm) implies (Q1 or .. Qn) where the Ps and Qs are proposition symbols.
3. [25 points] Write the following sentences in predicate calculus, using appropriate predicates:
   1. All big houses are expensive.
   2. All expensive houses are big.
   3. A house is expensive if it is big.
   4. Any small house costs less than any big house.
   5. Some condominiums are more expensive that some big houses.
   6. There is a house which is bigger than any other house in the village.
   7. Every house has at least one bathroom.
   8. There is only one house with a garden.
4. [15 points]
   You are given the following knowledge base:
   1. No computer science PhDs are unemployed.
   2. All unemployed people are poor.
   1. write the statements in predicate calculus using following predicates:
      C(x): x has PhD in computer science
      E(x): x is employed
      P(x): x is poor
   2. convert the statements to CNF skolemizing as needed,
   3. prove by resolution that "No computer science PhDs are poor."
   If you cannot prove the sentence, explain why it cannot be proven and make a small change to the knowledge base so that it can be proven.

Lisp questions

For this part we will use the logic package in aima. If you have not downloaded it, go to http://aima.cs.berkeley.edu/lisp/doc/install.html and follow the instructions. If you have it already, proceed with the questions. As always look into the file logic/test-logic.lisp to see examples of how to call the functions you will need to use.

Answer the following questions using the aima software:

1. [10 points] Show the truth table of
   1. (P or (not P and Q)) equivalent (P or Q)
   2. ((P implies Q) and (not Q)) implies P
   3. ((P or Q) and (P implies R) and (Q implies R)) implies R
   4. ((P or Q) and R) equivalent (P or (Q and R))
   What can you conclude for each of the cases? [write this part as a comment in your lisp file or as a separate file].
2. [10 points]
   1. solve using tell and ask in the aima software, the Problem 1 you solved above in the written part.
   2. do you know what algorithm does AIMA use to solve it? [write this part as a comment in your lisp file or as a separate file].
3. [10 points]
   1. represent using tell the following "If the unicorn is mythical, then it is immortal but if it is not mythical then it is a mortal mammal. If the unicorn is either immortal or a mammal, then it is horned. The unicorn is magical, if it is horned."
   2. use ask to answer the following questions "is the unicorn mythical", "is the unicorn magical", "is the unicorn horned"?