《离散数学关系的运算.ppt》由会员分享，可在线阅读，更多相关《离散数学关系的运算.ppt（22页珍藏版）》请在三一办公上搜索。
1、1,基本运算定义定义域、值域、域逆、合成、限制、像基本运算的性质幂运算定义求法性质,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为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=
2、1,2,3,4。,例1 设A=1，2，3，4，R1是A上的二元关系，当a,b A，且ab 时，(a,b)R1,求R和它的前域，值域和域。,3,2、逆与合成 R1=|R RS=|y(RS),例2 已知 R=,，,，S=,，求R1，RS，SR。,解：R1=,RS=,SR=,4,合成运算的图示方法,利用图示（不是关系图）方法求合成 RS=,SR=,例2 已知 R=,，,，S=,，求R1，RS，SR。,5,3、限制与像,定义 F 在A上的限制 FA=|xFy xA A 在F下的像 FA=ran(FA),例3 设 R=,，则 R1=,R1=2,4 R=R1,2=2,3,4注意：FAF,FA ranF,6
3、,二、关系基本运算的性质,定理1 设F是任意的关系,则(1)(F1)1=F(2)domF1=ranF,ranF1=domF,定理2 设F,G,H是任意的关系,则(1)(FG)H=F(GH)(2)(FG)1=G1F1,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)T,8,三、A上关系的幂运算,设R为A上的关系,n为自然数,则 R 的 n次幂定义为：(1)R0=|xA=IA(2)Rn+1=RnR 注意：对于A上的任何关系R1和
4、R2都有 R10=R20=IA 对于A上的任何关系 R 都有 R1=R,9,例：,10,定理 设 R 是 A 上的关系,m,nN,则(1)RmRn=Rm+n(2)(Rm)n=Rmn,四、幂运算的性质,11,关系运算的矩阵表示关系矩阵（matrix of relation）。设RAB，A=a1,a2,am,B=b1,b2,bn，那么R的关系矩阵 MR为一mn矩阵，它的第i,j分量rij只取值0或1，而,当且仅当aiRbj,当且仅当,12,某关系R的关系图为：,则R的关系矩阵为：,13,思考：写出集合A=1,2,3,4 上的恒等关系、空关系、全域关系和小于关系的关系矩阵。,答案：分别为：,14,在
5、讨论关系矩阵运算前,我们先定义布尔运算,它只涉及数字0和1。布尔加法（）：0+0=0 0+1=1+0=1+1=1布尔乘法（）：1 1=1 0 1=1 0=0 0=0,15,R0,R1,R2,R3,的关系图如下图所示,五、幂的求法,例3 设A=a,b,c,d,R=,求R的各次幂,分别用矩阵和关系图表示.解 R与R2的关系矩阵分别为,16,幂的求法（续）,对于集合表示的关系R，计算 Rn 就是n个R右复合.矩阵表示就是n个矩阵相乘,其中相加采用逻辑加.例3 设A=a,b,c,d,R=,求R的各次幂,分别用矩阵和关系图表示.解 R与R2的关系矩阵分别为,17,同理，R0=IA,R3和R4的矩阵分别是
6、：因此M4=M2,即R4=R2.因此可以得到R2=R4=R6=,R3=R5=R7=,幂的求法（续）,18,六、幂运算的性质,定理 设A为n元集,R是A上的关系,则存在自然数 s 和 t,使得 Rs=Rt.证 R为A上的关系,由于|A|=n,A上的不同关系只有 个.当列出 R 的各次幂 R0,R1,R2,必存在自然数 s 和 t 使得 Rs=Rt.,19,定理 设R A A,若存在自然数s,t(st),使得Rs=Rt,则下面等式成立：(1)Rs+q=Rt+q,qN;证明 Rs+q=RsRq=RtRq=Rt+q。(2)Rs+(ts)q+r=Rs+r,其中q,rN;证明对q用归纳法证明。当q=1,R
7、s+(ts)q+r=Rs+(ts)+r=Rt+r=Rs+r(1)设q=k时,命题成立,即Rs+(ts)k+r=Rs+r,其中q,rN;当q=k+1时,Rs+(ts)(k+1)+r=Rs+(ts)k+r+(ts)=Rs+(ts)k+r R(ts)=Rs+r Rts(归纳假设)=Rs+r+ts=Rt+r=Rs+r(1)所以,(2)成立,20,(2)Rs+(ts)q+r=Rs+r,其中q,rN;(3)令S=R0,R1,Rt1,则对于任意nN,均有RnS。(ss,因而存在q,rN,使得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。,21,Rs+(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+21000+0=R3+0=R3R0,R1,R4,22,Rs+(ts)q+r=Rs+r,(2)s=7,t=15,n=2000,=249 8+1,因此,q=249,r=1,R2000=R7+8249+1=R7+1=R8R0,R1,R14,
