第5 章
函 数
函数是一种特殊的关系,也称为映射,它在计算机科学与技术以及相关学科中有重要
的作用和广泛的应用。
函数概念的来源可以一直追溯到意大利物理学家、天文学家和哲学家伽利略(Galileo 
Galilei,1564—1642)。而最初开始使用函数一词的是德国哲学家和数学家莱布尼茨
(G.W.Leibniz,1646—1716),用以描述曲线的一个相关量。中文的“函数”一词由清朝数
学家李善兰(1811—1882)译出。
本章主要介绍函数的定义、几种特殊函数及相关性质、函数的运算以及常用的函数。
5.1 函数的定义
定义5.1 设f 为集合A 到B 的二元关系。若对于任意x∈Dom(f)都存在唯一的
y∈Ran(f)使得(x,y)∈f 成立,则称f 为函数(function),此时记y=f(x),称x 为自
变量(argument),y 为f 在x 的值(value)或x 在f 作用下的像(image)。函数也称为映射

144
离散数学及应用(第
3 
版)

(maig) tasomain)。

ppn或变换(rnfrto

xn 
)。
注:A=A1×A2×…×An 
时,一般也将f((x1,x2,…,xn 
))简记为f(x1,x2,…, 

函数的概念如图5.

1所示
。
【例5.1,2,4,3,5,


1】R1={(1),(3),(1),(5),(3)}
是函数;而R2={(1,1),(1,3),(4,1),(3,5),(5,3)}不是
函数,因为R2(1)={1,3}。

在函数R1 中,R1(1)=1,R1(2)=3,R1(4)=1, 
R1(3)=5,R1(5)=3,于是R1 也可以写作R1={(1, 图5.

1 函数的概念

R1(1)),(2,R1(2)),(4,R1(4)),(3,R1(3)),(5, 

R1(5))}。
2】B=R, x)x+1,x)x,h(x)=1都是函数。

【例5.设A=则f(=g(= 

x 

注:两个函数
f 
和
g 
相等当且仅当同时满足下面两个条件: 

(1)Dom(f)=Dom(g)。

(2)对于任意x∈Dom(f)=Dom(g)都有f(x)=g()。
例如,函数f(=(1)/(1) x)x+1不因为Df).Dg)。
x)x2-x-和g(=相等,(x) om(om(
定义5.设A、
f 
是
A 
到
B 
的一个关系。如果对每个x∈A,

2 B 
是非空集合,存在唯
一的y∈B,使得(y)∈f, 记作f:
A 
→B。此时也称
f 
是处

x,则称
f 
为
A 
到
B 
的函数, 
处定义的(everywheredefined)。
注: 

(a)对于
A 
到
B 
的函数f,Dom(f)=A,Ran(f).B。
(b)对于定义5.
1中定义的函数,有时也将其称作
A 
到
B 
的函数,但对于
x 
. 
Dom(f),需指定f(x)的值为“无定义”。

(c)对于定义5.当Dom(有些文献也称其为部分函数
(partialfunction)。
1中定义的函数, f).
A 
时, 

如果一个
A 
到
B 
的关系是函数,则它的关系矩阵中每一行至多有一个1;如果它是
一个
A 
到
B 
的函数,则它的关系矩阵每一行恰好有一个1。

如果一个
A 
上的关系是函数,则它的关系图中每一个顶点至多发出一条有向边(出
度不超过1);如果它是一个
A 
上的函数,则它的关系图中每一个顶点恰好发出一条有向
边(出度恰为1)。

【例5.设A=则f(=x+1是R到R的函数, x)=

3】B=R, x)而g(x和h(x)= 

1则不是。

x 

定义5.设函数f:则称f(为A1 
在
f 
下的

3 
A→B,A1.A, A1)={f(x)|x∈A1} 
像(imagfA1udrf),A) ige)。

eonef(称为函数的像(ma
【例5.设函数f:定义为f(1)=f(=1(则有f({2,3})

2,4】
={2}。
Z+→
Z+ 1,n)n-n>1), = 
f({1,3})1,


145
第
5 
章　函数

下面定义一些常用的函数。

定义5.

4 

(a)设f:A→B,如果存在c∈
B 
使得对所有的x∈
A 
都有f(x)=c,则称f:
A 
→
B 
是常值函数。
(b)设
A 
是非空集合,称
A 
上的恒等关系
。
IA 
为
A 
上的恒等函数(n), 
也记作1A 
。即对于所有的x∈A,1A 
(x)=
x 
identityfunctioa)=
(c[
)设
R 
是
A 
上的等价关系,定义从
A 
到A/
R 
的函数g:A→A/R,对任意a∈A,
g 
(a],即将元素映射到该元素所在的等价类,称
g 
是从
A 
到商集A/
R 
的典范映射
(canonicalmap)或自然映射。
n-dn

(d)设
n 
是一个正整数,则可以定义从
Z 
到{0,1,2,…,1}的取余函数mo。
(e)设集合A.B,
A 
到
B 
的包含映射(或嵌入(为函数i: 
AB,对于任意x∈A,i(x)=。
inclusionmap) embedding) 
注:给定集合
A 
和
A 
上的个等价关系R,就可以确定一个典范映射g:A→A/R。
不同的等价关系确定不同的典范映射。一(x) 
【例5.定义函数
g 
为g(=则
g 
是C到C的常值函数。56 
】】
A={1,2,3} 
x)2, 
1,1),(1,2,2),(3,3,3)}

【例5.上的等价关系R={(3),(1),(所确
定的典范映射是g1(1)=g1(3)={1,3},g1(2)={2}。
A 
={1,2,3}上的恒等关系IA 
所
确定的典范映射是g2(1)={1},2)={2},3)={3}。

g2(g2(

习题5.

1 

5.1 
判断以下A={±1,±2,±3,±4}上的关系中哪些构成函数。
(a)R={(y)|x∈A,y+x<7 }。
x,y∈A,
(b)R={(x,y∈A,2≤20 }
。


y)|x∈A,x2+
y
(c)R={(y)|x∈A,y=x2}
。


x,y∈A,
(d)R={(x,
a,c} 
2}
。


y)|x∈A,y∈A,x=y

5.2 
判断以下A={b,上的关系中哪些构成函数,哪些构成
A 
上的函数。
(a)R={(b),(c),(b),(a)}。
a,a,b,b,
(b)R={(b),(b)}
。


a,b,
(c)R={(b),(b),(
c


a,b,c,)}。

5. 
判断以下关系
f 
中哪些是
A 
到
B 
的函数。
(a)A=B=R,fy 
当且仅当x2=y2。
x
(b)A=B=R,fy 
当且仅当x3=y3
。
(c)A=B=C,((x) c+di)当且仅当a=
。


a+bi)f( c 

5.4 
设f:
Z+→
Z+,定义为
x/2, 
x 
为偶数
f(x)
= 
x+1,
x 
为奇
数
令A={0,1},B={2},计算f(A)和f(B)
。



1 46 离散数学及应用(第3 版) 
5.5 设f 和g 都是集合A 到集合B 的函数,证明f∩g 也是函数。
5.6 将集合A 到集合B 的所有函数的集合记为BA ,称为指数集,即BA ={f |f:A → 
B}。设A 、B 都是有限集合,|A|=m ,|B|=n,计算|BA|。
5.7 设集合A ={a,b,c,d,e,f}上划分{{a,b,c},{d,e},{f}}决定的等价关系为R,计
算A/R 的典范映射。
5.2 函数的性质
定义5.5 设函数f:A →B。
(a)若Ran(f)=B,则称f 是满射(surjection)或映上的(onto)。
(b)若任意y ∈Ran(f)都存在唯一的x ∈A 使得f (x)=y,则称f 是单射
(injection)或一一的(one-to-one)。
(c)若f 既是满射又是单射,则称f 是双射(bijection)或一一对应(one-to-one 
correspondence)。
注: 
(a)f 是满射意味着:对于任意y∈B,都存在x∈A 使得f(x)=y。
(b)f 是单射另有如下两个等价定义: 
(b.1)如果a,b∈A 满足a≠b,则f(a)≠f(b)。
(b.2)如果a,b∈A 满足f(a)=f(b),则a=b。
函数的满射、单射和双射如图5.2所示。其中,(a)是单射,(b)是满射,(c)是双射。
图5.2 函数的性质
【例5.7】 函数f:Z+ →Z+ ,定义为f(1)=1,f(n)=n-1(n>1)。f 是满射———对
于任意y∈Z+ ,有f(y+1)=y;但不是单射———f(1)=f(2)=1。从而f 不是双射。
【例5.8】 函数g:R →R,定义为g (x)=x2 -2x +1。g 不是单射———g (0)= 
g(2)=1;g 也不是满射———g 在x=1取得最小值0。从而g 不是双射。
【例5.9】 函数h:R→R,定义为h(x)=2x+1。h 是单射———若2x1+1=2x2+1, 
则必然有x1=x2;h 是满射———对于任意y∈R,有h y-1 
2 
.
è .
.
. ÷ 
=y。从而h 是双射。
【例5.10】 设A 是非空集合,A 上的恒等函数1A 既是单射又是满射,从而是双射。
【例5.11】 设A 是非空集合,R 是A 上的一个等价关系,则恒等关系IA 所确定的
典范映射是双射,而其他的典范映射只是满射。
对于有限集合上的函数,有如下主要结论。

147
第
5 
章　函数

定理5.设
A 
和
B 
是两个有限集合且满足|A||B|,则函数f:
A 
→
B 
是单射当

1 
=
且仅当
f 
是满射。
定理5.2 
设
A 
和
B 
都是有限集合,则

(a)若|A|<|B|,则必然存在从
A 
到
B 
的单射函数,必然不存在从
A 
到
B 
的满射
函数。
(b)若|A|>|B|,则必然存在从
A 
到
B 
的满射函数,必然不存在从
A 
到
B 
的单射
函数。
(c)若|A|=|B|,则必然存在从
A 
到
B 
的双射函数
。
推论设
A 
是有限集合,
B 
是无限集合,
则
(a)必然不存在从
A 
到
B 
的满射函数。
(b)必然不存在从
B 
到
A 
的单射函数
。
函数性质在关系矩阵和关系图中的体现如下
:
(a)如果一个
A 
到
B 
的函数是单射,则它的关系矩阵中每一列至多有一个1;如果它
是一个满射,则它的关系矩阵每一列至少有一个1;如果它是一个双射,则它的关系矩阵
每一行每一列都恰好有一个1。
(b)如果一个
A 
上的函数是单射,则它的关系图中每一个顶点至多存在一条指向它
的边(入度不超过1);如果它是一个满射,则它的关系图中每一个顶点至少存在一条指向
它的边(入度不小于1);如果它是一个双射,则它的关系图中每一个顶点都发出一条有向
边,且恰存在一条指向它的边(出度和入度都恰好为1)。
习题2

5.
5.给出以下函数的例子。
8 

(a)
Z+到
Z+的既非单射又非满射的函数
。
(b)
Z+到
Z+的是单射但不是满射的函数
。
(c)
Z+到
Z+的非单射但是是满射的函数
。
(d)
Z+到
Z+的既是单射又是满射的函数
。


5.判断下列函数是否为单射、满射、双射,为什么?
9 

(a)f:f(=n。

(c)f:f(=(x,
(d)f:x,x+y+1 
。
(e)f:
Z×Z→
Z,f(
fy(
)=
y)x+y,)
。


Z+→R,x)lx
(b)f:
R→R,x)=x|
。
R+→R+
f,
(
x)
|
x2+1)/其中R+为正实数集
。


f)f:x,

Z×Z→
Z×Z,x,=(x-
y
(
R×R→R×R,f(y)=(x+y,x-y)
。


5.10 
设
A 
和
B 
是两个有限集,函数f:A→B,证明: 
(a)若
f 
是单射,则|A|≤|B|。
(b)若
f 
是满射,则|B|≤|A|。
1。

5.11 
证明定理5.

148
离散数学及应用(第
3 
版)

2。

5.12 
证明定理5.
5.13 
设A、
B 
都是有限集合,|A|=m,|B|=n,请计算集合
A 
到集合
B 
的所有单射函
数的个数。
14 
设A、
B 
都是有限集合,=请计算集合
A 
到集合
B 
的所有双射函数的

5.
个数。
|A||B|=n, 
5.设有函数f:g:
C 
→D,则可定义
A 
×C 
到
B 
×D 
的函数
f 
×g 
为f×
15 A 
→B,
y)f(x),))
。


g(x,=(g(
y 

(a)证明:若
f 
和
g 
都是单射,则f×g 
也是单射。
(b)证明:若
f 
和
g 
都是满射,则f×g 
也是满射。
(c)证明:若
f 
和
g 
都是双射,则f×g 
也是双射。
5.16 
对于以下集合
A 
和B,构造从
A 
到
B 
的双射函数。
(a)A=(0,1),B=(5,25)( 二者都是实数集上的开区间)。
(b)A={b,B={张三,李四,王五}。
a,c}
,
(c)A=R,B=R+
。


5.函数的复合
3 

B、
f 
是
A 
到
B 
的关系,

定理5.3 
设A、
C 
是集合,
g 
是
B 
到
C 
的关系。若f、
g 
是函
数,则g..
f 
也是函数,且满足以下两个条件: 
(a)Dom(g..f)={x|x∈Dom(f)且f(x)∈Dom(g)}。

(b)对于任意x∈Dom(g..f)有g..f(x)=g(f(x))。
证明:由定义4若对于某个x∈D存在y1,n(使得(x,
10, om(g..f) y2∈Rag..f) y1)∈ 
g..f且(x,,(.) 则存在t1∈Dom(使得(t1)∈
f 
且(y1)∈g,g)

y2)∈g..fg) x,t1,t2∈Dom(
使得(x,ty2)∈
g 
因此tt又由于(1,ty2)∈

t2)∈
f 
且(2,。由于
f 
是函数, 1=2; ty1)∈g,(2,
g,且
g 
是函数,有y1=y2。因此f..
g 
为函数。

(a)由定义4.
10 即得。

(b)由定理4.3所示。
□
6即得
。
函数的复合如图5.



图5.

3 函数的复合

于是,也可以定义函数的幂,它也是函数。
由定理5.

3及关系复合运算的性质易得如下推论。
推论设A、B、C、
f 
为
A 
到
B 
的关系,
h 
为C

D 
均为非空集合,
g 
为
B 
到
C 
的关系,


第
5 
章　函数

149
到
D 
的关系。若f、g、
h 
都是函数,则(h..g)..
f 
和h..(g..f)也都是函数,且(h..g)..f= 

【例5.
R→R定义为f(=g:x)2

h..(g..f)。
12】函数f:x)x+1,
R→R定义为g(=x+1, 

h:
R→R定义为h(x)=x2+1,则
g..f(x)=g(f(x))=2f(x)+1=2(x+1)+1=2x+3 
f..g(x)=f(g(x))=g(x)+1=2x+1+1=2x+2 
h..g..f(x)=h(g(f(x)))=(2x+3)2+1=4x2+12x+10 
定理5.设A、B、
C 
为非空集合,函数f:g:那么

(a)如果
4 g 
和
f 
都是满射,则g..
f 
也是满射
A
。
→B,B→C, 
(b)如果
g 
和
f 
都是单射,则g..
f 
也是单射。
(c)如果
g 
和
f 
都是双射,则g..
f 
也是双射
。
证明
:
(a)对于任意的c∈C, 故存在b∈
B 
使得g(=现考查b,
因
g 
是满射, b)c; 因
f 
是满
a)g(=b)c,

射,故而存在a∈
A 
使得f(b。于是g..f(a))从而证明g..
f 
是满射。
a)==f(g(=

(b)假设存在x1,x2∈
A 
使得g..f(x1)=g..f(x2),则由g(f(x1))=g(f(x2))及
g 
是单射知f(x1)=f(x2);又由于
f 
也是单射,所以x1=x2。从而证明g..
f 
是单射。
(c)由(a)、(b)即得。□ 
定理5.4的说明见图5.4,其中(a)为满射的复合,(b)为单射的复合,(c)为双射的
复合。


图5.4用图

4 定理5.

但是反过来,定理5.而只是部分成立。

4的逆定理并不全部成立
,
5 
A→B,B→C,


定理5.设A、B、
C 
为非空集合,函数f:g:那么

(a)若g..
f 
是单射,则
f 
是单射。
(b)若g..
f 
是满射,则
g 
是满射。

150
离散数学及应用(第
3 
版)

(c)若g..
f 
是双射,则
f 
是单射,
g 
是满射。
证明: 
(a2∈A,a1)a2),于是g..f(

a)假设
f 
不是单射,即存在a1,a1≠a2 且f(=f(a1)= 
a1))a2))a2),而这与g..
f 
是单射矛盾。

g(f(=g(f(=g..f(

(b)若g..
f 
是满射, 存在a∈A, f(=c, f(c, 
故
g 
是满射。
则对于任意c∈C, 使得g..a)于是g(a)
=

(c)由(a)、(b)即得。□ 
定理5.5可以用图5.5说明。(a)中g..
f 
是单射,而
g 
不是单射;(b)中g..
f 
是满射, 
而
f 
不是满射;(c)中g..
f 
是双射,而
g 
不是单射且
f 
不是满射。


图5.5用图

5 定理5.

定理5.6 
设A、
B 
为集合,函数f:A→B,则f=f..1A 
=1B..f。
证明:由定理4.□

7即得。

本节最后给出一些除函数复合外的常用记号
:
(f1+f2)(x)=f1(x)+f2(x)
(f1·f2)(x)=f1(x)·f2(x)
(m·f)(x)=m·f(x)(
m 
为非零常数
)


习题5.

3 

α),(α),(β)},g={(0),(1)},

5.设f={(b,α,计算g..f。
17 
a,c,β,

5.18 
设函数f:
R→R定义为f(x)=256x,g:
R→R定义为g(x)=2h:
R→R定义
为h(x)=x3,计算g..f(x)、f..g(x)、h..g..f(x)。
x ,
19 
f(x2, x≥3 g:g(


5.设函数f:
R→R,x)= -2,x<3;
R→R,x)=x+2 。求f..
g 
和g..f。

第
5 
章　函数

151
5.设函数f:
Z+→
Z+,定义为
f(x)=
x/2, 
x 
为偶数
计算f4(和f6(65 )。
x+1,
x 
为奇数
15) 
的函数:f(g(x(1)。证明:

设有两个
Z+到
Z+ n)n)1,

5.21 
(a)
f 
是单射而不是满射。
=n+1,=man(b)
g 
是满射而不是单射。
(c)g..f=1Z+,而f..g≠1Z+。
5.逆函数
4 

关系的逆关系仍然是关系;而函数作为关系,其逆关系却不一定也是函数。
【例5.设f={(1),(3),(1),(5),(3)}是一个函数,而
f 
的逆关系

13】1,2,4,3,5,
f-1={(1,1),(3,2),(1,4),(5,3),(3,5)}是一个关系,但不是函数。

定义5.设A、
B 
为集合,如果以函数f:A→
B 
作为关系的逆关系f-1是
B 
到
A 
的
函数,则称之为可逆的(tbe), 1为
f 
的反函数或逆函数(nesucin 

6 

7 
iilf:A
称
→
fB-
, 1 
ivrefnto)。
定理5.设A、B为(n) 集(v) 合,(r) (e) 若函数f-存在,则
(a)f-1..f=1A 
。
(b)f..f-1=1。
证明:假设函数(B) f-1存在,对于任意x∈A,由于
f 
是
A 
到
B 
的函数,因此存在y∈B, 

使得(x,x,1..f,即得11..f。又由于
f 
和f-1 定

y)∈f。于是(x)∈f-
A 
.f-都是函数, 
理5.1..
f 
也是函数, 若还存在y∈
A 
使得(x,y)∈f-1..

3表明f-因此对于任意x∈A, 

f,则必然有y=x,即f-1..f=1A 
。
类似地,可证明f..f-1=1B 
。□ 
定理5.

8给出了逆函数存在的充要条件。
定理5.8 
设A、
B 
为非空集合,函数f:A→B,则
f 
可逆当且仅当
f 
是双射,且
f 
的

逆函数若存在则也是双射。
证明:(充分性)假设
f 
是双射。下面证明f-1是
B 
到
A 
的函数。
因为
f 
是函数,所以f-1是关系,且由
f 
是双射有Df-n(
f 
)=B, 

Ran(f-1)=Dom(f)=A。
b,a1)∈f-
omb(
,1)=Ra
对于任意的b∈B,若存在a1,1且(a2)∈f-则由关系逆

a1,a2,
a2∈
A 
使得(
a2 
1, 
的定义有(b)∈
f 
且(b)∈f,根据
f 
是单射可得a1=。从而证明f-1是
B 
到
A 
的函数。

(必要性)假设
f 
可逆,以下分两个步骤证明
f 
是双射
:
(1)
f 
是单射。由定理5.f-1..f=1A 
,而1A 
是单射, 5,


7,由定理5.
f 
是单射。
(2)
f 
是满射。由定理5.f..f-1=1而1B 
由定理5.
f 
是满射。

7,
B 
, 是满射, 5,
下面证明f-1也是双射:
7,1而1由定理5.是满射。(f-f

1)f-1是满射。由定理5.1..f=
A 
, 
A 
是满射, 5,1 


152
离散数学及应用(第
3 
版)

(2)f-1 7,1=1而1由定理5.f-1是单射。□

是单射。由定理5.f..f-
B 
, 
B 
是单射, 5,
注:由定理5.8及关系的逆运算、复合运算的性质,易得
:


(a)若函数f:A→
B 
是双射,则(f-1)-1=f。
(b)若函数f:A→B,g:B→
C 
均是双射,则(g..f)-1=f-1..
g 
-1。
【例5.函数h:
R→R,x)=2因此可逆, 1(x)=
14】h(x+1是双射, 其逆函数是h

x-1。而函数g:
R→R,x)=-x2+2x-因此
g 
的逆函数不存在。

g(1不是双射,

2 
本节最后给出一个更强的结论,它在实际应用中具有重要意义和价值。
定理5.设A、
B 
为集合,若
A 
到
B 
的函数
f 
和
B 
到
A 
的函数
g 
满足g..f=及
f..g=1B 
,则
9 f 
是一个
A 
到
B 
的双射,
g 
是一个
B 
到
A 
的双射,而且
f 
和
g 
互为逆1函数。(A) 证明:由g..f=1A 
知
f 
是满射,由f..g=1B 
知
f 
是单射,因此
f 
是双射,

f-1=f-1..(f..g)=(f-1..f)..g=1A..g=g。
f 
可逆。且
类似可证明
g 
也是双射,
g 
可逆且
g 
-1=f。□ 
由此逆函数也可以等价地定义如下。
定义5.7 
设A、
B 
为集合,对于函数f:A→
B 
若存在函数
g 
使得g..f=1A 
且f..g= 

1B 
。则称
f 
为可逆的,此时称
g 
为
f 
的反函数或逆函数,记作g=f-1。

习题5.

4 

1,求出
A 
上所有的可逆函数。

5.22 
设A={2,3}, 
x2,x≥3 ;g:
R→R定义为g(x)=x+2 。如
5.23 
设函数f:
R→R定义为f(x)=9, x<3
果
f 
和
g 
存在逆函数,则求出它们的逆函数;如果不存在逆函数,说明理由。

5.24 
设函数f:x,=(x-y
R×R→R×R定义为f(y)x+y,)。

(a)证明
f 
是双射。
(b)求
f 
的逆函数。
(c)求f..f。
5.25 
设f1,f3:
Z+→
Z+ 
f1(n)=2n 
f2,定义为

n)n/2, 
n 
为偶数
f2(
= 
n+1,
n 
为奇数
f3(
= 
n-1,
n 
为偶数

n)n+1,
n 
为奇
数
分析f1、f2、f3 是否为单射、满射、双射,说明f1、f2、f3 是否可逆
。


26 
A→B,B→C,C→A。若h..g..f=
A 
,h..g=
B 
,h=
C ,
f、g、
h 
均为双射
。


5.设f:g:h:1f 
..1g..
f 
..1证明