離散數(shù)學(xué)及應(yīng)用（第3版）課件第四章 二元關(guān)系 （上）

第四章二元關(guān)系《離散數(shù)學(xué)及應(yīng)用》第四章二元關(guān)系§4.1關(guān)系及其表示§4.1.1有序?qū)εc笛卡兒積§4.1.2二元關(guān)系的定義§4.1.3二元關(guān)系的表示§4.2關(guān)系的運(yùn)算§4.2.1關(guān)系的基本運(yùn)算§4.2.2關(guān)系的冪和道路§4.3關(guān)系的性質(zhì)§4.3.1關(guān)系性質(zhì)的定義和判斷§4.3.2關(guān)系運(yùn)算對(duì)性質(zhì)的保持23有序?qū)λ拿麑W(xué)生——{張,白,宋,方}三門課程——{離散數(shù)學(xué),數(shù)據(jù)結(jié)構(gòu),計(jì)算機(jī)網(wǎng)絡(luò)}可以使用什么樣的數(shù)學(xué)結(jié)構(gòu)來表示學(xué)生選課的情況？一個(gè)選擇集合例如{張,離散數(shù)學(xué)}4有序?qū)υ倏紤]另一個(gè)問題：他們四人進(jìn)行單循環(huán)羽毛球賽，希望使用一種數(shù)學(xué)結(jié)構(gòu)來表示各場(chǎng)比賽的勝負(fù)關(guān)系。使用集合——{白,方}和{方,白}誰是勝者？需要在數(shù)學(xué)結(jié)構(gòu)中體現(xiàn)出序

(order)5有序?qū)τ蓛蓚€(gè)對(duì)象

a,b

按照一定次序組成的二元組稱為一個(gè)有序?qū)蛐蚺迹╫rderedpair），記作

(a,b)，其中

a

是它的第一元素或第一座標(biāo)，b是它的第二元素或第二座標(biāo)。(a,b)=(c,d)

當(dāng)且僅當(dāng)

a=c

且

b=d例：平面直角坐標(biāo)系上，每一個(gè)點(diǎn)的坐標(biāo)都是一個(gè)有序?qū)Α?笛卡爾積設(shè)

A、B

為兩個(gè)集合，定義它們的笛卡爾積（Cartesianproduct）A×B為

A×B={(a,b)|a

A且

b

B

}，它也稱作直積（directproduct）。A

=

B=

一般來講

A

B

B

A例：平面直角坐標(biāo)系就是笛卡爾積

7笛卡爾積所有可能的選課情況：{張,白,宋,方}

{離散數(shù)學(xué),數(shù)據(jù)結(jié)構(gòu),計(jì)算機(jī)網(wǎng)絡(luò)}=

{(張,離散數(shù)學(xué)),(張,數(shù)據(jù)結(jié)構(gòu)),(張,計(jì)算機(jī)網(wǎng)絡(luò))(白,離散數(shù)學(xué)),(白,數(shù)據(jù)結(jié)構(gòu)),(白,計(jì)算機(jī)網(wǎng)絡(luò)),(宋,離散數(shù)學(xué)),(宋,數(shù)據(jù)結(jié)構(gòu)),(宋,計(jì)算機(jī)網(wǎng)絡(luò)),

(方,離散數(shù)學(xué)),(方,數(shù)據(jù)結(jié)構(gòu)),(方,計(jì)算機(jī)網(wǎng)絡(luò))}8笛卡爾積定理

若

A、B都是有限集，則

A

B

也是有限集，且|A

B|=|A||B|證明：考慮A

B中的每一個(gè)元素(a,b)的產(chǎn)生方式，由乘法原理即得。笛卡爾積定理

笛卡兒積對(duì)于并或交運(yùn)算滿足分配律，即若A、B、C都是集合，則

A×(B∩C)=(A×B)∩(A×C)；

A×(B∪C)=(A×B)∪(A×C)；(B∩C)×A=(B×A)∩(C×A)；(B∪C)×A=(B×A)∪(C×A)。910笛卡爾積笛卡爾積的推廣：

A1

A2…Am ={(a1,a2,…,am)|ai

Ai,i=1,2,…,m

}第四章二元關(guān)系§4.1關(guān)系及其表示§4.1.1有序?qū)εc笛卡兒積§4.1.2二元關(guān)系的定義§4.1.3二元關(guān)系的表示§4.2關(guān)系的運(yùn)算§4.2.1關(guān)系的基本運(yùn)算§4.2.2關(guān)系的冪和道路§4.3關(guān)系的性質(zhì)§4.3.1關(guān)系性質(zhì)的定義和判斷§4.3.2關(guān)系運(yùn)算對(duì)性質(zhì)的保持11二元關(guān)系實(shí)際的選課情況只是笛卡爾積

{張,白,宋,方}

{離散數(shù)學(xué),數(shù)據(jù)結(jié)構(gòu),計(jì)算機(jī)網(wǎng)絡(luò)}的一部分。在羽毛球比賽中，不可能出現(xiàn)(張,張)也不可能同時(shí)出現(xiàn)(張,白)和(白,張)1213二元關(guān)系“關(guān)系”是一個(gè)基本而且普遍的概念。數(shù)學(xué)上講——假設(shè)

A、B

是集合，A×B

的子集

R

稱為A到B的一個(gè)二元關(guān)系，簡稱為關(guān)系（relation）。14二元關(guān)系若

R

A

B

，當(dāng)

(a,b)

R

時(shí)，稱

a與b具有關(guān)系R（aisrelatedtobbyR），記為aRb；若

(a,b)

R，則稱

a,b不具有關(guān)系

R，記為

aRb

。如果

A=B

則稱

R

為

A上的一個(gè)二元關(guān)系。二元關(guān)系例：A={1,2,3,4}R={(1,1),(1,2),(1,4),(2,1),(3,2),(3,4)}“選課”的例子：R={(張,數(shù)據(jù)結(jié)構(gòu)),(張,離散數(shù)學(xué)),(白,數(shù)據(jù)結(jié)構(gòu)),(方,計(jì)算機(jī)網(wǎng)絡(luò))}

{張,白,宋,方}

{離散數(shù)學(xué),數(shù)據(jù)結(jié)構(gòu),計(jì)算機(jī)網(wǎng)絡(luò)}“羽毛球賽”的例子：{(張,白),(宋,張),(張,方),(白,宋),(方,白),(宋,方)}

1516二元關(guān)系對(duì)于任意集合

A

，可以在其冪集P

(A)

上定義包含關(guān)系為：假設(shè)A是非零整數(shù)集的任一子集，則可以定義A上的整除關(guān)系為：

DA={(x,y)|x,y

A且

x|y

}假設(shè)B是實(shí)數(shù)集的任一子集，則可以定義B上的小于等于關(guān)系為：LB={(x,y)|x,y

A且

x≤y}17恒等關(guān)系假設(shè)

A

是任一個(gè)集合，則可定義

A

上的恒等關(guān)系（equality

relation）

為

：

IA={(a,a)|a

A}

。即(a,b)

IA

當(dāng)且僅當(dāng)

a=b

。18二元關(guān)系思考如果|A|=n,那么可以在

A

上定義多少個(gè)不同的關(guān)系?R

A

A|P(A

A)|=2|A

A||A

A|=|A||A|=n2二元關(guān)系假設(shè)

A、B

是集合，R

A×B是

A

到

B

的一個(gè)二元關(guān)系，C

A，則定義關(guān)系

R在集合

C上的限制（restrictionofRtoC）為集合{(a,b)|(a,b)

R

且

a

C}，

記之為

R|C

。19定義域與值域假設(shè)

A、B

是集合，R

A×B是

A

到

B

的一個(gè)二元關(guān)系，R

的定義域（domain）為集合

Dom(R)={a|a

A,

存在

b

B使得

(a,b)

R}，即R中所有有序?qū)Φ牡谝辉貥?gòu)成的集合；R

的值域（range）為集合

Ran(R)={b|b

B,

存在

a

A使得

(a,b)

R}，即R中所有有序?qū)Φ牡诙貥?gòu)成的集合。

20定義域與值域Dom(R)= {a|a

A,b

Bsuchthat(a,b)R}Ran(R)= {b|b

B,a

Asuchthat(a,b)R}2122定義域與值域A={1,2,3,4}R={(1,1),(1,2),(1,4),(2,1),(3,2),(3,4)}Dom(R)={1,2,3}Ran(R)={1,2,4}像集假設(shè)

A、B

是集合，R

A×B

是

A

到

B

的一個(gè)二元關(guān)系，對(duì)于

A

中任一元素

x，可定義

x的像集(image)為

R(x)={y

B|xRy}；對(duì)于A的任一子集A1，可定義A1的像集為

R(A1)={y

B|xRy

對(duì)某

x

A1成立}，且定義

R(

)=

。2324像集R(x)={y

B|xRy}R(A1)={y

B|xRy

且存在

x

A1}R(A1)=∪R(x)，對(duì)所有

x

A1R(

)=

像集25A={1,2,3,4}R={(1,1),(1,2),(1,4),(2,1),(3,2),(3,4)}R(2)=?R(3)=?R({2,3})=?R(2)={1}R(3)={2,4}R({2,3})={1,2,4}26像集定理：

假設(shè)

A、B

是集合，R、S

是

A

到

B

的二元關(guān)系，若對(duì)于所有

a

A

都有R(a)=S(a)

成立，則

R=S

。證明：

R

S

S

R27像集證明：

R

S

若

(a,b)

R

則

b

R(a)=S(a)

于是

(a,b)

S

.

因此

R

S.

S

R ……第四章二元關(guān)系§4.1關(guān)系及其表示§4.1.1有序?qū)εc笛卡兒積§4.1.2二元關(guān)系的定義§4.1.3二元關(guān)系的表示§4.2關(guān)系的運(yùn)算§4.2.1關(guān)系的基本運(yùn)算§4.2.2關(guān)系的冪和道路§4.3關(guān)系的性質(zhì)§4.3.1關(guān)系性質(zhì)的定義和判斷§4.3.2關(guān)系運(yùn)算對(duì)性質(zhì)的保持2829二元關(guān)系的表示形式二元關(guān)系主要具有以下三種表示方法笛卡爾積的子集有序?qū)Φ募详P(guān)系矩陣有向圖表示30關(guān)系矩陣設(shè)

A={a1,a2,…,am}，B={b1,b2,…,bn}，R

是從

A

到

B

的關(guān)系，定義

R

的關(guān)系矩陣為一個(gè)

m

n的布爾矩陣

MR=[rij]m

n，其中關(guān)系矩陣31A={1,2,3,4}R={(1,1),(1,2),(1,4),(2,1),(3,2),(3,4)}12341√√√2√3√√40000101000011011MR=關(guān)系矩陣離散數(shù)據(jù)結(jié)構(gòu)網(wǎng)絡(luò)張

√√白√宋方

√32“選課”的例子R={(張,離散數(shù)學(xué)),(張,數(shù)據(jù)結(jié)構(gòu)),

(白,數(shù)據(jù)結(jié)構(gòu)),(方,計(jì)算機(jī)網(wǎng)絡(luò))}100000010011MR=關(guān)系圖33設(shè)A={a1,a2,…,am}，R是

A上的關(guān)系例：A={1,2,3,4}R={(1,1),(1,2),(1,4),(2,1),(3,2),(3,4)}關(guān)系圖34對(duì)

A中每個(gè)元素，畫一個(gè)圓形，并在圓形之中標(biāo)明該元素。此稱之為關(guān)系圖的頂點(diǎn)（vertice）A={1,2,3,4}R={(1,1),(1,2),(1,4), (2,1),(3,2),(3,4)}1234關(guān)系圖35若(ai,aj)

R，則從頂點(diǎn)

ai向頂點(diǎn)

aj畫一個(gè)箭頭，稱為有向邊或簡稱邊（edge），若

ai=aj則稱這條邊為自環(huán)（cycle）。1234A={1,2,3,4}R={(1,1),(1,2),(1,4),(2,1),(3,2),(3,4)}關(guān)系圖36得到的圖表示稱作關(guān)系

R

的關(guān)系圖（directedgraph，或digraph）。1234A={1,2,3,4}R={(1,1),(1,2),(1,4),(2,1),(3,2),(3,4)}關(guān)系的示意圖（和關(guān)系圖不同）R={(張,離散數(shù)學(xué)),(張,數(shù)據(jù)結(jié)構(gòu)),(白,數(shù)據(jù)結(jié)構(gòu)),(方,計(jì)算機(jī)網(wǎng)絡(luò))}37張白宋方離散數(shù)據(jù)結(jié)構(gòu)網(wǎng)絡(luò)第四章二元關(guān)系§4.1關(guān)系及其表示§4.1.1有序?qū)εc笛卡兒積§4.1.2二元關(guān)系的定義§4.1.3二元關(guān)系的表示§4.2關(guān)系的運(yùn)算§4.2.1關(guān)系的基本運(yùn)算§4.2.2關(guān)系的冪和道路§4.3關(guān)系的性質(zhì)§4.3.1關(guān)系性質(zhì)的定義和判斷§4.3.2關(guān)系運(yùn)算對(duì)性質(zhì)的保持3839關(guān)系的基本運(yùn)算假設(shè)

A、B

是兩個(gè)集合，a

A，b

B，R、S

為

A

到

B

的兩個(gè)關(guān)系，于是R

和

S

都是

A

B

的子集。于是集合的運(yùn)算也可以應(yīng)用于

R

和

S

。40關(guān)系的基本運(yùn)算R

與

S

的交（intersection）關(guān)系

R∩S定義為：

(a,b)

R∩S當(dāng)且僅當(dāng)

(a,b)

R且

(a,b)

S；R

與

S的并（union）關(guān)系

R∪S定義為：

(a,b)

R∪S當(dāng)且僅當(dāng)

(a,b)

R或

(a,b)

S；R

的補(bǔ)（complement）關(guān)系

R

定義為

；aRb當(dāng)且僅當(dāng)

aRb

關(guān)系的基本運(yùn)算{張,白,宋,方}

{離散數(shù)學(xué),數(shù)據(jù)結(jié)構(gòu),計(jì)算機(jī)網(wǎng)絡(luò)}=R

=

{(張,數(shù)據(jù)結(jié)構(gòu)),(張,離散數(shù)學(xué)),

(白,數(shù)據(jù)結(jié)構(gòu)),(方,計(jì)算機(jī)網(wǎng)絡(luò))}R={(張,計(jì)算機(jī)網(wǎng)絡(luò)),(白,離散數(shù)學(xué)),(白,計(jì)算機(jī)網(wǎng)絡(luò)),

(宋,離散數(shù)學(xué)),(宋,數(shù)據(jù)結(jié)構(gòu)),(宋,計(jì)算機(jī)網(wǎng)絡(luò)),

(方,離散數(shù)學(xué)),(方,數(shù)據(jù)結(jié)構(gòu)),}41{(張,離散數(shù)學(xué)),(張,數(shù)據(jù)結(jié)構(gòu)),(張,計(jì)算機(jī)網(wǎng)絡(luò))(白,離散數(shù)學(xué)),(白,數(shù)據(jù)結(jié)構(gòu)),(白,計(jì)算機(jī)網(wǎng)絡(luò)),(宋,離散數(shù)學(xué)),(宋,數(shù)據(jù)結(jié)構(gòu)),(宋,計(jì)算機(jī)網(wǎng)絡(luò)),

(方,離散數(shù)學(xué)),(方,數(shù)據(jù)結(jié)構(gòu)),(方,計(jì)算機(jī)網(wǎng)絡(luò))}42關(guān)系的基本運(yùn)算例：A={1,2,3,4}R={(1,1),(1,2),(1,4),(2,1),(3,2),(3,4)}S={(1,2),(1,3),(2,1),(2,2),(2,4),(4,4)}R∩S={(1,2),(2,1)}R∪S={(1,1),(1,2),(1,3),(1,4),(2,1),(2,2),(2,4),(3,2),(3,4),(4,4)}

關(guān)系的基本運(yùn)算假設(shè)

A、B

是兩個(gè)集合，R

為

A

到

B

的關(guān)系，則

R

的逆（inverse）關(guān)系

定義為R

1={(b,a)|b

B,a

A,(a,b)

R}

B

A。簡言之，R

的逆關(guān)系是由將

R

中每個(gè)有序?qū)Φ脑仨樞蚪粨Q構(gòu)成的。例：A={1,2,3,4}R={(1,1),(1,2),(1,4),(2,1),(3,2),(3,4)}R

1={(1,1),(2,1),(4,1),(1,2),(2,3),(4,3)}43關(guān)系的基本運(yùn)算例R

={(張,數(shù)據(jù)結(jié)構(gòu)),(張,離散數(shù)學(xué)),

(白,數(shù)據(jù)結(jié)構(gòu)),(方,計(jì)算機(jī)網(wǎng)絡(luò))}R

1=

{(數(shù)據(jù)結(jié)構(gòu),張),(離散數(shù)學(xué),張),

(數(shù)據(jù)結(jié)構(gòu),白),(計(jì)算機(jī)網(wǎng)絡(luò),方)}44關(guān)系的基本運(yùn)算45A={1,2,3,4}R={(1,1),(1,2),(1,4),(2,1),(3,2),(3,4)}R

1={(1,1),(2,1),(4,1),(1,2),(2,3),(4,3)}關(guān)系的基本運(yùn)算假設(shè)

A、B、C

是集合，R

為

A

到

B

的關(guān)系，S

為

B

到

C

的關(guān)系，則

S?R

表示

A

到

C

的一個(gè)關(guān)系S?R={(a,c)|

a

A,c

C,存在

b

B使得

(a,b)

R

且

(b,c)

S

}，稱為

R

和

S

的復(fù)合（composition）關(guān)系或合成關(guān)系。

46關(guān)系的基本運(yùn)算47R={(張,數(shù)據(jù)結(jié)構(gòu)),(張,離散數(shù)學(xué)),

(白,數(shù)據(jù)結(jié)構(gòu)),(方,計(jì)算機(jī)網(wǎng)絡(luò))}，S={(數(shù)據(jù)結(jié)構(gòu),逸夫樓),(數(shù)據(jù)結(jié)構(gòu),一教),

(離散數(shù)學(xué),一教),(計(jì)算機(jī)網(wǎng)絡(luò),四教)}

張白宋方離散數(shù)據(jù)結(jié)構(gòu)網(wǎng)絡(luò)一教逸夫樓四教RS關(guān)系的基本運(yùn)算48S?R=?張白宋方離散數(shù)據(jù)結(jié)構(gòu)網(wǎng)絡(luò)一教逸夫樓四教}(方,四教)(白,一教),(白,逸夫樓),(張,逸夫樓),(張,一教),={RS關(guān)系的基本運(yùn)算R={(1,1),(1,2),(1,4),(2,1),(3,2),(3,4)}S={(1,2),(1,3),(2,1),(2,2),(2,4),(4,4)}R?S=?R?S={(1,1),(1,2),(1,4),(2,1),(2,2),(2,4)}S?R=?S?R

={(1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(3,1),(3,2),(3,4)}49關(guān)系的基本運(yùn)算假設(shè)

A、B、C

為有限集合，R

為

A

到

B

的關(guān)系，S

為

B到

C

的關(guān)系，則有MS?R=MR⊙MS500000101000011011MR=1000000010110110MS=0000101101101111MR⊙

MS=0000101101101111MS?R=V.S.51r11r12…r1mr21r22…r2m………ri1ri2…rim………rn1rn2…rnms11s12…s1j…s1ps21s22…s2j…s2p…………sm1sm2…smj…smp⊙ri1ri2…rims1js2j…smj∧∧∧cij∨rik

=1skj

=1kjikikj關(guān)系的基本運(yùn)算關(guān)系矩陣形式關(guān)系圖形式

RMR=MR=1-MR圖的“補(bǔ)”R∩SMR∩S=MR∧MS圖的“交”R∪SMR∪S=MR∨MS圖的“并”R

1MR

1=(MR)T每條邊做“反向”S?RMS?R=MR⊙MS52關(guān)系運(yùn)算的性質(zhì)定理

假設(shè)

A、B

是集合，R、S為

A

到

B

的關(guān)系，則：Dom(R

1)=Ran(R)，Dom(R)=Ran(R

1)；R

=

R；(R

1)

1=R；

R

1

=

(R)

1；(R∩S)

1=R

1∩S

1且

(R∪S)

1=R

1∪S

1。R∩S

=R∪S且

R∪S

=R∩S。

53關(guān)系運(yùn)算的性質(zhì)R=S

當(dāng)且僅當(dāng)

MR=MS證明：M(R∩S)1=(MR∩S)T=(MR∧MS)TMR1∩S

1=(MR

1∧MS

1)=MRT∧MST

54(rji∧sji)(R∩S)1=R1∩S1關(guān)系運(yùn)算的性質(zhì)定理

假設(shè)

A、B、C、D

均為非空集合，R

為

A

到

B

的關(guān)系，S

為

B

到

C

的關(guān)系，T為

C

到

D

的關(guān)系，則T?(S?R)=(T?S)?R5556關(guān)系運(yùn)算的性質(zhì)證明： MT?(S?R)

=(MR⊙MS)⊙MT M(T?S)?R=MR⊙(MS⊙MT)關(guān)系運(yùn)算的性質(zhì)定理

假設(shè)

A、B、C

為非空集合，R

為

A

到

B

的關(guān)系，S

為

B

到

C

的關(guān)系，則(S?R)

1

=R

1?S

157關(guān)系運(yùn)算的性質(zhì)定理

假設(shè)

A、B、C

是集合，R、S為

A

到

B

的關(guān)系，若

R

S，則

R

1

S

1；若

R

S，則

S

R。5859定理

假設(shè)

A、B、C

為集合，R1、R2

為

A

到

B

的關(guān)系，S1、S2

為

B

到

C

的關(guān)系，R1

R2，S1

S2，則

S1?R1

S2?R2。關(guān)系的基本運(yùn)算關(guān)系運(yùn)算的性質(zhì)定理

假設(shè)

A、B、C、D為集合，R

為

A

到

B

的關(guān)系，S1、S2

為

B到

C

的關(guān)系，T

為

C

到

D

的關(guān)系，則：(S1∪S2)?R

=(S1?R)∪(S2?R)(S1∩S2)?R

(S1?R)∩(S2?R)T?(S1∪S2)=(T?S1)∪(T?S2)T?(S1∩S2)

(T?S1)∩(T?S2)

6061定理

假設(shè)

A、B、C

為集合，R

為

A

到

B

的關(guān)系，S

為

B

到

C

的關(guān)系，則對(duì)于

A

的任意子集

A1

有：(S?R)(A1)=S(R(A1))。關(guān)系運(yùn)算的性質(zhì)關(guān)系運(yùn)算的性質(zhì)62(S?R)(A1)=S(R(A1))RSBCAA1R(A1)S(R(A1))S?R(S?R)(A1)關(guān)系運(yùn)算的性質(zhì)63(S?R)(白)={逸夫樓,一教}S(R(白))=S({數(shù)據(jù)結(jié)構(gòu)})={逸夫樓,一教}張白宋方離散數(shù)據(jù)結(jié)構(gòu)網(wǎng)絡(luò)一教逸夫樓四教RS64證明（主體思路） (a)(S?R)(A1)

S(R(A1))令

c

(S?R)(A1)。則存在

a

A1，使得

(a,c)

S?R。存在b

B，使得

(a,b)

R

且

(b,c)

S。于是

b

R(A1)，并且有

c

S(R(A1))。故而

c

S(R(A1))。 (b)S(R(A1))

(S?R)(A1)

……關(guān)系運(yùn)算的性質(zhì)(S?R)(A1)=S(R(A1))關(guān)系運(yùn)算的性質(zhì)██

1R∩SR∩S=R∪S(R∩S)

1=R

1∩S

1R∪SR∪S=R∩S(R∪S)

1=R

1∪S

1S?R/(S?R)

1=R

1?S

1R

SS

RR

1

S

1R=R(R

1)

1=RR

1

=(R)

165第四章二元關(guān)系§4.1關(guān)系及其表示§4.1.1有序?qū)εc笛卡兒積§4.1.2二元關(guān)系的定義§4.1.3二元關(guān)系的表示§4.2關(guān)系的運(yùn)算§4.2.1關(guān)系的基本運(yùn)算§4.2.2關(guān)系的冪和道路§4.3關(guān)系的性質(zhì)§4.3.1關(guān)系性質(zhì)的定義和判斷§4.3.2關(guān)系運(yùn)算對(duì)性質(zhì)的保持66關(guān)系的冪和道路671234關(guān)系的冪和道路假設(shè)

A

為集合，a,b

A，集合

A

上關(guān)系

R

中從

a

到

b

長為

n的道路（path）是指

A

上有限序列

:a,x1,x2,…xn

1,b，滿足：aRx1xiRxi+1，1

i

n

2xn

1Rb注：長度為n的道路包含n+1個(gè)頂點(diǎn)（允許重復(fù)）。68abx1x2xn-1……關(guān)系的冪和道路69從

a

到

e長為

8

的一條道路abcdfegh關(guān)系的冪和道路70假設(shè)

A

為集合，a,b

A，集合

A

上關(guān)系

R

中從

a

到

b

的一條道路（path）是指

A

上有限序列

:a,x1,x2,…xn

1,b，其中

n>0

稱為該道路的長度（length），a

稱作道路的起點(diǎn)，b

稱作道路的終點(diǎn)。關(guān)系的冪和道路71從

a

到

d的一條道路abcdfegh關(guān)系的冪和道路72起點(diǎn)和終點(diǎn)相同的道路稱之為回路（circuit）。abcdfegh關(guān)系的冪和道路73假設(shè)

1:a,x1,x2,…,xn-1,b

和

2:b,y1,y2,…,ym-1,c是關(guān)系

R

中的兩條道路則定義

1

和

2的復(fù)合（composition）為道路

a,x1,…,xn-1,b,y1,…,ym-1,c關(guān)系的冪和道路74

1:a,e,b,c,d

2:d,f,g,e

2?1:a,e,b,c,d,f,g,eabcdfegh關(guān)系的冪和道路設(shè)

R

為集合

A

上的關(guān)系定義A

上的關(guān)系

Rn

為：a,b

A，則

aRn

b當(dāng)且僅當(dāng)存在

R

中從

a

到

b

長為

n

的道路定義A

上的關(guān)系

R

為：a,b

A，則

aR

b當(dāng)且僅當(dāng)存在

R

中從

a

到

b

的道路75關(guān)系的冪和道路761234R2R1234關(guān)系的冪和道路771234R∞R1234關(guān)系的冪和道路781234RR212341234R∞R∞Rn關(guān)系的冪和道路79當(dāng)集合A

中元素較多時(shí)，如何計(jì)算

Rn

和

R

？手工繪制？繁瑣

困難變更技術(shù)路線代數(shù)方法關(guān)系的冪和道路設(shè)

R

為集合

A

上的關(guān)系，n

為自然數(shù)則

R

的

n次冪（power）Rn可遞歸地定義為R0=IARn=Rn

1?R

，

n=1,2,3,...與之前的定義等價(jià)80關(guān)系的冪和道路設(shè)

R

為有限集合

A

上的關(guān)系，n

為自然數(shù)，則MR2=MR⊙MR

MRn=MR⊙MR

…⊙MR(n個(gè)R的復(fù)合)

也記作

(MR)⊙n

81關(guān)系的冪和道路定理：

設(shè)

R

為集合

A

上的關(guān)系，則

R

=R∪R2∪R3∪……

，即 MR

=

MR∨MR2∨MR3∨…

=MR∨(MR)⊙2

∨(MR)⊙3…

82關(guān)系的冪和道路證明：(1)R

R∪R2∪R3∪……假設(shè)

a,b

A

且

aR

b，則存在

R

中從

a

到

b

的道路

。設(shè)

的長度為

n，則

aRnb，于是

(a,b)

R∪R2∪R3∪……

。(2)R∪R2∪R3∪……

R

對(duì)于任意

(a,b)

R∪R2∪R3∪……

，必存在整數(shù)

n

使得

aRnb，即存在

R

中從

a

到

b

長為

n

的道路，于是存在

R

中從

a

到

b

的道路，繼而因此

aR

b。83關(guān)系的冪和道路定理：

設(shè)

R

為集合

A

上的關(guān)系，則

R

=R∪R2∪R3∪……

，即 MR

=

MR∨MR2∨MR3∨…

=MR∨(MR)⊙2

∨(MR)⊙3…

84計(jì)算可行性？關(guān)系的冪和道路定理

假設(shè)

R

是有限集合

A

上的關(guān)系，|A|=n，則：R

=R∪R2∪R3∪…∪Rn

。85關(guān)系的冪和道路證明：

分兩部分證明： (a)顯然有R∪R2∪…∪Rn

R

=R∪R2∪…。 (b)下面證明

R

R∪R2∪R3∪…∪Rn。86關(guān)系的冪和道路證明：

若

aR

b，則存在

R

中從

a

到

b

的道路

:a,x1,x2,…xm

1,b其中

m≥1。

若m

1>n

則由鴿巢原理，必定存在頂點(diǎn)

xi

和

xj，i<j使得

xi=xj。

8788證明：關(guān)系的冪和道路axi...xi+1bxj+1......xj-1xj更短的道路！關(guān)系的冪和道路證明：

因此總可以假定道路中間經(jīng)過的頂點(diǎn)各異，且

m

1

n

。（道路長度為m）

若

m

1<n

，則定理成立。

若

m

1=n

，則存在

k，使得1

k

m

1,a=xk

或

b=xk；不失一般性地假定

a=xk

。則——8990證明：關(guān)系的冪和道路ax1bxk+1......xk-1xk更短的道路！91證明：

因此，存在從

a

到

b

的道路

’，其長度不超過

n，即

(a,b)

R∪R2∪R3∪…∪Rn。

關(guān)系的冪和道路關(guān)系的冪和道路思考：是否存在集合A

和A

上的關(guān)系R，使得對(duì)于任意n

1，都有R∪R2∪R3∪…∪Rn

R

？92第四章二元關(guān)系§4.1關(guān)系及其表示§4.1.1有序?qū)εc笛卡兒積§4.1.2二元關(guān)系的定義§4.1.3二元關(guān)系的表示§4.2關(guān)系的運(yùn)算§4.2.1關(guān)系的基本運(yùn)算§4.2.2關(guān)系的冪和道路§4.3關(guān)系的性質(zhì)§4.3.1關(guān)系性質(zhì)的定義和判斷§4.3.2關(guān)系運(yùn)算對(duì)性質(zhì)的保持93關(guān)系的性質(zhì)自反關(guān)系、非自反關(guān)系涉及“1個(gè)”元素對(duì)稱關(guān)系、非對(duì)稱關(guān)系、反對(duì)稱關(guān)系涉及“2個(gè)”元素傳遞關(guān)系涉及“3個(gè)”元素94自反性①假設(shè)

R

為集合

A

上的關(guān)系，如果

(a,a)

R對(duì)于所有

a

A成立，則稱

R

是自反的（reflexive），或稱

R

滿足自反性；如果

(a,a)

R對(duì)于所有

a

A

成立，則稱

R

是非自反的（irreflexive），或稱

R

滿足非自反性。95自反性關(guān)系矩陣的特點(diǎn)關(guān)系圖的特點(diǎn)自反關(guān)系

a(a,a)

R主對(duì)角線元素全是1，即對(duì)于所有

i，MR(i,i)=1每個(gè)頂點(diǎn)都有自環(huán)非自反關(guān)系

a(a,a)

R主對(duì)角線元素全是0，即對(duì)于所有

i，MR(i,i)=0每個(gè)頂點(diǎn)都無自環(huán)9697自反？非自反？1234R98自反？非自反？1234R99自反？非自反？1234R100自反關(guān)系與非自反關(guān)系A(chǔ)

上所有關(guān)系自反關(guān)系非自反關(guān)系對(duì)稱性②

假設(shè)

R

為集合

A

上的關(guān)系，如果對(duì)于任意

a,b

A，若

(a,b)

R必然有

(b,a)

R，則稱

R

是對(duì)稱的（symmetric），或稱

R

滿足對(duì)稱性；如果對(duì)于任意

a,b

A，若

(a,b)

R必然有

(b,a)

R，則稱

R

是非對(duì)稱的（asymmetric），或稱

R

滿足非對(duì)稱性；如果對(duì)于任意

a,b

A，若

(a,b)

R且

(b,a)

R

必然有

a=b，則稱

R

是反對(duì)稱的（antisymmetric），或稱

R

滿足反對(duì)稱性。101102反對(duì)稱性另一等價(jià)定義

a

b((a,b)

R∧(b,a)

R

a=b)

a

b(~((a,b)

R∧(b,a)

R)∨a=b)

a

b(~(a,b)

R∨~(b,a)

R∨a=b)

a

b(~((a,b)

R∧a

b)∨~(b,a)

R)

a

b((a,b)

R∧a

b

(b,a)

R)

對(duì)稱？非對(duì)稱？反對(duì)稱？103A={1,2,3},R={(1,2),(3,1),(3,3)}abaRbbRa

aRb

bRa11FFT12TFF13FTT21FTT22FFT23FFT31TFF32FFT33TTT123010000101不具有對(duì)稱性對(duì)稱？非對(duì)稱？反對(duì)稱？104A={1,2,3},R={(1,2),(3,1),(3,3)}abaRbbRa

aRb~bRa11FFT12TFT13FTT21FTT22FFT23FFT31TFT32FFT33TTF123010000101不具有非對(duì)稱性對(duì)稱？非對(duì)稱？反對(duì)稱？105A={1,2,3},R={(1,2),(3,1),(3,3)}abaRbbRaaRb

bRa

b=a11FFT12TFT13FTT21FTT22FFT23FFT31TFT32FFT33TTT123010000101具有反對(duì)稱性對(duì)稱性106關(guān)系矩陣的特點(diǎn)關(guān)系圖的特點(diǎn)對(duì)稱關(guān)系矩陣是對(duì)稱矩陣

，即對(duì)于所有i,j，MR(i,j)=MR(j,i)如果兩個(gè)頂點(diǎn)之間有邊，一定是一對(duì)方向相反的邊非對(duì)稱關(guān)系對(duì)于所有i,j，若MR(i,j)=1則

MR(j,i)=0兩頂點(diǎn)之間至多存在一條有向邊，每個(gè)頂點(diǎn)都無自環(huán)反對(duì)稱關(guān)系對(duì)于所有i,j，若i≠j且MR(i,j)=1則MR(j,i)=0兩互異頂點(diǎn)之間至多存在一條有向邊，允許存在自環(huán)107對(duì)稱性保留對(duì)稱關(guān)系的有向圖中的頂點(diǎn)，且將所有有向邊改作無向邊，其結(jié)果稱作該關(guān)系的圖（graph）。對(duì)稱性1081234R1234R對(duì)稱性1091234R1234R110傳遞性③假設(shè)

R

為集合

A

上的關(guān)系，如果對(duì)于任意

a,

b,c

A，若

(a,b)

R且

(b,c)

R

必然有

(a,c)

R，則稱

R

是傳遞的（transitive），或稱

R

滿足傳遞性。具有傳遞性？111A={1,2},R={(1,1),(1,2)}abcaRbbRaaRcaRb

bRc

aRc111TTTT112TTTT121TFTT122TFTT211FTFT212FTFT221FFFT222FFFT12具有傳遞性？112A={1,2},R={(1,2),(2,1)}abcaRbbRaaRcaRb

bRc

aRc111FFFT112FTTT121TTFF122TFTT211TFFT212TTFF221FTFT222FFFT12具有傳遞性？113A={1,2},R={(1,2)}abcaRbbRaaRcaRb

bRc

aRc111FFFT112FTTT121TFFT122TFTT211FFFT212FTFT221FFFT222FFFT12不具有傳遞性 ~a

b

c((a,b)R∧(b,c)R

(a,c)R)

a

b

c((a,b)R∧(b,c)R∧(a,c)R)114a=cbaaaabc傳遞性115關(guān)系矩陣的特點(diǎn)關(guān)系圖的特點(diǎn)傳遞關(guān)系

a

b

c((a,b)

R∧(b,c)

R

(a,c)

R)??116關(guān)系性質(zhì)的判斷定理

設(shè)

R

為集合

A

上的關(guān)系，則R

具有對(duì)稱性當(dāng)且僅當(dāng)

R=R

1

R

具有非對(duì)稱性當(dāng)且僅當(dāng)

R∩R

1=

R

具有反對(duì)稱性當(dāng)且僅當(dāng)

R∩R

1

IA

關(guān)系性質(zhì)的判斷證明：R

具有對(duì)稱性當(dāng)且僅當(dāng)

R=R

1

若

R

具有對(duì)稱性則

R=R

1

(i)

R

R

1.假設(shè)(x,y)

R，

由于

R

具有對(duì)稱性，因此

(y,x)

R即

(x,y)

R

1于是

(x,y)

R

1，于是

R

R

1(ii)R

1

R.117關(guān)系性質(zhì)的判斷證明：R

具有對(duì)稱性當(dāng)且僅當(dāng)

R=R

1

若則

R=R

1