在Prolog中,Negation-as-Failure如何运作？

Question

我想知道Prolog如何解决这个程序:

test(X, Y).
test(X, X):-!, fail.

我用谷歌搜索"否定为失败",但我很困惑!

Answer 1

请考虑以下示例:

father(nick, john).

我们使用谓词父(X,Y)来表示X的父亲是Y.让我们查询数据库:

?- father(nick,X).
X = john.

?- father(john,Y).
false.

在这两种情况下,我们都询问谁是某人的父亲(分别是尼克,约翰).在第一种情况下,prolog知道答案(约翰)然而在第二种情况下它没有,所以答案是错误的,这意味着约翰没有任何父亲.我们可能会期望,因为我们没有提供关于约翰父亲的信息,所以它会回应unknown.这将是一个开放的世界,如果不知道某些事情,我们不会认为这是错误的.相反,在prolog的封闭世界中,如果我们不知道某事,我们认为这是错误的.

请注意,基于知道任何人必须拥有父亲的基础上我们说我们不知道约翰的父亲是谁的世界并不是一个开放的世界; 它可以很容易地在prolog中建模:

data_father(nick, john).
father(X,Y):-
    data_father(X,Y) -> true ; true.

另一方面,在一个开放的世界序言中,你会写出事实和反事实:

father(nick, john).
not father(adam, X).

这就是失败的否定.但是,这不是您的程序中发生的事情:

test(X, Y).
test(X, X):-!, fail.

无论参数的值如何,第一个子句总是会成功.事实上,正因为如此,命名参数没有意义,prolog会给你一个单例警告; 你可以把这个条款写成test(_, _).

另一方面,第二个子句总是会失败.它可能以两种方式失败:(1)参数可能不同(2)参数是统一的,因此prolog移动到身体然后失败.

正是因为prolog正在使用一个封闭的世界模型,所以没有任何条款(没有副作用(但这被认为是不好的做法))总是失败.相反,这些额外调用会导致程序运行速度变慢并占用更多内存.

值得注意的是,cut(!/0)在这里没有任何作用,因为当你到达它时,没有更多的选择点.但请考虑这个例子:

test(X, Y).
test(X, X):-!, fail.
test(X, 42).

?- test(1,42).
true ;
true.

?- test(42,42).
true ;
false.

在这两种情况下,prolog都会创建3个选择点,每个子句一个.在第一种情况下,Prolog将成功匹配第一个条款的头部并成功,因为没有正文.然后,它将无法匹配第二个子句的头部,并且主体将不会被"执行".最后,它将匹配第三个子句的头部并成功,因为没有正文.

然而,在第二种情况下:Prolog将成功匹配第一个条款的头部并成功,因为没有正文.然后,它将成功匹配第二个子句的头部; 切割将删除所有其他选择点,然后它将失败,因为fail.因此,prolog不会尝试第三个条款.

自从你提到它以来,关于否定就是失败的几句话.否定是基于封闭的世界假设; 因为我们假设任何不能从我们已经拥有的事实中推断出来的东西都是错误的,如果我们不能证明某些东西,那就意味着它的反面被认为是真的.例如,考虑一下:

father(nick, john).
fatherless(X) :- \+ father(X, _).

和

?- fatherless(nick).
false.

?- fatherless(john).
true.

相反,在一个开放的世界序言中,代码如下:

father(nick, john).
not father(adam, X).
fatherless(X) :- \+ father(X, _).

fatherless/1只会成功adam,因为缺口而失败并返回unknown其他任何东西