《二元关系 (2)优秀PPT.ppt》由会员分享，可在线阅读，更多相关《二元关系 (2)优秀PPT.ppt（134页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、二元关系第1页，本讲稿共134页4-1 序偶与集合的笛卡尔积序偶与集合的笛卡尔积实际上“序偶”概念以前已经用过。例如，用序偶表示平面直角坐标系中一个点(a,b)。设x表示上衣,y表示裤子,(x,y)可以表示一个人的着装。一一.序偶与有序序偶与有序n n元组元组1.1.定义定义:由两个对象x、y组成的序列称为有序二元组，也称之为序偶，记作；称x、y分别为序偶的第一，第二元素。注意，序偶与集合x,y不同：序偶：元素x和y有次序；集合x,y：元素x和y的次序是无关紧要的。第2页，本讲稿共134页2.2.定义定义：设：设，是两个序偶，如果是两个序偶，如果 x=u x=u和和y=vy=v，则称，则称和和
2、相等，相等，记作记作=.=.3.定义定义:有序有序3元组是一个序偶元组是一个序偶,其第一个元素也是个序偶。其第一个元素也是个序偶。有序有序3元组元组,c可以简记成可以简记成。但但a,不是有序不是有序3元组。元组。4.定义定义:有序有序n元组是一个序偶元组是一个序偶,其第一个元素本身是个有序其第一个元素本身是个有序n-1元组元组,记作记作,xn。且可以简记成。且可以简记成。5.定义定义：=(x1=y1)(x2=y2)(xn=yn)第3页，本讲稿共134页二二.集合的集合的笛卡尔积 例如“斗兽棋”的16颗棋子，可看成是由两种颜色的集合A和8种动物的集合B组成的。A=红,蓝 B=象,狮,虎,豹,狼,
3、狗,猫,鼠每个棋子可以看成一个序偶，斗兽棋可记成集合AB：,虎象狮豹狼鼠猫狗虎象狮豹狼鼠猫狗第4页，本讲稿共134页1.定义定义:设A、B是集合，由A的元素为第一元素，B的元素为第二元素组成序偶的集合，称为A和B的笛卡尔积，记作AB，即 AB=|xAyB 例1 设A=0,1，B=a,b，求AB，BA，AA。解：AB=,BA=,AA=,可见 ABBA所以，集合的笛卡尔积运算不满足交换律。第5页，本讲稿共134页 另外 (AB)C=,c|AB cC A(BC)=a,|aA BC,因 a,不是有序三元组,所以(AB)CA(BC)。故也不满足结合律。2.性质性质 1)如果如果A、B都是有限集，且|A|
4、=m,|B|=n，则|AB|=mn.证明：由笛卡尔积的定义及排列组合中的乘法原理，直接推得此定理。2)A=B=第6页，本讲稿共134页3)对对和和满足分配律。满足分配律。设设A,B,C是任意集合，则是任意集合，则 A(BC)=(A B)(A C)；A(BC)=(A B)(A C)；(AB)C=(A C)(B C)；(AB)C=(A C)(B C)证明证明：任取：任取 A(BC)x A y BC x A (y By C)(x A y B)(x A y C)A B A C (A B)(A C)所以所以式成立。式成立。其余可以类似证明。其余可以类似证明。第7页，本讲稿共134页4)若若C,则则 A
5、B(A C B C)(C A C B).证明证明:必要性：必要性：设设A B，求证，求证 A C B C任取任取 A C x A y C x B y C (因因A B)B C 所以所以,A C B C.充分性：充分性：若若C,由由A C B C 求证求证 A B 取取C中元素中元素y,任取任取 x Ax A y C A C B C (由由A C B C)x B y C x B 所以所以,A B.所以所以 A B(A C B C)类似可以证明类似可以证明 A B(C A C B).第8页，本讲稿共134页5)设A、B、C、D为非空集合，则 ABCDACBD.证明:首先,由ABCD 证明ACBD.
6、任取xA，任取yB，所以 xAyBABCD (由ABCD)xCyD 所以,ACBD.其次,由AC，BD.证明ABCD任取AB AB xAyB xCyD (由AC，BD)CD 所以,ABCD 证毕.第9页，本讲稿共134页6)约定 (A1A2)An-1)An)=A1A2An 特别 AAA=An 设R是实数集合，则R2表示笛卡尔坐标平面，R3表示三维空间，Rn表示n维空间。3.应用1)令令A1=x|x是学号是学号 A2=x|x是姓名是姓名 A3=男男,女女 A4=x|x是出生日期是出生日期 A5=x|x是是班级班级 A6=x|x是是籍贯籍贯 则A1A2A3 A4A5 A6中一个元素：这就是学生档案
7、数据库的一条信息，所以学生的档案就是A1A2A3 A4A5 A6的一个子集。n 个个第10页，本讲稿共134页2)令A=a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z 是英文字母表 一个英文单词可以看成有序n元组：如 at=,boy=,data=,computer=于是可以说：atA2,boyA3,dataA4,computerA8,于是英文词典中的单词集合可以看成是 AA2An 的一个子集。作业 第105页 第11页，本讲稿共134页4-2 关系及其表示法关系及其表示法 关系是一个非常普遍的概念，如数值的大于关系、整除关系，人类的父子关
8、系、师生关系、同学关系等。下面讨论如何从中抽象出关系的定义和如何表示关系。一一.例子例子1.大写英字母与五单位代码的对应关系R1:令=A,B,C,D,Z =30,23,16,22,21是五单位代码集合=11000,10011,01110,10010,10001R1=,.,第12页，本讲稿共134页2.令=1,2,3,4,A中元素间的关系R2：R2=,AA二二.基本概念基本概念1.关系的定义定义1:设A、是集合，如果 AB，则称R是一个从A到B的二元关系。如果 RAA，则称R是A上的二元关系。二元关系简称为关系。定义2:任何序偶的集合，都称之为一个二元关系。如:R=,第13页，本讲稿共134页R
9、 xRy 也称之为x与y有关系。后缀表示中缀表示R xRy 也称之为x与y没有关系。例3.R是实数集合，R上的几个熟知的关系：从例3中可以看出关系是序偶(点)的集合(构成线、面)。x2+y2=4=xy第14页，本讲稿共134页2.关系的定义域与值域定义域定义域(domain)：设R AB，由所有R的第一个元素组成的集合，称为R的定义域，记作dom R，即 dom R=x|y(R)值域值域(range)：设R AB，由所有R的第二个元素组成的集合，称为R的值域，记作ran R，即 ran R=y|x(R)上述 R2=,dom R2=1,2,3,4 ran R2=1,2,3,4第15页，本讲稿共1
10、34页三.关系的表示方法1.枚举法:即将关系中所有序偶一一列举出，写在大括号内。如前的R2=,。2.谓词公式法：即用谓词公式表示序偶的第一元素与第二元素间的关系。例如 R=|xy3.有向图法：R AB,用两组小圆圈(称为 结点)分别表示A和B的元素，当R时，从x到y引一条有向弧(边)。这样得到的图形称为R的关系图。第16页，本讲稿共134页 如R AA,即R是集合A中关系时,可能有R,则从x到x画一条有向环(自回路)。例例 设A=1,2,3,4,B=a,b,c，R3 AB，R3=,则R3的关系图如下：例例 设A=1,2,3,4,R4 AA，R4=,则R4的关系图如右上图。1。2。3。4。ABa
11、bc1。4。23R4:R3:第17页，本讲稿共134页4.矩阵表示法：有限集合之间的关系也可以用矩阵来表示，这种表示有限集合之间的关系也可以用矩阵来表示，这种表示法便于用计算机来处理关系。法便于用计算机来处理关系。设设A=a1,a2,am，B=b1,b2,bn是个有限集，是个有限集，R AB，定义，定义R的的mn阶矩阵阶矩阵 MR=(rij)mn，其中，其中 rij=R3=,R4=,上例中 MR=MR4=1 若R0 若R(1im,1jn)31 0 10 1 01 0 00 0 1431 2 3 4a b c1 0 0 10 0 1 01 1 0 01 0 0 1441 2 3 41 2 3 4
12、第18页，本讲稿共134页四.三个特殊关系1.空关系：因为 AB，(或 AA)，所以也是一个从A到B(或A上)的关系，称之为空空关系关系。即无任何元素的关系，它的关系图中只有结点,无任何边；它的矩阵中全是0。2.完全关系(全域关系)：AB(或AA)本身也是一个从A到B(或A上)的关系，称之为完全关系。即含有全部序偶的关系。它的矩阵中全是1。第19页，本讲稿共134页3.A上的恒等关系IA：IA AA，且IA=|xA称之为A 上的恒等关系。例如A=1,2,3,则IA=,A上的、完全关系及IA的关系图及矩阵如下：MIA=1 0 00 1 00 0 1331。2。31。2。31 1 11 1 11
13、1 1331。2。30 0 00 0 00 0 033M=MAA=AAIA第20页，本讲稿共134页五.关系的集合运算由于关系就是集合，所以集合的、-、和运算对关系也适用。例如，A是学生集合，R是A上的同乡关系，S是A上的同姓关系，则RS：或同乡或同姓关系RS：既同乡又同姓关系R-S：同乡而不同姓关系RS：同乡而不同姓,或同姓而不同乡关系 R：不是同乡关系,这里R=(AA)-R作业 第109页 、c)d)第21页，本讲稿共134页4-3 关系的性质 本节将研究关系的一些性质，它们在关系的研究中起着重要的作用。这是本章最重要的一节这是本章最重要的一节。本节中所讨论的关系都是集合A中的关系。关系的
14、性质主要有：自反性、反自反性、对称性、反对称性和传递性。一一.自反性自反性定定义义:设R是集合A中的关系，如果对于任意xA都有R(xRx)，则称R是A中自反关系。即 R是A中自反的x(xAxRx)例如在实数集合中,“”是自反关系，因为，对任意实数x，有x x.第22页，本讲稿共134页从关系有向图看自反性:每个结点都有环。从关系矩阵看自反性：主对角线都为1。令A=1,2,3给定A上八个关系如下：1。2。1。2。1。2。1。2。33331。2。1。2。1。2。1。2。3333R2R1R3R4R5R6R7R8第23页，本讲稿共134页 可见这八个关系中R1、R3、R4是自反的。二二.反自反性反自反
15、性定义定义：设R是集合A中的关系，如果对于任意的xA都有R，则称R为A中的反自反关系。即R是A中反自反的x(xAR)从关系有向图看反自反性:每个结点都无环。从关系矩阵看反自反性：主对角线都为0。如实数的大于关系，父子关系是反自反的。注意注意：一个不是自反的关系，不一定就是反自反的，如前边R6、R7非自反,也非反自反。第24页，本讲稿共134页下面R2、R5、R8、均是反自反关系。1。2。1。2。1。2。1。2。33331。2。1。2。1。2。1。2。3333R2R1R3R4R5R6R7R8第25页，本讲稿共134页三三.对称性对称性定义定义:R是集合A中关系,若对任何x,yA,如果有xRy,必
16、有yRx,则称R为A中的对称关系。R是是A上对称的上对称的x y(x A y A xRy)yRx)从关系有向图看对称性:在两个不同的结点之间，若有边的话，则有方向相反的两条边。从关系矩阵看对称性：以主对角线为对称的矩阵。邻居关系是对称关系，朋友关系是对称关系。第26页，本讲稿共134页下边R3、R4、R6、R8均是对称关系。1。2。1。2。1。2。1。2。33331。2。1。2。1。2。1。2。3333R2R1R3R4R5R6R7R8第27页，本讲稿共134页四.反对称性定义定义:设R为集合A中关系,若对任何x,yA,如果有xRy,和yRx,就有x=y,则称R为A中反对称关系。R是A上反对称的
17、x y(x A y A xRy yRx)x=y)x y(x A y A x y xRy)y x)(P112)由R的关系图看反对称性：两个不同的结点之间最多有一条边。从关系矩阵看反对称性：以主对角线为对称的两个元素中最多有一个1。另外对称与反对称不是完全对立的，有些关系它既是对称也是反对称的，如空关系和恒等关系。R第28页，本讲稿共134页下边R1、R2、R4、R5、R8均是反对称关系。R4、R8既是对称也是反对称的。1。2。1。2。1。2。1。2。33331。2。1。2。1。2。1。2。3333R2R1R3R4R5R6R7R8第29页，本讲稿共134页五五.传递性传递性定义定义:R是是A中关系
18、，对任何中关系，对任何x,y,zA,如果有如果有xRy,和和yRz,就就有有xRz,则称则称R为为A中传递关系。中传递关系。即即R在在A上传递上传递x y z(x A y A z A xRy yRz)xRz)实数集中的实数集中的、，集合、，集合、是传递的。是传递的。从关系关系图和关系矩阵中不易看清是否有传递性。有从关系关系图和关系矩阵中不易看清是否有传递性。有时，必须直接根据传递的定义来检查。时，必须直接根据传递的定义来检查。检查时要特别注意使得传递定义表达式的前件为检查时要特别注意使得传递定义表达式的前件为F的时候的时候此表达式为此表达式为T，即是传递的。，即是传递的。即若即若R与与R有一个
19、是有一个是F时时(即定义的前件为即定义的前件为假假)，R是传递的。是传递的。第30页，本讲稿共134页例如例如A=1,2,下面下面A中关系中关系R是传递的是传递的.通过带量词的公式在论域展开式说明通过带量词的公式在论域展开式说明R在在A上传递上传递x y z(x A y A z A xRy yRz)xRz)x y z(xRy yRz)xRz)(为了简单做些删改为了简单做些删改)y z(1Ry yRz)1Rz)y z(2Ry yRz)2Rz)(z(1R1 1Rz)1Rz)z(1R2 2Rz)1Rz)(z(2R1 1Rz)2Rz)(z(2R2 2Rz)2Rz)(1R1 1R1)1R1)(1R1 1
20、R2)1R2)(1R2 2R1)1R1)(1R2 2R2)1R2)(2R1 1R1)2R1)(2R1 1R2)2R2)(2R2 2R1)2R1)(2R2 2R2)2R2)(F F)F)(F T)T)(T F)F)(T F)T)(F F)F)(F T)F)(F F)F)(F F)F)T1 2第31页，本讲稿共134页下边R1、R3、R4、R5、R8均是传递的关系。1。2。1。2。1。2。1。2。33331。2。1。2。1。2。1。2。3333R2R1R3R4R5R6R7R8第32页，本讲稿共134页本节要求本节要求：1.准确掌握这五个性质的定义。准确掌握这五个性质的定义。2.熟练掌握五个性质的判
21、断和证明。熟练掌握五个性质的判断和证明。R是是A中中自反自反的的x(x AxRx)R是是A中中反自反反自反的的x(x A R)R是是A上上对称对称的的x y(x A y A xRy)yRx)R是是A上上反对称反对称的的x y(x A y A xRy yRx)x=y)x y(x A y A x y xRy)y x)R在在A上上传递传递x y z(x A y A z A xRy yRz)xRz)上述定义表达式都是上述定义表达式都是蕴涵式蕴涵式,所以判断关系所以判断关系R性质时要特性质时要特别注意使得性质定义表达式的前件为别注意使得性质定义表达式的前件为F的时候此表达式的时候此表达式为为T，即，即R
22、是满足此性质的。是满足此性质的。(自反和反自反性除外自反和反自反性除外)R第33页，本讲稿共134页自反性自反性反自反性反自反性对称性对称性传递性传递性反对称性反对称性每个结点都有环每个结点都有环 主对角线全是主对角线全是1每个结点都无环每个结点都无环 主对角线全是主对角线全是0不同结点间如果有边不同结点间如果有边,则有方向相反的两条则有方向相反的两条边边.是以对角线为对称是以对角线为对称 的矩阵的矩阵不同结点间不同结点间,最多有一最多有一条边条边.以主对角线为对称以主对角线为对称的位置不会同时为的位置不会同时为1如果有边如果有边,则也有边则也有边.或者定义的前件为假或者定义的前件为假.如果如
23、果aij=1,且且ajk=1,则则aik=1从关系的矩从关系的矩阵阵从关系的有向从关系的有向图图 性性质质判定判定:第34页，本讲稿共134页 下面归纳这八个关系的性质：Y-有 N-无1。2。1。2。1。2。1。2。3333R2R1R3R4自反性 反自反性 对称性 反对称性 传递性 R1 Y N N Y Y R2 N Y N Y N R3 Y N Y N Y R4 Y N Y Y Y 第35页，本讲稿共134页1。2。1。2。1。2。1。2。3333R5R6R7R8自反性 反自反性 对称性 反对称性 传递性 R5 N Y N Y Y R6 N N Y N N R7 N N N N N R8 N
24、 Y Y Y Y 第36页，本讲稿共134页练习练习1:令令I是整数集合，是整数集合，I上关系上关系R定义为：定义为：R=|x-y可被可被3整除整除，求证，求证R是自反、对称和传递的。是自反、对称和传递的。证明证明：证自反性证自反性：任取：任取xI,(要证出要证出 R)因因 x-x=0,0可被可被3整除整除,所以有所以有R,故故R自反。自反。证对称性证对称性：任取：任取x,yI,设设R,(要证出要证出 R)由由R定义得定义得 x-y可被可被3整除整除,即即x-y=3n(nI)，y-x=-(x-y)=-3n=3(-n),因因-nI,R,所以所以R对称。对称。证传递性证传递性:任取任取x,y,zI
25、,设设xRy,yRz,(要证出要证出xRz)由由R定义得定义得 x-y=3m,y-z=3n(m.nI)x-z=(x-y)+(y-z)=3m+3n=3(m+n),因因m+nI,所以所以xRz,所以所以R传递。传递。证毕证毕 第37页，本讲稿共134页练习练习2：设R是集合A上的一个自反关系,求证：R是对称和传递的，当且仅当 和在R中,则有也在R中。证明：必要性:已知R是对称和传递的。设R 又R，(要证出 R)因R对称的故R,又已知R 由传递性得R。所以有如果和在R中,则有也在R中。充分性:已知任意 a,b,cA，如和在R中,则有也在R中。先证先证R对称对称：任取 a,bA 设R，(要证出 R)因
26、R是自反的,所以R，由R且R，根据已知条件得R，所以R是对称的。第38页，本讲稿共134页再证再证R传递传递：任取 a,b,cA 设R，R。(要证出R)由R是对称的,得R，由R且R，根据已知条件得R，所以R是传递的。作业 第113页 、第39页，本讲稿共134页4-4 关系的复合 二元关系除了可进行集合并、交、补等运算外，还可以进行一些新的运算，先介绍由两个关系生成一种新的关系，即关系的复合运算。例如，有3个人a,b,c，A=a,b,c，R是A上兄妹关系，S是A上母子母子关系，RS即a是b的哥哥,b是a的妹妹;b是c的母亲，c是b的儿子。则a和c间就是舅舅和外甥舅舅和外甥的关系,记作 RS,称
27、它是R和S的复合关系。abcRS第40页，本讲稿共134页1.1.定义定义:设是R从X到Y的关系，S是从Y到Z的关系，则R和S的复合关系记作RS。定义为：RS=|xXzZy(yY RS)显然，RS 是从X到Z的关系。2.复合关系的计算方法(俗称过河拆桥法)A=1,2,3 B=1,2,3.4 C=1,2,3,4,5R AB S BC枚举法R=,S=,则 RS=,第41页，本讲稿共134页有向图法关系矩阵法令A=a1,a2,am B=b1,b2,bn C=c1,c2,ct R AB S BC。C123。41。2。3。A1。2。3。A。B123。4RS5。C123。45第42页，本讲稿共134页c1
28、1=(a11b11)(a12b21).(a1nbn1)=(a1kbk1)(其中是逻辑乘,是逻辑加)cij=(ai1b1j)(ai2b2j).(ainbnj)=(aikbkj)(1im,1jt)MS MR.(aij).(bij).M(cij)0 1 0 00 0 1 11 0 0 034。1 0 0 0 01 0 1 0 00 0 0 1 00 1 0 0 1=451 0 1 0 00 1 0 1 11 0 0 0 03 5k=1nk=1n第43页，本讲稿共134页谓词公式法设I是实数集合，R和S都是I上的关系，定义如下：R=|y=x2+3x S=|y=2x+3所以 RS=|y=2x2+6x+3
29、三.性质 关系复合运算不满足交换律，但是1.满足结合律:R AB S BC T CD 则xx2+3x2(x2+3x)+3 =2x2+6x+3RS第44页，本讲稿共134页证明：任取R (S T)b(bBR S T)b(bBRc(cCST)bc(bBR(cCST)cb(cC(bBRST)c(cCb(bBRS)T)c(cCR S)T)(R S)TABCDRSTR SS TR (S T)(R S)T)所以可以用下图形象表示:第45页，本讲稿共134页2.R AB S BC T BC R (ST)=(R S)(R T)R (ST)(R S)(R T)证明 任取R (ST)b(bBRST)b(bBR(S
30、T)b(bBRS)(bBRT)b(bBRS)b(bBRT)R SR T(R S)(R T)所以R (ST)=(R S)(R T)第46页，本讲稿共134页证明 任取R (ST)b(bBRST)b(bBR(ST)b(bBRS)(bBRT)b(bBRS)b(bBRT)R S R T(R S)(R T)所以 R (ST)(R S)(R T)x(A(x)B(x)xA(x)xB(x)第47页，本讲稿共134页3.R是从A到B的关系，则 R IB=IA R=R此式的证明很容易，从略。下面列举一例来验证。令A=1,2,3,B=a,b,c,d从这两个图看出它们的复合都等于R。1。2。3。AIA。Babc。dR
31、1。2。3。ARIB。abc。d。Babc。d1。2。3。AB第48页，本讲稿共134页4.关系的乘幂 令R是A上关系，由于复合运算可结合，所以关系的复合可以写成乘幂形式。即 R R=R2，R2 R=R R2=R3，一般地 R0=IA，Rm Rn=Rm+n (Rm)n=Rmn (m,n为非负整数)例如R是A上关系，如上图所示,可见R2,表明在R图上有从a到c有两条边的路径:a b c;R3,表明在R图上有从a到d有三条边的路径:a b c d。.如果Rk,表明在R图上有从x到y有k条边(长为k)的路径。(x,yA)adbcR:第49页，本讲稿共134页4-5 逆关系 逆关系(反关系)也是我们经
32、常遇到的概念，例如与就是互为逆关系。一.定义 R是从A到B的关系，如果将R中的所有序偶的两个元素的位置互换，得到一个从B到A的关系，称之为R的逆关系，记作RC，或 R-1。RC=|R RC R二.计算方法 1.R=,RC=,第50页，本讲稿共134页2.RC的有向图：是将R的有向图的所有边的方向颠倒一下即可。3.RC的矩阵 M =(MR)T 即为R矩阵的转置。如 三.性质令R、S都是从X到Y的关系，则 1.(RC)C=R 2.(RS)C=RCSC。3.(RS)C=RCSC。4.(RS)C=RCSC。RC1 0 11 0 1 00 0 0 11 0 1 1MR=340 0 01 0 10 1 1
33、MR=c 43第51页，本讲稿共134页证明1.：任取(RS)C，则(RS)C RS RS RCSC RCSC所以 (RS)C=RCSC，其它类似可证。5.R S RC SC。证明：充分性，已知RC SC，则任取RRC SC S R S 必要性，已知R S，则任取RC RS SC RC SC 6.(R)C=RC证明:任取(R)C RR RC RC .(R)C=RC第52页，本讲稿共134页7.令R是从X到Y的关系，S是Y到 Z的关系，则 (R S)C=SC RC。(注意RC SC)证明：任取(R S)CR Sy(yYRS)y(yYSCRC)SC RC 所以(R S)C=SC RC 8.R是A上
34、关系，则 R是对称的，当且仅当 RC=R R是反对称的，当且仅当 RRC IA。证明：充分性，已知 RC=R (证出R对称)任取x,yA 设R,则RC,而RC=R 所以有R，所以R对称。第53页，本讲稿共134页必要性，已知R 对称，(证出RC=R)先证RCR，任取RC,则R,因R对称所以有R，所以RCR。再证R RC，任取R,因R对称，所以有R，则RC,所以RRC。最后得RC=R。证明 充分性，已知RRC IA，(证出R反对称)任取x,yA 设R 且R，RRRRC，RRC IA (因RRC IA)x=y 所以R反对称。第54页，本讲稿共134页必要性，已知R反对称，(证出RRC IA)任取R
35、RC RRCRRC RRx=y (因R反对称)IA 所以RRC IA。第4-3和4-4节的要求：熟练掌握求复合关系和逆关系的计算方法及性质。作业：第118页、a)b)、第55页，本讲稿共134页4-6 关系的闭包运算 关系的闭包是个很有用的概念，特别是传递闭包。关系的闭包是通过关系的复合和求逆构成的一个新的关系。这里要介绍关系的自反闭包、对称闭包和传递闭包。一.例子 给定 A中关系R，如图所示，分别求A上另一个关系R，使得它是包含R的“最小的”(序偶尽量少)分别具有自反(对称、传递)性的关系。这个R就分别是R的自反(对称、传递)闭包。1。2。3第56页，本讲稿共134页这三个关系图分别是R的自
36、反、对称、传递闭包。二.定义：给定 A中关系R,若A上另一个关系R，满足：RR；R是自反的(对称的、传递的)；R是“最小的”，即对于任何A上自反(对称、传递)的关系R”,如果RR”,就有RR”。则称R是R的自反(对称、传递)闭包。记作r(R)、(s(R)、t(R)(reflexive、symmetric、transitive)1。2。31。2。31。2。3第57页，本讲稿共134页实际上r(R)、(s(R)、t(R)就是包含R的“最小”的自反(对称、传递)关系。三.计算方法定理1.给定 A中关系R,则 r(R)=RIA。证明：令R=RIA,显然R是自反的和RR，下面证明R是“最小的”：如果有A
37、上自反关系R”且RR”,又IAR”,所以 RIAR”,即RR”。所以R就是R的自反闭包。即r(R)=RIA。定理2.给定 A中关系R,则 s(R)=RRC。证明方法与1.类似。定理3.给定 A中关系R,则 t(R)=RR2R3.。证明：令R=RR2R3.,显然有 RR；第58页，本讲稿共134页证R是传递的：任取x,y,zA,设有R R,由R定义得必存在整数i,j使得Ri,Rj,根据关系的复合得Ri+j,又因Ri+j R,所以R,R传递。证R是“最小的”：如果有A上传递关系R”且 RR”,（证出RR”）任取R,则由R定义得必存在整数i,使得Ri,根据关系的复合得A中必存在i-1个元素e1,e2
38、,.,ei-1，使得 (见49页)RR.R。因RR”,有R”R”.R”。由于R”传递，所以有R”。RR”。综上所述，R就是R的传递闭包，即 t(R)=RR2R3=Rii=1第59页，本讲稿共134页用上述公式计算t(R)，要计算R的无穷大次幂,好象无法实现似的。其实则不然，请看下例:A=1,2,3 A中关系R1,R2,R3,如下：R1=,R2=,R3=,=所以t(R1)=R1 =,=,=IA,=R2 .t(R2)=R2 =,=t(R3)=R2 2R13R14R11R12R13R12R23R24R23R22R23R23R32R32R32R3第60页，本讲稿共134页定理4.给定 A中关系R,如果
39、A是有限集合，|A|=n则 t(R)=RR2.Rn。证明：令R=RR2R3.,R”=RR2.Rn下面证明R=R”，显然有R”R。下面证明RR”：任取R,由R定义得必存在最小的正整数i 使得Ri,(下面证明in)如果in,根据关系的复合得A中必存在i-1个元素e1,e2,.,ei-1，使得 RR.R。上述元素序列:x=e0,e1,e2,.,ei-1,y=ei中共有i+1个元素，i+1n,而A 中只有n个元素，所以上述元素中至少有两个相同，设ej=ek(jk)，于是R的关系图中会有下面这些边：第61页，本讲稿共134页从此图中删去回路中k-j(k-j1)条边后得Ri-(k-j)，i-(k-j)i,
40、与i是最小的矛盾。所以in,所以R”,于是 RR”。最后得 R=R”，所以 t(R)=RR2.Rn 定理证毕。xe1ej-1ej=ekej+1。.。ej+2ek-1ek-2ek+1ek+2.ei-1y第62页，本讲稿共134页求t(R)的矩阵Warshall算法：|X|=n,RXX,令MR=A R2的矩阵为A2，Rk的矩阵为Ak.于是t(R)的矩阵记作MR+=A+A2+Ak+(+是逻辑加)置新矩阵 A:=MR;置 i=1;对所有 j,如果Aj,i=1,则对k=1,2,n Aj,k:=Aj,k+Ai,k;/*第j行+第i行,送回第j行*/i加1;如果in,则转到步骤，否则停止。下面举例，令X=1
41、,2,3,4,X中关系R图如右图所示。运行该算法求t(R)的矩阵：1。2。43第63页，本讲稿共134页i=1(i-列,j-行)A4,1=1 1行+4行4行i=2 A1,2=1,1行+2行1行 A2,2=1,2行+2行2行 A不变 A4,2=1,4行+2行4行,4行全1,A不变i=3 A1,3=1,1行+3行1行,3行全0,A不变 A2,3=1,2行+3行2行,3行全0,A不变 A4,3=1,4行+3行4行,3行全0,A不变i=4 A1,4=1,1行+4行1行 A4,4=1,4行+4行4行 A不变,最后 A=Mt(R)A=MR=A=A的初值:A=A=第64页，本讲稿共134页四.性质定理5.R
42、是A上关系，则R是自反的，当且仅当 r(R)=R.R是对称的，当且仅当 s(R)=R.R是传递的，当且仅当 t(R)=R.证明略，因为由闭包定义即可得。定理6.R是A上关系，则R是自反的，则s(R)和t(R)也自反。R是对称的，则r(R)和t(R)也对称。R是传递的，则r(R)也传递。证明:因为R自反,由定理5得r(R)=R,即RIA=R,r(s(R)=s(R)IA=(RRC)IA=(RIA)RC=r(R)RC=RRC=s(R)s(R)自反 第65页，本讲稿共134页类似可以证明t(R)也自反。证明.证明t(R)对称:(t(R)C=(RR2.Rn.)C =RC(R2)C.(Rn)C.=RC(R
43、C)2.(RC)n.=RR2.Rn.(R对称，RC=R)=t(R)所以t(R)也对称。类似可以证明r(R)也对称。证明.证明r(R)传递:先用归纳法证明下面结论:(RIA)i=IARR2.Ri i=1时 RIA=IAR 结论成立。假设ik 时结论成立，即 (RIA)k=IARR2.Rk(R2)c=(R R)c=Rc Rc=(Rc)2第66页，本讲稿共134页当i=k+1时(RIA)k+1=(RIA)k (RIA)=(IARR2.Rk）(IAR)=(IARR2.Rk)(RR2.Rk+1)=IARR2.RkRk+1所以结论成立.t(r(R)=t(RIA)=(RIA)(RIA)2(RIA)3.=(I
44、AR)(IARR2)(IARR2R3).=IARR2R3.=IAt(R)=IAR (R传递t(R)=R)=r(R)所以r(R)也传递。第67页，本讲稿共134页定理7：设R1、R2是A上关系，如果R1R2，则 r(R1)r(R2)s(R1)s(R2)t(R1)t(R2)证明 r(R1)=IAR1IAR2=r(R2)，类似可证。定理8：设R是A上关系，则 sr(R)=rs(R)tr(R)=rt(R)st(R)ts(R)证明：sr(R)=r(R)(r(R)c=(RIA)(RIA)c =(RIA)(RcIAc)=RIARcIA =(RRc)IA=s(R)IA=rs(R)的证明用前边证明的结论：(RI
45、A)k=IARR2.Rk很容易证明，这里从略。第68页，本讲稿共134页 因 Rs(R)由定理7得 t(R)ts(R)st(R)sts(R)因s(R)对称，有定理6得ts(R)也对称，由定理5得sts(R)=ts(R)所以有st(R)ts(R)。证明完毕。通常将t(R)记成R+，tr(R)记成R*，即 t(R)=R+=RR2.Rn=tr(R)=rt(R)=R*=R0RR2.Rn=练习：给定A中关系R如图所示：分别画出r(R)、s(R)、t(R)、sr(R)、rs(R)、tr(R)、rt(R)、st(R)、ts(R)的图。1。2。43Rii=1Rii=0第69页，本讲稿共134页1。2。431。
46、2。431。2。431。2。431。2。431。2。431。2。431。2。431。2。43r(R)s(R)t(R)sr(R)rs(R)tr(R)rt(R)st(R)ts(R)第70页，本讲稿共134页本节重点掌握闭包的定义、计算方法和性质。作业 第127页 、第71页，本讲稿共134页4-7 集合的划分与覆盖图书馆的图书，要分成许多类存放，学校的学生图书馆的图书，要分成许多类存放，学校的学生要按照专业分成许多班，要按照专业分成许多班，即对集合的元素划分即对集合的元素划分一一.定义定义 设X是一个非空集合,A=A1,A2,.,An,Ai AiX(i=1,2,.,n),如果满足A1A2.An=X
47、 (i=1,2,.,n)则称A为集合X的覆盖。设A=A1,A2,.,An是X一个覆盖,且AiAj=(ij,1i,jn)则称A是X的划分。每个Ai均称为这个划分的一个划分(类)。第72页，本讲稿共134页例 X=1,2,3,A1=1,2,3,A2=1,2,3,A3=1,2,3,A4=1,2,2,3,A5=1,3A1,A2,A3,A4 是覆盖。A1,A2,A3也是划分。划分,一定是覆盖；但覆盖,不一定是划分。二.最小划分与最大划分最小划分与最大划分最小划分：划分块最少的划分。即只有一个划分块的划分，这个划分块就是X本身。如A1。最大划分：划分块最多的划分。即每个划分块里只有一个元素的划分。如A2。
48、A1,A2,A3是一种划分,其中A1是最小划分,A2是最大划分。第73页，本讲稿共134页三.交叉划分 例 X是东大学生集合,A和B都是X的划分：A=M,W,MX,WX,M=男生,W=女生B=L,N,LX,NX,L=辽宁人,N=非辽宁人C=LM,LW,NM,NW 称C是X的交叉划分。MWLNLMLWNMNW辽宁男生辽宁女生非辽宁男生非辽宁女生第74页，本讲稿共134页定义：定义：若A=A1,A2,.,Am与B=B1,B2,.,Bn都是集合X的划分,则其中所有的AiBj,组成的集合C,称为C是A与B两种划分的交叉划分.(此定理的证明不讲)证明:A1,A2,.,Am与B1,B2,.,Bn的交叉划分
49、是 C=A1B1,A1B2,.,A1Bn,A2B1,A2B2,.,A2Bn,.,AmB1,AmB2,.,AmBn在C中任取元素,AiBhX (AiX,BjX)(A1B1)(A1B2).(A1Bs)(A2B1)(A2Bs).(ArB1)(ArB2).(ArBs)=(A1(B1B2B3.Bs)(A2(B1B2B3.Bs).(Ar(B1B2B3.Bs)=(A1A2A3.Ar)(B1B2B3.Bs)=XX=X第75页，本讲稿共134页再验证C中任意两个元素不相交：在C中任取两个不同元素AiBh和AjBk,考察 (AiBh)(AjBk)(i=j和h=k不同时成立)=(AiAj)(BhBk)ij,hk (
50、AiAj)(BhBk)=Ai=ij,hk (AiAj)(BhBk)=ij,h=k (AiAj)(BhBk)=Bh=综上所述，C是X的划分。作业：第130页(1)第76页，本讲稿共134页4-8 4-8 等价关系与等价类等价关系与等价类等价关系是很重要的关系，它是我们遇到最多的等价关系是很重要的关系，它是我们遇到最多的关系，例如，数值相等关系关系，例如，数值相等关系=、命题间的等价关、命题间的等价关系系、三角形相似、三角形相似和全等关系和全等关系，.一.等价关系1.定义定义:设R是A上关系,若R是自反的、对称的和传递的，则称R是A中的等价关系。若a,bA，且aRb，则称a与b等价。例子，集合A=