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

第3-3講

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

S，S

R，R

R，R

R

R。解：R

S={<1,5>,<2,1>,<3,2>,<2,5>}S

R={<4,2>,<4,3>,<3,2>,<1,4>}R

R={<1,2>,<1,3>,<2,2>,<2,3>,<2,4>}R

R

R=(R

R)

R={<1,2>,<1,3>,<1,4>,<2,2>,<2,3>,<2,4>}

R

R和R

R

R分別記作R(2)、

R(3)，進(jìn)而有R(n)。21、復(fù)合關(guān)系〔續(xù)〕關(guān)系的復(fù)合運(yùn)算可以利用關(guān)系矩陣求出：

設(shè)關(guān)系矩陣A=(aij)n

n，B=(bij)n

n，C=(cij)n

n，A

B=C其中如例1可用矩陣運(yùn)算求解如下：式中：表示邏輯析取表示邏輯合取32、逆關(guān)系定義2二元關(guān)系R的逆關(guān)系定義為：RC={<y,x>|<x,y>

R}。設(shè)R={<1,2>,<2,3>,<3,4>,<2,2>}，那么RC={<2,1>,<3,2>,<4,3>,<2,2>}。定理1設(shè)R、S都是集合A到B的二元關(guān)系，那么〔1〕(RC)C=R〔2〕(RS)C=RCSC〔3〕(RS)C=RCSC〔4〕(AB)C=BA〔5〕(~R)C=~(RC)〔這里~R=AB-R,即R的絕對(duì)補(bǔ)〕〔6〕(R-S)C=RC-SC42、逆關(guān)系〔續(xù)2〕定理2設(shè)T是X到Y(jié)的關(guān)系，S是Y到Z的關(guān)系，證明

(T

S)C=SC

TC證：<z,x>

(T

S)C

<x,z>

T

Sy(<x,y>

T

<y,z>

S)y(<y,x>

TC

<z,y>

SC)<z,x>

SC

TC

定理3設(shè)R為A上的關(guān)系，那么〔1〕R在A上自反當(dāng)且僅當(dāng)IAR．〔2〕R在A上反自反當(dāng)且僅當(dāng)RIA=．〔3〕R在A上對(duì)稱當(dāng)且僅當(dāng)R＝RC．〔4〕R在A上反對(duì)稱當(dāng)且僅當(dāng)RRCIA．〔5〕R在A上傳遞當(dāng)且僅當(dāng)RRR．52、逆關(guān)系〔續(xù)3〕〔定理3的證明〕證：(1)R在A上自反當(dāng)且僅當(dāng)IA

R。必要性。任取<x,x>

IA，如果R在A上自反,必有<x,x>

IA

x

A

<x,x>

R從而證明了IA

R。充分性。當(dāng)IA

R時(shí)，任取x

A

<x,x>

IA

<x,x>

R，因此R在A上是自反的?！?〕R在A上反自反當(dāng)且僅當(dāng)RIA=。必要性。用反證法。假設(shè)R在A上反自反但RIA，必存在<x,y>RIA，由于IA是A上的恒等關(guān)系，從而推出x=y，xA且<x,x>R，這與R在A上是反自反的相矛盾。充分性。設(shè)RIA=，任取xA<x,x>IA<x,x>R。從而證明了R在A上是反自反的。62、逆關(guān)系〔續(xù)4〕〔定理3的證明〕(5)R在A上傳遞當(dāng)且僅當(dāng)RRR。必要性。如果R在A上是傳遞的，任取<x,y>RR，有<x,y>RRt(<x,t>R<t,y>R)<x,y>R,所以RRR．充分性。假設(shè)RRR，如果<x,y>、<y,z>R，因<x,y>R<y,z>R<x,z>RR<x,z>R,所以R是傳遞的。證：(4)R在A上反對(duì)稱當(dāng)且僅當(dāng)RRCIA必要性。任取<x,y>RRC<x,y>R<x,y>RC<x,y>R<y,x>Rx=y〔因?yàn)镽在A上是反對(duì)稱的〕<x,y>IA。這就證明了RRCIA．充分性假設(shè)RRCIA，任取<x,y>R，如果同時(shí)有<y,x>R，由于<x,y>R<y,x>R<x,y>R<x,y>RC<x,y>RRC<x,y>IAx=y所以，R在A上是反對(duì)稱的．73、閉包的概念定義3設(shè)R是非空集合A上的關(guān)系，如果(1)R’是自反的(對(duì)稱的、傳遞的)；(2)RR’；(3)假設(shè)R〞是A上自反(對(duì)稱.傳遞)關(guān)系,如果R〞R，那么R〞R’。那么稱R’是R的自反閉包(對(duì)稱閉包、傳遞閉包)。記作r(R),s(R),t(R)。關(guān)系可以具有自反、對(duì)稱、傳遞等性質(zhì)。然而，不是所有的關(guān)系都具有這些性質(zhì)。但通過(guò)對(duì)給定的關(guān)系添加新的元素〔有序?qū)Α?，所得的關(guān)系將具有這些性質(zhì)。當(dāng)然，在對(duì)給定的關(guān)系進(jìn)行擴(kuò)充時(shí)，一方面要使擴(kuò)充后的關(guān)系具有某些性質(zhì)；另一方面，又不想添加過(guò)多的元素，做到恰到好處，即添加的元素要最少。對(duì)給定的關(guān)系用擴(kuò)充元素的方法得出具有某些性質(zhì)的新關(guān)系叫閉包運(yùn)算。83、閉包的概念〔續(xù)1〕定理4設(shè)R是非空集合A上的關(guān)系，R是自反的(對(duì)稱的、傳遞的)，當(dāng)且僅當(dāng)r(R)=R〔s(R)=R,t(R)=R〕。從閉包的定義可知，R的自反閉包(對(duì)稱閉包、傳遞閉包)是包含R且具有自反(對(duì)稱、傳遞)性質(zhì)的“最小〞關(guān)系。同時(shí)，如果R本身已經(jīng)具備這些性質(zhì)，那么它們就是具備這些性質(zhì)且包含R的“最小〞關(guān)系。于是，有下面的定理：93、閉包的概念〔續(xù)2〕例2設(shè)A={1,2,3,4}，R={<1,2>,<2,1>,<2,3>,<3,4>}，求r(R)，s(R)，t(R)。解：r(R)=R

IA={<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<2,1>,<2,3>,<3,4>}

s(R)=R

RC={<1,2>,<2,1>,<2,3>,<3,2>,<3,4>,<4,3>}t(R)={<1,2>,<2,1>,<2,3>,<3,4>,<1,1>,<2,2>,<1,3>,<2,4>,<1,4>}也可從R的關(guān)系圖來(lái)求關(guān)系閉包。104、構(gòu)造閉包定理5設(shè)R是A上的關(guān)系，那么(1)r(R)=RIA(2)s(R)=RRC(3)t(R)=RR2R3…

下面的定理給出了構(gòu)造關(guān)系閉包更一般的方法。證：(1)r(R)=RIA設(shè)R’=RIA,下面證明R’滿足自反閉包定義中的三個(gè)條件。任取xA，<x,x>IA<x,x>RIA<x,x>R'，故R'是自反的。任取<x,y>R<x,y>RIA<x,y>R',故RR'。設(shè)R"是自反的，且RR"，任取<x,y>R'<x,y>RIA<x,y>R<x,y>IA<x,y>R“<x,y>IA(因RR〞)<x,y>R"(因R"是自反的)這說(shuō)明R'R〞。綜上所述，R'=RIA是R的自反閉包。114、構(gòu)造閉包〔續(xù)1〕定理5設(shè)R是A上的關(guān)系，那么(2)s(R)=RRC定理5〔2〕的證明。證：設(shè)R'=RRC,顯然RRRC〔=R'〕任取<x,y>RRC<x,y>R<x,y>RC<y,x>RC<y,x>R<y,x>RRC所以R'是對(duì)稱的。設(shè)R"是對(duì)稱的且RR"。任取<x,y>R'<x,y>R<x,y>RC<x,y>R"<y,x>R(因RR")<x,y>R"<y,x>R"(因RR")<x,y>R"<x,y>R"(因R"是對(duì)稱的)<x,y>R"故R'R"124、構(gòu)造閉包〔續(xù)2〕定理5設(shè)R是A上的關(guān)系，那么(3)t(R)=RR2R3…定理5〔3〕的證明。證：先證RR2R3…t(R)，只須證明對(duì)任意正整數(shù)n均有Rnt(R)即可。用歸納法證明。n=1時(shí)，R1=R,Rt(R)。假設(shè)Rnt(R)，那么對(duì)任意<x,y>Rn+1<x,y>RnRt(<x,t>Rn<t,y>R)t(<x,t>t(R)<t,y>t(R))<x,y>t(R)(因t(R)是傳遞的)從而命題得證。再證t(R)RR2R3…。為此，只需證RR2R3…是傳遞的，因?yàn)閠(R)是包含R的最小傳遞閉包。任意<x,y>RR2R3…<y,z>RR2R3…s(<x,y>Rs)t(<y,z>Rt)st(<x,y>Rs<y,z>Rt)st(<x,y>RsRt)<x,y>RR2R3…這說(shuō)明RR2R3…是傳遞的。134、構(gòu)造閉包〔續(xù)3〕推論設(shè)R為有限n元集合A上的關(guān)系，那么存在正整數(shù)kn，使得：t(R)=RR2R3…Rk證：設(shè)任意<x,y>t(R)，那么存在正整數(shù)p，使<x,y>Rp。那么，存在a1,a2,…ap-1A，使得<x,a1>,<a1,a2>,…,<ap-1,y>R。如果滿足上述條件的最小正整數(shù)p>n，因A只有n個(gè)元素，而x、a1、a2、…、ap-1、y共計(jì)為p+1個(gè)元素，那么必存在t和s(0t<sp)，使得at=as。從而有xRa1,a1Ra2,…,at-1Rat,asRas+1,…,ap-1Ry這個(gè)序列中，xRa1,a1Ra2,…,at-1Rat共計(jì)是t項(xiàng)，asRas+1,…,ap-1Ry是(p-1)-s+1=p-s項(xiàng)，令k=t+p-s=p-(s-t)<p，那么<x,y>Rk，這與p是滿足條件的最小者相悖，故p>n是不可能的。由<x,y>的任意性可知本推論為真。144、構(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的自反、對(duì)稱、傳遞閉包還可進(jìn)一步復(fù)合成新的閉包，例如rs(R)應(yīng)理解為r(s(R))，tsr(R)=t(s(r