Prolog否定(\+)用法与非亲子关系谓词正确实现

已定义的基础事实 #

female(mary).
female(sandra).
female(juliet).
female(lisa).
male(peter).
male(paul).
male(dony).
male(bob).
male(harry).
parent(bob, lisa).
parent(bob, paul).
parent(bob, mary).
parent(juliet, lisa).
parent(juliet, paul).
parent(juliet, mary).
parent(peter, harry).
parent(lisa, harry).
parent(mary, dony).
parent(mary, sandra).

问题根因 #

Prolog的否定运算符\+采用失败即否定的实现逻辑：

• 它不会主动为规则里的自由变量枚举可能取值
• 执行\+ Goal时，Prolog会先尝试证明Goal成立：只要能找到任意一组变量绑定让Goal为真，\+ Goal就直接返回假；只有当Goal完全无法被证明时，\+ Goal才返回真

这就解释了两次写法不符合预期的原因：

1. 第一版规则not_parent(X, Y) :- \+parent(X, Y).
   当查询绑定常量的目标比如not_parent(bob, juliet)时，X、Y都是固定值，Prolog检查发现parent(bob, juliet)没有对应事实，就返回正确结果。但查询带自由变量的not_parent(X, Y)时，X、Y都未绑定，Prolog尝试证明parent(X,Y)——事实库中存在多组亲子关系，parent(X,Y)显然可满足，因此\+parent(X,Y)直接返回false，不会做任何枚举。
2. 第二版规则

   father_of(X, Y):-male(X), parent(X, Y). 
   mother_of(X, Y):-female(X), parent(X, Y).
   
   not_parent(X, Y):- 
       male(X), \+ father_of(X, Y);
       female(X), \+ mother_of(X, Y).
   

   这版只通过male(X)、female(X)给X绑定了具体取值，但Y始终是未绑定的自由变量。执行\+ father_of(X,Y)时，只要X存在任何一个子女，father_of(X,Y)就可满足，否定直接失败；只有X没有任何子女时，否定才成立，但此时Y没有被绑定任何值，自然无法枚举出完整的X-Y组合。

正确实现方案 #

要枚举所有不存在亲子关系的人员组合，必须在调用否定判断前，先把X、Y都绑定到具体的人员实体上：

1. 首先定义谓词枚举所有出现过的人员：

   person(X) :- female(X) ; male(X).
   

2. 重写not_parent/2规则，先枚举所有可能的人员配对，再过滤存在亲子关系的组合：

   not_parent(X, Y) :-
       person(X),
       person(Y),
       \+ parent(X, Y).
   

此时查询not_parent(X, Y)，Prolog就会逐一列出所有符合要求的配对结果。

关键注意点 #

只要需要用\+做否定判断、同时需要枚举自由变量的合法取值，必须在调用\+之前，把目标中涉及的所有自由变量都绑定到具体的实体/常量上，否则会出现判断逻辑错误、无法枚举结果的问题。

内容的提问来源于stack exchange，提问作者Dragos Polifronie