第5章
函数
【本章知识结构图】
5.函数的定义
1
5.1.1
内容提要
定义5.设
f
为集合
A
到
B
的二元关系。若对于任意x∈D都存在唯一的
y∈Ran(f)
1
使得(y)∈
f
成立, 此时记y=f(x),
om(f)
y
为f
x,则称
f
为函数, 称
x
为自变量,
在
x
的值或
x
在
f
作用下的像。函数也称为映射或变换。
定义5.设A、
B
是非空集合,
f
是
A
到
B
的一个关系。如果对每个x∈A,存在唯
2
1 52 离散数学及应用学习指导与习题解析
一的y∈B,使得(x,y)∈f,则称f 为A 到B 的函数,记作f:A →B。此时也称f 是处
处定义的。
定义5.3 设函数f:A →B,A1.A ,则称f(A1)={f(x)|x∈A1}为A1 在f 下的
像,f(A)称为函数的像。
定义5.4
(a)设f:A →B,如果存在c∈B 使得对所有的x∈A 都有f(x)=c,则称f:A →B
是常值函数。
(b)设A 是非空集合,称A 上的恒等关系IA 为A 上的恒等函数,也记作1A 。即对
于所有的x∈A ,1A (x)=x。
(c)设R 是A 上的等价关系,定义从A 到A/R 的函数g:A →A/R,对任意a∈A ,
g(a)=[a],即将元素映到该元素所在的等价类,称g 是从A 到商集A/R 的典范映射或
自然映射。
(d)设n 是一个正整数,则可以定义从Z到{0,1,2,…,n-1}的取余函数modn。
(e)设集合A.B,A 到B 的包含映射或嵌入为函数i:A B,对于任意x∈A,i(x)=x。
5.1.2 主教材习题参考解答
5.1 判断以下A ={±1,±2,±3,±4}上的关系中哪些构成函数。
(a)R={(x,y)|x∈A ,y∈A ,y+x<7}。
(b)R={(x,y)|x∈A ,y∈A ,x2+y2≤20}。
(c)R={(x,y)|x∈A ,y∈A ,y=x2}。
(d)R={(x,y)|x∈A ,y∈A ,x=y2}。
解:只有(c)是函数。
5.2 判断以下A ={a,b,c}上的关系中哪些构成函数,哪些构成A 上的函数。
(a)R={(a,b),(a,c),(b,b),(b,a)}。
(b)R={(a,b),(b,b)}。
(c)R={(a,b),(b,b),(c,c)}。
解:(b)和(c)是函数,(c)是A 上的函数。
5.3 判断以下关系f 中哪些是A 到B 的函数。
(a)A =B=R,xfy 当且仅当x2=y2。
(b)A =B=R,xfy 当且仅当x3=y3。
(c)A =B=C,(a+bi)f(c+di)当且仅当a=c。
解:只有(b)是A 到B 的函数。
5.4 设f:Z+ →Z+ ,定义为
f(x)= x/2, 若x 为偶数
x+1, 若x 为奇数{
令A ={0,1},B={2},计算f(A)和f(B)。
解:f(A)={0,2},f(B)={1}。
5.5 设f 和g 都是集合A 到集合B 的函数,证明f∩g 也是函数。
第
5
章 函数
153
证明:否则存在x∈A、y1,x,x,。于是(y1)∈
f
且(y2)∈f,
y2∈B,(y1)∈f∩
g
且(y2)∈f∩gx,
□x,与
f
是集合
A
到集合
B
的函数矛盾。
5.6
将集合
A
到集合
B
的所有函数的集合记为BA
,称为指数集,即BA
={f|f:
A→B}。设A、
B
都是有限集合,|A|=m,|B|=n,请计算|BA|。
解
7
:|BA|=|B||A|
a=
,
nmc
。
,e,上划分{{b,d,f}}
5.设集合A={b,d,f} a,c},{e},{决定的等价关系为
R,计算A/
R
的典范映射。
g(=c)a,c},d)g(={e},f)f}。
解:典范映射是g(a)=b)g(={b,g(=e)d,g(={
5.函数的性质
2
5.2.1
内容提要
定义5.设函数f:A→B。
5
(a)若Ran(f)=B,则称
f
是满射或映上的。
一的
(
。
b)若任意y∈Ran(f)都存在唯一的x∈
A
使得f(x)=y,则称
f
是单射或一
(c)若
f
既是满射又是单射,则称
f
是双射或一一对应
。
注
:
(a)
f
是满射意味着:对于任意y∈B,都存在x∈
A
使得f(x)=y
。
(b)
f
是单射另有如下两个等价定义
:
b∈
A
满足a≠b, b)。
(1)如果a,则f(
b.a)≠f(
(b.b∈
A
满足f(=b), b。
2)如果a,a)f(则a=
定理5.1
设
A
和
B
是两个有限集合且满足|A|=|B|,则函数f:A→
B
是单射当
且仅当
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
的单射函数。
5.2.2
主教材习题参考解答
5.给出以下函数的例子。
8
(a)
Z+到
Z+的既非单射又非满射的函数。
1 54 离散数学及应用学习指导与习题解析
(b)Z+ 到Z+ 的是单射但不是满射的函数。
(c)Z+ 到Z+ 的非单射但是是满射的函数。
(d)Z+ 到Z+ 的既是单射又是满射的函数。
解:
(a)例如f(x)= 2, 若x 为偶数
1, 若x 为奇数{ 。
(b)例如f(x)= x, 若x 为偶数
x+2, 若x 为奇数{ 。
(c)例如f(x)= x/2, 若x 为偶数
1, 若x 为奇数{ 。
(d)例如f(x)= x-1, 若x 为偶数
x+1, 若x 为奇数{ 。
5.9 判断下列函数是否为单射、满射、双射,为什么?
(a)f:Z+ →R,f(x)=lnx。
(b)f:R→R,f(x)=|x|。
(c)f:R+ →R+ ,f(x)=(x2+1)/x,其中R+ 为正实数集。
(d)f:Z×Z→Z,f(x,y)=x+y+1。
(e)f:Z×Z→Z×Z,f(x,y)=(x+y,x-y)。
(f)f:R×R→R×R,f(x,y)=(x+y,x-y)。
解:
(a)是单射,不是满射,不是双射。
(b)不是单射,不是满射,不是双射。
(c)不是单射(如f(2)=f(1/2)),不是满射((x2+1)/x≥2),不是双射。
(d)不是单射,是满射,不是双射。
(e)是单射,不是满射,不是双射。
(f)是单射,是满射,是双射。
5.10 设A 和B 是两个有限集,函数f:A →B,证明:
(a)若f 是单射,则|A|≤|B|。
(b)若f 是满射,则|B|≤|A|。
证明:
(a)设A ={a1,a2,…,an },则f (a1),f (a2),…,f (an )彼此互异,且{f (a1),
f(a2),…,f(an)}.B。于是|A|=n=|{f(a1),f(a2),…,f(an)}|≤|B|。
(b)设B ={b1,b2,…,bm },则对于任一bi ∈B,都存在ai ∈A 使得f (ai)=bi,
1≤i≤m 。而且{a1,a2,…,am }彼此互异,于是|B|=m =|{a1,a2,…,am }|≤|A|。□
5.11 证明定理5.1。
证明:设A ={a1,a2,…,an}。若f 是单射,则f(a1),f(a2),…,f(an )彼此互异,
且{f(a1),f(a2),…,f(an)}.B;而由|{f(a1),f(a2),…,f(an)}|≤|B|=|A|=n 可
得{f(a1),f(a2),…,f(an)}=B,于是f 是满射。
第
5
章 函数
155
设B={b1,b2,…,bn
}。若
f
是满射,则对于任一bi
∈B,都存在ai
∈
A
使得
f(=i,a1,na1,}.A,于是由|{a1,
。{a2,…,} a2,…,a2,…,
ai)b1≤i≤na彼此互异且{a
n
可得{a2,…,}=A。这表明对于任(n) 意ai,都
ai)=bi≠bj
=aj)。于是f是单(a) □有(a) f5.
(
12
证明定理
f5(
.2。射。(n) aj
∈A,
n
}|≤|A|=|B|=a1,ai
≠aj
,
证明:设A={a2,…,},b2,…,}。
a1,aB={bm
nb1,
(a)若n<m,则可以构造一个单射函数f(ai)=bi,1≤i≤n。而若存在
A
到
B
的
满射函数,则由题5.b), 产生矛盾。
(b)若n>m,则可以构造一个满射函数f(:1≤i≤
m
时,
时,f(ai)=b1。
10(有|B|≤|A|,
10(
ai)
有|A|≤|B|,
f(ai)=bi;
m
<i≤
n
而若存在
A
到
B
的单射函数,则由题5.a), 产生矛盾。
(c)若n=m,则可以构造一个双射函数f(=i,。□
ai)b1≤i≤
n
5.13
设A、
B
都是有限集合,|A|=m,|B|=n,请计算集合
A
到集合
B
的所有单
射函数的个数。
解:设
A
={a1,a2,…,am
},
f
是集合
A
到集合
B
的单射函数。则
f
(a1),
f(f(
a2),…,am
)是
B
中元素组成的、各项彼此不同的、长为
m
的序列,这样的序列的个
数是P(m)。
n,
5.14
设A、
B
都是有限集合,|A|=|B|=n,请计算集合
A
到集合
B
的所有双射函
数的个数。
},a1),a2),…, 解:设A={a1,a2,…,
f
是集合
A
到集合
B
的双射函数。则f(f(
an
f(an
)是
B
中元素组成的、各项彼此不同的、长为
n
的序列,即
B
中元素的一个全排列,这
样的序列的个数是n!。
5.g:C→D,
15
设有函数f:A→B,则可定义A×C
到B×D
的函数f×g
为f×
g(x,=(x),y))。
y)f(g(
(a)证明:若
f
和
g
都是单射,则f×g
也是单射。
(b)证明:若
f
和
g
都是满射,则f×g
也是满射。
(c)证明:若
f
和
g
都是双射,则f×g
也是双射。
证明:
x1,x2,y1)f×g(x2,f(
(a)若(y1),(y2)∈A×C
使得f×g(x1,=y2), 则有(x1),
g(y1))=(f(x2),g(y2))。于是f(x1)=f(x2)及g(y1)=g(y2), 并由
f
和
g
都是单
射可得x1=x2 且y1=即(y1)x2,
u,
y2, x1,=(y2)。
x)=
(b)设(v)∈B×D。由于
f
和
g
都是满射,因此存在x∈
A
及y∈
C
使得f(
u
且g(y)=。于是f×g(y)=(v)。
(c)由)和(b)即得。
x,u,
□(a(v)
5.对于以下集合
A
和B,构造从
A
到
B
的双射函数。
16
(a)A=(0,1),B=(5,25)( 二者都是实数集上的开区间)
。
(b)A={b,B={ 李四
,
a,c},张三, 王五}
。
(c)A=R,B=R+
。
1 56 离散数学及应用学习指导与习题解析
解:
(a)例如f(x)=20x+5。
(b)例如f={(a,张三),(b,李四),(c,王五)}。
(c)例如f(x)=ex 。
5.3 函数的复合
5.3.1 内容提要
定理5.3 设A 、B、C 是集合,f 是A 到B 的关系,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))。
推论 设A 、B、C、D 均为非空集合,f 为A 到B 的关系,g 为B 到C 的关系,h 为C
到D 的关系。若f、g、h 都是函数,则(h..g)..f 和h..(g..f)也都是函数,且(h..g)..f=
h..(g..f)。
定理5.4 设A 、B、C 为非空集合,函数f:A →B,g:B→C,那么
(a)如果g 和f 都是满射,则g..f 也是满射。
(b)如果g 和f 都是单射,则g..f 也是单射。
(c)如果g 和f 都是双射,则g..f 也是双射。
定理5.5 设A 、B、C 为非空集合,函数f:A →B,g:B→C,那么
(a)若g..f 是单射,则f 是单射。
(b)若g..f 是满射,则g 是满射。
(c)若g..f 是双射,则f 是单射,g 是满射。
定理5.6 设A 、B 为集合,函数f:A →B,则f=f..1A =1B..f。
5.3.2 主教材习题参考解答
5.17 设f={(a,α),(b,α),(c,β)},g={(α,0),(β,1)},计算g..f。
解:g..f={(a,0),(b,0),(c,1)}。
5.18 设函数f:R→R定义为f(x)=256x,g:R→R定义为g(x)=2x ,h:R→
R定义为h(x)=x3,计算g..f(x)、f..g(x)、h..g..f(x)。
解:g..f(x)=2256x ,f..g(x)=256×2x =2x +8,h..g..f(x)=2768x 。
5.19 设函数f:R →R,f(x)= x2, x≥3
-2, x<3 { ;g:R →R,g(x)=x+2。求f..g
和g..f。
解:f..g(x)= (x+2)2, x≥1
-2, x<1 { ,g..f(x)= x2+2, x≥3
0, x<3 { 。
5.20 设函数f:Z+ →Z+ ,定义为
第5 章 函数1 57
f(x)= x/2, x 为偶数
x+1, x 为奇数{
计算f4(15)和f6(65)。
解:f4(15)=2,f6(65)=9。
5.21 设有两个Z+ 到Z+ 的函数:f(n)=n+1,g(n)=max(1,n-1)。证明:
(a)f 是单射而不是满射。
(b)g 是满射而不是单射。
(c)g..f=1Z+ ,而f..g≠1Z+ 。
证明:
(a)不存在正整数n 使得f (n)=1;若f (n1)=f (n2),则由n1+1=n2+1可得
n1=n2。
(b)对于任意正整数y 存在正整数y+1使得f(y+1)=y;而g(1)=g(2)=1。
(c)g..f(n)=max(1,(n+1)-1)=max(1,n)=n,因此g..f=1Z+ 。而f..g(1)=
f(1)=2,因此f..g≠1Z+ 。□
5.4 逆 函 数
5.4.1 内容提要
定义5.6 设A 、B 为集合,如果以函数f:A →B 作为关系的逆关系f-1是B 到A
的函数,则称之为可逆的,此时称f-1为f 的反函数或逆函数。
定理5.7 设A 、B 为集合,f:A →B,若函数f-1存在,则
(a)f-1..f=1A 。
(b)f..f-1=1B 。
定理5.8 设A 、B 为非空集合,函数f:A →B,则f 可逆当且仅当f 是双射,且f
的逆函数若存在则也是双射。
定理5.9 设A 、B 为集合,若A 到B 的函数f 和B 到A 的函数g 满足g..f=1A 及
f..g=1B ,则f 是一个A 到B 的双射,g 是一个B 到A 的双射,而且f 和g 互为逆函数。
定义5.7 设A 、B 为集合,对于函数f:A →B 若存在函数g 使得g..f =1A 且
f..g=1B 。则称f 为可逆的,此时称g 为f 的反函数或逆函数,记作g=f-1。
5.4.2 主教材习题参考解答
5.22 设A ={1,2,3},求出A 上所有的可逆函数。
解:A 上所有的可逆函数为{(1,1),(2,2),(3,3)}、{(1,1),(2,3),(3,2)}、{(1,2),
(2,1),(3,3)}、{(1,2),(2,3),(3,1)}、{(1,3),(2,1),(3,2)}、{(1,3),(2,2),(3,1)}。
5.23 设函数f:R→R定义为f(x)= x2, x≥3
9, x<3 { ;g:R→R定义为g(x)=x+
2。如果f 和g 存在逆函数,则求出它们的逆函数;如果不存在逆函数,请说明理由。
1 58 离散数学及应用学习指导与习题解析
解:f 不存在逆函数,因为f 明显不是单射。g 存在逆函数g-1(x)=x-2。
5.24 设函数f:R×R→R×R定义为f(x,y)=(x+y,x-y)。
(a)证明f 是双射。
(b)求f 的逆函数。
(c)求f..f。
解:
(a)对于任意的(x,y),存在((x+y)/2,(x-y)/2)使得f((x+y)/2,(x-y)/2)
=(x,y)。因此f 是满射。
若有f(x,y)=f(a,b),则由x+y=a+b,x-y=a-b 可得x=a,y=b。因此f
是单射。
(b)对于(x,y)∈R×R,f-1(x,y)=((x+y)/2,(x-y)/2)。
(c)对于(x,y)∈R×R,(f..f)(x,y)=(2x,2y)。
5.25 设f1,f2,f3:Z+ →Z+ 定义为
f1(n)=2n
f2(n)= n/2, n 为偶数
n+1, n 为奇数{
f3(n)= n-1, n 为偶数
n+1, n 为奇数{
分析f1、f2、f3 是否为单射、满射、双射,说明f1、f2、f3 是否可逆。
解:f1 是单射,不是满射,不是双射,不可逆。
f2 不是单射(f(4)=f(1)=2),是满射,不是双射,不可逆。
f3 是单射,也是满射,故是双射,可逆。
5.26 设f:A →B,g:B→C,h:C→A 。若h..g..f=1A ,f..h..g=1B ,g..f..h=1C ,
证明f、g、h 均为双射。
证明:由定理5.5及h..g..f=1A 知f 是单射,h 是满射。
由定理5.5及f..h..g=1B 知g 是单射,f 是满射。
由定理5.5及g..f..h=1C 知h 是单射,g 是满射。
因此,f、g、h 均为双射。□
5.5 计算机科学中的常用函数
5.5.1 内容提要
定义5.8 设U 为全集,对于任意集合A .U ,可定义A 的特征函数χA :U →
{0,1}为
χA (a)= 1, a∈A
0, a∈..A {
将集合运算转化为特征函数的运算见定理5.10。
第5 章 函数1 59
定理5.10 设U 为全集,A 、B 是U 的子集,则特征函数满足以下陈述:
(a)对于所有x∈U ,χ..A (x)=1-χA (x)。
(b)对于所有x∈U ,χA∩B (x)=min(χA (x),χB (x))=χA (x)χB (x)。
(c)对于所有x∈U,χA∪B (x)=max(χA (x),χB (x))=χA (x)+χB (x)-χA (x)χB (x)。
(d)对于所有x∈U ,χA..B (x)=χA (x)+χB (x)-2χA (x)χB (x)。
(e)对于所有x∈U ,χA-B (x)=χA (x)(1-χB (x))。
(f)A .B 当且仅当对于所有x∈U 有χA (x)≤χB (x)。
(g)A =B 当且仅当对于所有x∈U 有χA (x)=χB (x)。
定义5.9 定义在R上的下取整函数,也称作地板函数,其值是不超过自变量x 的最
大整数,记作floor(x)或.x.。
定义5.10 定义在R上的上取整函数,也称作天花板函数,其值是不小于x 的最小
整数,记作ceiling(x)或éxù。
上取整函数和下取整函数的性质见定理5.11。
定理5.11 设n 为任意整数,x、y 为实数,则
(a).x.=n 当且仅当n≤x<n+1。
éxù=n 当且仅当n-1<x≤n。
.x.=n 当且仅当x-1<n≤x。
éxù=n 当且仅当x≤n<x+1。
(b)x-1<.x .≤x≤éxù<x+1。
(c).-x.=-éxù。
é-xù=-.x.。
(d).x+n.=.x.+n。
éx+nù=éxù+n。
(e)若x<y,则.x.≤.y.,éxù≤éyù。
若x≤y,则.x.≤.y.,éxù≤éyù。
定义5.11 设非空有限集合S 包含n 个元素,S 上的一个双射f 称为S 的一个n 元
置换,简称置换,表示为
π= x1 x2 … xn
f(x1) f(x2) … f(xn)
.
è .
.
. ÷
其中xi 表示S 中的互异元素。n 称为置换的阶。
定义5.12 设有限集合S 包含n 个元素,则称S 上的恒等函数为S 的恒等置换或不
变置换。
定义5.13 设π 是集合S 的一个置换,则可定义π 的幂为
(1)π0=1S ,
(2)πn =πn-1..π,n≥1。
定义5.14 设π 是集合S 的一个置换,使得πk =1S 成立的最小正整数k 称作π 的周
期,记作per(π)。
定理5.12 设π 是有限集合S 的一个置换,则π 的周期必定存在。
1 60 离散数学及应用学习指导与习题解析
定义5.15 设有限集合S 包含n 个元素,以(a1,a2,…,ar)表示S 的一个如下置换:
将a1 映射为a2,将a2 映射为a3……将ar-1映射为ar,将ar 映射为a1,同时将其他元素
映射到自身。(a1,a2,…,ar)称为一个r-轮换,简称轮换,r 称为该轮换的长度。2-轮换
也称为对换。
定义5.16 若两个轮换σ1=(a1,a2,…,ar)和σ2=(b1,b2,…,bs)满足{a1,a2,…,
ar}∩{b1,b2,…,bs}=.,则称它们是不相交的轮换。
定理5.13 任一非恒等置换都可以唯一地(不计轮换的次序)表示成若干不相交轮换
的复合(积)。
定理5.14 任一非恒等置换都可以表示成若干对换之积。
定义5.17 设σ= 1 2 … n
σ(1) σ(2) … σ(n)
.
è .
.
. ÷
是1~n 的一个置换。若数对(i,j)满足
σ(i)>σ(j)且i<j,则称其是一个逆序对。若σ 中逆序对的总个数是奇数时,称σ 为奇
置换;否则称σ 为偶置换。
定理5.15 置换σ 的逆序对总个数奇偶性等于将其表示为对换之积时对换个数的奇
偶性。注
:
(a)置换的奇偶性等于它分解成轮换后各个轮换长度之和与轮换个数之差的奇偶
性,或者等价地说,等于各个轮换长度减一之和的奇偶性。
(b)偶置换与偶置换之积仍然是偶置换,偶置换与奇置换之积是奇置换,奇置换与奇
置换之积是偶置换。
定义5.18 设n 为大于1的正整数,则可以定义Z到{0,1,2,…,n-1}的取余函数
modn,(modn)(x)习惯上也记做x modn,y=x modn 当且仅当y≡x (modn)。
定义5.19 设A 为有限集合,n 为确定的正整数,则A * 到An 的函数H :A * →An
可称作一个哈希函数。
5.5.2 主教材习题参考解答
5.27 设U ={1,2,3,4,5,6,7,8},A ={2,3,5,7},B={1,2,4,8},计算特征函数χA
和χB 。用0-1序列表示集合A ∩B、A ∪B、A -B、..A 、..B 和A ..B。
解:A ∩B 对应的序列是01000000。A ∪B 对应的序列是11111011。A -B 对应的
序列是00101010。..A 对应的序列是10010101。..B 对应的序列是00101110。A ..B 对应
的序列是10111011。
5.28 证明定理5.10的(d)和(e)。
证明:
(d)分以下4种情况讨论:
(1)x∈A 且x∈B,此时x.A ..B。χA..B (x)=0,χA (x)=1,χB (x)=1。
(2)x∈A 且x.B,此时x∈A ..B。χA..B (x)=1,χA (x)=1,χB (x)=0。
(3)x.A 且x∈B,此时x∈A ..B。χA..B (x)=1,χA (x)=0,χB (x)=1。
(4)x.A 且x.B,此时x.A ..B。χA..B (x)=0,χA (x)=0,χB (x)=0。