Can prolog answer undetermined instead of just yes or no?

Question

Suppose I have the knowledge base

likes(john,mary).
person(mary).
person(john).

If we ask prolog whether

|?- likes(mary,john)

It will answer no because we did not assert that. Is there any way to make prolog answer unknown unless we explicitly state.

\+ likes(mary,john)

In other words can we ask prolog to treat unbound expressions as possible rather than false. I've been using IDP system which permits existential quantification and treats non asserted relations as if unbound rather than false, but I would like to use something more mainstream. http://adams.cs.kuleuven.be/idp/server.html

For example in IDP you can make the statement

vocabulary V{
    type Person
    Likes(Person,Person)
}


theory T: V{

    //Everyone might like someone and disallow narcisiscm
    !x : ?y: Likes(x,y) & ~Likes(x,x).

}

//some instance without special meaning
structure S:V{
    Person={A..C}
}

procedure main(){
    //Print all possible solutions
    printmodels(allmodels(T,S))
}

Which yields

Number of models: 27
Model 1
=======
structure  : V {
  Person = { "A"; "B"; "C" }
  Likes = { "A","B"; "A","C"; "B","A"; "B","C"; "C","A"; "C","B" }
}
//...

Are you aware of [Closed-world assumption](https://en.wikipedia.org/wiki/Closed-world_assumption) vs. [Open-world assumption](https://en.wikipedia.org/wiki/Open-world_assumption) ? — Guy Coder, Mar 07 '17 at 18:50
Are you saying that prolog can only answer a closed system? Because I guess you could say I'm asking it can consider an open system, or it is limited in that respect and I should try a different language. — awiebe, Mar 07 '17 at 18:54
`likes(mary,john)` will succeed, because `mary` and `john` are persons. That's what your second clause says. — Willem Van Onsem, Mar 07 '17 at 18:55
I am not the expert here, but standard Prolog is a closed world as far as I know and use it. I have read of purposed extensions and research into Open-world system with Prolog but I have never worked with them and can not say more. Since there might be an add on package that changes how Prolog works that I am not aware of, I will wait for more knowledgeable people here to respond. — Guy Coder, Mar 07 '17 at 19:02
`person(X),person(Y) :-likes(X,Y).` isn't valid syntax. Not sure what you mean by it. — lurker, Mar 07 '17 at 19:16

score 3 · Accepted Answer · answered Mar 07 '17 at 20:46

3

As stated, Prolog is using the closed-world assumption, i.e. asking if a fact is true means that we ask if we know it's true - a no means that we don't know if it's true, not that it's false. Of course, being a Turing-complete language you can simulate an open world - something like:

like(true, mary, john).
like(false, mary, nick).
like(unknown, X, Y).

Probably best to have some extra wrappers to deal with edge cases (e.g. having both true and false for a pair), and possibly use some higher-order predicate trick to avoid writing lots of boilerplate - but the core of the implementation is that you explicitly declare what's false, what's true and the rest is unknown.

answered Mar 07 '17 at 20:46

Thanos Tintinidis

5,828
1
20
31

I think a more reasonable definition to catch the edge cases would be `like(unknown, X, Y):- \+like(true, X, Y),\+like(false, X, Y).` – awiebe Mar 07 '17 at 22:43
@awiebe yep, that clears it up - although there's still a chance of having `like(true, mary, john). like(false, mary, john)`, probably by accident. Generally, I find it easier to reason about it if there are separate predicates for "pure" data and the related logic – Thanos Tintinidis Mar 08 '17 at 19:41

score 1 · Answer 2 · answered Mar 07 '17 at 22:39

What has been said so far is quite right: Prolog operates under the so-called Closed World Assumption (CWA). Still, I would like to offer a complementary perspective in addition to what has been posted already.

First, a Prolog program may not even terminate, and so we may never receive either of the possible answers you mention.

But even if the program does terminate, we may still obtain answers that are neither equivalent to true nor to false.

For example, using GNU Prolog:

| ?- X #\= 3.

X = _#2(0..2:4..127@)

Here, the answer is a pending constraint, a goal that is said to flounder because its truth is not definitely decided.

Such answers may or may not describe solutions.

For example:

| ?- fd_all_different([X,Y,Z]), fd_domain([X,Y,Z], 0, 1).

X = _#2(0..1)
Y = _#20(0..1)
Z = _#50(0..1)

yes

In this case, no solutions exist! To see this, we need to explicitly search for them:

| ?- fd_all_different([X,Y,Z]), fd_domain([X,Y,Z], 0, 1),
     fd_labeling([X,Y,Z]).

no

Thus, in the example above, it may really be more advisable to answer with maybe instead of yes.

Moreover, we know from fundamental logical theorems that such issues are unavoidable when reasoning over integers.

In this sense, Prolog systems can really give answers whose truth not only isn't, but moreover cannot be determined.

Can prolog answer undetermined instead of just yes or no?

2 Answers2