complete vs incomplete knowledge (was basic question from Tjitze Rienstra)
From: Bert Van Nuffelen (Bert.VanNuffelen+google_at_cs.kuleuven.ac.be)
Date: 10/05/04
- Next message: Carlo Capelli: "Re: http_open in swi-prolog"
- Previous message: Jan Wielemaker: "Re: http_open in swi-prolog"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: 5 Oct 2004 05:23:04 -0700
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
- Next message: Carlo Capelli: "Re: http_open in swi-prolog"
- Previous message: Jan Wielemaker: "Re: http_open in swi-prolog"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
|
