3-7 复合关系和逆关系复合关系和逆关系一、复合关系一、复合关系引例：引例：a，，b，，c三人，三人，a，，b是兄妹关系，是兄妹关系，b，，c是母子关系是母子关系则则a，，c是舅甥关系是舅甥关系设设R表示兄妹关系，表示兄妹关系，S表示母子关系，表示母子关系，则则R与与S的合成关系就是舅甥关系，的合成关系就是舅甥关系，而而S与与R合成是母女关系；合成是母女关系；如果如果R是父子关系，是父子关系，R与与R合成是祖孙关系了合成是祖孙关系了1 1. 概念概念定义：定义：设设R为为X到到Y的关系，的关系，S为从为从Y到到Z的关系，则的关系，则RoS称为称为R和和S的的复合（或合成）关系，复合（或合成）关系，表示为：表示为：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}={<1,5>,<2,4>,<3,3>}S={|y-z=2} ={<3,1>,<4,2>,<5,3>}求求A到到C的复合关系的复合关系RoS。
解：从有序对中搜索：解：从有序对中搜索：∵∵<1,5>∈∈R,<5,3>∈∈S,∴∴<1,3>∈∈RoS∵∵<2,4> R,<4,2> S,∴∴<2,2> RoS∵∵<3,3> R,<3,1> S,∴∴<3,1> RoS从而从而RoS={<1,3>,<2,2>,<3,1>}另可以用推导另可以用推导: ∵∵x+y=6,y-z=2,消去消去y得得x+z=4∴∴ RoS={|x+z=4}={<1,3>,<2,2>,<3,1>}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上的关系，但一般地上的关系，但一般地RoS SoR，从例子中可以，从例子中可以看出。
看出4 例：集合例：集合A={0,1,2,3,4}，， R和和S是是A上的关系，上的关系， R={|x+y=4}={<0,4>,<4,0>,<1,3>,<3,1>,<2,2>} S={ y-x=1}={<0,1>,<1,2>,<2,3>,<3,4>} 求求RoS、、SoR、、RoR、、SoS、、(RoS)oR、、Ro(SoR)解：解：RoS={<4,1>,<1,4>,<3,2>,<2,3>}={ x+y=5}SoR={<0,3>,<1,2>,<2,1>,<3,0>}={ x+y=3}RoR={<0,0>,<1,1>,<2,2>,<3,3>,<4,4>}={ x-y=0}SoS={<0,2>,<1,3>,<2,4>}={ y-x=2}(RoS)oR={<4,3>,<1,0>,<3,2>,<2,1>}={ x-y=1}Ro(SoR)={<4,3>,<3,2>,<2,1>,<1,0>}={ x-y=1}5 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的关系，的关系，R4是从集是从集合合Z到到W的关系4) 若若R2 R3，则：，则：R1oR2 R1oR3，， R2oR4 R3oR45) ①① R1o(R2∪∪R3)=(R1oR2)∪∪(R1oR3) ②② R1o(R2∩R3) (R1oR2)∩(R1oR3)③③(R2∪∪R3)oR4=(R2oR4)∪∪(R3oR4) ④④(R2∩R3)oR4 (R2oR4)∩(R3oR4)6) (R1oR2 ) oR4=R1o(R2oR4 )6 证明：在此只证明证明：在此只证明5) ①①和和6））5））①① ∈∈R1o(R2∪∪R3) y∈∈Y,∈∈R1∧∧∈∈(R2∪∪R3)∈∈R1∧∧(∈∈R2∨∨∈∈R3)(∈∈R1∧∧∈∈R2)∨∨(∈∈R1∧∧∈∈R3)∈∈R1o R2∨∨∈∈R1o R3∈∈(RoS)∪∪(RoT)从而从而 R1o(R2∪∪R3) (R1oR2)∪∪(R1oR3) 以上各步均可逆以上各步均可逆 ,从而从而(R1oR2)∪∪(R1oR3) R1o(R2∪∪R3)∴∴ ①①成立。
成立7 说明：说明：②② R1o(R2∩R3) (R1oR2)∩(R1oR3) ④④(R2∩R3)oR4 (R2oR4)∩(R3oR4)中是子集关系，不能中是子集关系，不能改成等号改成等号例如：令例如：令A={a,b,c,d}，，R={,}，，S={}，，T={}都是都是A上的关系上的关系则则Ro(S∩T)=R∩{ }={ }而而(RoS)∩(RoT)={} 二者并不相等二者并不相等8 6）证明：）证明： ∈∈(R1oR2 ) oR4z∈∈Z，，∈∈ R1oR2 ，，∈∈R4y∈∈Y,∈∈R1,∈∈R2,∈∈R4∈∈R1，，∈∈R2oR4 ∈∈ R1o(R2oR4 ) ，，∴∴ (R1oR2 ) oR4 R1o(R2oR4 )类似可以证类似可以证R1o(R2oR4 ) (R1oR2 ) oR4从而从而 (R1oR2 ) oR4 = R1o(R2oR4 )9 定理：定理：R是集合是集合A上的关系，上的关系，R有传递性的充要条件是有传递性的充要条件是R RoR R。
证明：证明：设设∈∈RoR，根据合成关系定义有，根据合成关系定义有 z∈∈A，使得，使得∈∈R且且∈∈R，，∵∵R传递，传递，∴∴∈∈R，，∴∴ RoR R 设设∈∈R，，∈∈R，根据合成关系定义有，根据合成关系定义有∈∈RoR，， ∵∵ RoR R，，∴∴∈∈R，，∴∴R传递传递10 3. 关系的幂关系的幂定义：定义：设设R是是A上的二元关系，上的二元关系，n∈∈N,则关系的则关系的n次幂次幂Rn定定义为：义为：1) R0 = A是是A上的恒等关系；上的恒等关系；2) Rn+1=RnoR说明：说明：如果如果R是是A到到B的关系且的关系且A≠B，则，则R2是无意义的，是无意义的，因为因为RoR是无法复合的是无法复合的例例3：设：设A={1,2,3,4,5}，，A上关系上关系R为，为，R={<1,2>，，<2,1>，，<2,3>，，<3,4>，，<4,5>}，求，求R1,R2,…可见可见 R2=R4=R6=…，， R3=R5=R7=...说明：说明：对于有限集合上的关系求幂，如果一直算下去，最后对于有限集合上的关系求幂，如果一直算下去，最后总会得到相等的幂，这个规律是通用的。
总会得到相等的幂，这个规律是通用的11 定理：定理：设设R是集合是集合A上的关系，上的关系，m,n∈∈N，则，则1））Rm o Rn=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)m+(n+1)(2) n=0时，时，(R(Rm m) )0 0=R=R0 0= R= Rm·0m·0 假设假设(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, j∈∈N ，使得，使得Ri=Rj ，其中，其中0≤i
证明：证明：∵∵ |A|=n，，∴∴A的子集有的子集有2n个，即个，即|P(A)|=2n,∴∴|A A|=n2, |P(A A)|=2n2由关系的定义，可知由关系的定义，可知R是是A A的子集，的子集，对任意自然数对任意自然数t都有都有Rt是是A A的子集的子集∴∴R0,R1,…,R2n2共有共有2n2 +1个，它们都是个，它们都是A A的子集的子集根据根据鸽巢原理鸽巢原理，至少存在两个幂是相同的，，至少存在两个幂是相同的，不妨记为不妨记为Ri=Rj ，，0≤i,,}, S={,,,}求求RoS的关系矩阵。
的关系矩阵解：解：RoS S={,,}MR=0 1 0 0 00 1 0 0 00 0 0 1 00 0 0 0 00 0 0 0 0MS=0 0 1 0 00 0 0 0 11 0 0 0 00 1 0 0 00 0 0 0 0MRoS S =0 0 0 0 10 0 0 0 10 1 0 0 00 0 0 0 00 0 0 0 0=MR×M×MS S= =0 1 0 0 00 1 0 0 00 0 0 1 00 0 0 0 00 0 0 0 00 0 1 0 00 0 0 0 11 0 0 0 00 1 0 0 00 0 0 0 015 二、逆关系二、逆关系定义：定义：设设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的关系图中的弧改变方向的关系图中的弧改变方向16 例：例：设某合设某合A={a,b,c,d}，，R为为A上的关系，上的关系，R={,,,,,}求求Rc并给出关系矩阵和关系图并给出关系矩阵和关系图R的关系矩阵的关系矩阵MR=1 0 0 10 0 0 11 1 0 00 0 1 01 0 1 00 0 1 00 0 0 11 1 0 0MR-1=Rc的关系矩阵的关系矩阵R的关系的关系图图abcdRc的关系图的关系图abcd解：解：Rc={,,,,,}17 定理：定理：设设R和和S均是均是A到到B的关系，则的关系，则1））(Rc)c = R2））(R∪∪S)c = Rc∪∪Sc3））(R∩S)c = Rc∩Sc4））(R-S)c = Rc-Sc5））(A×B)c = B×A6））Фc= Ф7））R=S Rc=Sc证明：证明： (在此只证明在此只证明3))3）） ∈∈(R∩S)c，则，则∈∈R∩S,∈∈R且且∈∈S, 则则∈∈Rc且且∈∈Sc则则∈∈Rc∩Sc ∴∴(R∩S)c Rc∩Sc，，以上推导过程均为可逆。
以上推导过程均为可逆∴∴Rc∩Sc (R∩S)c∴∴ (R∩S)c=Rc∩Sc18 定理：定理：设设R是是A到到B的关系，的关系，S是是B到到C的关系，的关系，则则(RoS)c=ScoRc证明：证明：1) (RoS)c (RoS)y B, R, S Sc, Rc, ScoRc(R·S)c ScoRc2) ScoRcy B, Sc, Rc R, S RoS (RoS)c ScoRc (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={<1,a>，，<2,b>，，<4,a>，，<4,c>，，}ScoRc={<1,a>,<2,b>,<2,c>,<4,a>,<4,c>,<5,a>,<5,c>}验证了验证了 ScoRc=（（RoS））c注意：注意：复合关系的逆等于它们逆关系的反复合；复合关系的逆等于它们逆关系的反复合；设设R是是A到到B的关系，的关系，S是是B到到C的关系，则的关系，则(RoS)c RcoSc 因Rc是是B到到A的关系，的关系，Sc是是C到到B的关系，的关系，ScoRc是可以复合的，而是可以复合的，而RcoSc是不能复合的是不能复合的20 定理定理7：：R是集合是集合A上的关系，则：上的关系，则： 1) R是对称关系的充要条件是是对称关系的充要条件是R=Rc 2) R是反对称关系的充要条件是是反对称关系的充要条件是R∩Rc 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 。