離散數(shù)學(xué)第5章

第五章 映射與無限集1映射(函數(shù))計算機科學(xué)通過研究映射的性質(zhì)獲取描述處理對象的技術(shù).所謂映射,其實是一個集合到另一個集合元素之間所對應(yīng)關(guān)系的一種指定規(guī)則.映射也稱為函數(shù)。由于映射有很多情形,概括的說有四類： ①多對一; ②一對一;③多對多; ④一對多2映射定義一個映射函數(shù)f:X→Y是一個滿足下列兩個條件的關(guān)系：1.對每個x∈X，必存在y∈Y，使得(x,y)∈f2.對每個x∈X，僅存在一個y，使(x,y)∈f我們把y稱為x在映射f下的象把x稱為y的原象3映射表示方法表示映射的方法：1.f:X→Y2.X→Y3.Y=f(x)={f(x)|x∈X}實例

f：N→N,f(x)=2x是從N到N的函數(shù)

g：N→N,g(x)=2也是從N到N的函數(shù)f4例1X={x1,x2,x3}Y={y1,y2}F1={<x1,y1>,<x2,y2>,<x3,y2>}F2={<x1,y1>,<x1,y2>}F3={<x1,y2>,<x3,y2>}

F1是函數(shù),F2不是函數(shù),F3不是函數(shù)5例2R為實數(shù)的集合，X=Y=R，并設(shè)f={(x,y)|x,y∈R,y=x2}g={(x,y)|x,y∈R,y2=x}f是X到Y(jié)的映射g不是映射，違反唯一性6函數(shù)相等定義設(shè)F,G為函數(shù),則

F=G

F(x)=G(x)

如果兩個函數(shù)F和G相等,一定滿足下面兩個條件：

(1)D(F)=D(G)

(2)

x[x∈D(F)∧x∈D(G

)]都有F(x)=G(x)

實例函數(shù)

F(x)=(x2

1)/(x+1),G(x)=x

1

不相等,因為x=-1，F(xiàn)(-1)=0,G(-1)=-2.7函數(shù)的性質(zhì)定義設(shè)f：A→B,

（1）若R(f)=B,則稱f：A→B是滿射的.

（2）若任意x1，x2A

而且不相等，都有f(x1)與f(x2)不相等,則稱f：A→B是單射的.

（3）若f：A→B既是滿射又是單射的,則稱f：

A→B是雙射的（一一到上的）f

滿射意味著：

y

B,都存在x使得

f(x)=y.f單射意味著：f(x1)=f(x2)

x1=x28練習(xí)：例4判斷下面函數(shù)是否為單射,滿射,雙射的,為什么?

(1)f：R→R,f(x)=

x2+2x

1

(2)f：Z+→R,f(x)=lnx,Z+為正整數(shù)集

(3)f：R→Z,f(x)=

x

(4)f：R→R,f(x)=2x+1

(5)f：R+→R+,f(x)=(x2+1)/x,其中R+為正實數(shù)集.

9解(1)f：R→R,f(x)=

x2+2x

1

在x=1取得極大值0.既不單射也不滿射.

(2)f：Z+→R,f(x)=lnx

單調(diào)上升,是單射.但不滿射,ranf={ln1,ln2,…}.(3)f：R→Z,f(x)=

x

滿射,但不單射,例如f(1.5)=f(1.2)=1.

(4)f：R→R,f(x)=2x+1

滿射、單射、雙射,因為它是單調(diào)的并且ranf=R.

(5)f：R+→R+,f(x)=(x2+1)/x

有極小值f(1)=2.該函數(shù)既不單射也不滿射.

練習(xí)（續(xù)）10一一對應(yīng)定義：集合X和Y間，存在從X到Y(jié)上的雙射，則稱集合X和Y一一對應(yīng)。集合X和Y一一對應(yīng)，則：1.X中每個元素在Y中有唯一的象。2.X中不同元素的象各不相同。3.Y中每個元素在X上都有原象。11實例判斷從{a,b,c,d}到{1,2,3,4,5}是否一一對應(yīng)。f為：f(a)=4,f(b)=5,f(c)=1,f(d)=3不是一一對應(yīng)的關(guān)系。雖然是單射，但不是滿射。所以不是雙射。所以不是一一對應(yīng)的關(guān)系。12映射(函數(shù))的復(fù)合對關(guān)系而言，有關(guān)系的復(fù)合；函數(shù)是關(guān)系，所以函數(shù)也是可復(fù)合的。已知映射：f:X→Y，和g:Y→Z，由這兩個映射可構(gòu)成新映射：h，記為g?f,稱為f和g的復(fù)合映射。h=g?f=g(f(x)){(x,z)|

x∈X,

z∈Z,

y∈Y,y=f(x),z=g(y)}13映射(函數(shù))的復(fù)合例：X={x1,x2,x3},Y={y1,y2},Z={z1,z2}

f:X→Y，g:Y→Z，h=g?fx1x2x3y1y2z1z2注意g和f的位置14函數(shù)復(fù)合運算的性質(zhì)

定理

設(shè)f

：A→B,g

：B→C.

(1)如果g,f都是滿射的,則

g°f

：A→C也是滿射的.

(2)如果g,f

都是單射的,則g°f

：A→C也是單射的.

(3)如果g,f

都是雙射的,則g°f

：A→C也是雙射的.

15練習(xí)：1.下列哪些關(guān)系可以構(gòu)成函數(shù)？a.f={(x,y)|x,y∈N,x+y<10}b.f={(x,y)|x,y∈R,x2=y}2.判斷下列函數(shù)是單射、滿射或雙射？a.f:N→N,f(x)=x+2;b.f:N→N,f(x)=x(mod2);c.f:N→ρ(N),f(x)={x};不能能單射單射什么都不是16練習(xí)：3.已知：f:X→Y,g:Y→Z,h=g°f,f是滿射，h是單射，求證g是單射。17證明3：已知：f:X→Y,g:Y→Z,h=g°f,f是滿射，h是單射.求證g是單射。證：假設(shè)g不是單射，1.則存在y1≠y2,而g(y1)=g(y2)；2.而f是滿射，每個y都一定有對應(yīng)的x，所以對于y1和y2，必存在y1=f(x1),y2=f(x2)3.y1≠y2所以f(x1)≠f(x2)，所以x1≠x2;4.h(x1)=g(f(x1))=g(y1)h(x2)=g(f(x2))=g(y2)所以h(x1)=h(x2)對于不同的x，h函數(shù)具有相同值，顯然就不是單射了，與已知條件矛盾！所以原假設(shè)不成立！18逆函數(shù)(反函數(shù))對關(guān)系R來說，都存在逆關(guān)系；但是對映射(函數(shù))來說，不一定存在逆函數(shù)！需要依據(jù)一定的條件來判斷！19反函數(shù)存在的條件任給函數(shù)F,它的逆F

1不一定是函數(shù),是二元關(guān)系.實例：F={<a,b>,<c,b>}，F(xiàn)

1={<b,a>,<b,c>}判斷函數(shù)F的逆函數(shù)是否存在，則轉(zhuǎn)而判斷F是否是雙射函數(shù)。如果F是雙射函數(shù)，則存在逆函數(shù)。否則，不存在逆函數(shù)！20反函數(shù)的性質(zhì)定理

設(shè)f：A→B是雙射的,則f

1：B→A也是雙射函數(shù).

證因為f是函數(shù),所以f

1是關(guān)系,且

domf

1=ranf=B,ranf

1=domf

=A,

對于任意的y∈B=domf

1,假設(shè)有x1,x2∈A使得

<y,x1>∈f

1∧<y,x2>∈f

1成立,則由逆的定義有

<x1,y>∈f∧<x2,y>∈f根據(jù)f的單射性可得x1=x2,從而證明了f

1是函數(shù)，且是滿射的.下面證明f

1

的單射性.

若存在y1,y2∈B使得f

1(y1)=f

1(y2)=x,從而有

<y1,x>∈f

1∧<y2,x>∈f

1

<x,y1>∈f∧<x,y2>∈f

y1=y2

21反函數(shù)的性質(zhì)定理

設(shè)f：A→B是雙射的,則

f

1°f=IA,f°f

1=IB

對于雙射函數(shù)f：A→A,有

f

1°f=f°f

1=IA

22例題：構(gòu)造下列函數(shù)的反函數(shù)：1.f(x)=sinx2.f(x)=x2,x∈(-∞，0)3.A={1,2,3},B={a,b,c},f:A→B,f={(1,a),(2,c),(3,b)}23例題(續(xù))：1.f(x)=sinx

f-1(x)=arcsinx2.f(x)=x2,x∈(-∞，0)

f-1(x)=-x1/23.A={1,2,3},B={a,b,c},f:A→B,f={(1,a),(2,c),(3,b)}f-1={(a,1),(c,2),(b,3)}24函數(shù)復(fù)合與反函數(shù)的計算例設(shè)f：R→R,g：R→R

求f

g,g

f.如果f和g存在反函數(shù),求出它們的反函數(shù).

解

f：R→R不是雙射的,不存在反函數(shù).g：R→R是雙射的,它的反函數(shù)是g

1：R→R,g

1(x)=x

225由映射產(chǎn)生的等價關(guān)系定義： 設(shè)X,Y兩個集合，f是X到Y(jié)上的映射。若X中有2個元素x1和x2，f(x1)=f(x2),則x1和x2具有關(guān)系R，記為x1Rx2

?，F(xiàn)在檢驗關(guān)系R是否是等價關(guān)系：1）對于X中任意x，f(x)=f(x).自反性成立。2）若f(x1)=f(x2),則f(x2)=f(x1),對稱性。3）若f(x1)=f(x2),f(x2)=f(x3),則f(x1)=f(x3),滿足傳遞性。所以是一種等價關(guān)系！26由映射產(chǎn)生的等價關(guān)系因此，可以劃分出集合的等價類。集合X的等價類為：[x]={s|f(s)=f(x)}——具有相同y值的自變量構(gòu)成一個等價類。所以X的商集X/E={[x],[y],[z],…}[x][y]ab27由映射產(chǎn)生的等價關(guān)系例題：設(shè)S是由一群學(xué)生所組成的集合。對這群學(xué)生檢查發(fā)育情況，分為三個等級：優(yōu)、良、差。集合X={優(yōu),良,差}映射表示檢查狀態(tài)。對于集合S中，如果學(xué)生x1,x2，f(x1)=f(x2),則說明兩個學(xué)生發(fā)育狀態(tài)一樣。他們位于同一個等價類中。28規(guī)范映射設(shè)R是集合X到集合Y上的映射f產(chǎn)生的等價關(guān)系，映射g:X→X/R則是從集合X到商集X/R的規(guī)范映射。構(gòu)造規(guī)范映射的準則：g(x)=[x]29規(guī)范映射例：集合X={a,b,c,d},集合Y={0,1,2,3,4},映射f:X→Y是：f(a)=1,f(b)=0,f(c)=1,f(d)=31)由f產(chǎn)生的等價關(guān)系R為：

R={(a,a),(b,b),(c,c),(d,d),(a,c),(c,a)}2)對應(yīng)等價類：[a]={a,c},[b]=,[d]=s2xg2y03)商集：{[a],[b],[d]}4)規(guī)范映射g:g:X→X/Rg(a)=[a],g(c)=[a],g(b)=[b],g(d)=[d]30練習(xí)：已知x={a,b,c},Y={1,2,3,4}f:X→Y如圖所示,試構(gòu)造函數(shù)g:Y→X,使得g·f=Ixabc1234g={(1,a),(2,c),(3,b),(4,a)}315-2無限集可用1-1對應(yīng)法則討論無限集的勢1638，Galilo(意)指出：對于每個自然數(shù)，都有且只有一個平方數(shù)與之對應(yīng)1，2，3，4，……，，……1，4，9，16，……，，……類似地，自然數(shù)與奇數(shù)、與偶數(shù)、與整數(shù)之間均可1-1對應(yīng)，因而等勢

32等勢定義：當(dāng)且僅當(dāng)集合A的元素和集合B的元素之間一一對應(yīng)。集合A和B就是等勢的，記為A~B。例如：f(n)=2n,n為自然數(shù)。則自然數(shù)和偶數(shù)之間可以建立一一對應(yīng)的關(guān)系。所以自然數(shù)和偶數(shù)之間就是等勢的。33等勢所以，如果A,B是任意集合1.如果存在A到B的雙射，則A,B等勢。|A|=|B|2.如果存在A到B的單射，|A|≤|B|。3.如果存在A到B的單射，但不存在雙射函數(shù)，|A|<|B|。34集合的勢勢是衡量集合大小的一個量對于有限集，可有兩種方法知道集合的大小“數(shù)數(shù)”——一個一個地數(shù)。個數(shù)即勢（也稱基數(shù)）與已知集合比較——1-1對應(yīng)的方法35Hilbert旅館一旅店有無窮多個房間，各房間編號依次為

#1，#2，#3，……現(xiàn)所有房間已住滿了人。這時來了一位新客人要求住店。怎么安排？

店主人把#1房的客人移到#2房，把#2房的客人移到#3房，依此類推，新客人就住進了已騰空的#1房間

接著，又來了第二位新客人，旅店主也照此辦理，使第二位客人得到落實

緊接著，來了一個有無限多個游客的旅游團要求定住房間，怎么辦

？

36店主人把#1房的客人移到#2房，把#2房的客人移到#4房，#3房的客人移到#6房，等等，所有奇數(shù)號的房間全部騰空了，新的無限多個客人就全住進了旅店

緊接著發(fā)生了更為嚴重