离散数学关系的运算

离散数学关系的运算演示文稿第1页，共20页。（优选）离散数学关系的运算第2页，共20页。32、逆与合成

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页，共20页。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

。

第4页，共20页。53、限制与像定义

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页，共20页。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页，共20页。7定理设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页，共20页。8三、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页，共20页。9例：第9页，共20页。10定理设R是A上的关系,m,n∈N,则

(1)Rm∘Rn=Rm+n

(2)(Rm)n=Rmn

四、幂运算的性质第10页，共20页。11关系运算的矩阵表示关系矩阵（matrixofrelation）。设R

A×B，A=｛a1,a2,…,am｝,B=｛b1,b2,…,bn｝，那么R的关系矩阵

MR为一m×n矩阵，它的第i,j分量rij

只取值0或1，而当且仅当aiRbj

当且仅当

第11页，共20页。12某关系R的关系图为：则R的关系矩阵为：第12页，共20页。13思考：写出集合A=｛1,2,3,4｝上的恒等关系、空关系、全域关系和小于关系的关系矩阵。答案：分别为：第13页，共20页。14在讨论关系矩阵运算前,我们先定义布尔运算,它只涉及数字0和1。布尔加法（∨）：

0+0=0

0+1=1+0=1+1=1布尔乘法（∧）：

1·1=1

0·1=1·0=0·0=0第14页，共20页。15R0,R1,R2,R3,…的关系图如下图所示五、幂的求法例3设A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>},求R的各次幂,分别用矩阵和关系图表示.

解R与R2的关系矩阵分别为第15页，共20页。16幂的求法（续）对于集合表示的关系R，计算Rn就是n个R右复合.矩阵表示就是n个矩阵相乘,其中相加采用逻辑加.例3设A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>},求R的各次幂,分别用矩阵和关系图表示.

解R与R2的关系矩阵分别为第16页，共20页。17同理，R0=IA,R3和R4的矩阵分别是：因此M4=M2,即R4=R2.因此可以得到

R2=R4=R6=…,R3=R5=R7=…

幂的求法（续）第17页，共20页。18六、幂运算的性质定理设A为n元集,R是A上的关系,则存在自然数s和t,使得Rs=Rt.证R为A上的关系,由于|A|=n,A上的不同关系只有个.当列出R的各次幂

R0,R1,R2,…,,…,必存在自然数s和t使得Rs=Rt.第18页，共20页。19定理设R

A

A,若存在自然数s,t(s<t),使得Rs=Rt,则下面等式成立：(1)Rs+q=Rt+q,q

N;证明

Rs+q=RsRq=RtRq=Rt+q。(2)Rs+(t–s)q+r=Rs+r,其中q,r

N;证明对q用归纳法证明。 当q=1,Rs+(t–s)q+r=Rs+(t–s)+r=Rt+r=Rs+r(1)

设q=k时,命题成立,

即Rs+(t–s)k+r=Rs+r,其中q,r

N;

当q=k+1时,Rs+(t–s)(k+1)+r