Homework 4 -- due Thursday April 4

Written questions

1. [20 points] For each of the following sentences, decide if the logic sentence given is a correct translation of the English sentence or not. If not explain briefly why not and correct it:
   1. All houses have at least one bathroom.
      ∀ x [House(x) ∧ ∃ y Bathroom(y)] ⇒ In(x,y)
   2. There is a house in Minneapolis which costs more than any other house.
      ∀ x [House(x) ∧ In(x,Minneapolis)] ⇒ [∃ y House(y) ∧ Cost(y) > Cost(x)]
   3. There is only one house in Minneapolis that is pink.
      ∃ x House(x) ∧ In(x,Minneapolis) ∧ Color(x,Pink)
   4. Some houses cost less than some apartments.
      ∃ x House(x) ∧ ∃ y Apartment(y) ⇒ Cheaper(x,y)
   5. There are fastfood places in every city.
      ∀ x ∀ y [City(x) ∧ Fastfood (y)] ⇒ In(y,x)
2. [20 points] Convert these English sentences to predicate calculus, using the following predicates: Cat(x) = x is a cat; Bird(x) = x is a bird; Dog(x) = x is a dog; Animal(x) = x is an animal; Person(x) = x is a person. Owns(x,y) = x owns y; Likes(x,y) = x likes y, Kill(x,y) = x kills y. John is a constant.
   1. Birds do not like cats.
   2. Any person who owns a cat does not own a bird.
   3. No person would kill a cat.
   4. Some persons own a cat and a dog.
   5. John owns only one bird.
3. [10 points]
   1. Write the knowledge given below in predicate calculus using the following predicates: Person(x) = x is a person; Rich(x) = x is rich; Happy(x) = x is happy; Read(x) = x can read; Exciting(x) = x has an exciting life; Stupid(x) = x is stupid
      The change made to Exciting is to make things easier. You are free to use the predicates I had before
      "All persons who are rich and are not stupid are happy. Persons who can read are not stupid. Happy persons have exciting lives. John is a person. John can read and he is rich. "
   2. convert to CNF
   3. Answer the question "is there anyone who has an exciting life?" Notice that this is a question that requires not just True or False as an answer.
4. [20 points] Prove by resolution that the following set of clauses (in predicate calculus) is unsatisfiable. Assume that upper case arguments are constant, lower case arguments are variable:
   1. G(B)
   2. ¬ G(x) ∨ H(x)
   3. ¬ H(z) ∨ I(z)
   4. ¬ H(w) ∨ J(w,D)
   5. ¬ I(B) ∨ J(C,B)
   6. ¬ I(q) ∨ ¬ J(q,y)
5. [30 points]
   1. Write the following statements in predicate calculus:
      1. A truck is a vehicle.
      2. A SUV is a vehicle.
      3. A car is a vehicle.
      4. A truck is bigger than a SUV.
      5. There is a SUV that is bigger than every car.
      6. A RAM is a truck.
      7. A Tesla is a car.
      8. Bigger is transitive, i.e. if x is bigger than y and y is bigger than z then x is bigger than z.
   2. Convert them to CNF. Pay attention to how you skolemize existentially quantified variables. Recall that a Skolem constant cannot be unified with another constant except itself, but it can be unified with a variable.
   3. Prove by resolution with refutation: "A RAM is bigger than a Tesla". Remember that a Skolem constant cannot be unified with another constant except itself, but it can be unified with a variable.