使用not设置Intersection谓词Prolog

Question

我正在尝试构建一个简单的谓词,它将两个列表作为输入,结果是由前两个列表的交集组成的第三个.我决定使用逻辑陈述.我很确定我的逻辑是正确的,但我的谓词不起作用.有任何想法吗？:

element(X,[H|T]) :- 
      X=H
   ;
      element(X,T).

intersection(L1,L2,R) :-
    not((
        element(A,L1),
        not(element(A,L2))
    )),
    not((
        element(A,L1),
        not(element(A,R))
    )).

请不要发布替代方法我想知道为什么每次都返回FALSE.

Answer 1

你的定义太正确了.它承认,例如,这[]是任何两个列表的交集过于笼统.即它错误地成功了intersection([],[a],[a]).它没有第三个"for all"成语,表明两个列表中的所有元素都将出现在结果列表中.

但是否则你的定义很好.对于地面案例.有点不寻常的是交叉点是第一个而不是最后一个参数.变量名称让我非常恼火.我认为这R意味着"结果",因此是交集.而L1与L2是两套打造的交集.

但它有点过于笼统 - 就像许多Prolog谓词一样(想想append([], non_list, non_list).除了列表,你的定义也承认既不是列表也不是部分列表的术语:

?- intersection(non_list1,[1,2|non_list2],[3,4|non_list3]).

为了使它真正有用,请使用它:

?- when(ground(intersection(I, A, B)), intersection(I, A, B)).

或者:

?- (  ground(intersection(I, A, B))
   -> intersection(I, A, B)
   ;  throw(error(instantiation_error, intersection(I, A, B)))
   ).

或者,使用iwhen/2:

?- iwhen(ground(intersection(I, A, B)), intersection(I, A, B) ).

作为一个小问题,而不是(\+)/1代替not/1.

Answer 2

问题是not/1只是否定了你的结果element/2.它不会导致element/2回溯以找到封闭not/1将为真的其他实例.

考虑以下程序.

a(1).
a(2).

b(1).
b(2).
b(3).

以下查询:

1. b(X), not(a(X)).
2. not(a(X)), b(X).

第一个产生,X = 3而第二个产生false.这是因为第一个查询首先实例化为X1,然后是2,然后是3,直到最后not(a(X))成功.
第二个查询首先实例化为X1,a(1)成功,因此not(a(1))失败.没有回溯!

Answer 3

由于@SQB指出的否定而导致的回溯缺乏实际上并不是代码的唯一问题.如果您使用地面查询稍微玩一下,您会发现@false指出的非列表和空列表也不是唯一的问题.请考虑以下查询:

   ?- intersection([2,3],[1,2,3],[2,3,4]).
yes
   ?- intersection([2],[1,2,3],[2,3,4]).
yes
   ?- intersection([3],[1,2,3],[2,3,4]).
yes
   ?- intersection([],[1,2,3],[2,3,4]).
yes

第一个通常被理解为交叉点.其他三个都是交集的子列表,包括普通的子列表[].这是由于谓词描述交叉点的方式:在交集中不是元素在第一个而不是第二个列表中的情况,并且所述元素在第一个而不是第三个列表中.该描述明显符合上述三个查询,因此它们成功.在考虑到这种描述的情况下多搞一点,还有一些其他值得注意的基本查询成功:

   ?- intersection([2,2,3],[1,2,3],[2,3,4]).
yes

解决方案中是否存在重复的问题实际上是一个争论的问题.列表[2,2,3]和[2,3]虽然不同,表示相同的集合{2,3}.关于Prolog联盟的一个问题,最近有一个答案正在详细阐述答案的这些方面.当然,上面提到的交叉点的子列表也可以包含重复或倍数:

   ?- intersection([2,2,2],[1,2,3],[2,3,4]).
yes

但为什么会这样呢？对于空列表,这很容易看到.查询

   ?- element(A,[]).
no

失败因此连接element(A,L1), not(element(A,L2))也失败了L1=[].因此,缠绕它的否定成功了.第二个否定也是如此,因此[]可以作为交集推导出来.要了解为什么[2]并[3]成功作为交集,将谓词编写为逻辑公式,并明确记下通用量词是有帮助的:

∀ L1∀ L2∀ R∀ A (intersection(L1,L2,R)←¬ (element(A,L1)∧¬ element(A,L2))∧¬ (element(A,L1)∧¬element(A,R)))

如果你查阅一本关于逻辑的教科书或一篇关于逻辑编程的教科书,它也会将Prolog代码显示为逻辑公式,你会发现规则头部没有出现的变量的通用量词可以作为存在量词移动到正文中.在这种情况下A:

∀ L1∀ L2∀ R (intersection(L1,L2,R)←∃ A (¬ (element(A,L1)∧¬ element(A,L2))∧¬ (element(A,L1)∧¬element(A,R))))

因此,对于所有论点,L1,L2,R有一些 A满足目标.这解释了交叉点的子列表的推导和元素的多次出现.

但是,查询更烦人

   ?- intersection(L1,[1,2,3],[2,3,4]).

循环而不是产生解决方案.如果您认为L1未实例化,请查看以下查询的结果

   ?- element(A,L1).
L1 = [A|_A] ? ;
L1 = [_A,A|_B] ? ;
L1 = [_A,_B,A|_C] ? ;
...

它变得清晰,查询

   ?- element(A,L1),not(element(A,[1,2,3])).

必须循环由于L1包含A第一个目标所描述的无限多个列表.因此,谓词中的相应连接也必须循环.除了产生结果之外,如果这样的谓词反映了Prolog的关系性质并且反过来也是另一种方式(第二或第三个参数变量)也是很好的.让我们将您的代码与这样的解决方案进行比较.(为了便于比较,下面的谓词就像你的代码一样描述了交集的子列表,对于不同的定义,请参见下文.)

为了反映它的声明性质,我们称之为list_list_intersection/3:

list_list_intersection(_,_,[]).
list_list_intersection(L1,L2,[A|As]) :-
   list_element_removed(L1,A,L1noA),
   list_element_removed(L2,A,L2noA),
   list_list_intersection(L1noA,L2noA,As).

list_element_removed([X|Xs],X,Xs).
list_element_removed([X|Xs],Y,[X|Ys]) :-
   dif(X,Y),
   list_element_removed(Xs,Y,Ys).

与您的谓词一样,此版本也使用交集的元素来描述关系.因此它产生了相同的子列表(包括[]):

   ?- list_list_intersection([1,2,3],[2,3,4],I).
I = [] ? ;
I = [2] ? ;
I = [2,3] ? ;
I = [3] ? ;
I = [3,2] ? ;
no

但没有循环.但是,由于已经匹配的元素被list_element_removed/3删除,因此不再产生多次出现.但是,两个第一个列表中的多次出现都正确匹配:

   ?- list_list_intersection([1,2,2,3],[2,2,3,4],[2,2,3]).
yes

这个谓词也适用于其他方向:

   ?- list_list_intersection([1,2,3],L,[2,3]).
L = [2,3|_A] ? ;
L = [2,_A,3|_B],
dif(_A,3) ? ;
L = [2,_A,_B,3|_C],
dif(_A,3),
dif(_B,3) ? ;
...

   ?- list_list_intersection(L,[2,3,4],[2,3]).
L = [2,3|_A] ? ;
L = [2,_A,3|_B],
dif(_A,3) ? ;
L = [2,_A,_B,3|_C],
dif(_A,3),
dif(_B,3) ? ;
...

因此,此版本对应于没有重复项的代码.注意A交集的元素如何显式出现在规则的头部,其中交集的所有元素都是递归遍历的.我相信这是你试图通过在Prolog规则面前使用隐式通用量词来实现的.

回到我的答案开头的某一点,这不是通常被理解为交集的东西.在所有的结果list_list_intersection/3描述了参数[1,2,3]和[2,3,4]仅[2,3]是在交叉点.在这里,您的代码会遇到另一个问题:如果您使用交集的元素来描述关系,那么如何确保覆盖所有相交元素？毕竟,所有元素都[2]发生在[1,2,3]和[2,3,4].一个显而易见的想法是遍历其中一个列表的元素,并描述两者中出现的那些也在交叉点中.以下是使用if_/3和memberd_t/3的变体:

list_list_intersection([],_L2,[]).
list_list_intersection([X|Xs],L2,I) :-
   if_(memberd_t(X,L2),
       (I=[X|Is],list_element_removed(L2,X,L2noX)),
       (I=Is,L2noX=L2)),
   list_list_intersection(Xs,L2noX,Is).

请注意,也可以遍历第二个列表的参数而不是第一个列表.谓词memberd_t/3是谓词元素/ 2的具体变体,list_element_removed/3在描述中再次使用,以避免在解决方案中出现重复.现在解决方案是独特的

   ?- list_list_intersection([1,2,3],[2,3,4],L).
L = [2,3] ? ;
no

并且上面的"问题查询"按预期失败:

   ?- list_list_intersection([1,2,3],[2,3,4],[]).
no
   ?- list_list_intersection([1,2,3],[2,3,4],[2]).
no
   ?- list_list_intersection([1,2,3],[2,3,4],[3]).
no
   ?- list_list_intersection([1,2,3],[2,3,4],[2,2,3]).
no
   ?- list_list_intersection([1,2,3],[2,3,4],[2,2,2]).
no

当然,您也可以在其他方向使用谓词:

   ?- list_list_intersection([1,2,3],L,[2,3]).
L = [2,3] ? ;
L = [3,2] ? ;
L = [2,3,_A],
dif(_A,1) ? ;
...

   ?- list_list_intersection(L,[2,3,4],[2,3]).
L = [2,3] ? ;
L = [2,3,_A],
dif(4,_A) ? ;
...