離散數(shù)學(xué)-3-7 復(fù)合關(guān)系和逆關(guān)系

1、1第三章 集合與關(guān)系3-7 復(fù)合關(guān)系和逆關(guān)系授課人：李朔Email:2一關(guān)系的復(fù)合一關(guān)系的復(fù)合二元關(guān)系是以序偶為元素的集合，可以進(jìn)行集合運(yùn)算，產(chǎn)生新的集合，本課介紹關(guān)系的一種新的運(yùn)算，關(guān)系的復(fù)合。定義定義3.7.13.7.1 設(shè)R為X到Y(jié)的關(guān)系，S為從Y到Z的關(guān)系，則RS稱為R和S的復(fù)合關(guān)系復(fù)合關(guān)系，表示為 RS RS x x X X z z Z Zy(yy(y Y Y R R S)S) 易見(jiàn)RS是從X到Z的關(guān)系。 *從R和S，求RS稱為關(guān)系的合成運(yùn)算關(guān)系的合成運(yùn)算。 合成運(yùn)算由兩個(gè)關(guān)系生成一個(gè)新的關(guān)系* *P114P114例如：例如：R R1 1是關(guān)系是關(guān)系“是是兄弟兄弟”，R R2 2是關(guān)

2、系是關(guān)系“是是父親父親”，那么，那么R1R2是關(guān)系是關(guān)系“是是的叔伯的叔伯” 若若R1R1是關(guān)系是關(guān)系“是是的父親的父親”，那么，那么R1R2是關(guān)系是關(guān)系“是是的祖父的祖父”3一關(guān)系的復(fù)合一關(guān)系的復(fù)合例題1：R=,S=,則 RS=, SR=, (RS)R=? R(SR)=? SS= RR=, RRR=,可以證明，關(guān)系的復(fù)合運(yùn)算滿足結(jié)合律，即： （RS）TR（ST） 故可記為 RSTP115 例題2*當(dāng)R與自己復(fù)合時(shí)，記記RRRRR R2 2。 一般定義 R Rn n+1+1= =R Rn nRR4一關(guān)系的復(fù)合一關(guān)系的復(fù)合例：設(shè)X=0,1,2,3,則 R=,R2=RR=?,R3= R2R =?,

3、*關(guān)系可用矩陣表示，故復(fù)合關(guān)系亦可用矩陣表示。（類似矩陣乘法，但采用邏輯加）P1155例例例題例題3 A=1,2,3,4,5，A上的二元關(guān)系R和S定義如下： R=1,2,2,2,3,4 S=1,3,2,5,3,1,4,2試求MR S和MR MS，它們是否相等 ? 解：按照R 和S的定義，求出 R S=1,5,2,5 ,3,2 寫出R 、S和R S關(guān)系矩陣如下： MR= MS= MR S=0000000000010000001000010000000001000001100000010000000000000001010000100006例例 MR MS= = 00000000000100000

4、0100001000000000100000110000001000000000000000101000010000 所以MR S=MR MS7二、關(guān)系的逆二、關(guān)系的逆 關(guān)系是序偶的集合，由于序偶的有序性，關(guān)系還關(guān)系是序偶的集合，由于序偶的有序性，關(guān)系還有一些特殊的運(yùn)算。有一些特殊的運(yùn)算。P117 P117 定義定義3.7.23.7.2 設(shè)R為X到y(tǒng)的二元關(guān)系，如將R中每一序偶的元素順序互換，所得的集稱為R R的逆的逆關(guān)系關(guān)系，記為Rc，即：Rc=Rn例如：R=, 則 Rc =,n易見(jiàn) (Rc)c = R n又如集合Z上，關(guān)系“”8二、關(guān)系的逆二、關(guān)系的逆 P117 P117 定理定理3.7.

5、13.7.1 設(shè)R，S，T都是從A到B的二元關(guān)系，則1）(ST)C=SCTC2）(ST)C =SCTC3）(AB)C =BA4）(R)C =RC (R=AB-R, RC=BA-RC)5）(S-T)C =SCTC 9二、關(guān)系的逆二、關(guān)系的逆 證： 1)(ST)CSTSTS C T c S C T C4)(R) CRRR C(R) C5)因STST，故(S-T) C =( ST) C =S C (T) C =S C T C =S C -T C 10二、關(guān)系的逆二、關(guān)系的逆P117 P117 定理定理3.7.23.7.2 設(shè)T為從X到Y(jié)的關(guān)系，S為從Y到Z的關(guān)系，則（TSTS）C CS S C CT

6、T C C證：（TS）CTSy(yYTS)y(yYT C S C)S CT C11二、關(guān)系的逆二、關(guān)系的逆定理定理3.7.33.7.3 設(shè)R為X上的二元關(guān)系，則：n1）R是對(duì)稱的，當(dāng)且僅當(dāng)RR C；n2）R是反對(duì)稱的，當(dāng)且僅當(dāng)RR C IX。證證：1）R對(duì)稱，故RRR C,故RR C反之R CR，則RR CR，即R對(duì)稱。12二、關(guān)系的逆二、關(guān)系的逆定理定理3.7.33.7.3 設(shè)R為X上的二元關(guān)系，則：n1）R是對(duì)稱的，當(dāng)且僅當(dāng)RR C；n2）R是反對(duì)稱的，當(dāng)且僅當(dāng)RR C IX。證證：2）設(shè)R反對(duì)稱RR C 則 R且 R C 故有Rx=y 即 IXRRC IX,反之設(shè)RR C IX R且R則 R C RR C即有IX x=y R是反對(duì)稱的。13二、關(guān)系的逆二、關(guān)系的逆*關(guān)于R C的圖形，是R的圖形中將其弧線的箭頭反置即得，而R C的關(guān)系矩陣是R的關(guān)系矩陣的轉(zhuǎn)置。例：X=a, b, c其上二元關(guān)系R關(guān)系陣為則R C的關(guān)系陣為11101110110111011114例例 例例 設(shè)X=1,2,3,4，Y=a,b,c，X到Y(jié)二元關(guān)系 R=1,a,2,b,4,c， 試求RC，寫出MR和 ，驗(yàn)證 =MRT 畫出R和RC的關(guān)系圖，驗(yàn)證將R關(guān)系圖中的弧線的箭頭反置可得到RC關(guān)系圖。 解：RC=a,1,b,2,c,4 R和RC的關(guān)系矩陣是： MR= =顯然，