离散数学及应用（第3版）课件第四章 二元关系 （下）

第四章二元关系《离散数学及应用》第四章二元关系§4.4关系的闭包§4.5等价关系和集合的划分§4.5.1等价关系、等价类和商集§4.5.2集合的划分§4.5.3等价关系与划分的一一对应*§4.6相容关系与集合的覆盖2闭包例1打开电脑；之后输入正确的密码进行登录；登录成功后请打开word。3闭包例24124356879101211闭包关系的运算能够生成新的关系，但也可能会失去一些性质；另一方面，有的关系“先天性”地就缺少一些特定的性质。5闭包设R

是集合A

上的关系集合A

上的关系R1

称作R

的关于某特定性质的闭包，如果

R1

包含

R

；

R1

具有所希望的性质

；且

R1

是A

上满足

和

的最小关系。若

A

上的关系

S

也满足

和

则必然有R1

S

。6闭包A={0,1},R={(1,0),(1,1)}R的自反闭包是：70000100001001100001010100110111000011001010111010011101101111111包含R具有自反性是“最小的”闭包一般将关系

R

的自反闭包记作

r(R)对称闭包记作

s(R)传递闭包记作

t(R)8自反闭包（ReflexiveClosure）设R

是集合

A

上的一个关系，则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）设R

是集合

A

上的一个关系，则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）定理

设

R

为集合

A

上的任意二元关系，则

R

是R

的传递闭包。13传递闭包（TransitiveClosure）证明： ①R

R

②R

具有传递性

若

aR

b

且

bR

c

，则存在

R

中从

a到

b

的道路

1和从

b

到

c

的道路

2，

于是

1

和

2

的复合即是为从

a

到

c

的道路，

因此有

aR

c

，R

具有传递性。

14abc传递闭包（TransitiveClosure）证明： ③R

是“最小的”

对于A

上任一满足

R

S的传递关系

S，由其满足传递性知对于所有

n≥1，Sn

S，于是R

=R∪R2∪R3∪…

S∪S2∪S3∪…

S。15使用关系矩阵计算关系的闭包假设|A|=n自反闭包Mr(R)=

MR∨In对称闭包Mr(R)=

MR∨(MR)T传递闭包MR

=

MR∨MR2∨MR3∨…∨MRn16关系的闭包运算在关系图的表现自反闭包每个顶点如果没有自环则增加自环对称闭包如果有顶点i到顶点j的有向边且

i

j

，则添加（如果该图中不存在）有向边

(j,i)或者保留该关系的有向图中的顶点，且将所有有向边改作无向边传递闭包不断更新有向图：如果存在顶点

i

到

j

的道路，则将边

(i,j)

添加到有向图中（如果该图中不存在），直至没有新的有向边可添加为止17沃舍尔算法设

R

为集合

A

上的任意二元关系，则

R

是R

的传递闭包。假设

R

是有限集合

A

上的关系，|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算法纸上作业法第k次第k行为1元素所在列画纵向直线，第k列为1元素所在行画横向直线，直线相交位置如果为0，则改为1。24Warshall算法纸上作业法250110010110000010k=1Warshall算法纸上作业法260110011110000010k=1k=2Warshall算法纸上作业法271110111110001010k=3Warshall算法纸上作业法281111111110001010k=4Warshall算法纸上作业法291111111111111111Warshall算法纸上作业法和Warshall算法的关系？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算法纸上作业法310110011110000010k=1k=2C[

,2]=1C[2,

]=1C[

,

]关系闭包运算的性质定理1

假设

R

是集合

A

上的关系，则R

是自反的当且仅当

r(R)=RR

是对称的当且仅当

s(R)=RR

是传递的当且仅当

t(R)=R32关系闭包运算的性质证明：(c)

R是传递的当且仅当

t(R)=R(1)假设R

是传递的，则：

R

是传递的

R

R

对于任何包含

R

的传递关系

S

都有

R

S(2)假设t(R)=R则

R

是某个关系的传递闭包，其必然是传递的

33关系闭包运算的性质定理2

假设

R,S

是集合

A

上的关系且

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关系闭包运算的性质定理3

假设

R是集合

A上的关系，则(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关系闭包运算的性质定理3

假设

R是集合

A上的关系，则(a)如果

R

是自反的，那么

s(R)和

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

R

是对称的，那么

r(R)和

t(R)都是对称的(c)如果

R

是传递的，那么

r(R)是传递的。

36那么s(R)呢？关系闭包运算的性质定理4

设

R

是集合

A上任一二元关系，则(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关系闭包运算的性质定理4

设

R

是集合

A上任一二元关系，则(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))？第四章二元关系§4.4关系的闭包§4.5等价关系和集合的划分§4.5.1等价关系、等价类和商集§4.5.2集合的划分§4.5.3等价关系与划分的一一对应*§4.6相容关系与集合的覆盖39等价关系假设

R

是非空集合

A

上的关系，如果

R

是自反的、对称的和传递的，则称

R

是

A

上的等价关系（equivalencerelation）。40等价关系例恒等关系、三角形的相似关系、“同班同学”关系、矩阵的相似关系41等价关系A={1,2,…,8}，则A

上的“模3同余”关系

R是一个

A

上的等价关系A

上的“模2同余”关系

S

是一个

A

上的等价关系42等价关系A={1,2,…,8}，A

上的“模3同余”关系

R43等价关系假设

R

是非空集合

A

上的等价关系，元素

a

A，集合

R(a)称为

a

所在的等价类（equivalenceclass），也记作

[a]R或

[a]。集合

{R(a)|a

A}称作

A

关于

R

的商集（quotientsets），记作

A/R

；a

称作R(a)的代表元。44等价关系例设A={1,2,3,4}，定义

A

A上的关系

R

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

当且仅当

x+y

=u+v

。则R

是一个等价关系。那么，(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等价关系(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等价关系定理

设

R

是

A

上的一个等价关系，

a,b

A，则

aRb

当且仅当R(a)=R(b)。47等价关系证明

“”

假设R(a)=R(b)。则由

R

具有自反性有

b

R(b)。

于是

b

R(a)，也即

aRb

。48设

R

是

A

上的一个等价关系，a,b

A，则

aRb

当且仅当R(a)=R(b)。等价关系证明 “

”

假设

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设

R

是

A

上的一个等价关系，a,b

A，则

aRb

当且仅当R(a)=R(b)。等价关系例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)}都是等价关系。而R∪S={(a,a),(b,b),(c,c),(a,b),

(b,a),(b,c),(c,b)}则不是等价关系。50等价关系定理

假设

A两个集合，R、S为集合

A

上的两个等价关系，则

R∩S也是等价关系。（为什么？）但一般来讲

R∪S不一定也是等价关系。

（为什么？）

51等价关系定理

假设

R、S

为集合

A

上的等价关系，则包含

R∪S的最小等价关系为

(R∪S)

52等价关系证明：(1)显然

R∪S

(R∪S)

。(2)(R∪S)

实际上是一个等价关系：R∪S具有自反性和对称性故而(R∪S)

=t(R∪S)也具有自反性和对称性(R∪S)

=t(R∪S)明显具有传递性(3)对于任何包含

R∪S

的等价关系

T

，T

必定具有传递性，

由于(R∪S)

是

R∪S

的传递闭包，

因此

(R∪S)

T。

53第四章二元关系§4.4关系的闭包§4.5等价关系和集合的划分§4.5.1等价关系、等价类和商集§4.5.2集合的划分§4.5.3等价关系与划分的一一对应*§4.6相容关系与集合的覆盖*§4.7关系在计算机中的表示方法54划分一个问题——将学生们分成若干个小组每名同学一定在某个小组中没有同学同时出现在不同小组中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},{d},{h,l,p}}构成一个划分abefijmncgkodhlp划分{

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

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

{c,d,h},

{l,p}}构成一个划分59abefijmncgkodhlp划分{

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

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

{l,n,o,p}}构成划分么？60abefijmncgkodhlp划分{

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

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

{j,l,n,o,p}}构成划分么？61abefijmncgkodhlp划分假设

A

是整数集的任一子集，n

是一个大于1的正整数则可以根据模n

的余数对

A

进行划分62划分如何证明

P

是

A的一个划分？①对于任意a

A

，存在B

P，使得a

B；②对于任意

A1,

A2

P，

A1

A2，则A1∩A2=Ø。63第四章二元关系§4.4关系的闭包§4.5等价关系和集合的划分§4.5.1等价关系、等价类和商集§4.5.2集合的划分§4.5.3等价关系与划分的一一对应*§4.6相容关系与集合的覆盖*§4.7关系在计算机中的表示方法64由划分构造等价关系“分班”“同班同学关系”“划分”

“等价关系”？65由划分构造等价关系66A上等价关系A的划分由划分构造等价关系定理

设

P

是集合

A

的一个划分，定义

A

上的关系

R

为：

aRb

当且仅当

a

和

b

属于同一个划分块。

则

R

是

A

上的一个等价关系。67由划分构造等价关系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由划分构造等价关系定理的证明 (a)自反性？

若

a

A

则明显

a

在自己所处的划分块中，于是

aRa

。 (b)对称性？

若

aRb

则

a

与

b

处于相同的划分块，于是

bRa

。 (c)传递性？

若

aRb

且

bRc

则

a

与

b

处于相同的划分块、b与

c

处于相同的划分块，于是

aRc

。69abc由划分构造等价关系R

称作由

P决定的等价关系。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)}由等价关系得到划分71A上等价关系A的划分例由等价关系得到划分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由等价关系得到划分定理

设

R

是

A

上的一个等价关系，则

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

A}是

A

的一个划分，

而且

R

就恰是由

P

决定的等价关系。73由等价关系得到划分定理的证明：

要证明

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)，产生矛盾。74由等价关系得到划分定理的证明：

而且由引理知，aRb

当且仅当

a,b

属于P

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

A}的同一个划分块，因此

P

决定的等价关系就是

R

。75由等价关系得到划分76A上等价关系A的划分由等价关系得到划分定理所构造的划分

P

由

R

的所有等价类构成，也记作

A/R

。77A/R={{a,b,c,d},{e,f}}bafcde由等价关系得到划分由划分与等价关系的一一对应，可得：定理

设

R1和

R2为非空集合

A

上的等价关系，则

R1=R2当且仅当

A/R1=A/R2。78第四章二元关系§4.4关系的闭包§4.5等价关系和集合的划分§4.5.1等价关系、等价类和商集§4.5.2集合的划分§4.5.3等价关系与划分的一一对应*§4.6相容关系与集合的覆盖79相容关系与集合的覆盖在实际问题中往往有些关系不具有传递性，例如朋友关系、父子关系等就不具有传递性，本节介绍一种应用广泛的新的关系——相容关系。80相容关系与集合的覆盖定义设

X

是非空集合，S

P(X)

，如果

，则称

S是集合

X

的一个覆盖（covering）。例设

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

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

X

的覆盖。81相容关系与集合的覆盖定义设

R

为集合

X

上的二元关系，如果R具有自反性和对称性，则称

R

为

X

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