离散数学关系的运算.pptVIP

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)。称domRranR为R的域，记为fldR。即fldR=domRranR。,解：根据题意R1=(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)故前域domR1=1,2,3,值域ranR1=2,3,4，fldR=1,2,3,4。,例1设A=1，2，3，4，R1是A上的二元关系，当a,bA，且ab时，(a,b)R1,求R和它的前域，值域和域。,3,2、逆与合成R1=|RRS=|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=|xFyxAA在F下的像FA=ran(FA),例3设R=,，则R1=,R1=2,4R=R1,2=2,3,4注意：FAF,FAranF,6,二、关系基本运算的性质,定理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)=(RS)(RT)（2）(ST)R=(SR)(TR)（3）R(ST)(RS)(RT)（4）(ST)R(SR)(TR)（5）R(ST)=(RS)T,8,三、A上关系的幂运算,设R为A上的关系,n为自然数,则R的n次幂定义为：(1)R0=|xA=IA(2)Rn+1=RnR注意：对于A上的任何关系R1和R2都有R10=R20=IA对于A上的任何关系R都有R1=R,9,例：,10,定理设R是A上的关系,m,nN,则(1)RmRn=Rm+n(2)(Rm)n=Rmn,四、幂运算的性质,11,关系运算的矩阵表示关系矩阵（matrixofrelation）。设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,在讨论关系矩阵运算前,我们先定义布尔运算,它只涉及数字0和1。布尔加法（）：0+0=00+1=1+0=1+1=1布尔乘法（）：11=101=10=00=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的矩阵分别是：因此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,定理设RAA,若存在自然数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,Rs+(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+rR(ts)=Rs+rRts(归纳假设)=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,使得ns=(ts)q+r(0rts1)即n=s+(ts)q+rRn=Rs+(ts)q+r=Rs+r(2)而s+rs+ts1=t1,所以Rn=Rs+rS。,21,Rs+(ts)q+r=Rs+r,例设RAA,化简R2003的指数。(1)已知R3=R5；(2)已知R7=R15。解(1)s=3,t=5,n=2003,=1000,=10001+0,因此,q=1000,r=0,R2003=R3+2100