離散數(shù)學(xué)第三章第三節(jié)

1、1,第3-3講 復(fù)合關(guān)系、逆關(guān)系與閉包運算,1. 復(fù)合關(guān)系2. 逆關(guān)系3. 閉包的概念4. 構(gòu)造閉包5. 課堂練習(xí)6. 第3-3講 作業(yè),,,,,2,1、復(fù)合關(guān)系,定義1 設(shè)R是X到Y(jié)的關(guān)系，S是Y到Z的關(guān)系，則R?S稱為R和S的復(fù)合關(guān)系，定義為： R?S= { ??y(?R??S）},,,,,例1 設(shè)R={,,,} S={,,,,}求R?S，S?R，R?R，R?R?R。,解：R?S={,

2、,,} S?R={,,,} R?R ={,,,,}R?R?R=( R?R) ?R={,,,,,} R?R和 R?R?R分別記作R(2)、 R(3)，進(jìn)而有R(n)。,3,1、復(fù)合關(guān)系（續(xù)）,關(guān)系的復(fù)合運算可以利用關(guān)系矩陣求出： 設(shè)關(guān)系矩陣A=(aij)n?n，B=(bij)n?n， C=(cij)n?n， A?B =C其中,,,,,如例1可用矩陣運算求解如下：,式中：? 表示邏輯析取?

3、 表示邏輯合取,4,2、逆關(guān)系,定義2 二元關(guān)系R的逆關(guān)系定義為： RC={|?R}。,,,,,設(shè)R={,,,}，則 RC={,,,}。,定理1 設(shè)R、S都是集合A到B的二元關(guān)系，則（1）(RC)C=R（2）(R?S)C= RC?SC（3）(R?S)C= RC?SC（4）(A?B)C=B ? A（5）(~R)C= ~(RC) （這里~R= A?B-R,即R的絕對補(bǔ)）（6）(R-S

4、)C= RC-SC,5,2、逆關(guān)系（續(xù)2）,定理2 設(shè)T是X到Y(jié)的關(guān)系，S是Y到Z的關(guān)系，證明 (T?S)C=SC?TC,,,,,證：? (T?S)C ? ?T?S ??y( ?T ? ?S) ??y( ?TC ? ?SC) ? ?SC?TC,定理3 設(shè)R為A上的關(guān)系，則（1）R在A上自反當(dāng)且僅當(dāng) IA ? R．（2）R在A上反自反當(dāng)且僅當(dāng) R?IA=?．（3）R在A上對稱當(dāng)且

5、僅當(dāng) R＝RC．（4）R在A上反對稱當(dāng)且僅當(dāng) R?RC?IA．（5）R在A上傳遞當(dāng)且僅當(dāng) R?R?R．,6,2、逆關(guān)系（續(xù)3）,（定理3的證明）,,,,,證：(1)R在A上自反當(dāng)且僅當(dāng) IA ? R。必要性。任取?IA，如果R在A上自反,必有 ?IA? x ?A ??R從而證明了IA ? R。充分性。當(dāng)IA ? R時，任取x?A ? ?IA? ?R，因此R在A上是自反的。,（2）R在A上反自反當(dāng)且僅當(dāng) R?I

6、A=?。必要性。用反證法。假設(shè)R在A上反自反但R?IA??，必存在?R?IA，由于IA是A上的恒等關(guān)系，從而推出x=y，x?A且?R ，這與R在A上是反自反的相矛盾。充分性。設(shè)R?IA=?，任取x?A??IA? ?R。從而證明了R在A上是反自反的。,7,2、逆關(guān)系（續(xù)4）,（定理3的證明）,,,,,(5) R在A上傳遞當(dāng)且僅當(dāng) R?R?R 。必要性。如果R在A上是傳遞的，任取?R?R，有 ?R?R??t(?R??R)??R,

7、 所以R?R?R．充分性。若R?R?R，如果、?R，因 ?R ??R ? ?R?R ? ?R, 所以R是傳遞的。,證：(4) R在A上反對稱當(dāng)且僅當(dāng) R?RC?IA必要性。任取? R?RC??R??RC ??R??R ? x=y（因為 R在A上是反對稱的） ? ?IA。這就證明了R?RC?IA．充分性若R?RC?IA，任取? R，如果同時有?R，

8、 由于?R? ?R ? ?R??RC ??R?RC??IA? x=y 所以，R在A上是反對稱的．,8,3、閉包的概念,定義3 設(shè)R是非空集合A上的關(guān)系，如果(1) R’是自反的(對稱的、傳遞的)； (2) R?R’；(3)若R”是A上自反(對稱.傳遞)關(guān)系,如果R”?R，則R”?R’。則

9、稱R’是R的自反閉包(對稱閉包、傳遞閉包)。記作r(R),s(R),t(R)。,,,,,關(guān)系可以具有自反、對稱、傳遞等性質(zhì)。然而，不是所有的關(guān)系都具有這些性質(zhì)。但通過對給定的關(guān)系添加新的元素（有序?qū)Γ?，所得的關(guān)系將具有這些性質(zhì)。當(dāng)然，在對給定的關(guān)系進(jìn)行擴(kuò)充時，一方面要使擴(kuò)充后的關(guān)系具有某些性質(zhì)；另一方面，又不想添加過多的元素，做到恰到好處，即添加的元素要最少。 對給定的關(guān)系用擴(kuò)充元素的方法得出具有某些性質(zhì)的新關(guān)系叫閉包運算。,9

10、,3、閉包的概念（續(xù)1）,定理4 設(shè)R是非空集合A上的關(guān)系，R是自反的(對稱的、傳遞的)，當(dāng)且僅當(dāng)r(R)=R（s(R)=R,t(R)=R）。,,,,,從閉包的定義可知，R的自反閉包(對稱閉包、傳遞閉包)是包含R且具有自反(對稱、傳遞)性質(zhì)的“最小”關(guān)系。同時，如果R本身已經(jīng)具備這些性質(zhì)，那么它們就是具備這些性質(zhì)且包含R的“最小”關(guān)系。于是，有下面的定理：,10,3、閉包的概念（續(xù)2）,例2 設(shè)A={1,2,3,4}，R={,,,}，

11、 求 r(R)，s(R)，t(R)。,,,,,解：r(R)=R?IA={,,,,,,,} s(R)=R?RC={,,,,,} t(R)={,,,,,,,,}也可從R的關(guān)系圖來求關(guān)系閉包。,11,4、構(gòu)造閉包,定理5 設(shè)R是A上的關(guān)系，則 (1) r(R)=R? IA (2) s(R)=R?RC (3)

12、 t(R)=R?R2?R3?…,,,,,下面的定理給出了構(gòu)造關(guān)系閉包更一般的方法。,證：(1) r(R)=R?IA 設(shè)R’= R?IA,下面證明R’滿足自反閉包定義中的三個條件。 任取x?A，? IA ??R? IA ??R'，故R'是自反的。 任取?R??R? IA ??R', 故R? R'。 設(shè)R"是自反的，且R?R"， 任取?R&

13、#39;??R? IA ??R?? IA ??R“?? IA (因R?R”) ??R" (因R"是自反的)這說明R'?R”。綜上所述，R'= R? IA是R的自反閉包。,12,4、構(gòu)造閉包（續(xù)1）,定理5 設(shè)R是A上的關(guān)系，則 (2) s(R)=R?RC,,,,,定理5（2）的證明。,證：設(shè)R'= R?RC,顯然R? R?RC（=R'

14、）任取?R?RC ? ?R??RC ??RC??R ? ?R?RC所以R'是對稱的。設(shè)R"是對稱的且R?R"。任取?R'??R??RC ??R"??R (因R?R") ??R"??R" (因R?R") ??R"??R" (

15、因R"是對稱的) ??R"故R'?R",13,4、構(gòu)造閉包（續(xù)2）,定理5 設(shè)R是A上的關(guān)系，則 (3) t(R)=R?R2?R3?…,,,,,定理5（3）的證明。,證：先證R?R2?R3?…? t(R)，只須證明對任意正整數(shù)n均有Rn?t(R)即可。用歸納法證明。 n=1時，R1=R ,R? t(R)。 假設(shè)Rn ? t(R)，則對 任意?Rn+1? ?

16、 Rn?R? ?t(?Rn??R) ??t(? t(R)?? t(R)) ? ? t(R) (因t(R)是傳遞的) 從而命題得證。 再證t(R) ?R?R2?R3?…。為此，只需證R?R2?R3?…是傳遞的，因為t(R)是包含R的最小傳遞閉包。 任意?R?R2?R3?… ? ?R?R2?R3?…? ?s(?Rs) ? ?t(?Rt) ? ?s?t(?Rs??Rt)? ?s?t(?Rs?Rt)

17、? ? R?R2?R3?…這說明R?R2?R3?…是傳遞的。,14,4、構(gòu)造閉包（續(xù)3）,推論 設(shè)R為有限n元集合A上的關(guān)系，則存在正整數(shù)k?n，使得： t(R)=R?R2?R3?…?Rk,,,,,證：設(shè)任意?t(R)，則存在正整數(shù)p，使?Rp。 那么，存在a1,a2,…ap-1?A，使得,,…,?R。 如果滿足上述條件的最小正整數(shù)p>n，因A只有n個元素，而x、a1、a2、…、ap-1、y共計為p+

18、1個元素，則必存在t和s(0?t?Rk，這與p是滿足條件的最小者相悖，故p>n是不可能的。由的任意性可知本推論為真。,15,4、構(gòu)造閉包（續(xù)5）,定理5 設(shè)R為非空集合X上的二元關(guān)系，則 (1) rs(R)=sr(R)； (2) rt(R)=tr(R)； (3) ts(R)=st(R)。,,,,,關(guān)系R的自反、對稱、傳遞閉包還可進(jìn)一步復(fù)合成新的閉包，例如rs(R)應(yīng)理解為r(s(R))，tsr(

19、R)= t(s(r(R)))。對此，有如下定理：,16,7、課堂練習(xí),,,,,練習(xí)1：設(shè)R1、R2為非空集合A上的關(guān)系，且R1?R2，則(1) r(R1)?r(R2); (2) s(R1)?s(R2); (3) t(R1)?t(R2)。證：以(3)為例。按傳遞閉包的定義R2?t(R2)，又已知R1?R2，所以R1?t(R2)。因為t(R1)是包含R1的最小傳遞關(guān)系，t(R2)也是包含R1的傳遞關(guān)系，故t(R1)?t(R2)。,17,