離散數(shù)學(xué)（第二版） 課件 鄒麗娜 5 二元關(guān)系3

離散數(shù)學(xué)第5章二元關(guān)系二元關(guān)系的性質(zhì)自反性反自反性對稱性反對稱性傳遞性二元關(guān)系的性質(zhì)自反：在集合A上的關(guān)系R，對任意x

A，有<x，x>

R。

abca1??b?1?c??1二元關(guān)系的性質(zhì)R1在A’上是反自反的R2在A’上不是自反的，也不是反自反的反自反:在集合A上的關(guān)系R，對任意x

A，有<x，x>

R。

abca0??b?0?c??0自反性和反自反性設(shè)A={1，2，3}，定義A上的關(guān)系R，S和T如下：(1)R={<1，1>，<1，2>，<2，2>，<3，3>}；(2)S={<1，2>，<2，3>，<3，1>}；(3)T={<1，1>，<1，2>，<1，3>，<3，1>，<3，3>}。試判斷它們是否有自反性和反自反性。(1)因?yàn)锳中

x，都有<x，x>

R，所以R是自反的；(2)因?yàn)锳中

x，都有<x，x>

S，所以S是反自反的；(3)因?yàn)榇嬖?

A，使<2，2>

T，所以T不是自反的；又因?yàn)榇嬖?

A，使<1，1>

T，所以T不是反自反的，

即T既不是自反的，也不是反自反的.自反性和反自反性(2)設(shè)R，S和T的關(guān)系矩陣分別為MR，MS和MT，則：(3)R，S和T的關(guān)系圖分別是下圖的(a)，(b)和(c)。133123212

(a)(b)(c)(1)A上的全域關(guān)系EA、恒等關(guān)系IA都是A上的自反關(guān)系.(2)小于等于關(guān)系LA={<x,y>

x,y

A∧x≤y},A

R.

整除關(guān)系DA={<x,y>

x,y

A∧x整除y},A

Z*.

都是自反關(guān)系.(3)

小于關(guān)系SA={<x,y>

x,y

A∧x

y},A

R.是反自反關(guān)系.(4)設(shè)A={1,2,3},R1={<1,1>,<2,2>,<3,3>,<1,2>}R2={<1,3>}R3={<1,1>,<2,2>}是A上的自反關(guān)系;

是A上的反自反關(guān)系;既不是自反的,也不是反自反的.自反性和反自反性

123123自反性與反自反性結(jié)論：(1)自反性和反自反性不是相反概念，即存在既不是自反的也不是反自反的關(guān)系。(2)關(guān)系R是自反的?

R一定不是反自反的。(3)關(guān)系R是自反的

關(guān)系圖中每個(gè)結(jié)點(diǎn)都有自環(huán)。關(guān)系R是反自反的

關(guān)系圖中每個(gè)結(jié)點(diǎn)都無自環(huán)。(4)關(guān)系R是自反的

關(guān)系矩陣的主對角線上全為1。關(guān)系R是反自反的

關(guān)系矩陣的主對角線上全為0。對稱性與反對稱性對稱的不是對稱的即在集合A上的關(guān)系R，如果有<x，y>

R，必有<y，x>

R，則稱R是對稱的。對稱性與反對稱性反對稱的反對稱的即在集合A上的關(guān)系R，如果<x，y>

R

，必有<y，x>

R，則稱R是反對稱的。

abca11b1c1二元關(guān)系的性質(zhì)（對稱、反對稱的矩陣解釋）

abca0b1cabca01b1c1不是對稱，不是反對稱

abca0b1c1abca1bc1既是對稱，也是反對稱對稱性與反對稱性練習(xí)：設(shè)A={1，2，3，4}，定義A上的關(guān)系R，S，T和V,試判定對稱性和反對稱性。(1)R={<1，1>，<1，3>，<3，1>，<4，4>}；(2)S={<1，1>，<1，3>，<1，4>，<2，4>}；(3)T={<1，1>，<1，2>，<1，3>，<3，1>，<1，4>}；(4)V={<1，1>，<2，2>，<3，3>，<4，4>}。(1)關(guān)系R是對稱的；(2)關(guān)系S是反對稱的；(3)在關(guān)系T中，有<1，2>，但沒有<2，1>,即T不是對稱的；另外有<1，3>，且有<3，1>，但是1≠3，即T不是反對稱的。

因此T既不是對稱的，也不是反對稱的；(4)在關(guān)系V中，對

x，

y

A，x≠y時(shí)都有<x，y>

R，

V既是對稱的，也是反對稱的。對稱性與反對稱性設(shè)R，S，T和V的關(guān)系矩陣分別為MR，MS，MT和MV，則R，S，

T和Ｖ的關(guān)系圖分別是圖(a)，(b)，(c)和(d)1234(a)(b)(c)(d)123412341234例(1)A上的全域關(guān)系EA,恒等關(guān)系IA

及空關(guān)系

都是A上的對稱關(guān)系;IA

和

同時(shí)也是A上的反對稱關(guān)系.(2)設(shè)A={1,2,3},則R1={<1,1>,<2,2>}既是A上的對稱關(guān)系,也是A上的反對稱關(guān)系;R2={<1,1>,<1,2>,<2,1>}對稱的,但不是反對稱的;R3={<1,2>,<1,3>}

是反對稱的,但不是對稱的;R4={<1,2>,<2,1>,<1,3>}

不是對稱的也不是反對稱的。

123123對稱性與反對稱性結(jié)論：(1)對稱性和反對稱性不是對立概念，存在既不是對稱也不是反對稱的關(guān)系，也存在既是對稱也是反對稱的關(guān)系。(2)關(guān)系R是對稱的

關(guān)系圖中任何一對結(jié)點(diǎn)之間，要么有方向相反的兩條邊，要么無任何邊；關(guān)系R是反對稱的

關(guān)系圖中任何一對結(jié)點(diǎn)之間，至多有一條邊；(3)關(guān)系R是對稱的

R的關(guān)系矩陣為對稱矩陣關(guān)系R是反對稱的

R的關(guān)系矩陣為反對稱矩陣。傳遞性不是傳遞的不是傳遞的是傳遞的如果(1)不存在傳遞條件，或(2)存在傳遞條件且復(fù)合結(jié)果也屬于R，則為傳遞的。如果存在傳遞條件，但復(fù)合結(jié)果不屬于R，則認(rèn)為不是傳遞的.傳遞性練習(xí)：試判定下列關(guān)系是否具有傳遞性。設(shè)A={1，2，3}，定義A上的關(guān)系R，S，T和V如下：(1)R={<1，1>，<1，2>，<2，3>，<1，3>}；(2)S={<1，2>}；(3)T={<1，1>，<1，2>，<2，3>}；(4)V={<1，2>，<2，3>，<1，3>，<2，1>}。(1)關(guān)系R是傳遞的；(2)關(guān)系S是傳遞的；(3)T在關(guān)系T中，存在x=1，y=2，z=3

A且<1，2>，<2，3>

T，但(1，3)

T，T不是傳遞的；(4)在關(guān)系V中，存在x=1，y=2和z=1

A，使得<1，2>

V

且<2，1>

V，但是<1，1>

V，關(guān)系V不是傳遞的。傳遞性(2)設(shè)R，S，T和V的關(guān)系矩陣分別為MR，MS,，MT

和MV，則。(3)R，S，T和Ｖ的關(guān)系圖分別是圖(a)，(b)，(c)和(d).123(a)(b)(c)(d)123123123例題(1)A上全域關(guān)系EA,恒等關(guān)系IA和空關(guān)系

都是傳遞關(guān)系。(2)小于等于關(guān)系,整除關(guān)系和包含關(guān)系是傳遞關(guān)系,小于關(guān)系和真包含關(guān)系也是傳遞關(guān)系。(3)設(shè)A={1,2,3},則R={<1,2>,<2,3>，<1,3>}R1={<1,1>,<2,2>}

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

都是A上的傳遞關(guān)系,不是A上的傳遞關(guān)系。

都是A上的傳遞關(guān)系,

都是A上的傳遞關(guān)系,傳遞性總結(jié)：(1)R在A上是傳遞的當(dāng)且僅當(dāng)對任意的x，y，z

A，滿足下列任意一個(gè)條件：

<x，y>

R

，<y，z>

R且<x，z>

R

；

<x，y>

R或者<y，z>

R。(2)R在A上不是傳遞的當(dāng)且僅當(dāng)存在x，y，z

A

，有<x，y>

R且<y，z>

R

，<x，z>

R

。

(3)關(guān)系R是傳遞的

關(guān)系圖中任三個(gè)節(jié)點(diǎn)x,y,z之間,若從x到y(tǒng)有一條邊,從y到z有一條邊,則從x到z一定有一條邊。(4)關(guān)系R是傳遞的

R的關(guān)系矩陣中如rij＝1且rjk＝1則

rik＝1設(shè)A={1,2,3},IA={<1,1>,<2,2>,<3,3>}

R1={<1,1>,<2,2>,<3,3>,<1,2>,<2,1>}R2={<2,1>,<1,3>}R3={<1,3>,<3,2>,<1,2>}R3

R3={<1,2>}

R3自反、對稱、反對稱、傳遞自反、對稱、傳遞反自反、反對稱反自反、反對稱、傳遞

123123

性質(zhì)表示自反性反自反性對稱性反對稱性傳遞性集合表達(dá)式IA

RR∩IA=

R=R–1R∩R–1

IAR

R

R關(guān)系矩陣關(guān)系圖各種性質(zhì)在關(guān)系矩陣和關(guān)系圖中的體現(xiàn)

主對角線元素全是1主對角線元素全是0矩陣是對稱矩陣。若rij=1,且i≠j,則rji=0.對角線可能為1對M2中1所在的位置,M中相應(yīng)的位置都是1。每個(gè)頂點(diǎn)都有環(huán)每個(gè)頂點(diǎn)都沒有環(huán)如果兩個(gè)頂點(diǎn)之間有邊,則必是一對方向相反的邊。每對頂點(diǎn)之間至多有一條邊,(不會有雙向邊)如果頂點(diǎn)xi到xj有邊,xj到xk有邊,則從xi到xk也有邊。11/12/20239:09PM

23判斷圖中關(guān)系的性質(zhì)解:(a)該關(guān)系是對稱的.其它性質(zhì)均不具備。

(b)該關(guān)系是反自反的,反對稱的,同時(shí)也是傳遞的。

(c)該關(guān)系是自反的,反對稱的,但不是傳遞的。(a)(b)(c)321231231關(guān)系運(yùn)算與關(guān)系的性質(zhì)

24布爾矩陣的加運(yùn)算25布爾矩陣的乘運(yùn)算2627關(guān)系矩陣運(yùn)算的含義M是R的關(guān)系矩陣，N是S的關(guān)系矩陣，則M+N是

的關(guān)系矩陣是的關(guān)系矩陣?yán)涸O(shè)A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>},求用矩陣求R的各次冪解:R的關(guān)系矩陣:

28可見M4=M2。故R2=R4=R6=…;R3=R5=R7=…。29GR30F和G是