Prolog: simulate disjunctive facts

Question

I've got a logic problem that I'd like to solve, so I thought, "I know, I'll try Prolog!"

Unfortunately, I'm running into a brick wall almost immediately. One of the assumptions involved is a disjunctive fact; either A, B or C is true (or more than one), but I do not know which. I've since learned that this is something Prolog does not support.

There's a lot of documentation out there that seems to address the subject, but most of it seems to immediately involve more intricate concepts and solves more advanced problems. What I'm looking for is an isolated way to simulate defining the above fact (as defining it straight away is, by limitations of Prolog, not possible).

How could I address this? Can I wrap it in a rule somehow?

EDIT: I realise I have not been very clear. Given my lack of familiarity with Prolog, I did not want to get caught up in a syntax error when trying to convey the problem, and instead went with natural language. I guess that did not work out, so I'll give it a shot in pseudo-Prolog anyway.

Intuitively, what I would want to do would be something like this, to declare that either foo(a), foo(b) or foo(c) holds, but I do not know which:

foo(a); foo(b); foo(c).

Then I would expect the following result:

?- foo(a); foo(b); foo(c).
true

Unfortunately, the fact I'm trying to declare (namely foo(x) holds for at least one x \in {a, b, c}) cannot be defined as such. Specifically, it results in No permission to modify static procedure '(;)/2'.

Side-note: after declaring the disjunctive fact, the result of ?- foo(a). would be a bit unclear to me from a logical perspective; it is clearly not true, but false does not cover it either -- Prolog simply does not have sufficient information to answer that query in this case.

EDIT 2: Here's more context to make it more of a real-world scenario, as I might have over-simplified and lost details in translation.

Say there are three people involved. Alice, Bob and Charlie. Bob holds two cards out of the set {1, 2, 3, 4}. Alice asks him questions, in response to which he shows her one card that Charlie does not see, or shows no cards. In case more cards are applicable, Bob shows just one of them. Charlie's task is to learn what cards Bob is holding. As one might expect, Charlie is an automated system.

Alice asks Bob "Do you have a 1 or a 2?", in response to which Bob shows Alice a card. Charlie now learns that Bob owns a 1 or a 2.

Alice then asks "Do you have a 2 or a 3", to which Bob has no cards to show. Clearly, Bob had a 1, which he showed Alice previously. Charlie should now be able to derive this, based on these two facts.

What I'm trying to model is the knowledge that Bob owns a 1 or a 2 (own(Bob, 1) \/ own(Bob, 2)), and that Bob does not own a 2 or a 3 (not (own(Bob, 2) \/ own(Bob, 3))). Querying if Bob owns a 1 should now be true; Charlie can derive this.

Answer 1

The straight-forward answer to your question:

if you can model your problem with constraint logic programming over finite domains, then, an "exclusive or" can be implemented using #\ as follows:

Of the three variables X, Y, Z, exactly one can be in the domain 1..3.

D = 1..3, X in D #\ Y in D #\ Z in D

To generalize this, you can write:

disj(D, V, V in D #\ Rest, Rest).

vars_domain_disj([V|Vs], D, Disj) :-
    foldl(disj(D), Vs, Disj, V in D #\ Disj).

and use it as:

?- vars_domain_disj([X,Y,Z], 2 \/ 4 \/ 42, D).
D = (Y in 2\/4\/42#\ (Z in 2\/4\/42#\ (X in 2\/4\/42#\D))).

If you don't use CLP(FD), for example you can't find a nice mapping between your problem and integers, you can do something else. Say your variables are in a list List, and any of them, but exactly one, can be foo, and the rest cannot be foo, you can say:

?- select(foo, [A,B,C], Rest), maplist(dif(foo), Rest).
A = foo,
Rest = [B, C],
dif(B, foo),
dif(C, foo) ;
B = foo,
Rest = [A, C],
dif(A, foo),
dif(C, foo) ;
C = foo,
Rest = [A, B],
dif(A, foo),
dif(B, foo) ;
false.

The query reads: in the list [A,B,C], one of the variables can be foo, then the rest must be different from foo. You can see the three possible solutions to that query.

Original answer

It is, sadly, often claimed that Prolog does not support one thing or another; usually, this is not true.

Your question is not exactly clear at the moment, but say you mean that, with this program:

foo(a).
foo(b).
foo(c).

You get the following answer to the query:

?- foo(X).
X = a ;
X = b ;
X = c.

Which you probably interpreted as:

foo(a) is true, and foo(b) is true, and foo(c) is true.

But, if I understand your question, you want a rule which says, for example:

exactly one of foo(a), foo(b), and foo(c) can be true.

However, depending on the context, that it, the rest of your program and your query, the original solution can mean exactly that!

But you really need to be more specific in your question, because the solution will depend on it.

Edit after edited question

Here is a solution to that particular problem using constraint programming over finite domains with the great library(clpfd) by Markus Triska, available in SWI-Prolog.

Here is the full code:

:- use_module(library(clpfd)).

cards(Domain, Holds, QAs) :-
    all_distinct(Holds),
    Holds ins Domain,
    maplist(qa_constraint(Holds), QAs).

qa_constraint(Vs, D-no) :-
    maplist(not_in(D), Vs).
qa_constraint([V|Vs], D-yes) :-
    foldl(disj(D), Vs, Disj, V in D #\ Disj).

not_in(D, V) :- #\ V in D.

disj(D, V, V in D #\ Rest, Rest).

And two example queries:

?- cards(1..4, [X,Y], [1 \/ 2 - yes, 2 \/ 3 - no]), X #= 1.
X = 1,
Y = 4 ;
false.

If the set of cards is {1,2,3,4}, and Bob is holding two cards, and when Alice asked "do you have 1 or 2" he said "yes", and when she asked "do you have 2 or 3" he said no, then: can Charlie know if Bob is holding a 1?

To which the answer is:

Yes, and if Bob is holding a 1, the other card is 4; there are no further possible solutions.

Or:

?- cards(1..4, [X,Y], [1 \/ 2 - yes, 2 \/ 3 - no]), X #= 3.
false.

Same as above, can Charlie know if Bob is holding a 3?

Charlie knows for sure that Bob is not holding a three!

What does it all mean?

:- use_module(library(clpfd)).

Makes the library available.

cards(Domain, Holds, QAs) :-
    all_distinct(Holds),
    Holds ins Domain,
    maplist(qa_constraint(Holds), QAs).

This defines the rule we can query from the top level. The first argument must be a valid domain: in your case, it will be 1..4 that states that cards are in the set {1,2,3,4}. The second argument is a list of variables, each representing one of the cards that Bob is holding. The last is a list of "questions" and "answers", each in the format Domain-Answer, so that 1\/2-yes means "To the question, do you hold 1 or 2, the answer is 'yes'".

Then, we say that all cards that Bob holds are distinct, and each of them is one of the set, and then we map each of the question-answer pairs to the cards.

qa_constraint(Vs, D-no) :-
    maplist(not_in(D), Vs).
qa_constraint([V|Vs], D-yes) :-
    foldl(disj(D), Vs, Disj, V in D #\ Disj).

The "no" answer is easy: just say that for each of the cards Bob is holding, it is not in the provided domain: #\ V in D.

not_in(D, V) :- #\ V in D.

The "yes" answer means that we need an exclusive or for all cards Bob is holding; 2\/3-yes should result in "Either the first card is 2 or 3, or the second card is 2 or 3, but not both!"

disj(D, V, V in D #\ Rest, Rest).

To understand the last one, try:

?- foldl(disj(2\/3), [A,B], Rest, C in 2\/3 #\ Rest).
Rest = (A in 2\/3#\ (B in 2\/3#\ (C in 2\/3#\Rest))).

Answer 2

A generate-and-test solution in vanilla Prolog:

 card(1). card(2). card(3). card(4).

 owns(bob, oneof, [1,2]).  % i.e., at least one of

 owns(bob, not, 2).

 owns(bob, not, 3).

 hand(bob, Hand) :-
   % bob has two distinct cards:
   card(X), card(Y), X < Y, Hand = [X, Y],
   % if there is a "oneof" constraint, check it:
   (owns(bob, oneof, S) -> (member(A,S), member(A, Hand)) ; true),
   % check all the "not" constraints:
   ((owns(bob, not, Card), member(Card,Hand)) -> false; true).

Transcript using the above:

$ swipl
['disjunctions.pl'].
% disjunctions.pl compiled 0.00 sec, 9 clauses
true.

?- hand(bob,Hand).
Hand = [1, 4] ;
;
false.

Note that Prolog is Turing complete, so generally speaking, when someone says "it can't be done in Prolog" they usually mean something like "it involves some extra work".

Answer 3

Just for the sake of it, here is a small program:

card(1). card(2). card(3). card(4). % and so on

holds_some_of([1,2]). % and so on

holds_none_of([2,3]). % and so on

holds_card(C) :-
    card(C),
    holds_none_of(Ns),
    \+ member(C, Ns).

I have omitted who owns what and such. I have not normalized holds_some_of/1 and holds_none_of/1 on purpose.

This is actually enough for the following queries:

?- holds_card(X).
X = 1 ;
X = 4.

?- holds_card(1).
true.

?- holds_card(2).
false.

?- holds_card(3).
false.

?- holds_card(4).
true.

which comes to show that you don't even need the knowledge that Bob is holding 1 or 2. By the way, while trying to code this, I noticed the following ambiguity, from the original problem statement:

Alice asks Bob "Do you have a 1 or a 2?", in response to which Bob shows Alice a card. Charlie now learns that Bob owns a 1 or a 2.

Does that now mean that Bob has exactly one of 1 and 2, or that he could be holding either one or both of the cards?

PS

The small program above can actually be reduced to the following query:

?- member(C, [1,2,3,4]), \+ member(C, [2,3]).
C = 1 ;
C = 4.