第七章 二元关系精选文档.ppt

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

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

2、且，且A B=|x A y B.例例1A=1,2,3,B=a,b,c A B=,B A=,A=,B=P(A)A=,P(A)B=4本讲稿第四页，共九十九页笛卡儿积的性质笛卡儿积的性质(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)

3、若若|A|=m,|B|=n,则则|A B|=mn(6)A CB DAB CD5本讲稿第五页，共九十九页性质证明性质证明证明证明A(B C)=(A B)(A C)证证任取任取A(BC)xAyBC xA(yByC)(xAyB)(xAyC)ABAC(AB)(AC)所以有所以有A(BC)=(AB)(AC).6本讲稿第六页，共九十九页性质性质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成立成立,证明如下：证明如下：任取

4、任取xA,xA,由于由于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本讲稿第七页，共九十九页实例实例例例2(1)证明证明A=B,C=D A C=B D(2)A C=B D是

5、否推出是否推出A=B,C=D?为什么？为什么？(3)AB=ACB=C(4)A-(BC)=(A-B)(A-C)(5)存在集合存在集合A,使得使得A AA解解(1)任取任取 A Cx A y Cx B y D B D(2)不一定不一定.反例如下：反例如下：A=1，B=2,C=D=,则则A C=B D但是但是A B.8本讲稿第八页，共九十九页解解 (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

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

7、系根据上面的记法，可以写根据上面的记法，可以写1R2,aRb,a c等等.10本讲稿第十页，共九十九页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上有

8、上有个不同的二元关系个不同的二元关系.例如例如|A|=3,则则A上有上有=512个不同的二元关系个不同的二元关系.11本讲稿第十一页，共九十九页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本讲稿第十二页，共九十九页实例实例例如例如,A=

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

10、若若A=x1,x2,xm，R是从是从A上的关系，上的关系，R的关系图是的关系图是GR=,其中其中A为结点集，为结点集，E为边集为边集.如果如果属于属于关系关系R，在图中就有一条从，在图中就有一条从xi 到到xj 的的有向边有向边.注意：注意：l关系矩阵适合表示从关系矩阵适合表示从A到到B的关系或的关系或A上的关系（上的关系（A,B为有为有穷集）穷集）l关系图适合表示有穷集关系图适合表示有穷集A上的关系上的关系即即ExiRxj15本讲稿第十五页，共九十九页实例实例例例4 A=1,2,3,4,R=,R的关系矩阵的关系矩阵MR和关系图和关系图GR如下：如下：16本讲稿第十六页，共九十九页7.3关系的

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

12、 ranR=y|ranR=y|x(R)x(R)(3)R(3)R的定义域和值域的并集称为的定义域和值域的并集称为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本讲稿第十八页，共九十九页关系运算关系运算(逆与合成逆与合成)定义定义7.7关系的关系的逆运逆运算算 R 1=|R 定义定义7.8关系的关系的合成合成运算运算 R S

13、=|y(R S)例例6R=,S=,R 1=,R S=,S R=,19本讲稿第十九页，共九十九页合成的图示法合成的图示法利用图示（不是关系图）方法求合成利用图示（不是关系图）方法求合成R S=,S R=,20本讲稿第二十页，共九十九页关系运算关系运算(限制与像限制与像)定义定义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 的子

14、集，即的子集，即RA ranR21本讲稿第二十一页，共九十九页实例实例例例7设设R=,则则R 1=,R=R 2,3=,R1=2,3R=R3=222本讲稿第二十二页，共九十九页关系运算的性质关系运算的性质定理定理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本讲稿第二十三页，共九十九页定理定

15、理7.2设设F,G,H是任意的关系是任意的关系,则则(1)(F G)H=F(G H)(2)(F G)1=G 1 F 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本讲稿第二十四页，共九十九页证明证明(2)任取任取,(F G)1F G t(FG)t(G 1F 1)G 1 F 1所以所以(F G)1=G 1 F 125本讲稿第二十五页，共九十九页关系运算的性质关系运算的性质定理定理7.3设设R为为A上的关系上的关系,则则R IA=IA R=R证证任取任

16、取R IA t(RIA)t(Rt=yyA)R26本讲稿第二十六页，共九十九页关系运算的性质关系运算的性质定理定理7.4(1)F(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本讲稿第二十七页，共九十九页推广推广定理定理7.4的结论可以推广到有限多个关系的结论可以推广到有限多个关系R(R1R2Rn)=R R1R R2R Rn(R1R2Rn)R=R1 RR2 RRn RR(

17、R1R2Rn)R R1R R2R Rn(R1R2Rn)R R1 RR2 RRn R28本讲稿第二十八页，共九十九页关系运算的性质关系运算的性质定理定理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本讲稿第二十九页，共九十九页证明证明证证只证只证(1)和和(4).(1)任取任取F (AB)FxABF(xAxB)(FxA)(FxB)F AF BF AF B所以有所以有F (AB)=F AF B.30本讲稿第三十页，共九十九页证明证明(4)任取任取y,yF AB x(Fx

18、AB)x(FxAxB)x(FxA)(FxB)x(FxA)x(FxB)yF AyF ByF AF B所以有所以有F AB=F AF B.31本讲稿第三十一页，共九十九页关系的幂运算关系的幂运算定义定义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本讲稿第三十二页，共九十九页例例8设设A=a,b,c,d,R=,求求R的各次幂的各次幂,分别用矩阵和关系

19、图表示分别用矩阵和关系图表示.解解 R 与与 R2的关系矩阵分别是：的关系矩阵分别是：幂的求法幂的求法33本讲稿第三十三页，共九十九页R3和和R4的矩的矩阵阵是：是：因此因此M4=M2,即即R4=R2.因此可以得到因此可以得到R2=R4=R6=，R3=R5=R7=R0的关系矩阵是的关系矩阵是幂的求法幂的求法34本讲稿第三十四页，共九十九页关系图关系图R0,R1,R2,R3,的关系图如下图所示的关系图如下图所示.R0R1R2=R4=R3=R5=35本讲稿第三十五页，共九十九页幂运算的性质幂运算的性质定理定理7.6设设A 为为n 元集元集,R 是是A上的关系上的关系,则存在自然数则存在自然数s 和

20、和t,使得使得Rs=Rt.证证R 为为A上的关系上的关系,由于由于|A|=n,A上的不同关系只有上的不同关系只有个个.列出列出R 的各次幂的各次幂 R0,R1,R2,必存在自然数必存在自然数s 和和t 使得使得Rs=Rt 36本讲稿第三十六页，共九十九页定理定理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)

21、=(Rm Rn)R=Rm+n+1,所以对一切所以对一切m,nN有有Rm Rn=Rm+n.37本讲稿第三十七页，共九十九页证明证明(2)对于任意给定的对于任意给定的mN,施归纳于施归纳于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本讲稿第三十八页，共九十九页定理定理7.8设设R是是A上的关系上的关系,若存在自然数若存在自然数s,t(st)使得使得Rs=Rt,则则(1)对对任何任何kN有有Rs+k=Rt+k(2)对对任何

22、任何k,iN有有Rs+kp+i=Rs+i,其中其中p=t s(3)令令S=R0,R1,Rt 1,则对则对于任意的于任意的qN有有RqS幂运算的性质幂运算的性质证证(1)Rs+k=Rs Rk=Rt Rk=Rt+k(2)对对k归纳归纳.若若k=0,则有则有Rs+0p+i=Rs+i假设假设Rs+kp+i=Rs+i,其中其中p=t s,则则Rs+(k+1)p+i=Rs+kp+i+p=Rs+kp+i Rp=Rs+i Rp=Rs+p+i=Rs+t s+i=Rt+i=Rs+i由归纳法命题得证由归纳法命题得证.39本讲稿第三十九页，共九十九页证明证明(3)任取任取 qN,若若 q t,显然有显然有 RqS,若

23、若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本讲稿第四十页，共九十九页7.4关系的性质关系的性质定义定义7.11设设R 为为A上的关系上的关系,(1)若若 x(xA R),则称则称R 在在A 上是上是自反自反的的.(2)若若 x(xA R),则称则称R 在在A 上是上是反自反反自反的的.实例：实例：自反：全域关系自反：全域关系EA,恒等关系恒等关系IA,小于等于关系小于等于关系LA,整除关系整除关系DA反自反：实数集上的小于

24、关系、幂集上的真包含关系反自反：实数集上的小于关系、幂集上的真包含关系.A=1,2,3,R1,R2,R3是是A上的关系上的关系,其中其中 R1,R2,R3R2自反自反，R3反自反，反自反，R1既不是自反的也不是反自反的既不是自反的也不是反自反的.41本讲稿第四十一页，共九十九页对称性与反对称性对称性与反对称性定义定义7.12设设R 为为A上的关系上的关系,(1)若若 x y(x,yARR),则称则称R 为为A上上对对称称的关系的关系.(2)若若 x y(x,yARRx=y),则称则称R 为为A上的上的反对称反对称关系关系.实例：对称关系：实例：对称关系：A上的全域关系上的全域关系EA,恒等关系

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

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

27、对称上反对称当且仅当当且仅当 RR 1 IA(5)R 在在A上传递上传递当且仅当当且仅当 R R R 44本讲稿第四十四页，共九十九页证明证明证明证明只证只证(1)(1)必要性必要性任取任取,由于由于R 在在A上自反必有上自反必有IA x,yAx=y R从而证明了从而证明了IA R充分性充分性.任取任取x,有有xA IA R因此因此R 在在A上是自反的上是自反的.45本讲稿第四十五页，共九十九页自反性自反性反自反性反自反性对称性对称性反对称性反对称性传递性传递性集合集合IA RRIA=R=R 1RR 1 IAR R R关系关系矩阵矩阵主对角主对角线元素线元素全是全是1主对角线主对角线元素全是元

28、素全是0矩阵是矩阵是对称矩阵对称矩阵若若rij1,且且ij,则则rji0M2中中1位置位置,M中相应中相应位置都是位置都是1关系关系图图每个顶每个顶点都有点都有环环每个顶点每个顶点都没有环都没有环两点之间两点之间有边有边,是是一对方向一对方向相反的边相反的边两点之间有两点之间有边边,是一条是一条有向边有向边点点xi到到xj有有边边,xj 到到xk有边有边,则则xi到到xk也有边也有边关系性质的三种等价条件关系性质的三种等价条件46本讲稿第四十六页，共九十九页例例7.13设设A是集合是集合,R1和和R2是是A上的关系上的关系,证明：证明：（1）若若R1,R2是自反的和对称的是自反的和对称的,则则

29、R1R2也是自反的和对也是自反的和对称的称的.（2）若若R1和和R2是传递的是传递的,则则R1R2也是传递的也是传递的.47本讲稿第四十七页，共九十九页证证 （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题的结果有题的结果有(R1

30、R2)(R1R2)-1-1=R1=R1-1-1R2R2-1-1=R1R2=R1R2从而证明了从而证明了R1R2R1R2也是也是A A上对称的关系上对称的关系.48本讲稿第四十八页，共九十九页（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

31、 o R1 (R1 (将前面的包含式代入将前面的包含式代入)R1R2R1R2从而证明了从而证明了R1R2R1R2也是也是A A上的传递关系上的传递关系 49本讲稿第四十九页，共九十九页自反性自反性反自反性反自反性对称性对称性反对称性反对称性传递性传递性R1 1R1R2R1R2R1 R2R1 R2关系的性质和运算之间的联系关系的性质和运算之间的联系50本讲稿第五十页，共九十九页例例7.14 7.14 判断图判断图7.37.3中关系的性质中关系的性质,并说明理由并说明理由.51本讲稿第五十一页，共九十九页解（1）该关系是对称的,因为无单向边.它不是自反的也不是反自反的.因为有的顶点有环,有的顶点无

32、环.它不是反对称的,因为图中有双向边.它也不是传递的,因为图中有边和,但没有从3到3的边,即通过3的环.（2）该关系是反自反的但不是自反的,因为每个顶点都没有环.它是反对称的但不是对称的,因为图中只有单向边.它也是传递的,因为不存在顶点x,y,z,使得x到y有边,y到z有边,但x到z没有边,其中x,y,z1,2,3.（3）该关系是自反的但不是反自反的,因为每个顶点都有环.它是反对称的但不是对称的,因为图中只有单向边.但他不是传递的,因为2到1有边,1到3有边,但2到3没有边.52本讲稿第五十二页，共九十九页7.5关系的闭包关系的闭包主要内容主要内容l闭包定义闭包定义l闭包的构造方法闭包的构造方

33、法集合表示集合表示矩阵表示矩阵表示图表示图表示l闭包的性质闭包的性质53本讲稿第五十三页，共九十九页闭包定义闭包定义定义定义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上的关系上的

34、关系,则有则有(1)r(R)=RR0(2)s(R)=RR 1(3)t(R)=RR2R3说明：对有穷集说明：对有穷集A(|A|=n)上的关系上的关系,(3)中的并最多不超过中的并最多不超过Rn54本讲稿第五十四页，共九十九页证明证明证证只证只证(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 有有R

35、n t(R).n=1时有时有R1=R t(R).假设假设Rn t(R)成立成立,那么对任意的那么对任意的Rn+1=Rn R t(RnR)t(t(R)t(R)t(R)这就证明了这就证明了Rn+1 t(R).由归纳法命题得证由归纳法命题得证.55本讲稿第五十五页，共九十九页证明证明再证再证t(R)RR2成立成立,为此只须证明为此只须证明RR2传递传递.任取任取,则则RR2RR2 t(Rt)s(Rs)t s(Rt Rs)t s(Rt+s)RR2从而证明了从而证明了RR2是传递的是传递的.56本讲稿第五十六页，共九十九页闭包的矩阵表示和图表示闭包的矩阵表示和图表示设关系设关系R,r(R),s(R),t

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

37、xj 的单向边的单向边,ij,则在则在G中加一条中加一条xj 到到xi 的反向边的反向边,得到得到Gs(3)考察考察G 的每个顶点的每个顶点xi,找找xi 可达的所有顶点可达的所有顶点xj(允许允许i=j)，如果没有从如果没有从xi 到到xj的边的边,就加上这条边就加上这条边,得到图得到图Gt57本讲稿第五十七页，共九十九页实例实例例例9设设A=a,b,c,d,R=,R和和r(R),s(R),t(R)的关系图如下图所示的关系图如下图所示.Rr(R)s(R)t(R)58本讲稿第五十八页，共九十九页闭包的性质闭包的性质定理定理7.11设设R是非空集合是非空集合A上的关系上的关系,则则(1)R是自反

38、的当且仅当是自反的当且仅当r(R)=R.(2)R是对称的当且仅当是对称的当且仅当s(R)=R.(3)R是传递的当且仅当是传递的当且仅当t(R)=R.定理定理7.12设设R1和和R2是非空集合是非空集合A上的关系上的关系,且且R1 R2,则则(1)r(R1)r(R2)(2)s(R1)s(R2)(3)t(R1)t(R2)证明证明 略略59本讲稿第五十九页，共九十九页定理定理7.13设设R是非空集合是非空集合A上的关系上的关系,(1)若若R是自反的是自反的,则则s(R)与与t(R)也是自反的也是自反的(2)若若R是对称的是对称的,则则r(R)与与t(R)也是对称的也是对称的(3)若若R是传递的是传递

39、的,则则r(R)是传递的是传递的.说明：如果需要进行多个闭包运算，比如求说明：如果需要进行多个闭包运算，比如求R的自反、对的自反、对称、传递的闭包称、传递的闭包tsr(R)，运算顺序如下：，运算顺序如下：闭包的性质闭包的性质60本讲稿第六十页，共九十九页证证（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-

40、1=RI=RIA A=r(R)=r(R)这就证明了这就证明了r(R)r(R)是对称的是对称的.61本讲稿第六十一页，共九十九页命题：若命题：若R R是对称的是对称的,则则R Rn n也是对称的也是对称的,其中其中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是对称的是对称的.

41、由归纳法命题得证由归纳法命题得证.62本讲稿第六十二页，共九十九页下面证明下面证明t(R)t(R)的对称性的对称性.任取任取t(R)t(R)n(Rn(Rn n)n(Rn(Rn n)（因为（因为R Rn n是对称的）是对称的）t(R)t(R)从而证明了从而证明了t(R)t(R)的对称性的对称性.63本讲稿第六十三页，共九十九页定理定理7.137.13讨论了讨论了关系性质关系性质和和闭包运算闭包运算之间的关系之间的关系.如果关系如果关系R R是是自反的和对称的自反的和对称的,那么经过求闭包的运算以后所得到的关系那么经过求闭包的运算以后所得到的关系仍就是自反的和对称的仍就是自反的和对称的.但是对于但

42、是对于传递的传递的关系则不然关系则不然.它的它的自反闭包仍旧保持传递性自反闭包仍旧保持传递性,而对称闭包就而对称闭包就有可能失去传递性有可能失去传递性.64本讲稿第六十四页，共九十九页7.6 等价关系与划分等价关系与划分主要内容主要内容l等价关系的定义与实例等价关系的定义与实例l等价类及其性质等价类及其性质l商集与集合的划分商集与集合的划分l等价关系与划分的一一对应等价关系与划分的一一对应65本讲稿第六十五页，共九十九页等价关系的定义与实例等价关系的定义与实例定义定义7.15设设R为非空集合上的关系为非空集合上的关系.如果如果R是是自反的、对称的和自反的、对称的和传递传递的的,则称则称R为为A

43、上的上的等价关系等价关系.设设R 是一个等价关系是一个等价关系,若若R,称称x等价于等价于y,记做记做xy.实例实例设设A=1,2,8,如下定义如下定义A上的关系上的关系R：R=|x,yAx y(mod3)其中其中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本讲稿第六十

44、六页，共九十九页模模 3等价关系的关系图等价关系的关系图等价关系的实例等价关系的实例67本讲稿第六十七页，共九十九页把模把模3 3的等价关系推广的等价关系推广,对任何正整数对任何正整数n n可以定义整数集合可以定义整数集合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

45、4 9 9 14 14 .68本讲稿第六十八页，共九十九页等价类定义等价类定义定义定义7.16设设R为非空集合为非空集合A上的等价关系上的等价关系,xA，令，令xR=y|yAxRy称称xR 为为x关于关于R的等价类的等价类,简称为简称为x的的等价类等价类,简记为简记为x或或实例实例A=1,2,8上模上模3等价关系的等价类：等价关系的等价类：1=4=7=1,4,72=5=8=2,5,83=6=3,669本讲稿第六十九页，共九十九页等价类的性质等价类的性质定理定理7.14设设R是非空集合是非空集合A上的等价关系上的等价关系,则则(1)x A,x是是A的非空子集的非空子集(2)x,y A,如果如果x

46、Ry,则则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从而证明了从而证明了zy.综上所述必有综上所述必有x y.同理可证同理可证y x.这就得到了这就得到了x=y.70本讲稿第七十页，共九十九页商集与划分商集与划分定义定义7.177.17 设设 R R 为非空集合为非空集合A A上的上的等价关系等价关系,以以 R R 的所有等的所有等价类作为元素的集合称为价类作为元素的集合称为A A关于关于R R的的商集商集,记做记做A A/R R,A

47、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,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本讲稿第七十一页，共九十九页商

48、集与划分商集与划分定义定义7.18设设A为非空集合为非空集合,若若A的子集族的子集族(P(A)满足满足:(1)(2)x y(x,y xyxy=)(3)=A则称则称是是A的一个的一个划分划分,称称中的元素为中的元素为A的的划分块划分块.72本讲稿第七十二页，共九十九页划分实例划分实例例例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本讲稿第七十三页，共九十九页例例11给出给

49、出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=,IAR4=,IA解解先做出先做出A的划分的划分,从左到右分别记作从左到右分别记作 1,2,3,4,5.74本讲稿第七十四页，共九十九页练习练习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本讲稿第七十五页，

50、共九十九页解答解答(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本讲稿第七十六页，共九十九页练习练习22设设A=1,2,3,4，在，在A A上定义二元关系上定义二元关系R：,R x+y=u+v，求求R导出的划分导出的划分.A A=,根据根据中的中的x+y=2,3,4,5,6,7,8将将A划分成等价类：划分成等价类：A/R=,77本讲稿第七十七页，共九十九页3设设R是是Z上的模上的模n 等价关系等价关系,即即 x yx y(modn),试给出由试给出由R确定的确定的Z的划分的划分