complete vs incomplete knowledge (was basic question from Tjitze Rienstra)

Hi,

Suppose you have a database

fact(john,mary).
fact(peter,martha).

and you want to express (derive) that also

fact(mary,john).
fact(matha,peter).

hold, then adding the following rule is insufficient, even incorrect:

fact(A,B) :- fact(B,A).

why?

You will obtain the program

fact(john,mary).
fact(peter,martha).
fact(A,B):-fact(B,A).

I will give you

a) as expected:

fact(john,mary)    --> yes
fact(peter,martha) --> yes
fact(mary,john)    --> yes (using rule 3 and then rule 1)
fact(martha,peter) --> yes (using rule 3 and then rule 2)

b) and as unexpected

an infinite loop.... (apply for ever the last rule)

More correct is the following definition:

fact_db(peter,martha).
fact_db(john,mary).

fact(A,B) :- fact_db(A,B).
fact(A,B) :- fact_db(B,A).


This still does not address the problem of you (in)completeness of
your database.
If you want to express that your knowledge the fact_db relation is
incomplete, you can''t do it in Prolog.
Prolog assumes that your knowledge about the world is fully complete.

For that reason, one has investigated other logics and reasoners.
To give you some hints:

*) abductive logic programming
This distinguishes between defined and abducible predicates. Abducible
predicates are predicates of which the user's knowledge is incomplete.

Such a program would look like this:

definied(fact(_,_)).
abducible(fact_db(_,_)).

fact_db(peter,martha).
fact_db(john,mary).

fact(A,B) :- fact_db(A,B).
fact(A,B) :- fact_db(B,A).

An abductive solver (e.g. the Asystem) will answer that apart from the
four fact instances, there might exists an instance

fact(sk1,sk2) provided that the instance fact_db(sk1,sk2) exists.

(sk1 and sk2 are two globally existentially quatified variables or
skolemconstants.)

*) Answer Set Programming
which is roughly stated Logic Programming under the Stable Model
semantics.

For this paradigm, one finds two related solvers sModels and DLV which
encode incompleteness in a slightly different manner.

sModels: by using negation

fact_db(X,Y) :- not fact_db_star(X,Y), rangex(X),rangey(Y).
fact_db_star(X,Y) :- not fact_db_star(X,Y), rangex(X),rangey(Y).

fact_db(peter,martha).
fact_db(john,mary).

The auxiliary predicates rangex and rangey are necessary in this
paradigm to limit the language to a finite number of symbols.

DLV: by using disjunction

fact_db(X,Y) v fact_db_star(X,Y) :- rangex(X),rangey(Y).

fact_db(peter,martha).
fact_db(john,mary).


More info on any of these systems, you find by googleing them ;-)

Bert