版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、3-8 关系的闭包,本节讲述关系的闭包运算。要求会求关系的自反(对称、传递)闭包。,现在来讨论另一种重要关系闭包. 所谓闭包是指,对于给定的关系R和一种性质P, 则把包含R并且满足性质P的最小关系称为R对于P的闭包, 记为P(R). 若P是自反的, 则称R是自反闭包, 记为r(r), 若P是对称的,则称R是对称闭包, 记为s(R); 若P是传递的, 则称R是传递闭包,记为t(R). 也可形式地给出下面的定义和定理.,一、关系的闭包定义 定义3-8.1:设R是X上的二元关系,如果另外有一个关系R满足: (1)R是自反的(对称的,传递的); (2)RR; (3)对于任何自反的(对称的,传递的)关系
2、R,如果有RR,就有RR。则称关系R为R的自反(对称,传递)闭包。记作r(R),(s(R),t(R),例:设集合X=x,y,z,X上的关系 R=,则自反闭包 r(R)=, 对称闭包 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为自反. 由于RR, 并取右方R为S, 以
3、及任何包含R的自反关系 T, 有S T, 可见R满足自反闭包定义, 即r(R) = R. 充分性: 由自反闭包定义R是自反的. 下面再给出关于闭包的三个构造性定理.,2、定理3-8.2:设R是集合X上的二元关系,则r(R)=Rx 证明:RRx,Rx是自反的,定义的前两条满足了。设R”满足RR”,R”是自反的, Rx,则R或x。如果R则由RR”,R”。如果x则必有x=y,即x,由R”的自反性,则R”,总之均有R”,所以RXR”,满足定义第三条。得r(R)=Rx。 对关系矩阵而言,r(R)的关系矩阵只要将MR的对角元置1即可。,3、定理3-8.3:设R是集合X上的二元关系,则s(R)=RRc。 证
4、明:RRRc满足定义第一条。 RRcRRcRcRRRc,所以RRc是对称的,满足定义的第二条。 如果RR”,且R”是对称的,RRc,则R或Rc,如R,由RR”,则R”,如Rc则R则R”,又因R”对称,所以R”,所以RRcR”,满足定义第三条。得s(R)=RRc。,4、定理3-8.4:设R是集合X上的二元关系,则 t(R)= R(i)=RR(2)R(3) 证明 首先证明 R t(R). 用归纳法证明如下: 基础步: 根据传递闭包定义, Rt(R); 归纳步: 假设n1时Rnt(R), 欲证Rn+1t(R)令 x,y X, 则: x Rn+1yx Rn * Ry (z)(xRnzzRy) xRnz
5、zRy xt(R)zzt(R)y xt(R)y 因此, Rnt(R). 于是, Ri t(R).,次证t(R) Ri, 由于包含 R的传递关系都包含t(R),且R Ri, 因此只需证明 Ri是传递即可. 令x, y, z X, 则 x( Ri)yy( Ri)z (j)(xRjy) (k)(yRkz) xRjyyRkz 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)=, 为了求t(R),先写出 0 1 0 MR=
6、0 0 1 1 0 0 0 1 0 0 1 0 0 0 1 MR2= 0 0 1 0 0 1 = 1 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 1 0 MR3= 1 0 0 0 0 1 = 0 0 1 0 1 0 1 0 0 1 0 0 继续计算求解,会得出R4=R=R3n+1, R5=R2=R3n+2 , R6=R3=R3n+3 所以t(R)= R R2 R3,5、定理3-8.5:设X含有n个元素的集合,R是X上的二元关系,则存在一个正整数kn,使得 t(R)=RR(2)R(3)R(K),例:A=a,b,c,d,R=,求t(R)。 解: R(2)=, R(3)=
7、R(4)= 所以t(R)=RR(2)R(3)R(4) =, ,,6、Warshall算法 设R是个元素集合A上的二元关系, (1)A是R的相关矩阵; (2)置i=1; (3)对所有,如果aji=1,则对k=1,2,n ajk=ajk+aik(第i行与第j行逻辑相加,记于第j行) (4)i=i+1; (5)如果in,则转到步骤(3),否则停止。,7、关系图作法如下 (1)r(R)在R的基础上添加自回路,使得每点均有自回路。 (2)s(R)在R中两结点间只有一条弧时,再添一条反向弧,使两结点间或是0条弧,或是两条弧,原来两点间没有弧不能添加。 (3)t(R)在R中如结点x通过有向路能通到z,则添加
8、一条从x到z的有向弧,其中包括如x能达到自身,则必须添从x到x的自回路。,定理3.8.6 R为自反s(R)和t(R)为自反 R为对称r(R)和t(R)是对称 R为传递r(R)是传递的 证明 只给出的证明 因为r(R)=RIx, 已知R为对称, 而Ix显然也是对称的, 因此r(R)是对称的. t(R)=RR2R3, 用归纳法证明t(R)对称. 由于 R是对称的, 则对于x,yX, 可推出:,xR2y x(R * R)y (z)(xRzzRy) (z)(zRxyRz) (z)(yRzzRx) y(R * R)x 因此R2是对称的 假设对于n1时, Rn是对称, 欲证Rn+1是对称. 令x, yX, 则: xRn+1y x(Rn * R)y (z)(xRnzzRy) (z)(zR
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2026年私立医院工作计划
- 副处级管理干部竞聘知识能力考试题(B卷)及答案
- 安全生产责任制及管理制度
- 2026四川天府德阳分行人才招聘备考题库带答案详解(综合题)
- 2026上半年甘肃事业单位分类考试备考题库发布了吗附答案详解(研优卷)
- 2026四川天府德阳分行人才招聘备考题库附参考答案详解(培优)
- 2026年一般从业人员(全员培训)《新安全生产法》安全生产模拟考试题含答案
- 员工个人总结与自我评价范文6篇
- 2026上半年贵州事业单位联考贵州省红十字会招聘1人备考题库附答案详解(综合卷)
- 2026广东广州花都区新雅街尚雅小学招聘语文专任教师2人备考题库含答案详解(综合题)
- 2025华夏银行贷款合同全文
- 消防维保安全保障措施及应急预案
- 工程部机电安装主管年终总结
- 电机润滑基础知识培训课件
- DB51∕T 2998-2023 四川省小型水库标准化管理规程
- 旅游业内部审计制度及流程研究
- 区块链原理与实践全套完整教学课件
- 看图猜词游戏规则模板
- 英语四级词汇表
- 药用高分子材料-高分子材料概述
- 社区春节活动方案
评论
0/150
提交评论