Homework 4 -- due Wednesday April 1

Written questions

1. [15 points] Convert these English sentences to predicate calculus, using the following predicates: Student(x), Athlete(v), School(y), Class(z), InClass(x,z), Faster(x,w).
   1. There is a class where all the students are athletes.
   2. There is a class that has only one student.
   3. Every school has a class where at least one student in the class is an athlete.
   4. Not every student takes a Biology class.
   5. John is faster than any other student in his class.
2. [15 points] Specify if each of the following expressions represents correctly the corresponding English statement. If not explain why not and correct it.
   1. There is a cat in each house.

      ∀ x ∀ y [House(x) ∧ Cat(y) ⇒ In(y,x)]

   2. Every cat owner loves all animals.

      ∃ x ∃ y [Person(x) ∧ Cat(y) ∧ Owns(x,y)] ∧ ∀ z [Animal(z) ⇒ Loves(x,z)]

   3. Cats catch birds.

      ∀ x ∃ y Cat(x) ∧ Bird(y) ∧ Catch(x,y)]

   4. Birds live in all cities.

      ∀ x City(x) ∧ ∃ y Bird(y) ∧ Livesin(y,x)

   5. Anyone who owns a bird does not own any cat.

      ∀ x ∀ y ∀ z Person(x) ∧ Bird(y) ∧ Cat(z) ∧ Own(x,y) ∧ ¬ Own(x,z)

3. [10 points] Write the following sentences in English, making clear what are the differences between them:
   1. ∀ x ∃ y Class(x) ⇒ Student(y) ∧ In(y,x)
   2. ∃ y ∀ x Student(y) ∧ Class(x) ⇒ In(y,x)
   3. ∃ x ∃ y Class(x) ∧ Student(y) ∧ In(y,x)
   4. ∀ x ∀ y Class(x) ∧ Student(y) ⇒ In(y,x)
   5. ∀ x ∀ y Class(x) ∧ Student(y) ∧ In(y,x)
4. [10 points] Convert to following expressions to CNF
   1. (B ∨ (A ∧ C)) ⇒ (B ∨ ¬ A)
   2. ∀ p [ [Pet(p) ∧ ∃ c [Owner(c,p) ∨ Feeds(c,p)]] ⇒ Happy(p)]
   3. ∀ x ∃ y ∀ z [P(x,y,z) ⇒ [∃ u Q(x,u)]]
5. [15 points]
   1. This question requires to use resolution for propositional logic. First, convert the following sentences to CNF:
      1. ¬ A ⇒ B ∨ C
      2. A ⇒ B
      3. ¬ (¬ B ⇒ D)
   2. Prove "C ∧ ¬ D'' using resolution with refutation. Show the steps in the resolution proof.
6. [15 points]
   1. Represent the following sentences in predicate calculus, using the predicates Cat(x), Bird(y), Eat(x,y), and Hate(x,y).
      1. Bill hates cats who eat birds.
      2. Felix is a cat.
      3. Felix ate a bird.
   2. Convert each of them to conjunctive normal form.
   3. Prove by resolution that "Bill hates Felix."
7. [20 points]
   1. What is a Horn clause? why are Horn clauses important?
   2. Is Modus Ponens in propositional calculus complete? What does completeness mean?
   3. Entailment in propositional calculus is decidable, but in predicate calculus it is only semidecidable. What does it mean? Be precise.
   4. Suppose you use resolution with refutation to prove that α ⊨ β. Does is mean that β is valid? If not, why not?
   Copyright: © 2020 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.