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.