lecture9关系的运算

《lecture9关系的运算》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、问：已经学过的关系的运算有哪一些？1）集合的运算：有一类运算：广义并，广义交，幂集，绝对补；和二类运算：并，交，相对补，对称差。2）关系特有的运算：有domR、ranR、fldR、R-1、R〇AFG和R[A]。为了使集合表达式更为简洁，我们进一步规定：本节所定义的关系运算中逆运算优先于其它运算，而所有的关系运算都优先于集合运算，对于没有优先权的运算以括号决定运算顺序。定理7.1设F是任意的关系，则(1)(F-1)-1=F(2)domF-1=ranF，ranF-1=domF证(1)任取，由逆的定义有∈

2、(F-1)-1∈F-1∈F。所以有(F-1)-1=F。(2)任取x,x∈domF-1y(∈F-1)y(∈F)x∈ranF所以有domF-1=ranF。定理7.2设F，G，H是任意的关系，则(1)(FoG)oH=Fo(GoH)(2)(FoG)-1=F-1oG-1证(1)任取,∈(FoG)oHt(∈FoG∧(t,y)∈H)t(s(∈F∧∈G)∧∈H)ts(∈F∧

3、∈G∧∈H)s(∈F∧t(∈G∧∈H))s(∈F∧∈GoH)∈F(GoH)所以(FoG)H=F(GoH)（2）任取,∈(FoG)-1∈FoGt(∈F∧(t,x)∈G)t(∈G-1∧(t,y)∈F-1)∈G-1oF-1所以（FoG）-1=F-1oG-1。定理7.3设R为A上的关系，则RoIA=IAoR=R证任取

4、>∈RoIAt(∈R∧(t,y)∈IA)t(∈R∧t=y)=>∈R∈R=>∈R∧y∈A=>∈R∧∈IA=>∈RoIA综合上述有RoIA=R。定理7.4设F，G，H是任意关系，则(1)Fo(G∪H)=FoG∪FoH(2)(G∪H)oF=GoF∪HoF(3)Fo(G∩H)FoG∩FoH(4)(G∩H)oFGoF∩HoF证(3)任取,∈Fo(G∩H)t(

5、∈F∧∈G∩H)t(∈F∧∈G∧∈H)t((∈F∧∈G)∧(∈F∧∈H))=>t(∈F∧∈G)∧t(∈F∧∈H))∈FoG∧∈FoH∈FoG∩FoH所以有F(G∩H)FG∩FH。由数学归纳法不难证明定理7.4的结论对于有限多个关系的并和交也是成立的，即有Ro(R1∪R2∪…∪Rn)=RoR1∪RoR2∪…∪RoRn(R1∪R2∪…∪Rn)oR=R1

6、oR∪R2oR∪…∪RnoRRo(R1∩R2∩…∩Rn)RoR1∩RoR2∩…∩RoRn(R1∩R2∩…∩Rn)oRR1oR∩R2oR∩…∩RnoR定理7.5设F为关系，A，B为集合，则(1)F(A∪B)=FA∪FB(2)F[A∪B]=F[A]∪F[B](3)F(A∩B)FA∩FB(4)F[A∩B]F[A]∩F[B]证(4)任取y，y∈F[A∩B]x(∈F∧x∈A∩B)x(∈F∧x∈A∧x∈B)x((∈F∧x∈A)∧(∈F∧x∈

7、B))=>x(∈F∧x∈A)∧x(∈F∧x∈B)y∈F[A]∧y∈F[B]y∈F[A]∩F[B]所以有F[A∩B]F[A]∩F[B]。定义7.10设R为A上的关系，n为自然数，则R的n次幂定义为：（1）R0={

8、x∈A}=IA（2）Rn+1=RnoR由以上定义可知，对于A上的任何关系R1和R2都有R10=R20=IA也就是说，A上任何关系的0次幂都相等，都等于A上的恒等关系IA。此外对于A上的任何关系R都有R1=R，因为R1=R0oR=IAoR=R给定A上的

9、关系R和自然数n，怎样计算Rn呢？若n是0或1，结果是很简单的。下面考虑n≥2的情况。如果R是用集合表达式给出的，可以通过n-1次右复合