離散數(shù)學 關(guān)系的性質(zhì)市公開課一等獎省名師優(yōu)質(zhì)課賽課一等獎?wù)n件

4.3關(guān)系性質(zhì)自反性反自反性對稱性反對稱性傳遞性1自反反自反對稱反對稱傳遞定義x∈A,有<x,x>R),x∈A,有<x,x>R,若

<x,y>∈R有<y,x>∈R),若<x,y>∈R且x

y,則<y,x>R若<x,y>∈R<y,z>∈R，則<x,z>∈R),表示式IARR∩IA=R=R1

R∩R1

IA

RRR關(guān)系矩陣主對角線元素全是1主對角線元素全是0矩陣是對稱矩陣若rij＝1,且i≠j,則rji＝0對M2中1所在位置,M中對應(yīng)位置都是1關(guān)系圖每個頂點都有環(huán)每個頂點都沒有環(huán)假如兩個頂點之間有邊,是一對方向相反邊(無單邊)假如兩點之間有邊,是一條有向邊(無雙向邊)假如頂點xi連通到xk,則從xi到xk有邊2自反性與反自反性例：自反關(guān)系：A上全域關(guān)系EA,恒等關(guān)系IA

小于等于關(guān)系LA,整除關(guān)系DA反自反關(guān)系：實數(shù)集上小于關(guān)系冪集上真包含關(guān)系

3實例例1A={1,2,3},R1,R2,R3是A上關(guān)系,其中

R1＝{<1,1>,<2,2>}

R2＝{<1,1>,<2,2>,<3,3>,<1,2>}

R3＝{<1,3>}R2自反,R3反自反,R1既不是自反也不是反自反4對稱性與反對稱性實例：對稱關(guān)系：A上全域關(guān)系EA,恒等關(guān)系IA和空關(guān)系反對稱關(guān)系：恒等關(guān)系IA，空關(guān)系是A上反對稱關(guān)系.

5實例例2設(shè)A＝{1,2,3},R1,R2,R3和R4都是A上關(guān)系,其中

R1＝{<1,1>,<2,2>}，R2＝{<1,1>,<1,2>,<2,1>}

R3＝{<1,2>,<1,3>}，R4＝{<1,2>,<2,1>,<1,3>}

R1對稱、反對稱.R2對稱，不反對稱.R3反對稱，不對稱.R4不對稱、也不反對稱.6傳遞性實例：A上全域關(guān)系EA,恒等關(guān)系IA和空關(guān)系小于等于關(guān)系,小于關(guān)系，整除關(guān)系，包含關(guān)系，真包含關(guān)系

7實例例3設(shè)A＝{1,2,3},R1,R2,R3是A上關(guān)系,其中

R1＝{<1,1>,<2,2>}

R2＝{<1,2>,<2,3>}

R3＝{<1,3>}

R1和R3是A上傳遞關(guān)系R2不是A上傳遞關(guān)系8關(guān)系性質(zhì)充要條件設(shè)R為A上關(guān)系,則

(1)R在A上自反當且僅當IAR

(2)R在A上反自反當且僅當R∩IA=

(3)R在A上對稱當且僅當R=R1

(4)R在A上反對稱當且僅當R∩R1IA

(5)R在A上傳遞當且僅當RRR

9實例例.判斷下列圖中關(guān)系性質(zhì),并說明理由.(2)反自反，不是自反；反對稱，不是對稱；是傳遞.(1)不自反也不反自反；對稱,不反對稱；不傳遞.(3)自反，不反自反；反對稱，不是對稱；不傳遞.10自反性證實證實模式證實R在A上自反任取x,xA

……………..….…….<x,x>R前提推理過程結(jié)論例4證實若IAR，則R在A上自反.證任取x,

xA<x,x>IA<x,x>R

所以R在A上是自反.11對稱性證實證實模式證實R在A上對稱任取<x,y><x,y>R

……………..….…….<y,x>R前提推理過程結(jié)論例5證實若R=R1,則R在A上對稱.證任取<x,y>

<x,y>R<y,x>R

1

<y,x>R

所以R在A上是對稱.

12反對稱性證實證實模式證實R在A上反對稱任取<x,y><x,y>R<y,x>R

………..……….

x=y前提推理過程結(jié)論例6證實若R∩R1IA,

則R在A上反對稱.證任取<x,y>

<x,y>R<y,x>R<x,y>R<x,y>R

1

<x,y>R∩R

1

<x,y>IA

x=y

所以R在A上是反對稱.13傳遞性證實證實模式證實R在A上傳遞任取<x,y>，<y,z><x,y>R<y,z>R

…..……….<x,z>R前提推理過程結(jié)論例7證實若RRR

,

則R在A上傳遞.證任取<x,y>，<y,z><x,y>R<y,z>R

<x,z>RR

<x,z>R

所以R在A上是傳遞.14運算與性質(zhì)關(guān)系自反性反自反性對稱性反對稱性傳遞性R11

√√√√√R1∩R2

√√√√√R1∪R2

√√√××R1R2

×√√√×R1°R2

√××××154.4關(guān)系閉包閉包定義閉包結(jié)構(gòu)方法集合表示矩陣表示圖表示閉包性質(zhì)16閉包定義定義設(shè)R是非空集合A上關(guān)系,R自反（對稱或傳遞）閉包是A上關(guān)系R,使得R滿足以下條件：

（1）R是自反（對稱或傳遞）

（2）RR

（3）對A上任何包含R自反（對稱或傳遞）關(guān)系R有RR.普通將R自反閉包記作r(R),對稱閉包記作s(R),傳遞閉包記作t(R).

17閉包結(jié)構(gòu)方法定理1設(shè)R為A上關(guān)系,則有

(1)r(R)=R∪R0

(2)s(R)=R∪R1

(3)t(R)=R∪R2∪R3∪…

說明：對于有窮集合A(|A|=n)上關(guān)系,(3)中并是有限.若R是自反，則r(R)=R;若R是對稱，則

s(R)=R;若R是傳遞，則t(R)=R.18（3）t(R)＝R∪R2∪R3∪…

先證R∪R2∪…t(R)成立，為此只需證實對任意正整數(shù)n有Rn

t(R)即可。用歸納法。n＝1時，有R1＝Rt(R)。假設(shè)Rnt(R)成立，那么對任意<x,y>有 <x,y>∈Rn+1＝RnR

t(<x,t>∈Rn∧<t,y>∈R)

t(<x,t>∈t(R)∧<t,y>∈t(R))

<x,y>∈t(R)（因為t(R)是傳遞）這就證實了Rn+1

t(R)。由歸納法命題得證。19再證t(R)R∪R2∪…成立，為此只須證實R∪R2∪…是傳遞。任取<x,y>,<y,z>，則 <y,z>∈R∪R2∪…∧<x,y>∈R∪R2∪…

t(<y,z>∈Rt)∧s(<x,y>∈Rs)

ts(<y,z>∈Rt∧<x,y>∈Rs)

ts(<x,z>∈Rt

Rs)

ts(<x,z>∈Rt+s)

<x,z>∈R∪R2∪…從而證實了R∪R2∪…是傳遞。20推論

設(shè)R為有窮集A上關(guān)系，則存在正整數(shù)r使得t(R)=R∪R2∪…∪Rr21閉包結(jié)構(gòu)方法（續(xù)）設(shè)關(guān)系R,r(R),s(R),t(R)關(guān)系矩陣分別為M,Mr,Ms和Mt,則

Mr=M+EMs=M+M’

Mt=M+M2+M3+…E是和M同階單位矩陣,M’是M轉(zhuǎn)置矩陣.注意在上述等式中矩陣元素相加時使用邏輯加.22閉包結(jié)構(gòu)方法（續(xù)）設(shè)關(guān)系R,r(R),r(R),s(R),t(R)關(guān)系圖分別記為G,Gr,Gs,Gt,則Gr,Gs,Gt頂點集與G頂點集相等.除了G邊以外,以下述方法添加新邊：

(1)考查G每個頂點,假如沒有環(huán)就加上一個環(huán)，最終得到Gr.(2)考查G每條邊,假如有一條xi到xj單向邊,i≠j,則在G

中加一條xj到xi反方向邊，最終得到Gs.(3)考查G每個頂點xi,找從xi出發(fā)每一條長度不超出n路徑，假如從xi到路徑中任何結(jié)點xj沒有邊，就加上這條邊.當檢驗完所有頂點后就得到圖Gt.23實例例1設(shè)A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>},R和r(R),s(R),t(R)關(guān)系圖以下列圖所表示.Rr(R)s(R)t(R)24R={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>},r(R)=R∪R0={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>}∪{<a,a>,<b,b>,<c,c>,<d,d>}

={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>,<a,a>,<b,b>,<c,c>,<d,d>}s(R)=R∪R1={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>}∪{<b,a>,<a,b>,<c,b>,<d,c>,<b,d>}}={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>,<c,b>,<d,c>,<b,d>}t(R)=R1∪R2∪R3∪R4={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>}∪{<a,a>,<a,c>,<b,b>,<b,d>,<c,b>,<d,a>,<d,c>}∪{<a,b>,<a,d>,<b,a>,<b,b>,<b,c>,<c,a>,<c,c>,<d,b