You should turn in a Prolog program, documented as described above, and a sample run showing the outcome of a good selection of test cases.
More generally, one could pick the names of any two movie actors (or directors or producers or whatever), and try to find how closely they are related to one another. Two actors who were in the same movie are one "degree" apart; two actors who were not in the same movie together, but they were each in a movie with the same other actor, are two "degrees" apart; and so on.
(If you're not interested in movies, you can do the same thing with rock bands, or even classes at Adelphi University.)
(This part of the assignment should be extremely easy; it doesn't require any actual programming, only coming up with examples.)
Test your examples by asking a variety of queries: some with both arguments bound, some with only the person bound (i.e. "list all the movies this person was in"), some with only the movie bound ("list all the people who were in this movie"), etc.
Test your definition by asking a variety of queries: some with both arguments bound ("are these two people related?"), some with one argument bound ("who is related to this person?"), etc. Check that there are no asymmetries, situations in which Joe is related to Mary but Mary isn't related to Joe.
For your first attempt, get this to work for degree 1, and then degrees 1 and 2. Once we've discussed arithmetic and recursion in Prolog, try to get it to work for any degree.
Test your definition by asking a variety of queries: some with all three arguments bound ("are these two people 2 degrees apart?"), some with both actors bound but the number unbound ("how far apart are these two people?"), some with one actor and the number bound ("who is one degree apart from this person?"), etc.
What happens when both actors in the query are the same? What happens when you ask Prolog for further answers after the first? What do you think should happen in these cases?