第4章二元關(guān)系與函數(shù)4.1集合笛卡兒積與二元關(guān)系4.2關(guān)系運(yùn)算4.3關(guān)系性質(zhì)4.4關(guān)系閉包4.5等價(jià)關(guān)系和偏序關(guān)系4.6函數(shù)定義和性質(zhì)4.7函數(shù)復(fù)合和反函數(shù)1第1頁4.1集合笛卡兒積和二元關(guān)系

有序?qū)Φ芽▋悍e及其性質(zhì)二元關(guān)系定義二元關(guān)系表示2第2頁有序?qū)Χx

由兩個(gè)元素x和y，按照一定次序組成二元組稱為有序?qū)Γ涀?lt;x,y>實(shí)例：平面直角坐標(biāo)系中點(diǎn)坐標(biāo)<3,

4>有序?qū)π再|(zhì)1）有序性<x,y>

<y,x>（當(dāng)x

y時(shí)）2）<x,y>與<u,v>相等充分必要條件是<x,y>=<u,v>

x=u

y=v例1<2,x+5>=<3y

4,y>，求x,y.解3y

4=2,x+5=y

y=2,x=3

3第3頁有序n元組定義一個(gè)有序n(n3)元組<x1,x2,…,xn>是一個(gè)有序?qū)Γ渲械谝粋€(gè)元素是一個(gè)有序n-1元組，即<x1,x2,…,xn>=<<x1,x2,…,xn-1>,xn>

實(shí)例：空間直角坐標(biāo)系中坐標(biāo)

<3，5，－6>n維向量是有序n元組.當(dāng)n=1時(shí),<x>形式上能夠看成有序1元組.4第4頁笛卡兒積定義設(shè)A,B為集合，用A中元素為第一個(gè)元素，B中元素為第二個(gè)元素，組成有序?qū)?全部這么有序?qū)M成集合叫做A與B笛卡兒積

記作A

B，即A

B={<x,y>|x

A

y

B}例2A={1,2,3},B={a,b,c}

A

B={<1,a>,<1,b>,<1,c>,<2,a>,<2,b>,<2,c>,<3,a>,<3,b>,<3,c>}

B

A={<a,1>,<b,1>,<c,1>,<a,2>,<b,2>,<c,2>,<a,3>,<b,3>,<c,3>}

A={

},P(A)

A={<

,

>,<{

},

>}5第5頁笛卡兒積性質(zhì)不適合交換律

A

B

B

A(A

B,A

,B

)不適合結(jié)合律

(A

B)

C

A

(B

C)(A

,B

)對于并或交運(yùn)算滿足分配律

A

(B

C)=(A

B)

(A

C)(B

C)

A=(B

A)

(C

A)

A

(B

C)=(A

B)

(A

C)(B

C)

A=(B

A)

(C

A)若A或B中有一個(gè)為空集，則A

B就是空集.

A

=

B=

若|A|=m,|B|=n,則|A

B|=mn

6第6頁性質(zhì)證實(shí)證實(shí)A

(B

C)=(A

B)

(A

C)證任取<x,y><x,y>∈A×(B∪C)

x∈A∧y∈B∪C

x∈A∧(y∈B∨y∈C)

(x∈A∧y∈B)∨(x∈A∧y∈C)

<x,y>∈A×B∨<x,y>∈A×C

<x,y>∈(A×B)∪(A×C)所以有A×(B∪C)=(A×B)∪(A×C).7第7頁例題解(1)任取<x,y><x,y>

A

C

x

A

y

C

x

B

y

D

<x,y>

B

D

例3(1)證實(shí)A=B

C=D

A

C=B

D

(2)A

C=B

D是否推出A=B

C=D?為何？(2)不一定.反例以下：

A={1}，B={2},C=D=

,則A

C=B

D不過A

B.8第8頁例4(1)證實(shí)A

B

C

D

A

C

B

D

(2)A

C

B

D是否推出A

B

C

D解(1)任取<x,y><x,y>

A

C

x

A

y

C

x

B

y

D

<x,y>

B

D

(2)不一定.反例以下：

A={1}，B={2},C=D=

9第9頁例5設(shè)A、B、C、D為任意集合，判斷以下等式是否成立，說明為何。(A

B)(C

D)=(A

C)(B

D)(A

B)(C

D)=(A

C)

(B

D)(A-B)(C-D)=(A

C)-(B

D)(A

B)(C

D)=(A

C)

(B

D)解：(1)成立，因?yàn)閷θ我?lt;x,y><x,y>

(A

B)(CD)x

A

ByCDx

A

x

ByCyD<x,y>

A

C

<x,y>

B

D10第10頁(2)(A

B)(C

D)=(A

C)(B

D)解：不成立，若A=D=B=C={1}則有：(A

B)(CD)=B

C={<1,1>}(3)(A-B)(C-D)=(A

C)-(B

D)解：不成立，A=B={1}C={2}D={3}(A-B)(C-D)=(A

C)-(BD)={<1,2>}{<1,3>}={<1,2>}(4)(A

B)(C

D)=(A

C)

(B

D)解：A={1}B=C=D={1}(A

B)(CD)={1,1}(A

C)(BD)=11第11頁設(shè)A1,A2,…,An是集合(n≥2),它們n階笛卡爾積記作A1

A2

…

An,其中A1

A2

…

An={<x1,x2,…,xn>︱x1A1,x2

A2,…,xnAn}.當(dāng)A1=A2

=…=An時(shí)，可將它們n階笛卡爾積記作An比如：A={a,b},則A3={<a,a,a>,<a,a,b>,<a,b,a>,<a,b,b>,<b,a,a>,<b,a,b>,<b,b,a>,<b,b,b>}12第12頁二元關(guān)系：集合中兩個(gè)元素之間某種關(guān)系例1甲、乙、丙3個(gè)人進(jìn)行乒乓球比賽，任何兩個(gè)人之間都要比賽一場。假設(shè)比賽結(jié)果是乙勝甲，甲勝丙，乙勝丙。比賽結(jié)果可表示為：{<乙,甲>，<甲,丙>，<乙,丙>}，其中<x,y>表示x勝y，它表示了集合{甲,乙,丙}中元素之間一個(gè)勝敗關(guān)系.例2有A、B、C3個(gè)人和四項(xiàng)工作G1、G2、G3、G4，已知A能夠從事工作G1和G4，B能夠從事工作G3，C能夠從事工作G1和G2.那么，人和工作之間對應(yīng)關(guān)系能夠記作R＝

{<A,G1>,<A,G4>,<B,G3>,<C,G1>,<C,G2}它表示了集合{A,B,C}到工作{G1,G2,G3,G4}之間關(guān)系13第13頁二元關(guān)系定義定義假如一個(gè)集合滿足以下條件之一：（1）集合非空,且它元素都是有序?qū)Γ?）集合是空集則稱該集合為一個(gè)二元關(guān)系,簡稱為關(guān)系，記作R.如<x,y>∈R,可記作xRy；假如<x,y>

R,則記作xy實(shí)例：R={<1,2>,<a,b>},S={<1,2>,a,b}.R是二元關(guān)系,當(dāng)a,b不是有序?qū)r(shí)，S不是二元關(guān)系依據(jù)上面記法，能夠?qū)?R2,aRb,ac等.14第14頁從A到B關(guān)系與A上關(guān)系定義設(shè)A,B為集合,A×B任何子集所定義二元關(guān)系叫做從A到B二元關(guān)系,當(dāng)A=B時(shí)則叫做A上二元關(guān)系.例4A={0,1},B={1,2,3},R1={<0,2>},R2=A×B,R3=

,R4={<0,1>}.那么R1,R2,R3,R4是從A到B二元關(guān)系,R3和R4同時(shí)也是A上二元關(guān)系.計(jì)數(shù)|A|=n,|A×A|=n2,A×A子集有個(gè).所以A上有個(gè)不一樣二元關(guān)系.比如|A|=3,則A上有=512個(gè)不一樣二元關(guān)系.15第15頁A上主要關(guān)系實(shí)例設(shè)A為任意集合，

是A上關(guān)系，稱為空關(guān)系EA,IA分別稱為全域關(guān)系與恒等關(guān)系，定義以下：

EA={<x,y>|x∈A∧y∈A}=A×A

IA={<x,x>|x∈A}

比如,A={1,2},則

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

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

16第16頁A上主要關(guān)系實(shí)例（續(xù)）小于等于關(guān)系LA,整除關(guān)系DA,包含關(guān)系R

定義：LA={<x,y>|x,y∈A∧x≤y},A

R，R為實(shí)數(shù)集合DB={<x,y>|x,y∈B∧x整除y},B

Z+,Z+為非0整數(shù)集R

={<x,y>|x,y∈A∧x

y},A是集合族.類似還能夠定義大于等于關(guān)系,小于關(guān)系,大于關(guān)系,真包含關(guān)系等等.17第17頁實(shí)例比如A={1,2,3},B={a,b},則

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

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

A=P(B)={

,{a},{b},{a,b}},則A上包含關(guān)系是R

={<

,

>,<

,{a}>,<

,{b}>,<

,{a,b}>,<{a},{a}>,<{a},{a,b}>,<{b},{b}>,<{b},{a,b}>,<{a,b},{a,b}>}

18第18頁關(guān)系表示表示方式：關(guān)系集合表示式、關(guān)系矩陣、關(guān)系圖關(guān)系矩陣：若A={x1,x2,…,xm}，B={y1,y2,…,yn}，R是從A到B關(guān)系，R關(guān)系矩陣是布爾矩陣MR=[rij]m

n,其中rij

=1

<xi,yj>

R.關(guān)系圖：若A={x1,x2,…,xm}，R是從A上關(guān)系，R關(guān)系圖是GR=<A,R>,其中A為結(jié)點(diǎn)集，R為邊集.假如<xi,xj>屬于關(guān)系R，在圖中就有一條從xi

到xj有向邊.注意：A,B為有窮集，關(guān)系矩陣適于表示從A到B關(guān)系或者A上關(guān)系，關(guān)系圖適于表示A上關(guān)系19第19頁實(shí)例A={1,2,3,4},R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>},R關(guān)系矩陣MR和關(guān)系圖GR以下：20第20頁基本運(yùn)算定義定義域、值域、域逆、合成、限制、像基本運(yùn)算性質(zhì)冪運(yùn)算定義求法性質(zhì)4.2關(guān)系運(yùn)算21第21頁關(guān)系基本運(yùn)算定義定義域、值域

和域domR={x|

y(<x,y>

R)}ranR={y|

x(<x,y>

R)}fldR=domR

ranR例1R={<1,2>,<1,3>,<2,4>,<4,3>},則domR={1,2,4}ranR={2,3,4}fldR={1,2,3,4}22第22頁關(guān)系基本運(yùn)算定義（續(xù)）定義設(shè)F、G為任意關(guān)系，A為集合，則逆與合成

F

1={<y,x>|<x,y>

F}

F°G=|<x,y>|

z(<x,z>

G

<z,y>

F)}例2R={<1,2>,<2,3>,<1,4>,<2,2>}

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

R

1={<2,1>,<3,2>,<4,1>,<2,2>}S°R={<1,3>,<2,2>,<2,3>}R°S={<1,2>,<1,4>,<3,2>,<3,3>}23第23頁合成運(yùn)算圖示方法

利用圖示（不是關(guān)系圖）方法求合成

R°S={<1,2>,<1,4>,<3,2>,<3,3>}

S°R={<1,3>,<2,2>,<2,3>}R°SS°R24第24頁限制與像定義F在A上限制

F?A={<x,y>|xFy

x

A}A在F下像

F[A]=ran(F?A)實(shí)例R={<1,2>,<2,3>,<1,4>,<2,2>}

R?{1}={<1,2>,<1,4>}

R[{1}]={2,4}

R?=

R[{1,2}]={2,3,4}注意：F?A

F,F[A]ranF

25第25頁例.設(shè)F、G是N上關(guān)系，其定義為F={<x,y>︱x,yNy=x2}G={<x,y>︱x,yNy=x+1}求G

1、F°G、G°F、F?{1,2}、F[{1,2}]解：G

1={<y,x>︱y,xNy=x+1}G

1={<1,0><2,1><3,2>,…<x+1,x>,…}對任何xN有y=z2=(x+1)2，所以

F°G={<x,y>︱x,yNy=(x+1)2

}G°F={<x,y>︱x,yNy=x2+1}F?{1,2}={<1,1>,<2,4>}F[{1,2}]=ran(F?{1,2})={1,4}26第26頁例.設(shè)F={<a,{a}>,<{a},{a,{a}}>},求F°F、F?{a}、F[{a}]解：F°F={<a,{a,{a}}>}F?{a}={<a,{a}>}A={a}F[A]=ran(F?A)=ran{<a,{a}>}={{a}}27第27頁關(guān)系基本運(yùn)算性質(zhì)定理4.1設(shè)F是任意關(guān)系,則(1)(F

1)

1=F(2)domF

1=ranF,ranF

1=domF證(1)任取<x,y>,由逆定義有<x,y>∈(F

1)

1

<y,x>∈F

1

<x,y>∈F所以有(F

1)

1=F(2)任取x,x∈domF

1

y(<x,y>∈F

1)

y(<y,x>∈F)

x∈ranF

所以有domF

1=ranF.同理可證ranF

1=domF.28第28頁(3)(F°G)°H=F°(G°H)(4)(F°G)

1=G

1°F

1證(3)任取<x,y>,<x,y>

(F°G)°H

t(<x,t>∈H∧<t,y>∈F°G)

t(<x,t>∈H∧

s(<t,s>∈G)∧<s,y>∈F))

t

s(<x,t>∈H∧<t,s>∈G∧<s,y>∈F)

s(<s,y>∈F∧

t(<x,t>∈H∧<t,s>∈G))

s(<s,y>∈F∧<x,s>∈G°H)

<x,y>∈F°(G°H)

所以(F°G)°H=F°(G°H)關(guān)系基本運(yùn)算性質(zhì)（續(xù)）

29第29頁(4)任取<x,y>,<x,y>∈(F°G)

1

<y,x>∈F°G

t(<y,t>∈G∧(t,x)∈F)

t(<x,t>∈F

1∧(t,y)∈G

1)

<x,y>∈G

1°F

1所以(F°G)

1=G

1°F

1

關(guān)系基本運(yùn)算性質(zhì)（續(xù)）

30第30頁關(guān)系基本運(yùn)算性質(zhì)（續(xù)）

定理4.2設(shè)F、G、H為任意二元關(guān)系，則有：F°(G

H)

=F°G

F°H(G

H)

°F=G°F

H°F(合成運(yùn)算對運(yùn)算滿足分配律）3.F°(G

H)

F°G

F°H4.(G

H)

°F

G°F

H°F(合成運(yùn)算對

運(yùn)算分配后是包含關(guān)系）31第31頁A上關(guān)系冪運(yùn)算設(shè)R為A上關(guān)系,n為自然數(shù),則R

n次冪定義為：(1)R0={<x,x>|x∈A}=IA

(2)Rn

=Rn-1°R,n≥1注意：對于A上任何關(guān)系R1和R2都有

R10=R20=IA

對于A上任何關(guān)系R都有

R1=R32第32頁冪求法(1)對于集合表示關(guān)系R，計(jì)算Rn就是n個(gè)R左復(fù)合.(2)矩陣表示就是n個(gè)矩陣相乘,其中相加采取邏輯加.例3設(shè)A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>},求R各次冪,分別用矩陣和關(guān)系圖表示.