Duplicate Solutions.

The definition of aunts and uncles is slightly more difficult than grand-parents. A sibling of a parent is an aunt or an uncle. Two sibling have the same parents. The spouse of an aunt or uncle is also an aunt or uncle. If naively coded in Prolog, this rule allows infinite loops - an aunt is married to an uncle is married to an aunt is married to ... . A solution is to distinguish between the direct relation and the relation by marriage.

parents(william, diana,     charles).
parents(henry,   diana,     charles).
parents(charles, elizabeth, philip).
parents(diana,   frances,   edward).

parents(anne,    elizabeth, philip).
parents(andrew,  elizabeth, philip).
parents(edwardW, elizabeth, philip).

married(diana,   charles).
married(elizabeth, philip).
married(frances, edward).
married(anne,    mark).

parent(C,M) <= parents(C,M,D).
parent(C,D) <= parents(C,M,D).

sibling(X,Y) <= parents(X,M,D)
            and parents(Y,M,D). {NB. sibling(X, X)}

aORuDirect(C, A) <= parent(C,P) and sibling(P,A).
aORuMarr(C, A)   <= aORuDirect(C,X) and married(X,A).
aORuMarr(C, A)   <= aORuDirect(C,X) and married(A,X).
aORu(C,A)        <= aORuDirect(C,A).
aORu(C,A)        <= aORuMarr(C,A).

? aORu(william, A).

{\fB The Aunt/Uncle Relation. \fP}

When the program is run it produces the following answers.

aORu(william, diana) yes
aORu(william, charles) yes
aORu(william, anne) yes
aORu(william, andrew) yes
aORu(william, edwardW) yes
aORu(william, charles) yes
aORu(william, mark) yes
aORu(william, diana) yes

 --- William's Supposed Aunts and Uncles. --- 

Note that this includes the correct aunts and uncles - Andrew, Anne, Edward (Windsor) and Mark - but also includes Charles and Diana twice. The reason is that an individual is considered to be his or her own sibling (same parents). This makes Diana a direct aunt and Charles a direct uncle. Diana is married to Charles and therefore is also an aunt by marriage and Charles is similarly an uncle by marriage. The way to cure this problem is to state negative information; siblings must differ.

equal(X, X).
sibling(X, Y) <= parents(X, M, D) and parents(Y, M, D) and not equal(X, Y).

 --- Use of Negative Information. --- 

   ? sibling(X, Y).

part output:
   sibling(william, henry) yes
   sibling(henry, william) yes
   sibling(charles, anne) yes
   sibling(charles, andrew) yes

 --- Siblings. --- 

Negation (not) can be implemented using the negation by failure rule which attempts to prove `not equal(charles, charles' by proving `equal(charles, charles)'. The latter succeeds and so `not equal(charles, charles)' fails or is considered false. In general, `not p(...)' succeeds or is considered true if and only if `p(...)' fails. For example, `equal(charles, edwardW)' fails and so `not equal(charles, edwardW)' succeeds.

aORu(william, anne) yes
aORu(william, andrew) yes
aORu(william, edwardW) yes
aORu(william, mark) yes

 --- William's Genuine Aunts and Uncles. --- 

Negation by failure is not guaranteed to behave correctly if there is an unbound variable in the negated atom. In particular, if the negated atom appeared immediately after the `<=' in the improved rule for sibling then the rule would not work correctly.

sibling (X, Y) <= not equal(X, Y) and parents(X, M, D) and parents(Y, M, D).

 --- Rule unsuitable for (simple) negation by failure. --- 

With this rule and assuming that X and Y are unbound, it is possible to satisfy `equal(X,Y)' by binding X to Y and therfore the `not equal(X,Y)' and the rule fail in Prolog. From the logic point of view, there are many ways for `not equal(X,Y)' to succeed, for example with X bound to `william' and Y bound to `plus(fred,7)'. Only when X and Y are bound to constant or ground terms is negation by failure guaranteed to work correctly. Note that some Prolog interpreters delay any negated atom that contains an unbound variable to cure this problem.

[Previous Page] [Next Page] [Index] © L. Allison, Dept. Computer Science, Monash University