1. Consider the following situation in the blocks world:

   

   Given the (separate) facts that:

   • A is on B
   • B is on C
   • The table supports C
   • For any two entities, if the first entity supports the second, then the second is on the first.
   • For any two entities, if the first entity is on the second, then the first is “above” the second.
   • For any three entities, if the first entity is above the second which is above the third, then the first is above the third.

   Write these facts in FOL and use resolution/unification to prove that A is above the table.

   If you find it easier to submit this on paper, then do that and we'll grade it along with the programs you submit online.

2. Write a recursive implementation of Euclid’s algorithm for computing the greatest common divisor (GCD) of two integers. This algorithm can be defined recursively as follows:

   

   Note that Prolog functions don't return values, so you'll need to write the gcd function with 3 parameters, the 2 values and the result to be returned. The function should work as follows:

   ?- gcd(2,2,X).
   X = 2 ;
   false.
   
   ?- gcd(10,5,X).
   X = 5 ;
   false.
   
   ?- gcd(21,28,X).
   X = 7 ;
   false.
   
   ?- gcd(7,13,X).
   X = 1 ;
   false.
   

3. For this exercise, load the program in potter.pl and familiarize yourself with its contents. Now, write Prolog questions that determine the answers to the following queries, writing Prolog rules as necessary to support your questions:

   1. Who are Narcissa Black’s siblings?
   2. Who are Cygnus Black’s parents?
   3. Who are Draco Malfoy’s aunts and/or uncles?
   4. Do Draco Malfoy and Sirius Black share an ancestor?

   We suggest creating functions for siblings/2 , parent/2 , auntOrUncle/2 , and ancestor/2 . Be sure to write the Prolog rules necessary to respond to general queries of these forms (i.e., “who are X’s siblings?”).

Final project suggestion: Consider addressing some interesting planning problem using GraphPlan (see Section 10.3).

Checking in

Submit the files specified above in Moodle under homework 12. We will grade your work according to the following criteria:

• 30% - Exercise 1 - Specify your facts and proof clearly.
• 30% - Exercise 2 - Build correct, efficient and understandable code that solves the given problem.
• 40% - Exercise 3 - Build correct, efficient and understandable code that solves the given problem.