離散數(shù)學及應(yīng)用（第3版）課件第四章 二元關(guān)系 （下）

第四章二元關(guān)系《離散數(shù)學及應(yīng)用》第四章二元關(guān)系§4.4關(guān)系的閉包§4.5等價關(guān)系和集合的劃分§4.5.1等價關(guān)系、等價類和商集§4.5.2集合的劃分§4.5.3等價關(guān)系與劃分的一一對應(yīng)*§4.6相容關(guān)系與集合的覆蓋2閉包例1打開電腦；之后輸入正確的密碼進行登錄；登錄成功后請打開word。3閉包例24124356879101211閉包關(guān)系的運算能夠生成新的關(guān)系，但也可能會失去一些性質(zhì)；另一方面，有的關(guān)系“先天性”地就缺少一些特定的性質(zhì)。5閉包設(shè)R

是集合A

上的關(guān)系集合A

上的關(guān)系R1

稱作R

的關(guān)于某特定性質(zhì)的閉包，如果

R1

包含

R

；

R1

具有所希望的性質(zhì)

；且

R1

是A

上滿足

和

的最小關(guān)系。若

A

上的關(guān)系

S

也滿足

和

則必然有R1

S

。6閉包A={0,1},R={(1,0),(1,1)}R的自反閉包是：70000100001001100001010100110111000011001010111010011101101111111包含R具有自反性是“最小的”閉包一般將關(guān)系

R

的自反閉包記作

r(R)對稱閉包記作

s(R)傳遞閉包記作

t(R)8自反閉包（ReflexiveClosure）設(shè)R

是集合

A

上的一個關(guān)系，則R

的自反閉包是R∪IA。

R

R∪IA。

R∪IA

具有自反性——由于

IA

R∪IA。

若

R

S

且

S

是自反的，則

IA

S

于是

R∪IA

S

。9自反閉包（ReflexiveClosure）101234R∪IA

R1234對稱閉包（SymmetricClosure）設(shè)R

是集合

A

上的一個關(guān)系，則R

的對稱閉包是R∪R

1。

R

R∪R

1

(R∪R

1)1=(R)1∪(R

1)1=R

1∪R

=R∪R

1。

若

S

具有對稱性，且

R

S，則由

S

是對稱的，有

S=S

1。由

R

S，得到

R1

S1。

因此

R∪R

1

S∪S

1

=

S。11對稱閉包（SymmetricClosure）121234R∪R-1R12341234傳遞閉包（TransitiveClosure）定理

設(shè)

R

為集合

A

上的任意二元關(guān)系，則

R

是R

的傳遞閉包。13傳遞閉包（TransitiveClosure）證明： ①R

R

②R

具有傳遞性

若

aR

b

且

bR

c

，則存在

R

中從

a到

b

的道路

1和從

b

到

c

的道路

2，

于是

1

和

2

的復(fù)合即是為從

a

到

c

的道路，

因此有

aR

c

，R

具有傳遞性。

14abc傳遞閉包（TransitiveClosure）證明： ③R

是“最小的”

對于A

上任一滿足

R

S的傳遞關(guān)系

S，由其滿足傳遞性知對于所有

n≥1，Sn

S，于是R

=R∪R2∪R3∪…

S∪S2∪S3∪…

S。15使用關(guān)系矩陣計算關(guān)系的閉包假設(shè)|A|=n自反閉包Mr(R)=

MR∨In對稱閉包Mr(R)=

MR∨(MR)T傳遞閉包MR

=

MR∨MR2∨MR3∨…∨MRn16關(guān)系的閉包運算在關(guān)系圖的表現(xiàn)自反閉包每個頂點如果沒有自環(huán)則增加自環(huán)對稱閉包如果有頂點i到頂點j的有向邊且

i

j

，則添加（如果該圖中不存在）有向邊

(j,i)或者保留該關(guān)系的有向圖中的頂點，且將所有有向邊改作無向邊傳遞閉包不斷更新有向圖：如果存在頂點

i

到

j

的道路，則將邊

(i,j)

添加到有向圖中（如果該圖中不存在），直至沒有新的有向邊可添加為止17沃舍爾算法設(shè)

R

為集合

A

上的任意二元關(guān)系，則

R

是R

的傳遞閉包。假設(shè)

R

是有限集合

A

上的關(guān)系，|A|=n，則：R

=R∪R2∪R3∪…∪Rn

。MR

=

MR∨MR2∨MR3∨…∨MRn18沃舍爾算法191234R1101011101101000MR2=0111111111010110MR3=0110010110000010MR=1111111101111101MR4=111101111110101011111111111111101111111111111111

(n-1)(⊙+

)(n-1)(n2(2n

1)+n2)沃舍爾算法另一種思路若aRb

且bRc，則

(a,c)

一定屬于

R

的傳遞閉包20abc沃舍爾算法211234R0110011110000010W1=1110111110001010W2=0110010110000010W0=MR=1111111110001010W3=11111111111111111111111111111111W4=R

沃舍爾算法22C←MRfor

k=1to

n

for

i=1to

n

for

j=1tonC[i,j]←C[i,j]∨(C[i,k]∧C[k,j])2

n3沃舍爾算法231234R0110011110000010W1=1110111110001010W2=0110010110000010W0=MR=1111111110001010W3=11111111111111111111111111111111W4=R

Warshall算法紙上作業(yè)法第k次第k行為1元素所在列畫縱向直線，第k列為1元素所在行畫橫向直線，直線相交位置如果為0，則改為1。24Warshall算法紙上作業(yè)法250110010110000010k=1Warshall算法紙上作業(yè)法260110011110000010k=1k=2Warshall算法紙上作業(yè)法271110111110001010k=3Warshall算法紙上作業(yè)法281111111110001010k=4Warshall算法紙上作業(yè)法291111111111111111Warshall算法紙上作業(yè)法和Warshall算法的關(guān)系？30Warshall’sAlgorithmC←MRfor

k=1to

n

for

i=1to

n

for

j=1to

nC[i,j]←C[i,j]∨(C[i,k]∧C[k,j])Warshall算法紙上作業(yè)法310110011110000010k=1k=2C[

,2]=1C[2,

]=1C[

,

]關(guān)系閉包運算的性質(zhì)定理1

假設(shè)

R

是集合

A

上的關(guān)系，則R

是自反的當且僅當

r(R)=RR

是對稱的當且僅當

s(R)=RR

是傳遞的當且僅當

t(R)=R32關(guān)系閉包運算的性質(zhì)證明：(c)

R是傳遞的當且僅當

t(R)=R(1)假設(shè)R

是傳遞的，則：

R

是傳遞的

R

R

對于任何包含

R

的傳遞關(guān)系

S

都有

R

S(2)假設(shè)t(R)=R則

R

是某個關(guān)系的傳遞閉包，其必然是傳遞的

33關(guān)系閉包運算的性質(zhì)定理2

假設(shè)

R,S

是集合

A

上的關(guān)系且

R

S，則(a)r(R)

r(S)(b)s(R)

s(S)(c)t(R)

t(S)證明：(a)由于

r(S)

滿足自反性，而且

R

S

r(S)

，因此由自反閉包的最小性有

r(R)

r(S)。34關(guān)系閉包運算的性質(zhì)定理3

假設(shè)

R是集合

A上的關(guān)系，則(a)如果

R

是自反的，那么

s(R)和

t(R)都是自反的(b)如果

R

是對稱的，那么

r(R)和

t(R)都是對稱的(c)如果

R

是傳遞的，那么

r(R)是傳遞的。證明：(b)的一部分R=R

1于是

(r(R))

1=(R∪IA)

1=R

1∪(IA)

1

=R∪IA=r(R)r(R)

是對稱的。35關(guān)系閉包運算的性質(zhì)定理3

假設(shè)

R是集合

A上的關(guān)系，則(a)如果

R

是自反的，那么

s(R)和

t(R)都是自反的(b)如果

R

是對稱的，那么

r(R)和

t(R)都是對稱的(c)如果

R

是傳遞的，那么

r(R)是傳遞的。

36那么s(R)呢？關(guān)系閉包運算的性質(zhì)定理4

設(shè)

R

是集合

A上任一二元關(guān)系，則(a)r(s(R))=s(r(R))(b)r(t(R))=t(r(R))(c)t(s(R))

s(t(R))證明：(c)由閉包的定義有R

s(R)因此可得

t(R)

t(s(R))

由于

s(R)

具有對稱性，t(s(R))

也具有對稱性因為

s(t(R))

是

t(R)的對稱閉包，由最小性即有

s(t(R))

t(s(R))37關(guān)系閉包運算的性質(zhì)定理4

設(shè)

R

是集合

A上任一二元關(guān)系，則(a)r(s(R))=s(r(R))(b)r(t(R))=t(r(R))(c)t(s(R))

s(t(R))

38t(s(R))

s(t(R))？第四章二元關(guān)系§4.4關(guān)系的閉包§4.5等價關(guān)系和集合的劃分§4.5.1等價關(guān)系、等價類和商集§4.5.2集合的劃分§4.5.3等價關(guān)系與劃分的一一對應(yīng)*§4.6相容關(guān)系與集合的覆蓋39等價關(guān)系假設(shè)

R

是非空集合

A

上的關(guān)系，如果

R

是自反的、對稱的和傳遞的，則稱

R

是

A

上的等價關(guān)系（equivalencerelation）。40等價關(guān)系例恒等關(guān)系、三角形的相似關(guān)系、“同班同學”關(guān)系、矩陣的相似關(guān)系41等價關(guān)系A(chǔ)={1,2,…,8}，則A

上的“模3同余”關(guān)系

R是一個

A

上的等價關(guān)系A(chǔ)

上的“模2同余”關(guān)系

S

是一個

A

上的等價關(guān)系42等價關(guān)系A(chǔ)={1,2,…,8}，A

上的“模3同余”關(guān)系

R43等價關(guān)系假設(shè)

R

是非空集合

A

上的等價關(guān)系，元素

a

A，集合

R(a)稱為

a

所在的等價類（equivalenceclass），也記作

[a]R或

[a]。集合

{R(a)|a

A}稱作

A

關(guān)于

R

的商集（quotientsets），記作

A/R

；a

稱作R(a)的代表元。44等價關(guān)系例設(shè)A={1,2,3,4}，定義

A

A上的關(guān)系

R

為：(x,y)R(u,v)

當且僅當

x+y

=u+v

。則R

是一個等價關(guān)系。那么，(A

A)/R=？{{(1,1)},{(1,2),(2,1)},

{(1,3),(2,2),(3,1)},{(1,4),(2,3),(3,2),(4,1)},{(2,4),(3,3),(4,2)},

{(3,4),(4,3)},{(4,4)}}45等價關(guān)系(1,1)(1,2)(1,3)(1,4)(2,1)(2,2)(2,3)(2,4)(3,1)(3,2)(3,3)(3,4)(4,1)(4,2)(4,3)(4,4)46等價關(guān)系定理

設(shè)

R

是

A

上的一個等價關(guān)系，

a,b

A，則

aRb

當且僅當R(a)=R(b)。47等價關(guān)系證明

“”

假設(shè)R(a)=R(b)。則由

R

具有自反性有

b

R(b)。

于是

b

R(a)，也即

aRb

。48設(shè)

R

是

A

上的一個等價關(guān)系，a,b

A，則

aRb

當且僅當R(a)=R(b)。等價關(guān)系證明 “

”

假設(shè)

aRb。由

R

的對稱性有

bRa，于是a

R(b)且

b

R(a)。

對于任意

x

R(b)，因

R

具有傳遞性，由

x

R(b)

及

b

R(a)可得

x

R(a)。因此R(b)

R(a)。

類似地可證明

R(a)

R(b)，故有R(a)=R(b)。

49設(shè)

R

是

A

上的一個等價關(guān)系，a,b

A，則

aRb

當且僅當R(a)=R(b)。等價關(guān)系例A={a,b,c}R={(a,a),(b,b),(c,c),(b,c),(c,b)}S={(a,a),(b,b),(c,c),(a,b),(b,a)}R∩S={(a,a),(b,b),(c,c)}都是等價關(guān)系。而R∪S={(a,a),(b,b),(c,c),(a,b),

(b,a),(b,c),(c,b)}則不是等價關(guān)系。50等價關(guān)系定理

假設(shè)

A兩個集合，R、S為集合

A

上的兩個等價關(guān)系，則

R∩S也是等價關(guān)系。（為什么？）但一般來講

R∪S不一定也是等價關(guān)系。

（為什么？）

51等價關(guān)系定理

假設(shè)

R、S

為集合

A

上的等價關(guān)系，則包含

R∪S的最小等價關(guān)系為

(R∪S)

52等價關(guān)系證明：(1)顯然

R∪S

(R∪S)

。(2)(R∪S)

實際上是一個等價關(guān)系：R∪S具有自反性和對稱性故而(R∪S)

=t(R∪S)也具有自反性和對稱性(R∪S)

=t(R∪S)明顯具有傳遞性(3)對于任何包含

R∪S

的等價關(guān)系

T

，T

必定具有傳遞性，

由于(R∪S)

是

R∪S

的傳遞閉包，

因此

(R∪S)

T。

53第四章二元關(guān)系§4.4關(guān)系的閉包§4.5等價關(guān)系和集合的劃分§4.5.1等價關(guān)系、等價類和商集§4.5.2集合的劃分§4.5.3等價關(guān)系與劃分的一一對應(yīng)*§4.6相容關(guān)系與集合的覆蓋*§4.7關(guān)系在計算機中的表示方法54劃分一個問題——將學生們分成若干個小組每名同學一定在某個小組中沒有同學同時出現(xiàn)在不同小組中55劃分集合A

的非空子集的集合P

稱作A

的一個劃分或者商集，如果1.

A

中的每一個元素都包含于

P中的一個元素；2.若

A1

和

A2

是P中的相異元素，則必然有A1∩A2=?。

P

中的元素稱作這個劃分的劃分塊。56劃分S={a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p}57abefijmncgkodhlp劃分58{{a,b,e,f,i,j,m,n},{c,g,k,o},dsjh98y,{h,l,p}}構(gòu)成一個劃分abefijmncgkodhlp劃分{

{a,b,e,f,i,j},

{g,k,m,n,o},

{c,d,h},

{l,p}}構(gòu)成一個劃分59abefijmncgkodhlp劃分{

{a,b,c,d,e,h},

{g,i,j,k,m},

{l,n,o,p}}構(gòu)成劃分么？60abefijmncgkodhlp劃分{

{a,b,c,e,i,j,m},

{d,f,g,h,k},

{j,l,n,o,p}}構(gòu)成劃分么？61abefijmncgkodhlp劃分假設(shè)

A

是整數(shù)集的任一子集，n

是一個大于1的正整數(shù)則可以根據(jù)模n

的余數(shù)對

A

進行劃分62劃分如何證明

P

是

A的一個劃分？①對于任意a

A

，存在B

P，使得a

B；②對于任意

A1,

A2

P，

A1

A2，則A1∩A2=?。63第四章二元關(guān)系§4.4關(guān)系的閉包§4.5等價關(guān)系和集合的劃分§4.5.1等價關(guān)系、等價類和商集§4.5.2集合的劃分§4.5.3等價關(guān)系與劃分的一一對應(yīng)*§4.6相容關(guān)系與集合的覆蓋*§4.7關(guān)系在計算機中的表示方法64由劃分構(gòu)造等價關(guān)系“分班”“同班同學關(guān)系”“劃分”

“等價關(guān)系”？65由劃分構(gòu)造等價關(guān)系66A上等價關(guān)系A(chǔ)的劃分由劃分構(gòu)造等價關(guān)系定理

設(shè)

P

是集合

A

的一個劃分，定義

A

上的關(guān)系

R

為：

aRb

當且僅當

a

和

b

屬于同一個劃分塊。

則

R

是

A

上的一個等價關(guān)系。67由劃分構(gòu)造等價關(guān)系R={(a,a),(a,b),(a,c),(a,d),(b,a),(b,b),(b,c),(b,d),(c,a),(c,b),(c,c),(c,d),(d,a),(d,b),(d,c),(d,d),(e,e),(e,f),(f,e),(f,f)}68A={a,b,c,d,e,f}P

={{a,b,c,d},{e,f}}abdecf由劃分構(gòu)造等價關(guān)系定理的證明 (a)自反性？

若

a

A

則明顯

a

在自己所處的劃分塊中，于是

aRa

。 (b)對稱性？

若

aRb

則

a

與

b

處于相同的劃分塊，于是

bRa

。 (c)傳遞性？

若

aRb

且

bRc

則

a

與

b

處于相同的劃分塊、b與

c

處于相同的劃分塊，于是

aRc

。69abc由劃分構(gòu)造等價關(guān)系R

稱作由

P決定的等價關(guān)系。70abdecfR={(a,a),(a,b),(a,c),(a,d),(b,a),(b,b),(b,c),(b,d),(c,a),(c,b),(c,c),(c,d),(d,a),(d,b),(d,c),(d,d),(e,e),(e,f),(f,e),(f,f)}由等價關(guān)系得到劃分71A上等價關(guān)系A(chǔ)的劃分例由等價關(guān)系得到劃分72R(a)={a,b,c,d} R(b)={a,b,c,d} R(c)={a,b,c,d} R(d)={a,b,c,d} R(e)={e,f} R(f)={e,f}P

={{a,b,c,d},{e,f}}bafcde由等價關(guān)系得到劃分定理

設(shè)

R

是

A

上的一個等價關(guān)系，則

P=A/R={R(a)|a

A}是

A

的一個劃分，

而且

R

就恰是由

P

決定的等價關(guān)系。73由等價關(guān)系得到劃分定理的證明：

要證明

P

是一個劃分： (a)A

中每一個元素都屬于一個等價類。

對于任意

a

A

，由

R

的自反性有

a

R(a)。 (b)若R(a)

R(b)

則

R(a)∩R(b)=

。

否則若存在

c

R(a)∩R(b)

則

c

R(a)

且

c

R(b)

，即

aRc

且

bRc

。

由引理有

R(a)=R(c)=R(b)，產(chǎn)生矛盾。74由等價關(guān)系得到劃分定理的證明：

而且由引理知，aRb

當且僅當

a,b

屬于P

=A/R={R(a)|a

A}的同一個劃分塊，因此

P

決定的等價關(guān)系就是

R

。75由等價關(guān)系得到劃分76A上等價關(guān)系A(chǔ)的劃分由等價關(guān)系得到劃分定理所構(gòu)造的劃分

P

由

R

的所有等價類構(gòu)成，也記作

A/R

。77A/R={{a,b,c,d},{e,f}}bafcde由等價關(guān)系得到劃分由劃分與等價關(guān)系的一一對應(yīng)，可得：定理

設(shè)

R1和

R2為非空集合

A

上的等價關(guān)系，則

R1=R2當且僅當

A/R1=A/R2。78第四章二元關(guān)系§4.4關(guān)系的閉包§4.5等價關(guān)系和集合的劃分§4.5.1等價關(guān)系、等價類和商集§4.5.2集合的劃分§4.5.3等價關(guān)系與劃分的一一對應(yīng)*§4.6相容關(guān)系與集合的覆蓋79相容關(guān)系與集合的覆蓋在實際問題中往往有些關(guān)系不具有傳遞性，例如朋友關(guān)系、父子關(guān)系等就不具有傳遞性，本節(jié)介紹一種應(yīng)用廣泛的新的關(guān)系——相容關(guān)系。80相容關(guān)系與集合的覆蓋定義設(shè)

X

是非空集合，S

P(X)

，如果

，則稱

S是集合

X

的一個覆蓋（covering）。例設(shè)

X={1,2,3,4,5}，則

S1={{1},{2,3},{2,4,5}}，S2={{1},{3,4},{2,4,5}}都是集合

X

的覆蓋。81相容關(guān)系與集合的覆蓋定義設(shè)

R

為集合

X

上的二元關(guān)系，如果R具有自反性和對稱性，則稱

R

為

X

上的相容關(guān)系（compatibilityrelation）。例R={(1,1),(2,2),(3,3),(4,4),(5,5),(1,3),(3,1),