lisp - 给出了二元关系 R。在 LISP 中构建传递自反闭包 R *

Question

给出了二元关系R。构造传递和自反闭包R *。在 LISP 中////怎么来的？

Answer 1

您没有提供太多信息，但通常情况下，给定一个关系 R，R 的传递和自反闭包是一个关系 R*，定义如下:

• 对于满足R(X,Y)的所有X,Y，关系R*(X,Y)也成立；
• 对于满足 R(X,Y) 和 R*(Y,Z) 的所有 X,Y,Z，关系 R*(X,Z) 成立；

假设给定了一个函数 R，其行为如下:

• (funcall R :x X :y Y) 返回非零值当且仅当 R(X,Y)
• (funcall R :x X) 返回满足 R(X,Y) 的所有 Y
• (funcall R :y Y) 返回满足 R(X,Y) 的所有 X
• (funcall R) 返回满足 R(X,Y) 的 (X.Y) 对列表。

然后您可以构建一个函数来计算传递闭包和自反闭包；如果您想知道 R*(X,Z) 是否成立，您可以从 X 开始并尝试所有可能满足 的 Y R(X,Y) 直到 Y 等于 Z，或者您可以递归地确定 R*(Y,Z).

实现并测试之后，也尝试检测周期。