离散数学ch7[3]关系的合成课件

1、离 散 数 学,第二部分 集合论 关系论3 关系的合成,关系的合成,关系的逆,本节主要内容:,关系的合成,x是y的父亲,y是z的母亲,x是z的什么关系？,x是y的父亲,y是x的什么关系？,设 R 是从集合 X 到集合 Y 的关系，,合成关系,关系的合成,定义,S 是从集合 Y 到集合 Z 的关系。,于是，可把从 X 到 Z 的关系 RS 定义成:,RS=|(xX)(zZ)(y)(yY) (R)(S),通常称 RS 是关系 R 和 S 的合成关系。,从 R 和 S 求得 RS 的运算，称为关系的合成。,合成关系,关系的合成,例1:,R=|x,yI,(1)RS=,I是整数集合，R,S是I上的关系,

2、S=|x,yI,|xI,(2)SR=,|xI,(3)RR=,|xI,(4)SS=,|xI,合成关系,关系的合成,例1:,I是整数集合，R,S是I上的关系,RS的关系图,合成关系,关系的合成,例2:,R=|x,yPx是y的父亲,(1)RR表示的关系是:,P是所有人的集合，R和S是P上的关系,S=|x,yPx是y的母亲,xRRy表示x是y的祖父,(2)RS表示的关系是:,xRSy表示x是y的外祖父,(3)|x,yPx是y的祖母的集合表示为:,SR,合成关系,关系的合成,注,若R1的值域与R2的定义域的交集为空，则R1R2为空关系,设IA、IB分别为A和B上的相等关系，R是A到B的二元关系,则IAR

3、=RIB=R,但 RIA,RIB无意义,在关系图上，R1R2是由这样的序偶组成，从aA到cC有一长度为2的路径，其中第一条弧属于R1第二条弧属于R2.,给定集合 X,Y,Z 和 W。设R1是从 X 到 Y 的关系；R2和R3都是从Y到Z的关系，R4是从Z到W的关系,于是应有：,合成关系,合成关系的分配率,定理,(1) R1(R2R3)=(R1R2)(R1R3),(3) R1(R2R3) (R1R2) (R1R3),(4) (R2R3)R4 (R2R4)(R3R4),(2) (R2R3 )R4=(R2R4)(R3R4),合成关系,证明:,(1) R1(R2R3)=(R1R2)(R1R3),即证明

4、两个序偶集合相等,R1(R2R3),(y)(R1)( R2R3),(y)(R1)(R2R3),(y)(R1R2)(R1R3),(y)(R1R2)(y)(R1R3),R1R2,R1R2R1R3,合成关系的分配率,R1R3,合成关系,合成关系的结合率,给定集合 X,Y,Z 和 W。,定理,(R1R2)R3=R1(R2R3),设R1是从 X 到 Y 的关系,R2是从Y到Z的关系，,R3是从Z到W的关系,于是有：,合成关系,证明:,(R1R2)R3=R1(R2R3),(R1R2)R3,(z)(R1R2)(R3),(z)(y)(R1R2)(R3),(z)(y)(R1R2)(R3),(z)(y)(R1)(

5、R2R3),(y)(z)(R1)(R2R3),(y) (R1)(z)(R2R3),(y) (R1)(R2R3),R1(R2R3),合成关系的结合率,爱上海 爱上海论坛 殟翀爿,合成关系,例3:,设A=1,2,3,4,5,A上的二元关系R=,S=,则 RS=,SR=,(RS)R=,R(SR)=,RR=,SS=,合成关系的交换率？,结合率?,合成关系,关系的幂,定义,于是可把R的n次幂Rn定义成：,(1)R0=Ix=|xX,(2)Rn+1=RnR,给定集合X，并且R是 X 中的二元关系。,设n N=0,1,2,.，,亦即R0是集合X中的恒等关系Ix.,合成关系,定理,给定集合X,并且R是 X 中的

6、二元关系，设m,nN。,于是应有：,(1)RmRn=Rm+n,(2)(Rm)n=Rmn,合成关系,证明(1) RmRn=Rm+n,根据定义,即n=1时成立,Rm+1=RmR1,假设Rm+n-1=RmRn-1成立,则有,Rm+n=Rm+n-1R,=(RmRn-1)R,=Rm(Rn-1R),=RmRn,定理,合成关系,即n=1时成立,(Rm)1=Rm,假设(Rm)n-1 =Rm(n-1)成立,则有,(Rm)n=(Rm)n-1Rm,=Rmn,证明(2)(Rm)n=Rmn,根据定义,=Rm(n-1)Rm,=Rm(n-1)+m,定理,合成关系,例4:,集合X=a,b,c,并且X中有关系:,R1=,R2=

7、,求得关系的各次幂,R12=,R13 =,R14=R15=,R22=,R23=,R24=,= R2,R25=,R24R2,=R22,合成关系,定理,于是，必定存在这样的 s 和 t,能使,设 X 是个有穷集合，,并且|X|=n和nN，,R 是 X 中的二元关系，,合成关系,不论怎么放，至少有一个抽屉中至少有2只苹果的事实。,抽屉原理(boxprinciple),又称鸽笼原理。,定理,证明:,在k个抽屉放多于k只苹果，,合成关系,由关系定义可知,集合X中的每一个二元关系都是X2的子集,即，R0，R1 ， R2 X2,|X2|的元素个数是n2个,作为苹果。,所以至少有一个抽屉中至少有2只苹果,即,

8、定理,证明:,合成关系,例5:,R是X上的二元关系，试证R是传递的充要条件是RRR,证：,RR,y使得 R，R,R是传递的,R,RRR,则RR,若R,且R,RRR,R,由x,y,z任意性知,xyz （RRR）,R是传递的,合成的表达,因而关系的合成也可以用矩阵和关系图来表达。,关系可以用矩阵和关系图来表示，,而合成关系仍是关系，,合成的表达,设集合 X、Y、Z的基数分别为 m、n、p。,矩阵表达,R 是 X 到 Y 的关系，S 是 Y 到 Z 的关系,MR表示R的关系矩阵,Ms表示S的关系矩阵,(mn),(np),MRS表示合成关系RS的关系矩阵,(mp),合成的表达,矩阵表达,例1.,设x=

9、1,2 y=a,b,c z=,R=, S=,则 MR=,MS=,MRMS=,1,1,0,0,合成的表达,矩阵表达,设R 是 X 到 Y 的关系，S 是 Y 到 Z 的关系,MR表示R的关系矩阵,Ms表示S的关系矩阵,(mn),(np),MRS表示合成关系RS的关系矩阵,(mp),MRMS中的元素,定理,则MRS=MRMS,合成的表达,矩阵表达,MRMS中的元素,证明定理,MRS=MRMS,证：,若Cij =1,则存在某k使 aikbkj=1，,aik=1xiRyk bkj=1ykSzj,xi(RS)zj, MRMS = MRS,注：,若存在多个k，使aik、bkj都为1，,则Cij仍为1，,只

10、是从xi到zj存在多条长度为2的路径，,此时等式仍然正确,合成的表达,矩阵表达,例2.,设x=1,2 y=a,b,c z=,R=, S=,则 MR=,MS=,MRMS=,MRS=,=,1,1,0,0,合成的表达,用关系矩阵表达关系运算后的新关系, MRS=MRMS 其中cij=aij bij, MRS=MRMS 其中cij=aij bij, MR=cij 其中cij=aij, MR-S=MRMS 其中cij=aij (bij),合成的表达,Rn的关系图的意义,在Rn的图形上，有一条a到b的弧，则在R的图形上从 a到b有一条长度为n的路径,在R2的图形上，有一条a到b的弧，,则在R的图形上从a到

11、b有一条长度为2的路径,关系的逆,则从 Y 到 X 的关系,逆关系,给定任意两个集合 X 和 Y,如果 R 是个从 X 到 Y 的关系,=|R,称为 R 的逆关系.,关系的逆,逆关系,例1:,集合X=0,1,2,3，,X中的R=,解:,=,关系的逆,（1）,注 ：,逆关系,关系的逆,逆关系,例2: 写出以下关系的逆关系,整数集上的 关系的逆是:, 关系,集合族上的 关系的逆是:,空关系的逆是:,空关系,AB的全域关系的逆是:,BA的全域关系,关系的逆,逆关系,例3:,R=|x,yPx是y的父亲,P是所有人的集合，R和S是P上的关系,S=|x,yPx是y的母亲,(3)|x,yPy是x的外祖母的集

12、合表示为:,逆关系,定理,设 R 是从集合 X 到 Y 的关系， 并且 S 是从集合 Y 到 Z 的关系。,于是有：,证:,设是 的任一元素，则, RS,y(RS),逆关系,矩阵表达证:,定理,于是有：,设 R 是从集合 X 到 Y 的关系， 并且 S 是从集合 Y 到 Z 的关系。,逆关系,例3:,给定关系矩阵:,计算:,并验证,逆关系,例3:,给定关系矩阵:,计算:,并验证,逆关系,例3:,给定关系矩阵:,计算:,并验证,逆关系,定理,给定集合 X 和 Y，R 和 S 都是从 X 到 Y 的关系。,于是有：,(a),(e),(b),(c),(d),逆关系,证明:,(a),(c),(d),R, (RS), RS,XY,YX,逆关系,定理,于是有：,给定集合 X 和 Y，且 R 和 S 都是从 X 到 Y 的关系。用 R 表示(XY)-R; 用 表示R-S的逆关系。,(a),(b),证明(a)：,R,R,证明(b):,逆关系,定理,于是有：,