离散数学电子教材

第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是