离散数学-关系的闭包省名师优质课赛课获奖课件市赛课一等奖课件

4.4关系闭包闭包定义闭包结构方法

集合表示矩阵表示图表示闭包性质第1页1一、闭包定义

定义设R是非空集合A上关系,R自反（对称或传递）闭包是A上关系R

,使得R

满足以下条件：

（1）R

是自反（对称或传递）

（2）R

R

（3）对A上任何包含R自反（对称或传递）关系R

有R

R

.

普通将R自反闭包记作r(R),对称闭包记作s(R),传递闭包记作t(R).第2页2由闭包定义可知，R自反（对称，传递）闭包是含有R而且含有自反（对称，传递）性质“最小”关系。

假如R已是自反二元关系，显然有：R=r(R)。一样，当R是对称二元关系时R=s(R)；当R是传递二元关系时，R=t(R)，且反之亦然。第3页3二、关系闭包运算

（1）已知一个集合中二元关系R，则

r(R),s(R),t(R)是唯一，它是包含R最小自反（对称，传递）关系；（2）若R是自反（对称，传递），则

r(R),s(R),t(R)就是R本身。（3）若R不是自反（对称，传递），则能够补上最少序偶，使之变为自反、对称、传递关系，从而得到r(R),s(R),t(R)；第4页4例：设Ａ={a,b,c},R={<a,b>,<b,c>,<c,a>}，求r(R),s(R),t(R)。解：r(R)=s(R)=t(R)={<a,b>,<b,c>,<c,a>,<a,c>,<b,a>,<c,b>,<a,a>,<b,b>,<c,c>}例：设Ａ={a,b},R={<a,a><a,b>}，则r(R)={<a,a><a,b><b,b>},s(R)={<a,a><a,b><b,a>},t(R)={<a,a><a,b>}=R第5页5

设R是A上二元关系，x∈A，将全部(x,x)

R有序对加到R上去，使其扩充成自反二元关系，扩充后自反关系就是R自反闭包r(R)。

比如，A={a,b,c,d},R={(a,a),(b,d),(c,c)}。R自反闭包r(R)={(a,a),(b,d),(c,c),(b,b),(d,d)}。

于是可得：定理:R是A上二元关系，则R自反闭包r(R)=R∪IA。1.结构R自反闭包方法。

三、闭包结构方法第6页62.结构R对称闭包方法。

每当(a,b)∈R，而(b,a)

R时，将有序对(b,a)加到R上去，使其扩充成对称二元关系，扩充后对称关系就是R对称闭包s(R)。

比如，A={a,b,c,d,e},R={(a,a),(a,b),(b,a),(b,c),(d,e)}。R对称闭包s(R)={(a,a),(a,b),(b,a),(b,c),(c,b),(d,e),(e,d)}。

定理:R是A上二元关系，是其逆关系，则R对称闭包s(R)=R∪

。

由逆关系定义可知：第7页73.结构R传递闭包方法。

设R是A上二元关系，每当(a,b)∈R和(b,c)∈R而(a,c)

R时，将有序对(a,c)加到R上使其扩充成R1，并称R1

为R传递扩张，R1

假如是传递关系，则R1是R传递闭包；假如R1不是传递关系，继续求R1传递扩张R2，假如R2是传递关系时，则R2是R传递闭包；假如R2不是传递关系时，继续求R2传递扩张R3…，假如A是有限集，R经过有限次扩张后，定能得到R传递闭包。扩张后传递关系就是R传递闭包t(R)。

定理:设R为A上关系,则有t(R)=R∪R2∪R3∪…

说明：对于有穷集合A(|A|=n)上关系,上式中并最多不超出Rn.第8页8思索：设A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>},求r(R),s(R),t(R).解:r(R)=R∪R0={<a,a>,<a,b>,<b,a>,<b,b>,<b,c>,<c,c>,<c,d>,<d,d>},s(R)=R∪R

1={<a,b>,<b,a>,<b,c>,<c,b>,<c,d>,<d,c>},

t(R)=R∪R2∪R3∪R4

R2={<a,a>,<a,c>,<b,b>,<b,d>}R3={<a,b>,<a,d>,<b,a>,<b,c>}R4={<a,b>,<a,c>,<b,b>,<b,d>}=R2于是t(R)=R∪R2∪R3=

{<a,a>,<a,b>,<a,c>,<a,d>,<b,a>,<b,b>,<b,c>,<b,d>,<c,d>}.第9页9闭包结构方法（续）设关系R,r(R),s(R),t(R)关系矩阵分别为M,Mr,Ms和Mt,则

Mr=M+EMs=M+M’

Mt=M+M2+M3+…E是和M同阶单位矩阵,M’是M转置矩阵.注意在上述等式中矩阵元素相加时使用逻辑加.第10页10闭包结构方法（续）设关系R,r(R),s(R),t(R)关系图分别记为G,Gr,Gs,Gt,则Gr,Gs,Gt顶点集与G顶点集相等.除了G边以外,以下述方法添加新边：

考查G每个顶点,假如没有环就加上一个环，最终得到Gr.考查G每条边,假如有一条xi到xj单向边,i≠j,则在G中加一条xj到xi反方向边，最终得到Gs.考查G每个顶点xi,找从xi出发每一条路径，假如从xi到路径中任何结点xj没有边，就加上这条边.当检验完全部顶点后就得到图Gt.第11页11实例例1设A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>},R和r(R),s(R),t(R)关系图以下列图所表示.Rr(R)s(R)t(R)第12页12南宁空调回收

南宁空调出租仧莒彾MicrosoftOfficePowerPoint，是微软企业演示文稿软件。用户能够在投影仪或者计算机上进行演示，也能够将演示文稿打印出来，制作成胶片，方便应用到更广泛领域中。利用MicrosoftOfficePowerPoint不但能够创建演示文稿，还能够在互联网上召开面对面会议、远程会议或在网上给观众展示演示文稿。MicrosoftOfficePowerPoint做出来东西叫演示文稿，其格式后缀名为：ppt、pptx；或者也能够保留为：pdf、图片格式等第13页定理

R是A上关系，则⑴R是自反，当且仅当r(R)=R.⑵R是对称，当且仅当s(R)=R.⑶R是传递，当且仅当t(R)=R.证实略，因为由闭包定义即可得。定理

R是A上关系，则⑴R是自反，则s(R)和t(R)也自反。⑵R是对称，则r(R)和t(R)也对称。⑶R是传递，则r(R)也传递。证实:⑴因为R自反,得r(R)=R,即R∪IA=R,r(s(R))=s(R)∪IA=(R∪R-1)∪IA=(R∪IA)∪R-1=r(R)∪R-1=R∪R-1=s(R)∴s(R)自反

第14页14类似能够证实t(R)也自反。证实⑵.证实t(R)对称:(t(R))-1=(R∪R2∪...∪Rn∪...)-1

=R-1∪(R2)-1∪...∪(Rn)-1∪...

=R-1∪(R-1)2∪...∪(R-1)n∪...=R∪R2∪...∪Rn∪...(∵R对称，∴R-1=R)=t(R)所以t(R)也对称。类似能够证实r(R)也对称。证实⑶.证实r(R)传递:先用归纳法证实下面结论:(R∪IA)i=IA∪R∪R2∪...∪Ri①i=1时R∪IA=IA∪R结论成立。②假设i≤k时结论成立，即(R∪IA)k=IA∪R∪R2∪...∪Rk(R2)-1=(RR)-1=R-1R-1=(R-1)2第15页15③当i=k+1时(R∪IA)k+1=(R∪IA)k(R∪IA)

=(IA∪R∪R2∪...∪Rk）(IA∪R)

=(IA∪R∪R2∪...∪Rk)∪(R∪R2∪...∪Rk+1)=IA∪R∪R2∪...∪Rk∪Rk+1所以结论成立.t(r(R))=t(R∪IA)=(R∪IA)∪(R∪IA)2∪(R∪IA)3∪...=(IA∪R)∪(IA∪R∪R2)∪(IA∪R∪R2∪R3)∪...=IA∪R∪R2∪R3∪...=IA∪t(R)=IA∪R(R传递t(R)=R)=r(R)所以r(R)也传递。

。。第16页16定理设R1、R2是A上关系，假如R1

R2

，则

⑴

r(R1)

r(R2)⑵s(R1)

s(R2)⑶

t(R1)

t(R2)

证实⑴r(R1)=IA∪R1

IA∪R2=

r(R2)⑵，⑶类似可证。定理设R是A上关系，则

⑴

sr(R)=rs(R)⑵tr(R)=rt(R)⑶st(R)ts(R)证实：⑴sr(R)=r(R)∪(r(R)-1=(R∪IA)∪(R∪IA)-1

=(R∪IA)∪(R-1∪IA-1)=R∪IA∪R-1∪IA

=(R∪R-1)∪IA=s(R)∪IA=rs(R)⑵证实用前边证实结论：(R∪IA)k=IA∪R∪R2∪...∪Rk很轻易证实，这里从略。第17页17⑶