第3-3講

復合關系、逆關系與閉包運算1.復合關系2.逆關系3.閉包的概念4.構造閉包5.課堂練習6.第3-3講作業11、復合關系定義1設R是X到Y的關系，S是Y到Z的關系，那么RS稱為R和S的復合關系，定義為：RS={<x,z>y(<x,y>R<y,z>S〕}例1設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)，進而有R(n)。21、復合關系〔續〕關系的復合運算可以利用關系矩陣求出：

設關系矩陣A=(aij)n

n，B=(bij)n

n，C=(cij)n

n，A

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

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

(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設R為A上的關系，那么〔1〕R在A上自反當且僅當IAR．〔2〕R在A上反自反當且僅當RIA=．〔3〕R在A上對稱當且僅當R＝RC．〔4〕R在A上反對稱當且僅當RRCIA．〔5〕R在A上傳遞當且僅當RRR．52、逆關系〔續3〕〔定理3的證明〕證：(1)R在A上自反當且僅當IA

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

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

IA

x

A

<x,x>

R從而證明了IA

R。充分性。當IA

R時，任取x

A

<x,x>

IA

<x,x>

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

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