复合关系和逆关系.ppt

《复合关系和逆关系.ppt》由会员分享，可在线阅读，更多相关《复合关系和逆关系.ppt（22页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、3-7复合关系和逆关系复合关系和逆关系一、复合关系一、复合关系引例：引例：a，b，c三人，三人，a，b是兄妹关系，是兄妹关系，b，c是母子关系是母子关系则则a，c是舅甥关系。是舅甥关系。设设R表示兄妹关系，表示兄妹关系，S表示母子关系，表示母子关系，则则R与与S的合成关系就是舅甥关系，的合成关系就是舅甥关系，而而S与与R合成是母女关系；合成是母女关系；如果如果R是父子关系，是父子关系，R与与R合成是祖孙关系了。合成是祖孙关系了。11.概念概念定义：定义：设设R为为X到到Y的关系，的关系，S为从为从Y到到Z的关系，则的关系，则RoS称为称为R和和S的的复合（或合成）关系，复合（或合成）关系，表示

2、为：表示为：RoS=x X,z Z,y Y,使使 R,S说明：说明：R与与S能进行复合的必要条件是：能进行复合的必要条件是：R的值域所属集合的值域所属集合Y与与S定义域所属集合是同一个集定义域所属集合是同一个集合，否则就不能复合。合，否则就不能复合。2例：例：A=1,2,3,4,5，B=3,4,5,C=1,2,3，R是是A到到B的关的关系，系，S是是B到到C的关系：的关系：R=|x+y=6=,S=|y-z=2=,求求A到到C的复合关系的复合关系RoS。解：从有序对中搜索：解：从有序对中搜索：R,S,RoS R,S,RoS R,S,RoS从而从而RoS=,另可以用推导另可以用推导:x+y=6,y

3、-z=2,消去消去y得得x+z=4RoS=|x+z=4=,3例：集合例：集合A=a,b,c,d,e，R=,，S=,，求，求RoS,SoR,RoR,SoS解：解：RoS=,，SoR=,，RoR=,、SoS=说明：关系的复合不满足交换律。说明：关系的复合不满足交换律。R是是A到到B的关系，的关系，S是是B到到C的关系，的关系，RoS是可以的，是可以的，而而SoR根本不能复合；根本不能复合；若若A=C，则，则RoS是是A上的关系，上的关系，SoR是是B上的关系，上的关系，根本不可能相等；根本不可能相等；若若A=B=C，则，则R、S均为均为A上的关系，上的关系，RoS和和SoR也也是是A上的关系，但一

4、般地上的关系，但一般地RoS SoR，从例子中可以，从例子中可以看出。看出。4例：集合例：集合A=0,1,2,3,4，R和和S是是A上的关系，上的关系，R=|x+y=4=,S=y-x=1=,求求RoS、SoR、RoR、SoS、(RoS)oR、Ro(SoR)解：解：RoS=,=x+y=5SoR=,=x+y=3RoR=,=x-y=0SoS=,=y-x=2(RoS)oR=,=x-y=1Ro(SoR)=,=x-y=152.复合关系的性质复合关系的性质1)若若Ran(R)Dom(S)=，则则RoS=。2)Dom(RoS)Dom(R)，Ran(RoS)Ran(S)。3)R是是X到到Y的关系，则的关系，则I

5、XoR=RoIY=R，oR=Ro=。设设R1是从集合是从集合X到到Y的关系，的关系，R2,R3是从集合是从集合Y到到Z的关系，的关系，R4是从集是从集合合Z到到W的关系。的关系。4)若若R2 R3，则：，则：R1oR2 R1oR3，R2oR4 R3oR45)R1o(R2R3)=(R1oR2)(R1oR3)R1o(R2R3)(R1oR2)(R1oR3)(R2R3)oR4=(R2oR4)(R3oR4)(R2R3)oR4(R2oR4)(R3oR4)6)(R1oR2)oR4=R1o(R2oR4)6证明：在此只证明证明：在此只证明5)和和6）5）R1o(R2R3)yY,R1(R2R3)R1(R2R3)(

6、R1R2)(R1R3)R1oR2R1oR3(RoS)(RoT)从而从而R1o(R2R3)(R1oR2)(R1oR3)以上各步均可逆以上各步均可逆,从而从而(R1oR2)(R1oR3)R1o(R2R3)成立。成立。7说明：说明：R1o(R2R3)(R1oR2)(R1oR3)(R2R3)oR4(R2oR4)(R3oR4)中是子集关系，不能中是子集关系，不能改成等号。改成等号。例如：令例如：令A=a,b,c,d，R=,，S=，T=都是都是A上的关系。上的关系。则则Ro(ST)=R=而而(RoS)(RoT)=二者并不相等二者并不相等86）证明：）证明：(R1oR2)oR4zZ，R1oR2，R4yY,R

7、1,R2,R4R1，R2oR4R1o(R2oR4)，(R1oR2)oR4 R1o(R2oR4)类似可以证类似可以证R1o(R2oR4)(R1oR2)oR4从而从而(R1oR2)oR4=R1o(R2oR4)9定理：定理：R是集合是集合A上的关系，上的关系，R有传递性的充要条件是有传递性的充要条件是R RoR R。证明：证明：设设RoR，根据合成关系定义有，根据合成关系定义有 zA，使得，使得R且且R，R传递，传递，R，RoR R设设R，R，根据合成关系定义有，根据合成关系定义有RoR，RoR R，R，R传递传递103.关系的幂关系的幂定义：定义：设设R是是A上的二元关系，上的二元关系，nN,则关

8、系的则关系的n次幂次幂Rn定定义为：义为：1)R0=A是是A上的恒等关系；上的恒等关系；2)Rn+1=RnoR。说明：说明：如果如果R是是A到到B的关系且的关系且AB，则，则R2是无意义的，是无意义的，因为因为RoR是无法复合的。是无法复合的。例例3：设：设A=1,2,3,4,5，A上关系上关系R为，为，R=，求，求R1,R2,可见可见R2=R4=R6=，R3=R5=R7=.说明：说明：对于有限集合上的关系求幂，如果一直算下去，最后对于有限集合上的关系求幂，如果一直算下去，最后总会得到相等的幂，这个规律是通用的。总会得到相等的幂，这个规律是通用的。11定理：定理：设设R是集合是集合A上的关系，

9、上的关系，m,nN，则，则1）RmoRn=Rm+n(称第一指数律）称第一指数律）2）(Rm)n=Rmn(称第二指数律）称第二指数律）证明：（数学归纳法）证明：（数学归纳法）任意给定任意给定m，对，对n进行归纳进行归纳(1)n=0时，时，R Rm moRoRn n=R=Rm moIoIA A=R=Rm m=R=Rm+0m+0 假设假设R Rm moRoRn n=R=Rm+nm+n成立，则成立，则 R Rm moRoRn+1n+1=R=Rm mo(Ro(Rn noR)=(RoR)=(Rm moRoRn n)oR=R)oR=Rm+nm+noRoR =R =Rm+n+1m+n+1=R Rm+(n+1)

10、m+(n+1)(2)n=0时，时，(R(Rm m)0 0=R=R0 0=R=Rm0m0 假设假设(R(Rm m)n n=R=Rmnmn成立，则成立，则 (R (Rm m)n+1n+1=(R=(Rm m)n noRoRm m=R=RmnmnoRoRm m=R=Rmn+mmn+m=R Rm(n+1)m(n+1)12定理：定理：设设R是集合是集合A上的二元关系，上的二元关系，|A|=n，则存在，则存在i,jN，使得，使得Ri=Rj，其中，其中0ij2n2。证明：证明：|A|=n，A的子集有的子集有2n个，即个，即|P(A)|=2n,|A A|=n2,|P(A A)|=2n2由关系的定义，可知由关系的

11、定义，可知R是是A A的子集，的子集，对任意自然数对任意自然数t都有都有Rt是是A A的子集的子集R0,R1,R2n2共有共有2n2+1个，它们都是个，它们都是A A的子集的子集根据根据鸽巢原理鸽巢原理，至少存在两个幂是相同的，至少存在两个幂是相同的，不妨记为不妨记为Ri=Rj，0ij2n2134.复合关系的关系矩阵复合关系的关系矩阵1)布尔运算布尔运算0,10,1的运算的运算布尔加法（逻辑加法）布尔加法（逻辑加法）:0+0=0,0+1=1+0=1,1+1=1布尔乘法（逻辑乘法）布尔乘法（逻辑乘法）:00=0,01=10=0,11=12)关系合成运算的矩阵求法关系合成运算的矩阵求法定理：定理：

12、设集合设集合A=a1,am,B=b1,bn,C=C1,CP，R是是A到到B的关系，其关系矩阵的关系，其关系矩阵MR是是m n阶矩阵；阶矩阵；S是是B到到C的关系，其关系矩阵的关系，其关系矩阵MS是是n p阶矩阵；阶矩阵；合成关系合成关系RoS是是A到到C的关系，其关系矩阵的关系，其关系矩阵MRoS是是mp阶矩阵，则阶矩阵，则MRoS=MR MS(其中其中 是按布尔运算进行的矩阵乘法是按布尔运算进行的矩阵乘法)14例：设集合例：设集合A=a,b,c,d,e,R和和S是集合是集合A上的关系，上的关系，R=,S=,求求RoS的关系矩阵。的关系矩阵。解：解：RoS S=,MR=010000100000

13、0100000000000MS=0010000001100000100000000MRoS S=0000100001010000000000000=MRMMS S=0100001000000100000000000001000000110000010000000015二、逆关系二、逆关系定义：定义：设设R是集合是集合A到到B的二元关系，若将的二元关系，若将R中的各序偶的第中的各序偶的第一元素和第二元素互换，则得到一个新的一元素和第二元素互换，则得到一个新的B到到A的二元关的二元关系，称为系，称为R的逆关系。记作的逆关系。记作R-1或或Rc。即：。即：Rc=|R说明：说明：|R|=|Rc|；Rc

14、是是B到到A的二元关系；的二元关系；Rc的关系矩阵是的关系矩阵是R的关系矩阵的转置，即的关系矩阵的转置，即MR-1=MR-1；Rc的关系图就是将的关系图就是将R的关系图中的弧改变方向。的关系图中的弧改变方向。16例：例：设某合设某合A=a,b,c,d，R为为A上的关系，上的关系，R=,求求Rc并给出关系矩阵和关系图并给出关系矩阵和关系图R的关系矩阵的关系矩阵MR=10010001110000101010001000011100MR-1=Rc的关系矩阵的关系矩阵R的关系的关系图图abcdRc的关系图的关系图abcd解：解：Rc=,17定理：定理：设设R和和S均是均是A到到B的关系，则的关系，则1

15、）(Rc)c=R2）(RS)c=RcSc3）(RS)c=RcSc4）(R-S)c=Rc-Sc5）(AB)c=BA6）c=7）R=SRc=Sc证明：证明：(在此只证明在此只证明3)3）(RS)c，则，则RS,R且且S,则则Rc且且Sc则则RcSc(RS)c RcSc，以上推导过程均为可逆。以上推导过程均为可逆。RcSc(RS)c(RS)c=RcSc。18定理：定理：设设R是是A到到B的关系，的关系，S是是B到到C的关系，的关系，则则(RoS)c=ScoRc。证明：证明：1)(RoS)c(RoS)y B,R,S Sc,Rc,ScoRc(RS)c ScoRc2)ScoRcy B,Sc,Rc R,S

16、RoS(RoS)cScoRc(RoS)c由由1)和和2)可得可得(RoS)c=ScoRc19例：例：A=a,b,c,B=1,2,3,4,5,R是是A上关系，上关系，S是是A到到B的关的关系。系。R=，S=，验证定理，验证定理6。则则RoS=,Rc=，Sc=，ScoRc=,验证了验证了ScoRc=（RoS）c注意：注意：复合关系的逆等于它们逆关系的反复合；复合关系的逆等于它们逆关系的反复合；设设R是是A到到B的关系，的关系，S是是B到到C的关系，则的关系，则(RoS)c RcoSc。因。因Rc是是B到到A的关系，的关系，Sc是是C到到B的关系，的关系，ScoRc是可以复合的，而是可以复合的，而R

17、coSc是不能复合的。是不能复合的。20定理定理7：R是集合是集合A上的关系，则：上的关系，则：1)R是对称关系的充要条件是是对称关系的充要条件是R=Rc2)R是反对称关系的充要条件是是反对称关系的充要条件是RRc IA（证明留作练习）（证明留作练习）定理定理8：R是集合是集合A上的关系，则：上的关系，则：1）若）若R是自反的，则是自反的，则Rc也是自反的；也是自反的；2）若）若R是对称的，则是对称的，则Rc也是对称的；也是对称的；3）若）若R是传递的，则是传递的，则R-c也是传递的。也是传递的。证明：证明：1）对）对A中任意元素中任意元素a，R自反，自反，R由逆关系定义可知由逆关系定义可知Rc，Rc自反自反2）、）、3）证明略）证明略21思考：思考：若若R是反对称的关系，则在是反对称的关系，则在R Rc的关系矩阵中最的关系矩阵中最多有多少个非零值？多有多少个非零值？作作业业P1181、3、5、6、722