Resolution Example and Exercises
Solutions to Selected Problems
Example:
Consider the following axioms:
 All hounds howl at night.
 Anyone who has any cats will not have any mice.
 Light sleepers do not have anything which howls at night.
 John has either a cat or a hound.
 (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 wellformed formula in firstorder
predicate calculus. The clauses written for the above axioms are shown
below, using LS(x) for `light sleeper'.

&forall x (HOUND(x) &rarr HOWL(x))

&forall x &forall y (HAVE (x,y) &and CAT (y) &rarr ¬ &exist z (HAVE(x,z) &and MOUSE (z)))

&forall x (LS(x) &rarr ¬ &exist y (HAVE (x,y) &and HOWL(y)))

&exist x (HAVE (John,x) &and (CAT(x) &or HOUND(x)))

LS(John) &rarr ¬ &exist z (HAVE(John,z) &and 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.

&forall x (HOUND(x) &rarr HOWL(x))
¬ HOUND(x) &or HOWL(x)

&forall x &forall y (HAVE (x,y) &and CAT (y) &rarr
¬ &exist z (HAVE(x,z) &and MOUSE (z)))
&forall x &forall y (HAVE (x,y) &and CAT (y) &rarr
&forall z ¬ (HAVE(x,z) &and MOUSE (z)))
&forall x &forall y &forall z (¬ (HAVE (x,y) &and CAT (y))
&or ¬ (HAVE(x,z) &and MOUSE (z)))
¬ HAVE(x,y) &or ¬ CAT(y) &or ¬ HAVE(x,z) &or ¬ MOUSE(z)

&forall x (LS(x) &rarr
¬ &exist y (HAVE (x,y) &and HOWL(y)))
&forall x (LS(x) &rarr &forall y ¬ (HAVE (x,y) &and HOWL(y)))
&forall x &forall y (LS(x) &rarr ¬ HAVE(x,y) &or ¬ HOWL(y))
&forall x &forall y (¬ LS(x) &or ¬ HAVE(x,y) &or ¬ HOWL(y))
¬ LS(x) &or ¬ HAVE(x,y) &or ¬ HOWL(y)

&exist x (HAVE (John,x) &and (CAT(x) &or HOUND(x)))
HAVE(John,a) &and (CAT(a) &or HOUND(a))

¬ [LS(John) &rarr ¬ &exist z (HAVE(John,z)
&and MOUSE(z))] (negated conclusion)
¬ [¬ LS (John) &or ¬ &exist z (HAVE (John, z) &and MOUSE(z))]
LS(John) &and &exist z (HAVE(John, z) &and MOUSE(z)))
LS(John) &and HAVE(John,b) &and MOUSE(b)
The set of CNF clauses for this problem is thus as follows:

¬ HOUND(x) &or HOWL(x)

¬ HAVE(x,y) &or ¬ CAT(y) &or ¬ HAVE(x,z) &or ¬ MOUSE(z)

¬ LS(x) &or ¬ HAVE(x,y) &or ¬ HOWL(y)


HAVE(John,a)

CAT(a) &or HOUND(a)


LS(John)

HAVE(John,b)

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) &or HOWL(a) 
[2,5.(c):]  7.  ¬ HAVE(x,y) &or ¬ CAT(y) &or ¬ HAVE(x,b) 
[7,5.(b):]  8.  ¬ HAVE(John,y) &or ¬ CAT(y) 
[6,8:]  9.  ¬ HAVE(John,a) &or HOWL(a) 
[4.(a),9:]  10.  HOWL(a) 
[3,10:]  11.  ¬ LS(x) &or ¬ 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:
 Every child loves Santa.
 Everyone who loves Santa loves any reindeer.
 Rudolph is a reindeer, and Rudolph has a red nose.
 Anything which has a red nose is weird or is a clown.
 No reindeer is a clown.
 Scrooge does not love anything which is weird.
 (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:
 Anyone who buys carrots by the bushel owns either a rabbit or a
grocery store.
 Every dog chases some rabbit.
 Mary buys carrots by the bushel.
 Anyone who owns a rabbit hates anything that chases any rabbit.
 John owns a dog.
 Someone who hates something owned by another person will not date
that person.
 (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:
 Every Austinite who is not conservative loves some armadillo.
 Anyone who wears maroonandwhite shirts is an Aggie.
 Every Aggie loves every dog.
 Nobody who loves every dog loves any armadillo.
 Clem is an Austinite, and Clem wears maroonandwhite shirts.
 (Conclusion) Is there a conservative Austinite?
5. Consider the following axioms:
 Anyone whom Mary loves is a football star.
 Any student who does not pass does not play.
 John is a student.
 Any student who does not study does not pass.
 Anyone who does not play is not a football star.
 (Conclusion) If John does not study, then Mary does not love John.
6. Consider the following axioms:
 Every coyote chases some roadrunner.
 Every roadrunner who says ``beepbeep'' is smart.
 No coyote catches any smart roadrunner.
 Any coyote who chases some roadrunner but does not
catch it is frustrated.
 (Conclusion) If all roadrunners say ``beepbeep'', then all coyotes
are frustrated.
7. Consider the following axioms:
 Anyone who rides any Harley is a rough character.
 Every biker rides [something that is] either a Harley or a BMW.
 Anyone who rides any BMW is a yuppie.
 Every yuppie is a lawyer.
 Any nice girl does not date anyone who is a rough character.
 Mary is a nice girl, and John is a biker.
 (Conclusion) If John is not a lawyer, then Mary does not date John.
8. Consider the following axioms:
 Every child loves anyone who gives the child any present.
 Every child will be given some present by Santa if Santa
can travel on Christmas eve.
 It is foggy on Christmas eve.
 Anytime it is foggy, anyone can travel if he has some
source of light.
 Any reindeer with a red nose is a source of light.
 (Conclusion) If Santa has some reindeer with a red nose, then
every child loves Santa.
9. Consider the following axioms:
 Every investor bought [something that is] stocks or bonds.
 If the DowJones Average crashes, then all stocks that are
not gold stocks fall.
 If the TBill interest rate rises, then all bonds fall.
 Every investor who bought something that falls is not happy.
 (Conclusion) If the DowJones Average crashes and the TBill
interest rate rises, then any investor who is happy bought some gold stock.
10. Consider the following axioms:
 Every child loves every candy.
 Anyone who loves some candy is not a nutrition fanatic.
 Anyone who eats any pumpkin is a nutrition fanatic.
 Anyone who buys any pumpkin either carves it or eats it.
 John buys a pumpkin.
 Lifesavers is a candy.
 (Conclusion) If John is a child, then John carves some pumpkin.
11. Consider the following axioms:
 Every tree that is an oak contains some grackle.
 If anyone walks under any tree that contains any grackle,
then he hates every grackle.
 For every building, there is some tree that is beside it.
 Taylor Hall is a building.
 Every CS student visits Taylor Hall.
 If anyone visits any building, then he walks under every tree
that is beside that building.
 (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:
 Every child sees some witch.
 No witch has both a black cat and a pointed hat.
 Every witch is good or bad.
 Every child who sees any good witch gets candy.
 Every witch that is bad has a black cat.
 (Conclusion) If every witch that is seen by any child has a pointed hat,
then every child gets candy.
13. Consider the following axioms:
 Every boy or girl is a child.
 Every child gets a doll or a train or a lump of coal.
 No boy gets any doll.
 No child who is good gets any lump of coal.
 (Conclusion) If no child gets a train, then no boy is good.
14. Consider the following axioms:
 Every child who finds some [thing that is an] egg or chocolate
bunny is happy.
 Every child who is helped finds some egg.
 Every child who is not young or who tries hard finds some
chocolate bunny.
 (Conclusion) If every young child tries hard or is helped, then
every child is happy.
15. Consider the following axioms:
 Anything that is played by any student is tennis, soccer, or chess.
 Anything that is chess is not vigorous.
 Anyone who is healthy plays something that is vigorous.
 Anyone who plays any chess does not play any soccer.
 (Conclusion) If every student is healthy, then every student
who plays any chess plays some tennis.
16. Consider the following axioms:
 Every student who makes good grades is brilliant or studies.
 Every student who is a CS major has some roommate.
[Make ``roommate'' a twoplace predicate.]
 Every student who has any roommate who likes to party
goes to Sixth Street.
 Anyone who goes to Sixth Street does not study.
 (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:
 Everyone who aces any final exam studies or is brilliant or is lucky.
 Everyone who makes an A aces some final exam.
 No CS major is lucky.
 Anyone who drinks beer does not study.
 (Conclusion) If every CS major makes an A, then every CS major
who drinks beer is brilliant.
18. Consider the following axioms:
 Anyone who loves any lottery is a gambler.
 Everyone who favors the lottery proposition loves some lottery.
 Everyone favors the lottery proposition or opposes the lottery
proposition.
 If every Baptist votes and opposes the lottery proposition, then
the lottery proposition does not win.
 Every Baptist who is faithful is not a gambler.
 (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.
 Anyone who owns any sled is happy when it is snowy.
 When it is white, it is snowy.
 If Santa is happy at Christmas, then every child who is good
gets some toy at Christmas.
 Any child who gets a toy at any time is happy at that time.
 Santa owns a sled.
 (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.
 Anyone who is on Sixth Street and is not a police officer has some
costume.
 No CS student is a police officer.
 Every costume that is good is a robot costume.
 For anyone, if they are on Sixth Street and are happy, then every
costume they have is good or they are drunk.
 (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.
 For every mall, there is some Santa who is at the mall.
 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.]
 Every child who is a city child visits some mall.
 Every child who is good or who talks with some Santa gets some toy.
 (Conclusion) If every child who is not a city child is good,
then every child gets some toy.
22. Consider the following axioms.
 Everyone who feels warm either is drunk, or every costume they
have is warm.
 Every costume that is warm is furry.
 Every AI student is a CS student.
 Every AI student has some robot costume.
 No robot costume is furry.
 (Conclusion) If every CS student feels warm, then every AI
student is drunk.
23. Consider the following axioms.
 Every bird sleeps in some tree.
 Every loon is a bird, and every loon is aquatic.
 Every tree in which any aquatic bird sleeps is beside some lake.
 Anything that sleeps in anything that is beside any lake eats fish.
 (Conclusion) Every loon eats fish.
24.``Schubert's Steamroller'', for the ambitious. (See C. Walther,
AAAI84, 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 graineating animal.
Solutions to Selected Problems
Gordon S. Novak Jr.