离散数学关系的运算.ppt

第1页，共22页，星期日，2025年，2月5日*一、关系的基本运算定义1、定义域、值域和域定义设R是二元关系，由（x,y）∈R的所有x组成的集合称为R的前域，记为domR。即domR={x|?y(x,y?R)}。使（x,y）∈R的所有y组成的集合称为R的值域，记为ranR。即ranR={y|?x(x,y?R)}。称domR?ranR为R的域，记为fldR。即fldR=domR?ranR。解：根据题意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,b∈A，且ab时，(a,b)∈R1,求R和它的前域，值域和域。第2页，共22页，星期日，2025年，2月5日*2、逆与合成R?1={y,x|x,y?R}R°S=|x,z|?y(x,y?R?y,z?S)}例2已知R={1,2,1,4,2,2，2,3,}，S={1,1,1,3,2,3,3,2,3,3}，求R?1，R°S，S°R。解：R?1={2,1,3,2,4,1,2,2}R°S={1,3,2,2,2,3}S°R={1,2,1,4,3,2,3,3}第3页，共22页，星期日，2025年，2月5日*合成运算的图示方法利用图示（不是关系图）方法求合成R°S={1,3,2,2,2,3}S°R={1,2,1,4,3,2,3,3}例2已知R={1,2,1,4,2,2，2,3,}，S={1,1,1,3,2,3,3,2,3,3}，求R?1，R°S，S°R。第4页，共22页，星期日，2025年，2月5日*3、限制与像定义F在A上的限制F?A={x,y|xFy?x?A}A在F下的像F[A]=ran(F?A)例3设R={1,2,2,3,1,4,2,2}，则R?{1}={1,2,1,4}R[{1}]={2,4}R??=?R[{1,2}]={2,3,4}注意：F?A?F,F[A]?ranF第5页，共22页，星期日，2025年，2月5日*二、关系基本运算的性质定理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页，星期日，2025年，2月5日*定理设R,S,T均为A上二元关系，那么（1）Rο(S∪T)=(RοS)∪(RοT)（2）(S∪T)οR=(SοR)∪(TοR)（3）Rο(S∩T)(RοS)∩(RοT)（4）(S∩T)οR(SοR)∩(TοR)（5）Rο(SοT)=(RοS)οT第7页，共22页，星期日，2025年，2月5日*三、A上关系的幂运算设R为A上的关系,n为自然数,则R的n次幂定义为：(1)R0={x,x|x∈A}=IA(2)Rn+1=Rn°R注意：对于A上的任何关系R1和R2都有R10=R20=IA

对于A上的任何关系R都有R1=R第8页，共22页，星期日，2025年，2月5日*例：第9页，共22页，星期日，2025年，2月5日*定理设R是A上的关系,m,n∈N,则(1)Rm°Rn=Rm+n

(2)(Rm)n=Rmn四、幂运算的性质