Resolution Example and Exercises

Solutions to Selected Problems

Example:

Consider the following axioms:

  1. All hounds howl at night.

  2. Anyone who has any cats will not have any mice.

  3. Light sleepers do not have anything which howls at night.

  4. John has either a cat or a hound.

  5. (Conclusion) If John is a light sleeper, then John does not have any mice.

The conclusion can be proved using Resolution as shown below. The first step is to write each axiom as a well-formed formula in first-order predicate calculus. The clauses written for the above axioms are shown below, using LS(x) for `light sleeper'.

  1. ∀ x (HOUND(x) → HOWL(x))

  2. ∀ x ∀ y (HAVE (x,y) ∧ CAT (y) → ¬ ∃ z (HAVE(x,z) ∧ MOUSE (z)))

  3. ∀ x (LS(x) → ¬ ∃ y (HAVE (x,y) ∧ HOWL(y)))

  4. ∃ x (HAVE (John,x) ∧ (CAT(x) ∨ HOUND(x)))

  5. LS(John) → ¬ ∃ z (HAVE(John,z) ∧ MOUSE(z))

The next step is to transform each wff into Prenex Normal Form, skolemize, and rewrite as clauses in conjunctive normal form; these transformations are shown below.

  1. ∀ x (HOUND(x) → HOWL(x))

    ¬ HOUND(x) ∨ HOWL(x)

  2. ∀ x ∀ y (HAVE (x,y) ∧ CAT (y) → ¬ ∃ z (HAVE(x,z) ∧ MOUSE (z)))

    ∀ x ∀ y (HAVE (x,y) ∧ CAT (y) → ∀ z ¬ (HAVE(x,z) ∧ MOUSE (z)))

    ∀ x ∀ y ∀ z (¬ (HAVE (x,y) ∧ CAT (y)) ∨ ¬ (HAVE(x,z) ∧ MOUSE (z)))

    ¬ HAVE(x,y) ∨ ¬ CAT(y) ∨ ¬ HAVE(x,z) ∨ ¬ MOUSE(z)

  3. ∀ x (LS(x) → ¬ ∃ y (HAVE (x,y) ∧ HOWL(y)))

    ∀ x (LS(x) → ∀ y ¬ (HAVE (x,y) ∧ HOWL(y)))

    ∀ x ∀ y (LS(x) → ¬ HAVE(x,y) ∨ ¬ HOWL(y))

    ∀ x ∀ y (¬ LS(x) ∨ ¬ HAVE(x,y) ∨ ¬ HOWL(y))

    ¬ LS(x) ∨ ¬ HAVE(x,y) ∨ ¬ HOWL(y)

  4. ∃ x (HAVE (John,x) ∧ (CAT(x) ∨ HOUND(x)))

    HAVE(John,a) ∧ (CAT(a) ∨ HOUND(a))

  5. ¬ [LS(John) → ¬ ∃ z (HAVE(John,z) ∧ MOUSE(z))] (negated conclusion)

    ¬ [¬ LS (John) ∨ ¬ ∃ z (HAVE (John, z) ∧ MOUSE(z))]

    LS(John) ∧ ∃ z (HAVE(John, z) ∧ MOUSE(z)))

    LS(John) ∧ HAVE(John,b) ∧ MOUSE(b)

The set of CNF clauses for this problem is thus as follows:

  1. ¬ HOUND(x) ∨ HOWL(x)

  2. ¬ HAVE(x,y) ∨ ¬ CAT(y) ∨ ¬ HAVE(x,z) ∨ ¬ MOUSE(z)

  3. ¬ LS(x) ∨ ¬ HAVE(x,y) ∨ ¬ HOWL(y)

    1. HAVE(John,a)

    2. CAT(a) ∨ HOUND(a)

    1. LS(John)

    2. HAVE(John,b)

    3. MOUSE(b)

Now we proceed to prove the conclusion by resolution using the above clauses. Each result clause is numbered; the numbers of its parent clauses are shown to its left.

[1.,4.(b):] 6. CAT(a) ∨ HOWL(a)

[2,5.(c):]

7. ¬ HAVE(x,y) ∨ ¬ CAT(y) ∨ ¬ HAVE(x,b)

[7,5.(b):]

8. ¬ HAVE(John,y) ∨ ¬ CAT(y)

[6,8:]

9. ¬ HAVE(John,a) ∨ HOWL(a)

[4.(a),9:]

10. HOWL(a)

[3,10:]

11. ¬ LS(x) ∨ ¬ HAVE(x,a)

[4.(a),11:]

12. ¬ LS(John)

[5.(a),12:]

13. □

Exercises:

1. Unify (if possible) the following pairs of predicates and give the resulting substitutions. b is a constant.

a. P(x, f(x), z)
¬ P(g(y),f(g(b)),y)
b. P(x, f(x))
¬ P(f(y), y)
c. P(x, f(z))
¬ P(f(y), y)

2. Consider the following axioms:

  1. Every child loves Santa.

  2. Everyone who loves Santa loves any reindeer.

  3. Rudolph is a reindeer, and Rudolph has a red nose.

  4. Anything which has a red nose is weird or is a clown.

  5. No reindeer is a clown.

  6. Scrooge does not love anything which is weird.

  7. (Conclusion) Scrooge is not a child.
Represent these axioms in predicate calculus; skolemize as necessary and convert each formula to clause form. (Note: `has a red nose' can be a single predicate. Remember to negate the conclusion.) Prove the unsatisfiability of the set of clauses by resolution.

3. Consider the following axioms:

  1. Anyone who buys carrots by the bushel owns either a rabbit or a grocery store.

  2. Every dog chases some rabbit.

  3. Mary buys carrots by the bushel.

  4. Anyone who owns a rabbit hates anything that chases any rabbit.

  5. John owns a dog.

  6. Someone who hates something owned by another person will not date that person.

  7. (Conclusion) If Mary does not own a grocery store, she will not date John.

Represent these clauses in predicate calculus, using only those predicates which are necessary. For example, you need not represent `person', and phrases such as `who buys carrots by the bushel' may be represented by a single predicate. Negate the conclusion and convert to clause form, skolemizing as necessary. Prove the unsatisfiability of the resulting set of clauses by resolution.

4. Consider the following axioms:

  1. Every Austinite who is not conservative loves some armadillo.

  2. Anyone who wears maroon-and-white shirts is an Aggie.

  3. Every Aggie loves every dog.

  4. Nobody who loves every dog loves any armadillo.

  5. Clem is an Austinite, and Clem wears maroon-and-white shirts.

  6. (Conclusion) Is there a conservative Austinite?

5. Consider the following axioms:

  1. Anyone whom Mary loves is a football star.

  2. Any student who does not pass does not play.

  3. John is a student.

  4. Any student who does not study does not pass.

  5. Anyone who does not play is not a football star.

  6. (Conclusion) If John does not study, then Mary does not love John.

6. Consider the following axioms:

  1. Every coyote chases some roadrunner.

  2. Every roadrunner who says ``beep-beep'' is smart.

  3. No coyote catches any smart roadrunner.

  4. Any coyote who chases some roadrunner but does not catch it is frustrated.

  5. (Conclusion) If all roadrunners say ``beep-beep'', then all coyotes are frustrated.

7. Consider the following axioms:

  1. Anyone who rides any Harley is a rough character.

  2. Every biker rides [something that is] either a Harley or a BMW.

  3. Anyone who rides any BMW is a yuppie.

  4. Every yuppie is a lawyer.

  5. Any nice girl does not date anyone who is a rough character.

  6. Mary is a nice girl, and John is a biker.

  7. (Conclusion) If John is not a lawyer, then Mary does not date John.

8. Consider the following axioms:

  1. Every child loves anyone who gives the child any present.

  2. Every child will be given some present by Santa if Santa can travel on Christmas eve.

  3. It is foggy on Christmas eve.

  4. Anytime it is foggy, anyone can travel if he has some source of light.

  5. Any reindeer with a red nose is a source of light.

  6. (Conclusion) If Santa has some reindeer with a red nose, then every child loves Santa.

9. Consider the following axioms:

  1. Every investor bought [something that is] stocks or bonds.

  2. If the Dow-Jones Average crashes, then all stocks that are not gold stocks fall.

  3. If the T-Bill interest rate rises, then all bonds fall.

  4. Every investor who bought something that falls is not happy.

  5. (Conclusion) If the Dow-Jones Average crashes and the T-Bill interest rate rises, then any investor who is happy bought some gold stock.

10. Consider the following axioms:

  1. Every child loves every candy.

  2. Anyone who loves some candy is not a nutrition fanatic.

  3. Anyone who eats any pumpkin is a nutrition fanatic.

  4. Anyone who buys any pumpkin either carves it or eats it.

  5. John buys a pumpkin.

  6. Lifesavers is a candy.

  7. (Conclusion) If John is a child, then John carves some pumpkin.

11. Consider the following axioms:

  1. Every tree that is an oak contains some grackle.

  2. If anyone walks under any tree that contains any grackle, then he hates every grackle.

  3. For every building, there is some tree that is beside it.

  4. Taylor Hall is a building.

  5. Every CS student visits Taylor Hall.

  6. If anyone visits any building, then he walks under every tree that is beside that building.

  7. (Conclusion) If some CS student does not hate some grackle, then there is some tree beside Taylor Hall that is not an oak.

12. Consider the following axioms:

  1. Every child sees some witch.

  2. No witch has both a black cat and a pointed hat.

  3. Every witch is good or bad.

  4. Every child who sees any good witch gets candy.

  5. Every witch that is bad has a black cat.

  6. (Conclusion) If every witch that is seen by any child has a pointed hat, then every child gets candy.

13. Consider the following axioms:

  1. Every boy or girl is a child.

  2. Every child gets a doll or a train or a lump of coal.

  3. No boy gets any doll.

  4. No child who is good gets any lump of coal.

  5. (Conclusion) If no child gets a train, then no boy is good.

14. Consider the following axioms:

  1. Every child who finds some [thing that is an] egg or chocolate bunny is happy.

  2. Every child who is helped finds some egg.

  3. Every child who is not young or who tries hard finds some chocolate bunny.

  4. (Conclusion) If every young child tries hard or is helped, then every child is happy.

15. Consider the following axioms:

  1. Anything that is played by any student is tennis, soccer, or chess.

  2. Anything that is chess is not vigorous.

  3. Anyone who is healthy plays something that is vigorous.

  4. Anyone who plays any chess does not play any soccer.

  5. (Conclusion) If every student is healthy, then every student who plays any chess plays some tennis.

16. Consider the following axioms:

  1. Every student who makes good grades is brilliant or studies.

  2. Every student who is a CS major has some roommate. [Make ``roommate'' a two-place predicate.]

  3. Every student who has any roommate who likes to party goes to Sixth Street.

  4. Anyone who goes to Sixth Street does not study.

  5. (Conclusion) If every roommate of every CS major likes to party, then every student who is a CS major and makes good grades is brilliant.

17. Consider the following axioms:

  1. Everyone who aces any final exam studies or is brilliant or is lucky.

  2. Everyone who makes an A aces some final exam.

  3. No CS major is lucky.

  4. Anyone who drinks beer does not study.

  5. (Conclusion) If every CS major makes an A, then every CS major who drinks beer is brilliant.

18. Consider the following axioms:

  1. Anyone who loves any lottery is a gambler.

  2. Everyone who favors the lottery proposition loves some lottery.

  3. Everyone favors the lottery proposition or opposes the lottery proposition.

  4. If every Baptist votes and opposes the lottery proposition, then the lottery proposition does not win.

  5. Every Baptist who is faithful is not a gambler.

  6. (Conclusion) If every Baptist votes and the lottery proposition wins, then some Baptist is not faithful.

19. Consider the following axioms. Hint: the predicates WHITE, SNOWY, HAPPY, and GETS should each have a ``time'' argument.

  1. Anyone who owns any sled is happy when it is snowy.

  2. When it is white, it is snowy.

  3. If Santa is happy at Christmas, then every child who is good gets some toy at Christmas.

  4. Any child who gets a toy at any time is happy at that time.

  5. Santa owns a sled.

  6. (Conclusion) If it is white at Christmas and every child who is not good owns some sled, then every child is happy at Christmas.

20. Consider the following axioms.

  1. Anyone who is on Sixth Street and is not a police officer has some costume.

  2. No CS student is a police officer.

  3. Every costume that is good is a robot costume.

  4. For anyone, if they are on Sixth Street and are happy, then every costume they have is good or they are drunk.

  5. (Conclusion) If no CS student is drunk and every CS student on Sixth Street is happy, then every CS student on Sixth Street has some costume that is a robot costume.

21. Consider the following axioms.

  1. For every mall, there is some Santa who is at the mall.

  2. Every child who visits anywhere talks with every Santa who is at the place visited. [Don't make a predicate for ``the place visited''; it should just be a variable.]

  3. Every child who is a city child visits some mall.

  4. Every child who is good or who talks with some Santa gets some toy.

  5. (Conclusion) If every child who is not a city child is good, then every child gets some toy.

22. Consider the following axioms.

  1. Everyone who feels warm either is drunk, or every costume they have is warm.

  2. Every costume that is warm is furry.

  3. Every AI student is a CS student.

  4. Every AI student has some robot costume.

  5. No robot costume is furry.

  6. (Conclusion) If every CS student feels warm, then every AI student is drunk.

23. Consider the following axioms.

  1. Every bird sleeps in some tree.

  2. Every loon is a bird, and every loon is aquatic.

  3. Every tree in which any aquatic bird sleeps is beside some lake.

  4. Anything that sleeps in anything that is beside any lake eats fish.

  5. (Conclusion) Every loon eats fish.

24. Consider the following axioms.

  1. Everyone is like him/her self.

  2. If someone is a member of a club, then they want to be a member and the club will accept them.

  3. Groucho does not want to be a member of any club that will accept anyone like him.

  4. (Conclusion) Groucho is not a member of any club.

25.``Schubert's Steamroller'', for the ambitious. (See C. Walther, AAAI-84, p. 330.)

Wolves, foxes, birds, caterpillars, and snails are animals, and there are some of each of them. Also there are some grains, and grains are plants. Every animal either likes to eat all plants or all animals much smaller than itself that like to eat some plants. Caterpillars and snails are much smaller than birds, which are much smaller than foxes, which in turn are much smaller than wolves. Wolves do not like to eat foxes or grains, while birds like to eat caterpillars but not snails. Caterpillars and snails like to eat some plants. Therefore there is an animal that likes to eat a grain-eating animal.

Solutions to Selected Problems

Gordon S. Novak Jr.