CSci 4511 - Homework 4

Homework 4 -- due Thursday April 4

This homework will be graded out of 100 points. It will count 6% of the grade.

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.
Copyright: © 2019 by the Regents of the University of Minnesota
Department of Computer Science and Engineering. All rights reserved.
Comments to: Maria Gini
Changes and corrections are in red.