求证一个离散数学定理的证明求教rt(R)=tr(R)的证明（其中R是集合A上的二元关系,t(R)为A上的传递闭包,r(R)为A上的自反闭包）
来源：学生作业帮助网 编辑：六六作业网 时间：2024/11/29 02:13:08
求证一个离散数学定理的证明求教rt(R)=tr(R)的证明（其中R是集合A上的二元关系,t(R)为A上的传递闭包,r(R)为A上的自反闭包）
求证一个离散数学定理的证明
求教rt(R)=tr(R)的证明
（其中R是集合A上的二元关系,t(R)为A上的传递闭包,r(R)为A上的自反闭包）
求证一个离散数学定理的证明求教rt(R)=tr(R)的证明（其中R是集合A上的二元关系,t(R)为A上的传递闭包,r(R)为A上的自反闭包）
tr（R）=t(R U I)=(R U I)U(R U I)²U…=I U R U R²U…=I U t（R）=rt（R）
其中U表示析取,也就是或.
把R视作A*A的子集就可以写出它的各种闭包，
通俗地讲，如果R={(x_i,y_i):i∈A}是一个二元关系，那么它的自反闭包就是把所有在R中出现过的x_i,y_i对应的(x_i,x_i)和(y_i,y_i)也加进去。
比如R={(a,b),(b,b),(b,d)}，那么R的自反闭包就是
{(a,b),(b,b),(b,d)}∪{(a,a),(b,b),(d,d)}={(a...
全部展开
把R视作A*A的子集就可以写出它的各种闭包，
通俗地讲，如果R={(x_i,y_i):i∈A}是一个二元关系，那么它的自反闭包就是把所有在R中出现过的x_i,y_i对应的(x_i,x_i)和(y_i,y_i)也加进去。
比如R={(a,b),(b,b),(b,d)}，那么R的自反闭包就是
{(a,b),(b,b),(b,d)}∪{(a,a),(b,b),(d,d)}={(a,b),(b,b),(b,d),(a,a),(d,d)} ，
也就是r(R)=R ∩ {(x,x)|x∈ A}
-----------------------------------------------------------------
t(R)可视做{(x,y)|(x,y)∈ R, or 存在 x_1,...,x_n, s.t. (x,x_1)∈R, ...,(x_n,y)∈ R}，可证明它是传递的，且每个包含R的传递关系必须包含它。
如果xRy且R∈rt(R)，那么
rt(R)=t(R)∩{(x,x)|x∈ A},也就是xRx和yRy都成立，所以xRy∈r(R)，又因为xRy,yRy,yRx成立的时候，一定有关系xRx(传递性)，因此xRy∈tr(R).
收起