HW4
1. [25 points] For each of the following English sentences, decide if the logic sentence is a
correct translation or not. If not explain why not and correct it. Look at then carefully to make
sure you spot the mistakes:
1. Every house has a door.
∀x ∃y [House(x) ∧ Door(y)] ⇒ In(x,y)
2. An apartment is rentable only if it is empty.
∀x Apartment(x) ⇒ [Rentable(x) ∧ Empty(x)]
3. There is a seller who sells cars only to rich people
∀x ∃y [[Car(x) ∧ Seller(y) ∧ Person(z) ∧ Rich(z) ] ⇒ Sells(y,x,z)]
4. There is a cat in each house
∃x Cat(x) ∧ [∀y House(y) ⇒ In(x,y)]
5. There is only one park in Minneapolis that has a waterfall [Pay attention to “only one”]
∀x [Park(x) ∧ In(x,Mpls)] ⇒ ∃y Waterfall(y) ∧ In(y,x)
2. [20 points] You are given the English sentence “Anyone who owns a pool owns a house” and
different logical expressions:
1. ∀x∀y∀z [[Pool(y) ∧Owns(x, y) ∧Owns(x, z)] → House(z)]
2. ∃x∃y∃z [Pool(y) ∧House(z) ∧Owns(x, y) ∧Owns(x, z)]
3. ∀x∀y [[Pool(y) ∧Owns(x, y)] → [∃z House(z) ∧Owns(x, z)]
4. ∀x∀y∀z [ [Pool(y) ∧ Owns(x, y) ∧ House(z)] ] → Owns(x, z)]
For each of the logical sentences, write in English what the logical sentence is saying. Is any of
the logical expressions a correct translation from English to logic? If yes, which one?
3. [10 points] Convert the following predicate logic expressions to CNF:
1. ∀x [ [Dog(x) ∧ ∃y [Owner(y,x)]⇒ Feed(y,x) ∧ Loves(x,y) ]
2. ∀x ∃y ∀z ∃w { [Person(x) ∧ House(z)] ⇒ [ [Friend(y,x) ∧ Sell(x,y,z) ] ⇒ [Friend(y,w) ∧
Happy(w)] ]}
4. [20 points] Prove using resolution with refutation that ¬Dog(Fido) is entailed by this
knowledge base. Capital case letters used as arguments indicate constants, lower case letters
are variables. First, convert to CNF, then show the steps in the resolution with refutation proof:
1. ∀x Dog(x) ⇒ Strong(x)
2. ∀x Strong(x) ⇒ Independent(x)
3. ∀x ∀p [Strong(x) ∧ Owner(p,x)] ⇒ Loyal(x,p)
4. ∀x ∀y Independent(x) ⇒ ¬ Loyal(x,y)
5. Owner(John,Fido)
5. [25 points] Represent each of the following sentences in predicate calculus, using the
predicates Major(x,y): x is a major in y, Love(x,y): x loves y, Like(x,y): x likes y, Own(x,y): x owns
y.
1. All computer science majors own a Mac or a PC.
2. Everyone who owns a Mac owns an IPOD.
3. All except one student in Stats 101 are Math majors.
4. IPOD owners love music.
5. John is a CS major who does not like music. Bill hates all cats which eat birds.
Convert each sentence to CNF and show by resolution with refutation that “John owns a PC” is
entailed by the knowledge base. Show all the steps in the resolution until you reach a
contradiction.