Why is this prolog query both true and false?

Question

My SWI-Prolog knowledge base contains the following two facts:

f(a,b).
f(a,c).

Now if I pose the query

?- f(a,c).
true.

But

?- f(a,b).
true ;
false.

Why is f(a,b) both true and false? This also happens when there are three facts in the KB. If I append f(a,d). to the KB, then f(a,d) is true (only), but f(a,b) and f(a,c) are both true and false. What's going on, and what can I do so that Prolog answers (only) true to these queries?

Polytypic

Answer 1

(Note: this answer is somewhat of a guess)

Consider how Prolog determines whether f(a,c) is true or not. It checks the first rule, f(a,b), and doesn't find a match, but the second rule, f(a,c) matches. Therefore, f(a,c) is true. Furthermore, since there are no more rules for f, there is no point in allowing a backtrack to occur -- there are no other possible solutions.

Now consider f(a,b). Prolog will check the first rule, and find a match. Therefore, f(a,b) is true. However, not all rules have been exhausted. Therefore, Prolog will allow the search to continue (if you hit ;). When you do continue the search and backtrack, it will discover that the remaining rules, specifically f(a,c), do not match f(a,b). Therefore, the result is false.

Kohima

This answer is correct. In Prolog, the order in which your facts are rules are written determines the order they will be found by a query. More specifically, the 'backtrack' option ";" essentially tells forces the query engine to discard the returned result and answer the question "are there any other answers?". So, it is not that f(a,b) is both true and false; but rather that it is true and if you choose to ignore that result the engine will tell you there are no other f(a,b) fact entries. To prove this, watch what happens if you add a second f(a,b) fact. – Amylaceous

This is also illustrates why you should pay attention to the order of your arguments if you are concerned about performance. If the order of the arguments in predicate f was flipped, then this wouldn't have happened because the initial arguments are no longer the same, and so do not leave a choice point. This happens because most prologs perform argument indexing, which allows predicates with incompatible arguments to be pruned from the search-space in advance. SWI Prolog only indexes the first argument by default, but this can be changed. – Earthen

Answer 2

Just in addition to Michael Williamson's answer. If you want to tell Prolog to stop looking for answers after the first successful hit, then use the cut (!):

?- f(a, b), !.
true.

?- f(a, c), !.
true.

Mysterious