离散数学中关系的传递闭包：一种新的式子及其证明

摘要

本文从关系的传递闭包出发，总结了一种新的传递闭包的式子，即 t(R) = R∪R²∪R³∪...∪Rⁿ。通过解释和证明，说明了该式子的合理性和正确性，并讨论了其与书上给出的传递闭包式子的联系。

正文部分

1. 传递闭包的式子

传递闭包是指关系 R 的最小传递关系，即包含 R 的所有元素对 (x, y)，且对于任意的 (x, y)∈R，(y, z)∈R，则 (x, z)∈R。在离散数学中，传递闭包的式子通常是 t(R) = R∪R²∪R³∪...∪Rᵏ⁻¹，其中 k 表示关系 R 的元素个数。但是，我们也可以从关系图的角度出发，总结一种类似的传递闭包式子，即 t(R) = R∪R²∪R³∪...∪Rⁿ，其中 n 表示关系 R 中最长的链的长度。

2. 传递闭包式子的合理性

我们可以通过以下证明来说明 t(R) = R∪R²∪R³∪...∪Rⁿ 是一个合理的传递闭包式子：

首先，对于任意的 (x, y)∈R，(y, z)∈R，由于 R 是一个关系，所以 (x, z)∈R，即 (x, z)∈R²。同样地，对于任意的 (x, y)∈R²，(y, z)∈R²，由于 R 是一个关系，所以 (x, z)∈R³。依此类推，对于任意的 (x, y)∈R，(y, z)∈Rⁿ⁻¹，由于 R 是一个关系，所以 (x, z)∈Rⁿ。因此，我们可以得到 t(R) = R∪R²∪R³∪...∪Rⁿ 是一个传递闭包式子。

3. 传递闭包式子的正确性

接下来，我们需要证明 t(R) 确实是关系 R 的传递闭包。为了证明该结论，我们需要证明以下三个条件：

（1）t(R) 包含关系 R 的所有元素对。

（2）t(R) 是一个传递关系。

（3）t(R) 是关系 R 的最小传递关系。

首先，由于 t(R) = R∪R²∪R³∪...∪Rⁿ，所以 t(R) 肯定包含了关系 R 的所有元素对。

其次，对于任意的 (x, y)∈t(R)，(y, z)∈t(R)，我们可以将它们表示为 (x, y)∈Rⁱ，(y, z)∈Rʲ，其中 i, j∈N。根据传递闭包的定义，(x, z)∈Rⁱʲ。因此，我们可以得到 t(R) 是一个传递关系。

最后，我们需要证明 t(R) 是关系 R 的最小传递关系。假设存在另一个传递关系 S，且 S 包含于 t(R)，则 S 也包含于 R∪R²∪R³∪...∪Rⁿ。因此，S 也是 R 的传递闭包。因此，我们可以得到 t(R) 是关系 R 的最小传递关系。

4. 传递闭包式子的联系

从数学上来说，t(R) = R∪R²∪R³∪...∪Rⁿ 和 t(R) = R∪R²∪R³∪...∪Rᵏ⁻¹ 都是关系 R 的传递闭包式子。但是，它们的具体含义是不同的。前者表示 t(R) 包含了所有长度小于等于 n 的链，而后者表示 t(R) 包含了所有长度小于等于 k-1 的链。

在实际应用中，我们需要根据具体的问题来选择合适的传递闭包式子。例如，在社交网络分析中，我们需要找到两个人之间的关系链，这时候可以使用长度小于等于 n 的链来表示；而在路网分析中，我们需要找到两个地点之间的路径，这时候可以使用长度小于等于 k-1 的链来表示。

结论

本文从关系的传递闭包出发，总结了一种新的传递闭包的式子，即 t(R) = R∪R²∪R³∪...∪Rⁿ。通过解释和证明，说明了该式子的合理性和正确性，并讨论了其与书上给出的传递闭包式子的联系。在实际应用中，我们需要根据具体的问题来选择合适的传递闭包式子。

结束语

关系的传递闭包是离散数学中的一个重要概念，它在实际应用中有着广泛的应用。本文通过总结传递闭包的方法，给出了一种新的传递闭包式子，并对其进行了证明和讨论。希望本文能够对读者有所启发，对离散数学的学习和应用有所帮助。

参考文献

[1] Rosen, K. H. (2012). Discrete mathematics and its applications. New York: McGraw-Hill.

[2] 张凤荣. 离散数学[M]. 北京: 北京邮电大学出版社, 2013.

[3] 韩高阳. 离散数学[M]. 北京: 清华大学出版社, 2012.