First-Order Logic Homework

1. For each of the following pair of literals, give the most general unifier if it exists, or if none exists, explain why. See the definition MGU in the textbook, figure 9.1. We use the convention that variables are Capitalized (X,Y,Z) and constants are lowercase (a,b,c), which is like Prolog but the reverse of the convention in the textbook. Be careful about the scope of variables: variables with the same name that appear in different literals are not the same variable!

p(a,b,c) p(X,Y,Z)
p(a,b,X) p(X,b,Y)
q(Y,g(a,b)) q(g(X,X),Y)
older(father(Y),Y) older(father(X),john)
knows(father(Y),Y) knows(X,X)

2. Write a Prolog program that finds a solution to the following puzzle. Run your program to confrim that it works. You can download a good free version of Prolog from http://www.swi-prolog.org/.

The Mini Zebra Puzzle

  1. There are three houses in a row on street. Each house is inhabited by a man of a different nationality, who has a different pet, and drinks a different beverage.
  2. The Spaniard own a dog.
  3. The Ukranian drinks tea.
  4. The man in the third house drinks milk.
  5. The Norwegian lives next to the tea drinker.
  6. The juice drinker owns a fox.
  7. The fox is next door to the dog.

Question: Who owns the zebra? More generally, for each house: who lives there, what pet does he have, and what does he drink?

Notes: In Prolog, the atom "X=Y" is true if X and Y unify. The atom "X\=Y" is true if X and Y do not unifiy. One way to solve the puzzle is write a clause that guesses at a solution, and then verifies that it is correct. Think carefully about the predicates you will use. One approach is to use predicates that hold of houses, for example, dog(H) to mean that H is the house with the dog, and next(house1,house2) to mean that house1 is next to house2.

Following is the full version of the Zebra puzzle:

  1. There are five houses in a row on a street, each of a different color and inhabited by men of different nationalities, with different pets, drinks, and cigarettes.
  2. The Englishman lives in the red house.
  3. The Spaniard owns the dog.
  4. Coffee is drunk in the green house.
  5. The Ukrainian drinks tea.
  6. The green house is immediately to the right of the ivory house.
  7. The Old Gold smoker owns snails.
  8. Kools are smoked in the yellow house.
  9. Milk is drunk in the middle house.
  10. The Norwegian lives in the first house on the left.
  11. The man who smokes Chesterfields lives in the house next to the man with the fox.
  12. Kools are smoked in the house next to the house where the horse is kept.
  13. The Lucky Strike smoker drinks orange juice.
  14. The Japanese smoke Parliaments.
  15. The Norwegian lives next to the blue house.