集合论与图论2.2.doc

1、2.3 关系的运算*关系的运算有七种,分别列出如下:定义 7.6: 设 R 是二元关系.(1) R 中所有有序对的第一个元素构成的集合称为 R 的定义域, 记作 domR.domR=x | y(R)(2) R 中所有有序对的第二个元素构成的集合称为 R 的值域,记作 ranR.ranR=y | x(R).(3) R 的定义域和值域的并集称为 R 的域,记作 fldR.fldR = domR ranR .例 1: R=,则domR=1,2,4ranR=2,3,4fldR=1,2,3,4定义 7.7:设 R 为二元关系,R 的逆关系,简称 R 的逆,记作 R-1,定义为 R-1=|R.定义 7.8

2、:设 F,G 为二元关系,G 对 F 的右复合,记做 F G,定义为 F G=| t(FG) .例 2:设 F=, G=,则F-1=,F G=G F=.*左复合:F G=| t(GF)*有些书上用左复合,但右复合比较直观,本书用右复合.定义 7.9:设 R 为二元关系,A 是集合(1) R 在 A 上的限制,记作 R|A,定义为R|A=|xRyxA(2) A 在 R 下的像,记作 RA,定义为RA=ran(R|A)*R|A 是 R 的子关系,RA是 ranR 的子集.例 3:设 R=,则R|1=,R|=R|2,3=,R1=2,3R=R3=2 .*关系运算的优先级:1.逆运算2.关系的其它运算3

3、.集合运算4.先括号里后括号外5.同级运算从左到右例子: ranF -1, F GF H, ran(F|A).*关系运算的性质:定理 7.1:设 F 是任意的关系,则(1)(F-1)-1= F(2)domF-1=ranF, ranF-1=domF.证明: (1)任取,由逆的定义,有(F -1)-1 F -1 F,所以(F -1)-1= F.(2)任取 x,xdomF -1 y(F -1) y(F) xranF .所以 domF -1 = ranF.同理可证 ranF-1 = domF.定理 7.2:设 F,G,H 是任意的关系,则(1)(F G) H=F (G H)(2)(F G)-1=G-1

4、 F-1证明:(1)任取,(F G) Ht(F GH)t( s(FG)H)t s(FGH)s(F t(GH)s(FG H)F (G H)所以(F G) H=F (G H).(1) 的另一种证明:对任意(F G) H,则存在 t 使得F G 且H.又由F G,有 s 使得F 且G.由G 和H,有G H,再由F,有F (G H).故(F G) H F (G H).对任意F (G H),存在 s,使得F 且G H.再由G H,存在 t,使得G 且H.由F 和G,有F G,再由H,有(F G) H.故(F G) H F (G H).因此(F G) H=F (G H).(2) 任取,(F G)-1F G

5、t(FG)t(F -1G -1)t(G -1F -1)G -1 F-1 .定理 7.3:设 R 是 A 上的关系,则R IA = IA R = R .证明:任取,R IAt(RI A)t(Rt=y)RRRyARI AR IA从而有 R IA=R.同理可证 IA R=R .定理 7.4:设 F,G,H 为任意关系,则(1) F (GH)=(F G)(F H)(2) (GH) F=(G F)(H F)(3) F (GH) F GF H(4) (GH) F G FH F .证明:只证(3)式.任取,F (GH)t(FGH)t(F(GH)t(FG)(FH)t(FG) t(FH)F GF HF GF H

6、 .定理 7.5:设 F 为关系,A,B 为集合,则(1) F|(AB)=F|AF|B(2) FAB=FAFB(3) F|(AB) F|AF|B(4) FAB FAFB证明:只证(4).任取 y,若 yFAB,则存在 x,使得F 且 xAB,那么有 xA 且 xB,也就存在 x,使得F 且 xA,故 yFA;同时还有F 且 xB.故 yFB.从而 yFAFB.因此 FAB FAFB .定义 7.10:设 R 为 A 上的关系,n 为自然数,则 R 的 n 次幂定义为:(1) R0=|xA=I A ;(2) Rn+1=Rn R .*利用关系矩阵计算 Rn:设 M 为 R 的关系矩阵,则 Rn 的

7、关系矩阵为 Mn.即 n 个 M 的乘积,其中的加法为逻辑加法:1+1=1, 1+0=1, 0+1=1, 0+0=0.例 4:设 A=a,b,c,d,R=,关系矩阵如下.计算后可知,M 4=M2.即 R4=R2,从而有R2=R4=R6=R3=R5=R7=M= 01R0 和 IA 的关系矩阵为单位矩阵 .定理 7.6:设 A 为 n 元集,R 是 A 上的关系,则存在自然数 s 和t,使得 Rs=Rt.证明:设 R 为 A 上的关系,对任意自然数 k,Rk 都是 AA 的子集.又知|AA|=n 2,|P(AA)|= ,即 AA 的不同子集仅有2n个 ,当列出 R 的各次幂 R0,R1,Rm 时(

8、m= ),必有自然数2n 2ns 和 t,使得 Rs=Rt.*如上例中的 R2=R4.定理 7.7: 设 R 为 A 上的关系,m,nN,则(1) Rm Rn=Rm+n ;(2) (Rm)n=Rmn .证明:用归纳法.(1) 对任意给定的 mN,施归纳于 n.若 n=0,则有 Rm R0=Rm IA=Rm=Rm+0 .假设 Rm Rn=Rm+n .Rm Rn+1=Rm (Rn R)=(Rm Rn) R=Rm+n R=Rm+n+1.*最后一步由定义可得.(2) 对于任意给定的 mN,施归纳于 n.若 n=0,则有 (Rm)0=IA=R0=Rm0.假设(R m)n,则有(Rm)n+1=(Rm)n Rm=Rmn Rm=Rmn+m=Rm(n+1).所以对一切 m,nN,有(R m)n=Rmn.定理 7.8:设 R 为 A 上的关系,若存在自然数 s,t(s,给出 R 的关系矩阵和关系图.2.设 A=,B=,.求 AB,AB,domA,domB,dom(AB),ranA,ranB,ran(AB),fld(AB).3.设 A=a,b,c,d,R1 和 R2 为 A 上的关系.其中:R1=,R2=,求 R1 R2, R2 R1, , .234.证明:定理 7.4 的(1),(4)和定理 7.5 的 (3).