東南大學(xué)離散數(shù)學(xué)課件

第七章:二元關(guān)系

第一節(jié)：有序?qū)εc笛卡兒積第二節(jié)：二元關(guān)系

第三節(jié)：關(guān)系的運算第四節(jié)：關(guān)系的性質(zhì)第五節(jié)：關(guān)系的閉包第六節(jié)：等價關(guān)系與劃分第七節(jié)：偏序關(guān)系第七章:二元關(guān)系

第一節(jié)：有序?qū)εc笛卡兒積第二節(jié)：二元關(guān)系

第三節(jié)：關(guān)系的運算

第四節(jié)：關(guān)系的性質(zhì)第五節(jié)：關(guān)系的閉包第六節(jié)：等價關(guān)系與劃分第七節(jié)：偏序關(guān)系7.3關(guān)系的運算二元關(guān)系的定義域和值域定義域：值域：例X={1,2,3,4,5,6},Y={a,b,c,d,e,f}R={<1,a>,<2,b>,<3,c>,<4,d>}domR={1,2,3,4}ranR={a,b,c,d}7.3關(guān)系的運算二元關(guān)系的逆

例：R={<a,a>，<a,d>，<b,d>，<c,a>，<c,b>，<d,c>}R-1={<a,a>，<d,a>，<d,b>，<a,c>，<b,c>，<c,d>}

1001101000010010MR=1100MR-1=MRT=000100101100

7.3關(guān)系的運算關(guān)系的右復(fù)合例A={1,2,3,4,5},B={3,4,5},C={1,2,3}R={<x,y>|x+y=6}={<1,5>,<2,4>,<3,3>}S={<y,z>

y-z=2}={<3,1>,<4,2>,<5,3>}R○S={<1,3>,<2,2>,<3,1>}7.3關(guān)系的運算例R={<a,b>,<c,d>,<b,b>}S={<d,b>,<b,e>,<c,a>}R○S={<a,e>,<c,b>,<b,e>}S○R={<d,b>,<c,b>}R○R={<a,b>,<b,b>}S○S={<d,e>}注意：R○S

S○R。

7.3關(guān)系的運算定理：設(shè)F是任意的關(guān)系，則(F-1)-1=FdomF-1=ranF,ranF-1=domF定理：設(shè)F，G，H是任意的關(guān)系(F○G)○H=F○(G○H)(F○G)-1=G-1○F-17.3關(guān)系的運算例R={<a,a>,<a,c>,<b,b>,<c,b>,<c,c>}S={<a,1>,<a,4>,<b,2>,<c,4>,<c,5>}R-1={<a,a>,<b,b>,<b,c>,<c,a>,<c,c>}S-1={<1,a>,<2,b>,<4,a>,<4,c>,<c,c>}S-1○R-1={<1,a>,<2,b>,<2,c>,<4,a>,<4,c>,<5,a>,<5,c>}S-1○R-1=(R○S)-17.3關(guān)系的運算定理:設(shè)R為A上關(guān)系，則

R○IA＝IA○R＝R定理:R○(S∪T)=R○S∪R○TR○(S∩T)

R○S∩R○T(S∪T)○X=S○X∪T○X(S∩T)○X

S○X∩T○X7.3關(guān)系的運算證明

R○(S∪T)=R○S∪R○T

<x,z>∈R○(S∪T)

y(<x,y>∈R∧<y,z>∈S∪T)

y(<x,y>∈R∧(<y,z>∈S∨<y,z>∈T))

y((<x,y>∈R∧<y,z>∈S)∨(<x,y>∈R∧<y,z>∈T))

y((<x,y>∈R∧<y,z>∈S))∨

y((<x,y>∈R∧<y,z>∈T))

<x,z>∈R○S∨<x,z>∈R○T

<x,z>∈R○S∪R○T7.3關(guān)系的運算R的n次冪記為RnR0

=

ARn+1=Rn○R定理:設(shè)R是集合A上的關(guān)系，m,n∈NRm·

Rn=Rm+n(Rm)n=Rmn7.3關(guān)系的運算例R={<1,2>,<2,1>,<2,3>,<3,4>,<4,5>}R0=

{<1,1>,<2,2>,<3,3>,<4,4>,<5,5>}R1=RR2={<1,1>,<2,2>,<1,3>,<2,4>,<3,5>}R3=R2·R={<1,2>,<2,1>,<1,4>,<2,3>,<2,5>}R4=R3·R1={<1,1>,<2,2>,<1,5>,<2,4>,<1,3>}R5=R4·R1={<1,2>,<1,4>,<2,1>,<2,3>,<2,5>}7.3關(guān)系的運算從關(guān)系圖來看關(guān)系的n次冪R：

12345R2就是所有在R中通過二條弧連接的點則在R2這兩點間直接有條弧。

12345R3,R4…7.3關(guān)系的運算定理：R是A上的二元關(guān)系，若存在自然數(shù)i和j，且i<j，使Ri=Rj對所有的k≥0，則Ri+k=Rj+k對所有的k,m≥0

，則有Ri+md+k=Ri+k設(shè)S={R0,R1,R2,…,Rj-1}，則R的每一次冪是S的元素，即對n∈N,Rn∈S

第七章:二元關(guān)系

第一節(jié)：有序?qū)εc笛卡兒積第二節(jié)：二元關(guān)系

第三節(jié)：關(guān)系的運算第四節(jié)：關(guān)系的性質(zhì)第五節(jié)：關(guān)系的閉包第六節(jié)：等價關(guān)系與劃分第七節(jié)：偏序關(guān)系7.4關(guān)系的性質(zhì)自反性

a∈A，有<a,a>∈R，則R為A上的自反關(guān)系反自反性

a∈A，有<a,a>

R，R為A上的反自反關(guān)系例A={a,b,c}R1={<a,a>,<b,b>,<c,c>,<a,b>,<c,a>}R2={<a,b>,<b,c>,<c,a>}R3={<a,a>,<b,c>}7.4關(guān)系的性質(zhì)例：R是I+上的整除關(guān)系，則R具有自反性。證明：

x∈I+，x能整除x，∴<x,x>∈R，∴R具有自反性。例：R是I上的同余關(guān)系，則R具有自反性，證明：

x∈I，(x-x)/k=0∈I,∴x與x同余∴<x,x>∈R∴R具有自反性其它≤，≥關(guān)系，均是自反關(guān)系。7.4關(guān)系的性質(zhì)例：N上的互質(zhì)關(guān)系是反自反關(guān)系。證明：

x∈N，x與x是不互質(zhì)的，∴<x,x>

R，∴R具有反自反關(guān)系。實數(shù)上的＜,＞關(guān)系,均是反自反關(guān)系。7.4關(guān)系的性質(zhì)關(guān)系矩陣的特點自反關(guān)系的關(guān)系矩陣的對角元素均為1，反自反關(guān)系的關(guān)系矩陣的對角元素均為0。關(guān)系圖的特點?定理：R是A上的關(guān)系，則：R是自反關(guān)系的充要條件是IA

RR是反自反關(guān)系的充要條件是R∩IA=Ф。7.4關(guān)系的性質(zhì)對稱性

a,b∈A,如果<a,b>∈R,則必有<b,a>∈R,R為A上的對稱關(guān)系。

例R1＝{<1,1>,<2,3>,<3,2>}R1是對稱的R2＝{<1,1>,<3,3>}R2是對稱的R3＝{<2,2>,<2,3>,<3,2>,<3,1>}R3不是對稱的

7.4關(guān)系的性質(zhì)例：R是N上的互質(zhì)關(guān)系,R具有對稱性。關(guān)系矩陣特點對稱關(guān)系的關(guān)系矩陣是對稱矩陣關(guān)系圖特點？定理：R在A上對稱當(dāng)且僅當(dāng)R=R-17.4關(guān)系的性質(zhì)反對稱性

a,b∈R,如果<a,b>∈R且<b,a>∈R,則必有a＝b,

R是A上的反對稱關(guān)系

a,b∈A,如a≠b,<a,b>∈R,則必有<b,a>

R。例:

A＝{a,b,c}R＝{<a,a>,<b,b>}S＝{<a,b>,<a,c>}T＝{<a,c>,<b,a>,<a,b>}R,S是反對稱的,T不是反對稱的7.4關(guān)系的性質(zhì)例:實數(shù)集合上≤關(guān)系是反對稱關(guān)系

x,y∈實數(shù)集,如x≠y,且x≤y,則y≤x不成立例≥,<,>關(guān)系,均是反對稱關(guān)系。反對稱關(guān)系矩陣和關(guān)系圖特點？定理：R在A上反對稱當(dāng)且僅當(dāng)R∩R-1

IA7.4關(guān)系的性質(zhì)傳遞性

a,b,c∈A,如果<a,b>∈R,<b,c>∈R,必有<a,c>∈R,稱R為A上的傳遞關(guān)系例R1＝{<x,y>,<z,x>,<z,y>}是傳遞關(guān)系R2＝{<a,b>,<c,d>}是傳遞關(guān)系R3＝{<a,b>,<b,a>}不是傳遞關(guān)系7.4關(guān)系的性質(zhì)例:整除關(guān)系DI＋是I＋上的傳遞關(guān)系。

x,y,z∈I＋,如<x,y>∈DI＋,<y,z>∈DI＋,即x能整除y,且y能整除z,則必有x能整除z,<x,z>∈DI＋例:P(A)上的包含關(guān)系

具有傳遞性。若u

v,v

w,則必有u

w例:實數(shù)集上的≤關(guān)系具有傳遞性。若x≤y,y≤z必有x≤z7.4關(guān)系的性質(zhì)傳遞關(guān)系關(guān)系圖特點如果結(jié)點a能通過有向弧組成的有向路徑通向結(jié)點x,則a必須有有向弧直接指向x,否則R就不是傳遞的例R={<a,b>,<b,c>,<c,d>,<a,c>}定理：R在A上傳遞當(dāng)且僅當(dāng)R·R

Rdcba7.4關(guān)系的性質(zhì)自

反：反自反：

對

稱：反對稱：傳

遞：

7.4關(guān)系的性質(zhì)例X={1,2,3}R1={<1,2>,<2,3>,<1,3>}R2={<1,1>,<1,2>,<2,3>}反對稱反自反反對稱可傳遞7.4關(guān)系的性質(zhì)R3={<1,1>,<2,2>,<3,3>}R4=Ex

自反，對稱，可傳遞的

自反，對稱，反對稱，可傳遞的7.4關(guān)系的性質(zhì)X={1,2,3},R5=

反自反的，對稱的，反對稱的，可傳遞的若X=

，X上的空關(guān)系自反的，反自反的，對稱的，反對稱的，可傳遞的第七章:二元關(guān)系

第一節(jié)：有序?qū)εc笛卡兒積第二節(jié)：二元關(guān)系

第三節(jié)：關(guān)系的運算第四節(jié)：關(guān)系的性質(zhì)

第五節(jié)：關(guān)系的閉包第六節(jié)：等價關(guān)系與劃分第七節(jié)：偏序關(guān)系7.5關(guān)系的閉包定義R是非空集合A上的關(guān)系，若A上另外有一個關(guān)系R’滿足如下三條，R’是自反的（對稱的，傳遞的）R

R’A上任何一個滿足以上兩條的關(guān)系R”，均有R’

R”，稱關(guān)系R’為R的自反（對稱,傳遞）閉包,記作r(R),（s(R),t(R)）7.5關(guān)系的閉包解釋R’是在R的基礎(chǔ)上添加有序?qū)μ砑釉氐哪康氖鞘筊’具有自反性(對稱性,傳遞性)添加后使之具有自反性(對稱性,傳遞性)的所有關(guān)系中R’是最小的一個7.5關(guān)系的閉包例A={a,b,c}R={<a,a>,<a,b>,<b,c>}自反閉包r(R){<a,a>,<a,b>,<b,c>,<b,b>,<c,c>}對稱閉包s(R){<a,a>,<a,b>,<b,a>,<b,c>,<c,b>}傳遞閉包t(R){<a,a>,<a,b>,<b,c>,<a,c>}r(R)abccbaacbcbabac7.5關(guān)系的閉包例R={<a,b>,<b,a>,<b,c>,<c,d>,<d,e>}，求R的傳遞閉包

abcde7.5關(guān)系的閉包定理R是非空集合A上的關(guān)系,則r(R)=R

A證明:R

R

AR

A是自反的.設(shè)R”滿足R

R”,R”是自反的,

<a,b>

R

A則<a,b>

R或<a,b>

A如<a,b>

R,由R

R”知<a,b>

R”如<a,b>

A,由R”的自反性知<a,b>

R”。均有<a,b>

R”

R

A

R”

7.5關(guān)系的閉包定理:設(shè)R是非空集A的關(guān)系,則s(R)=R

R-1

證明:R

R

R-1滿足定義第2條

<a,b>

R

R-1

<a,b>

R

<a,b>

R-1

<b,a>

R-1

<b,a>

R

<b,a>

R

R-1

R

R-1是對稱的7.5關(guān)系的閉包如R

R”,且R”是對稱的

<a,b>

R

R-1<a,b>

R或<a,b>

R-1如<a,b>

R,由R

R”,則<a,b>

R”如<a,b>

R-1,則<b,a>

R,則<b,a>

R”因R”對稱

<a,b>

R”,

R

R-1

R”滿足定義第3條7.5關(guān)系的閉包例:設(shè)A={1,2,3},A上的關(guān)系R如圖,求r(R),s(R)解:R={<1,2>,<2,3>,<3,2>,<3,3>}r(R)=R

A

={<1,2>,<2,3>,<3,2>,<3,3>,<2,2>,<1,1>}s(R)=R

R-1

={<1,2>,<2,3>,<3,2>,<3,3>,<2,1>}

1237.5關(guān)系的閉包定理:設(shè)R是非空集合A上的關(guān)系,則t(R)=Ri=R

R2

…

推論:設(shè)A是非空有限集，|A|=n，R是集合A上的二元關(guān)系，

則t(R）=Ri=R

R2

…Rn7.5關(guān)系的閉包例A={a,b,c,d}R={<a,b>,<a,c>,<b,c>,<b,d>}S={<a,b>,<b,c>,<c,d>},求t(R),