离散数学 关系的性质.pptVIP

  1. 1、本文档共27页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
  5. 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
  6. 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们
  7. 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
  8. 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
4.3 关系的性质 自反性 反自反性 对称性 反对称性 传递性 自反性与反自反性 实例 例1 A={1,2,3}, R1, R2, R3是A上的关系, 其中 R1={1,1,2,2} R2={1,1,2,2,3,3,1,2} R3={1,3} 对称性与反对称性 实例 例2 设A={1,2,3}, R1, R2, R3和R4都是A上的关系, 其中 R1={1,1,2,2}, R2={1,1,1,2,2,1} R3={1,2,1,3}, R4={1,2,2,1,1,3} 传递性 实例 例3 设A={1,2,3}, R1, R2, R3是A上的关系, 其中  R1={1,1,2,2}  R2={1,2,2,3}  R3={1,3} 关系性质的充要条件 实例 自反性证明 对称性证明 反对称性证明 传递性证明 运算与性质的关系 4.4 关系的闭包 闭包定义 闭包的构造方法 集合表示 矩阵表示 图表示 闭包的性质 闭包定义 定义 设R是非空集合A上的关系, R的自反(对称或传递)闭包是A上的关系R?, 使得R?满足以下条件: (1)R?是自反的(对称的或传递的) (2)R?R? (3)对A上任何包含R的自反(对称或传递)关系 R?? 有 R??R??. 一般将 R 的自反闭包记作 r(R), 对称闭包记作 s(R), 传递闭包记作 t(R). 闭包的构造方法 (3)t(R)=R∪R2∪R3∪… 先证R∪R2∪… ? t(R)成立,为此只需证明对任意 的正整数n有 Rn ? t(R)即可。用归纳法。 n=1时,有 R1=R ? t(R)。 假设Rn?t(R)成立,那么对任意的x,y有 x,y∈Rn+1=Rn ? R ? ?t(x,t∈Rn∧t,y∈R) ? ?t(x,t∈t(R)∧t,y∈t(R)) ? x,y∈t(R) (因为t(R)是传递的) 这就证明了Rn+1 ? t(R)。 由归纳法命题得证。 再证t(R)?R∪R2∪…成立,为此只须证明R∪R2∪…是传递的。 任取x,y,y,z,则 y,z∈R∪R2∪… ∧ x,y∈R∪R2∪… ? ?t(y,z∈Rt) ∧ ?s(x,y∈Rs) ? ?t?s(y,z∈Rt ∧ x,y∈Rs) ? ?t?s(x,z∈Rt ? Rs) ? ?t?s(x,z∈Rt+s) ? x,z∈R∪R2∪… 从而证明了R∪R2∪…是传递的。 推论 设R为有穷集A上的关系,则存在正整数r 使得 t(R)=R∪R2∪…∪Rr 闭包的构造方法(续) 闭包的构造方法(续) 实例 R={a,b,b,a,b,c,c,d,d,b}, r(R) = R∪R0 ={a,b,b,a,b,c,c,d,d,b}∪{a,a,b,b,c,c,d,d} ={a,b,b,a,b,c,c,d,d,b,a,a,b,b,c,c,d,d} s(R)= R∪R?1 ={a,b,b,a,b,c,c,d,d,b}∪{b,a,a,b,c,b,d,c, b,d} } ={a,b,b,a,b,c,c,d,d,b ,c,b,d,c,b,d} t(R) = R1∪R2∪R3∪R4 ={a,b,b,a,b,c,c,d,d,b}∪{a,a,a,c,b,b,b,d, c,b,d,a,d,c}∪{a,b,a,d,b,a,b,b,b,c,c,a, c,c,d,b,d,d} ∪{a,a,a,b,a,c,,b,a,b,b,b,c, b,d,c,b,c,d,d,a,d,b,d,c} ={a,a,a,b,a,c,a,d,b,a,b,b,b,c,b,d,c,a, c,b,c,c,c,d,d,a,d,b,d,c,d,d} M r= Ms= Mt= 定理7.11 设R是非空集合A上的关系, 则 (1)R是自反的当且仅当r(R)=R。 (2)R是对称的当且仅当s(R)=R。 (3)R是传递的当且仅当t(R)=R。 * * 若x,y∈R y,z∈R,则x,z∈R), 若x,y∈R且x ? y ,则y,x ?R 若 x,y∈R有y,x∈R), ?x∈A,有x,x?R, ?x∈A,有x,x?R), 定义 如果顶点 xi 连通到xk , 则从 xi到 xk 有边 如果两点之间有边, 是一条有向边(无双向边) 如果两个顶点之间有边, 是一对方向相反的边(无单边) 每个顶点都没有环 每个顶点都有 环 关系图 对M2中1所在位置, M中相应位置都是1 若rij=1, 且 i≠j, 则rji=0 矩阵是对称矩阵 主对角线元素全是0 主对角线元素 全是1 关系 矩阵 R?R?R R∩R?1? IA R=R?1 R∩

文档评论(0)

smashing + 关注
实名认证
文档贡献者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档