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

11.4關(guān)系的性質(zhì)關(guān)系的性質(zhì)及特點關(guān)系性質(zhì)的充要條件21.自反的二元關(guān)系(1).定義：R是Ａ上的二元關(guān)系，若x(x∈A→<x,x>R),則稱R在A上是自反的二元關(guān)系。例如Ａ＝｛a,b,c｝,R={(a,a),(b,b),(c,c),(a,b)}，則Ｒ是自反的。又如Ａ＝｛1,2,3｝,R是Ａ上的整除關(guān)系，顯然，Ｒ是自反的，因為（1,1）,（2,2）,（3,3）都屬于R。即如果對于Ａ中的每一個元素a,都有(a,a)∈R，則稱Ｒ為自反的二元關(guān)系。一、關(guān)系的性質(zhì)及特點3注意，在關(guān)系的自反性定義中，要求對于A中的每一個元素a都有(a,a)∈R。所以當(dāng)A={a,b,c}，而R={(a,a),(b,b)}時，R并不是自反的，因為(c,c)R。又如A={1,2,3}，R是A上的二元關(guān)系，當(dāng)a,b∈A，且a和b都是素數(shù)時，(a,b)∈R?？梢姡遥絳(2,2),(3,3),(2,3),(3,2)}，Ｒ也不是自反關(guān)系，因為(1,1)R。4(2).關(guān)系矩陣的特點：關(guān)系矩陣中主對角線上的元素全為1。(3).關(guān)系圖的特點：關(guān)系圖中每個頂點都有環(huán)。實例：A上的全域關(guān)系EA,恒等關(guān)系IA，小于等于關(guān)系LA,整除關(guān)系DA都是自反關(guān)系：例1

設(shè)，

（1）自反與反自反

自反自反非自反反自反62．反自反的二元關(guān)系(1).定義：R是Ａ上的二元關(guān)系，若x(x∈A→<x,x>R),則稱R在A上是反自反的二元關(guān)系.例如Ａ＝｛a,b,c｝,R={(a,b),(b,c),(b,a)}，則Ｒ是反自反的。又如Ａ＝｛1,2,3｝,R是Ａ上的小于關(guān)系，即當(dāng)a<b時，(a,b)∈R。顯然，Ｒ是反自反的。注意，非自反的二元關(guān)系不一定是反自反的二元關(guān)系，因為存在著這樣的二元關(guān)系，它既不是自反的又不是反自反的，如Ａ={a,b,c},R={(a,a),(a,b)}，那么Ｒ不是自反的(因為(b,b),(c,c)都不屬于Ｒ)，Ｒ也不是反自反的(因為(a,a)∈R)。即對于Ａ中的每一個元素a,都有(a,a)R，則稱Ｒ為反自反的二元關(guān)系。7實例：實數(shù)集上的小于關(guān)系，空關(guān)系，冪集上的真包含關(guān)系都是反自反關(guān)系。

(2).關(guān)系矩陣的特點：關(guān)系矩陣中主對角線上的元素全為0。(3).關(guān)系圖的特點：關(guān)系圖中每個頂點都沒有環(huán)。8例2

A={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>}R1既不是自反也不是反自反的R2為自反關(guān)系,R3為反自反關(guān)系。93.對稱的二元關(guān)系(1).定義:R是Ａ上的二元關(guān)系，若x，y(x,y∈A∧<x,y>∈R→<y,x>∈R),則稱R為A上對稱的二元關(guān)系.例如Ａ={a,b,c,d},R={(a,a),(a,b),(b,a),(b,d),(d,b)}則Ｒ是對稱的二元關(guān)系。又如Ａ={1,2,3,4,5},對于Ａ中元素a和b,如果a,b是模3同余關(guān)系，則(a,b)∈Ｒ,易見Ｒ是對稱關(guān)系。即如果(a,b)∈R,就一定有(b,a)∈R,則稱Ｒ為對稱的二元關(guān)系。10實例：A上的全域關(guān)系EA,恒等關(guān)系IA和空關(guān)系都是對稱關(guān)系。(2).關(guān)系矩陣的特點：關(guān)系矩陣為對稱矩陣。(3).關(guān)系圖的特點：關(guān)系圖中如果兩個頂點之間有邊一定是一對方向相反的邊。114．反對稱的二元關(guān)系即R是Ａ上的二元關(guān)系，每當(dāng)有(a,b)∈Ｒ和有(b,a)∈Ｒ時，必有a=b,則稱Ｒ是反對稱的二元關(guān)系。反對稱的定義也可寫為：Ｒ是Ａ上的二元關(guān)系，當(dāng)a≠b時，如果(a,b)∈Ｒ,則必有(b,a)R,稱Ｒ為反對稱的二元關(guān)系。例如Ａ={1,2,3},R是Ａ上的小于關(guān)系，即a<b，（a,b）∈Ｒ。易見Ｒ={(1,2),(1,3),(2,3)},所以Ｒ是反對稱的。又如Ａ是一些整數(shù)組成的集合，如果a整除b，則(a,b)∈Ｒ,R也是反對稱的。(1).定義：若

x，y(x,y∈A∧<x,y>∈R∧<y,x>∈R→x=y),則稱R為A上的反對稱關(guān)系.12注意，“對稱的”和“反對稱的”這兩個概念并非相互對立，相互排斥的。存在著既不是對稱的又不是反對稱的二元關(guān)系，也存在著既是對稱的又是反對稱的二元關(guān)系。又如A={a,b,c},R={(a,a)},可知Ｒ是對稱的，又是反對稱的。因為雖有(a,b)∈R,(b,a)∈R，但(c,d)∈R時(d,c)R,因此R不是對稱的，例如A={a,b,c,d}R={(a,b),(b,a),(c,d)}這里R既不是對稱的，也不是反對稱的。因為有(a,b)∈R和(b,a)∈R，因此R不是反對稱的。13實例：恒等關(guān)系IA，空關(guān)系都是A上的反對稱關(guān)系。

(2).關(guān)系矩陣的特點：關(guān)系矩陣中以主對角線對稱的元素不能同時為1。(3).關(guān)系圖的特點：關(guān)系圖中如果兩個頂點之間有邊一定是一條有向邊。14例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不對稱、也不反對稱.

（2）對稱與反對稱對稱，非反對稱非對稱，反對稱非對稱，非反對稱對稱，反對稱165.可傳遞的二元關(guān)系(1).定義：R是A上的二元關(guān)系，xyz(x,y,z∈A∧<x,y>∈R∧<y,z>∈R→<x,z>∈R),

則稱R是A上的傳遞關(guān)系.

例如整除關(guān)系是可傳遞的，因為每當(dāng)（a，b）∈R時，即a能整除b，b能整除c時，顯然a能整除c，所以必有（a，c）∈R。又如A={a，b，c，d，e}，其中a、b、c、d、e分別是表示5個人，且a、b、c同住一個房間；d和e同住另一個房間。如果同住一房間的人認(rèn)為是相關(guān)的，顯然這種同房間關(guān)系是可傳遞的。每當(dāng)有(a,b)∈R和(b,c)∈R時，必有(a,c)∈R，則稱為可傳遞的二元關(guān)系。17實例：

A上的全域關(guān)系EA,恒等關(guān)系IA和空關(guān)系小于等于關(guān)系,小于關(guān)系，整除關(guān)系，包含關(guān)系，真包含關(guān)系都是傳遞的二元關(guān)系。(2).關(guān)系矩陣的特點：(3).關(guān)系圖的特點：關(guān)系圖中如果兩個頂點xi到xj之間有邊,xj到xk之間有邊,則從xi到xk之間有邊。例3設(shè)A＝{1,2,3},R1,R2是A上的關(guān)系,其中

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

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

R1是A上的傳遞關(guān)系R2不是A上的傳遞關(guān)系19關(guān)系性質(zhì)判別匯總表達(dá)式自反性反自反性對稱性

反對稱性傳遞性關(guān)系矩陣主對角線元素全是1主對角線元素全是0矩陣是對稱矩陣若rij＝1,且i≠j,則rji＝0關(guān)系圖每個頂點都有環(huán)每個頂點都沒有環(huán)如果兩個頂點之間有邊,是一對方向相反的邊(無單邊)如果兩點之間有邊,是一條有向邊(無雙向邊)如果頂點xi連通到xk,則從xi到xk有邊

20例4判斷下圖中關(guān)系的性質(zhì),并說明理由.(2)反自反，不是自反的；反對稱，不是對稱的；(1)不自反也不反自反；對稱,不反對稱；不傳遞.(3)自反，不反自反；反對稱，不是對稱；不傳遞.21二、關(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

例5設(shè)，下面分別給出集合A上三個關(guān)系的關(guān)系圖，試判斷它們的性質(zhì)。（2）非自反，也不是反自反，非對稱，反對稱，可傳遞。（3）是自反的，對稱的，可傳遞的，不是反自反，也不是反對稱。解（1）是自反的，非對稱，不是反對稱，不可傳遞但思考1.設(shè)A={a,b,c},R是A上的二元關(guān)系且