第 8章 函数离 散 数 学哈尔滨理工大学本科生课程计算机系本章说明
本章的主要内容
– 函数的定义
– 函数的性质
– 函数的逆
– 函数的合成
本章与后续各章的关系
– 是代数系统的基础
8.1 函数的定义与性质
8.2 函数的复合与反函数
8.3 一个电话系统的描述实例本章小结习题作业本章内容
8.1 函数的定义与性质定义 8.1 设 F为二元关系，若?x∈dom F,都存在 唯一的
y∈ran F 使 xFy成立，则称 F为 函数 (function)(或称作 映射
(mapping))。
对于函数 F,如果有 xFy,则记作 y＝ F(x),并称 y为 F在 x的值 。
举例 判断下列关系是否为函数
F1＝ {<x1,y1>,<x2,y2>,<x3,y2>}
F2＝ {<x1,y1>,<x1,y2>}
是函数不是函数说明
函数是特殊的二元关系。
函数的定义域为 dom F,而不是它的真子集。
一个 x只能对应唯一的 y。
定义 8.2 设 F,G 为函数，则 F＝ G? F?G∧G?F
由定义可知，两个函数 F和 G相等,一定满足下面两个条件：
（ 1） dom F＝ dom G
（ 2）?x∈dom F ＝ dom G,都有 F(x)＝ G(x)
例如 函数 F(x)＝ (x2?1)/(x+1),G(x)＝ x?1不相等,因为
dom F＝ {x|x∈ R∧ x ≠ -1}
dom G＝ R
显然,dom F≠dom G,所以两个函数不相等。
函数相等定义 8.3 设 A,B为集合，如果 f 为函数,dom f＝ A,ran f?B，
则称 f 为 从 A到 B的函数,记作 f,A→B 。
例如,f,N→N,f(x)＝ 2x是从 N到 N的函数，
g,N→N,g(x)＝ 2也是从 N到 N的函数。
定义 8.4 所有从 A到 B的函数的集合记作 BA,读作,B上 A”，
符号化表示为 BA＝ {f | f,A→B} 。
从 A到 B的函数例 8.2 设 A＝ {1,2,3},B＝ {a,b},求 BA。
解答 BA＝ { f0,f1,f2,f3,f4,f5,f6,f7} 。 其中
f 0＝ {<1,a>,<2,a>,<3,a>}
f 1＝ {<1,a>,<2,a>,<3,b>}
f 2＝ {<1,a>,<2,b>,<3,a>}
f 3＝ {<1,a>,<2,b>,<3,b>}
f 4＝ {<1,b>,<2,a>,<3,a>}
f 5＝ {<1,b>,<2,a>,<3,b>}
f 6＝ {<1,b>,<2,b>,<3,a>}
f 7＝ {<1,b>,<2,b>,<3,b>}
例 8.2
说明
若 |A|＝ m,|B|＝ n,且 m,n>0,则 |BA|＝ nm。
当 A或 B至少有一个集合是空集时：
A＝?且 B＝?，则 BA＝＝ {?}。
A＝?且 B≠?，则 BA＝ B?＝ {?}。
A≠?且 B＝?,则 BA＝?A＝?。
定义 8.5 设函数 f,A→B,A1?A,B1?B。
（ 1） 令 f(A1)＝ {f(x)|x∈A 1},称 f(A1)为 A1在 f 下的像 (image)。
特别地，当 A1＝ A时，称 f(A)为函数的像 。
（ 2） 令 f?1(B1)＝ {x|x∈A∧ f(x)∈B 1},称 f?1(B1)为 B1在 f 下的 完全原像 (preimage) 。
说明函数的像和完全原像
注意区别函数的值和像两个不同的概念。
函数值 f(x)∈B,而函数的像 f(A1)?B。
讨论
设 B1?B,显然 B1在 f 下的原像 f-1(B1)是 A的子集。
设 A1?A,那么 f(A1)?B。
f(A1)的完全原像就是 f-1(f(A1))。
一般来说,f-1(f(A1))≠A 1,但是 A1? f-1(f(A1))。
例如函数 f:{1,2,3}→{0,1},满足
f(1)＝ f(2)＝ 0,f(3)＝ 1
令 A1＝ {1},那么
f-1(f(A1))＝ f-1(f({1}))＝ f-1({0})＝ {1,2}
这时,A1是 f-1(f(A1))的真子集。
例 8.3设 f:N→N,且令 A＝ {0,1},B＝ {2},求 f(A)和 f?1(B)。
/2()
1
xxfx
xx
若 为 偶 数若 为 奇 数解答
f(A)＝ f({0,1})＝ {f(0),f(1)}＝ {0,2}
f?1(B)＝ f?1({2})＝ {1,4} (因为 f(1)＝ 2,f(4)＝ 2)
例 8.3
定义 8.6设 f:A→ B，
（ 1） 若 ran f＝ B,则称 f:A→ B是 满射 (surjection)的 。
（ 2） 若?y∈ ran f 都存在 唯一的 x∈ A使得 f(x)＝ y,则称
f:A→ B是 单射 (injection)的 。
（ 3） 若 f 既是满射又是单射的,则称 f:A→ B是 双射 (bijection)
的 (一一映像 (one-to-one mapping)) 。
说明满射、入射、双射
如果 f:A→ B是满射的，则对于任意的 y∈ B,都存在 x∈ A，
使得 f(x)＝ y。
如果 f:A→ B是单射的，则对于 x1,x2?A且 x1≠ x2,一定有 f(x1)≠ f(x2)。
换句话说，如果对于 x1,x2?A有 f(x1)＝ f(x2),则一定有
x1＝ x2。
不同类型的对应关系的示例
a
b
c
1
2
3
4
a
b
c
1
2
3
4
a
b
c
1
2
3
4d
a
b
c
1
2
3
4d
a
b
c
1
2
3
d
单射 不是函数双射 函数 满射例 8.4 判断下面函数是否为单射、满射、双射的，为什么?
(1) f,R→ R,f(x)= -x2+2x-1
(2) f,Z+→ R,f(x)=ln x,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+为正实数集。
例 8.4
（ 1） f 在 x=1取得极大值 0。 既不是单射也不是满射的 。
（ 2） f 是单调上升的，是单射的，但不满射 。 ranf={ln1,ln2,…} 。
（ 3） f 是满射的,但不是单射的，例如 f(1.5)=f(1.2)=1
（ 4） f 是满射、单射、双射的，因为它是单调函数并且 ran f=R。
（ 5） f 有极小值 f(1)=2。 该函数既不是单射的，也不是满射的 。
分析 实数集合上函数性质的判断方法例 8.5
例 8.5 对于以下各题给定的 A,B和 f,判断是否构成函数
f:A→ B。 如果是，说明 f:A→B 是否为单射、满射和双射的，
并根据要求进行计算。
(1)A＝ {1,2,3,4,5},B＝ {6,7,8,9,10}，
f＝ {<1,8>,<3,9>,<4,10>,<2,6>,<5,9>}
能构成 f:A→ B，
f 不是单射的，因为 f(3)＝ f(5)＝ 9,
f 不是满射的，因为 7?ran f。
(1)A＝ {1,2,3,4,5},B＝ {6,7,8,9,10}，
f＝ {<1,7>,<2,6>,<4,5>,<1,9>,<5,10>}
不能构成 f:A→ B,因为 <1,7>∈ f 且 <1,9>∈ f 。
例 8.5
(3)A＝ {1,2,3,4,5},B＝ {6,7,8,9,10}，
f＝ {<1,8>,<3,10>,<2,6>,<4,9>}
不能构成 f:A→ B,因为 dom f＝ {1,2,3,4}≠ A。
(4)A＝ B＝ R,f(x)＝ x
能构成 f:A→ B,且 f 是双射的 。
(5)A＝ B＝ R+,f(x)＝ x/(x2+1)（?x∈R + ）
能构成 f:A→ B,但 f 既不是单射的也不是满射的。
因为该函数在 x＝ 1 取得极大值 f(1)＝ 1/2,函数不是单调的，且 ran f ≠R +。
例 8.5
(6)A＝ B＝ R× R,f (<x,y>)＝ <x+y,x-y>
令 L＝ {<x,y>|x,y∈R∧ y＝ x+1},计算 f(L)。
能构成 f:A→ B,且 f 是双射的 。
f(L)＝ {<x+(x+1),x-(x+1)>|x∈R}
＝ {<2x+1,-1>|x∈R} ＝ R× {-1}
(7)A＝ N× N,B＝ N,f(<x,y>)＝ |x2-y2|
计算 f(N× {0}),f-1＝ ({0})。
能构成 f:A→ B,但 f 既不是单射也不是满射的。
因为 f(<1,1>)＝ f(<2,2>)＝ 0,且 2?ran f。
f(N× {0})＝ {n2-02|n∈N} ＝ {n2|n∈N}
f-1({0})＝ {<n,n>|n∈N}
例 8.6
例 8.6 对于给定的集合 A和 B构造双射函数 f:A→B 。
1） A＝ P({1,2,3}),B＝ {0,1}{1,2,3}
（ 2） A＝ [0,1],B＝ [1/4,1/2]
（ 3） A＝ Z,B＝ N
（ 4） A＝ [?/2,3?/2],B＝ [?1,1]
例 8.6的解答
（ 1） A＝ P({1,2,3}),B＝ {0,1}{1,2,3}
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
例 8.6的解答
（ 2） A＝ [0,1],B＝ [1/4,1/2]
令 f,A→B,f(x)＝ (x+1)/4。
（ 3） A＝ Z,B＝ N
将 Z中元素以下列顺序排列并与 N中元素对应：
Z,0?1 1?2 2?3 3 …
↓ ↓ ↓ ↓ ↓ ↓ ↓
N,0 1 2 3 4 5 6 …
则这种对应所表示的函数是：
20Z,( )
2 1 0
xxf N f x
xx
：
（ 4） A=[?/2,3?/2],B=[?1,1]
令 f,A→B,f(x)＝ sin x。
常用函数 — 常 函数和恒等函数
设 f,A→B,如果存在 c∈ B,使得对所有的 x∈ A都有 f(x)
＝ c,则称 f,A→B是 常函数 。
设 f,A→B,对所有的 x∈ A都有 IA(x)＝ x,称 IA为 A上的 恒等函数 。
常用函数 — 单调递增函数
设 <A,≤>,<B,≤>为偏序集,f,A→B,如果对任意的 x1,
x2∈ A,x1＜ x2,就有 f(x1)≤ f(x2),则称 f为 单调递增 的 ；
如果对任意的 x1,x2∈ A,x1＜ x2,就有 f(x1)＜ f(x2),则称 f为 严格单调递增 的 。
类似的也可以定义单调递减和严格单调递减的函数 。
举例,f,R→R,f(x)＝ x+1是严格单调递增的。
偏序集 <P({a,b}),R?>,<{0,1},≤>,R?为包含关系,≤ 为一般的小于等于关系。
令 f,P({a,b})→ {0,1},f(?)＝ f({a})＝ f({b})＝ 0,f({a,b})=1，
f是单调递增的,但不是严格单调递增的 。
常用函数 — 特 征函数
设 A为集合，对于任意的 AA,A?的 特征函数
A?,A→{0,1}定义为
1,a∈ A?
0,a∈ A?AA?(a) ＝
举例,A的每一个子集 A?都对应于一个特征函数，不同的子集对应于不同的特征函数。
例如 A＝ {a,b,c},则有
＝ {<a,0>,<b,0>,<c,0>},?{a} ＝ {<a,1>,<b,0>,<c,0 >}
{a,b} ＝ {<a,1>,<b,1>,<c,0 >}
常用函数 — 自 然映射
设 R是 A上的等价关系,令
g,A→A/R
g(a)=[a],?a∈ A
称 g是从 A到商集 A/R的 自然映射 。
给定集合 A和 A上的等价关系 R,就可以确定一个自然映射 g
,A→A/R。
例如 A＝ {1,2,3},R＝ {<1,2>,<2,1>}∪ IA
g(1)＝ g(2)＝ {1,2},g(3)＝ {3}
不同的等价关系确定不同的自然映射，其中恒等关系所确定的自然映射是双射,而其他的自然映射一般来说只是满射。
定 义在自然数集合上的计数函数
对于给定规模为 n的输入，计算算法所做基本运算的次数，
将这个次数表示为输入规模的函数。
– 排序和检索问题的基本运算是比较。
– 矩阵乘法的基本运算是元素的相乘。
估计算法在最坏情况下所做基本运算的次数记为 W(n)。
估计算法在平均情况下所做基本运算的次数记为 A(n)。
设 f是定义在自然数集合上的函数，当 n变得很大时,函数值
f(n)的增长取决于函数的阶 。阶越高的函数，算法的复杂度就越高，同时意味着算法的效率越低。
算法分析的主要工作就是估计复杂度函数的阶 。阶可以是：
n,n2,n3,nlog n,log n,2n ……
定 义在自然数集合上的计数函数
若存在正数 c和 n0,使得对一切 n≥ n0,有 0≤ f(n)≤ cg(n)，
记作 f(n)＝ O(g(n))。
若存在正数 c和 n0,使得对一切 n≥ n0,有 0≤ cg(n)≤ f(n)，
记作 f(n)＝ Ω(g(n))。
若 f(n)＝ O(g(n))且 f(n)＝ Ω(g(n)),则 f(n)＝ Θ(g(n))。
例如
– f(n)＝ 1/2 n2-3n,则 f(n)＝ Θ(n2)
– g(n)＝ 6n3,则 g(n)＝ Θ(n3)
8.2 函数的复合与反函数
函数的复合就是关系的右复合,一切和关系右复合有关的定理都适用于函数的复合。 本节重点考虑在复合中特有的性质。
定理 8.1(复合函数基本定理 )
定理 8.1 设 F,G是函数,则 F?G 也是函数，且满足
（ 1） dom (F?G)＝ {x|x∈ dom F∧ F(x)∈ dom G}
（ 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为函数 。
定理 8.1的证明定理 8.1的证明任取 x,(要证明 dom (F?G)＝ {x|x∈ dom F∧ F(x)∈ dom G})
x∈ dom (F?G)
t?y(<x,t>∈ F ∧ <t,y>∈ G)
t(x∈ dom F ∧ t＝ F(x) ∧ t∈ dom G)
x∈ {x|x∈ dom F ∧ F(x)∈ dom G}
所以（ 1）得证。
任取 x,（ 要证明?x∈ dom (F?G),有 F?G(x)＝ G(F(x))）
x∈ dom F ∧ F(x)∈ dom G
<x,F(x)>∈ F ∧ <F(x),G(F(x))>∈ G
<x,G(F(x))>∈ F?G
x∈ dom(F?G) ∧ F?G(x)＝ G(F(x))
所以（ 2）得证。
推论 1设 F,G,H为函数,则 (F?G)?H和 F?(G?H)都是函数,且
(F?G)?H=F?(G?H)
证明,由定理 8.1（复合函数基本定理）和定理 7.2（关系合成具有结合性）得证。
定理 8.1的推论 1
推论 2设 f,A→B,g,B→C,则 f?g,A→C,且?x∈ A都有
f?g(x)=g(f(x))。
证明,由定理 8.1（复合函数基本定理）可知 f?g是函数，且
dom (f?g) ＝ {x|x∈ dom f ∧ f(x)∈ dom g}
＝ {x|x∈ A ∧ f(x)∈ B}
＝ A
ran (f?g)? ran g? C
因此 f?g,A→C,且?x∈ A有 f?g(x)＝ g(f(x))。
定理 8.1的推论 2
定理 8.2 设 f,A→B,g,B→C。
（ 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也是双射的。
分析说明函数的复合运算的性质该定理说明函数的复合能够保持函数单射、满射、双射的性质。
定理 8.2的证明
(1)如果 f,A→B,g,B→C都是满射的,则 f?g,A→C也是满射的 。
证明：
任取 c∈ C,由 g,B→C的满射性,所以?b∈ B使得 g(b)=c。
对于这个 b,由 f,A→B的满射性,所以?a∈ A使得 f(a)=b。
由合成定理有
f?g(a) ＝ g(f(a))＝ g(b)＝ c
所以,f?g,A→C是满射的。
定理 8.2的证明
( 2 ) 如果 f,A→B,g,B→C 都 是单射 的,则 f?g,A→C 也是单射的 。
证明,假设存在 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。
所以,fog,A→C是单射的 。
( 3 ) 如果 f,A→B,g,B→C都是双射的,则 f?g,A→C也是双射的 。
证明：由 （ 1） 和 （ 2） 得证 。
定理 8.2之逆不为真
考虑集合 A＝ {a1,a2,a3},B＝ {b1,b2,b3,b4},C＝ {c1,c2,c3}。
令 f ＝ {<a1,b1>,<a2,b2>,<a3,b3>}
g＝ {<b1,c1>,<b2,c2>,<b3,c3>,<b4,c3>}
则 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不是满射的。
定理 8.3
定理 8.3 设 f,A?B,则 f ＝ f o IB ＝ IAof
证明,由定理 8.1的推论 2可知
f o IB,A?B 和 IAof,A?B
任取 <x,y>，
<x,y>∈ f
<x,y> ∈ f ∧ y?B
<x,y> ∈ f ∧ <y,y>?IB
<x,y> ∈ f o IB
所以,f? f o IB
<x,y>∈ f o IB
t(<x,t> ∈ f ∧ <t,y>?IB )
<x,t> ∈ f ∧ t=y
<x,y> ∈ f
所以,f o IB? f
所以,f ＝ f o IB
同理可证 f ＝ IAof
什么样的函数 f,A→B,它的逆 f?1是从 B到 A的函数呢？
任给函数 F,它的逆 F?1不一定是函数,只是一个二元关系 。
F＝ {<x1,y1>,<x2,y1>}
F -1＝ {<y1,x1>,<y1,x2>}
任给单射函数 f,A→B,则 f?1是函数,且是从 ran f到 A的双射函数,但不一定是从 B到 A的双射函数 。
因为对于某些 y∈ B－ ran f,f -1没有值与之对应 。
任给满射函数 f,A→B,则 f?1不一定是函数 。
对于双射函数 f,A→B,f?1,B→A是从 B到 A的双射函数。
反函数定理 8.4 设 f,A→B是双射的,则 f?1,B→A也是双射的 。
证明,
先证明 f-?1,B→A是函数,且 dom f?1＝ B,ran f?1＝ A。
因为 f 是函数,所以 f?1是关系,且
dom f?1＝ ran f ＝ B,ran f?1＝ dom f ＝ A，
对于任意的 x∈ B＝ dom f?1，
假设有 y1,y2∈ A,使得 <x,y1>∈ f?1∧ <x,y2>∈ f?1成立，
则由逆的定义有,<y1,x>∈ f∧ <y2,x>∈ f。
根据 f 的单射性，可得 y1＝ y2。
所以,f-?1是函数。
反函数存在的条件
再证明 f-?1,B→A的双射性质 。
（证明单射 ） 若存在 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 是单射的。
（证明满射 ） 对于任意的 y∈ A,因为 f 是双射的,
所以必存在 x∈ B,使得 <y,x>∈ f,所以 <x,y>∈ f?1，
所以,f?1 是满射的。
综上所述,f?1 是双射函数。
说明定理 8.4的证明对于双射函数 f,A→B,称 f-?1,B→A 是它的反函数。
反函数的性质定理 8.5 设 f,A→B是双射的,则 f-?1?f = IB,f? f-?1 = IA
证明,根据定理可知 f-?1,B→A也是双射的,且
f-?1?f,B→B,f? f-?1,A→A。
任取 <x,y>
<x,y>? f?1?f
t( <x,t>? f?1 ∧ <t,y>? f )
t( <t,x>? f ∧ <t,y>? f )
x=y ∧ x,y? B
<x,y>?IB
所以,f-?1?f? IB
<x,y>? IB
x＝ y ∧ x,y? B
t( <t,x>? f ∧ <t,y>? f )
t( <x,t>? f?1 ∧ <t,y>? f )
<x,y>? f-?1?f
所以,IB? f-?1?f
综上所述,f-?1?f ＝ IB。 同理可证 f? f-?1 ＝ IA
例 8.8
例 8.8 设 f,R→R,g,R→R
求 f?g,g?f。 如果 f 和 g 存在反函数，求出它们的反函数 。
解答
2 3
()
23
( ) 2
xx
fx
x
g x x
2
2
:
23
()
03
:
( 2) 1
()
21
f g R R
xx
f g x
x
g f R R
xx
g f x
x
g,R→R是双射的，它的反函数是
g?1,R→R,g?1(x)=x?2
本章主 要内容
函数的基本概念与性质 （ 单射,满射,双射 ） 。
函数的合成与反函数 。
本章学习要求
掌握函数,A到 B的函数,集合在函数下的像,集合在函数下的完全原像的概念及表示法；当 A与 B都是有穷集时
,会求 A到 B的函数的个数 。
掌握 A到 B的函数是单射,满射,和双射的定义及证明方法 。
掌握常函数,恒等函数,单调函数,特征函数,自然映射等概念 。
掌握合成函数的主要性质和求合成函数的方法 。
掌握反函数的概念及主要性质 。
对于任意的 <x,y>,<u,v>?R?R,有
:,
(,),
f R R R R
f x y x y x y
证明,任取 <u,v>?R?R,存在?R?R,使得,
22u v u v
(,),22u v u vf u v
(,) (,),,
,,
,,
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是满射的 。
因此 f是单射的 。
例题证明 f 既是满射的，也是单射的。其中例题令 X＝ {x1,x2,…,xm},Y={y1,y2,…,yn},问
（ 1） 有多少不同的由 X到 Y的关系？
（ 2） 有多少不同的 X到 Y的映射？
（ 3） 有多少不同的由 X到 Y的单射,双射？
解,（ 1） 有 2mn不同的由 X到 Y的关系 。
（ 2） 有 nm不同的 X到 Y的映射 。
（ 3） X到 Y的单射个数为：
若 m?n,有 0个单射 。
若 m＝ n,有 m!个单射 。
只有 m＝ n时,才存在 X到 Y的双射,个数为 m! 。
若 m?n,有 个单射 。m
nCm!
设 A,B,C,D是任意集合,f是 A到 B的双射,g是 C到 D的双射 。
令 h:A?C?B?D,且?<a,c>?A?C,h(<a,c>)=<f(a),g(c)>,那么 h是双射吗？ 请证明你的判断 。
证明,?先证明 h是满射 。
<b,d>?B?D,则 b?B,d?D，
因为 f是 A到 B的双射,g是 C到 D的双射,
所以,?a?A,c?C,使得 f(a)=b,g(c)=d，
也就是?<a,c>?A?C,使得 h(<a,c>)= <f(a),g(c)> =<b,d>,
所以,h是满射。
例题例题
再证 h是单射 。
<a1,c1>,<a2,c2>?A?C,若 h(<a1,c1>)= h(<a2,c2> ),则
<f(a1),g(c1)> = <f(a2),g(c2)>
所以,f(a1) = f(a2),g(c1) = g(c2)。
因为 f是 A到 B的双射,g是 C到 D的双射,
所以,a1 = a2,c1 = c2。
所以,<a1,c1>= <a2,c2>,
所以,h是单射 。
综上所述,h是双射 。
作业习题八,1,2,3,4,15,16,17,24
单射和满射的证明方法
证明函数 f:A→B 是满射的，基本方法是：
任取 y∈B,找到 x∈A (x与 y相关，可能是一个关于 y
的表达式 )或者证明存在 x∈A,使得 f(x)＝ y。
证明函数 f:A→B 是单射的，基本方法是：
假设 A中存在 x1和 x2,使得 f(x1)＝ f(x2),利用已知条件或者相关的定理 最终证明 x1＝ x2。
实数集合上函数性质的判断方法
对于实数集合上的函数，通常可以通过求导找到极值点。而有的极小值（或极大值）恰好是函数的最小值（或最大值），这样就可以求出 函数的值域,从而 判断函数是否为满射的 。
如果函数存在极值，那么可以断定函数不是单射的,因为在极值点两侧可以找到不相等的 x1和 x2满足 f(x1)＝ f(x2)。
证明函数不具有某种性质的一般方法就是给出反例。
为证明函数不是单射的，需要找到 x1≠ x2且 f(x1)＝ f(x2)。
有时可能不容易找到具体的 x1和 x2,但是可以证明这样的 x1和 x2
是存在的。
证明函数不是满射的一般方法就是找到 y∈B － ran f。
本章的主要内容
– 函数的定义
– 函数的性质
– 函数的逆
– 函数的合成
本章与后续各章的关系
– 是代数系统的基础
8.1 函数的定义与性质
8.2 函数的复合与反函数
8.3 一个电话系统的描述实例本章小结习题作业本章内容
8.1 函数的定义与性质定义 8.1 设 F为二元关系，若?x∈dom F,都存在 唯一的
y∈ran F 使 xFy成立，则称 F为 函数 (function)(或称作 映射
(mapping))。
对于函数 F,如果有 xFy,则记作 y＝ F(x),并称 y为 F在 x的值 。
举例 判断下列关系是否为函数
F1＝ {<x1,y1>,<x2,y2>,<x3,y2>}
F2＝ {<x1,y1>,<x1,y2>}
是函数不是函数说明
函数是特殊的二元关系。
函数的定义域为 dom F,而不是它的真子集。
一个 x只能对应唯一的 y。
定义 8.2 设 F,G 为函数，则 F＝ G? F?G∧G?F
由定义可知，两个函数 F和 G相等,一定满足下面两个条件：
（ 1） dom F＝ dom G
（ 2）?x∈dom F ＝ dom G,都有 F(x)＝ G(x)
例如 函数 F(x)＝ (x2?1)/(x+1),G(x)＝ x?1不相等,因为
dom F＝ {x|x∈ R∧ x ≠ -1}
dom G＝ R
显然,dom F≠dom G,所以两个函数不相等。
函数相等定义 8.3 设 A,B为集合，如果 f 为函数,dom f＝ A,ran f?B，
则称 f 为 从 A到 B的函数,记作 f,A→B 。
例如,f,N→N,f(x)＝ 2x是从 N到 N的函数，
g,N→N,g(x)＝ 2也是从 N到 N的函数。
定义 8.4 所有从 A到 B的函数的集合记作 BA,读作,B上 A”，
符号化表示为 BA＝ {f | f,A→B} 。
从 A到 B的函数例 8.2 设 A＝ {1,2,3},B＝ {a,b},求 BA。
解答 BA＝ { f0,f1,f2,f3,f4,f5,f6,f7} 。 其中
f 0＝ {<1,a>,<2,a>,<3,a>}
f 1＝ {<1,a>,<2,a>,<3,b>}
f 2＝ {<1,a>,<2,b>,<3,a>}
f 3＝ {<1,a>,<2,b>,<3,b>}
f 4＝ {<1,b>,<2,a>,<3,a>}
f 5＝ {<1,b>,<2,a>,<3,b>}
f 6＝ {<1,b>,<2,b>,<3,a>}
f 7＝ {<1,b>,<2,b>,<3,b>}
例 8.2
说明
若 |A|＝ m,|B|＝ n,且 m,n>0,则 |BA|＝ nm。
当 A或 B至少有一个集合是空集时：
A＝?且 B＝?，则 BA＝＝ {?}。
A＝?且 B≠?，则 BA＝ B?＝ {?}。
A≠?且 B＝?,则 BA＝?A＝?。
定义 8.5 设函数 f,A→B,A1?A,B1?B。
（ 1） 令 f(A1)＝ {f(x)|x∈A 1},称 f(A1)为 A1在 f 下的像 (image)。
特别地，当 A1＝ A时，称 f(A)为函数的像 。
（ 2） 令 f?1(B1)＝ {x|x∈A∧ f(x)∈B 1},称 f?1(B1)为 B1在 f 下的 完全原像 (preimage) 。
说明函数的像和完全原像
注意区别函数的值和像两个不同的概念。
函数值 f(x)∈B,而函数的像 f(A1)?B。
讨论
设 B1?B,显然 B1在 f 下的原像 f-1(B1)是 A的子集。
设 A1?A,那么 f(A1)?B。
f(A1)的完全原像就是 f-1(f(A1))。
一般来说,f-1(f(A1))≠A 1,但是 A1? f-1(f(A1))。
例如函数 f:{1,2,3}→{0,1},满足
f(1)＝ f(2)＝ 0,f(3)＝ 1
令 A1＝ {1},那么
f-1(f(A1))＝ f-1(f({1}))＝ f-1({0})＝ {1,2}
这时,A1是 f-1(f(A1))的真子集。
例 8.3设 f:N→N,且令 A＝ {0,1},B＝ {2},求 f(A)和 f?1(B)。
/2()
1
xxfx
xx
若 为 偶 数若 为 奇 数解答
f(A)＝ f({0,1})＝ {f(0),f(1)}＝ {0,2}
f?1(B)＝ f?1({2})＝ {1,4} (因为 f(1)＝ 2,f(4)＝ 2)
例 8.3
定义 8.6设 f:A→ B，
（ 1） 若 ran f＝ B,则称 f:A→ B是 满射 (surjection)的 。
（ 2） 若?y∈ ran f 都存在 唯一的 x∈ A使得 f(x)＝ y,则称
f:A→ B是 单射 (injection)的 。
（ 3） 若 f 既是满射又是单射的,则称 f:A→ B是 双射 (bijection)
的 (一一映像 (one-to-one mapping)) 。
说明满射、入射、双射
如果 f:A→ B是满射的，则对于任意的 y∈ B,都存在 x∈ A，
使得 f(x)＝ y。
如果 f:A→ B是单射的，则对于 x1,x2?A且 x1≠ x2,一定有 f(x1)≠ f(x2)。
换句话说，如果对于 x1,x2?A有 f(x1)＝ f(x2),则一定有
x1＝ x2。
不同类型的对应关系的示例
a
b
c
1
2
3
4
a
b
c
1
2
3
4
a
b
c
1
2
3
4d
a
b
c
1
2
3
4d
a
b
c
1
2
3
d
单射 不是函数双射 函数 满射例 8.4 判断下面函数是否为单射、满射、双射的，为什么?
(1) f,R→ R,f(x)= -x2+2x-1
(2) f,Z+→ R,f(x)=ln x,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+为正实数集。
例 8.4
（ 1） f 在 x=1取得极大值 0。 既不是单射也不是满射的 。
（ 2） f 是单调上升的，是单射的，但不满射 。 ranf={ln1,ln2,…} 。
（ 3） f 是满射的,但不是单射的，例如 f(1.5)=f(1.2)=1
（ 4） f 是满射、单射、双射的，因为它是单调函数并且 ran f=R。
（ 5） f 有极小值 f(1)=2。 该函数既不是单射的，也不是满射的 。
分析 实数集合上函数性质的判断方法例 8.5
例 8.5 对于以下各题给定的 A,B和 f,判断是否构成函数
f:A→ B。 如果是，说明 f:A→B 是否为单射、满射和双射的，
并根据要求进行计算。
(1)A＝ {1,2,3,4,5},B＝ {6,7,8,9,10}，
f＝ {<1,8>,<3,9>,<4,10>,<2,6>,<5,9>}
能构成 f:A→ B，
f 不是单射的，因为 f(3)＝ f(5)＝ 9,
f 不是满射的，因为 7?ran f。
(1)A＝ {1,2,3,4,5},B＝ {6,7,8,9,10}，
f＝ {<1,7>,<2,6>,<4,5>,<1,9>,<5,10>}
不能构成 f:A→ B,因为 <1,7>∈ f 且 <1,9>∈ f 。
例 8.5
(3)A＝ {1,2,3,4,5},B＝ {6,7,8,9,10}，
f＝ {<1,8>,<3,10>,<2,6>,<4,9>}
不能构成 f:A→ B,因为 dom f＝ {1,2,3,4}≠ A。
(4)A＝ B＝ R,f(x)＝ x
能构成 f:A→ B,且 f 是双射的 。
(5)A＝ B＝ R+,f(x)＝ x/(x2+1)（?x∈R + ）
能构成 f:A→ B,但 f 既不是单射的也不是满射的。
因为该函数在 x＝ 1 取得极大值 f(1)＝ 1/2,函数不是单调的，且 ran f ≠R +。
例 8.5
(6)A＝ B＝ R× R,f (<x,y>)＝ <x+y,x-y>
令 L＝ {<x,y>|x,y∈R∧ y＝ x+1},计算 f(L)。
能构成 f:A→ B,且 f 是双射的 。
f(L)＝ {<x+(x+1),x-(x+1)>|x∈R}
＝ {<2x+1,-1>|x∈R} ＝ R× {-1}
(7)A＝ N× N,B＝ N,f(<x,y>)＝ |x2-y2|
计算 f(N× {0}),f-1＝ ({0})。
能构成 f:A→ B,但 f 既不是单射也不是满射的。
因为 f(<1,1>)＝ f(<2,2>)＝ 0,且 2?ran f。
f(N× {0})＝ {n2-02|n∈N} ＝ {n2|n∈N}
f-1({0})＝ {<n,n>|n∈N}
例 8.6
例 8.6 对于给定的集合 A和 B构造双射函数 f:A→B 。
1） A＝ P({1,2,3}),B＝ {0,1}{1,2,3}
（ 2） A＝ [0,1],B＝ [1/4,1/2]
（ 3） A＝ Z,B＝ N
（ 4） A＝ [?/2,3?/2],B＝ [?1,1]
例 8.6的解答
（ 1） A＝ P({1,2,3}),B＝ {0,1}{1,2,3}
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
例 8.6的解答
（ 2） A＝ [0,1],B＝ [1/4,1/2]
令 f,A→B,f(x)＝ (x+1)/4。
（ 3） A＝ Z,B＝ N
将 Z中元素以下列顺序排列并与 N中元素对应：
Z,0?1 1?2 2?3 3 …
↓ ↓ ↓ ↓ ↓ ↓ ↓
N,0 1 2 3 4 5 6 …
则这种对应所表示的函数是：
20Z,( )
2 1 0
xxf N f x
xx
：
（ 4） A=[?/2,3?/2],B=[?1,1]
令 f,A→B,f(x)＝ sin x。
常用函数 — 常 函数和恒等函数
设 f,A→B,如果存在 c∈ B,使得对所有的 x∈ A都有 f(x)
＝ c,则称 f,A→B是 常函数 。
设 f,A→B,对所有的 x∈ A都有 IA(x)＝ x,称 IA为 A上的 恒等函数 。
常用函数 — 单调递增函数
设 <A,≤>,<B,≤>为偏序集,f,A→B,如果对任意的 x1,
x2∈ A,x1＜ x2,就有 f(x1)≤ f(x2),则称 f为 单调递增 的 ；
如果对任意的 x1,x2∈ A,x1＜ x2,就有 f(x1)＜ f(x2),则称 f为 严格单调递增 的 。
类似的也可以定义单调递减和严格单调递减的函数 。
举例,f,R→R,f(x)＝ x+1是严格单调递增的。
偏序集 <P({a,b}),R?>,<{0,1},≤>,R?为包含关系,≤ 为一般的小于等于关系。
令 f,P({a,b})→ {0,1},f(?)＝ f({a})＝ f({b})＝ 0,f({a,b})=1，
f是单调递增的,但不是严格单调递增的 。
常用函数 — 特 征函数
设 A为集合，对于任意的 AA,A?的 特征函数
A?,A→{0,1}定义为
1,a∈ A?
0,a∈ A?AA?(a) ＝
举例,A的每一个子集 A?都对应于一个特征函数，不同的子集对应于不同的特征函数。
例如 A＝ {a,b,c},则有
＝ {<a,0>,<b,0>,<c,0>},?{a} ＝ {<a,1>,<b,0>,<c,0 >}
{a,b} ＝ {<a,1>,<b,1>,<c,0 >}
常用函数 — 自 然映射
设 R是 A上的等价关系,令
g,A→A/R
g(a)=[a],?a∈ A
称 g是从 A到商集 A/R的 自然映射 。
给定集合 A和 A上的等价关系 R,就可以确定一个自然映射 g
,A→A/R。
例如 A＝ {1,2,3},R＝ {<1,2>,<2,1>}∪ IA
g(1)＝ g(2)＝ {1,2},g(3)＝ {3}
不同的等价关系确定不同的自然映射，其中恒等关系所确定的自然映射是双射,而其他的自然映射一般来说只是满射。
定 义在自然数集合上的计数函数
对于给定规模为 n的输入，计算算法所做基本运算的次数，
将这个次数表示为输入规模的函数。
– 排序和检索问题的基本运算是比较。
– 矩阵乘法的基本运算是元素的相乘。
估计算法在最坏情况下所做基本运算的次数记为 W(n)。
估计算法在平均情况下所做基本运算的次数记为 A(n)。
设 f是定义在自然数集合上的函数，当 n变得很大时,函数值
f(n)的增长取决于函数的阶 。阶越高的函数，算法的复杂度就越高，同时意味着算法的效率越低。
算法分析的主要工作就是估计复杂度函数的阶 。阶可以是：
n,n2,n3,nlog n,log n,2n ……
定 义在自然数集合上的计数函数
若存在正数 c和 n0,使得对一切 n≥ n0,有 0≤ f(n)≤ cg(n)，
记作 f(n)＝ O(g(n))。
若存在正数 c和 n0,使得对一切 n≥ n0,有 0≤ cg(n)≤ f(n)，
记作 f(n)＝ Ω(g(n))。
若 f(n)＝ O(g(n))且 f(n)＝ Ω(g(n)),则 f(n)＝ Θ(g(n))。
例如
– f(n)＝ 1/2 n2-3n,则 f(n)＝ Θ(n2)
– g(n)＝ 6n3,则 g(n)＝ Θ(n3)
8.2 函数的复合与反函数
函数的复合就是关系的右复合,一切和关系右复合有关的定理都适用于函数的复合。 本节重点考虑在复合中特有的性质。
定理 8.1(复合函数基本定理 )
定理 8.1 设 F,G是函数,则 F?G 也是函数，且满足
（ 1） dom (F?G)＝ {x|x∈ dom F∧ F(x)∈ dom G}
（ 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为函数 。
定理 8.1的证明定理 8.1的证明任取 x,(要证明 dom (F?G)＝ {x|x∈ dom F∧ F(x)∈ dom G})
x∈ dom (F?G)
t?y(<x,t>∈ F ∧ <t,y>∈ G)
t(x∈ dom F ∧ t＝ F(x) ∧ t∈ dom G)
x∈ {x|x∈ dom F ∧ F(x)∈ dom G}
所以（ 1）得证。
任取 x,（ 要证明?x∈ dom (F?G),有 F?G(x)＝ G(F(x))）
x∈ dom F ∧ F(x)∈ dom G
<x,F(x)>∈ F ∧ <F(x),G(F(x))>∈ G
<x,G(F(x))>∈ F?G
x∈ dom(F?G) ∧ F?G(x)＝ G(F(x))
所以（ 2）得证。
推论 1设 F,G,H为函数,则 (F?G)?H和 F?(G?H)都是函数,且
(F?G)?H=F?(G?H)
证明,由定理 8.1（复合函数基本定理）和定理 7.2（关系合成具有结合性）得证。
定理 8.1的推论 1
推论 2设 f,A→B,g,B→C,则 f?g,A→C,且?x∈ A都有
f?g(x)=g(f(x))。
证明,由定理 8.1（复合函数基本定理）可知 f?g是函数，且
dom (f?g) ＝ {x|x∈ dom f ∧ f(x)∈ dom g}
＝ {x|x∈ A ∧ f(x)∈ B}
＝ A
ran (f?g)? ran g? C
因此 f?g,A→C,且?x∈ A有 f?g(x)＝ g(f(x))。
定理 8.1的推论 2
定理 8.2 设 f,A→B,g,B→C。
（ 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也是双射的。
分析说明函数的复合运算的性质该定理说明函数的复合能够保持函数单射、满射、双射的性质。
定理 8.2的证明
(1)如果 f,A→B,g,B→C都是满射的,则 f?g,A→C也是满射的 。
证明：
任取 c∈ C,由 g,B→C的满射性,所以?b∈ B使得 g(b)=c。
对于这个 b,由 f,A→B的满射性,所以?a∈ A使得 f(a)=b。
由合成定理有
f?g(a) ＝ g(f(a))＝ g(b)＝ c
所以,f?g,A→C是满射的。
定理 8.2的证明
( 2 ) 如果 f,A→B,g,B→C 都 是单射 的,则 f?g,A→C 也是单射的 。
证明,假设存在 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。
所以,fog,A→C是单射的 。
( 3 ) 如果 f,A→B,g,B→C都是双射的,则 f?g,A→C也是双射的 。
证明：由 （ 1） 和 （ 2） 得证 。
定理 8.2之逆不为真
考虑集合 A＝ {a1,a2,a3},B＝ {b1,b2,b3,b4},C＝ {c1,c2,c3}。
令 f ＝ {<a1,b1>,<a2,b2>,<a3,b3>}
g＝ {<b1,c1>,<b2,c2>,<b3,c3>,<b4,c3>}
则 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不是满射的。
定理 8.3
定理 8.3 设 f,A?B,则 f ＝ f o IB ＝ IAof
证明,由定理 8.1的推论 2可知
f o IB,A?B 和 IAof,A?B
任取 <x,y>，
<x,y>∈ f
<x,y> ∈ f ∧ y?B
<x,y> ∈ f ∧ <y,y>?IB
<x,y> ∈ f o IB
所以,f? f o IB
<x,y>∈ f o IB
t(<x,t> ∈ f ∧ <t,y>?IB )
<x,t> ∈ f ∧ t=y
<x,y> ∈ f
所以,f o IB? f
所以,f ＝ f o IB
同理可证 f ＝ IAof
什么样的函数 f,A→B,它的逆 f?1是从 B到 A的函数呢？
任给函数 F,它的逆 F?1不一定是函数,只是一个二元关系 。
F＝ {<x1,y1>,<x2,y1>}
F -1＝ {<y1,x1>,<y1,x2>}
任给单射函数 f,A→B,则 f?1是函数,且是从 ran f到 A的双射函数,但不一定是从 B到 A的双射函数 。
因为对于某些 y∈ B－ ran f,f -1没有值与之对应 。
任给满射函数 f,A→B,则 f?1不一定是函数 。
对于双射函数 f,A→B,f?1,B→A是从 B到 A的双射函数。
反函数定理 8.4 设 f,A→B是双射的,则 f?1,B→A也是双射的 。
证明,
先证明 f-?1,B→A是函数,且 dom f?1＝ B,ran f?1＝ A。
因为 f 是函数,所以 f?1是关系,且
dom f?1＝ ran f ＝ B,ran f?1＝ dom f ＝ A，
对于任意的 x∈ B＝ dom f?1，
假设有 y1,y2∈ A,使得 <x,y1>∈ f?1∧ <x,y2>∈ f?1成立，
则由逆的定义有,<y1,x>∈ f∧ <y2,x>∈ f。
根据 f 的单射性，可得 y1＝ y2。
所以,f-?1是函数。
反函数存在的条件
再证明 f-?1,B→A的双射性质 。
（证明单射 ） 若存在 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 是单射的。
（证明满射 ） 对于任意的 y∈ A,因为 f 是双射的,
所以必存在 x∈ B,使得 <y,x>∈ f,所以 <x,y>∈ f?1，
所以,f?1 是满射的。
综上所述,f?1 是双射函数。
说明定理 8.4的证明对于双射函数 f,A→B,称 f-?1,B→A 是它的反函数。
反函数的性质定理 8.5 设 f,A→B是双射的,则 f-?1?f = IB,f? f-?1 = IA
证明,根据定理可知 f-?1,B→A也是双射的,且
f-?1?f,B→B,f? f-?1,A→A。
任取 <x,y>
<x,y>? f?1?f
t( <x,t>? f?1 ∧ <t,y>? f )
t( <t,x>? f ∧ <t,y>? f )
x=y ∧ x,y? B
<x,y>?IB
所以,f-?1?f? IB
<x,y>? IB
x＝ y ∧ x,y? B
t( <t,x>? f ∧ <t,y>? f )
t( <x,t>? f?1 ∧ <t,y>? f )
<x,y>? f-?1?f
所以,IB? f-?1?f
综上所述,f-?1?f ＝ IB。 同理可证 f? f-?1 ＝ IA
例 8.8
例 8.8 设 f,R→R,g,R→R
求 f?g,g?f。 如果 f 和 g 存在反函数，求出它们的反函数 。
解答
2 3
()
23
( ) 2
xx
fx
x
g x x
2
2
:
23
()
03
:
( 2) 1
()
21
f g R R
xx
f g x
x
g f R R
xx
g f x
x
g,R→R是双射的，它的反函数是
g?1,R→R,g?1(x)=x?2
本章主 要内容
函数的基本概念与性质 （ 单射,满射,双射 ） 。
函数的合成与反函数 。
本章学习要求
掌握函数,A到 B的函数,集合在函数下的像,集合在函数下的完全原像的概念及表示法；当 A与 B都是有穷集时
,会求 A到 B的函数的个数 。
掌握 A到 B的函数是单射,满射,和双射的定义及证明方法 。
掌握常函数,恒等函数,单调函数,特征函数,自然映射等概念 。
掌握合成函数的主要性质和求合成函数的方法 。
掌握反函数的概念及主要性质 。
对于任意的 <x,y>,<u,v>?R?R,有
:,
(,),
f R R R R
f x y x y x y
证明,任取 <u,v>?R?R,存在?R?R,使得,
22u v u v
(,),22u v u vf u v
(,) (,),,
,,
,,
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是满射的 。
因此 f是单射的 。
例题证明 f 既是满射的，也是单射的。其中例题令 X＝ {x1,x2,…,xm},Y={y1,y2,…,yn},问
（ 1） 有多少不同的由 X到 Y的关系？
（ 2） 有多少不同的 X到 Y的映射？
（ 3） 有多少不同的由 X到 Y的单射,双射？
解,（ 1） 有 2mn不同的由 X到 Y的关系 。
（ 2） 有 nm不同的 X到 Y的映射 。
（ 3） X到 Y的单射个数为：
若 m?n,有 0个单射 。
若 m＝ n,有 m!个单射 。
只有 m＝ n时,才存在 X到 Y的双射,个数为 m! 。
若 m?n,有 个单射 。m
nCm!
设 A,B,C,D是任意集合,f是 A到 B的双射,g是 C到 D的双射 。
令 h:A?C?B?D,且?<a,c>?A?C,h(<a,c>)=<f(a),g(c)>,那么 h是双射吗？ 请证明你的判断 。
证明,?先证明 h是满射 。
<b,d>?B?D,则 b?B,d?D，
因为 f是 A到 B的双射,g是 C到 D的双射,
所以,?a?A,c?C,使得 f(a)=b,g(c)=d，
也就是?<a,c>?A?C,使得 h(<a,c>)= <f(a),g(c)> =<b,d>,
所以,h是满射。
例题例题
再证 h是单射 。
<a1,c1>,<a2,c2>?A?C,若 h(<a1,c1>)= h(<a2,c2> ),则
<f(a1),g(c1)> = <f(a2),g(c2)>
所以,f(a1) = f(a2),g(c1) = g(c2)。
因为 f是 A到 B的双射,g是 C到 D的双射,
所以,a1 = a2,c1 = c2。
所以,<a1,c1>= <a2,c2>,
所以,h是单射 。
综上所述,h是双射 。
作业习题八,1,2,3,4,15,16,17,24
单射和满射的证明方法
证明函数 f:A→B 是满射的，基本方法是：
任取 y∈B,找到 x∈A (x与 y相关，可能是一个关于 y
的表达式 )或者证明存在 x∈A,使得 f(x)＝ y。
证明函数 f:A→B 是单射的，基本方法是：
假设 A中存在 x1和 x2,使得 f(x1)＝ f(x2),利用已知条件或者相关的定理 最终证明 x1＝ x2。
实数集合上函数性质的判断方法
对于实数集合上的函数，通常可以通过求导找到极值点。而有的极小值（或极大值）恰好是函数的最小值（或最大值），这样就可以求出 函数的值域,从而 判断函数是否为满射的 。
如果函数存在极值，那么可以断定函数不是单射的,因为在极值点两侧可以找到不相等的 x1和 x2满足 f(x1)＝ f(x2)。
证明函数不具有某种性质的一般方法就是给出反例。
为证明函数不是单射的，需要找到 x1≠ x2且 f(x1)＝ f(x2)。
有时可能不容易找到具体的 x1和 x2,但是可以证明这样的 x1和 x2
是存在的。
证明函数不是满射的一般方法就是找到 y∈B － ran f。
