CH07二元关系

,*,Click to edit Master text styles,Second level,Third level,Fourth level,Click to edit Master title style,本章说明,本章的主要内容,有序对与笛卡儿积,二元关系的定义和表示法,关系的运算,关系的性质,关系的闭包,等价关系与划分,偏序关系,本章与后续各章的关系,本章是函数的基础,本章是图论的基础,1,本章内容,7.1,有序对与笛卡儿积,7.2,二元关系,7.3,关系的运算,7.4,关系的性质,7.5,关系的闭包,7.6,等价关系与划分,7.7,偏序关系,本章小结,习题,作业,2,7.1,有序对与笛卡儿积,定义7.1,由两个元素,x,和,y（,允许,x=y）,按一定顺序排列成的二元组叫做一个,有序对,(,ordered pair,),或,序偶,，记作，,其中,x,是它的第一元素，,y,是它的第二元素。,有序对,具有以下性质：,（1）当,xy,时，。,（2）,的充分必要条件是,xu,且,yv。,说明,有序对中的元素是有序的,集合中的元素是无序的,3,例7.1,例7.1,已知，,求,x,和,y。,由有序对相等的充要条件有,x+25,2,x+y4,解得,x3,y-2。,解答,4,定义7.2,设,A，B,为集合,用,A,中元素为第一元素，,B,中元素为第二元素构成有序对。所有这样的有序对组成的集合叫做,A,和,B,的,笛卡儿积,(,Cartesian product),，记作,AB。,笛卡儿积的符号化表示为,AB|xAyB,笛卡儿积的定义,A,表示某大学所有学生的集合，,B,表示大学开设的所有课程的集合，,则,AB,可以用来表示该校学生选课的所有可能情况。,令,A,是直角坐标系中,x,轴上的点集，,B,是直角坐标系中,y,轴上的点集，,于是,AB,就和平面点集一一对应。,举例,5,笛卡尔积举例,设,A=a,b, B=0,1,2，,则,AB=,BA=,举例,说明,如果,|,A|=m,|B|=n,则,|,AB|=,mn,。,6,笛卡儿积的运算性质,(1)对任意集合,A，,根据定义有,A,A,(2)一般的说，,笛卡儿积运算不满足交换律,，即,ABBA (,当,A, B, AB,时),(3),笛卡儿积运算不满足结合律,，即,(,AB)CA(BC)(,当,A, B, C,时),(4),笛卡儿积运算对并和交运算满足分配律,，即,A(B,C)=(AB),(AC),(,B,C)A=(BA),(CA)A(B,C)=(AB),(AC),(,B,C)A=(BA),(CA),(5),A,C B,D,AB,CD,7,A(BC)=(AB)(AC),的证明,任取 ,A(BC),xA yBC, xA (yByC), (xAyB) (xAyC), AB AC, (AB)(AC),所以,A(B,C)=(AB),(AC),8,关于,A,CB,D,AB,CD,的讨论,该性质的逆命题不成立，可分以下情况讨论。,（1）当,A=B=,时，显然有,A,C,和,B,D,成立。,（2）当,A,且,B,时，也有,A,C,和,B,D,成立，证明如下：,任取,xA，,由于,B,必存在,yB,因此有,xAyB,AB,CD,xCyD,xC,从而证明了,A,C。,同理可证,B,D。,9,关于,A,CB,D,AB,CD,的讨论,该性质的逆命题不成立，可分以下情况讨论。,（3）当,A,而,B,时，有,A,C,成立，但不一定有,B,D,成立。,反例：令,A,B1,C3,D4。,（4）当,A,而,B,时，有,B,D,成立，但不一定有,A,C,成立。,反例略。,从上述的讨论得到的结论是：,设集合,A,，,B,，,C,D,为四个非空集合，则,AB,CD,的充要条件是,A,CB,D,。,（,证明略）,10,例7.2,例7.2,设,A=1,2,求,P(A)A。,P(A)A,1,2,1,21,2,解答,11,例7.3,例7.3,设,A，B，C，D,为任意集合，判断以下命题是否为真，并说明理由。(1),ABAC,BC,(2),A-(BC)(A-B)(A-C),(3),ABCD,ACBD,(4) 存在集合,A，,使得,A,AA,(1),不一定为真。当,A,，B1,C2,时，有,AB,AC，,但,BC。,(2) 不一定为真。当,A=B=1,C2,时，有,A-(BC)11,(,A-B)(A-C),1,(3) 为真。由等量代入的原理可证。,(4) 为真。当,A,时，有,A,AA,成立。,解答,12,7.2 二元关系,(,binary relation),定义7.3,如果一个集合满足以下条件之一：,（1）集合非空，且它的元素都是有序对（2）集合是空集,则称该集合为一个,二元关系,，记作,R。,二元关系也可简称为,关系,。对于二元关系,R，,如果R，,可记作,xRy；,如果,R，,则记作,xRy。,设,R,1,，R,2,a,b。,则,R,1,是二元关系，,R,2,不是二元关系，只是一个集合，除非将,a,和,b,定义为有序对。,根据上面的记法可以写1,R,1,2，aR,1,b，aR,1,c,等。,举例,R,是否为二元关系？,13,集合,A,上的二元关系的数目依赖于,A,中的元素数。,如果|,A|=n，,那么|,AA|=n,2,， AA,的子集就有 个。,每一个子集代表一个,A,上的二元关系，所以,A,上有 个不同的二元关系。,例如|,A|=3，,则,A,上有 个不同的二元关系。,7.2 二元关系,定义7.4,设,A，B,为集合，,AB,的任何子集所定义的二元关系叫做,从,A,到,B,的二元关系,；特别当,A=B,时，则叫做,A,上的二元关系,。,A=0,1，B=1,2,3，,那么,R,1,=，R,2,=AB，R,3,=,，R,4,=,等都是从,A,到,B,的二元关系，而,R,3,和,R,4,同时也是,A,上的二元关系。,举例,说明,14,常用的关系,定义7.5,对任意集合,A，,定义,全域关系,E,A,=|xAyA=AA,恒等关系,I,A,=|xA,空关系,设,A=1,2，,那么,E,A,=,I,A,=,举例,15,其它常用的关系,小于或等于关系,：,L,A,=|x,yAxy，,其中,A,R。,整除关系,：,D,B,=|x,yBx,整除,y，,其中,B,Z,*,Z,*,是非零整数集,包含关系,：,R,|x,yAx,y，,其中,A,是集合族。,(1)设,A=1,2,3，Ba,b,则,L,A,=, D,A,=,(2)令,A=P(B)=,a,b,a,b，,则,A,上的包含关系是,R, , ,举例,16,例7.4,例7.4,设,A=1,2,3,4，,下面各式定义的,R,都是,A,上的关系，试用列元素法表示,R。,(1),R= | x,是,y,的倍数(2),R= | (x-y),2,A,(3),R= | x/y,是素数(4),R= | xy,解答,(1),R=,(2),R=,(3),R=,(4)R=E,A,-I,A,=, ,17,关系的表示方法,关系的三种表示方法：,集合表达式,关系矩阵,关系图,关系矩阵和关系图可以表示有穷集上的关系。,18,关系矩阵和关系图的定义,设,A=x,1,x,2,x,n,R,是,A,上的关系。令,则,是,R,的,关系矩阵,，记作,M,R,。,设,A=x,1,x,2,x,n,R,是,A,上的关系。令图,G=，,其中顶点集合,V=A，,边集为,E。,对于,x,i,x,j,V，,满足,E,x,i,Rx,j,称图,G,为,R,的,关系图,，记作,G,R,。,19,关系矩阵和关系图的实例,设,A=1,2,3,4，R=,，,则,R,的关系矩阵和关系图分别是,20,7.3 关系的运算,定义7.6,设,R,是二元关系。,(1),R,中所有有序对的第一元素构成的集合称为,R,的,定义域,(,domain),，,记为,dom R。,形式化表示为：,dom R ,x |,y(R,),(2),R,中所有有序对的第二元素构成的集合称为,R,的,值域,(,range),，记作,ran R。,形式化表示为,ran Ry |,x(R),(3),R,的定义域和值域的并集称为,R,的,域,(,field),，记作,fld R。,形式化表示为,fld Rdom R ran R,例7.5,求,R=,的定义域、值域和域。,解答,dom R1,2,4 ran R2,3,4 fld R1,2,3,4,21,关系的逆和右复合运算,定义7.7,设,R,为二元关系，,R,的逆关系，简称,R,的,逆,(,inverse,),，,记作,R,-1,其中,R,-1,|R,定义7.8,设,F,G,为二元关系，,G,对,F,的,右复合,(,composite,),记作,F,G，,其中,F,G |,t,(FG),例7.6,设,F,G=，,则,F,-1,F,GG,F,说明,可以把二元关系看作一种作用，,R,可以解释为,x,通过,R,的作用变到,y。,F,G,表示两个作用的连续发生。,22,关系的限制和像,定义7.9,设,R,为二元关系，,A,是集合,(1),R,在,A,上的,限制,(,restriction,),记作,R,A，,其中,R,A=|xRyxA,(2) A,在,R,下的,像,(,image,),记作,RA，,其中,RA=ran(R,A),说明,R,在,A,上的限制,R,A,是,R,的子关系。,A,在,R,下的像,RA,是,ran R,的子集。,23,例7.7,设,R，,R,1,，,R,R,2,3,，,R,1,2,3,R,R,3,2,24,关系与集合的说明,关系是集合，集合运算对于关系也是适用的。,规定：,关系运算中逆运算优先于其它运算,所有的关系运算都优先于集合运算，,优先权的运算以括号决定运算顺序。,例如：,ran F,-1,F,GF,H,ran (F,A),25,定理7.1,定理7.1,设,F,是任意的关系，则,(1)(,F,-1,),-1,F,(2),dom F,-1,ran F， ran F,-1,dom F,(1)任取，,由逆的定义有,(F,-1,),-1,F,-1,F,(2)任取,x,x,dom,F,-1, ,y,(F,-1,),y,(F), xran F,所以有,dom F,-1,ran F,证明,26,定理7.2,定理7.2,设,F，G，H,是任意的关系，则,(1)(,F,G),HF,(G,H),(2)(F,G),-1,G,-1, F,-1,证明,(1)任取，,(,F,G),H, ,t,(F,G(,t,y)H),t,(,s,(FG)H), ,t,s,(FGH), ,s,(F,t,(GH), ,s,(FG,H),F,(,G,H),27,定理7.2,定理7.2,设,F，G，H,是任意的关系，则,(1)(,F,G),HF,(G,H),(2)(F,G),-1,G,-1,F,-1,证明,(2)任取，,(F,G),-1,F,G,t,(FG), ,t,(F,-1,G,-1,), G,-1, F,-1,28,定理7.3,定理7.3,设,R,为,A,上的关系，则,R,I,A,I,A,RR,证明,(1)任取，,R,I,A, ,t(R(,t,y)I,A,),t(R,t,y),R,R,RyA,RI,A,),R,I,A,综上所述，有,R,I,A,R,同理可证,I,A,RR,29,定理7.4,定理7.4,设,F，G，H,是任意的关系，则(1),F,(,G,H)F,GF,H(2) (GH),F,G,F,H,F,(3),F,(,GH),F,GF,H,(4),(GH),F,G,F,H,F,证明,(3) ,F,(,GH), ,t,(F(,t,y)GH),t,(F(,t,y)G(,t,y)H), ,t,(,(,F(,t,y)G,),(,F(,t,y)H,),),t,(F(,t,y)G) ,t,(F(,t,y)H), F,G, F,H,F,GF,H,30,定理7.4的推论,由数学归纳法不难证明定理7.4的结论对于有限多个关系的并和交也是成立的，即有,R,(R,1,R,2,R,n,)R,R,1,R,R,2,R,R,n,R,1,R,2,R,n,),RR,1,RR,2,RR,n,R,R,(R,1,R,2,R,n,),R,R,1,R,R,2,R,R,n,R,1,R,2,R,n,),R,R,1,RR,2,RR,n,R,31,定理7.5,定理7.5,设,F,为关系，,A,B,为集合，则,(1),F(AB)FAFB,(2) FABFAFB,(3),F(AB)FAFB,(4),FAB,FAFB,32,定理7.5 (1)的证明,(1),F(AB)FAFB,证明,任取，,F(AB),F x(AB),F (xAxB), (FxA) (FxB), F,A F,B, F,AF,B,所以有,F(AB)FAFB。,33,定理7.5 (4)的证明,(4),FAB,FAFB,证明,任取,y，,yFAB, ,x,(F,x,AB),x,(F,x,A,x,B), ,x,(F,x,A)(F,x,B),x,(F,x,A) ,x,(F,x,B), yFA yFB,yFAFB,所以有,FAB,FAFB,34,关系的幂运算,定义7.10,设,R,为,A,上的关系，,n,为自然数，则,R,的,n,次幂,定义为：,（1）,R,0,|xAI,A,（2） R,n+1,R,n,R,说明,对于,A,上的任何关系,R,1,和,R,2,都有,R,1,0,R,2,0,I,A,即：,A,上任何关系的0次幂都相等，都等于,A,上的,恒等关系,I,A,。,对于,A,上的任何关系,R,都有,R,1,R，,因为,R,1,R,0,RI,A,RR,35,R,n,的计算,给定,A,上的关系,R,和自然数,n，,怎样计算,R,n,呢？,若,n,是0或1，结果是很简单的。下面考虑,n2,的情况。,如果,R,是用,集合表达式,给出的，可以通过,n-1,次右复合,计算得到,R,n,。,如果,R,是用,关系矩阵,M,给出的，则,R,n,的关系矩阵是,M,n,，,即,n,个矩阵,M,之积,。与普通矩阵乘法不同的是，其中的相加是逻辑加，即,1+11，1+00+11，0+00,如果,R,是用,关系图,G,给出的，可以直接由图,G,得到,R,n,的关系图,G。G,的顶点集与,G,相同。考察,G,的每个顶点,x,i,，,如果,在,G,中从,x,i,出发经过,n,步长的路径到达顶点,x,j,，,则在,G,中加一条从,x,i,到,x,j,的边,。当把所有这样的便都找到以后，就得到图,G。,36,例7.8,例7.8,设,Aa,b,c,d，R,，,求,R,的各次幂，分别用矩阵和关系图表示。,解答,37,例7.8,因此,M,4,M,2,，,即,R,4,R,2,。,因此可以得到,R,2,R,4,R,6,R,3,R,5,R,7,用关系图的方法得到,R,0, R,1, R,2, R,3,的关系图如下图所示。,38,幂运算的性质,定理7.6,设,A,为,n,元集，,R,是,A,上的关系，则存在自然数,s,和,t,使得,R,s,=R,t,。,R,为,A,上的关系，对任何自然数,k，R,k,都是,AA,的子集。,证明,又知|,AA|=n,2,，|P(AA)|= ，,即,AA,的不同子集仅 个。,当列出,R,的各次幂,R,0,，R,1,，R,2,， ，,时，,必存在自然数,s,和,t,使得,R,s,=R,t,。,说明,该定理说明有穷集上只有有穷多个不同的二元关系。当,t,足够大时，,R,t,必与某个,R,s,(s,t),相等。,如,例7.8,中的,R,4,=R,2,。,39,定理7.7,定理7.7,设,R,是,A,上的关系，,m,nN，,则,(1),R,m,R,n,R,m+n,(2)(R,m,),n,R,mn,证明,(1)对于任意给定的,mN,施归纳于,n。,若,n=0，,则有,所以对一切,m,nN,有,R,m,R,n,R,m+n,。,R,m,R,0,R,m,I,A,R,m,R,m+0,假设,R,m,R,n,=R,m+n,，,则有,R,m,R,n+1,R,m,(R,n,R),(R,m,R,n,),R,R,m+n+1,，,40,定理7.7,定理7.7,设,R,是,A,上的关系，,m,nN，,则,(1),R,m,R,n,R,m+n,(2)(R,m,),n,R,mn,证明,(2)对于任意给定的,mN,施归纳于,n。,若,n=0，,则有,所以对一切,m,nN,有(,R,m,),n,=R,mn,。,(,R,m,),0,I,A,R,0,R,m0,假设(,R,m,),n,R,mn,，,则有,(,R,m,),n+1,(R,m,),n,R,m,R,mn+m,R,m(n+1),41,定理7.8,定理7.8,设,R,是,A,上的关系，若存在自然数,s,t(st),使得,R,s,=R,t,，,则,(1) 对任何,kN,有,R,s+k,=R,t+k,(2),对任何,k,iN,有,R,s+kp+i,=R,s+i,，,其中,p=t-s,(3),令,S=R,0,，R,1,，R,t-1,，,则对于任意的,qN,有,R,q,S,证明,(1),R,s+k,R,s,R,k,R,t,R,k,R,t+k,(2),对,k,归纳。,若,k=0，,则有,R,s+0 p+i,R,s+i,假设,R,s+kp+i,R,s+i,，,其中,pt-s，,则,R,s+(k+1)p+i,R,s+kp+i+p,R,s+i,R,p,=R,s+p+i,R,s+t-s+i,R,t+i,R,s+i,由归纳法命题得证。,R,s+kp+i,R,p,42,定理7.8,定理7.8,设,R,是,A,上的关系，若存在自然数,s,t(st),使得,R,s,=R,t,，,则,(1) 对任何,kN,有,R,s+k,=R,t+k,(2),对任何,k,iN,有,R,s+kp+i,=R,s+i,，,其中,p=t-s,(3),令,S=R,0,，R,1,，R,t-1,，,则对于任意的,qN,有,R,q,S,证明,(3)任取,qN，,若,qt，,显然有,R,q,S，,若,qt，,则存在自然数,k,和,i,使得,qs+kp+i,其中0,ip-1,pt-s。,于是,R,q,R,s+kp+i,R,s+i,而,s+is+p-1,s+t-s-1,t-1,这就证明了,R,q,S。,43,定理7.8的说明,有穷集,A,上的关系,R,的幂序列,R,0,，R,1,，,是一个周期性变化的序列。就象正弦函数一样，利用它的周期性可以将,R,的高次幂化简为,R,的低次幂。,例7.9,设,A=a,b,d,e,f，R=,。,求出最小的自然数,m,和,n，,使得,mn,且,R,m,=R,n,。,解答,由,R,的定义可以看出,A,中的元素可分成两组，即,a,b,和,d,e,f。,它们在,R,的右复合运算下有下述变化规律：,abab,defdef,对于,a,或,b,每个元素的变化周期是2。对于,d，e，f，,每个元素的变化周期是3。因此必有,R,m,=R,m+6,，,其中6是2和3的最小公倍数。取,m=0,n=6,即满足题目要求。,44,7.4 关系的性质,自反性,反自反性,对称性,反对称性,传递性,45,自反性和反自反性,定义7.11,设,R,为,A,上的关系，,(1)若,x,(xA,R)，,则称,R,在,A,上是,自反,(,reflexivity,),的。,(2)若,x(xA,R)，,则称,R,在,A,上是,反自反,(,irreflexivity,),的。,例如,全域关系,E,A,，,恒等关系,I,A,，,小于等于关系,L,A,，,整除关系,D,A,都是为,A,上的,自反关系,。,包含关系,R,是给定集合族,A,上的,自反关系,。,小于关系,和,真包含关系,都是给定集合或集合族上的,反自反关系,。,46,例7.10,例7.10,设,A=1,2,3，R,1,，R,2,，R,3,是,A,上的关系，其中,R,1,R,2,R,3,说明,R,1,，R,2,和,R,3,是否为,A,上的自反关系和反自反关系。,解答,R,1,既不是自反的也不是反自反的，,R,2,是自反的，,R,3,是反自反的。,47,对称性和反对称性,定义7.12,设,R,为,A,上的关系，,（1）若,x,y(x,yARR)，,则称,R,为,A,上,对称,(,symmetry,),的关系。,（2）若,x,y(x,yARRx=y)，,则称,R,为,A,上的,反对称,(,antisymmetry,),关系。,例如,A,上的,全域关系,E,A,，,恒等关系,I,A,和,空关系,都是,A,上的,对称关系,。,恒等关系,I,A,和,空关系,也是,A,上的,反对称,关系。,但全域关系,E,A,一般不是,A,上的反对称关系，除非,A,为单元集或空集。,48,例7.11,例7.11,设,A1,2,3，R,1,，R,2,，R,3,和,R,4,都是,A,上的关系，其中,R,1,R,2,R,3,R,4,说明,R,1,，R,2,，R,3,和,R,4,是否为,A,上对称和反对称的关系。,解答,R,1,既是对称也是反对称的。,R,2,是对称的但不是反对称的。,R,3,是反对称的但不是对称的。,R,4,既不是对称的也不是反对称的。,49,传递性,定义7.13,设,R,为,A,上的关系，若,x,y,z(x,y,zARRR),则称,R,是,A,上的,传递,(,transitivity,),关系。,例如,A,上的,全域关系,E,A,恒等关系,I,A,和,空关系,都是,A,上的,传递关系,。,小于等于关系,，,整除关系,和,包含关系,也是相应集合上的,传递关系,。,小于关系,和,真包含关系,仍旧是相应集合上的传递关系。,50,例7.12,例7.12,设,A1,2,3，R,1,，R,2,，R,3,是,A,上的关系，其中,R,1,R,2,R,3,说明,R,1,，R,2,和,R,3,是否为,A,上的传递关系。,解答,R,1,和,R,3,是,A,上的传递关系，,R,2,不是,A,上的传递关系。,51,关系性质的等价描述,定理7.9,设,R,为,A,上的关系，则,（1）,R,在,A,上自反当且仅当,I,A,R,（2）R,在,A,上反自反当且仅当,RI,A,（3）R,在,A,上对称当且仅当,RR,-1,（4）R,在,A,上反对称当且仅当,RR,-1,I,A,（5）R,在,A,上传递当且仅当,R,R,R,说明,利用该定理可以从关系的集合表达式来判断或证明关系的性质。,分析,关系性质的证明方法,52,定理7.9 (1)的证明,（1）,R,在,A,上自反当且仅当,I,A,R,必要性,。,任取，,有,I,A,x,yA xy,R,所以,I,A,R,充分性,。,任取,x,，,有,x,A,I,A,R,所以,R,在,A,上是自反的。,53,定理7.9 (2)的证明,（2）R,在,A,上反自反当且仅当,RI,A,充分性。,任取,x，,有,xA,I,A,R (RI,A,=,),所以,R,在,A,上是反自反的。,必要性。用反证法。,假设,RI,A,，,必存在RI,A,。,由于,I,A,是,A,上恒等关系，,可知,xA,且R。,这与,R,在,A,上是反自反的相矛盾。,54,定理7.9 (3)的证明,（3） R,在,A,上对称当且仅当,RR,-1,必要性。,任取，,有,R,R(,因为,R,在,A,上对称),R,-1,所以,RR,-1,充分性。,任取，,由,RR,-1,得,R,R,-1,R,所以,R,在,A,上是对称的。,55,定理7.9 (4)的证明,（4） R,在,A,上反对称当且仅当,RR,-1,I,A,必要性。,任取，,有,RR,-1,R R,-1,R R,xy (R,是反对称的),I,A,所以,RR,-1,I,A,充分性。,任取,则有, R R,R R,-1,RR,-1,I,A,(RR,-1,I,A,),xy,所以,R,在,A,上是反对称的。,56,定理7.9 (5)的证明,（5） R,在,A,上传递当且仅当,R,R,R,必要性,。任取，,有,R,R,t,(RR),R(,因为,R,在,A,上是传递的),所以,R,R,R。,充分性,。任取,R，,则, RR,R,R,R (,因为,R,R,R,),所以,R,在,A,上是传递的。,57,例7.13,例7.13,设,A,是集合，,R,1,和,R,2,是,A,上的关系，证明：,(1)若,R,1,，R,2,是自反的和对称的，则,R,1,R,2,也是自反的和对称的。,(2)若,R,1,和,R,2,是传递的，则,R,1,R,2,也是传递的。,58,例7.13 (1)的证明,(1)若,R,1,，R,2,是自反的和对称的，则,R,1,R,2,也是自反的和对称的。,证明,由于,R,1,和,R,2,是,A,上的自反关系，故有,I,A,R,1,和,I,A,R,2,从而得到,I,A,R,1,R,2,。,根据定理7.9可知,R,1,R,2,在,A,上是自反的。,再由,R,1,和,R,2,的对称性有,R,1,R,1,-1,和,R,2,R,2,-1,根据练习七第18题的结果有,(,R,1,R,2,),-1,R,1,-1,R,2,-1,R,1,R,2,从而证明了,R,1,R,2,也是,A,上对称的关系。,59,例7.13 (2)的证明,(2)若,R,1,和,R,2,是传递的，则,R,1,R,2,也是传递的。,证明,由,R,1,和,R,2,的传递性有,R,1,R,1,R,1,和,R,2,R,2,R,2,再使用定理7.4得,(,R,1,R,2,),(R,1,R,2,),R,1,R,1,R,1,R,2,R,2,R,1,R,2,R,2,(R,1,R,2,)R,1,R,2,R,2,R,1, (,将前面的包含式代入),R,1,R,2,从而证明了,R,1,R,2,也是,A,上的传递关系。,60,关系性质的特点,61,例7.14,例7.14,判断下图中关系的性质，并说明理由。,（1）对称的，不是自反的，不是反自反的，不是反对称的，不是传递的。,（2）是反自反的，不是自反的，是反对称的，不是对称的，是传递的,。,（3）,是自反的，不是反自反的，是反对称的，不是对称的，不是传递的。,62,关系的性质和运算之间的关系,63,问题,如果存在一条从数据中心,a,到,b,的电话线，,就属于关系,R。,如何确定从一个中心是否有一条电话线(可能不直接)链接到另一个中心？,通过构造,包含,R,的,最小,的,传递关系,来找出每一对有着联系的数据中心，这个关系叫做,R,的,传递闭包,。,波士顿,芝加哥,丹佛,底特律,圣地亚哥,纽约,64,7.5 关系的闭包,闭包（,closure,）,的定义,闭包的构造方法,闭包的性质,闭包的相互关系,65,闭包的定义,定义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),。,66,闭包的构造方法,定理7.10,设,R,为,A,上的关系，则有,（1）,r(R),R,R,0,（2）,s(R),R,R,-1,（3）,t(R),R,R,2,R,3,证明思路,(1)和(2)：证明右边的集合满足闭包定义的三个条件。,(3)采用集合相等的证明方法。,证明左边包含右边，即,t(R),包含每个,R,n,。,证明右边包含左边，即,R,R,2,具有传递的性质。,67,定理7.10 (1)的证明,（1）,r(R)RR,0,证明,由,I,A,R,0,RR,0,，,可知,RR,0,是自反的，,R,RR,0,。,设,R,是,A,上包含,R,的自反关系，,则有,R,R,和,I,A,R,。,任取，,必有,RR,0,RI,A,R,R,R,所以,RR,0,R,。,综上所述，,r(R),RR,0,。,68,定理7.10 (2)的证明,（2）,s(R)RR,-1,证明,R,RR,-1,。,证明,RR,-1,是对称的，,任取，,有,RR,-1,RR,-1,R,-1,R,RR,-1,所以,RR,-1,是对称的,。,综上所述，,s(R),RR,-1,。,设,R,是包含,R,的,对称关系，,任取，,有,RR,-1,RR,-1,RR,R,R,R,R,R,所以,RR,-1,R,。,69,定理7.10 (3)的证明,（3）,t(R)RR,2,R,3,证明,先证,RR2,t(R),成立，为此只需证明对任意的正整数,n,有,R,n,t(R),即可。用归纳法。,n1,时，有,R,1,R,t(R)。,假设,R,n,t(R),成立，那么对任意的,有,R,n+1,R,n,R,t,(R,n,R),t,(t(R),t,(R),t(R) （,因为,t(R),是传递的）,这就证明了,R,n+1,t(R)。,由归纳法命题得证。,70,定理7.10 (3)的证明,（3）,t(R)RR,2,R,3,证明,再证,t(R),RR,2,成立，为此只须证明,RR,2,是传递的。,任取,，,则,RR,2, RR,2,t,(R,t,) ,s,(R,s,),t,s,(R,t, R,s,),t,s,(R,t,R,s,),t,s,(R,t,+,s,),RR,2,从而证明了,RR,2,是传递的。,71,推论,推论,设,R,为有穷集,A,上的关系，则存在正整数,r,使得,t(R)=RR,2,R,r,证明,由定理7.6和7.10(3)得证。,例题,求整数集合,Z,上的关系,R | ab,的自反闭包和对称闭包。,解答,r(R)RR,0,|a|ab,|ab,s(R)RR,-1,|a|ba,|ab,72,通过关系矩阵求闭包的方法,设关系,R，r(R)，s(R)，t(R),的关系矩阵分别为,M，M,r,，M,s,和,M,t,，,则,M,r, ME,对角线上的值都改为1,M,s, MM,若,a,ij,1，,则令,a,ji,1,M,t, MM,2,M,3,沃舍尔算法,其中,E,是和,M,同阶的单位矩阵，,M,是,M,的转置矩阵。,注意在上述等式中矩阵的元素相加时使用逻辑加。,73,通过关系图求闭包的方法,设关系,R，r(R)，s(R)，t(R),的关系图分别记为,G，G,r,，G,s,，G,t,，,则,G,r,，G,s,，G,t,的顶点集与,G,的顶点集相等。,除了,G,的边以外，以下述方法,添加新的边,。,1)考察,G,的每个顶点，如果,没有环就加上一个环,。最终得到的是,G,r,。,2),考察,G,的每一条边，,如果有一条,x,i,到,x,j,的单向边,，,ij，,则在,G,中,加一条边,x,j,到,x,i,的反方向边,。最终得到,G,s,。,3),考察,G,的每个顶点,x,i,，,找出从,x,i,出发的所有2步，3步，,n,步长的路径,（,n,为,G,中的顶点数）。,设路径的终点为 。如果没有从,x,i,到 (,l=1,2,k),的边，就加上这条边。当检查完所有的顶点后就得到图,G,t,。,74,例7.15,例7.15,设,A=a,b,c,d，R=,，,则,R,和,r(R)，s(R)，t(R),的关系图如下图所示。其中,r(R)，s(R)，t(R),的关系图就是使用上述方法直接从,R,的关系图得到的。,75,Warshall 算法,输入：,M（R,的关系矩阵）,输出：,M,T,（t(R),的关系矩阵,）,1.,M,T,M,2.for,k, 1 to n do,3.for,i, 1 to n do,4.for,j, 1 to n do,5. M,T,i,j,M,T,i,j,+M,T,i,k,*M,T,k,j,注意：算法中矩阵加法和乘法中的元素相加都使用逻辑加。,76,Warshall 算法 举例,例,设,A=a,b,c,d，R=,，,求,t(R),。,分析,k,1,时，,M,T,i,jM,T,i,j+M,T,i,1,*M,T,1,j,M,T,1,jM,T,1,j+M,T,1,1,*M,T,1,j,M,T,2,jM,T,2,j+M,T,2,1,*M,T,1,j,将第,1,行加到第,2,行上,M,T,3,jM,T,3,j+M,T,3,1,*M,T,1,j,M,T,4,jM,T,4,j+M,T,4,1,*M,T,1,j,得到,M,1,。,77,Warshall 算法 举例,k,1,时，第,1,列中只有,M,2,1,1，,将第,1,行加到第,2,行上。,k,2,时，第,2,列中,M,1,2, M,2,2,M,4,2,1，,将第,2,行分别加到第,1,2,4,行上。,78,Warshall 算法 举例,k,3,时，第,3,列中,M,1,3,M,2,3,M,4,3,1，,将第,3,行分别加到第,1,2,4,行上。,k,4,时，第,4,列中,M,1,4, M,2,4,M,3,4M,4,4,1，,将第,4,行分别加到第,1,2,3,4,行上。,79,闭包的主要性质,定理7.11,设,R,是非空集合,A,上的关系，则,（1）,R,是自反的当且仅当,r(R)R。,（2）R,是对称的当且仅当,s(R)R。,（3）R,是传递的当且仅当,t(R)R。,证明,（1）充分性。,因为,Rr(R)，,所以,R,是自反的。,必要性。,显然有,R,r(R)。,由于,R,是包含,R,的自反关系，根据自反闭包定义有,r(R),R,。,从而得到,r(R)=R。,80,闭包的主要性质,定理7.12,设,R,1,和,R,2,是非空集合,A,上的关系，且,R,1,R,2,，,则,（1）,r(R,1,),r(R,2,),（2）s(R,1,),s(R,2,),（3）t(R,1,),t(R,2,),证明：(1)任取，,有,r(R,1,),R,1,I,A,R,1,I,A,R,2, I,A,R,2,I,A,r(R,2,),81,命题,命题,若,R,是对称的，则,R,n,也是对称的，其中,n,是任何正整数。,证明,用归纳法。,n=1，R,1,R,显然是对称的。,假设,R,n,是对称的，则对任意的，,有,R,n+1,R,n,R, , ,t,(R,n,R), , ,t,(R,n,R), ,R,R,n,R,1+n,R,n+1,所以,R,n+1,是对称的。由归纳法命题得证。,82,关系性质与闭包运算之间的联系,定理7.13,设,R,是非空集合,A,上的关系，,（1）若,R,是自反的，则,s(R),与,t(R),也是自反的。,（2）若,R,是对称的，则,r(R),与,t(R),也是对称的。,（3）若,R,是传递的，则,r(R),是传递的。,证明：只证（2）。,83,定理7.13 (2)的证明,（2）若,R,是对称的，则,r(R),与,t(R),也是对称的。,证明,r(R),是对,称的。,由于,R,是,A,上的对称关系，所以,RR,-1,，,同时,I,A,I,A,-1,。,r(R),-1,(RR,0,),-1,(RI,A,),-1,R,-1,I,A,-1,RI,A,r(R),所以，,r(R),是对称的。,84,定理7.13 (2)的证明,（2）若,R,是对称的，则,r(R),与,t(R),也是对称的。,下面证明,t(R),的对称性。,任取,t(R),n,(R,n,),n,(R,n,) （,因为,R,n,是对称的）,t(R),所以，,t(R),是,对称的。,85,定理7.13的讨论,从这里可以看出，如果计算关系,R,的自反、对称、传递的闭包，,为了不失去传递性，传递闭包运算应该放在对称闭包运算的后边,，若令,tsr(R),表示,R,的自反、对称、传递闭包，则,tsr(R)=t(s(r(R),反例,A=1，2，3，R=,是传递的,s(R)=,显然,s(R),不是传递的。,86,7.6 等价关系与划分,定义7.15,设,R,为非空集合,A,上的关系。如果,R,是,自反的,、,对称的,和,传递的,，则称,R,为,A,上的,等价关系,(,equivalent relation,),。设,R,是一个等价关系，若R，,称,x,等价于,y，,记做,xy。 (,同时具有三种性质,),举例,(1)平面上三角形集合中，三角形的相似关系。,(2)人群中的同性关系。,朋友关系 同学关系,87,例7.16,例7.16,设,A1,2,8，,如下定义,A,上的关系,R：R|x，yAxy(mod 3),其中,xy(mod 3),叫做,x,与,y,模3相等,，即,x,除以3的余数与,y,除以3的余数相等。不难验证,R,为,A,上的等价关系，因为,xA，,有,xx(mod 3),x,yA，,若,xy(mod 3)，,则有,yx(mod 3),x,y,zA，,若,xy(mod 3)，yz(mod 3)，,则有,xz(mod 3),88,等价类,定义7.16,设,R,为非空集合,A,上的等价关系，,xA，,令,x,R,=y|yAxRy,称,x,R,为,x,关于,R,的,等价类,，简称为,x,的,等价类,，简记为,x,或,x 。,x,的等价类是,A,中所有与,x,等价的元素构成的集合。,例,7.16,中的等价类是：,1471,4,7,2582,5,8,363,6,89,整数集合Z上的模n等价关系,设,x,是任意整数，,n,为给定的正整数，则存在唯一的整数,q,和,r，,使得,xqn+r,其中,0,rn-1,，,称,r,为,x,除以,n,的余数,。,例如,n3，,那么8除以3的余数为1，因为 -8-33+1,对于任意的整数,x,和,y，,定义,模,n,相等关系,xy,xy(mod n),不难验证它是整数集合,Z,上的等价关系。,将,Z,中的所有整数根据它们除以,n,的余数分类如下：,余数为,0,的数，其形式