第4章映射（函數）

映射（函數）是一個基本的數學概念，它是一個特殊的二元關系，我們可以把映射看作

輸入輸出關系，它把一個集合（輸入集合）的元素變成另一個集合（輸出集合）的元素。例

如，計算機中的程序可以把?定范圍內的任?組數據變化成另一組數據，它就是?個映射。

映射的概念經常出現在開關理論、自動機理論和可計算理論等領域中，在計算機科學中

有著廣泛的應用。

4.1映射（函數）的概念

考慮下面幾個由圖4-1所示的集合x到集合y的關系。

圖4-1

在這6個關系中，后4個關系凡，為,凡與與，R?不同，它們都有下面兩

個特點：

(1)其定義域為X；

(2)x中任一元素。對應唯一一個y中的元素〃。

我們稱具有這樣兩個特征的關系為映射(函數)。

定義4.1」設x,y是兩個任意的集合，而/是x到y的一個關系，若對每一個

XGX,都存在一個唯一的,，￡丫，使得",)，)￡/,則稱關系/為x到y的映射

(Mapping),記作

/：X—y或

若〈無,)?￡/,則稱A?為自變量(IndependentVariable),稱y為映射/在/處的值(或

像(Image)),￡/亦可記作y=/(x),/的值域ran/q丫，有時也記為R”即

R/={y|yw丫△(Hr)(xeX.\y=/(%)))

或記為

f(X)={f(x)\xEX}

集合Y稱為/的共域，R}亦稱為映射f的像集合。對于A之X,稱/(A)為A的像(Image

ofA),定義為

/(A)={,f(x)\xeA)={.y|3x(x￡A/\y=/(x))}

顯然，，/S)=。"({?)={/(x)}(xeX),

映射f是x到y的特殊的二元關系，其特殊性在于：

(1)dom/=X,即關系/的前域是X本身，而不是X的真子集。

(2)若則映射/在x處的值)，是唯一的，即

〈x，y〉w『A〈x,z)￡/ny=z

例4.1.1設乂={?b,c,d},y={1,2,3,4,5}，且有/={〈41〉,低3〉,化4〉,a4〉},

求dom于、&和/(x)o

解dom/=X={aybyC.d]

ran/={1,3,4)

/3)=1J?=3J(c)=4"(d)=4

例4.1.2判別下列關系中哪個構成映射。

(1)/={"由底/?}

(2)/={(x2,^|xe/?}

(3)/={(%),x2)|x1,x2G+X2<10)

(4)/={(x1,x2^|x1,x2G+X2=10)

(5)/={(xpx2)|x,x2GN,x2為小于再的素數個數}

⑹/={(x,y〉k，y￡R，kl=y}

⑺f={{x9y)\x,yGR]y\=x]

⑻f={〈x,?k，y￡R,|X=M

解(1)構成映射。

(2)(X2,X)G/,(X2,-X)G/,即值y不唯一，故不構成映射。

(3)因為芭不能取定義域中所有的值，且內對應很多勺，故不構成映射。

(4)因為凡不能取定義域中所有的值，故不構成映射。

(5)構成映射。

(6)構成映射。

(7)因為對X/xwA,值y不唯一，故不構成映射。

(8)因為對VXER,值y不唯一，故不構成映射。

例4.1.3下列集合中，哪些是映射？并求映射的定義域和值域。

(1)號={{1,〈2,3》,〈2,〈3,4》,〈3,〈1,4》,〈4,〈1,4》)

(2)§2={〈1,〈2,3》,〈2,〈3,4》,〈3,〈3,2》}

(3)S3={{1,〈2,3》,〈1,〈2,4》,〈2,〈3,4》}

(4)邑={{1,〈2,31,〈2,〈2,3》,(3,〈2,3》}

解(1)是映射。don，一{1,2,3,4},代={。，4〉，〈2,3〉,〈3,4)}

(2)是映射。dom邑={1,2,3},《={{2,3〉,〈3,2〉,〈3,4)}

(3)不是映射。

(4)是映射。domS4={1,2,3),&={{2,3)}

請注意區別X的像和{?的像兩個不同的概念。X的像/(幻￡丫，而像/({燈)￡丫。

關于像有下列性質：

定理4.1.1設/為犬到丫映射，對任意4=X,8=X,有

(1)/(AJB)=/M)U/(B)；

(2)

(3)/(A)-/(B)c/(A-Z?)o

證明(1)對任一ycY,

y￡/(AUB)o3A((XeA(JB)八()，=/(⑼)

o3x(((xeA)v(xeB))A(y=/(%)))

o3x(((xeA)A(y=/(x)))v((xGB)A(J=/0))))

<=>3X((A￡A)A()，=/(x)))vBx((xwB)A(y=/*)))

O()，E/(A))V()，E/(3))

=)，￡/(A)J/(8)

因此，/(AUB)=/(A)U/(B)o

(2)、(3)的證明請讀者完成。

注意：(2)、(3)中的“q”不能用“二”代替。下面我們舉例說明。

例4.1.4設X={a,b,c,d},7={1,2,3,4,5},f：如圖4-2所示。那么,

/(⑷)={2}

/({如={2}

/(⑷)。/({勿)={2}

f({a}-{b})=f[{a})={2}

f({aY{/.})(=/({?})/({〃})

圖42例4.1.4圖

由于映射歸結為關系，因而映射的表示及運算可歸結為集合的表示及運算，映射的相等

的概念、包含概念，也使歸結為關系相等的概念及包含概念。

定義4.1.2設/：A-g：CfD,如果A=C,B=D,且對于所有xwA,

有/(x)=g*)，則稱映射/和g相等，記作/=g。如果4工C,B=D,且對于所有

xeA,有/(x)=g(x),則稱映射/包含于g,記作了qg。

事實上，當不強調映射是定義在哪個集合上的時候，由于映射是序偶的集合(特殊的美

系)，所以g的充分必要條件是/ag且ga/。

從映射的定義可以知道XxY的子集并不能都成為X到Y的映射。

例如,設x={4,瓦c},r={O,l},Xxy={〈a,O),他0〉,(40〉,〈刊,他

XXy有26個可能的子集，但其中只有23個子集為從X到Y的映射：

f0=K〃，O)，S，O〉,〈cO)}?ft=?〃,0)，8,0〉G，l)}

f2={-0),—,力={{o,0},—1)}

h={伍1〉,9,O〉,〈C,O〉}，力={.」〉,伍,0〉,〈c,l)}

-={-1),—0)}，-={{訓,/

同理可知，從y到x可定義32個不同的映射:

go={1),〃》,“〃〉},.={{0,我〈1,硼,g2={〈0M〉，〈Lc)}，

g3={〈0,—a?,g4={(0M，M)},gs={{O,b),(\,c)}

g6={〈0,c〉,〈lM)},g7={{0,c〉，M)},g8={{0,c)，M?

一般地，設x和y都為有限集，分別有〃7和〃個不同元素，由于從x到y任意一個映

射的定義域是x,在這些映射中每一個恰有〃?個序偶。另外任何元素XEX,可以有丫的

〃個元素中的任何一個作為它的像，故共有個不同的映射。在上例中|x|二3,|y|=2,故

從x到y有23個不同的映射，從y到x有3?個不同的映射。今后我們用符號YX表示從x

到y的所有映射的集合，甚至當x和y是無限集時，也用這個符號，即

Yx={f\f:X^Y}

則有卜x|=|r||x|。特別地人八表示集合A上映射的全體。

習題4.1

1.指出下列各關系是否為x到y的函數：

(1)X=Y=N,R={(x,y)\(xGX)A(yGK)A(X+y<100))

?3

(2)X=y=R(實數集)，S={(x,>)|(xGX)A(y€y)A(,y=x)}

(3)X={l,2,3,4},Y=XxX,?={“(2,3》,〈2,〈3,4〉,(3,〈1,41,〈4,〈2,3》}

(4)設X={a,b},y={l,2,3},4={伍1),僅,2)},&={〈訓,他,1〉},

.={曰1〉,伍2》,&={(63?。

2.設/：X-y,g：xfy,求證：

(i)/Cg為Y到y的函數當日僅當/=g.

(2)為x到y的函數當且僅當f=g。

3.設/={〈。,{。,{。}}〉,〈{。},。)}為一函數，計算/(。)，/({。})，/(處,{。}})。

4.設X={a,b,c,d},Y={l,2,3,4},/：XTY為:/={?,1〉,仇3),化1〉,54)},

求

/({a})，f[{a,b}),/({a,)c}),/({〃,〃,c,d})。

4.2特殊映射

定義4.2.1設/：X-y,

(1)如果ran/=y,即丫的每一個元素都是X中一個或多個元素的像，則稱這個映

射為滿射(Surjection)(或到上映射)。

(2)如果對于任意￡X,若占=X2，則有f(X|)。/(工2)，則稱這個映射為入

射(Injection)(或單射，

(3)若/既是滿射又是入射，則稱/是雙射(Bijection)。雙射也稱為1—1對應(One

ToOneMapping)o

由定義不難看出，如果/：XfY是滿射，則對于任意ye丫，必存在xwX,使得

/(x)=y成立；如果力XfY是入射，則X中沒有兩個不同元素有相同的像，即對于任

意f(x])=f(x2)=>xl=x2o

圖4-3說明了這三類映射之間的關系。注意，既非單射又非滿射的函數是大量存在的。

圖4-3

例4.2.1(1)設1={。,反。,。},5={1,2,3},如果定義為

/(a)=1JS)=1J(c)=3,/(d)=2

則/是滿射的。

(2)/：｛%,)，｝一｛1,3,5｝定義為/(x)=lj(y)=5,則這個函數是入射，但不是滿射。

(3)令句表示實數的閉區間，ma,h]={x\a<x<b],f伍,以定義為:

f(x)=(b-a)x+a

則這個映射是雙射。

例4.2.2在圖4-4中,(。)、(c)是滿射，S)、(c)是入射,(c)是雙射。

例4.2.3設N是自然數集，下列映射哪些是滿射、入射、雙射。

(1)/：NTN，/(/)=r+2。

N->N,/(J)=7(mod3)o

/⑺二I，為奇數

(3)ftNTN,=y(mod2)

j為偶數

⑷f：Nf{0,1}，/(/)=,；/為奇數

./為偶數

⑸/：NTR,f(j)=log10j

(6)/：RfR,/(J)=/+2J-15=(J+1)2-16O

,,:

(7)f：N?fN,f(n}yn2)=n]

解：(1)入射。

(2)一般映射(既非滿射，也非入射)。

(3)一般映射(既非滿射，也非入射)。

(4)滿射。

(5)不是映射，f(0)無定義。

(6)一般映射(既非滿射,也非入射)。

(7)不是映射，/(0,0)無定義。

定理4.2.1令x和y為有限集，若x和y的元素個數相同，即|x|=|y|,則

/：Xfy是入射的，當且僅當它是一個滿射。

證明(1)若/是入射，則|/(X)|=|X|二M。從/的定義我們有/(X)qy,而

|/(x)|=|y|,因為盟是有限的，故/(x)=y,因此，/是一個滿射。

⑵若/是一個滿射，則/(x)=y，于是|x|=|H=|/(x)|。因為|x|=|/(x)|和兇

是有限的，所以，/是一個入射。

這個定理必須在有限集情況下才能成立，在無限集上不一定有效，如/：/->/,這里

fM=2x,在這種情況下整數映射到偶數，顯然這是一個入射，但不是滿射。

另外，還有兩個特殊而又重要的映射一常映射和恒等映射。

定義4.2.2(1)設/：X-八如果存在。￡丫，使得對所有的xwX都有/(x)=c,

即/(X)={c},則稱/：XfX是常映射。

(2)任意集合X上的恒等關系//為一映射，常稱為恒等映射，因為對任意x$X都

有(X)=X,即

Ix={(j;,jr)|xGX}o

對任意內。“2，有人($)。及(工2)，故4是入射；且=X，&是滿射。所以，

Ix是雙射。

習題4.2

1.設Z+，Z,R,C分別表示正整數集、整數集、實數集、復數集，試指出下列映射中哪些是

單射、滿射、雙射，并寫出定義域和值域。

⑴f:ZfZ+為/*)=[2乂+1。

(2)f:RfR為f(x)=cosxo

(3)):R-為/(x)=sin/。

(4)f:0,-^-為/(x)=cosx。

（5）.:[0,司一>[-1,1]為/（x）=sinxo

（6）f:CiC為以z）=e&z（其中。為一常數）,

2.下列關系中哪些能構成映射？。

（1）{<玉,々>|不￡￡乂,川+蒼<10}，其中N為自然數集。

（2）{<%%>1%）’2￡凡必=>'；},其中/?為實數集。

（3）卜如必>IX，）’2￡凡￡=x}，其中R為實數集。

3.下列集合能定義成映射嗎？如能，試求出它們的定義域及值域。

（1）{<1,<2,3?,<2,<3,4?,<3,<1,4?,<4,<1,4?}。

（2）{<1,<2,3?,<2,<3,4?,<3,<3,2?}0

（3）{<1,<2,3?,<2,<3,4?,<1,<2,4?）。

（4）{<1,<2,3?,<3,<2,3?）

4.設映射/:A->4,這里A={-l,0,l}2,B={-2,-l,0,l,2}

0XjX,>0

J

（1）/定義了何種關系？

（2）/的值域是什么？

（3）有多少與/具有同樣定義域和陪域的不同映射？。

（4）設/：xfy的映射且x=。，問/可能是單射嗎？可能是雙射嗎？

（5）證明存在一個從X到P（X）的單射，其中X為任意集合。

（6）設x與y均是有限集且x有，〃個元素，丫有〃個元素，說明下列斷言為真時，〃?

和〃必須成立的關系：

1）存在從x到y的單射。

2）存在從x到y的滿射。

3）存在從x到y的雙射。

4.3復合映射和逆映射

4.3.1復合映射

因為映射是一種特殊的關系，所以和關系一樣也有復合運算。

定義4.3.1設映射￡X-V,g：W-Z,若/(X)qW,則

g/=((X,Z)|XGXAZGZA(3jO(yeyAy=/(x)Az=1§(jO))

稱g在映射/的左邊可復合。

對于映射的復合我們有下面的定理：

定理4.3.1設/：X-y,g：WfZ,g在映射了的左邊可復合，即/(X)qW,

則g/是一個XfZ映射。

證明(1)對于任意xwX,因為/為映射，故必有唯一的序偶〈X,)，)，使y=/(x)

成立，而/(x)G/(X)即/*)￡W,又因為g是映射，故必有唯一序偶〈)，,z)，使z=g(y)

成立，根據復合定義，〈4z〉eg/,即X中每個x對應Z中某個z。

(2)假定g/中包含序偶和〈x,Z2”這樣在/中必存在))和乃，使得在/中

有〈X，X〉和〈乂為)，在g中有〈)*4〉和因為了是一個映射，故y=>2；又因為

g是一個映射，故Z]=Z2，即每個X￡X只能有唯一的〈X,Z〉6gfo

由(1)、(2)可知g/是一個映射。

在定義4.3.1中，當w=y時，則映射

gf={(X,z)|^GXAZGZA(3.y)(y￡yA)=f(x)AZ=g(y))}

稱為映射了與映射g的復合映射，或稱g/為g對/的左復合。

注意：在定義4.3.1中，假定ran/qdomg,如果不滿足這個條件，則定義g/為

空。

根據復合映射的定義，顯然有g/(%)=(?(/?)O

例4.3.1設乂={1,2,3,4},丫={1,2,3,4,5},2={1,2,3}。

f：X-八/={〈1,2〉,〈2,1〉,〈3,3〉,〈4,5)}

g：y-Z,且={(1,1),〈2,2〉,〈3,3〉,〈4,3〉,〈5,2)}

求gf。

解g/={(1,2),(2,1),(3,3),<4,2))

例4.3.2設7,g均為實函數，/*)=2x+l,g(x)=f+1。求/g,gftfft

gg。

解fg(x)=2(Y+i)+i=2/+3

gf(x)=(2A:+1)24-1=4x2+4x+2

f/(x)=2(2x+1)+1=4x4-3

gg(x)=(x2+1)2+1=x4+2x2+2

所以

f且={1,2_?+3),￡氏}

gf={(x,4x2+4X+2^|XGR]

f/={(X,4X+3)|XG/?}

gg={(x,x4+2x2+2^|xeR]

定理4.3.2設g/是一個復合映射。

(1)若/和g是滿射，則g/是滿射。

(2)若/和g是入射，則g/是入射。

(3)若/和g是雙射，則g/是雙射。

證明給定集合x,y,z,/：xfy,g：yfz,

(1)Vz￡Z,因為g是滿射，故小wy,使得g(y)=z；又因為/是滿射，故土wX,

使得/(x)=y.所以，

gfM=g(/(x))=g(y)=z

即XZzwZ,3XGX,使得gf(x)=zo因此，R-=Z,g/是滿射。

(2)對玉工馬，因為/是入射.，故/(石)工/(々)；又因為g是入射，

故g(/a))w8(/(/))，于是

X尸占ngf*2)

所以，g/是入射。

(3)因為/和g是雙射，根據(1)和(2),g/為滿射和入射，即g/是雙射。

定理4.3.3設g/是一個復合映射。

(1)若g/是滿射，則g是滿射。

(2)若g/是入射，則/是入射。

(3)若g/是雙射，則g是滿射，/是入射。

證明設/：X-y,g：yfz,gftx->Zo

(l)因為g/是滿射，則&f=Z,VZEZ,玉￡X,使g/(x)=z,故寺￡丫

使得y=/(x)，z=g(y),可見，R&=Z,所以g是滿射。

(2)設司,工2wX且%工%。因為g/是入射，故gfM?即

g(/(xJ)wg(/(X2))，因為g是一個映射,則/(占)工/(工2),即

內工工2=>/(內)。/*2)

所以，/是入射。

(3)g/是雙射，則g/是滿射且是入射。g/是滿射，由(1)可知g是滿射;

g7是入射，由(2)可知/是入射。

由于映射的復合仍然是一個映射、故可求三個以上映射的復合。

例4.3.3設R為實數集合，對XER,有f(x)=x+2,g(x)=x-2,/?(x)=3x

求g于，hg，(hg)f與h(gf)。

解：8。/={。㈤底可，

hg=((X,3(X-2))|XG/?}

@g)f={(x93x)\xeR)

h(gf)={(x93x)\xER]

所以有

h(gf)=(hg)f

一般地，有如下定理。

定理4.3.4設有函數/：x-y,g：yfz和加zfw,則有

h(g/)=(〃g)f

證明這可由關系的復合的可結合性得出，這里我們直接由映射相等的定義證明。

首先〃(g/)和(〃g)/都是X到W的函數。另外對任一xcX，有

〃(g/)1)=〃((g/)。))=/?(g(/。)))

=hg(f(x))=(hg)f(x)

由元素x的任意性，有

h(g/)=(〃g)f

由此可見，映射的復合運算滿足結合律，因此多個映射復合時可去掉括號，對3個映射

的復合即有

h(g，f)=(hg)f=hgfo

若有了：XfX,則//仍為X到X的映射，簡記為尸，一般地

ff…/簡記為顯然

II

/°(x)=Zx(x)=x

\r+,u)=/(r?)

注意：映射的復合運算不滿足交換律。

例4.3.4⑴設X={1,2,3},

/：X->X,/={(1,2〉,〈2,2〉,〈3,1)},

g：XTX,g={(l,2〉,〈2,l〉,(3,3〉},

則

f8={。,2〉,〈2,2〉,〈3,1)}。

所以

gf*/8。

映射的復合運算還有如下明顯的性質：

定理4.3.5設映射/：Xfy,則/=fIX=IYf.

證明對Vx￡X,VyEY,有4(x)=x，4。)二)、則

(/o/x)(X)=/(/x(A))=/(X)

出，/)(x)=/r(/(x))=/(x)

所以，

f=f/Y=Af

當x=y時，有

f=f1x=Ixf

4.3.2逆映射

在關系的定義中曾提到，從x到y的關系R,其逆關系是y到x的關系，

〈乂加內=(工,加A

但是，對于映射就不能用簡單的交換序偶的元素而得到逆映射，這是因為若有映射

/：x—y,但/的值域學可能只是y的一個真子集：即Rruy,此時，

dom廣\=RfuY,這不符合映射對定義域的要求。此外，若X—^丫的映射是多對一

的，即有〈%,)?￡/,小,))￡/,不工9,其逆關系將有尸，3幻《尸,％

這就違反了映射值唯一性的要求。為此，有如下定理：

定理4.3.6設/：xfy是一個雙射，那么/T是y—x的雙射。

證明設/={a，y〉k￡XA)，wy/\y=/(x)},廣={(y,必(x,

因為/是滿射，故對每一)，￡丫，必存在〈％》￡了,所以，即/T的前域為

y。又因為/是入射，對每一個恰有一個xwx,使〈工?白了，即僅有一個“ex,

使(y，4s/T,y對應唯一的X,故/"是映射。

因為ran=domf=X,所以，是滿射。

又設丁產月時，有尸(兇)=尸(52)，令廣(x)=x，尸(%)=/，則玉=/，故

/(x,)=/(x2),即％=%,與假設矛盾,所以/即/T是單射。

因此，/T是一個雙射。

定義4.3.2設/：Xfy是一雙射，稱yfx的雙射廣?為/的逆映射，記作廣二

例如，設乂=｛0,1,2｝,丫=｛她?°若f：XfY為:

/={{0,0,。,孫(2,胡,

則有尸：yfX,/-'=｛伍1〉,他,2〉,化0)｝。

/={(0,。,。,心2,必,

則/的逆關系2),(c,o)}

就不是一個函數。

再如，/：RfR,/(X)=X3-2,則廣|(幻=炳5。

函數的逆具有下面一些重要性質。

定理4.3.7如果映射力xfy有逆映射/-,：yfx,則f=ixf

frl=iyo

證明因為力xfy是雙射，所以yfx也是雙射。由定理4.3.2知,

/：Xfx和//-,：yfy都是雙射。

任取X￡X,ycy,若/0)=)，，廣(y)=x,貝！

(/-'。f)(x)=(/*))=f-\y)=x

(/r')(y)=/(r,(y))=/W=y

所以,

r'o/=/x；

定理4.3.8若/:Xfy是雙射，則=/0

證明因/：xfy是雙射，/-,：y—x也是雙射，因此，(/-1)-1：x->y是雙射

O由于

domf=dom(/')-1=X

(x,y)e(/-')-'=(y,x)e尸=y)e/

所以，(f\7=f。

定理4.3.9若f：x->y,g：yfz均為雙射，則(g/)-=yg，

證明(1)因/：x-y,g：yfz均為雙射.故廣1和gT均存在，且

/■'：yfx,g?zfy均為雙射，所以，,尸屋：zfx為雙射。

根據定理4.3.2,gftXfZ是雙射，故(g/)-'：Z-X是雙射，且

dom(廣g—)=doni(gf)~]=Z

(2)對任意zwZ=存在唯一yw丫，使得g(y)=z

=存在唯一xwX,使得/*)=y

故

(/-'gT)(z)=/T(gT(z))=/i(y)=x

又

(g-=g(/(x))=g(y)=z

故

Uo/)-'(Z)=X

因此，對任一Z￡Z有：(g/)T(Z)=(尸g”(Z)

由(1)、(2)可知

/■'g7=(g/)■,-

例4.列5設乂={0=2},丫={。ec},Z={a/,力，若有X-Y,g：YfZ,

其中，/={。,。,〈2,公(3力)}超={伍力佃0,化。〉},求8f)T和尸gj

解gL，GM，(3])},(g/尸={31〉,〈￡,3),仇2)}

={〈c,l),〈a,2)，8,3?,底={(a,c),偽⑼,仇a〉}

廣'晨={31),〈四3〉,仇2)}

可見，

(g/)-，=gT

習題4.3

1.證明或反駁下列命題：

(1)設BuAuX,/:X-丫為任一映射，則/(A-B)=/(A)-/(B),其中

f(A)={y\y=f(x),x^A},f(B)={y\y=f(x),XEB],

f(A-B)={y\y=f(x\xeA-B)。

(2)/:X->y是雙射，當且僅當對X中任兩個子集A與8,若A\B=。,則

〃A)rv(B)=。。

0)設/：x-y,x,y均為有限集且|x|=|y|,則下列命題等價：

①/是單射；②/是滿射；③/是可逆的。

2.設fR為〃外二/-2,其中R為實數集，試求了”。

3.證明從Xxy到yxx存在單射，并說明此映射是否為滿射。

4.設*={1,2,3,4}。

(1)試定義映射/：xfX使/，及且是單射。

(2)求//,/f\f'\f廣。

(3)能否找到另一gw/*的單射g:X->X,有gg=G?

(4)試定義一個映射/:XfX使72=/且/工4。

(5)試定義一個映射/:XfX使/7=/且/工〃。

5.求下列各映射的逆映射：

⑴/：/?->/?,/(X)=X;

13r1

(2)f/(x)=—+—；

4424

⑶于：RTR,于(x)=x—2；

⑷/:RfRJ3=2".

6.如果N為｛0,1,2,｝且

f:NfN為/(〃)=〃+1；

g:NTN為g(〃)=2n；

0〃為偶數

h:NfN為〃(〃)=?

1〃為奇數

試求/f，fg，gf，gh，hg，Qfg)h,

7.設/:X-X,g:XfX為任意兩個映射，證明

(I)如果g不是滿射，則g/也不是滿射。

(2)如果/不是單射，則g/也不是單射。

(3)如果/為滿射，f/=/,則/=/x。

4.4置換

定義4.4.1設X=(x,,x2,...,xJ,雙射/：XfX稱為集合X的置換

(Permutation),記作

p：XfX

這里，X中元素的個數|x|稱作置換的階。

定理4.4.1在〃個元素的集合中，不同的〃階置換的總數為，2！個。

,XxX,…X,

證明形如：p='723"

p(X)p(x2)〃(天)…PQJ

中的P(X[),P(W)，P*3)，…，P(X”)可以取為，/，0一、””的任意一個全排列，故總數為〃！

個。

定義4.4.2給定X={X]，z，,當}，恒等映射/x(x):XfX稱為集合X上的恒

等置換(IdenticalPermutation),記作

Fx,x2x3…X；

lx=

王X?工3--七

定義4.4.3設〃是集合乂=｛內,工2,…,x"的置換，如果可以取到X的元素

工;,E,…H（1w廠《〃），使“（X）=名,p（X）=X,p（%_i）=%,p（x；）=X，且x的其

余元素（如果還有的話）不變，則稱〃為一個輪換，記為（X；乂吊）。

若X=｛為,工2，七｝,則X的6個置換

都是輪換，它們分別記為（％）,（西犬2），（9了3），

（丹七），（石工2工3）和（司工3沏）。當X=｛X1,X,,X3，Z｝時，置換~不是輪換。

々X]/七_

一般地，|X|W3時，X的置換都是輪換：|X|>3時，X的置換未必是輪換。

定義4.4.4把置換看作定義在集合乂=｛為,々,，后｝上的雙射，置換的復合定義為

相應映射復合構成的置換，

234234一

例如,Pi=

3124一4321

1234-1234-

則P1“2=P，=

42I31|_2431

可見，Plp2Hp2〃|。

兩個輪換（44丸）與（X力x-2-Xj）的復合記為：.X.）（V，x.）o

定義4.4.5給定X=｛xpx2,-,xj,對任意的〃階置換

p=

p(%)p(&)p(x3)…p(xn)

記

,|「P*|)〃(/)〃(為)…P(%)-

P=

Lf毛形…x“j

容易驗證

PPl=P1P=【X

我們稱［尸為P的逆置換,

集合X={為,々，，%}上的所有〃階置換的全體記作S”。

置換的復合有以下性質：

(1)S“對于復合運算是封閉的：

(2)結合律成立,S3Vp-,/?-,pkeSn,有Mp)Pk=PiWpj；

(3)S”中有一個元素稱為恒等置換，使對任意〃eS〃有〃1=1p=p?,

(4)任意〃￡S”，都存在有逆置換/尸，使pTP=P［尸=I。

習題4.4

1.若乂={1,2,3},試寫出X上的全部置換，并指出各置換的逆。

2.設乂={1,2,3,4},P1,〃2，P3是X上的置換，

1234~|「1234"1234-

，p,—P、—，

2413-3421_2413_

求PiPi，PiP\,Pi用，2P；及P；。

1231231「123-

3.已知P[=

312132j-|_213_

請驗證：3〃2)〃3=Pl(P2“3)。

4.設A={1,2,3,4},計算(123)(234)(14)(23).

5.設4={1,2,3,4,5,6},A上的置換/=(1234),g=(134)(25)。求

(1)r1；

⑵fg廣。

*4.5特征函數

有些映射與集合之間可以建立■些特殊的關系，借助于這些映射，可對集合進行運算。

定義4.5.1令E是全集，A^E,rtl

1XGA

〃八⑴二3'A

0x^A

定義的映射〃足￡-?（0,1）,稱為集合4的特征函數（Eigen-function）。

定理4.5.1給定全集E,且A7E,B=E,對于所有XWE,特征函數有如下一

些性質。

（1）.A（"）=00A=0

（2）y/A（x）=1<=>A=E

（3）A^B

（4）匕i（x）=〃8（x）oA=8

（5）〃*'（_￥）=〃八（x）x〃8（x）

（6）〃A8（X）="八（X）+“8（X）一杯A8（X）

（7）〃彳（x）=l-〃式x）

（8）心4）=*=8（外

證明：（1）、（2）、17）顯然。

（3）若4口6,則對Vxwf,當xwA時，必有xwB,即〃八（x）=l,=\,

可見,材A（X）W〃8（X）；當時，則外"）=0,故也有”,a（x）W〃B（X）。

若勿4（x）W“8（x），即8A（"）=1時，WB（X）=\，亦即XEA時必有所以，

Aq8。

（4）若A=B,即且

由（3）得匕1a且工（工）《“八（幻，所以，“八（x）=%（x）。

若憶（.X）="3（X）,則”A（.E）=1時，勿6。）=1,即xwA時必有xeA,故A墨A：

四八（x）=0時，吠8（尤）=°，即x紀A時必有五后8,則xwB時必有xwA,即8口4。

所以，A=BO

（5）i//AAx）=l=xw4rB<=>xeA/\xeB<^>y/A（x）=1且〃.x）=1

所以“A8")="A*)X九")

(6)有以下三種可能：

1)xwA且xwB,則匕|(x)=l,-85)=1，〃43")=1，所以，

WA8(%)=——幻+%。)一68*)=1；

2)且x促3,則xeAB,y/A(x)=1,=0,i//A8(x)=0,所以，

6?M=y/A(x)+y/R(X)-4(B(x)=1；

3)x任A且xwB,則x《AB,i//A(x)=0,y/H(x)=1,i//Aw(x)=0,所以，

W八￡幻=〃式外+心*)，AQ)=l。

4JBox任A八x壬B=x任AB,則匕|(N)=0,i///f(x)=0,〃八&(x)=0,

所以，

WA￡X)=VG(X)+〃￡X)-〃八-3=0。

綜上所述，

少AB(X)="A(X)+/8(X)-3A8(X)。

(8)由于A-3=AQA,則

匕i(x)=w&(X)X%(x)=l//A(x)x(l-"8(x))

="A(x)-")x1//H(x)=WA(X)-y/A?(x)

應用特征函數的一些性質，也可以證明一些集合恒等式。

例4.5.1試證明:

(1)A=A

(2)A(BC)=(A8)一(AC)

證明(1)因為^]")=1-”式幻二1一(1一匕4。))=〃.(外，所以，A=A.

⑵WA(BC)W=^WX^CM

=W,\(x)XWB(X)+Wc(x)-wBc(x))

=勿A(x)x心(x)+少4(/)xWc(X)-外(幻x，川c(X)

="AM(X)+“ACW-^A(BC)(X)

=-Al(X)+〃AC(X)一〃(A?)(A。(工)

二匕A5)(AC)(X)

所以，

A((B\JC)=(A3)U(AC)o

例4.5.2設￡=c},E的子集是：0{a},{b},{<?},{〃,6},{a,c},{b,c}和

{aM,試給出七的所有子集的特征函數且建立特征函數與二進制之間的對應關系。

解：E的任何子集A的特征函數的值由表4T列出。

表4-1E的任何子集A的特征函數的值

A

。{b}{c}{〃，圻{a,c]屹,c}{〃,方?

a、01001101

b00101011

c00010111

如果規定元素的次序為a,b,c,則每個子集A的特征函數與一個三位二進制數相對應。

如%*ci*)61°1。令8={000,001,010,011,100,101/10,111},那么表4-1亦可看作從

E的募集到B的一個雙射。

習題4.5

1.設S=(AQ8)(AC)(BC),其中A8,C是