第5 章
函 数
函数是极其重要的数学概念,它与二元关系有着密切的联系.本章首先从关系的概念
出发引入函数的定义,然后讨论函数的单射、满射和双射的性质,最后介绍与函数相关的复
合与求逆运算. 
5.1 函数的定义及其性质
5.1.1 函数的定义 
函数是一种特殊的二元关系.先给出函数的定义. 
定义5.1 设f 是二元关系,如果对于任意x∈domf,都存在唯一的y∈ranf,使得
xfy 成立,则称f 为函数(或者映射).这时也称y 为f 在x 的值,记作y=f(x). 
注意,在上述定义中,符号y=f(x)既反映了y 与x 的对应关系,也反映了对应的唯一
性.与此不同的是,在关系R 中,如果与x 对应的有y 和z,y≠z,那么为了表示y 与x 的
对应关系,只能写<x,y>∈R 或者xRy,不能写y=f(x). 
函数是一种特殊的关系,关系又是集合,因此函数的相等可以用集合的相等来定义. 
定义5.2 设f,g 为函数,则
f =g .f .g ∧g .f 
根据上述定义,如果两个函数f 和g 相等,一定满足下面两个条件: 
(1)domf = domg. 
(2).x∈domf = domg 都有f(x)=g(x). 
例如,函数f 与g 的对应关系分别是:f(x)=(x2-1)/(x+1),g(x)=x-1,那么f 与g 
不相等,因为domf 是不等于-1的实数构成的集合,而domg 是实数集合. 
在所有函数中,从一个集合到另一个集合的函数是一类非常重要的函数.后面讨论的
函数基本上都是这类函数. 
定义5.3 设A ,B 为集合,如果
f 为函数,domf=A ,ranf.B 
则称f 为从A 到B 的函数,记作f:A →B. 
例5.1 下面是一些函数的例子. 
(1)f:N→N,f(x)=x+1是从N 到N 的函数.

118
离散数学(第4版) 

(2)g:R→R,g(x)=x2+2x-1是从
R 
到
R 
的函数
.
(3)h:A→P(h(={是从集合
A 
到幂集P(的函数
.


A),x)x} A) 

a1,}

(4)设V={a2,…,是
n 
项任务的集合,其中每项任务的执行时间都是正整数.
an 
函数t:V→
N 
表示一个调度方案,对于任务ai,t(=i,1,2,…,其中ti是第
i 
项

ai)ti=n. 
任务的开始时间
. 
下面考虑对f:A→
B 
函数的计数.设|A|=m,|B|=n,m,n>0,那么有多少个不同
的从
A 
到
B 
的函数呢? 考虑某个从
A 
到
B 
的函数f,
f 
应该具有下述形式: 
f={ba2,i2>bm

<,<,…,<>}
其中
m 
个有序对的第二元素选自
B 
集合,每个有
n 
种不同的选择,每一种选法对应了一个
函数,总共有nm 
种选法,因此有nm 
个不同的函数.使用BA 
的符号表示所有函数的集合,那
么有下述定义
. 

定义5.所有从
A 
到
B 
的函数的集合记作BA 
,符号化表示为

a1,i1>bam 
,i

4 

BA 
={f|f:A→B} 
=n≠0, nm

若|A
例5.2|=m,|B|n,m,则|BA|=
. 
设A={1,3},B={b}, 求BA.

2,a,
解BA 
={f0,f7}, 其中:
1,,2,,3,
}


f1,…,
f0={<a><a><a>
f1={<1,,2,,3,}

a><a><b>
f2={1,,2,<a>

<a><b>,3,} 
f3={<a><b>,3,}

1,,2,<b>
f4={1,b>2,3,

<,<a>,<a>} 
f5={<b><a>,3,}

1,,2,<b>
f6={<b>,<b>,<3,a>}

1,2,
f7={<b><b><b>

1,,2,,3,}

下面给出一些重要函数的实例
. 

定义5.(1)设f:A→B,如果存在c∈
B 
使得对所有的x∈
A 
都有f(x)c,则称

5 
=

f:A→
B 
是常函数
. 
(2)称
A 
上的恒等关系IA 
为
A 
上的恒等函数,对所有的x∈
A 
都有IA 
(x)=x. 
(3)设<A,.>,<B,.>为偏序集,f:A→B,如果对任意的x1,x2∈A,x1.x2,就有
f(x1).f(x2), 则称
f 
为单调递增的;如果对任意的x1,x2∈A,x1.x2,就有f(x1). 
x2), 则称
f 
为严格单调递增的.类似地,也可以定义单调递减和严格单调递减的函数.
f(
(4)设
A 
为集合,对于任意的A'.A,A'的特征函数χA' 
:A→{0,1}定义
为
χA'(=1 
a 
∈A'


a)
χA'(=
a 
∈
A 
-A' 

(5)设
R 
是
A 
上的等价关系, 
a
令
)
0
g:A→A/
R
g(a)=
[
称
g 
是从
A 
到商集A/
R 
的自然映射.
a].a∈
A 


函数

例5.3
(1)给定偏序集<P({b}),,<{1},≤>,其中R. 为包含关系,≤为
a,R.>0,
一般的小于或等于关系.令f:P({1},f(.)a})b})

b})f({f({0,f({

a,→{0,===a, 
b})=1,则
f 
是单调递增的,但不是严格单调递增的
. 

(2)设A={b,'都对应于一个特征函数,不同的子集对应于
a,c},
A 
的每一个子集A
不同的特征函数.例如: 
χ. ={a,b,0>c,0>χ{a,b,1>c,0>

<0>,,},b}={1>,,}

<<a,<<<

(3)给定集合
A 
和
A 
上的等价关系R,就可以确定一个自然映射g:A→A/R.不同
的等价关系确定不同的自然映射,如果
A 
={1,2,3}, 对于等价关系
R 
={<1,2>, 
第
章

119
<2,1>}∪IA 
,对应的自然映射是
=

g:
A 
→A/R,g(1)g(2)={1,2},g(3)={3}
而对于恒等关系IA 
,自然映射是
g:
A 
→A/IA 
,g(1)={1},g(2){2},g(3)={3}
=

在算法分析与设计中经常用到定义在正整数集合上的函数f:Z+→Z+ 

.例如,二分检

索算法最坏情况下的时间复杂度f(=O(on)①,插入排序算法最坏情况下的时间复杂

n)lg
度为O(等等
. 
检索问题中的
n 
表示被检索的线性表中的元素

n2), 这里的
n 
表示输入规模, 
个数,排序问题中的
n 
则表示被排序的数组中的元素个数.函数f(n)代表算法所做基本运
算的次数.在二分检索和排序中的基本运算是比较运算.一般说来,对于规模为
n 
的各种输
入情况,算法所做基本运算的次数是不一样的.考虑二分检索,如果输入的
n 
个元素是1, 
2,…,而被检索的元素恰好就是处在中间的那个数, 算法就结束了,

n, 那么通过1次比较, 
然后输出这个数在数组中的位置.如果被检索的数是其他数,那么必须通过更多次的比较, 
才能得到结果.所谓最坏情况就是对同样长度的数组所做的比较运算次数最多的情况.对
于二分搜索,每比较1次,需要检索的数的个数就减少一半,至多经过logn+1 次比较就可
以得到结果.因此,on, 记作O(on)如

表示基本运算次数的函数的阶是lg使用大
O 
记号, lg. 
果基本运算的次数与输入规模
n 
无关,是个常数,则记作O(1).对于同一个问题可以设计
各种不同的算法,排序算法就有插入排序、快速排序、归并排序、堆排序等许多算法.哪种算
法效率更高? 这依赖于它们的复杂度函数的阶.阶越高,效率就越低.不难看出,当
n 
增加
时,复杂度函数n2 显然比nlogn 
增长得更快.这意味着插入排序比归并排序在
n 
较大时效
率要低,因此估计算法复杂度函数的阶在算法分析中是经常要做的工作.关于这方面的应
用将在第10 章和第13 章给予更详细的介绍
. 

5.2 
函数的像与完全原像
1.
函数是特殊的关系,因此关系的各种运算(如并、交、补、求定义域、值域等)都适合于函
数.除此之外,对于从
A 
到
B 
的函数,还可以求集合的像和完全原像
. 
定义5.设函数f:A→B,A1.A,B1.B.

6 

(1)A1 在
f 
下的像f(A1)={f(x)|x∈A1}, 当A1=
A 
时,f(A)称为函数的像
. 

(2)B1 在
f 
下的完全原像f-1(B1)={x|x∈A∧f(x)∈B1}
. 

① 在算法分析中经常使用lgo2n. 
on=nl2, on=Θ(n.
on 
来表示lg由于lgln/n因此有lgln)这个等式的含义是: 
lon 
=ln)nO(on), no2n 
的阶相等.

gO(n且ln=lg即ln 
与lg


120
离散数学(第4版) 

这里要注意函数的值与函数的像之间的区别,函数值f(x)∈B,而像f(A1).B.一
般说来,对于A1.A,1(f(1(f(
. 
对于B1.B,

f-A1))≠A1,但是A1.f-A1))同样地, 也
有f(f-1(B1)).B1.例如: 

3},B={c},A1{1},B1c},
f 
<a>,<a>,<}

2,b,={={2,b>

A={1,a,=b,1,3,

那么

f-1(f(A1))=
f 
-1({a})={1,2},A1.f-1(f(A1)) 

-1(B1))f({3})b},f(-1(B1)).B1

f(
f 
=={
f 

5.3 
函数的性质
1.
函数的性质指的是函数f:
A 
→
B 
的满射、单射、双射的性质.下面给出这些性质的
定义
. 
定义5.设f:A→B,

7 

(1)若ranf=B,则称f:A→
B 
是满射的
. 
(2)若.y∈ranf 
都存在唯一的x∈
A 
使得f(x)=y,则称f:A→
B 
是单射的
. 
(3)若f:A→
B 
既是满射又是单射的,则称f:A→
B 
是双射的
. 
对于单射函数也有另外一个等价的定义.设f:A→B,对于x1,x2∈A,如果x1≠x2, 
则f(x1)≠f(x2), 那么称f:A→
B 
为单射的.一般函数从自变量到值的对应规则既允许
一对一,也允许多对一;而单射函数只允许一对一的对应,因此,单射函数也称作一对一的
函数
. 

例5.4
判断下面函数是否为单射、满射、双射的,为什么
?
(1)f:R→R,f(x)=-x2+2x-1.
(2)f:Z+→R,f(x)=lnx,Z+为正整数集
.
(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+为正实数集
. 
解(1)
f 
在x=1取得极大值0,因此,不是满射的;f(0)=f(2)=-1,因此,不是单

射的
.
(2)
f 
是单调上升的,是单射的.但不满射,raf={nn2,…
}


nl1,l.
(3)rnf 
不是单射的,因为f(4)f(1)1.


af=Z,
f 
是满射的.1.=1.=
(4)
f 
是满射、单射、双射的,因为它是单调函数并且ranf=R. 
(5)
f 
有极小值f(1)=2,且当x→0 和+∞ 时,f(x)都趋于+∞,因此,它既不是单射

的,也不是满射的
. 

判断函数f:A→
B 
是否为满射、单射、双射的依据是定义.判断满射就是检查
B 
中的
每个元素是否都是函数值.如果在
B 
中找到不是函数值的元素,那么
f 
就不是满射的.判
断单射的方法就是检查不同的自变量是否对应于不同的值.对于普通的初等函数,可以通
过其图像的单调性质来确定.如果函数图像是严格单调上升(或者严格单调下降), 那么函
数是单射的
. 

例5.5
对给定的A,
B 
和f,判断是否构成函数f:A→B.如果是,说明f:A→
B 
是否为单射、满射、双射的;如果不是,请说明理由,并根据要求进行计算
. 


函 数
第5章
1 21 
(1)A ={1,2,3,4,5},B={6,7,8,9,10},f={<1,8>,<3,9>,<4,10>,<2,6>,<5,9>}. 
(2)A ,B 同(1),f={<1,7>,<2,6>,<4,5>,<1,9>,<5,10>}. 
(3)A ,B 同(1),f={<1,8>,<3,10>,<2,6>,<4,9>}. 
(4)A =B=R,f(x)=x3. 
(5)A =B=R+ ,f(x)=x/(x2+1). 
(6)A =B=R×R,f(<x,y>)=<x+y,x-y>,令L ={<x,y>|x,y∈R∧y=x+ 
1},计算f(L). 
(7)A =N×N,B=N,f(<x,y>)=|x2-y2|.计算f(N×{0}),f-1({0}). 
解 (1)能构成f:A→B,f:A→B 既不是单射的,也不是满射的.因为f(3)=f(5)= 
9,且7.ranf. 
(2)不能构成f:A →B,因为f 不是函数.<1,7>∈f 且<1,9>∈f,与函数定义矛盾. 
(3)不能构成f:A →B,因为domf={1,2,3,4}≠A . 
(4)能构成f:A →B,且f:A →B 是双射的. 
(5)能构成f:A →B,f:A →B 既不是单射的,也不是满射的.因为该函数在x=1取
极大值f(1)=1/2.函数不是单调的,且ranf≠R+ . 
(6)能构成f:A→B,且f:A→B 是双射的.f(L)={<2x+1,-1>|x∈R}=R×{-1}. 
(7)能构成f:A →B,f:A →B 既不是单射的,也不是满射的.因为f (<1,1>)= 
f(<2,2>)=0,2.ranf.且
f(N× {0})={n2 -02|n ∈ N}={n2|n ∈ N} 
f-1({0})={<n,n>|n ∈ N} 
例5.6 设f1,f2,f3,f4∈RR,且
f1(x)= 1 x ≥0 
-1 x <0 { 
f2(x)=x 
f3(x)= 
-1 x ∈Z 
1 x .Z { 
f4(x)=1 
令Ei是由fi导出的等价关系,i=1,2,3,4,即xEiy.fi(x)=fi(y).令S 是4个划分的集
合{R/E1,R/E2,R/E3,R/E4},在S 上如下定义划分之间的加细关系T : 
<R/Ei,R/Ej>∈T ..x(x ∈ R/Ei → .y(y ∈ R/Ej ∧x .y)) 
即对于R/Ei的任何划分块x,都存在R/Ej 的划分块y 使得y 包含x,那么<R/Ei,R/Ej> 
属于T ,即划分R/Ei是划分R/Ej的加细.不难证明T 是S 上的偏序. 
(1)画出偏序集<S,T>的哈斯图. 
(2)gi:R→R/Ei是自然映射,求gi(0),i=1,2,3,4. 
(3)对每个i,说明gi的性质(单射、满射、双射). 
解 (1)因为E2 是恒等关系,对应的划分R/E2 具有无数个划分块,每块只含有1个
元素,是最细的划分,因此在加细关系的偏序集中为最小元.E4是全域关系,对应的划分
R/E4只有1个划分块,是最粗的划分,因此在加细关系的偏序集中是最大元.E1 对应的划

离散数学(第4 版) 
12  2 
图 5.1 
分R/E1 有2个划分块,所有的非负实数构成一块,所有的负数构成
另一块.因此R/E1 比R/E2 粗,比R/E4细,介于它们之间.类似地, 
E3对应的划分R/E3也由两块构成,所有的整数在一块,其他的实数
在另一块.它也介于R/E1 和R/E3之间.不难看出,R/E1 与R/E3 
之间不存在加细关系,它们是不可比的.因此哈斯图如图5.1所示. 
(2)gi(0)是所有与0等价的元素构成的集合,i=1,2,3,4. 
因此
g1(0)={x |x ∈ R ∧x ≥0},g2(0)={0}, 
g3(0)=Z,g4(0)=R 
(3)g1,g2,g3,g4都是满射的;其中g2 是双射的. 
例5.7 对于给定的集合A 和B 构造双射函数f:A →B. 
(1)A =P({1,2,3}),B={0,1}{1,2,3}. 
(2)设A ,B 为实数区间,其中A =[0,1],B=[1/4,1/2]. 
(3)A =Z,B=N. 
(4)设A ,B 为实数区间,其中A =[π/2,3π/2],B=[-1,1]. 
解 (1)A ={.,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}.B ={f0,f1,…,f7}, 
其中: 
f0 ={<1,0>,<2,0>,<3,0>} 
f1 ={<1,0>,<2,0>,<3,1>} 
f2 ={<1,0>,<2,1>,<3,0>} 
f3 ={<1,0>,<2,1>,<3,1>} 
f4 ={<1,1>,<2,0>,<3,0>} 
f5 ={<1,1>,<2,0>,<3,1>} 
f6 ={<1,1>,<2,1>,<3,0>} 
f7 ={<1,1>,<2,1>,<3,1>} 
令f:A →B,且满足
f(.)=f0,f({1})=f1,f({2})=f2,f({3})=f3, 
f({1,2})=f4,f({1,3})=f5,f({2,3})=f6,f({1,2,3})=f7 
(2)令f:[0,1]→[1/4,1/2],f(x)=(x+1)/4. 
(3)将Z中元素以下列顺序排列并与N 中元素对应. 
Z: 0 -1 1 -2 2 -3 3 … 
↓ ↓ ↓ ↓ ↓ ↓ ↓ 
N: 0 1 2 3 4 5 6 … 
则这种对应所表示的函数是
f:Z→ N, f(x)= 2x x ≥0 
-2x -1 x <0 { 
(4)令f:[π/2,3π/2]→[-1,1],f(x)=sinx. 
例5.8 设f:R×R → R×R

函 数
第5章
1 23 
f(<x,y>)=<x +y,x -y> 
证明f 既是满射的,也是单射的. 
证明 任取<u,v>∈R×R,存在<u +v 
2 ,u -v 
2 >使得
f <u +v 
2 ,u -v 
2 > .
è .
.
. ÷ 
=<u,v> 
因此,f 是满射的. 
对于任意的<x,y>,<u,v>∈R×R,有
f(<x,y>)=f(<u,v>).<x +y,x -y>=<u +v,u -v> 
.x +y =u +v,x -y =u -v.x =u,y =v 
.<x,y>=<u,v> 
因此,f 是单射的. 
5.2 函数的复合与反函数
函数可以进行各种运算,复合运算和求反函数的运算是最重要的运算. 
5.2.1 函数的复合
函数的复合就是关系的合成,所有关系合成的性质对于函数复合都是成立的,这里只讨
论有关函数复合的一些特殊性质.先给出关于函数复合运算的定理.这个定理说明两个函
数复合以后还是函数,同时给出了复合函数的定义域与函数值的计算规则. 
5.1 设f,g 是函数,则f..g 也是函数,且满足
(1)dom(f..g)={x|x∈domf∧f(x)∈domg}. 
(2).x∈dom(f..g)有f..g(x)=g(f(x)). 
证明 先证明f..g 是函数.因为f,g 是关系,所以f..g 也是关系.若对某个x ∈ 
dom(f..g)有xf..gy1 和xf..gy2,则 
<x,y1>∈f..g ∧ <x,y2>∈f..g 
. .t1(<x,t1>∈f ∧ <t1,y1>∈g)∧ .t2(<x,t2>∈f ∧ <t2,y2>∈g) 
. .t1.t2(t1 =t2 ∧ <t1,y1>∈g ∧ <t2,y2>∈g) (f 为函数) 
.y1 =y2 (g 为函数) 
所以f..g 为函数. 
再证明结论(1)和结论(2).任取x, 
x ∈dom(f..g) 
. .t.y(<x,t>∈f ∧ <t,y>∈g) 
. .t(x ∈domf ∧t=f(x)∧t ∈domg) 
.x ∈ {x|x ∈domf ∧f(x)∈domg} 
任取x, 
x ∈domf ∧f(x)∈domg 
. <x,f(x)>∈f ∧ <f(x),g(f(x))>∈g

124
离散数学(第4版) 

.<x,f(x))g
g(>∈f..

所以(1)和(2)得证
. 
.
x 
∈dom(f..g)∧f..g(x)=g(f(x)) 
从这个定理可知,复合函数f..
g 
的定义域可能小于
f 
的定义域,而它的值域也可能小
于
g 
的值域.它们之间的关系满足: 
dom(g).drn(f..ag


f..omf,ag).rn
1 
设f,
h 
为函数,则(..g..都是函数,且

g,f..g)
h 
和f..(h)

(f..g)..h=f..(g..h) 
证明由上述定理和关系合成运算的可结合性得证
. 
x))
2 
设f:
A 
→B,g:
B 
→C,则f..g:
A 
→C,且.
x 
∈
A 
都有f..g(x)= 

g(f(
证明
. 
由上述定理知f..
g 
是函数,
且
dom(f..g)={x|
x 
∈domf 
∧f(x)∈domg}
={x|
x 
∈
A 
∧f(x)∈B}=
A
ran(f..g).rang 
.
C
因此f..g:A→C,且.x∈
A 
有f..g(x)=g(f(x))
.
下面考虑函数的单射、满射、双射的性质与函数复合运算之间的关系
.



5.设f:A→B,g:B→C.
2 

(1)如果f:A→B,g:B→
C 
都是满射的,则f..g:A→
C 
也是满射的
. 
(2)如果f:A→B,g:B→
C 
都是单射的,则f..g:A→
C 
也是单射的
. 
(3)如果f:A→B,g:B→
C 
都是双射的,则f..g:A→
C 
也是双射的
. 
证明(
f..g(
a=
)
f(g(=
b)c.对于这个b,由
1)任取c∈C,由g:B→
C 
的满射性,.b∈
B 
使得g(=

f:A→
B 
的满射性,.a∈
A 
使得f(=b.由合成定理有
a)g(a))=b)
c
从而证明了f..g:A→
C 
是满射的
.


(2)假设存在x1,x2∈
A 
使得
f..g(x1)=f..g(x2) 
由合成定理有

g(f(x1))=g(f(x2)) 
因为g:B→
C 
是单射的,故f(x1)=f(x2).又由于f:A→
B 
也是单射的,所以x1=x2. 
从而证明f..g:A→
C 
是单射的
. 

(3)由(1)和(2)得证
. 
定理5.满射、但这个定理的逆
2说明函数的复合运算能够保持函数单射、双射的性质
. 
命题不为真,即如果f..g:
A 
→
C 
是单射(或满射、双射)的,不一定有f:
A 
→
B 
和

g:B→
C 
都是单射(或满射、双射)的.考虑集合A={a3},B={b4},C=
a2,b2,
c3}令
<b1>,<,<
a1,
} 
b1,b3,

{c1,c2,
. 

a1,b2>b3>
gb1,,b2,<c3>,b4,

f={a2,a3,

={<c1><c2>,b3,<c3>} 


函 数
第5章
1 25 
f..g ={<a1,c1>,<a2,c2>,<a3,c3>} 
那么f:A →B 和f..g:A →C 都是单射的,但g:B →C 不是单射的.考虑集合A = 
{a1,a2,a3},B={b1,b2,b3},C={c1,c2}.令
f ={<a1,b1>,<a2,b2>,<a3,b2>} 
g ={<b1,c1>,<b2,c2>,<b3,c2>} 
f..g ={<a1,c1>,<a2,c2>,<a3,c2>} 
那么g:B→C 和f..g:A →C 是满射的,但f:A →B 不是满射的. 
下面考虑恒等函数在复合运算中的作用. 
5.3 设f:A →B,则f=f..IB =IA..f. 
定理5.3的证明可以采用集合相等的证明方法,这个证明留给读者思考. 
设f:A →A ,则f=f..IA =IA..f. 
任何A 上的函数f 与IA 进行复合都等于f,就像普通加法与0相加或者普通乘法与1 
相乘一样.这里的0,1 和IA 都称为相关运算的单位元,关于单位元的性质将在后面
第14章给出详细的介绍.推论说明了IA 是A 上的函数复合运算的单位元. 
5.2.2 反函数
下面考虑函数的求逆运算.任给函数f,它的逆f -1不一定是函数,只是一个二元关系. 
任给单射函数f:A→B,则f -1是函数,且是从ranf 到A 的双射函数,但不一定是从B 到A 
的双射函数.对于双射函数f:A→B,容易证明f -1:B→A 是从B 到A 的双射函数. 
5.4 设f:A →B 是双射的,则f-1:B→A 也是双射的. 
证明 因为f 是函数,所以f -1是关系,且
domf -1=ranf =B, ranf -1=domf =A 
对于任意的x∈B=domf -1,假设有y1,y2∈A 使得<x,y1>∈f -1∧<x,y2>∈f -1 
成立,则由逆的定义有<y1,x>∈f∧<y2,x>∈f.根据f 的单射性可得y1=y2,从而证明
了f -1是函数,且由ranf -1=A 知f -1是满射的. 
若存在x1,x2∈B 使得f -1 (x1)=f-1(x2)=y,从而有 
<x1,y>∈f -1∧ <x2,y>∈f -1 
. <y,x1>∈f ∧ <y,x2>∈f.x1 =x2 (因为f 是函数) 
从而证明了f -1的单射性. 
对于双射函数f:A →B,称f -1:B→A 是它的反函数. 
例5.9 设f:R→R,g:R→R 
f(x)= 
x2 x ≥3 
-2 x <3 { 
g(x)=x +2 
求f..g,g..f.如果f 和g 存在反函数,求出它们的反函数. 
解
f..g:R → R 
f..g(x)= 
x2 +2 x ≥3 
0 x <3 {

离散数学(第4 版) 
12  6 
g..f:R → R 
g..f(x)= (x +2)2 x ≥1 
-2 x <1 
{ 
f:R→R 不是双射的,不存在反函数;g:R→R 是双射的,它的反函数是
g-1:R → R, g-1(x)=x -2 
函数f 的反函数具有下述性质. 
5.5 设f:A →B 是双射的,则
f -1..f =IB , f..f -1=IA 
证明 根据定理5.4可知f -1:B→A 也是双射的.由合成基本定理可知f -1..f:B→ 
B,f..f -1:A →A ,且它们都是恒等函数. 
对于双射函数f:A →A ,根据上述定理有f -1..f =f..f -1=IA . 
关系和函数是离散数学的基本概念,在离散系统建模中有着重要的应用.下面给出几
个例子. 
例5.10 关系代数(relationalgebra). 
关系代数是关系数据库的基础.一个通讯录可以看作一个简单的关系数据库,其中的
分组,如同学组、同事组、朋友组等都可以看作不同的关系.每个关系都是若干元组的集合, 
元组<A1,A2,…,An>代表该关系有n 个属性.例如,通讯录的朋友组R 可能含有下述信
息:<2,李明,50,融创大厦A 座502,13341556347,liming@hotmail.com.cn>,该信息是由编
号、姓名、年龄、地址、手机号、E-mail6 个属性构成的六元组.表5.1 给出了具有
4条信息的关系R. 
表 5.1 
编 号姓 名年 龄地 址手 机 号E-mail 
1 张晓光34 科斯公司市场部13520145678 zhxg@gmail.com.cn 
2 李 明50 融创大厦A座502 13341556347 liming@hotmail.com.cn 
3 王 恒43 求实中学13124567336 wheng@qq.com.cn 
4 石海生27 大华公司网络中心13822253689 Shihs@hotmail.com.cn 
为了得到相关的查询结果,数据库中定义了几种基本操作:并、交、差、笛卡儿积、选择、
投影.设R 与S 是具有相同属性的m 元关系,其中的m 个属性记作A1,A2,…,Am ,这些基
本操作说明如下: 
(1)R∪S 的元组既含有R 的元组,也含有S 的元组. 
(2)R∩S 的元组是同时存在于R 和S 中的元组. 
(3)R-S 的元组只在R 中但不在S 中. 
投影πAi1 ,Ai2 ,…,Ain (R )是从m 阶笛卡儿积A1×A2×…×Am 到n 阶笛卡儿积Ai1 × 
Ai2 ×…×Ain 的部分映射,πAi1 ,Ai2 ,…,Ain (R)表示只选取R 中属性为Ai1 ,Ai2 ,…,Ain 的列. 
例如,对表5.1中的关系R 进行投影运算,π姓名,手机号,E-mail(R)的查询结果如表5.2所示.