离散数学39集合的划分和覆盖310等价关系与等价类ppt课件.ppt

《离散数学39集合的划分和覆盖310等价关系与等价类ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、离散数学DiscreteMathematics山东科技大学信息科学与工程学院3-8关系的闭包关系的自反闭包关系的对称闭包关系的传递闭包一、关系的闭包定义定义3-8.1：设R是X上的二元关系，如果另外有一个关系R’满足：(1)R’是自反的(对称的，传递的)；(2)R’R；(3)对于任何自反的(对称的，传递的)关系R’’，如果有R’’R，就有R’’R’。则称关系R’为R的自反(对称，传递)闭包。记作r(R)，(s(R)，t(R))例：设集合X={x，y，z}，X上的关系R={，，}，则:自反闭包r(R)={，，

2、z>，，}对称闭包s(R)={，，，，}传递闭包t(R)={，，，}由闭包的定义可以知道，构造关系R的闭包方法就是向R中加入必要的有序对，使其具有所希望的性质。下面定理体现了这一点。二、关系的性质与闭包的关系1、定理3-8.1：设R是X上的二元关系，则(1)R是自反的，当且仅当r(R)=R(2)R是对称的，当且仅当s(R)=R(3)R是传递的，当且仅当t(R)=R证明只证明①①必要性:令R为自反.由于RR,并取右方R为S,以及任何包含R的自反关系T,有ST

3、,可见R满足自反闭包定义,即r(R)=R.充分性:由自反闭包定义R是自反的.二、关系的性质与闭包的关系1、定理3-8.1：设R是X上的二元关系，则(1)R是自反的，当且仅当r(R)=R(2)R是对称的，当且仅当s(R)=R(3)R是传递的，当且仅当t(R)=R2、定理3-8.2：设R是集合X上的二元关系，则r(R)=Rx证明：RRx，Rx是自反的，定义的前两条满足了。设R”满足RR”，R”是自反的，Rx，则R或x。如果R则由RR”，R”。如果x则必有x=y，即

4、x，由R”的自反性，则R”，总之均有R”，所以RXR”，满足定义第三条。得r(R)=Rx。对关系矩阵而言，r(R)的关系矩阵只要将MR的对角元置1即可。3、定理3-8.3：设R是集合X上的二元关系，则s(R)=RRc。证明：RRRc满足定义第一条。RRcRRcRcRRRc，所以RRc是对称的，满足定义的第二条。如果RR”，且R”是对称的，RRc，则R或Rc，如R，由RR”，则

5、y>R”，如Rc则R则R”，又因R”对称，所以R”，所以RRcR”，满足定义第三条。得s(R)=RRc。4、定理3-8.4：设R是集合X上的二元关系，则t(R)=R(i)=RR(2)R(3)…证明首先证明Rt(R).用归纳法证明如下:基础步:根据传递闭包定义,Rt(R);归纳步:假设n≥1时Rnt(R),欲证Rn+1t(R)令x,yX,则:xRn+1yxRn*Ry(z)(xRnz∧zRy)xRnz∧zRyxt(R)z∧zt(R)yxt(R)y因此,Rnt(R).于是,Rit(R).

6、次证t(R)Ri,由于包含R的传递关系都包含t(R)，且RRi,因此只需证明Ri是传递即可.令x,y,zX,则x(Ri)y∧y(Ri)z(j)(xRjy)∧(k)(yRkz)xRjy∧yRkzxRjy*yRkzxRj+kzx(Ri)z因此,Ri是传递的.综上可知,t(R)=Ri.例题1：设A={a，b，c}，R是A上的二元关系，且给定R={，，}，求r(R)，s(R)，t(R)。解：r(R)={，，，，，}s(R)={，，，

7、b>，，}为了求t(R)，先写出010MR=001100010010001MR2=001001=100100100010001010010MR3=100001=001010100100继续计算求解，会得出R4=R=R3n+1,R5=R2=R3n+2,R6=R3=R3n+3所以t(R)=RR2R35、定理3-8.5：设X含有n个元素的集合，R是X上的二元关系，则存在一个正整数k≤n，使得t(R)=RR(2)R(3)…R(K)例：A={a，b，c，d}，R={，，，}，求t(R)。解