《复合关系和逆关系.ppt》由会员分享，可在线阅读，更多相关《复合关系和逆关系.ppt（22页珍藏版）》请在三一办公上搜索。
1、1,3-7 复合关系和逆关系,一、复合关系引例：a，b，c三人，a，b是兄妹关系，b，c是母子关系则a，c是舅甥关系。设R表示兄妹关系，S表示母子关系，则R与S的合成关系就是舅甥关系，而S与R合成是母女关系；如果R是父子关系，R与R合成是祖孙关系了。,2,1.概念定义：设R为X到Y的关系，S为从Y到Z的关系，则RoS称为R和S的复合（或合成）关系，表示为：RoS=xX,zZ,yY,使R,S说明：R与S能进行复合的必要条件是：R的值域所属集合Y与S定义域所属集合是同一个集合，否则就不能复合。,3,例：A=1,2,3,4,5，B=3,4,5,C=1,2,3，R是A到B的关系，S是B到C的关系：R=
2、|x+y=6=,S=|y-z=2=,求A到C的复合关系RoS。,解：从有序对中搜索：R,S,RoSR,S,RoSR,S,RoS从而RoS=,另可以用推导:x+y=6,y-z=2,消去y得x+z=4 RoS=|x+z=4=,4,例：集合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上的关系，但一
3、般地RoSSoR，从例子中可以看出。,5,例：集合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=1,6,2.复合关系的性质1)若 Ran(R)Dom(S)=，则RoS=。2)Dom(RoS)Dom(R)，Ran(RoS)Ran(S)。3)R是X到Y的关系，则IXoR=RoIY=R，oR=Ro=。设R1是从集合X到Y的关系，R2,R3是从集合Y到Z
4、的关系，R4是从集合Z到W的关系。4)若R2R3，则：R1oR2R1oR3，R2oR4R3oR45)R1o(R2R3)=(R1oR2)(R1oR3)R1o(R2R3)(R1oR2)(R1oR3)(R2R3)oR4=(R2oR4)(R3oR4)(R2R3)oR4(R2oR4)(R3oR4)6)(R1oR2)oR4=R1o(R2oR4),7,证明：在此只证明5)和6）,5）R1o(R2R3)yY,R1(R2R3)R1(R2R3)(R1R2)(R1R3)R1o R2R1o R3(RoS)(RoT)从而 R1o(R2R3)(R1oR2)(R1oR3)以上各步均可逆,从而(R1oR2)(R1oR3)R1
5、o(R2R3)成立。,8,说明：,R1o(R2R3)(R1oR2)(R1oR3)(R2R3)oR4(R2oR4)(R3oR4)中是子集关系，不能改成等号。例如：令A=a,b,c,d，R=,，S=，T=都是A上的关系。则Ro(ST)=R=而(RoS)(RoT)=二者并不相等,9,6）证明：(R1oR2)oR4zZ，R1oR2，R4yY,R1,R2,R4R1，R2oR4 R1o(R2oR4)，(R1oR2)oR4 R1o(R2oR4)类似可以证R1o(R2oR4)(R1oR2)oR4从而(R1oR2)oR4=R1o(R2oR4),10,定理：R是集合A上的关系，R有传递性的充要条件是RoRR。,证
6、明：设RoR，根据合成关系定义有zA，使得R且R，R传递，R，RoRR 设R，R，根据合成关系定义有RoR，RoRR，R，R传递,11,3.关系的幂,定义：设R是A上的二元关系，nN,则关系的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=.说明：对于有限集合上的关系求幂，如果一直算下去，最后总会得到相等的幂，这个规律是通用的。,12,定理：设R是集合A上的关系，m,nN，则1）Rm o
7、 Rn=Rm+n(称第一指数律）2）(Rm)n=Rmn(称第二指数律）,证明：（数学归纳法）任意给定m，对n进行归纳(1)n=0时，RmoRn=RmoIA=Rm=Rm+0 假设RmoRn=Rm+n成立，则 RmoRn+1=Rmo(RnoR)=(RmoRn)oR=Rm+noR=Rm+n+1=Rm+(n+1)(2)n=0时，(Rm)0=R0=Rm0 假设(Rm)n=Rmn成立，则(Rm)n+1=(Rm)noRm=RmnoRm=Rmn+m=Rm(n+1),13,定理：设R是集合A上的二元关系，|A|=n，则存在i,jN，使得Ri=Rj，其中0ij2n2。,证明：|A|=n，A的子集有2n个，即|P(
8、A)|=2n,|AA|=n2,|P(A A)|=2n2由关系的定义，可知R是A A的子集，对任意自然数t都有Rt是A A的子集R0,R1,R2n2共有2n2+1个，它们都是A A的子集根据鸽巢原理，至少存在两个幂是相同的，不妨记为Ri=Rj，0ij2n2,14,4.复合关系的关系矩阵,1)布尔运算 0,10,1的运算布尔加法（逻辑加法）:0+0=0,0+1=1+0=1,1+1=1布尔乘法（逻辑乘法）:00=0,01=10=0,11=12)关系合成运算的矩阵求法定理：设集合A=a1,am,B=b1,bn,C=C1,CP，R是A到B的关系，其关系矩阵MR是m n阶矩阵；S是B到C的关系，其关系矩阵
9、MS是n p阶矩阵；合成关系RoS是A到C的关系，其关系矩阵MRoS是mp阶矩阵，则MRoS=MR MS(其中是按布尔运算进行的矩阵乘法),15,例：设集合A=a,b,c,d,e,R和S是集合A上的关系，R=,S=,求RoS的关系矩阵。,解：RoS=,16,二、逆关系,定义：设R是集合A到B的二元关系，若将R中的各序偶的第一元素和第二元素互换，则得到一个新的B到A的二元关系，称为R的逆关系。记作R-1或Rc。即：Rc=|R说明：|R|=|Rc|；Rc是B到A的二元关系；Rc 的关系矩阵是R的关系矩阵的转置，即 MR-1=MR-1；Rc的关系图就是将R的关系图中的弧改变方向。,17,例：设某合A
10、=a,b,c,d，R为A上的关系，R=,求Rc并给出关系矩阵和关系图,解：Rc=,18,定理：设R和S均是A到B的关系，则1）(Rc)c=R2）(RS)c=RcSc3）(RS)c=RcSc4）(R-S)c=Rc-Sc5）(AB)c=BA6）c=7）R=S Rc=Sc,证明：(在此只证明3)3）(RS)c，则RS,R且S,则Rc且Sc则RcSc(RS)cRcSc，以上推导过程均为可逆。RcSc(RS)c(RS)c=RcSc。,19,定理：设R是A到B的关系，S是B到C的关系，则(RoS)c=ScoRc。,证明：1)(RoS)c(RoS)yB,R,SSc,Rc,ScoRc(RS)c ScoRc,2
11、)ScoRcyB,Sc,RcR,SRoS(RoS)c ScoRc(RoS)c,由1)和2)可得(RoS)c=ScoRc,20,例：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是可以复合的，而RcoSc是不能复合的。,21,定理7：R是集合A上的关系，则：1)R是对称关系的充要条件是R=Rc 2)R是反对称关系的充要条件是RRcIA（证明留作练习）,定理8：R是集合A上的关系，则：1）若R是自反的，则Rc也是自反的；2）若R是对称的，则Rc也是对称的；3）若R是传递的，则R-c也是传递的。证明：1）对A中任意元素a，R自反，R由逆关系定义可知Rc，Rc自反2）、3）证明略,22,思考：若R是反对称的关系，则在RRc的关系矩阵中最多有多少个非零值？,作 业P1181、3、5、6、7,
