离散数学关系的运算

《离散数学关系的运算》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、y(R)}。使（x,y）∈R的所有y组成的集合称为R的值域，记为ranR。即ranR={y

3、x(R)}。称domRranR为R的域，记为fldR。即fldR=domRranR。解：根据题意R1={(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)}故前域domR1={1,2

4、,3},值域ranR1={2,3,4}，fldR={1,2,3,4}。例1设A={1，2，3，4}，R1是A上的二元关系，当a,b∈A，且a

5、R}R∘S=

6、

7、y(R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

8、,3>}S∘R={<1,2>,<1,4>,<3,2>,<3,3>}4合成运算的图示方法利用图示（不是关系图）方法求合成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。53、限制与像定义F在A上的限制F↾A={

9、xFyxA}A在F下的像F[A]=ran(F↾A)例3设R={<1,2>,<2,3>,<1,4>,<2,2>}，则R↾{1}=

10、{<1,2>,<1,4>}R[{1}]={2,4}R↾=R[{1,2}]={2,3,4}注意：F↾AF,F[A]ranF6二、关系基本运算的性质定理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17定理　设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ο

11、R)∩(TοR)（5）Rο(SοT)=(RοS)οT8三、A上关系的幂运算设R为A上的关系,n为自然数,则R的n次幂定义为：(1)R0={

12、x∈A}=IA(2)Rn+1=Rn∘R注意：对于A上的任何关系R1和R2都有R10=R20=IA对于A上的任何关系R都有R1=R9例：10定理设R是A上的关系,m,n∈N,则(1)Rm∘Rn=Rm+n(2)(Rm)n=Rmn四、幂运算的性质11关系运算的矩阵表示关系矩阵（matrixofrelation）。设RA×B，A=｛a1,a2,…,am｝,B=｛b1,b2,…,bn｝，那么R的关系矩阵MR为一m×n矩阵，

13、它的第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布尔乘法（∧）：1·1=10·1=1·0=0·0=015R0,R1,R2,R3,…的关系图如下图所示五、幂的求法例3设A={a,b,c,d},R={,,,},求R的各次幂,分别用矩阵和关系图表示

14、.解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上的关系,由于

15、A

16、=n,

17、A上的不同关系只有个.当列出R的各次幂