Question

离散数学传递闭包证明

• 你的回答被采纳后将获得：
• 系统奖励15（财富值+成长值）+难题奖励30（财富值+成长值）

Answer 1

因为∅∪∅=∅
所以∀n∅ⁿ=∅
t(∅)=∪∅ⁿ=∅

t(R)=∪Rⁿ
(t(R))²=∪R²ⁿ ⊆ ∪Rⁿ
⋮
(t(R))ⁿ=∪Rⁿⁿ ⊆ ∪Rⁿ
从而t(R)∪(t(R))²∪(t(R))³⋯
=∪Rⁿ
即t(t(R))=∪Rⁿ = t(R)

Answer 2

因为∅∪∅=∅
所以∀n∅ⁿ=∅
t(∅)=∪∅ⁿ=∅
t(R)=∪Rⁿ
(t(R))²=∪R²ⁿ ⊆ ∪Rⁿ
⋮
(t(R))ⁿ=∪Rⁿⁿ ⊆ ∪Rⁿ
从而t(R)∪(t(R))²∪(t(R))³⋯
=∪Rⁿ
即t(t(R))=∪Rⁿ = t(R)

Answer 3

R的传递闭包是包含R且具有传递性的最小关系

t(R) = R U R^2 U R^3 U ...... U R^n

一般说来，要证明S是R的传递闭包，需要证明以下几点：
（1）S具有传递性；
（2）S包含R
（3）对任何包含R且具有传递性的T，都有S包含于T