3-7 復(fù)合關(guān)系和逆關(guān)系

1、1,3-7 復(fù)合關(guān)系和逆關(guān)系,一、復(fù)合關(guān)系引例：a，b，c三人，a，b是兄妹關(guān)系，b，c是母子關(guān)系則a，c是舅甥關(guān)系。設(shè)R表示兄妹關(guān)系，S表示母子關(guān)系，則R與S的合成關(guān)系就是舅甥關(guān)系，而S與R合成是母女關(guān)系；如果R是父子關(guān)系，R與R合成是祖孫關(guān)系了。,2,1. 概念定義：設(shè)R為X到Y(jié)的關(guān)系，S為從Y到Z的關(guān)系，則RoS稱為R和S的復(fù)合（或合成）關(guān)系，表示為：RoS={?x?X,z?Z,?y?Y,使

2、?R,?S}說(shuō)明：R與S能進(jìn)行復(fù)合的必要條件是：R的值域所屬集合Y與S定義域所屬集合Ｙ是同一個(gè)集合，否則就不能復(fù)合。,3,例：A={1,2,3,4,5}，B={3,4,5},C={1,2,3}，R是A到B的關(guān)系，S是B到C的關(guān)系：R={|x+y=6}={,,}S={|y-z=2} ={,,}求A到C的復(fù)合關(guān)系RoS。,解：從有序?qū)χ兴阉鳎骸摺蔙,∈S,∴∈RoS∵?R,?S,∴?RoS∵?R,?S,∴?R

3、oS從而RoS={,,}另可以用推導(dǎo): ∵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={}說(shuō)明：關(guān)系的復(fù)合不滿足交換律。R是A到B的關(guān)系，S是B到C的關(guān)系，RoS是可以的， 而SoR根本不能復(fù)合；

4、若A=C，則RoS是A上的關(guān)系，SoR是B上的關(guān)系，根本不可能相等；若A=B=C，則R、S均為A上的關(guān)系，RoS和SoR也是A上的關(guān)系，但一般地RoS?SoR，從例子中可以看出。,5,例：集合A={0,1,2,3,4}， R和S是A上的關(guān)系， R={|x+y=4}={,,,,} S={?y-x=1}={,,,} 求RoS、SoR、RoR、SoS、(RoS)oR、Ro(SoR),解：RoS={,,,}={?x+y=5

5、}SoR={,,,}={?x+y=3}RoR={,,,,}={?x-y=0}SoS={,,}={?y-x=2}(RoS)oR={,,,}={?x-y=1}Ro(SoR)={,,,}={?x-y=1},6,2.復(fù)合關(guān)系的性質(zhì)1) 若 Ran(R)?Dom(S)= ? ，則RoS=?。2) Dom(RoS)?Dom(R)，Ran(RoS)?Ran(S)。3) R是X到Y(jié)的關(guān)系，則IXoR= RoIY =R，?oR= R

6、o?= ?。設(shè)R1是從集合X到Y(jié)的關(guān)系，R2,R3是從集合Y到Z的關(guān)系，R4是從集合Z到W的關(guān)系。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)

7、6) (R1oR2 ) oR4=R1o(R2oR4 ),7,證明：在此只證明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) ?

8、R1o(R2∪R3)∴ ①成立。,8,說(shuō)明：,② R1o(R2∩R3)?(R1oR2)∩(R1oR3) ④(R2∩R3)oR4?(R2oR4)∩(R3oR4)中是子集關(guān)系，不能改成等號(hào)。例如：令A(yù)={a,b,c,d}，R={,}，S={}，T={}都是A上的關(guān)系。則Ro(S∩T)=R∩{ }={ }而(RoS)∩(RoT)={} 二者并不相等,9,6）證明：?∈(R1oR2 ) oR4??z∈Z，∈ R1o

9、R2 ，∈R4??y∈Y,∈R1,∈R2,∈R4?∈R1，∈R2oR4 ?∈ R1o(R2oR4 ) ，∴ (R1oR2 ) oR4? R1o(R2oR4 )類似可以證R1o(R2oR4 ) ? (R1oR2 ) oR4從而 (R1oR2 ) oR4 = R1o(R2oR4 ),10,定理：R是集合A上的關(guān)系，R有傳遞性的充要條件是RoR?R。,證明：?設(shè)∈RoR，根據(jù)合成關(guān)系定義有?z∈A，使

10、得∈R且∈R，∵R傳遞，∴∈R，∴ RoR?R ?設(shè)∈R，∈R，根據(jù)合成關(guān)系定義有∈RoR， ∵ RoR?R，∴∈R，∴R傳遞,11,3. 關(guān)系的冪,定義：設(shè)R是A上的二元關(guān)系，n∈N,則關(guān)系的n次冪Rn定義為：1) R0 =?A是A上的恒等關(guān)系；2) Rn+1=RnoR。說(shuō)明：如果R是A到B的關(guān)系且A≠B，則R2是無(wú)意義的，因?yàn)镽oR是無(wú)法復(fù)合的。例3：設(shè)A={1,2,3,4,

11、5}，A上關(guān)系R為，R={，，，，}，求R1,R2,…可見(jiàn) R2=R4=R6=…， R3=R5=R7=...說(shuō)明：對(duì)于有限集合上的關(guān)系求冪，如果一直算下去，最后總會(huì)得到相等的冪，這個(gè)規(guī)律是通用的。,12,定理：設(shè)R是集合A上的關(guān)系，m,n∈N，則1）Rm o Rn=Rm+n (稱第一指數(shù)律）2）(Rm)n=Rmn (稱第二指數(shù)律）,證明：（數(shù)學(xué)歸納法）任意給定m，對(duì)n進(jìn)行歸納(1) n=0時(shí)，Rm

12、oRn=RmoIA=Rm=Rm+0 假設(shè)RmoRn=Rm+n成立，則 RmoRn+1=Rmo(RnoR)=(RmoRn)oR=Rm+noR =Rm+n+1= Rm+(n+1)(2) n=0時(shí)，(Rm)0=R0= Rm·0 假設(shè)(Rm)n=Rmn成立，則 (Rm)n+1=(Rm)noRm = RmnoRm=Rmn+m= Rm(n+1),13,定理：設(shè)R是集合A上的二元關(guān)系，

13、|A|=n，則存在i, j∈N ，使得Ri=Rj ，其中0≤i<j≤2n2。,證明：∵ |A|=n，∴A的子集有2n個(gè)，即|P(A)|=2n,∴|A?A|=n2, |P(A ? A)|=2n2由關(guān)系的定義，可知R是A ? A的子集，對(duì)任意自然數(shù)t都有Rt是A ? A的子集∴R0,R1,…,R2n2共有2n2 +1個(gè)，它們都是A ? A的子集根據(jù)鴿巢原理，至少存在兩個(gè)冪是相同的，不妨記為R

14、i=Rj ，0≤i<j≤2n2,14,4. 復(fù)合關(guān)系的關(guān)系矩陣,1)布爾運(yùn)算 {0,1}?{0,1}的運(yùn)算布爾加法（邏輯加法）: 0+0=0,0+1=1+0=1,1+1=1布爾乘法（邏輯乘法）: 0×0=0,0×1=1×0=0,1×1=12)關(guān)系合成運(yùn)算的矩陣求法定理：設(shè)集合A={a1,…,am},B={b1,…,bn},C={C1,…, CP}，R是A到B

15、的關(guān)系，其關(guān)系矩陣MR是m ? n階矩陣；S是B到C的關(guān)系，其關(guān)系矩陣MS是n ? p階矩陣；合成關(guān)系RoS是A到C的關(guān)系，其關(guān)系矩陣MRoS是m×p階矩陣，則MRoS=MR ? MS (其中?是按布爾運(yùn)算進(jìn)行的矩陣乘法),15,例：設(shè)集合A={a,b,c,d,e}, R和S是集合A上的關(guān)系，R={,,}, S={,,,}求RoS的關(guān)系矩陣。,解：RoS={,,},16,二、逆關(guān)系,定義：設(shè)R是集合A到B的二元關(guān)系，

16、若將R中的各序偶的第一元素和第二元素互換，則得到一個(gè)新的B到A的二元關(guān)系，稱為R的逆關(guān)系。記作R-1或Rc。即：Rc={| ∈R}說(shuō)明：|R|=| Rc|；Rc是B到A的二元關(guān)系；Rc 的關(guān)系矩陣是R的關(guān)系矩陣的轉(zhuǎn)置，即 MR-1=MR-1；Rc的關(guān)系圖就是將R的關(guān)系圖中的弧改變方向。,17,例：設(shè)某合A={a,b,c,d}，R為A上的關(guān)系，R={,,,,,}求Rc并給出關(guān)系矩陣和關(guān)系圖,解：Rc={,,,,,

17、},18,定理：設(shè)R和S均是A到B的關(guān)系，則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，以

18、上推導(dǎo)過(guò)程均為可逆?！郣c∩Sc?(R∩S)c∴ (R∩S)c=Rc∩Sc。,19,定理：設(shè)R是A到B的關(guān)系，S是B到C的關(guān)系，則(RoS)c=ScoRc。,證明：1) ??(RoS)c??(RoS)??y?B,?R,?S??Sc, ?Rc,?? ScoRc?(R·S)c? ScoRc,2) ??ScoRc??y?B,?Sc,?Rc??R,?S??RoS??(RoS)c? S

19、coRc ? (RoS)c,由1)和2)可得 (RoS)c = ScoRc,20,例：A={a,b,c},B={1,2,3,4,5},R是A上關(guān)系，S是A到B的關(guān)系。R={，，，，}S={，，，，}，驗(yàn)證定理6。,則RoS={,,,,,,}Rc={，，，，}Sc={，，，，}ScoRc={,,,,,,}驗(yàn)證了 ScoRc=（RoS）c注意：復(fù)合關(guān)系的逆等于它們逆關(guān)系的反復(fù)合；設(shè)R是A到B的

20、關(guān)系，S是B到C的關(guān)系，則(RoS)c? RcoSc 。因Rc是B到A的關(guān)系，Sc是C到B的關(guān)系，ScoRc是可以復(fù)合的，而RcoSc是不能復(fù)合的。,21,定理7：R是集合A上的關(guān)系，則： 1) R是對(duì)稱關(guān)系的充要條件是R=Rc 2) R是反對(duì)稱關(guān)系的充要條件是R∩Rc?IA（證明留作練習(xí)）,定理8：R是集合A上的關(guān)系，則：1）若R是自反的，則Rc也是自反的；2）若R是對(duì)稱的，則Rc也是對(duì)稱的；