CPSC 322 - Homework Assignment 1

Due by 6:00AM, Friday, September 24, 2004

Problem 1 (5 points):  Here's something just to get you warmed up.  
It's adapted from an exercise in your textbook.  Below is the knowledge 
base we presented in class for a very tiny part of the royal family 
tree (the whole tree can be seen in the figure for problem 2):

  parent(charles, william).
  parent(charles, harry).
  male(charles).
  male(william).
  male(harry).
  brother(A, B) <- male(A) & parent(C, A) & parent(C, B).

There are three individuals in D:

  D = {charles', william', and harry'} 

(The ' is the textbook's way of indicating that we're referring to the
real individuals here, not corresponding symbols in the RRS.)

There are also three constants -- charles, william, and harry -- and
three predicate symbols -- male, parent, and brother.

Now consider all the possible interpretations for this language of the
form I = (D, phi, pi).  (Sorry, I don't have my Greek symbols handy.)
How many interpretations exist for this language?  Justify your answer.
Hint:  Consider how many ways there are to map the constants onto the
elements of D (that's the phi function).  Then consider how many ways 
                                                   n
there are to map each n-ary predicate symbol from D  into {TRUE, FALSE}
(that's what the pi function does).  Please don't enumerate all the 
possible interpretations...just do the math.

---------------------------------------------------------------------------

Problem 2 (30 points):  Consider the following family tree diagram which 
we previously presented in class:

Using CILOG and a handy computer, construct a knowledge base of facts
and rules that represents the information contained in the diagram. 
At the very least, your knowledge base should include (i.e., there 
should be rules for) the following important relationships:

  parent, mother, father, grandparent, grandmother, grandfather,
  child, daughter, son, grandchild, granddaughter, grandson,
  aunt, uncle, firstcousin, sisterinlaw, brotherinlaw,
  descendant, ancestor

You may need additional information, but you should make sure that
your teaching assistants can easily find the above-named relationships
in your CILOG program.  Use the ASK feature in CILOG to test some of
these relationships, and include the test results when you submit
your homework.  Remember, not only are you trying to impress your teaching 
assistants with your skill and insight, but you also want to make the
marking (or grading, as we say in the States) process as easy as 
possible for them.  A happy TA is a generous TA.

---------------------------------------------------------------------------

Problem 3 (15 points):  Here's another problem that I borrowed from
elsewhere:

The following story is from N. Wirth's (1976) "Algorithms + data 
structures = programs".

"I married a widow (let's call her W) who has a grown-up daughter
(call her D).  My father (F), who visited us quite often, fell in 
love with my step-daughter and married her.  Hence, my father became
my son-in-law and my step-daughter became my mother.  Some months
later, my wife gave birth to a son (S1), who became the brother-in-law
of my father, as well as my uncle.  The wife of my father,  that is,
my step-daughter, also had a son (S2)."

Using CILOG, create a knowledge base that represents the situation in
the above story.  Add the necessary expressions defining basic family
relationships such as the definition of father-in-law, grandfather, and
so on.  (You may be able to reuse some of what you've done for problem
2 here.)  Once you think you have your knowledge base the way you want
it, use the ASK feature in CILOG to prove that "I am my own grandfather."
Hint:  The solution shouldn't involve a fact that looks something like
grandfather(me, me).