离散数学-3-8关系的闭包运算revised.ppt_第1页
离散数学-3-8关系的闭包运算revised.ppt_第2页
离散数学-3-8关系的闭包运算revised.ppt_第3页
离散数学-3-8关系的闭包运算revised.ppt_第4页
离散数学-3-8关系的闭包运算revised.ppt_第5页
已阅读5页，还剩10页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、1、第三章集合和关系，3-8关系的闭包运算课程师：李朔email :2，2，闭包的概念，对于集合x上的二元关系r，有时希望对r具有有用的性质。 这需要在r上增加一些序列，但希望r不要太大。 闭包运算可以解决这个问题。 闭包运算：通过在给定的关系上扩展多个有序集合来获得具有特定性质的新关系。 3，一、闭包的概念，将P129定义3-8.1作为x上的二元关系，如果有另一个关系r，则：1)R是自逆(对称的，可传递的) (闭包具有相应的性质)2)RR (闭包根据r得到)3)任何自逆的(对称的，传递的) 3)R被传递，仅在t(R)=R的情况下。 证明：1)如果r是自反的话，因为有包含RR以及r的自反关系r

2、，RR，所以r是自反闭包，即r(R)=R。 相反，如果r(R)=R，则必定相反。 佗证略。5、二、闭包的求解方法，具体是如何求解x上关系r的闭包的方法如下所示。 当设P120定理3-8.2为非空集x上的二元关系时，设r(R)=RRIX证： RRIX，则被称为任意的xX，r在x上自然相反。 因为是R RIX所以是R R。 如果有自反关系r且RR，IX R是否可以从R IX RR用r(R)=R IX关系图求出？ 当将P120定理3-8.3设为非空集x上的二维关系时，设S(R)=RR C证： R=RRC，并且由于是RRC，故当设r为r或RC，r为对称并且RR时，则得到任意r 各单向边加上相反方向的一

3、边，设7，2，闭包的求法，定理3-8.4为非空集x上的二元关系，则t(R)=RR2R3证明：证明分为两个部分： (1) (基础)闭包的定义，立即根据cRn和c，bR .归纳的前提和基础步骤，a 由于包括r在内的所有可传递关系都包括t(R )，因此t(R )可以从a )和b )得到t(R)=并且通常记为r。 关系图求法？ 为了在不直通但有通路的两节点间加上有向弧、8、二、闭包的求法，求出P121例1: A=a、b、c、R=、r(R )、S(R )，因为R=R4=R3n 1 R2=R5=R3n 2 R3=R6=R3n 3 可知闭包的求法的T(R ).(可以用关系图求解)、10，2、闭包的求法，将定

4、理3-8.5设为包含n个要素的集合，将r设为x上的二维关系时，存在正整数kn，当满足t(R)=RR 2R 3Rk的上述条件的最小p大于n时*根据本定理可知，在n个要素的有限集合上关系r的传递闭包可以写成t(R)=RR 2R 3Rn。 例2 :设2: P123，11，二，闭包的求法，定理3-8.6为集合，r为x上的二元关系，则a)rs(r)=sr(r)b)rt (。a ) Sr(R )=s (ixr )=(ixr ) c=(ixr ) (I xcrc )=IX RRC=ixs(R )=RS () 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. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论