離散數(shù)學(xué)-3-7復(fù)合關(guān)系和逆關(guān)系省名師優(yōu)質(zhì)課獲獎(jiǎng)?wù)n件市賽課一等獎(jiǎng)?wù)n件

第三章集合與關(guān)系3-7復(fù)合關(guān)系和逆關(guān)系講課人：李朔Email:chn.nj.ls@第1頁1一．關(guān)系復(fù)合二元關(guān)系是以序偶為元素集合，能夠進(jìn)行集合運(yùn)算，產(chǎn)生新集合，本課介紹關(guān)系一個(gè)新運(yùn)算，關(guān)系復(fù)合。定義3.7.1設(shè)R為X到Y(jié)關(guān)系，S為從Y到Z關(guān)系，則RоS稱為R和S復(fù)合關(guān)系，表示為RоS＝{<x,z>

x

X

z

Z

y(y

Y

<x,y>

R

<y,z>

S)

易見RоS是從X到Z關(guān)系。*從R和S，求RоS稱為關(guān)系合成運(yùn)算。合成運(yùn)算由兩個(gè)關(guān)系生成一個(gè)新關(guān)系*P114比如：R1是關(guān)系“…是…弟兄”，R2是關(guān)系“…是…父親”，那么R1оR2是關(guān)系“…是……叔伯”若R1是關(guān)系“…是……父親”，那么R1оR2是關(guān)系“…是…祖父”第2頁2一．關(guān)系復(fù)合例題1：R={<1,2>,<3,4>,<2,2>},S={<4,2>,<2,5>,<3,1>}則RоS={<1,5>,<3,2>,<2,5>}

SоR={<4,2>,<3,2>}(RоS)оR=?Rо(SоR)=?SоS={<4,5>}RоR={<1,2>,<2,2>}RоRоR={<1,2>,<2,2>}能夠證實(shí)，關(guān)系復(fù)合運(yùn)算滿足結(jié)合律，即：（RоS）оT＝Rо（SоT）故可記為＝RоSоTP115例題2*當(dāng)R與自己復(fù)合時(shí)，記RоR＝R2。普通定義Rn+1=RnоR第3頁3一．關(guān)系復(fù)合例：設(shè)X={0,1,2,3},則R={<0,1>,<1,2>,<2,3>,<0,0>,<2,1>}R2=RоR=?{<0,2>,<1,3>,<1,1>,<0,1>,<0,1>,<0,0>,<2,2>}R3=R2оR=?{<0,3>,<0,1>,<1,2>,<0,2>,<0,0>,<2,3>,<2,1>}*關(guān)系可用矩陣表示，故復(fù)合關(guān)系亦可用矩陣表示。（類似矩陣乘法，但采取邏輯加）P115第4頁4例例題3

A=

1,2,3,4,5

，A上二元關(guān)系R和S定義以下：

R=

1,2

,

2,2

,

3,4

S=

1,3

,

2,5

,

3,1

,

4,2

試求MR°S和MR°

MS，它們是否相等?解：按照R

和S定義，求出

R°S=

1,5

,

2,5

,

3,2

寫出R

、S和R°S關(guān)系矩陣以下：

MR=MS=MR°S=第5頁5例

MR°

MS=°=

所以MR°S=MR°

MS第6頁6二、關(guān)系逆

關(guān)系是序偶集合，因?yàn)樾蚺加行蛐?，關(guān)系還有一些特殊運(yùn)算。P117定義3.7.2

設(shè)R為X到y(tǒng)二元關(guān)系，如將R中每一序偶元素次序交換，所得集稱為R逆關(guān)系，記為Rc，即：Rc={<y,x>

<x,y>

R}比如：R={<1,a>,<2,b>,<3,c>}則Rc={<a,1>,<b,2>,<c,3>}易見(Rc)c=R

又如集合Z上，關(guān)系“<”逆關(guān)系是“>”第7頁7二、關(guān)系逆

P117定理3.7.1設(shè)R，S，T都是從A到B二元關(guān)系，則1）(S

T)C=SC

TC2）(S

T)C=SC

TC3）(A

B)C=B

A4）(

R)C=

RC(

R=A

B-R,

RC=BA-RC)5）(S-T)C=SC－TC

第8頁8二、關(guān)系逆

證：1)<x,y>

(S

T)C

<y,x>

S

T

<y,x>

S

<y,x>

T

<x,y>

SC

<x,y>

Tc

<x,y>

SC

TC4)<x,y>

(

R)C

<y,x>

R

<y,x>

R

<x,y>

RC

<x,y>

(

R)C5)因S－T＝S

T，故(S-T)C=(S

T)C=SC

(

T)C=SC

TC=SC-TC

第9頁9二、關(guān)系逆P117定理3.7.2

設(shè)T為從X到Y(jié)關(guān)系，S為從Y到Z關(guān)系，則（TоS）C＝SCоTC證：<z,x>

（TоS）C

<x,z>

TоS

y(y

Y

<x,y>

T

<y,z>

S)

y(y

Y

<y,x>

TC

<z,y>

SC)

<z,x>

SCоTC第10頁10二、關(guān)系逆定理3.7.3設(shè)R為X上二元關(guān)系，則：1）R是對(duì)稱，當(dāng)且僅當(dāng)R＝RC；2）R是反對(duì)稱，當(dāng)且僅當(dāng)R

RC

IX。證：1）∵R對(duì)稱，故<x,y>

R

<y,x>

R

<x,y>

RC,故R＝RC反之RC＝R，則<x,y>

R

<y,x>

RC

<y,x>

R，即R對(duì)稱。第11頁11二、關(guān)系逆定理3.7.3設(shè)R為X上二元關(guān)系，則：1）R是對(duì)稱，當(dāng)且僅當(dāng)R＝RC；2）R是反對(duì)稱，當(dāng)且僅當(dāng)R

RC

IX。證：2）設(shè)R反對(duì)稱

<x,y>

R

RC則<x,y>

R且<x,y>

RC

故有<y,x>

R

x=y即<x,y>

IX

R

RC

IX,反之設(shè)R

RC

IX

<x,y>

R且<y,x>

R則<x,y>

RC

<x,y>

R

RC即有<x,y>

IX

x=y

R是反對(duì)稱。第12頁12二、關(guān)系逆*關(guān)于RC圖形，是R圖形中將其弧線箭頭反置即得，而RC關(guān)系矩陣是R關(guān)系矩陣轉(zhuǎn)置。例：X={a,b,c}其上二元關(guān)系R關(guān)系陣為則RC關(guān)系陣為第13頁13例例設(shè)X=

1,2,3,4

，Y=

a,b,c

，X到Y(jié)二元關(guān)系

R=

1,a

,

2,b

,

4,c

，⑴試求RC，寫出MR和，驗(yàn)證=MRT⑵畫出R和RC關(guān)系圖，驗(yàn)證將R關(guān)系圖中弧線箭頭反置可得到RC關(guān)系圖。解：RC=

a,1

,

b,2

,

c,4

R和RC關(guān)系矩陣是：

MR=