判断一个数是否是另一个数的倍数

Question

查看下面的代码：

multiple(X,0).
multiple(X,Y) :- lt(0,X), lt(0,Y), diff(Y,X,D), multiple(X,D).

刚好出了点问题。供您参考：
lt/2是第一个参数是否小于第二个。
diff/3是第三个参数是否等于第一个参数减去第二个。
lt/2 和 diff/3 定义正确。

定义中是否存在逻辑错误？假设 0 是每个数字的倍数有问题还是其他地方存在逻辑错误？我得到了正确的答案，但我认为查询进入了无限循环。

编辑：
这是其他定义。

natNum(0).
natNum(s(X)) :- natNum(X).

lt(0,s(X)) :- natNum(X).
lt(s(X),s(Y)) :- lt(X,Y).

sum(0,X,X).
sum(s(X),Y,s(Z)) :- sum(X,Y,Z).

diff(X,Y,Z) :- sum(Z,Y,X).

?- multiple(X, s(s(s(s(s(s(0))))))).

其中 s(0) 是 1，s(s(0)) 是 2 等等。它给出了 X 的所有所需答案，但在最后一个答案之后，它卡住了。我假设在一个无限递归循环中？

Answer 1

你的程序发生了什么？它会永远循环，还是只需要一些时间，因为您近几十年来没有更新硬件？我们不知道。（实际上，我们可以通过查看您的程序来判断，但目前太复杂了）。

我们可以轻松地缩小这种代价高昂的努力的来源。而这，没有深入了解您的程序。让我们从查询开始：

| ?- multiple(X, s(s(s(s(s(s(0))))))).
X = s(0) ? ;
X = s(s(0)) ? ;
X = s(s(s(0))) ? ;
X = s(s(s(s(s(s(0)))))) ? ;
** LOOPS or takes too long ***

没有更简单的方法吗？所有这些分号输入。相反，只需将 false 添加到您的查询中。以这种方式，找到的解决方案不再显示，我们可以专注于这个烦人的循环。而且，如果我们这样做，您还可以将 false 目标添加到您的计划中！通过这样的目标，推理的数量可能会减少（或保持不变）。如果生成的片段（称为 failure-slice）正在循环，那么这就是 原程序循环的原因：

multiple(_X,0) :- false.
multiple(X,Y) :- lt(0,X), false, lt(0,Y), diff(Y,X,D), multiple(X,D).

natNum(0) :- false.
natNum(s(X)) :- natNum(X), false.

lt(0,s(X)) :- natNum(X), false.
lt(s(X),s(Y)) :- false, lt(X,Y).

?- multiple(X, s(s(s(s(s(s(0))))))), false.
** LOOPS ***

你认识你的程序吗？只剩下循环所需的那些部分。而且，实际上在这种情况下，我们有一个无限循环。

要解决此问题，我们需要修改剩余的可见部分。我会选择 lt/2，其第一个子句可以概括为 lt(0, s(_))。

但是等等！为什么可以概括掉我们有一个自然数的要求？看看你写的事实multiple(X,0).。您也没有要求 X 是自然数。这种过度概括经常出现在Prolog程序中。它们以相对较低的价格改进了终止属性：有时它们过于笼统，但所有额外适合泛化的项都不是自然数。它们是 any 或 [a,b,c] 之类的术语，因此如果它们出现在某处，您就知道它们不属于解决方案。

所以我的想法是将 false 目标放入您的程序中，这样生成的程序（失败片段）仍然会循环。在最坏的情况下，您将 false 放在错误的位置并且程序终止。通过反复试验，您可以获得最小的故障片。现在略过的所有那些东西无关紧要！特别是 diff/3。所以不需要去理解它（暂时）。看剩下的程序就够了

判断一个数是否是另一个数的倍数

Finding whether a number is a multiple of another

prolog

failure-slice

successor-arithmetics