复合关系逆关系及闭包

复合关系逆关系及闭包2023/5/261第一页，共三十四页，编辑于2023年，星期五3-7.2逆关系定义2[逆(inverse)关系]:

设R是X到Y的二元关系，则从Y到X的二元关系Rc定义为：Rc={<y,x>|<x,y>R}.整数集合上的“>”关系的逆关系是“<”关系。人群中的父子关系的逆关系是子父关系。容易看出(Rc)c=R2023/5/262第二页，共三十四页，编辑于2023年，星期五例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页）2023/5/263第三页，共三十四页，编辑于2023年，星期五定理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)zzR3w)

z(zZ

y(yY

xR1yyR2z)zR3w)

zy(zZ

yY

xR1yyR2zzR3w)

ytz(zZ

yY

xR1y(yR2zzR3w))

y(yY

xR1yz(zZ

yR2zzR3w))

y(yY

xR1yy(R2°R3)w)

xR1°(R2°R3)w<x,w>R1°(R2°R3)

(R1°R2)°R3

=R1°(R2

°

R3).#说明:本定理说明复合运算满足结合律.2023/5/264第四页，共三十四页，编辑于2023年，星期五

由复合关系满足结合律，可以把关系R本身所组成的复合关系写成：R°R，R°R°R，，R°R°°R(m个)，分别记作R(2)，R(3)，，R(m)。可以证明复合关系不满足交换律。R1°R2R2°R12023/5/265第五页，共三十四页，编辑于2023年，星期五7-3.3关系矩阵的性质：(1)MRc=(MR)T(T表示矩阵转置)(2)MR1°R2=MR1MR2

(表示布尔乘法,其中加法使用逻辑,乘法使用逻辑

)2023/5/266第六页，共三十四页，编辑于2023年，星期五3-7.4逆关系关系图的性质：关系Rc的图形是将关系R图形中弧的箭头方向反置。2023/5/267第七页，共三十四页，编辑于2023年，星期五定理2:

设R、R1

、R2都是从A到B的二元关系，则有(1)(R1R2)c=R1cR2c(2)(R1R2)c=R1cR2c(3)(A×B)c=B×A(4)(~R)c=

~Rc,这里~R＝A×B-R(5)(R1-R2)c=R1c-R2c注：证明(1)(4)(5)见书117页。2023/5/268第八页，共三十四页，编辑于2023年，星期五定理3:

设R,S为二元关系,则(R°S)c=Sc°Rc.证明:<x,y>,<x,y>(R°S)c

<y,x>(R°S)

z(yRzzSx)

z(zRcyxScz)

z(xSczzRcy)

<x,y>Sc°Rc.2023/5/269第九页，共三十四页，编辑于2023年，星期五定理4:设R为X上的二元关系，则(1)R是对称的R=Rc（证明见书118页）(2)是反对称的RRcIX定理5:[P119(2)]设R为X上的二元关系，则(1)R是传递的(R°R)R(2)R是自反的IXR2023/5/2610第十页，共三十四页，编辑于2023年，星期五例题:设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,从而求出它们的集合表达式.2023/5/2611第十一页，共三十四页，编辑于2023年，星期五110110MR1=101MR1c=100000010011000MR2=001MR2c=100000110011MR1R2=MR1MR2=011000R1°R2

={<a,b>,<a,c>,<b,b>,<b,c>}.2023/5/2612第十二页，共三十四页，编辑于2023年，星期五110110111MR1R1=MR1MR1=101101=110000000000R1°R1

={<a,a>,<a,b>,<a,c>,<b,a>,<b,b>}.011110101MR2R1=MR2MR1=001101=000000000000R2°R1

={<a,b>,<a,c>}.2023/5/2613第十三页，共三十四页，编辑于2023年，星期五解: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>}.2023/5/2614第十四页，共三十四页，编辑于2023年，星期五作业(3-7)：P118(1)(5)2023/5/2615第十五页，共三十四页，编辑于2023年，星期五3-8关系的闭包运算自反闭包r(R)(reflexivityclosure)对称闭包s(R)(symmetryclosure)传递闭包t(R)(transitivityclosure)闭包的性质,求法,相互关系2023/5/2616第十六页，共三十四页，编辑于2023年，星期五3-8.1自反闭包(reflexiveclosure)定义1[自反闭包]:

包含给定关系R的最小自反关系,称为R的自反闭包,记作r(R).(1)r(R)是自反的;(2)Rr(R);(3)(S)((RSS自反)r(R)S).2023/5/2617第十七页，共三十四页，编辑于2023年，星期五3-8.2对称闭包(symmetricclosure)定义2[对称闭包]:

包含给定关系R的最小对称关系,称为R的对称闭包,记作s(R).(1)s(R)是对称的;(2)Rs(R);(3)(S)((RSS对称)s(R)S).2023/5/2618第十八页，共三十四页，编辑于2023年，星期五3-8.3传递闭包(transitiveclosure)定义3[传递闭包]:

包含给定关系R的最小传递关系,称为R的传递闭包,记作t(R).(1)t(R)是传递的;(2)Rt(R);(3)(S)((RSS传递)t(R)S).2023/5/2619第十九页，共三十四页，编辑于2023年，星期五定理1:设RAA且A,则

(1)R自反

r(R)=R;(2)R对称

s(R)=R;(3)R传递

t(R)=R;证明:(1)RRR自反

r(R)R

又Rr(R),r(R)=R.(2)(3)完全类似.2023/5/2620第二十页，共三十四页，编辑于2023年，星期五*（补充）定理1:设R1R2AA且A,则

(1)r(R1)r(R2);(2)s(R1)s(R2);(3)t(R1)t(R2);证明:(1)R1R2r(R2)自反,

r(R1)r(R2)(2)(3)类似可证.2023/5/2621第二十一页，共三十四页，编辑于2023年，星期五*（补充）定理2:设R1,R2AA且A,则

(1)r(R1R2)=r(R1)r(R2);(2)s(R1R2)=s(R1)s(R2);(3)t(R1R2)t(R1)t(R2).证明:(1)利用定理20,r(R1R2)r(R1)r(R2).r(R1)r(R2)自反且包含R1R2,所以

r(R1R2)r(R1)r(R2).

r(R1R2)=r(R1)r(R2)2023/5/2622第二十二页，共三十四页，编辑于2023年，星期五证明(2):利用定理20,s(R1R2)s(R1)s(R2).s(R1)s(R2)对称且包含R1R2,所以

s(R1R2)s(R1)s(R2).

s(R1R2)=s(R1)s(R2)证明(3):利用定理20,t(R1R2)t(R1)t(R2).

反例:t(R1R2)t(R1)t(R2).2023/5/2623第二十三页，共三十四页，编辑于2023年，星期五定理2:设RAA且A,则

(1)r(R)=RIA;(2)s(R)=RRc;(3)t(R)=RR2R3….对比:R自反

IARR对称

R=RcR传递

R2R2023/5/2624第二十四页，共三十四页，编辑于2023年，星期五证明:(1)r(R)=RIA;i)RRIA;ii)IARIARIA自反

r(R)RIA;iii)Rr(R)r(R)自反

Rr(R)IAr(R)RIAr(R)

r(R)=RIA.2023/5/2625第二十五页，共三十四页，编辑于2023年，星期五证明:(2)s(R)=RRc;i)RRRc;ii)(RRc)c=RRc

RRc对称

s(R)RRc;iii)Rs(R)s(R)对称Rs(R)Rcs(R)RRcs(R)

s(R)=RRc.2023/5/2626第二十六页，共三十四页，编辑于2023年，星期五证明(3)之前，说明以下事实：复合运算对并运算满足分配律R1

°(R2

R3)=(R1

°R2)(R1

°R3)(R1R2)°R3=(R1

°R3)(R2

°R3)复合运算对交运算满足弱分配律R1

°(R2R3)(R1°R2)(R1

°R3)(R1R2)°R3

(R1°R2)(R1

°R3)2023/5/2627第二十七页，共三十四页，编辑于2023年，星期五证明:(3)t(R)=RR2R3….证明:i)先证t(R)RR2R3…;∵RRR2R3…;∵(RR2R3…)2=R2R3…RR2R3…

RR2R3…传递

∴t(R)RR2R3…;ii)再证RR2R3…t(R)∵Rt(R)t(R)传递

Rt(R)R2t(R)R3t(R)…

RR2R3…t(R)

t(R)=RR2R3….#2023/5/2628第二十八页，共三十四页，编辑于2023年，星期五定理3：设X是含有n个元素的集合，R是X上的二元关系，则存在一个正整数kn，使得t(R)=RR2R3…Rk证明：见P122。2023/5/2629第二十九页，共三十四页，编辑于2023年，星期五例题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)=RRc={<a,b>,<b,a>,<b,c>,<c,b>,<c,d><d,c>}t(R)=RR2R3R4

={<a,a>,<a,b>,<a,c>,<a,d>,<b,a>,<b,b>,<b,c>,<b,d>,<c,d>}见P1232023/5/2630第三十页，共三十四页，编辑于2023年，星期五求传递闭包的另一种方法：当有限集X的元素较多时，矩阵运算很繁琐，Warshall在1962年提出了R+的一个有效算法如下：（1）置新矩阵A=M（2）置i=1（3）对所有j如果A