第七章 二元关系精选PPT.ppt

《第七章 二元关系精选PPT.ppt》由会员分享，可在线阅读，更多相关《第七章 二元关系精选PPT.ppt（99页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第七章第七章二元关系二元关系1第1页，本讲稿共99页7.1有序对与笛卡儿积有序对与笛卡儿积定义定义7.1由两个元素由两个元素x 和和y，按照一定的顺序组成的二元组，按照一定的顺序组成的二元组称为称为有序对有序对(序偶序偶)，记作，记作.有序对性质有序对性质:(1)有序性有序性（当（当x y时）时）(2)与与相等的充分必要条件是相等的充分必要条件是=x=u y=v.注：与二元集的区别注：与二元集的区别2第2页，本讲稿共99页例例 已知已知=,=,求求x x和和y.y.3第3页，本讲稿共99页笛卡儿积笛卡儿积定义定义7.2设设A,B为集合，为集合，A与与B的的笛卡儿积笛卡儿积记作记作A B，且，且

2、A B=|x A y B.例1A=1,2,3,B=a,b,c AB=,BA=,A=,B=P(A)A=,P(A)B=4第4页，本讲稿共99页笛卡儿积的性质笛卡儿积的性质(1)不适合交换律不适合交换律A B B A(A B,A,B)(2)不适合结合律不适合结合律(A B)C A(B C)(A,B,C)(3)对于并或交运算满足分配律对于并或交运算满足分配律A(B C)=(A B)(A C)(B C)A=(B A)(C A)A(B C)=(A B)(A C)(B C)A=(B A)(C A)(4)若若A 或或B 中有一个为空集，则中有一个为空集，则A B 就是空集就是空集.A=B=(5)若若|A|=m

3、,|B|=n,则则|A B|=mn(6)A CB DAB CD5第5页，本讲稿共99页性质证明性质证明证明证明A(B C)=(A B)(A C)证证任取任取A(BC)xAyBC xA(yByC)(xAyB)(xAyC)ABAC(AB)(AC)所以有所以有A(BC)=(AB)(AC).6第6页，本讲稿共99页性质性质6 6的逆命题不成立的逆命题不成立,分以下情况讨论分以下情况讨论.(1)(1)当当A=B=A=B=时时,显然有显然有A A C C和和B B D D成立成立.(2)(2)当当AA且且BB时时,也有也有A A C C和和B B D D成立成立,证明如下：证明如下：任取任取xA,xA,由

4、于由于B B,必存在必存在yB,yB,因此有因此有xAyBxAyBABABCDCDxCyD xCyD xCxC 从而证明了从而证明了A A C C.同理可证同理可证B B D.D.(3)(3)当当A=A=而而BB时时,有有A A C C成立成立,但不一定有但不一定有B B D D成立成立.反例：令反例：令A=A=,B=1,C=3,D=4.,B=1,C=3,D=4.(4)(4)当当AA而而B=B=时时,有有B B D D成立成立,但不一定有但不一定有A A C C成立成立.7第7页，本讲稿共99页实例实例例例2(1)证明证明A=B,C=D A C=B D(2)A C=B D是否推出是否推出A=B

5、,C=D?为什么？为什么？(3)AB=ACB=C(4)A-(BC)=(A-B)(A-C)(5)存在集合存在集合A,使得使得A AA解(1)任取ACxAyCxByDBD(2)不一定.反例如下：A=1，B=2,C=D=,则AC=BD但是A B.8第8页，本讲稿共99页解解 (3)(3)不一定为真不一定为真.当当A=A=,B=1,C=2,B=1,C=2时时,有有AB=AC,AB=AC,但但BC.BC.(4)(4)不一定为真不一定为真.当当A=B=1,C=2A=B=1,C=2时有时有 A-(BC)=1=1A-(BC)=1=1(A-B)(A-C)=(A-B)(A-C)=1=1=(5)(5)为真为真.当当

6、A=A=时有时有A A AA AA成立成立 9第9页，本讲稿共99页7.2 二元关系二元关系定义定义7.3如果一个集合满足以下条件之一：如果一个集合满足以下条件之一：(1)集合非空集合非空,且它的元素都是且它的元素都是有序对有序对(2)集合是空集集合是空集则称该集合为一个则称该集合为一个二元关系二元关系,简称为关系，记作简称为关系，记作R.如果如果R,可记作可记作xRy；如果；如果 R,则记作则记作xy实例：实例：R=,S=,a,b.R是二元关系是二元关系,当当a,b不是有序对时，不是有序对时，S不是二元关系不是二元关系根据上面的记法，可以写根据上面的记法，可以写1R2,aRb,a c等等.1

7、0第10页，本讲稿共99页A到到B的关系与的关系与A上的关系上的关系定义定义7.4设设A,B为集合为集合,AB的任何子集所定义的二元关系叫做的任何子集所定义的二元关系叫做从从A到到B的二元关系的二元关系,当当A=B时则叫做时则叫做A上的二元关系上的二元关系.例例3A=0,1,B=1,2,3,那么那么R1=,R2=AB,R3=,R4=R1,R2,R3,R4是从是从A 到到B 的二元关系的二元关系,R3和和R4也是也是A上的二元关系上的二元关系.计数计数:|A|=n,|AA|=n2,AA的子集有的子集有个个.所以所以A上有上有个不同的二元关系个不同的二元关系.例如例如|A|=3,则则A上有上有=5

8、12个不同的二元关系个不同的二元关系.11第11页，本讲稿共99页A上重要关系的实例上重要关系的实例定义定义7.5设设A 为集合为集合,(1)是是A上的关系，称为上的关系，称为空关系空关系(2)全域关系全域关系EA=|xAyA=AA 恒等关系恒等关系IA=|xA小于等于关系小于等于关系 LA=|x,yAxy,A为实数子集为实数子集 整除关系整除关系DB=|x,yBx整除整除y,A为非为非0整数子集整数子集 包含关系包含关系 R=|x,yAx y,A是集合族是集合族.12第12页，本讲稿共99页实例实例例如例如,A=1,2,则则EA=,IA=,例如例如A=1,2,3,B=a,b,则则LA=,DA

9、=,例如例如A=P(B)=,a,b,a,b,则则A上的包含关系是上的包含关系是R=,类似的还可以定义：类似的还可以定义：大于等于关系大于等于关系,小于关系小于关系,大于关系大于关系,真包含关系等真包含关系等.13第13页，本讲稿共99页关系的表示关系的表示1.关系矩阵关系矩阵若若A=x1,x2,xm，B=y1,y2,yn，R是从是从A到到B的的关系，关系，R的的关系矩阵关系矩阵是布尔矩阵是布尔矩阵MR=rijm n,其中其中rij=1 R.即即则则14第14页，本讲稿共99页关系的表示关系的表示2.关系图关系图若若A=x1,x2,xm，R是从是从A上的关系，上的关系，R的关系图是的关系图是GR

10、=,其中其中A为结点集，为结点集，E为边集为边集.如果如果属于属于关系关系R，在图中就有一条从，在图中就有一条从xi 到到xj 的的有向边有向边.注意：注意：l关系矩阵适合表示从关系矩阵适合表示从A到到B的关系或的关系或A上的关系（上的关系（A,B为有为有穷集）穷集）l关系图适合表示有穷集关系图适合表示有穷集A上的关系上的关系即即ExiRxj15第15页，本讲稿共99页实例实例例例4 A=1,2,3,4,R=,R的关系矩阵的关系矩阵MR和关系图和关系图GR如下：如下：16第16页，本讲稿共99页7.3关系的运算关系的运算*基本概念基本概念1.1.定义域、值域、域、逆关系定义域、值域、域、逆关系

11、 关系的基本运算有七种关系的基本运算有七种,分别定义如下：分别定义如下：定义定义7.6 7.6 设设R R是二元关系是二元关系.(1)R(1)R中所有的有序对的第一元素构成的集合称为中所有的有序对的第一元素构成的集合称为R R的定义域的定义域,记为记为domR.domR.形式化表示为：形式化表示为：domR=x|y(R)17第17页，本讲稿共99页(2)R(2)R中所有有序对的第二元素构成的集合称为中所有有序对的第二元素构成的集合称为R R的值域的值域,记作记作ranR.ranR.形式化表示为形式化表示为 ranR=y|ranR=y|x(R)x(R)(3)R(3)R的定义域和值域的并集称为的定

12、义域和值域的并集称为R R的域的域,记作记作fldR.fldR.形式化形式化表示为表示为 fldR=domRranRfldR=domRranR例例5 5 设设R=,R=,则则 domR=1,2,4 domR=1,2,4 ranR=2,3,4 ranR=2,3,4 fldR=1,2,3,4 fldR=1,2,3,47.3关系的运算关系的运算18第18页，本讲稿共99页关系运算关系运算(逆与合成逆与合成)定义定义7.7关系的关系的逆运逆运算算 R 1=|R 定义定义7.8关系的关系的合成合成运算运算 R S=|y(R S)例6R=,S=,R1=,RS=,SR=,19第19页，本讲稿共99页合成的图

13、示法合成的图示法利用图示（不是关系图）方法求合成利用图示（不是关系图）方法求合成R S=,S R=,20第20页，本讲稿共99页关系运算关系运算(限制与像限制与像)定义定义7.9设设R为二元关系为二元关系,A是集合是集合(1)R在在A上的上的限制限制记作记作 R A,其中其中R A=|xRyxA(2)A在在R下的下的像像记作记作RA,其中其中RA=ran(R A)说明：说明：lR在在A上的限制上的限制R A是是R 的子关系，即的子关系，即R A RlA在在R下的像下的像RA是是ranR 的子集，即的子集，即RA ranR21第21页，本讲稿共99页实例实例例例7设设R=,则则R 1=,R=R

14、2,3=,R1=2,3R=R3=222第22页，本讲稿共99页关系运算的性质关系运算的性质定理定理7.1设设F是任意的关系是任意的关系,则则(1)(F 1)1=F(2)domF 1=ranF,ranF 1=domF证证(1)任取任取,由逆的定义有由逆的定义有(F 1)1F 1F.所以有所以有(F 1)1=F.(2)任取任取x,xdomF 1 y(F 1)y(F)xranF所以有所以有domF 1=ranF.同理可证同理可证ranF 1=domF.23第23页，本讲稿共99页定理定理7.2设设F,G,H是任意的关系是任意的关系,则则(1)(F G)H=F(G H)(2)(F G)1=G 1 F

15、1关系运算的性质关系运算的性质证证(1)任取任取,(F G)H t(F GH)t(s(FG)H)t s(FGH)s(F t(GH)s(FG H)F(G H)所以所以(F G)H=F(G H)24第24页，本讲稿共99页证明证明(2)任取任取,(F G)1F G t(FG)t(G 1F 1)G 1 F 1所以所以(F G)1=G 1 F 125第25页，本讲稿共99页关系运算的性质关系运算的性质定理定理7.3设设R为为A上的关系上的关系,则则R IA=IA R=R证证任取任取R IA t(RIA)t(Rt=yyA)R26第26页，本讲稿共99页关系运算的性质关系运算的性质定理定理7.4(1)F(

16、G H)=F GF H (2)(GH)F=G FH F(3)F(GH)F GF H (4)(GH)F G FH F只证只证(3)任取任取,F(GH)t(FGH)t(FGH)t(FG)(FH)t(FG)t(FH)F GF HF GF H所以有所以有F(GH)=F GF H27第27页，本讲稿共99页推广推广定理定理7.4的结论可以推广到有限多个关系的结论可以推广到有限多个关系R(R1R2Rn)=R R1R R2R Rn(R1R2Rn)R=R1 RR2 RRn RR(R1R2Rn)R R1R R2R Rn(R1R2Rn)R R1 RR2 RRn R28第28页，本讲稿共99页关系运算的性质关系运算

17、的性质定理定理7.5设设F 为关系为关系,A,B为集合为集合,则则(1)F (AB)=F AF B(2)F AB=F AF B(3)F (AB)=F AF B(4)F AB F AF B29第29页，本讲稿共99页证明证明证证只证只证(1)和和(4).(1)任取任取F (AB)FxABF(xAxB)(FxA)(FxB)F AF BF AF B所以有所以有F (AB)=F AF B.30第30页，本讲稿共99页证明证明(4)任取任取y,yF AB x(FxAB)x(FxAxB)x(FxA)(FxB)x(FxA)x(FxB)yF AyF ByF AF B所以有所以有F AB=F AF B.31第3

18、1页，本讲稿共99页关系的幂运算关系的幂运算定义定义7.10设设R 为为A 上的关系上的关系,n为自然数为自然数,则则R 的的n 次幂次幂定义为：定义为：(1)R0=|xA=IA(2)Rn+1=Rn R注意：注意：l对于对于A上的任何关系上的任何关系R1和和R2都有都有R10=R20=IAl对于对于A上的任何关系上的任何关系R 都有都有R1=R32第32页，本讲稿共99页例例8设设A=a,b,c,d,R=,求求R的各次幂的各次幂,分别用矩阵和关系图表示分别用矩阵和关系图表示.解解 R 与与 R2的关系矩阵分别是：的关系矩阵分别是：幂的求法幂的求法33第33页，本讲稿共99页R3和和R4的矩的矩

19、阵阵是：是：因此因此M4=M2,即即R4=R2.因此可以得到因此可以得到R2=R4=R6=，R3=R5=R7=R0的关系矩阵是的关系矩阵是幂的求法幂的求法34第34页，本讲稿共99页关系图关系图R0,R1,R2,R3,的关系图如下图所示的关系图如下图所示.R0R1R2=R4=R3=R5=35第35页，本讲稿共99页幂运算的性质幂运算的性质定理定理7.6设设A 为为n 元集元集,R 是是A上的关系上的关系,则存在自然数则存在自然数s 和和t,使得使得Rs=Rt.证证R 为为A上的关系上的关系,由于由于|A|=n,A上的不同关系只有上的不同关系只有个个.列出列出R 的各次幂的各次幂 R0,R1,R

20、2,必存在自然数必存在自然数s 和和t 使得使得Rs=Rt 36第36页，本讲稿共99页定理定理7.7设设R 是是A上的关系上的关系,m,nN,则则(1)Rm Rn=Rm+n(2)(Rm)n=Rmn幂运算的性质幂运算的性质证证用归纳法用归纳法(1)对于任意给定的对于任意给定的mN,施归纳于施归纳于n.若若n=0,则有则有Rm R0=Rm IA=Rm=Rm+0 假设假设Rm Rn=Rm+n,则有则有Rm Rn+1=Rm (Rn R)=(Rm Rn)R=Rm+n+1,所以对一切所以对一切m,nN有有Rm Rn=Rm+n.37第37页，本讲稿共99页证明证明(2)对于任意给定的对于任意给定的mN,施

21、归纳于施归纳于n.若若n=0,则有则有(Rm)0=IA=R0=Rm0假设假设(Rm)n=Rmn,则有则有(Rm)n+1=(Rm)n Rm=(Rmn)Rn =Rmn+m=Rm(n+1)所以对一切所以对一切m,nN有有(Rm)n=Rmn.38第38页，本讲稿共99页定理定理7.8设设R是是A上的关系上的关系,若存在自然数若存在自然数s,t(st)使得使得Rs=Rt,则则(1)对对任何任何kN有有Rs+k=Rt+k(2)对对任何任何k,iN有有Rs+kp+i=Rs+i,其中其中p=t s(3)令令S=R0,R1,Rt 1,则对则对于任意的于任意的qN有有RqS幂运算的性质幂运算的性质证(1)Rs+k

22、=RsRk=Rt Rk=Rt+k(2)对k归纳.若k=0,则有Rs+0p+i=Rs+i假设Rs+kp+i=Rs+i,其中p=ts,则Rs+(k+1)p+i=Rs+kp+i+p=Rs+kp+iRp=Rs+iRp=Rs+p+i=Rs+ts+i=Rt+i=Rs+i由归纳法命题得证.39第39页，本讲稿共99页证明证明(3)任取任取 qN,若若 q t,显然有显然有 RqS,若若q t,则存在自然数则存在自然数 k 和和 i 使得使得 q=s+kp+i,其中其中0ip 1.于是于是Rq=Rs+kp+i=Rs+i 而而s+i s+p 1=s+t s 1=t 1从而从而证明了证明了RqS.40第40页，本

23、讲稿共99页7.4关系的性质关系的性质定义定义7.11设设R 为为A上的关系上的关系,(1)若若 x(xA R),则称则称R 在在A 上是上是自反自反的的.(2)若若 x(xA R),则称则称R 在在A 上是上是反自反反自反的的.实例：自反：全域关系EA,恒等关系IA,小于等于关系LA,整除关系DA反自反：实数集上的小于关系、幂集上的真包含关系.A=1,2,3,R1,R2,R3是A上的关系,其中 R1,R2,R3R2自反，R3反自反，R1既不是自反的也不是反自反的.41第41页，本讲稿共99页对称性与反对称性对称性与反对称性定义定义7.12设设R 为为A上的关系上的关系,(1)若若 x y(x

24、,yARR),则称则称R 为为A上上对对称称的关系的关系.(2)若若 x y(x,yARRx=y),则称则称R 为为A上的上的反对称反对称关系关系.实例：对称关系：A上的全域关系EA,恒等关系IA和空关系反对称关系：恒等关系IA和空关系也是A上的反对称关系.设A1,2,3,R1,R2,R3和R4都是A上的关系,其中 R1,，R2,R3,，R4,R1：对称和反对称；R2：只有对称；R3：只有反对称；R4：不对称、不反对称42第42页，本讲稿共99页传递性传递性定义定义7.13设设R为为A上的关系上的关系,若若 x y z(x,y,zARRR),则称则称R 是是A上的上的传递传递关系关系.实例：A

25、上的全域关系EA,恒等关系IA和空关系，小于等于和小于关系，整除关系，包含与真包含关系设A1,2,3,R1,R2,R3是A上的关系,其中 R1,R2,R3R1和R3是A上的传递关系,R2不是A上的传递关系.43第43页，本讲稿共99页关系性质成立的充要条件关系性质成立的充要条件定理定理7.9设设R为为A上的关系上的关系,则则(1)R 在在A上自反上自反当且仅当当且仅当 IA R(2)R 在在A上反自反上反自反当且仅当当且仅当 RIA=(3)R 在在A上对称上对称当且仅当当且仅当 R=R 1(4)R 在在A上反对称上反对称当且仅当当且仅当 RR 1 IA(5)R 在在A上传递上传递当且仅当当且仅

26、当 R R R 44第44页，本讲稿共99页证明证明证明证明只证只证(1)(1)必要性必要性任取任取,由于由于R 在在A上自反必有上自反必有IA x,yAx=y R从而证明了从而证明了IA R充分性充分性.任取任取x,有有xA IA R因此因此R 在在A上是自反的上是自反的.45第45页，本讲稿共99页自反性自反性反自反性反自反性对称性对称性反对称性反对称性传递性传递性集合集合IA RRIA=R=R 1RR 1 IAR R R关系关系矩阵矩阵主对角主对角线元素线元素全是全是1主对角线主对角线元素全是元素全是0矩阵是矩阵是对称矩阵对称矩阵若若rij1,且且ij,则则rji0M2中中1位置位置,M

27、中相应中相应位置都是位置都是1关系关系图图每个顶每个顶点都有点都有环环每个顶点每个顶点都没有环都没有环两点之间两点之间有边有边,是是一对方向一对方向相反的边相反的边两点之间有两点之间有边边,是一条是一条有向边有向边点点xi到到xj有有边边,xj 到到xk有边有边,则则xi到到xk也有边也有边关系性质的三种等价条件关系性质的三种等价条件46第46页，本讲稿共99页例例7.13设设A是集合是集合,R1和和R2是是A上的关系上的关系,证明：证明：（1）若若R1,R2是自反的和对称的是自反的和对称的,则则R1R2也是自反的和对也是自反的和对称的称的.（2）若若R1和和R2是传递的是传递的,则则R1R2

28、也是传递的也是传递的.47第47页，本讲稿共99页证证 （1 1）由于由于R1R1和和R2R2是是A A上的自反关系上的自反关系,故有故有I IA A R1R1和和I IA A R2 R2，从而得到，从而得到I IA A R1R2.R1R2.根据定理根据定理7.97.9可知可知R1R2R1R2在在A A上是自反的上是自反的.再由再由R1R1和和R2R2的对称性有的对称性有R1=R1R1=R1-1-1和和R2=R2R2=R2-1-1 根据本章习题第根据本章习题第2020题的结果有题的结果有(R1R2)(R1R2)-1-1=R1=R1-1-1R2R2-1-1=R1R2=R1R2从而证明了从而证明了

29、R1R2R1R2也是也是A A上对称的关系上对称的关系.48第48页，本讲稿共99页（2 2）由由R1R1和和R2R2的传递性有的传递性有R1 R1 o o R1 R1 R1R1和和R2 R2 o o R2 R2 R2R2 再使用定理再使用定理7.47.4得得 (R1R2)(R1R2)o o(R1R2)(R1R2)R1 R1 o o R1R1 R1R1 o o R2R2 R2R2 o o R1R2 R1R2 o o R2 R2(R1R2)R1(R1R2)R1 o o R2R2 R2R2 o o R1 (R1 (将前面的包含式代入将前面的包含式代入)R1R2R1R2从而证明了从而证明了R1R2R

30、1R2也是也是A A上的传递关系上的传递关系 49第49页，本讲稿共99页自反性自反性反自反性反自反性对称性对称性反对称性反对称性传递性传递性R1 1R1R2R1R2R1 R2R1 R2关系的性质和运算之间的联系关系的性质和运算之间的联系50第50页，本讲稿共99页例例7.14 7.14 判断图判断图7.37.3中关系的性质中关系的性质,并说明理由并说明理由.51第51页，本讲稿共99页解（1）该关系是对称的,因为无单向边.它不是自反的也不是反自反的.因为有的顶点有环,有的顶点无环.它不是反对称的,因为图中有双向边.它也不是传递的,因为图中有边和,但没有从3到3的边,即通过3的环.（2）该关系

31、是反自反的但不是自反的,因为每个顶点都没有环.它是反对称的但不是对称的,因为图中只有单向边.它也是传递的,因为不存在顶点x,y,z,使得x到y有边,y到z有边,但x到z没有边,其中x,y,z1,2,3.（3）该关系是自反的但不是反自反的,因为每个顶点都有环.它是反对称的但不是对称的,因为图中只有单向边.但他不是传递的,因为2到1有边,1到3有边,但2到3没有边.52第52页，本讲稿共99页7.5关系的闭包关系的闭包主要内容主要内容l闭包定义闭包定义l闭包的构造方法闭包的构造方法集合表示集合表示矩阵表示矩阵表示图表示图表示l闭包的性质闭包的性质53第53页，本讲稿共99页闭包定义闭包定义定义定义

32、7.14设设R是非空集合是非空集合A上的关系上的关系,R的的自反自反(对称对称或或传递传递)闭闭包包是是A上的关系上的关系R,使得使得R 满足以下条件：满足以下条件：(1)R 是自反的是自反的(对称的或传递的对称的或传递的)(2)R R(3)对对A上任何包含上任何包含R的自反的自反(对称或传递对称或传递)关系关系R 有有RR R的自反闭包记作的自反闭包记作r(R),对称闭包记作对称闭包记作s(R),传递闭包记作传递闭包记作t(R).定理定理7.10设设R为为A上的关系上的关系,则有则有(1)r(R)=RR0(2)s(R)=RR 1(3)t(R)=RR2R3说明：对有穷集说明：对有穷集A(|A|

33、=n)上的关系上的关系,(3)中的并最多不超过中的并最多不超过Rn54第54页，本讲稿共99页证明证明证证只证只证(1)和和(3).(1)由由IA=R0 RR0知知RR0是自反的是自反的,且满足且满足R RR0设设R 是是A上包含上包含R的自反关系的自反关系,则有则有R R 和和IA R .从而有从而有RR0 R.RR0满足闭包定义满足闭包定义,所以所以r(R)=RR0.(3)先证先证RR2 t(R)成立成立.用归纳法证明对任意正整数用归纳法证明对任意正整数n 有有Rn t(R).n=1时有时有R1=R t(R).假设假设Rn t(R)成立成立,那么对任意的那么对任意的Rn+1=Rn R t(

34、RnR)t(t(R)t(R)t(R)这就证明了这就证明了Rn+1 t(R).由归纳法命题得证由归纳法命题得证.55第55页，本讲稿共99页证明证明再证再证t(R)RR2成立成立,为此只须证明为此只须证明RR2传递传递.任取任取,则则RR2RR2 t(Rt)s(Rs)t s(Rt Rs)t s(Rt+s)RR2从而证明了从而证明了RR2是传递的是传递的.56第56页，本讲稿共99页闭包的矩阵表示和图表示闭包的矩阵表示和图表示设关系设关系R,r(R),s(R),t(R)的关系矩阵分别为的关系矩阵分别为M,Mr,Ms 和和Mt 则则Mr=M+E Ms=M+M Mt=M+M2+M3+E 是单位矩阵是单

35、位矩阵,M 是是转置矩阵，相加时使用转置矩阵，相加时使用逻辑加逻辑加.设关系设关系R,r(R),s(R),t(R)的关系图分别记为的关系图分别记为G,Gr,Gs,Gt,则则Gr,Gs,Gt 的顶点集与的顶点集与G 的顶点集相等的顶点集相等.除了除了G 的边以外的边以外,以下以下述述方法添加新的边：方法添加新的边：(1)考察考察G 的每个顶点的每个顶点,若没环就加一个环，得到若没环就加一个环，得到Gr(2)考察考察G 的每条边的每条边,若有一条若有一条xi 到到xj 的单向边的单向边,ij,则在则在G中加一条中加一条xj 到到xi 的反向边的反向边,得到得到Gs(3)考察考察G 的每个顶点的每个

36、顶点xi,找找xi 可达的所有顶点可达的所有顶点xj(允许允许i=j)，如果没有从如果没有从xi 到到xj的边的边,就加上这条边就加上这条边,得到图得到图Gt57第57页，本讲稿共99页实例实例例例9设设A=a,b,c,d,R=,R和和r(R),s(R),t(R)的关系图如下图所示的关系图如下图所示.Rr(R)s(R)t(R)58第58页，本讲稿共99页闭包的性质闭包的性质定理定理7.11设设R是非空集合是非空集合A上的关系上的关系,则则(1)R是自反的当且仅当是自反的当且仅当r(R)=R.(2)R是对称的当且仅当是对称的当且仅当s(R)=R.(3)R是传递的当且仅当是传递的当且仅当t(R)=

37、R.定理7.12设R1和R2是非空集合A上的关系,且R1R2,则(1)r(R1)r(R2)(2)s(R1)s(R2)(3)t(R1)t(R2)证明证明 略略59第59页，本讲稿共99页定理定理7.13设设R是非空集合是非空集合A上的关系上的关系,(1)若若R是自反的是自反的,则则s(R)与与t(R)也是自反的也是自反的(2)若若R是对称的是对称的,则则r(R)与与t(R)也是对称的也是对称的(3)若若R是传递的是传递的,则则r(R)是传递的是传递的.说明：如果需要进行多个闭包运算，比如求说明：如果需要进行多个闭包运算，比如求R的自反、对的自反、对称、传递的闭包称、传递的闭包tsr(R)，运算顺

38、序如下：，运算顺序如下：闭包的性质闭包的性质60第60页，本讲稿共99页证证（2 2）由于由于R R是是A A上的对称关系上的对称关系,所以所以R=RR=R-1-1,同时同时I IA A=I=IA A-1-1.根据根据 (RI(RIA A)-1-1=R=R-1-1IIA A-1-1从而推出从而推出r(R)r(R)-1-1=(RR=(RR0 0)-1-1=(RI=(RIA A)-1-1=R=R-1-1IIA A-1-1=RI=RIA A=r(R)=r(R)这就证明了这就证明了r(R)r(R)是对称的是对称的.61第61页，本讲稿共99页命题：若命题：若R R是对称的是对称的,则则R Rn n也是

39、对称的也是对称的,其中其中n n是任何正整数是任何正整数.证明证明 用用归纳法归纳法.n=1,Rn=1,R1 1=R=R显然是对称的显然是对称的.假设假设R Rn n是对称的是对称的,则对任意的则对任意的有有RRn+1n+1RRn n o o R Rt()Rt()Rn nR)R)t(Rt(Rn nR)R)R R o o R Rn nRR1+n1+n=R=Rn+1n+1所以所以R Rn+1n+1是对称的是对称的.由归纳法命题得证由归纳法命题得证.62第62页，本讲稿共99页下面证明下面证明t(R)t(R)的对称性的对称性.任取任取t(R)t(R)n(Rn(Rn n)n(Rn(Rn n)（因为（因

40、为R Rn n是对称的）是对称的）t(R)t(R)从而证明了从而证明了t(R)t(R)的对称性的对称性.63第63页，本讲稿共99页定理定理7.137.13讨论了讨论了关系性质关系性质和和闭包运算闭包运算之间的关系之间的关系.如果关系如果关系R R是是自反的和对称的自反的和对称的,那么经过求闭包的运算以后所得到的关系那么经过求闭包的运算以后所得到的关系仍就是自反的和对称的仍就是自反的和对称的.但是对于但是对于传递的传递的关系则不然关系则不然.它的它的自反闭包仍旧保持传递性自反闭包仍旧保持传递性,而对称闭包就而对称闭包就有可能失去传递性有可能失去传递性.64第64页，本讲稿共99页7.6 等价关

41、系与划分等价关系与划分主要内容主要内容l等价关系的定义与实例等价关系的定义与实例l等价类及其性质等价类及其性质l商集与集合的划分商集与集合的划分l等价关系与划分的一一对应等价关系与划分的一一对应65第65页，本讲稿共99页等价关系的定义与实例等价关系的定义与实例定义定义7.15设设R为非空集合上的关系为非空集合上的关系.如果如果R是是自反的、对称的和自反的、对称的和传递传递的的,则称则称R为为A上的上的等价关系等价关系.设设R 是一个等价关系是一个等价关系,若若R,称称x等价于等价于y,记做记做xy.实例实例设设A=1,2,8,如下定义如下定义A上的关系上的关系R：R=|x,yAx y(mod

42、3)其中其中x y(mod3)叫做叫做x与与y 模模3相等相等,即即x除以除以3的余数与的余数与y除以除以3的余数相等的余数相等.不难验证不难验证R 为为A上的等价关系上的等价关系,因为因为(1)xA,有有 x x(mod3)(2)x,yA,若若x y(mod3),则有则有y x(mod3)(3)x,y,zA,若若x y(mod3),y z(mod3),则有则有x z(mod3)66第66页，本讲稿共99页模模 3等价关系的关系图等价关系的关系图等价关系的实例等价关系的实例67第67页，本讲稿共99页把模把模3 3的等价关系推广的等价关系推广,对任何正整数对任何正整数n n可以定义整数集合可以

43、定义整数集合Z Z上模上模n n的等价关系的等价关系.R R|x,yZxy(mod n)|x,yZxy(mod n)例如例如,当当n n5 5时时,整数之间的等价性满足整数之间的等价性满足:10 10 5 5 0 0 5 5 10 10 9 9 4 4 1 1 6 6 11 11 8 8 3 3 2 2 7 7 12 12 7 7 2 2 3 3 8 8 13 13 6 6 1 1 4 4 9 9 14 14 .68第68页，本讲稿共99页等价类定义等价类定义定义定义7.16设设R为非空集合为非空集合A上的等价关系上的等价关系,xA，令，令xR=y|yAxRy称称xR 为为x关于关于R的等价类

44、的等价类,简称为简称为x的的等价类等价类,简记为简记为x或或实例实例A=1,2,8上模上模3等价关系的等价类：等价关系的等价类：1=4=7=1,4,72=5=8=2,5,83=6=3,669第69页，本讲稿共99页等价类的性质等价类的性质定理定理7.14设设R是非空集合是非空集合A上的等价关系上的等价关系,则则(1)x A,x是是A的非空子集的非空子集(2)x,y A,如果如果xRy,则则x=y(3)x,y A,如果如果x y,则则x与与y不交不交(4)x|x A=A证证(1)由定义由定义,x A有有x A.又又x x,即即x非空非空.(2)任取任取z,则有则有zxR R R R R R从而证

45、明了从而证明了zy.综上所述必有综上所述必有x y.同理可证同理可证y x.这就得到了这就得到了x=y.70第70页，本讲稿共99页商集与划分商集与划分定义定义7.177.17 设设 R R 为非空集合为非空集合A A上的上的等价关系等价关系,以以 R R 的所有等的所有等价类作为元素的集合称为价类作为元素的集合称为A A关于关于R R的的商集商集,记做记做A A/R R,A A/R R=x x R R|x xA A 实例实例(1)(1)设设 A A=1,2,8=1,2,8，A A关于模关于模3 3等价关系等价关系R R的商集为的商集为 A/R A/R=1,4,7,2,5,8,3,6=1,4,

46、7,2,5,8,3,6A A关于恒等关系和全域关系的商集为：关于恒等关系和全域关系的商集为：A/IA/IA A =1,2,8=1,2,8，A/EA/EA A =1,2,8=1,2,8 (2)(2)在整数集合在整数集合z z上模上模n n的等价关系的商集是的等价关系的商集是 nz+i|z nz+i|z Z|i=0,1,n-1Z|i=0,1,n-171第71页，本讲稿共99页商集与划分商集与划分定义定义7.18设设A为非空集合为非空集合,若若A的子集族的子集族(P(A)满足满足:(1)(2)x y(x,y xyxy=)(3)=A则称则称是是A的一个的一个划分划分,称称中的元素为中的元素为A的的划分

47、块划分块.72第72页，本讲稿共99页划分实例划分实例例例10设设Aa,b,c,d,给定给定 1,2,3,4,5,6如下：如下：1=a,b,c,d 2=a,b,c,d 3=a,a,b,c,d 4=a,b,c 5=,a,b,c,d 6=a,a,b,c,d 则则 1和和 2是是A的划分的划分,其他都不是其他都不是A的划分的划分.73第73页，本讲稿共99页例例11给出给出A1,2,3上所有的等价关系上所有的等价关系实例实例1 123 31 1 123 351 123 321 123 341 123 331对应对应EA,5对应对应IA,2,3和和4分别对应分别对应R2,R3和和R4.R2=,IAR3

48、=,IAR4=,IA解解先做出先做出A的划分的划分,从左到右分别记作从左到右分别记作 1,2,3,4,5.74第74页，本讲稿共99页练习练习11设设A=1,2,3,R=|x,y A且且x+2y 6，S=,求求:(1)R的集合表达式的集合表达式(2)R 1(3)domR,ranR,fldR(4)R S,R3(5)r(R),s(R),t(R)75第75页，本讲稿共99页解答解答(1)R=,(2)R 1=,(3)domR=1,2,3,ranR=1,2,fldR=1,2,3(4)R S=,R3=,(5)r(R)=,s(R)=,t(R)=,76第76页，本讲稿共99页练习练习22设设A=1,2,3,4

49、，在，在A A上定义二元关系上定义二元关系R：,R x+y=u+v，求求R导出的划分导出的划分.A A=,根据根据中的中的x+y=2,3,4,5,6,7,8将将A划分成等价类：划分成等价类：A/R=,77第77页，本讲稿共99页3设设R是是Z上的模上的模n 等价关系等价关系,即即 x yx y(modn),试给出由试给出由R确定的确定的Z的划分的划分.练习练习3解解设除以设除以n 余数为余数为r 的整数构成等价类的整数构成等价类r，则，则r=kn+r|k Z,r=0,1,n 1=r|r=0,1,n 178第78页，本讲稿共99页练习练习44设设R是是A上的二元关系，上的二元关系，设设 S=|c

50、(R R).证明如果证明如果R是等价关系，则是等价关系，则S也是等价关系。也是等价关系。证证 R是是A上的等价关系上的等价关系.(1)证自反证自反任取任取x,x A R x(R R)S(2)证对称证对称任取任取,S c(R R)c(R R)S(3)证传递证传递任取任取,S S c(R R)d(R R)R R S79第79页，本讲稿共99页关系性质的证明方法关系性质的证明方法1.证明证明R在在A上自反上自反任取任取x,x A.R前提前提推理过程推理过程结论结论2.证明证明R在在A上对称上对称任取任取，R.R前提前提推理过程推理过程结论结论80第80页，本讲稿共99页3.证明证明R在在A上反对称上