(OPTIONAL) PROGRAMMING PROJECT #3

Ontology for a Knowledge Base

For this project, you will define an ontology for genealogy: children, siblings, parents, grandparents, cousins, etc., and, given a knowledge base containing facts that can be expressed using this ontology, you will answer questions about the knowledge base. (This project is adapted from Russell & Norvig.)

You may do this project either in SNePS or else in FOL. If you choose SNePS, you must use the computer and our SNePS implementation, turning in a demo file. If you choose FOL, you may do the project just using "paper and pencil" (well, actually just using a word-processor!). However, there are a couple of implementations of FOL theorem-provers that you could use if you wish, and there's even a different version of SNePS that you could use! (See below.)

1. Below are informal definitions of several predicates. (The definitions are adapted from the Collins COBUILD dictionary for speakers of English as a second language.)

   Write formal definitions of these predicates in your chosen KR language. Be sure to give the syntax and semantics of all non-logical expressions (primarily terms and predicates).

   Here's an example: "Your sibling is your brother or sister" can be represented in FOL as follows:

   AxAy[Sibling(x,y) <-> Az[Parent(z,x) <-> Parent(z, y)]]

   (I.e., for all x and for all y: x and y are siblings iff, for all z: z is a parent of x iff z is a parent of y.)

   Syntax	Semantics
   Sibling(x,y)	x and y are siblings
   Parent(x,y)	x is a parent of y

   It can be represented in SNePS as follows:

   (assert forall ($x $y)
           thresh 1
           arg (build rel Sibling object (*x *y))
   	arg (build forall $z
                      thresh 1
                      arg (build rel Parent object1 *z object2 *x)
                      arg (build rel Parent object1 *z object2 *y)))
   

   (Note: For the syntax and semantics of the "thresh" relation in SNePS, see the SNePS User Manual.

   (You would, of course, also need to provide the syntax and semantics of any new case frames that you introduce.)

   And it can be represented in SNePSLOG (see below) as follows:

   all(x,y)(Sibling({x,y}) <=> all(z)(Parent(z,x) <=> Parent(z,y)))
   

   (Here, you could use the same kind of syntax and semantics as for FOL, since there are no (usable) case frames in SNePSLOG!)

   Now, here are the informal definitions that you must represent in your chosen KR language:

   • Your grandchild is a child of your child.
   • Your great-grandparent is a parent of your grandparent.
   • Your brother is a male who has the same parents as you.
   • Your sister is a female who has the same parents as you.
   • Your daughter is your female child.
   • Your son is your male child.
   • Your aunt is the sister of your parent, or the wife of your uncle.
   • Your uncle is the brother of your parent, or the husband of your aunt.
   • Your brother-in-law is the brother of your spouse, or the husband of your sister or of your spouse's sister.
     • Note: some people restrict this to: the brother of your spouse or the husband of your sister, but we'll use the more complex definition :-)
   • Your sister-in-law is the sister of your spouse, or the wife of your brother or of your spouse's brother.
   • Your first cousin is the child of your uncle or aunt.

   Here are some other hints: You might find it useful to decide which relations are "primitive" (i.e., which ones are "given" and cannot be defined in terms of any others) and then define the rest in terms of these (otherwise, you'll risk having circular definitions). Here is a suggested set of primitives (you may need others):

   [[Female(x)]] = x is female
   [[Male(x)]] = x is male
   [[Child(x,y)]] = x is a child of y
   [[Parent(x,y)]] = x is a parent of y
   [[Spouse(x,y)]] = x and y are spouses (i.e., x and y are married to each other)
   

2. Next, consider the following portion of the British royal family tree:
   

   Here is the syntax and semantics for understanding this tree:

   [[George]] = King George
   [[Mum]] = the Queen Mother
   [[Spencer]] = Lord Spencer
   [[Kydd]] = Kydd, Spencer's wife
   [[Elizabeth]] = Queen Elizabeth II
   [[Philip]] = Prince Philip
   [[Margaret]] = Princess Margaret
   [[Diana]] = Princess "Di"
   [[Charles]] = Charles, Prince of Wales
   [[Anne]] = Princess Anne
   [[Mark]] = Mark, whose title I don't know
   [[Andrew]] = Prince Andrew
   [[Sarah]] = "Fergie"
   [[Edward]] = Prince Edward
   [[William]] = Prince William, "the heir"
   [[Harry]] = Prince Harry, "the spare"
   [[Peter]] = Prince(?) Peter
   [[Zara]] = Princess(?) Zara
   [[Beatrice]] = Princess(?) Beatrice
   [[Eugenie]] = Princess(?) Eugenie
   [[x = y]] = [[x]] is married to [[y]]
   [["x = y" -> z]] = z is a child of x and y.

   Now, represent the basic facts depicted in this family tree in your chosen KR language.

3. Based on all this knowledge, answer the following questions:
   • Who are Elizabeth's grandchildren?
   • Who are Diana's brothers-in-law?
   • Who are Zara's great-grandparents?

   (a) If you are working in SNePS or SNePSLOG, input all the wffs you have represented, and let SNIP answer these questions.

   (b) If you are working in FOL, use Resolution (together with the clause-form algorithm, the refutation strategy, and the unification algorithm) to answer these questions.

1. One is the "tell/ask" feature of Russell & Norvig's software; instructions for using it (and an example of its use) were included in "HW 4 Answers & Grading Scheme"

2. The other is Prof. Shapiro's resolution theorem prover. (Also take a look at his "Foundations of Logic & Inference website).

Finally, for those of you using SNePS, you might want to consider using instead SNePSLOG: a logic-oriented version of SNePS, which has its own "tell/ask" interface. Briefly, in SNePSLOG, you enter information in a variety of FOL, but use SNIP to handle inference! To run SNePSLOG, just type (snepslog) instead of (sneps) at the Lisp prompt after loading SNePS. For more information on SNePSLOG, see the SNePS [2.5] User Manual, especially the sections on SNePSLOG and on "The Tell-Ask Interface".

Extra Credit:

• Actually, this is so complex that I might very well have erred in my computation of its definition; if so, please post a correction to the newsgroup!:-)

• In addition, the predicates defined above may not suffice: You may need to define other predicates (e.g., "great-grandparent", "great-great-grandparent", etc.).

• First, note that x and y are first cousins iff one of x's grandparents = one of y's grandparents.
  • This is a theorem that should follow from your definition of "grandparent" (above) plus the definition of "first cousin" given above.

  • "mth cousins" are at the same "generational level", namely, the mth level:

• x and y are 2nd cousins iff one of x's great-grandparents = one of y's great-grandparents.
  Note: From here on, I will use numerals as follows: "2-great-grandparent" for: great-great-grandparent, "4-great-grandparent" for: great-great-great-great-grandparent, and, in general, "n-great-grandparent" for: great-...-great (n times) grandparent.

• x and y are 3rd cousins iff one of x's 2-great-grandparents = one of y's 2-great-grandparents.

• x and y are mth cousins iff one of x's (m-1)-great-grandparents = one of y's (m-1)-great-grandparents.
  Note: Now we start a new series:

• x and y are 1st cousins, once removed iff one of x's grandparents = one of y's great-grandparents.
  • I.e., the "removed" part indicates how many "levels" you have to move the lower-generation person "up" to be at the same generational "level" as the higher-generation person, and the "cousin" part indicates which generational level that is.

• x and y are 1st cousins, twice removed iff one of x's grandparents = one of y's 2-great-grandparents.

• x and y are 1st cousins, n times removed iff one of x's grandparents = one of y's n-great-grandparents.
  Note: Now we put them together:

• x and y are mth cousins, once removed iff one of x's (m-1)-great-grandparents = one of y's m-great-grandparents.

• x and y are mth cousins, twice removed iff one of x's (m-1)-great-grandparents = one of y's (m+1)-great-grandparents.
  Note: And here's what you have to define formally:

• x and y are mth cousins, n times removed iff one of x's (m-1)-great-grandparents = one of y's (m+n-1)-great-grandparents.

  Hint: You might find it easier to try to define the predicate "MthCousin", where [[MthCousin(m,x,y)]] = x and y are mth cousins. And you might find it fun to try to define it recursively! Hint: We don't talk about "0th cousins", but we do have more familiar expressions for that relation; what are they? Then you could try to define the predicate "MthCousinNtimesRemoved", where [[MthCousinNtimesRemoved(m,n,x,y)]] = x and y are mth cousins, n times removed. Define this recursively, too, in terms of "MthCousin". Hint: What might "0th cousins, once removed" be?

As usual, you should turn in a conference-paper-style report (or a report in the style of a section of Brachman & Levesque) discussing what you did, giving the full syntax and semantics of your representations, and providing annotated demos and commented code. Any software you use that you did not write should be fully and correctly cited.

This project is optional in the following sense: You do not have to do it. If, however, you choose to do it, then I will compute your overall project grade by dropping the lowest of the 3 project grades and averaging the remaining 2. If this does not improve your overall project grade (e.g., because your grade on this optional project is lower than your other two project grades), then I will raise that average to the next highest letter grade (e.g., B+ would become A-). So, you can't lose by doing this project. However, only a complete Project 3 is eligible for this treatment; incomplete projects will not be considered.