序言:模拟析取事实 [英] Prolog: simulate disjunctive facts

问题描述

我有一个逻辑问题要解决，所以我想:我知道，我会尝试Prolog！"

不幸的是，我几乎立即遇到了砖墙.所涉及的假设之一是析取事实. A，B或C是正确的(或不止一个)，但我不知道哪个.从那以后，我了解到这是 Prolog不支持的内容.

那里有很多文档可以解决这个问题，但是大多数文档似乎立即涉及到更复杂的概念并解决了更高级的问题.我正在寻找的是一种模拟定义上述事实的孤立方法(由于Prolog的限制，无法立即定义它).

我该如何解决?我可以以某种方式将其包装起来吗?

编辑:我知道我不太清楚.由于我不熟悉Prolog，因此我不想在传达问题时陷入语法错误，而是选择自然语言.我想那还没有解决，所以无论如何我还是会用伪序言给它打个针.

直觉上，我想做的就是这样，声明foo(a)，foo(b)或foo(c)成立，但我不知道哪个:

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

然后我会期望得到以下结果:

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

不幸的是，我要声明的事实(即至少一个x \in {a, b, c}保持foo(x))不能这样定义.具体来说，结果为No permission to modify static procedure '(;)/2'.

旁注:在声明了析取事实之后，从逻辑上看，?- foo(a).的结果对我来说还是不清楚的；它显然不是true，但是false也不覆盖它-在这种情况下，Prolog根本没有足够的信息来回答该查询.

这里有更多的上下文可以使它更像一个真实的场景，因为我可能在翻译中过分简化和遗漏了细节.

说有三个人参与.爱丽丝，鲍勃和查理.鲍勃在集合{1, 2, 3, 4}中持有两张牌.爱丽丝问他一些问题，为此他向她出示了一张查理看不到的卡片，或者没有出示卡片.如果有更多卡可用，Bob只会显示其中一张.查理的任务是学习鲍勃持有的卡.如人们所料，查理是一个自动化系统.

爱丽丝问鲍勃你有1还是2?"，作为回应，鲍勃向爱丽丝出示了一张卡片.查理现在得知鲍勃拥有1或2.

然后，爱丽丝问你有2还是3"，鲍勃没有可显示的卡片.显然，鲍勃有一个1，他以前曾向爱丽丝展示过.查理现在应该能够基于这两个事实得出这一结论.

我要建模的知识是，鲍勃拥有1或2(own(Bob, 1) \/ own(Bob, 2))，而鲍勃不拥有2或3(not (own(Bob, 2) \/ own(Bob, 3))).现在查询Bob是否拥有1应该是true；查理可以得出这个结论.

解决方案

您问题的直接答案:

如果您可以使用有限域上的约束逻辑编程来对问题进行建模，那么可以使用#\来实现异或"，如下所示:

在三个变量X，Y，Z中，只有一个可以位于域1..3.中.

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

要对此进行概括，可以编写:

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

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

并将其用作:

?- 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))).

例如，如果您不使用CLP(FD)，则无法在问题和整数之间找到良好的映射，则可以执行其他操作.假设您的变量在列表List中，并且其中任何一个(但只有一个)可以是foo，其余的不能是foo，您可以说:

?- 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.

查询显示:在列表[A,B,C]中，变量之一可以是foo，然后其余变量必须与foo不同.您可以看到该查询的三种可能的解决方案.

原始答案

可悲的是，经常有人声称Prolog不支持一件事或另一件事.通常，这是不正确的.

您的问题目前尚不十分清楚，但是您的意思是，使用此程序:

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

您对查询获得以下答案:

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

您可能将其解释为:

foo(a)是true，和 foo(b)是true，和 foo(c)是true.

但是，如果我理解您的问题，则需要一条规则，例如:

与foo(a)，foo(b)和foo(c)完全相同的是正确的.

但是，根据上下文，程序的其余部分和查询的不同，原始解决方案可能恰好意味着这一点！

但是您确实需要在问题中更加具体，因为解决方案将取决于此.

问题编辑后进行编辑

这是对问题的一种解决方案，它使用具有 library(clpfd)，作者:Markus Triska ，可在SWI-Prolog中找到.

这是完整的代码:

:- 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).

和两个示例查询:

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

如果卡片组为{1,2,3,4}，而Bob持有两张卡片，当爱丽丝问您有1或2"时，他说是"，而当她问做"时，您有2或3"，他说不，然后:查理可以知道鲍勃是否持有1吗?

答案是:

是的，如果Bob持有1，则另一张卡为4；否则，则为4.没有其他可能的解决方案.

或者:

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

与上述相同，查理可以知道鲍勃是否持有3分吗?

查理肯定知道鲍勃没有拿着三分！

这是什么意思?

:- use_module(library(clpfd)).

使库可用.

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

这定义了我们可以从顶层查询的规则.第一个参数必须是有效域:在您的情况下，1..4将指出卡片在集合{1,2,3,4}中.第二个参数是变量列表，每个变量代表Bob持有的一张牌.最后是问题"和答案"的列表，它们的格式分别为Domain-Answer，因此1\/2-yes的意思是对于问题，您持有1或2，答案为是"."

然后，我们说Bob持有的所有卡都是不同的，并且每个卡都是其中的一组，然后我们将每个问答对映射到这些卡上.

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).

否"的答案很容易:只要说鲍勃持有的每张卡，在提供的域#\ V in D中就不是.

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

回答是"表示我们需要Bob持有的所有卡片的独占或全部； 2\/3-yes的结果应为第一张卡是2或3，或者第二张卡是2或3，但不能同时！"

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

要了解最后一个，请尝试:

?- 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))).

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.

解决方案

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))).

这篇关于序言:模拟析取事实的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！