复合关系逆关系及闭包

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)。可以证明复合关系不满足交换律。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作业(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