使用 Peano 数除法

Question

我正在尝试制作一个除以两个 Peano 数的程序。不幸的是，在我寻找其他答案后，循环开始运行。有什么办法可以避免使用我的方法重复？

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

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

    minus(A, B, C) :- plus(C, B, A).

    division(0, _ , 0).
    division(X, s(0), X).
    division(A, B, s(N)) :- minus(A, B, R), division(R, B, N).

输出

?- division(s(s(s(s(0)))), s(0),X).
X = s(s(s(s(0)))) ;
X = s(s(s(s(0)))) ;
X = s(s(s(s(0)))) ;
X = s(s(s(s(0)))) ;
X = s(s(s(s(0)))) ;
X = s(s(s(s(0)))) ;
false.

输出#2

?- divide(s(s(s(s(0)))), Y,X).
Y = s(0),
X = s(s(s(s(0)))) ;
Y = s(s(s(s(0)))),
X = s(0) ;
Y = X, X = s(s(0)) ;
Y = s(0),
X = s(s(s(s(0)))) ;
Y = s(0),
X = s(s(s(s(0)))) ;
Y = s(0),
X = s(s(s(s(0)))) ;
Y = s(0),
X = s(s(s(s(0)))) ;
Y = s(0),
X = s(s(s(s(0)))) ;
;ERROR: Out of local stack

Answer 1

正确性。首先，让我们考虑正确性问题。根据你的定义，0/0 = 0。即division(0, 0, 0)。所以你说0除以0是0。另一个问题是s/1的定义。有关更多信息，请参阅 successor-arithmetics。

冗余答案。要确定冗余来源，请考虑每个谓词的子句。有没有可能他们都申请了同一个ground query？让我们看看：对于 plus/3，这不会发生，因为事实在第一个参数中需要 0，但规则需要 s(_)。这永远不可能同时发生。因此没有冗余源。然而，对于 division/3，两者都适用于 division(0, s(0), 0). 此外，第二个事实和规则也可能适用。

非终止。 在进入 another answer 中讨论的技术细节之前，让我们先回顾一下您期望从 4/ 中得到什么X = Y。显然，这些解决方案(X,Y): [(1,4),(2,2),(4,1)]。但是 0 的解决方案呢？

使用 Peano 数除法

Division using Peano numbers

prolog

successor-arithmetics