lecture9关系的运算.ppt

问：已经学过的关系的运算有哪一些？ 1）集合的运算：有一类运算：广义并，广义交，幂集 ，绝对补；和二类运算：并，交，相对补，对称差。 2）关系特有的运算：有domR、ranR、fldR、R-1、RA F G和 RA。 为了使集合表达式更为简洁，我们进一步规定：本节所 定义的关系运算中逆运算优先于其它运算，而所有的关 系运算都优先于集合运算，对于没有优先权的运算以括 号决定运算顺序。 定理7.1 设F是任意的关系，则 (1)(F-1)-1=F (2)domF-1=ranF，ranF-1=domF 证 (1)任取，由逆的定义有 (F-1)-1F-1F。 所以有(F-1)-1=F。 (2)任取x, xdomF-1y(F-1) y(F)xranF 所以有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(FG)H) ts(FGH) s(Ft(GH) s(FGoH) 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 证 任取 RoIA t(R(t,y)IA) t(Rt=y) = R R = RyA = RIA = RoIA 综合上述有RoIA=R。 定理7.4 设F，G，H是任意关系，则 (1) Fo(GH)=FoGFoH (2) (GH)oF=GoFHoF (3) Fo(GH)FoGFoH (4) (GH)oFGoFHoF 证 (3) 任取, Fo(GH) t(FGH) t(FGH) t(FG)(FH) = t(FG) t(FH) FoGFoH FoGFoH 所以有F(GH)FGFH。 由数学归纳法不难证明定理7.4的结论对于有限多个关 系的并和交也是成立的，即有 Ro(R1R2Rn)=RoR1RoR2RoRn (R1R2Rn)oR=R1oRR2oRRnoR Ro(R1R2Rn)RoR1RoR2RoRn (R1R2Rn)oRR1oRR2oRRnoR 定理7.5 设F为关系，A，B为集合，则 (1) F (AB)=F AF B (2) FAB=FAFB (3) F (AB)F AF B (4) FABFAFB 证 (4) 任取y， yFAB x(FxAB) x(FxAxB) x(FxA)(FxB) = x(FxA)x(FxB) yFAyFB yFAFB 所以有FABFAFB。 定义7.10 设R为A上的关系，n为自然数，则R的n次幂定 义为： （1） R0=|xA=IA （2） Rn+1=RnoR 由以上定义可知，对于A上的任何关系R1和R2都有 R10=R20=IA 也就是说，A上任何关系的0次幂都相等，都等于A上的 恒等关系IA。 此外对于A上的任何关系R都有R1=R，因为 R1=R0oR=IAoR=R 给定A上的关系R和自然数n，怎样计算Rn呢？若n是0或 1，结果是很简单的。下面考虑n2的情况。 如果R是用集合表达式给出的，可以通过n-1次右复合计 算得到Rn。 如果R是用关系矩阵M给出的，则Rn的关系矩阵是Mn， 即n个矩阵M之积。与普通矩阵乘法不同的是，其中的 相加是逻辑加，即 1+1=1,1+0=0+1=1,0+0=0 如果R是用关系图G给出的，可以直接由图G得到Rn的关 系图G。G的顶点集与G相同。考察G的每个顶点xi，如 果在G中从xi出发经过n步长的路径到达顶点xj，则在G 中加一条从xi到xj的边。当把所有这样的便都找到以后 ，就得到图G。 例7.8 设A = a,b,c,d，R = ,， 求R的各次幂，分别用矩阵和关系图表示。 解 R的关系矩阵为 M= 则R2，R3，R4的关系矩阵分别是 M2= = M3=M2M= = M4=M3M= = 因此M4=M2，即R4=R2。因此可以得到 R2=R4=R6= R3=R5=R7= 而R0=IA，R各次幂的关系矩阵都得到了。 用关系图的方法得到R0, R1, R2, R3,的关系图如图所示 定理7.6 设A为n元集，R是A上的关系，则存在自然数s 和t,使得Rs=Rt。 证 R为A上的关系，对任何自然数k，Rk都是AA的子集 。又知|AA|=N=n2，|P(AA)|=2N，即AA的不同子集 仅2N个。当列出R的各次幂R0，R1，R2，R2N， 必存在自然数s和t使得Rs=Rt。 该定理说明有穷集上只有有穷多个不同的二元关系。当 t足够大时Rt必与某个Rs(s,。求出最小的自然数 m和n，使得mn且Rm=Rn。 解 由R的定义可以看出A中的元素可分成两组，即a,b 和d,e,f。它们在R的右复