14.3關(guān)系的性質(zhì)關(guān)系的性質(zhì)及特點(diǎn)關(guān)系性質(zhì)的充要條件關(guān)系性質(zhì)的證明運(yùn)算和性質(zhì)的關(guān)系離散數(shù)學(xué)-關(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)系，顯然，Ｒ是自反的，因?yàn)椋?,1）,（2,2）,（3,3）都屬于R。即如果對(duì)于Ａ中的每一個(gè)元素a,都有(a,a)∈R，則稱Ｒ為自反的二元關(guān)系。一、關(guān)系的性質(zhì)及特點(diǎn)離散數(shù)學(xué)-關(guān)系的性質(zhì)3注意，在關(guān)系的自反性定義中，要求對(duì)于A中的每一個(gè)元素a都有(a,a)∈R。所以當(dāng)A={a,b,c}，而R={(a,a),(b,b)}時(shí)，R并不是自反的，因?yàn)?c,c)

R。又如A={1,2,3}，R是A上的二元關(guān)系，當(dāng)a,b∈A，且a和b都是素?cái)?shù)時(shí)，(a,b)∈R?？梢姡遥絳(2,2),(3,3),(2,3),(3,2)}，Ｒ也不是自反關(guān)系，因?yàn)?1,1)

R。離散數(shù)學(xué)-關(guān)系的性質(zhì)4(2).關(guān)系矩陣的特點(diǎn)：關(guān)系矩陣中主對(duì)角線上的元素全為1。(3).關(guān)系圖的特點(diǎn)：關(guān)系圖中每個(gè)頂點(diǎn)都有環(huán)。實(shí)例：A上的全域關(guān)系EA,恒等關(guān)系IA，小于等于關(guān)系LA,整除關(guān)系DA都是自反關(guān)系：離散數(shù)學(xué)-關(guān)系的性質(zhì)52．反自反的二元關(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時(shí)，(a,b)∈R。顯然，Ｒ是反自反的。注意，非自反的二元關(guān)系不一定是反自反的二元關(guān)系，因?yàn)榇嬖谥@樣的二元關(guān)系，它既不是自反的又不是反自反的，如Ａ={a,b,c},R={(a,a),(a,b)}，那么Ｒ不是自反的(因?yàn)?b,b),(c,c)都不屬于Ｒ)，Ｒ也不是反自反的(因?yàn)?a,a)∈R)。即對(duì)于Ａ中的每一個(gè)元素a,都有(a,a)

R，則稱Ｒ為反自反的二元關(guān)系。離散數(shù)學(xué)-關(guān)系的性質(zhì)6實(shí)例：實(shí)數(shù)集上的小于關(guān)系，空關(guān)系

，冪集上的真包含關(guān)系都是反自反關(guān)系。

(2).關(guān)系矩陣的特點(diǎn)：關(guān)系矩陣中主對(duì)角線上的元素全為0。(3).關(guān)系圖的特點(diǎn)：關(guān)系圖中每個(gè)頂點(diǎn)都沒有環(huán)。離散數(shù)學(xué)-關(guān)系的性質(zhì)7例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>}R1既不是自反也不是反自反的R2為自反關(guān)系,R3為反自反關(guān)系。離散數(shù)學(xué)-關(guān)系的性質(zhì)83.對(duì)稱的二元關(guān)系(1).定義:R是Ａ上的二元關(guān)系，若

x，y(x,y∈A∧<x,y>∈R→<y,x>∈R),則稱R為A上對(duì)稱的二元關(guān)系.例如Ａ={a,b,c,d},R={(a,a),(a,b),(b,a),(b,d),(d,b)}則Ｒ是對(duì)稱的二元關(guān)系。又如Ａ={1,2,3,4,5},對(duì)于Ａ中元素a和b,如果a,b是模3同余關(guān)系，則(a,b)∈Ｒ,易見Ｒ是對(duì)稱關(guān)系。即如果(a,b)∈R,就一定有(b,a)∈R,則稱Ｒ為對(duì)稱的二元關(guān)系。離散數(shù)學(xué)-關(guān)系的性質(zhì)9實(shí)例：A上的全域關(guān)系EA,恒等關(guān)系IA和空關(guān)系

都是對(duì)稱關(guān)系。(2).關(guān)系矩陣的特點(diǎn)：關(guān)系矩陣為對(duì)稱矩陣。(3).關(guān)系圖的特點(diǎn)：關(guān)系圖中如果兩個(gè)頂點(diǎn)之間有邊一定是一對(duì)方向相反的邊。離散數(shù)學(xué)-關(guān)系的性質(zhì)104．反對(duì)稱的二元關(guān)系即R是Ａ上的二元關(guān)系，每當(dāng)有(a,b)∈Ｒ和有(b,a)∈Ｒ時(shí)，必有a=b,則稱Ｒ是反對(duì)稱的二元關(guān)系。反對(duì)稱的定義也可寫為：Ｒ是Ａ上的二元關(guān)系，當(dāng)a≠b時(shí)，如果(a,b)∈Ｒ,則必有(b,a)

R,稱Ｒ為反對(duì)稱的二元關(guān)系。例如Ａ={1,2,3},R是Ａ上的小于關(guān)系，即a<b，（a,b）∈Ｒ。易見Ｒ={(1,2),(1,3),(2,3)},所以Ｒ是反對(duì)稱的。又如Ａ是一些整數(shù)組成的集合，如果a整除b，則(a,b)∈Ｒ,R也是反對(duì)稱的。(1).定義：若

x，y(x,y∈A∧<x,y>∈R∧<y,x>∈R→x=y),則稱R為A上的反對(duì)稱關(guān)系.離散數(shù)學(xué)-關(guān)系的性質(zhì)11注意，“對(duì)稱的”和“反對(duì)稱的”這兩個(gè)概念并非相互對(duì)立，相互排斥的。存在著既不是對(duì)稱的又不是反對(duì)稱的二元關(guān)系，也存在著既是對(duì)稱的又是反對(duì)稱的二元關(guān)系。又如A={a,b,c},R={(a,a)},可知Ｒ是對(duì)稱的，又是反對(duì)稱的。因?yàn)殡m有(a,b)∈R,(b,a)∈R，但(c,d)∈R時(shí)(d,c)R,因此R不是對(duì)稱的，例如A={a,b,c,d}R={(a,b),(b,a),(c,d)}這里R既不是對(duì)稱的，也不是反對(duì)稱的。因?yàn)橛?a,b)∈R和(b,a)∈R，因此R不是反對(duì)稱的。離散數(shù)學(xué)-關(guān)系的性質(zhì)12實(shí)例：恒等關(guān)系IA，空關(guān)系

都是A上的反對(duì)稱關(guān)系。

(2).關(guān)系矩陣的特點(diǎn)：關(guān)系矩陣中以主對(duì)角線對(duì)稱的元素不能同時(shí)為1。(3).關(guān)系圖的特點(diǎn)：關(guān)系圖中如果兩個(gè)頂點(diǎn)之間有邊一定是一條有向邊。離散數(shù)學(xué)-關(guān)系的性質(zhì)13例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對(duì)稱、反對(duì)稱.R2對(duì)稱，不反對(duì)稱.R3反對(duì)稱，不對(duì)稱.R4不對(duì)稱、也不反對(duì)稱.離散數(shù)學(xué)-關(guān)系的性質(zhì)145.可傳遞的二元關(guān)系(1).定義：R是A上的二元關(guān)系，

x

y

z(x,y,z∈A∧<x,y>∈R∧<y,z>∈R→<x,z>∈R),

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

例如整除關(guān)系是可傳遞的，因?yàn)槊慨?dāng)（a，b）∈R時(shí)，即a能整除b，b能整除c時(shí)，顯然a能整除c，所以必有（a，c）∈R。又如A={a，b，c，d，e}，其中a、b、c、d、e分別是表示5個(gè)人，且a、b、c同住一個(gè)房間；d和e同住另一個(gè)房間。如果同住一房間的人認(rèn)為是相關(guān)的，顯然這種同房間關(guān)系是可傳遞的。每當(dāng)有(a,b)∈R和(b,c)∈R時(shí)，必有(a,c)∈R，則稱為可傳遞的二元關(guān)系。離散數(shù)學(xué)-關(guān)系的性質(zhì)15實(shí)例：

A上的全域關(guān)系EA,恒等關(guān)系IA和空關(guān)系

小于等于關(guān)系,小于關(guān)系，整除關(guān)系，包含關(guān)系，真包含關(guān)系都是傳遞的二元關(guān)系。(2).關(guān)系矩陣的特點(diǎn)：(3).關(guān)系圖的特點(diǎn)：關(guān)系圖中如果兩個(gè)頂點(diǎn)xi到xj之間有邊,xj到xk之間有邊,則從xi到xk之間有邊。離散數(shù)學(xué)-關(guān)系的性質(zhì)16關(guān)系性質(zhì)判別匯總表達(dá)式自反性反自反性對(duì)稱性

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

離散數(shù)學(xué)-關(guān)系的性質(zhì)例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)系離散數(shù)學(xué)-關(guān)系的性質(zhì)18例4判斷下圖中關(guān)系的性質(zhì),并說明理由.(2)反自反，不是自反的；反對(duì)稱，不是對(duì)稱的；(1)不自反也不反自反；對(duì)稱,不反對(duì)稱；不傳遞.(3)自反，不反自反；反對(duì)稱，不是對(duì)稱；不傳遞.離散數(shù)學(xué)-關(guān)系的性質(zhì)19二、關(guān)系性質(zhì)的充要條件設(shè)R為A上的關(guān)系,則

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

R

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

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

1

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

1

IA

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

R

R

離散數(shù)學(xué)-關(guān)系的性質(zhì)201.自反性證明證明模式證明R在A上自反任取x,x

A

……………..….…….

<x,x>

R前提推理過程結(jié)論例5證明若IA

R，則

R在A上自反.三、關(guān)系類型的證明證任取x,

x

A

<x,x>

IA

<x,x>

R

因此R在A上是自反的.離散數(shù)學(xué)-關(guān)系的性質(zhì)212.對(duì)稱性證明證明模式證明R在A上對(duì)稱任取<x,y><x,y>

R

……………..….…….

<y,x>

R前提推理過程結(jié)論例6證明若R=R

1,則R在A上對(duì)稱.證任取<x,y>

<x,y>

R

<y,x>

R

1

<y,x>

R

因此R在A上是對(duì)稱的.

離散數(shù)學(xué)-關(guān)系的性質(zhì)223.反對(duì)稱性證明證明模式證明R在A上反對(duì)稱任取<x,y><x,y>

R

<y,x>

R

………..……….

x=y前提推理過程結(jié)論例7證明若R∩R

1

IA,

則R在A上反對(duì)稱.證任取<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上是反對(duì)稱的.離散數(shù)學(xué)-關(guān)系的性質(zhì)234.傳遞性證明證明模式證明R在A上傳遞任取<x,y>，<y,z><x,y>

R

<y,z>

R

…..……….

<x,z>

R前提推理過程結(jié)論例8證明若R

R

R

,

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

R

<y,z>

R

<x,z>

R

R

<x,z>

R

因此R在A上是傳遞的.離散數(shù)學(xué)-關(guān)系的性質(zhì)思考1.設(shè)A={a,b,c},R是A上的二元關(guān)系且R={(a,a),(b,b),(a,c),(c,a)},問R是自反的嗎？是反自反的嗎？是對(duì)稱的嗎？是反對(duì)稱的嗎？是可傳遞的嗎？解：由于cR,但(c,c)R,所以R不是自反關(guān)系；又由于(c,a)R,(a,c)R,但(c,c)R,所以R不是傳遞關(guān)系。顯然R是對(duì)稱關(guān)系，R不是反對(duì)稱關(guān)系；由于(a,a)R,(b,b)R,所以R也不是反自反關(guān)系；離散數(shù)學(xué)-關(guān)系的性質(zhì)思考2.設(shè)A={a,b}，寫出（1）A上所有的自反關(guān)系；（2）A上所有的反自反關(guān)系；（3）A上所有的對(duì)稱關(guān)系；（4）A上所有的反對(duì)稱關(guān)系。解（1）由于A×A={(a,a),(b,b),(a,b),(b,a)}，而A上的自反關(guān)系必須含有(a,a),(b,b)。所以A上的自反關(guān)系共有4種。它們是{(a,a),(b,b)}，{(a,a),(b,b),(a,b)}，{(a,a),(b,b),(b,a)}，{(a,a),(b,b),(a,b),(b,a)}。離散數(shù)學(xué)-關(guān)系的性質(zhì)(2)由于A上的反自反關(guān)系必須不含有(a,a),(b,b)。所以A上的反自反關(guān)系也有4種。它們是?(空關(guān)系)，

{(a,b)}，{(b,a)}，{(a,b),(b,a)}。(3)由于A上的對(duì)稱關(guān)系R,當(dāng)(a,b)∈R時(shí),必有(b,a)∈R,所以只需考慮在(a,a),(b,b),(a,b)中選取0個(gè)，1個(gè)，2個(gè)，3個(gè)有序?qū)?gòu)成的集合。它們是空關(guān)系

,{(a,a)},{(b,b)},{(a,b),(b,a)},{(a,a),(b,b)},{(a,a),(a,b),(b,a)}，{(b,b),(a,b),(b,a)},{(a,a),(b,b),(a,b),(b,a)}。所以A上的對(duì)稱關(guān)系有8種。離散數(shù)學(xué)-關(guān)系的性質(zhì)27所以在A×A的子集中刪去同時(shí)含有(a,b)和(b,a)的子集后，其它子集都是反對(duì)稱關(guān)系，共有12種。即?(空關(guān)系)，

{(a,a)},{(a,b)},{(b,a)},{(b,b)},

{(a,a),(a,b)},{(a,a),(b,a)},{(a,a),(b,b)},{(a,b),(b,b)},{(b,a),(b,b)},{(a,a),(a,b),(b,b)}，{(a,a),(b,a),(b,b)}。（4）由于A上的反對(duì)稱關(guān)系，當(dāng)(a,b)∈R必有(b,a)

R。離散數(shù)學(xué)-關(guān)系的性質(zhì)28思考3.設(shè)A={1，2，3}，問在A上有多少種不同的自反關(guān)系？解：當(dāng)R是A上的自反關(guān)系時(shí)，R必須含有表格中對(duì)角線上的

3個(gè)小方格所表示的有序?qū)Γ瑢?duì)于表格中余下的6個(gè)小方格，可以依次選取1個(gè)，2個(gè)，……，6個(gè)小方格，也可以不取，它們所表示的二元關(guān)系都是A上的自反關(guān)系，因此，A上共有64個(gè)自反關(guān)系。離散數(shù)學(xué)-關(guān)系的性質(zhì)5.傳遞性的判定方法判定定理1：設(shè)集合A={a1,a2,…,an}，R是A上的二元關(guān)系，R的關(guān)系矩陣為MR，令MR2

=MR

MR，則R是A上的傳遞關(guān)系的充要條件是對(duì)MR2中1所在位置,MR中相應(yīng)位置都是1。例9：設(shè)A={a，b，c，d，e}，R={<a,b>,<a,c>,<b,c>,<d,c>,<e,d>,<e,c>},試判斷R的傳遞性。判定定理2：設(shè)集合A={a1,a2,…,an}，R是A上的二元關(guān)系，R的關(guān)系矩陣為MR，R是A上的傳遞關(guān)系的充要條件是若MR中的零元素aij=0所對(duì)應(yīng)