离散数学 关系的运算_图文.ppt

《离散数学 关系的运算_图文.ppt》由会员分享，可在线阅读，更多相关《离散数学 关系的运算_图文.ppt（23页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1n基本运算定义基本运算定义定义域、值域、域定义域、值域、域逆、合成、限制、像逆、合成、限制、像n基本运算的性质基本运算的性质n幂运算幂运算定义定义求法求法性质性质4.2 关系的运算关系的运算2一、关系的基本运算定义一、关系的基本运算定义1、定义域、定义域、值域值域 和和 域域定义定义 设设R是二元关系，由（是二元关系，由（x,y）R 的所有的所有x 组成的集合组成的集合称为称为 R的前域，记为的前域，记为domR。即。即domR=x|y(R)。使（使（x,y）R 的所有的所有y组成的集合称为组成的集合称为R的值域，记为的值域，记为ranR。即即ranR=y|x(R)。称。称domR ranR

2、为为R的域，的域，记记为为fldR。即。即fldR=domR ranR。解：根据题意解：根据题意R1=(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)故前域故前域dom R1=1,2,3,值域值域 ran R1=2,3,4，fldR=1,2,3,4。例例1 设设A=1，2，3，4，R1是是A上的二元关系，当上的二元关系，当a,b A，且且ab 时，时，(a,b)R1 ,求求R和它的前域，值域和域。和它的前域，值域和域。32、逆、逆与与合成合成 R 1=|R R S=|y(R S)例例2 已知已知 R=,，,，S=,，求求R 1，R S，S R。解：解：R 1=,R S=,

3、S R=,4合成运算的图示方法合成运算的图示方法 利用图示（不是关系图）方法求合成利用图示（不是关系图）方法求合成 R S=,S R=,例例2 已知已知 R=,，,，S=,，求求R 1，R S，S R。53、限制与像、限制与像定义定义 F 在在A上的上的限制限制 F A=|xFy x A A 在在F下的下的像像 FA=ran(F A)例例3 设设 R=,，则，则 R 1=,R1=2,4 R=R1,2=2,3,4注意：注意：F A F,FA ranF 6二、关系基本运算的性质二、关系基本运算的性质 定理定理1 设设F是任意的关系是任意的关系,则则(1)(F 1)1=F(2)domF 1=ranF

4、,ranF 1=domF定理定理2 设设F,G,H是任意的关系是任意的关系,则则 (1)(F G)H=F(G H)(2)(F G)1=G 1 F 1 7定理设定理设R,S,T均为均为A上二元关系，上二元关系，那么那么（1）R(ST)=(R S)(R T)（2）(ST)R=(S R)(T R)（3）R(ST)(R S)(R T)（4）(ST)R(S R)(T R)（5）R(S T)=(R S)T8三三、A上关系的幂运算上关系的幂运算设设R为为A上的关系上的关系,n为自然数为自然数,则则 R 的的 n次幂次幂定义为：定义为：(1)R0=|xA=IA (2)Rn+1=Rn R 注意：注意：对于对于A

5、上的任何关系上的任何关系R1和和R2都有都有 R10=R20=IA 对于对于A上的任何关系上的任何关系 R 都有都有 R1=R 9例：例：10定理定理 设设 R 是是 A 上的关系上的关系,m,nN,则则 (1)Rm Rn=Rm+n (2)(Rm)n=Rmn 四、幂运算的性质四、幂运算的性质11n关系运算的矩阵表示关系运算的矩阵表示n关系矩阵（关系矩阵（matrix of relation）。）。设设RAB，A=a1,a2,am,nB=b1,b2,bn，那么那么R的关系矩阵的关系矩阵 nMR为为一一mn矩矩阵阵，它它的的第第i,j分分量量rij只只取取值值0或或1，而而当且仅当当且仅当aiRb

6、j 当且仅当当且仅当 12某关系某关系R的关系图为：的关系图为：则R的的关系关系矩阵为：矩阵为：13某关系某关系R的关系图为：的关系图为：则R的的关系关系矩阵为：矩阵为：14n思考：思考：写出集合写出集合A=1,2,3,4 上的恒等关系、上的恒等关系、空关空关系、系、全域关系和小于关系的关系矩阵。全域关系和小于关系的关系矩阵。答案：分别为：答案：分别为：15n在讨论关系矩阵运算前在讨论关系矩阵运算前,我们先定义布尔运算我们先定义布尔运算,它只涉及数字它只涉及数字0和和1。n布尔加法（布尔加法（）：0+0=0 0+1=1+0=1+1=1n布尔乘法（布尔乘法（）：1 1=1 0 1=1 0=0 0

7、=016R0,R1,R2,R3,的关系图如下图所示的关系图如下图所示五、幂的求法五、幂的求法例例3 设设A=a,b,c,d,R=,求求R的各次幂的各次幂,分别用矩阵和关系图表示分别用矩阵和关系图表示.解解 R与与R2的关系矩阵分别为的关系矩阵分别为17幂的求法（续）幂的求法（续）对于集合表示的关系对于集合表示的关系R，计算，计算 Rn 就是就是n个个R右复合右复合.矩阵表示就是矩阵表示就是n个矩阵相乘个矩阵相乘,其中相加采用逻辑加其中相加采用逻辑加.例例3 设设A=a,b,c,d,R=,求求R的各次幂的各次幂,分别用矩阵和关系图表示分别用矩阵和关系图表示.解解 R与与R2的关系矩阵分别为的关系

8、矩阵分别为18同理，同理，R0=IA,R3和和R4的矩阵分别是：的矩阵分别是：因此因此M4=M2,即即R4=R2.因此可以得到因此可以得到R2=R4=R6=,R3=R5=R7=幂的求法（续）幂的求法（续）19六、幂运算的性质六、幂运算的性质定理定理 设设A为为n元集元集,R是是A上的关系上的关系,则存在自然数则存在自然数 s 和和 t,使得使得 Rs=Rt.证证 R为为A上的关系上的关系,由于由于|A|=n,A上的不同关系只上的不同关系只有有 个个.当列出当列出 R 的各次幂的各次幂 R0,R1,R2,必存在自然数必存在自然数 s 和和 t 使得使得 Rs=Rt.20定理定理 设设R A A,

9、若存在自然数若存在自然数s,t(st),使得使得Rs=Rt,则下面等式成立：则下面等式成立：(1)Rs+q=Rt+q,q N;证明证明 Rs+q=RsRq=RtRq=Rt+q。(2)Rs+(ts)q+r=Rs+r,其中其中q,r N;证明证明对对q用归纳法证明。用归纳法证明。当当q=1,Rs+(ts)q+r=Rs+(ts)+r=Rt+r=Rs+r (1)设设q=k时时,命题成立命题成立,即即Rs+(ts)k+r=Rs+r,其中其中q,r N;当当q=k+1时时,Rs+(ts)(k+1)+r=Rs+(ts)k+r+(ts)=Rs+(ts)k+r R(ts)=Rs+r Rts (归纳假设归纳假设)

10、=Rs+r+ts=Rt+r=Rs+r (1)所以所以,(2)成立成立 21(2)Rs+(ts)q+r=Rs+r,其中其中q,r N;(3)令令S=R0,R1,Rt1,则对于任意则对于任意n N,均均有有Rn S。(ss,因而存在因而存在q,r N,使得使得n s=(t s)q+r (0rt s 1)即即n=s+(t s)q+r Rn=Rs+(ts)q+r =Rs+r (2)而而s+rs+t s 1=t 1,所以所以 Rn=Rs+r S。22nRs+(ts)q+r=Rs+r,例例 设设R A A,化简化简R2003的指数。的指数。(1)已知已知 R3=R5；(2)已知已知 R7=R15。解解(1)s=3,t=5,n=2003,=1000=1000 1+0,因此因此,q=1000,r=0,R2003=R3+2 1000+0=R3+0=R3 R0,R1,R423nRs+(ts)q+r=Rs+r,(2)s=7,t=15,n=2000,=249 8+1,因此因此,q=249,r=1,R2000=R7+8 249+1=R7+1=R8 R0,R1,R14大连婚纱摄影 http:/