離散數(shù)學關(guān)系的運算

離散數(shù)學關(guān)系的運算第1頁，共22頁，2023年，2月20日，星期一2一、關(guān)系的基本運算定義1、定義域、值域

和域定義設(shè)R是二元關(guān)系，由（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。

解：根據(jù)題意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設(shè)A={1，2，3，4}，R1是A上的二元關(guān)系，當a,b∈A，且a<b時，(a,b)∈R1,求R和它的前域，值域和域。第2頁，共22頁，2023年，2月20日，星期一32、逆與合成

R1={<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>}，求R1，R°S

，S°R

。

解：R1={<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頁，2023年，2月20日，星期一4合成運算的圖示方法

利用圖示（不是關(guān)系圖）方法求合成

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>}，求R1，R°S

，S°R

。

第4頁，共22頁，2023年，2月20日，星期一53、限制與像定義

F在A上的限制

F?A={<x,y>|xFy

xA}A在F下的像

F[A]=ran(F?A)例3設(shè)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?AF,F[A]ranF

第5頁，共22頁，2023年，2月20日，星期一6二、關(guān)系基本運算的性質(zhì)定理1設(shè)F是任意的關(guān)系,則(1)(F1)1=F(2)domF1=ranF,ranF1=domF定理2設(shè)F,G,H是任意的關(guān)系,則

(1)(F°G)°H=F°(G°H)(2)(F°G)1=G1°F1第6頁，共22頁，2023年，2月20日，星期一7定理設(shè)R,S,T均為A上二元關(guān)系，那么（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頁，2023年，2月20日，星期一8三、A上關(guān)系的冪運算設(shè)R為A上的關(guān)系,n為自然數(shù),則R的n次冪定義為：

(1)R0={<x,x>|x∈A}=IA

(2)Rn+1=Rn°R

注意：對于A上的任何關(guān)系R1和R2都有

R10=R20=IA

對于A上的任何關(guān)系R都有

R1=R第8頁，共22頁，2023年，2月20日，星期一9例：第9頁，共22頁，2023年，2月20日，星期一10定理設(shè)R是A上的關(guān)系,m,n∈N,則

(1)Rm°Rn=Rm+n

(2)(Rm)n=Rmn

四、冪運算的性質(zhì)第10頁，共22頁，2023年，2月20日，星期一11關(guān)系運算的矩陣表示關(guān)系矩陣（matrixofrelation）。設(shè)R

A×B，A=｛a1,a2,…,am｝,B=｛b1,b2,…,bn｝，那么R的關(guān)系矩陣

MR為一m×n矩陣，它的第i,j分量rij只取值0或1，而當且僅當aiRbj

當且僅當

第11頁，共22頁，2023年，2月20日，星期一12某關(guān)系R的關(guān)系圖為：則R的關(guān)系矩陣為：第12頁，共22頁，2023年，2月20日，星期一13思考：寫出集合A=｛1,2,3,4｝上的恒等關(guān)系、空關(guān)系、全域關(guān)系和小于關(guān)系的關(guān)系矩陣。答案：分別為：第13頁，共22頁，2023年，2月20日，星期一14在討論關(guān)系矩陣運算前,我們先定義布爾運算,它只涉及數(shù)字0和1。布爾加法（∨）：

0+0=0

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

1·1=1

0·1=1·0=0·0=0第14頁，共22頁，2023年，2月20日，星期一15R0,R1,R2,R3,…的關(guān)系圖如下圖所示五、冪的求法例3設(shè)A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>},求R的各次冪,分別用矩陣和關(guān)系圖表示.

解R與R2的關(guān)系矩陣分別為第15頁，共22頁，2023年，2月20日，星期一16冪的求法（續(xù)）對于集合表示的關(guān)系R，計算Rn就是n個R右復(fù)合.矩陣表示就是n個矩陣相乘,其中相加采用邏輯加.例3設(shè)A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>},求R的各次冪,分別用矩陣和關(guān)系圖表示.

解R與R2的關(guān)系矩陣分別為第16頁，共22頁，2023年，2月20日，星期一17同理，R0=IA,R3和R4的矩陣分別是：因此M4=M2,即R4=R2.因此可以得到

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

冪的求法（續(xù)）第17頁，共22頁，2023年，2月20日，星期一18六、冪運算的性質(zhì)定理設(shè)A為n元集,R是A上的關(guān)系,則存在自然數(shù)s和t,使得Rs=Rt.證R為A上的關(guān)系,由于|A|=n,A上的不同關(guān)系只有個.當列出R的各次冪

R0,R1,R2,…,,…,必存在自然數(shù)s和t使得Rs=Rt.第18頁，共22頁，2023年，2月20日，星期一19定理設(shè)R

AA,若存在自然數(shù)s,t(s<t),使得Rs=Rt,則下面等式成立：(1)Rs+q=Rt+q,qN;證明

Rs+q=RsRq=RtRq=Rt+q。(2)Rs+(t–s)q+r=Rs+r,其中q,rN;證明對q用歸納法證明。 當q=1,Rs+(t–s)q+r=Rs+(t–s)+r=Rt+r=Rs+r(1)

設(shè)q=k時,命題成立,

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

當q=k+1時,Rs+(t–s)(k+1)+r=Rs+(t–s)k+r+(t–s)

=Rs+(t–s)k+r

R(t–s)=Rs+r

Rt–s(歸納假設(shè))=Rs+r+t–s=Rt+r=Rs+r(1)所以,(2)成立第19頁，共22頁，2023年，2月20日，星期一20(2)Rs+(t–s)q+r=Rs+r,其中q,rN;(3)令S={R0,R1,…,Rt–1},則對于任意nN,均有RnS。(s<t)證明若n≤t–1,結(jié)論顯然成立。 設(shè)n≥t,則n>s,因而存在q,rN,使得

n–s=(t–s)q+r(0≤r≤t–s–1)即 n=s+(t–s)q+rRn=Rs+(t–s)q+r=Rs+r(2)

而s+r≤s+t–s–1=t–1,

所以Rn=Rs+r

S。▎第20頁，共22頁，2023年，2月20日，星期一21Rs+(t–s)q+r=Rs+r,例設(shè)RAA,化簡R2003的指數(shù)。(1)已知R3=R5；(2)已知R7=R15。解(1)s=3,t=5,n=2003, ==1000=1000

1+0,因此,q=1000,r=0,R2003=R3+21000+0=R