




已阅读5页,还剩10页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1,第三章 集合与关系,3-8 关系的闭包运算 授课人:李朔 Email:,2,一闭包的概念,对集合X上的二元关系R,有时候希望R具有一些有用的性质,这就需要在R中增加一些序偶,但又希望R不要变得太大。闭包运算就能解决这一问题。 闭包运算:对给定的关系用扩充一些序偶的办法得到具有某些特殊性质的新关系。,3,一、闭包的概念,P129 定义3-8.1 设R为X上的二元关系,若有另一个关系R满足: 1)R是自反的(对称,可传递的);(闭包具有相应性质) 2)RR;(闭包在R的基础上得到) 3)对任何自反的(对称的,传递的)关系R,若RR,就有R R(最小),则称关系R为R的自反(对称,传递)闭包,记作: r ( R ), (S (R),t (R) *自反(对称,传递)闭包应是包含R的具有相应性质的最小关系,4,一、闭包的概念,定理3-8.1 设R为X上的二元关系,则 1)R是自反的,当且仅当r(R)=R; 2)R是对称的,当且仅当S(R)=R; 3)R是传递的,当且仅当t(R)=R。 证明:1)若R自反的,因RR,且任何包含R的自反关系R,有RR,故R为自反闭包,即 r(R)=R。反之,若r(R)=R,则必自反。 其余证明略。,5,二、闭包的求法,具体如何求X上关系R的闭包呢?下面给出方法。 P120 定理3-8.2 设R为非空集X上的二元关系,则 r(R)=RRIX 证: 设RRIX ,则称任xX,R 故R在X上自反。 又R RIX,故R R。 若有自反关系R且RR,则IX R 故 R IX RR 所以 r(R)=R IX 关系图求法? 无环结点加环,6,二、闭包的求法,P120 定理3-8.3 设R为非空集X上的二元关系,则S(R)=RR C 证: 令R=RRC,因R RRC即RR, 又设 R,则R或 RC 即 RC或R 故RRC,故R是对称的。 设R是对称的且RR,则对任R 则R或 RC 当R则R 当RC则R,R 因R对称,故R,故RR 即S(R)= RRC 关系图求法? 各单向边加相反方向的一条边,7,二、闭包的求法,定理3-8.4 设R为非空集X上的二元关系,则t(R)=RR2R3 证明: 证明分两部分: (1) (基础)从传递闭包的定义,立即得到Rt(R) (2) (归纳)假设Rnt(R),n1.设a,bRn+1. 因为Rn+1=RnR, 存在cA,使a,cRn和c,bR.根据归纳前提和基础步骤,a,ct(R)和c,bt(R). 因为t(R)是传递的,得a,bt(R).这证明了 Rn+1t(R). 所以有 设a,b , c,b ,则必存在整数s和t,使得a,b RS, c,b Rt,这样RSRt,即a,c ,所以 是传递的。 由于包含R的可传递关系都包含t(R),故t(R) 由a)和b)可得t(R)= ,通常 ,将 记作R+。 关系图求法?为不直通但有通路的两结点间加上一条有向弧,8,二、闭包的求法,P121 例1: A=a, b, c, R=,求r(R),S(R),t(R). 解:r(R)=R IA =, , , , , s(R)= RR C =, 为求t(R)先求R2,R3,R4 即R2, R3=, R4=, 可见R=R4=R3n+1 R2= R5= R3n+2 R3= R6= R3n+3 故t(R) = RR 2R 3 = , , , , , , , , ,9,二、闭包的求法,例: 设A=1,2,3,4,5,R是A上的二元关系,R=, 分别求r(R),S(R),T(R). (可用关系图求解),10,二、闭包的求法,定理3-8.5 设X是含有n个元素的集合,R是X上的二元关系,则存在一个正整数kn,使得:t(R)=RR 2R 3Rk 证明:设有xi,xjX,记t(R)=R+,如果xiR+xj则存在整数p0,使xiRpxj成立,即存在e1,e2,ep-1有xiRe1,e1Re2,ep-1Rxj。设满足上述条件的最小p大于n,则在上述序列中必有0tn不成立。 *从本定理可以知道,在n个元素的有限集上关系R的传递闭包不妨写为 t(R)= RR 2R 3Rn。 例2: P123,11,二、闭包的求法,定理3-8.6设X是集合,R是X上的二元关系,则:a)rs(R)=sr(R) b)rt(R)=tr(R) c)ts(R)st R) 证明:令Ix表示X上的恒等关系。 a) sr(R)=s(IxR)=(IxR)(IxR)c =(IxR)(IxcRc)=IxRRc =Ixs(R) =rs(R) * 求R+的Warshall算法 P124,12,求R+的Warshall算法,R=, , i=1,2,3n,各行i列元素为1?与I行逻辑加,13,若R是自反的,则s(R) 和t(R) 也是自反的 若R是对称的,则r(R) 和t(R)
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025年度沙发厂厂长聘用合同范本
- 2025版公路运输合同服务质量保障协议
- 2025版外汇市场交易执行顾问服务合同专业
- 2025年度房地产抵押权转让合同模板
- 2025照明灯具行业合作研发合同范本
- 2025版全新协议离婚财产放弃及共同子女财产租赁合同
- 2025年仓储服务与仓储设施租赁及仓储管理合同
- 2025民法典宣传周·旅游合同法律风险评估合同
- 2025年度新能源产业第三方担保服务合同
- 2025年大学生实习安全协议汇编及法律风险提示
- 《孙子兵法》全文及译文
- 2026年日历表全年表(含农历、周数、节假日及调休-A4纸可直接打印)-
- 《经济法基础》 (第2章) 第二章 会计法律制度
- 病案管理法律法规培训
- 电力系统安全运行与故障预警机制
- 企业员工工会建设计划
- 电信行业网络优化与安全保障措施
- 《无人机搭载红外热像设备检测建筑外墙及屋面作业》
- JJF(京) 114-2023 安德森六级撞击微生物采样器校准规范
- 幼儿园情商培训
- 物流无人机技术与应用解决方案
评论
0/150
提交评论