离散数学第四章2.ppt

  1. 1、本文档共62页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
离散数学第四章2

南通大学理学院 第四章 二元关系和函数(2/3) 4.2 关系的运算 例4.2.1 设R={1,2,1,3,2,4,4,3},则   domR={1,2,4}   ranR={2,3,4}  fldR={1,2,3,4} 怎样计算Rn 呢? 如果R是用集合表达式给出的,可以通过n-1次右复合计算得到Rn .如果R是用关系矩阵M给出的,则Rn 的关系矩阵是Mn,即n个矩阵M之积.与普通矩阵乘法不同的是,其中的相加是逻辑加,即 1+1=1,1+0=0+1=1,0+0=0 如果R是用关系图G给出的,可以直接由图G得到Rn 的关系图G.G的顶点集与G相同.考察G的每个顶点xi,如果在G中从xi 出发经过n步长的路径到达顶点xj,则在G中加一条从xi 到xj 的边.当把所有这样的便都找到以后,就得到图G. 例4.2.5 设A={a,b,c,d} R={a,b,b,a,b,c,c,d}, 求R的各次幂,分别用矩阵和关系图表示. 解:用关系图的方法得到关系图 如下: 4.3 关系的性质 一般起: 4.4 关系的闭包 4.5 等价关系和偏序关系 作业 Page 113, Ex 1-6,12-16 (2) 由R1和R2的传递性有 R1 ??R1 ??R1和R2 ??R2 ??R2 而 (R1∩R2) ??(R1∩R2)  ?R1 ??R1∩R1 ??R2∩R2 ??R1∩R2 ??R2  (R1∩R2)∩R1 ??R2∩R2 ??R1 ?R1∩R2 从而证明了R1∩R2也是A上的传递关系. × × × × √ R1???R2 × √ √ √ × R1-R2 × × √ √ √ R1∪R2 √ √ √ √ √ R1∩R2 √ √ √ √ √ R1-1 传递性 反对称性 对称性 反自反性 自反性  关系闭包定义 定义7.14 设R是非空集合A上的关系,R的自反(对称或传递)闭包是A上的关系R,使得R 满足以下条件: (1)R是自反的(对称的或传递的) (2)R ??R (3)对A上任何包含R的自反(对称或传递)关系R有R ? R. 一般将R的自反闭包记作r(R),对称闭包s(R),传递闭包记作t(R). 定理4.4.1 设R为A上的关系,则有 (1)r(R)=R∪R0 (2)s(R)=R∪R-1 (3)t(R)=R∪R2∪R3∪… 关系闭包的求法 关系矩阵和关系图求闭包的方法: 设关系R,r(R),s(R),t(R)的关系矩阵分别为M,Mr,Ms和Mt,则Mr=M+E Ms=M+M Mt=M+M2+M3+… 其中E是和M同阶的单位矩阵,M是M的转置矩阵.注意在上述等式中矩阵的元素相加时使用逻辑加. 设关系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出发的所有2步,3步,…,n步长的路径(n为G中的顶点数),检查完所有的顶点后就得到图Gt . 例4.4.1 设A={a,b,c,d},R={a,b,b,a,b,c,c,d,d,b},求r(R),s(R),t(R)以及它们的关系图和矩阵. 解: r(R)={a,b,b,a,b,c,c,d,d,b,a,a,b,b,c,c,d,d} s(R)={a,b,b,a,b,c,c,b,c,d,d,c,d,b,b,d} t(R)=R∪R2∪R3={a,a,a,b,a,c,a,d,b,a,b,b,b,c,b,d,c,d} 一.等价关系 定义4.5.1 设R为非空集合上的关系.如果R是自反的、对称的和传递的,则称R为A上的等价关系.设R是一个等价关系,若x,y∈R,称x等价于y,记做x~y. 例 4.5.1 设A={1,2,…,8},如下定义A上的关系R:R={x,y|x,y∈A∧x≡y(mod 3)} 其中x≡y(mod 3)叫做x与y模3相等,即x除以3的余数与y除以3的余数相等. R为A上的等价关系,因为 x∈A,有x≡x(mod 3) x,y∈A,若x≡y(mod 3),则有y≡x(mod 3) x,y,z∈A,若x≡y(mod 3),y≡z(mod 3),则有x≡z(mod 3)

文档评论(0)

dajuhyy + 关注
实名认证
内容提供者

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

1亿VIP精品文档

相关文档