離散數(shù)學(xué)關(guān)系的性質(zhì)

1第1頁，共27頁，2023年，2月20日，星期一自反反自反對稱反對稱傳遞定義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),表達(dá)式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)系圖每個(gè)頂點(diǎn)都有環(huán)每個(gè)頂點(diǎn)都沒有環(huán)如果兩個(gè)頂點(diǎn)之間有邊,是一對方向相反的邊(無單邊)如果兩點(diǎn)之間有邊,是一條有向邊(無雙向邊)如果頂點(diǎn)xi連通到xk,則從xi到xk有邊

第2頁，共27頁，2023年，2月20日，星期一自反性與反自反性例：自反關(guān)系：A上的全域關(guān)系EA,恒等關(guān)系IA

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

第3頁，共27頁，2023年，2月20日，星期一實(shí)例例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頁，共27頁，2023年，2月20日，星期一對稱性與反對稱性實(shí)例：對稱關(guān)系：A上的全域關(guān)系EA,恒等關(guān)系IA和空關(guān)系反對稱關(guān)系：恒等關(guān)系IA，空關(guān)系是A上的反對稱關(guān)系.

第5頁，共27頁，2023年，2月20日，星期一實(shí)例例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頁，共27頁，2023年，2月20日，星期一傳遞性實(shí)例：

A上的全域關(guān)系EA,恒等關(guān)系IA和空關(guān)系小于等于關(guān)系,小于關(guān)系，整除關(guān)系，包含關(guān)系，真包含關(guān)系

第7頁，共27頁，2023年，2月20日，星期一實(shí)例例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頁，共27頁，2023年，2月20日，星期一關(guān)系性質(zhì)的充要條件設(shè)R為A上的關(guān)系,則

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

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

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

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

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

第9頁，共27頁，2023年，2月20日，星期一實(shí)例例.判斷下圖中關(guān)系的性質(zhì),并說明理由.(2)反自反，不是自反的；反對稱，不是對稱的；是傳遞的.(1)不自反也不反自反；對稱,不反對稱；不傳遞.(3)自反，不反自反；反對稱，不是對稱；不傳遞.第10頁，共27頁，2023年，2月20日，星期一自反性證明證明模式證明R在A上自反任取x,xA

……………..….…….<x,x>R

前提推理過程結(jié)論例4證明若IAR，則

R在A上自反.證任取x,

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

因此R在A上是自反的.第11頁，共27頁，2023年，2月20日，星期一對稱性證明證明模式證明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頁，共27頁，2023年，2月20日，星期一反對稱性證明證明模式證明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頁，共27頁，2023年，2月20日，星期一傳遞性證明證明模式證明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頁，共27頁，2023年，2月20日，星期一運(yùn)算與性質(zhì)的關(guān)系自反性反自反性對稱性反對稱性傳遞性R11

√√√√√R1∩R2

√√√√√R1∪R2

√√√××R1R2

×√√√×R1°R2

√××××第15頁，共27頁，2023年，2月20日，星期一4.4關(guān)系的閉包閉包定義閉包的構(gòu)造方法集合表示矩陣表示圖表示閉包的性質(zhì)第16頁，共27頁，2023年，2月20日，星期一閉包定義定義設(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頁，共27頁，2023年，2月20日，星期一閉包的構(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頁，共27頁，2023年，2月20日，星期一（3）t(R)＝R∪R2∪R3∪…

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

t(R)即可。用歸納法。n＝1時(shí)，有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)（因?yàn)閠(R)是傳遞的）這就證明了Rn+1

t(R)。由歸納法命題得證。第19頁，共27頁，2023年，2月20日，星期一再證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頁，共27頁，2023年，2月20日，星期一推論

設(shè)R為有窮集A上的關(guān)系，則存在正整數(shù)r使得t(R)=R∪R2∪…∪Rr第21頁，共27頁，2023年，2月20日，星期一閉包的構(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)置矩陣.注意在上述等式中矩陣的元素相加時(shí)使用邏輯加.第22頁，共27頁，2023年，2月20日，星期一閉包的構(gòu)造方法（續(xù)）設(shè)關(guān)系R,r(R),r(R),s(R),t(R)的關(guān)系圖分別記為G,Gr,Gs,Gt,則Gr,Gs,Gt的頂點(diǎn)集與G的頂點(diǎn)集相等.除了G的邊以外,以下述方法添加新邊：

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

中加一條xj到xi的反方向邊，最終得到Gs.(3)考察G的每個(gè)頂點(diǎn)xi,找從xi出發(fā)的每一條長度不超過n的路徑，如果從xi到路徑中任何結(jié)點(diǎn)xj沒有邊，就加上這條邊.當(dāng)檢查完所有的頂點(diǎn)后就得到圖Gt.第23頁，共27頁，2023年，2月20日，星期一實(shí)例例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)第24頁，共27頁，2023年，2月20日，星期一R={<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>}