復合關系逆關系及閉包

2024/3/2613-7復合關系和逆關系3-7.1復合關系定義1[復合(合成)(composite)關系]:設R為X到Y的關系，S為從Y到Z上的關系，則R°S稱為R和S的復合關系，表示為：R°S={<x,z>|x

X

z

Z

(

y)(y

Y

<x,y>

R

<y,z>

S)}.2024/3/2623-7.2逆關系定義2[逆(inverse)關系]:

設R是X到Y的二元關系，則從Y到X的二元關系Rc定義為：Rc={<y,x>|<x,y>

R}.整數集合上的“>”關系的逆關系是“<”關系。人群中的父子關系的逆關系是子父關系。容易看出(Rc)c=R2024/3/263例1:設R={<a,b>,<c,d>},S={<b,e>,<d,c>}.求:(1)Rc，Sc.(2)R°S,S°R解:(1)Rc={<b,a>,<d,c>}Sc={<e,b>,<c,d>}.(2)R°S={<a,e>,<c,c>}S°R={<d,d>}.例2:（書上的例題2，第115頁）2024/3/264定理1:

設R1,R2,R3為關系，R1是X到Y的關系，R2是Y到Z的關系，R3是Z到W的關系則(R1°R2)°R3=R1°

(R2°

R3)．證明:

<x,w>,<x,w>

(R1

°R2)

°R3

z(zZ

x(R1°R2)z

zR3w)

z(zZ

y(yY

xR1yyR2z)

zR3w)

zy(zZ

yY

xR1yyR2z

zR3w)

yt

z(zZ

yY

xR1y

(yR2z

zR3w))

y(yY

xR1y

z(zZ

yR2z

zR3w))

y(yY

xR1y

y(R2°R3)w)

xR1°(R2°R3)w

<x,w>

R1°(R2°R3)

(R1°R2)°R3

=R1°(R2

°

R3).#說明:本定理說明復合運算滿足結合律.2024/3/265

由復合關系滿足結合律，可以把關系R本身所組成的復合關系寫成：R°R，R°R°R，

，R°R°

°R(m個)，分別記作R(2)，R(3)，

，R(m)?？梢宰C明復合關系不滿足交換律。R1°R2

R2°R12024/3/2667-3.3關系矩陣的性質：(1)MRc=(MR)T(T表示矩陣轉置)(2)MR1°R2=MR1

MR2

(

表示布爾乘法,其中加法使用邏輯

,乘法使用邏輯

)2024/3/2673-7.4逆關系關系圖的性質：關系Rc的圖形是將關系R圖形中弧的箭頭方向反置。2024/3/268定理2:

設R、R1

、R2都是從A到B的二元關系，則有(1)(R1

R2)c=R1c

R2c(2)(R1

R2)c=R1c

R2c(3)(A×B)c=B×A(4)(~R)c=

~Rc,這里~R＝A×B-R(5)(R1-R2)c=R1c-R2c注：證明(1)(4)(5)見書117頁。2024/3/269定理3:

設R,S為二元關系,則(R°S)c=Sc°Rc.證明:

<x,y>,<x,y>

(R°S)c

<y,x>

(R°S)

z(yRz

zSx)

z(zRcy

xScz)

z(xScz

zRcy)

<x,y>

Sc°Rc.2024/3/2610定理4:設R為X上的二元關系，則(1)R是對稱的

R=Rc（證明見書118頁）(2)是反對稱的

R

Rc

IX定理5:[P119(2)]設R為X上的二元關系，則(1)R是傳遞的

(R°R)R(2)R是自反的IXR2024/3/2611例題:設A={a,b,c},R1={<a,a>,<a,b>,<b,a>,<b,c>},R2={<a,b>,<a,c>,<b,c>},用MR1,MR2確定MR1c,MR2c,MR1°R1,MR1°R2,MR2°R1,從而求出它們的集合表達式.2024/3/2612110110MR1=101MR1c=100000010011000MR2=001MR2c=100000110011MR1

R2=MR1

MR2=011000R1°R2

={<a,b>,<a,c>,<b,b>,<b,c>}.2024/3/2613110110111MR1

R1=MR1

MR1=101

101=110000000000R1°R1

={<a,a>,<a,b>,<a,c>,<b,a>,<b,b>}.011110101MR2

R1=MR2

MR1=001

101=000000000000R2°R1

={<a,b>,<a,c>}.2024/3/2614解:R1c={<a,a>,<a,b>,<b,a>,<c,b>}R2c={<b,a>,<c,a>,<c,b>}R1°R1

={<a,a>,<a,b>,<a,c>,<b,a>,<b,b>}.R1°R2

={<a,b>,<a,c>,<b,b>,<b,c>}.R2°R1

={<a,b>,<a,c>}.2024/3/2615作業(yè)(3-7)：P118(1)(5)2024/3/26163-8關系的閉包運算自反閉包r(R)(reflexivityclosure)對稱閉包s(R)(symmetryclosure)傳遞閉包t(R)(transitivityclosure)閉包的性質,求法,相互關系2024/3/26173-8.1自反閉包(reflexiveclosure)定義1[自反閉包]:

包含給定關系R的最小自反關系,稱為R的自反閉包,記作r(R).(1)r(R)是自反的;(2)R

r(R);(3)(

S)((R

S

S自反)

r(R)

S).2024/3/26183-8.2對稱閉包(symmetricclosure)定義2[對稱閉包]:

包含給定關系R的最小對稱關系,稱為R的對稱閉包,記作s(R).(1)s(R)是對稱的;(2)R

s(R);(3)(

S)((R

S

S對稱)

s(R)

S).2024/3/26193-8.3傳遞閉包(transitiveclosure)定義3[傳遞閉包]:

包含給定關系R的最小傳遞關系,稱為R的傳遞閉包,記作t(R).(1)t(R)是傳遞的;(2)R

t(R);(3)(

S)((R

S

S傳遞)

t(R)

S).2024/3/2620定理1:設R

A

A且A

,則

(1)R自反

r(R)=R;(2)R對稱

s(R)=R;(3)R傳遞

t(R)=R;證明:(1)R

R

R自反

r(R)

R

又R

r(R),

r(R)=R.(2)(3)完全類似.2024/3/2621*（補充）定理1:設R1

R2

A

A且A

,則

(1)r(R1)

r(R2);(2)s(R1)

s(R2);(3)t(R1)

t(R2);證明:(1)R1

R2

r(R2)自反,

r(R1)

r(R2)(2)(3)類似可證.2024/3/2622*（補充）定理2:設R1,R2

A

A且A

,則

(1)r(R1

R2)=r(R1)

r(R2);(2)s(R1

R2)=s(R1)

s(R2);(3)t(R1

R2)

t(R1)

t(R2).證明:(1)利用定理20,r(R1

R2)

r(R1)

r(R2).r(R1)

r(R2)自反且包含R1

R2,所以

r(R1

R2)

r(R1)

r(R2).

r(R1

R2)=r(R1)

r(R2)2024/3/2623證明(2):利用定理20,s(R1

R2)

s(R1)

s(R2).s(R1)

s(R2)對稱且包含R1

R2,所以

s(R1

R2)

s(R1)

s(R2).

s(R1

R2)=s(R1)

s(R2)證明(3):利用定理20,t(R1

R2)

t(R1)

t(R2).

反例:t(R1

R2)

t(R1)

t(R2).2024/3/2624定理2:設R

A

A且A

,則

(1)r(R)=R

IA;(2)s(R)=R

Rc;(3)t(R)=R

R2

R3

….對比:R自反

IA

RR對稱

R=RcR傳遞

R2

R2024/3/2625證明:(1)r(R)=R

IA;i)R

R

IA;ii)IA

R

IA

R

IA自反

r(R)

R

IA;iii)R

r(R)

r(R)自反

R

r(R)

IA

r(R)

R

IA

r(R)

r(R)=R

IA.2024/3/2626證明:(2)s(R)=R

Rc;i)R

R

Rc;ii)(R

Rc)c=R

Rc

R

Rc對稱

s(R)

R

Rc;iii)R

s(R)

s(R)對稱

R

s(R)

Rc

s(R)

R

Rc

s(R)

s(R)=R

Rc.2024/3/2627證明(3)之前，說明以下事實：復合運算對并運算滿足分配律R1

°(R2

R3)=(R1

°R2)(R1

°R3)(R1

R2)°R3=(R1

°R3)(R2

°R3)復合運算對交運算滿足弱分配律R1

°(R2

R3)

(R1°R2)(R1

°R3)(R1

R2)°R3

(R1°R2)(R1

°R3)2024/3/2628證明:(3)t(R)=R

R2

R3

….證明:i)先證t(R)

R

R2

R3

…;∵R

R

R2

R3

…;∵(R

R2

R3

…)2=R2

R3

…

R

R2

R3

…

R

R2

R3

…傳遞

∴

t(R)

R

R2

R3

…;ii)再證R

R2

R3

…

t(R)∵R

t(R)

t(R)傳遞

R

t(R)

R2

t(R)

R3

t(R)

…

R

R2

R3

…

t(R)

t(R)=R

R2

R3

….#2024/3/2629定理3：設X是含有n個元素的集合，R是X上的二元關系，則存在一個正整數k

n，使得t(R)=R

R2

R3

…

Rk證明：見P122。2024/3/2630例題1:設A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>}.

求r(R),s(R),t(R).解:r(R)=RIA={<a,a>,<b,b>,<c,c>,<d,d><a,b>,<b,a>,<b,c>,<c,d>}s(R)=R

Rc={<a,b>,<b,a>,<b,c>,<c,b>,<c,d><d,c>}t(R)=R

R2

R3

R4

={<a,a>,<a,b>,<a,c>,<a,d>,<b,a>,<b,b>,<b,c>,<b,d>,<c,d>}見P1232024/3/2631求傳遞閉包的另一種方法：當有限集X的元素較多時，矩陣運算很繁瑣，Warshall在1962年提出了R+的一個有效算法如下：（1）置新矩陣A=M（2）置i=1（3）對所有j如果A[j,i]=1，則對k=1,2,…,nA[j,k]=A[j,k]+A[i,k]（4）i=i+1（5）如果i

n,則轉到步驟（3）,否則停止。2024/3/2632引出下面定理：閉包運算是否可以交換順序?即：(1)rs(R)=sr(R)?(2)rt(R)=tr(R)?(3)st(R)=ts(R)?2024/3/2633定理4：設R