So let's start with a simple example. Let's say I have this set of people who are related:
Giuseppe Albina Ida GeorgeAlexandar
\ / \ /
\ / \ /
Estelle George
\ /
\ /
John
In this graph, I'm showing parents linked to children, where the
parents are the people higher up in the graph. There are a number
of ways we could represent the parent-child relationships in this
graph. For example, we could base it all on a single relation
parent(P,C), which could be read "P is the parent of C." Then
we could express the information in the graph as:
parent(giuseppe,estelle).
parent(albina,estelle).
parent(ida,george).
parent(georgeAlexandar,george).
parent(estelle,john).
parent(george,john).
We also know that every child has exactly two parents: one father
and one mother, the difference being that a mother is a female
parent and a father is a male parent. Thus we could first add
two predicates, male(Name) and female(Name) to
indicate gender:
male(giuseppe).
male(georgeAlexandar).
male(george).
male(john).
female(albina).
female(ida).
female(estelle).
At this point, let's say we want 2 predicates
mother(M,Child) and father(F,child). One way to do
it would be to enumerate each of these relationships specifically,
like so:
father(giuseppe,estelle).
father(georgeAlexandar,george).
father(george,john).
mother(albina,estelle).
mother(ida,george).
mother(estelle,john).
On the other hand, this is very inefficient, since we
already have all the information we need to determine mother
and father based on the parent, male, and
female relations. Basically, M is a mother of Child if M is a
parent of Child and M is female, or in Prolog:
mother(M,Child) :- parent(M,Child), female(M).
The father predicate can be defined smilarly:
father(F,Child) :- parent(F,Child), male(F).
Thus, with two simple rules, we've replaced the 6 facts above.
Think if this were a database of all of the children at a school
and their parents names; then we've replaced hundreds or thousands
of simple facts with two simple rules.
Now consider the childOf relationship. If P is the parent of C, then C is the child of P. This is easy enough in Prolog:
child(C,P) :- parent(P,C).
Now as an exercise, you can try to define predicates to express son and daughter using parent, male, and female. The solutions are here.
Now let's consider the sibling relationships. Someone is my brother if he is male and he has the same parents as me. Actually, I'm male, and I have the same parents as me, but I'm not my own brother. Thus I have to include something that indicates that the brother is not the same person as who they are a brother of. In Prolog, we would write this as:
brother(B,P) :- male(B),
mother(M,B),
mother(M,P),
father(F,B),
father(F,P),
B /= P.
/= is the way of expressing "not equal" in Prolog
You should be able to define sister easily, since the only
difference from brother is that she's female instead of male.
Ok, so how about grandparents. They're the parents of the
parents, or in other words:
grandparent(G,X) :- parent(P,X),
parent(G,P).
(version 1)
Note that the order of the predicates in the body could be
reversed, and Prolog would work just fine:
grandparent(G,X) :- parent(G,P),
parent(P,X).
(version 2)
The advantage of the first method lies in the fact that any person
only has two parents, but they may have many children. So let's
say one of my pairs of grandparents had 4 children, of which my
father was the youngest, and my other set of grandparents had 7
children, of which my mother was the youngest. Let's also say my
parents had 5 children, of which I'm the youngest. And finally,
let's say all the parent relationships are listed in chronological
order.:
parent(giuseppe,margaret).
parent(giuseppe,evelyn).
parent(giuseppe,robert).
parent(giuseppe,grace).
parent(giuseppe,fred).
parent(giuseppe,mary).
parent(giuseppe,estelle).
parent(albina,margaret).
parent(albina,evelyn).
parent(albina,robert).
parent(albina,grace).
parent(albina,fred).
parent(albina,mary).
parent(albina,estelle).
parent(ida,catherine).
parent(ida,juanita).
parent(ida,edythe).
parent(ida,george).
parent(johnMiddleton,catherine).
parent(georgeAlexandar,juanita).
parent(georgeAlexandar,edythe).
parent(georgeAlexandar,george).
parent(estelle,steve).
parent(estelle,judy).
parent(estelle,david).
parent(estelle,marilyn).
parent(estelle,john).
parent(george,steve).
parent(george,judy).
parent(george,david).
parent(george,marilyn).
parent(george,john).
Now let's say I want to find out my grandparents names. I would
give a query like this:
grandparent(G,john).
If I use version 2 of the grandparent predicate above,
Prolog will match my query to the head of the rule and bind G = G
and X = john. Then it will put the clauses of the body on the
goal stack, and try to solve parent(G,P) first. Since no variable
is bound, it'll match the fact parent(giuseppe,margaret). If I
had my aunt Margaret's children listed here, I'd then have to
search through them before it would fail and go back and reselect
parent(giuseppe,evelyn).
Thus, I'd have to search through all my aunts and uncles (and cousins if they were defined as well) before I'd ever get to my parents and me. On the other hand, if I use version 2, then I go directly to my parents, and then to their parents. As I pointed out in class, this is an excellent illustration of somewhere where backward chaining my search is an advantage over forward chaining.
But what if I try this query:
grandparent(giuseppe,X).
Here I'm trying to find the names of Giuseppe's grandchildren. In
this case version 2 will be more efficient than version
1, since it will avoid my grandparents on the other side.
What we can gain from this is that though all predicates in
Prolog are bi-directional (i.e. it doesn't distinguish inputs from
outputs), typically performance is much better in one direction
than the other. Thus if you want to search both ways, you might
be better off defining two functions which are direction specific.
In this case:
grandparent(G,X) :- parent(P,X),
parent(G,P).
grandchild(G,X) :- parent(G,P),
parent(P,X).
Note that my decision to represent the parent-child relationship
as a 2 argument predicate was an arbitrary decision. In fact,
every person has exactly two parents, so I could have chosen to
represent it as a 3 argument predicate like this:
parents(childname,fathername,mothername).
Here's the way some of the facts and rules might have come out if
I'd have made that choice:
male(john).
male(david).
male(steve).
male(george).
male(georgeA).
male(giuseppe).
male(robert).
male(fred).
male(moses).
male(jacques).
female(judy).
female(marilyn).
female(estelle).
female(evelyn).
female(margaret).
female(mary).
female(albina).
female(ida).
female(theresa).
female(therese).
female(susan).
parents(john,george,estelle).
parents(david,george,estelle).
parents(steve,george,estelle).
parents(marilyn,george,estelle).
parents(judy,george,estelle).
parents(george,georgeA,ida).
parents(georgeA,moses,theresa).
parents(moses,jacques,therese).
parents(estelle,giuseppe,albina).
parents(evelyn,giuseppe,albina).
parents(margaret,giuseppe,albina).
parents(fred,giuseppe,albina).
parents(robert,giuseppe,albina).
parents(mary,giuseppe,albina).
parents(susan,robert,inger).
sister(S,X) :- parents(S,F,M),
parents(X,F,M),
female(S),
S /= X.
parent(P,X) :- parents(X,P,_).
parent(P,X) :- parents(X,_,P).
aunt(A,X) :- parent(P,X),
sister(A,P).
grandparent(G,X) :- parent(G,P),
parent(P,X).
grandmother(GM,X) :- grandparent(GM,X), female(GM).
If you want to make sure you understand this stuff, try defining
some other familial relationships using either (or both) of these
representations. Try doing uncle, neice, nephew, and half-sister.
If you want to do a slightly harder one, try ancestor. Your
ancestor is anyone who you can get to just by following a parent
relationship (i.e. your parents, your parents' parents, your
parents' parents' parents, etc. are your ancestors).