Prolog/剪枝和否定
本节介绍了如何使用剪枝来控制回溯、Prolog 中的否定方式以及两者结合使用的有效方法。
考虑以下程序。
a :- b.
b :- c.
c :- d.
b.
如果你将此加载到 Prolog 并询问 Prolog **?- a.**，Prolog 将首先搜索任何可以使 **a** 为真的规则；它将 **a** 添加到其要证明的目标列表中。第一条规则表明 **a** 为真，如果 **b** 为真，那么 Prolog 将目标 **b** 添加到其列表中。它找到了 **c** 的规则，现在需要证明 **d**，这失败了。Prolog 现在从其列表中删除目标 **d**，因为它无法证明它，并尝试以不同的方式证明 **c**。这被称为 **回溯**。Prolog 也无法证明 **c**，再次回溯并尝试 **b**。它可以使用程序的最后一行来证明这一点，Prolog 终止。
理解 Prolog 如何评估你的查询对于 Prolog 编程至关重要。为了控制 Prolog 评估你的程序的方式，你可以使用 **剪枝** 运算符：**!**。剪枝运算符是一个原子，可以以以下方式使用
a(X) :- b(X), c(X), !, d(X).
如果 Prolog 在规则中发现剪枝，它将不会回溯它所做的选择。例如，如果它为变量 X 选择了 frank，并遇到剪枝，那么 Prolog 将认为 frank 是 X 的唯一选项，即使数据库中还有其他可能性。这由以下程序说明
a(X, Y) :- b(X), !, c(Y).
b(1).
b(2).
b(3).
c(1).
c(2).
c(3).
如果我们询问 Prolog **?- a(Q, R).** 它将首先回答
?- a(Q, R).
Q = 1
R = 1 ;
当我们使用 **;** 键询问 Prolog 更多答案时：**
Q = 1
R = 2 ;
Q = 1
R = 3 ;
否
.
正如你所见，Prolog 将 1 视为 Q 的唯一选项，而它返回了 R 的所有备选方案。当 Prolog 开始进行查询时，它试图使用程序的第一行来证明 **a(Q, R)**。为了证明这条规则，它首先需要 **证明 b(Q)**，它在 Q = 1 时成功。然后 Prolog 遇到剪枝并将 Q = 1 设置为 Q 的唯一选项。它继续进行规则的最后一个目标，c(R)。它首先找到 R = 1，并完成了它的目标。当用户按下 **;** 时，Prolog 首先检查目标 c(R) 的备选方案。请记住，当 Prolog 遇到剪枝时，它还没有为 R 选择实例，所以它仍然可以查找 R 的备选方案。当它用完 R 的备选方案时，Prolog 无法查找 Q 的备选方案，并终止。
为了理解剪枝如何改变程序的含义，请考虑以下内容
a(X) :- b(X), !, c(X).
b(1).
b(2).
b(3).
c(2).
如果没有第一行中的剪枝，Prolog 将返回 **Q = 2** 到查询 **?- a(Q).**。使用剪枝，Prolog 无法找到答案。为了证明这个目标，它首先使用 Q = 1 来证明 b(Q)。然后它遇到剪枝，被强制设置为 Q=1，并且无法找到 **c(1)** 的证明。如果它可以搜索备选方案，它会发现 Q=2 使 b(Q) 和 c(Q) 都为真，但剪枝不允许这样做。但是，如果我们询问 Prolog **a(2)**，它将返回 yes。现在，Prolog 使用 2 来实例化程序第一行中的 X，因为用户已经指定了它，并且当 Prolog 达到剪枝时，X 被强制设置为 2，允许 Prolog 证明 c(2)。
剪枝也跨多个规则工作。如果一个程序有两个关于目标 **a(X)** 的规则，并且 Prolog 在第一个规则中遇到剪枝，那么它不仅被强制设置为变量的实例，而且还被强制设置为 **a(X)** 的第一个规则。Prolog 不会考虑第二个规则。例如，以下程序
a(X) :- b(X), !, c(X).
a(X) :- d(X).
b(1).
b(4).
c(3).
d(4).
将对查询 **?- a(X).** 失败。Prolog 可以使用第二个规则，使用 **X =4** 和程序的最后一行来解决查询，但 Prolog 首先尝试第一个规则，当它遇到剪枝时，它被迫忽略 a(Q) 的所有备选方案。这一次，查询 **?- a(4)** 也会失败，因为 Prolog 仍然到达剪枝。当它使用第一个规则尝试 **a(4)** 时，它成功地证明了 **b(4)** 并到达剪枝。然后它尝试 **c(4)**，这失败了，Prolog 必须终止。如果将 **b(4).** 和 **b(1).** 行从程序中删除，那么 Prolog 在遇到剪枝之前，在第一个规则上失败，并且被允许使用第二个规则来解决查询。
not(X) 是在 Prolog 中实现否定的方式；但是 not(X) 不意味着 X 为假，它意味着 X 无法被证明为真。
例如，使用以下数据库
man('Adam').
woman('Eve').
询问 not(man('Adam')). 将返回 no。
not(Goal) :- call(Goal),!,fail.
not(Goal).