离散数学关系的运算.ppt
离散数学关系的运算现在学习的是第1页，共22页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=1,2,3,4。例例1 设设A=1，2，3，4，R1是是A上的二元关系，当上的二元关系，当a,b A，且且ab 时，时，(a,b)R1 ,求求R和它的前域，值域和域。和它的前域，值域和域。现在学习的是第2页，共22页32、逆、逆与与合成合成 R 1=|R R S=|y(R S)例例2 已知已知 R=,，,，S=,，求求R 1，R S，S R。解：解：R 1=,R S=,S R=,现在学习的是第3页，共22页4合成运算的图示方法合成运算的图示方法 利用图示（不是关系图）方法求合成利用图示（不是关系图）方法求合成 R S=,S R=,例例2 已知已知 R=,，,，S=,，求求R 1，R S，S R。现在学习的是第4页，共22页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 现在学习的是第5页，共22页6二、关系基本运算的性质二、关系基本运算的性质 定理定理1 设设F是任意的关系是任意的关系,则则(1)(F 1)1=F(2)domF 1=ranF,ranF 1=domF定理定理2 设设F,G,H是任意的关系是任意的关系,则则 (1)(F G)H=F(G H)(2)(F G)1=G 1 F 1 现在学习的是第6页，共22页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现在学习的是第7页，共22页8三三、A上关系的幂运算上关系的幂运算设设R为为A上的关系上的关系,n为自然数为自然数,则则 R 的的 n次幂次幂定义为：定义为：(1)R0=|xA=IA (2)Rn+1=Rn R 注意：注意：对于对于A上的任何关系上的任何关系R1和和R2都有都有 R10=R20=IA 对于对于A上的任何关系上的任何关系 R 都有都有 R1=R 现在学习的是第8页，共22页9,2bcabcaR,accbbaR,cbaX 例：例：xIccbbaaRRR,23现在学习的是第9页，共22页10定理定理 设设 R 是是 A 上的关系上的关系,m,nN,则则 (1)Rm Rn=Rm+n (2)(Rm)n=Rmn 四、幂运算的性质四、幂运算的性质现在学习的是第10页，共22页11n关系运算的矩阵表示关系运算的矩阵表示n关系矩阵（关系矩阵（matrix of relation）。）。设设RAB，A=a1,a2,am,nB=b1,b2,bn，那么那么R的关系矩阵的关系矩阵 nMR为一为一mn矩阵，它的第矩阵，它的第i,j分量分量rij只只取值取值0或或1，而而10ijr当且仅当当且仅当aiRbj 当且仅当当且仅当 ija R b现在学习的是第11页，共22页12某关系某关系R的关系图为：的关系图为：234615abcd则R的的关系关系矩阵为：矩阵为：000011000100001000000010RM现在学习的是第12页，共22页13n思考：思考：写出集合写出集合A=1,2,3,4 上的恒等关系、上的恒等关系、空关系、空关系、全域关系和小于关系的关系矩阵。全域关系和小于关系的关系矩阵。100000000100000000100000000100001 1 1 101111 1 1 100111 1 1 100011 1 1 10000AAIA ALMMMM答案：分别为：答案：分别为：现在学习的是第13页，共22页14n在讨论关系矩阵运算前在讨论关系矩阵运算前,我们先定义布尔运算我们先定义布尔运算,它只它只涉及数字涉及数字0和和1。n布尔加法（布尔加法（）：0+0=0 0+1=1+0=1+1=1n布尔乘法（布尔乘法（）：1 1=1 0 1=1 0=0 0=0现在学习的是第14页，共22页15R0,R1,R2,R3,的关系图如下图所示的关系图如下图所示五、幂的求法五、幂的求法例例3 设设A=a,b,c,d,R=,求求R的各次幂的各次幂,分别用矩阵和关系图表示分别用矩阵和关系图表示.解解 R与与R2的关系矩阵分别为的关系矩阵分别为现在学习的是第15页，共22页16幂的求法（续）幂的求法（续）对于集合表示的关系对于集合表示的关系R，计算，计算 Rn 就是就是n个个R右复合右复合.矩阵表示就是矩阵表示就是n个矩阵相乘个矩阵相乘,其中相加采用逻辑加其中相加采用逻辑加.例例3 设设A=a,b,c,d,R=,求求R的各次幂的各次幂,分别用矩阵和关系图表示分别用矩阵和关系图表示.解解 R与与R2的关系矩阵分别为的关系矩阵分别为 0000100001010010M 0000000010100101000010000101001000001000010100102M现在学习的是第16页，共22页17同理，同理，R0=IA,R3和和R4的矩阵分别是：的矩阵分别是：因此因此M4=M2,即即R4=R2.因此可以得到因此可以得到R2=R4=R6=,R3=R5=R7=0000000010100101,000000000101101043MM 10000100001000010M幂的求法（续）幂的求法（续）现在学习的是第17页，共22页18六、幂运算的性质六、幂运算的性质定理定理 设设A为为n元集元集,R是是A上的关系上的关系,则存在自然数则存在自然数 s 和和 t,使得使得 Rs=Rt.证证 R为为A上的关系上的关系,由于由于|A|=n,A上的不同关系只上的不同关系只有有 个个.当列出当列出 R 的各次幂的各次幂 R0,R1,R2,必存在自然数必存在自然数 s 和和 t 使得使得 Rs=Rt.22n现在学习的是第18页，共22页19定理定理 设设R A A,若存在自然数若存在自然数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 (归纳假设归纳假设)=Rs+r+ts=Rt+r=Rs+r (1)所以所以,(2)成立成立 现在学习的是第19页，共22页20(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。现在学习的是第20页，共22页21nRs+(ts)q+r=Rs+r,例例 设设R A A,化简化简R2003的指数。的指数。(1)已知已知 R3=R5；(2)已知已知 R7=R15。解解(1)s=3,t=5,n=2003,=100022000stsn=1000 1+0,因此因此,q=1000,r=0,R2003=R3+2 1000+0=R3+0=R3 R0,R1,R4现在学习的是第21页，共22页22nRs+(ts)q+r=Rs+r,(2)s=7,t=15,n=2000,=249 8+1,stsn81993因此因此,q=249,r=1,R2000=R7+8 249+1=R7+1=R8 R0,R1,R14现在学习的是第22页，共22页
