离散数学及其应用-第2版 课件 第5章函数

第5章函数函数5.1函数的定义5.2特殊函数5.3复合函数5.4反函数5.5集合的基数

函数定义

设f是从集合A到B的一个二元关系，且对于任一x

A，都有唯一的y

B，使得(x，y)

f，则称f为从A到B的函数或映射，记作：f：A

B。例

设集合A={a,b,c}，B={1,2,3,4,5}，如果f={(a,1),(b,3),(c,5)},判断f是否是A到B的函数。解

是定义域和值域定义

如果f是从A到B的函数，则称A是f的定义域，B是f的陪域。如果(x，y)

f，则可写成y=f(x)，称y为x的像，x为y的原像。A中元素的所有像元素构成的集合，称为f的值域。

可以用domf表示f的定义域，ranf表示f的值域，所以有domf=A，ranf

B。例题例

设集合A={x1，x2}，B={y1，y2}，f={(x1，y1)，(x2，y2),，(x2，y1)}，g={(x1，y1)，(x2，y1)}，判断f和g是否是A到B的函数。解

f不是，

g是f是从A到B的函数需满足下列条件的关系：函数的定义域是A，不能是A的任一真子集。对集合A的任一元素，对应集合B中唯一的元素y。定义

设f、g均为集合A到集合B的函数。若对

x

A，都有f(x)=g(x)，则称函数f和g相等，记作f=g。定义

设A、B为集合，所有从A到B的函数构成BA，读作“B上A”，即BA={f|f：A

B}。例题例

集合A={0，1，2}，B={a，b}。写出所有从A到B的函数。解

所有从A到B的函数为：f1={(0，a)，(1，a)，(2，a)}f2={(0，a)，(1，a)，(2，b)}f3={(0，a)，(1，b)，(2，a)}f4={(0，a)，(1，b)，(2，b)}f5={(0，b)，(1，a)，(2，a)}f6={(0，b)，(1，a)，(2，b)}f7={(0，b)，(1，b)，(2，a)}f8={(0，b)，(1，b)，(2，b)}因而BA={f1，f2，f3，f4，f5，f6，f7，f8}。

如果|A|=m，|B|=n，则|BA|=nm。因为

x

A，f(x)有n种取

法，

。4.8.2特殊函数定义

给定函数f：A

B若对于

x1，x2

A，x1

x2

，都有f(x1)

f(x2)，则称f是单射函数(或一对一映射)。若对

y

B，都有x

A，使得f(x)=y，则称f是满射函数(或从A到B上的映射)。若f既是满射又是单射,则称f是双射函数(或一一对应映射)。例题例

令f是从A={a，b，c，d}到B={1，2，3，4，5}的函数，f(a)=1，f(b)=2，f(c)=3，f(d)=5，f是单射、满射还是双射函数？解

f是单射函数。例题例

图4.8.1定义了函数f，g，h，指出f，g，h哪些是单射，满射和双射。fgh

解

f是单射函数，g是满射函数，h是双射函数。常用的函数(1)设f:A→B,如果存在b∈B使得对所有的x∈A都有f(x)=b,则称f:A→B是常函数。(2)设f:A→A,如果对所有的x∈A都有f(x)=x，称f:A→A为A上的恒等函数。(3)设A为集合,对于任意的A'

A,A'

的特征函数

fA

':A→{0,1}定义为:常用的函数（续）(4)设R是A上的等价关系,令g:A→A/R，g(a)=[a]R,

a∈A

，称g是从A到商集A/R的自然映射。(5)对有理数x，f(x)为大于或等于x的最小整数，称f(x)为上取整函数，记为

(6)对有理数x，f(x)为小于或等于x的最大整数，称f(x)为下取整函数，记为

4.8.3复合函数定义

设f是从集合A到集合B的函数，g是从集合B到集合C的函数，f和g的复合用gof表示为gof={(x，z)|x

A

z

C

y(y

B

(x，y)

f

(y，z)

g)gof是从A到C的函数，称为f和g的复合函数。对任意x

A都有gof(x)=g(f(x))。注意，如果f的值域不是g的定义域的子集，就无法定义gof。例题例

令f和g为函数。f是从{a，b，c}到{1，2，3}的函数，f(a)=3，f(b)=2，f(c)=1。g是从{a，b，c}到它自己的函数，g(a)=b，g(b)=c，g(c)=a。求fog和gof。解由函数的复合定义有：fog(a)=f(g(a))=f(b)=2，fog(b)=f(g(b))=f(c)=1，

fog(c)=f(g(c))=f(a)=3。而gof没有定义。定理

定理

设函数g：A

B，f：B

C，则:（1）fog是A到C的函数。（2）对任意的x

A，有fog(x)=f(g(x))。证明

（1）对任意的x

A，因为g：A

B是函数，则存在y

B使(x,y)

g。对y

B，因为f：BC是函数，则存在z

C使(y,z)

f。根据复合关系的定义，由(x,y)

g和(y,z)

f得(x,z)

fog，所以domfog=A对任意的x

A，xfogy1和xfogy2,则<x,y1>∈fog∧<x,y2>∈fog

t1(<x,t1>∈g∧<t1,y1>∈f)∧

t2(<x,t2>∈g∧<t2,y2>∈f)

t1

t2(t1=t2∧<t1,y1>∈f∧<t2,y2>∈f

（g为函数）

y1=y2

（f为函数）所以fog为函数.证明（续）(2)对任意的x

A，因为g：A

B是函数，有(x,g(x))

g且g(x)

B，又由f：BC是函数，得(g(x),f(g(x)))

f，于是（x,f(g(x)))

fog。又因fog是A到C的函数，则可写成fog(x)=f(g(x))。例题设f和g是从整数集到整数集的函数。f(x)=x+2，g(x)=2x+1。求fog和gof。解由函数的复合定义有：fog(x)=f(g(x))=f(2x+1)=(2x+1)+2=2x+3

gof(x)=g(f(x))=g(x+2)=2(x+2)+1=2x+5由此可见，fog(x)

gof(x)。即函数的复合不满足交换律。定理

定理

设f：A

B，g：B

C，h：C

D均为函数，则ho(gof)=(hog)of

。证明

因为f：A

B，g：B

C，h：C

D均为函数，由定理4.8.1知，ho(gof)和(hog)of

都是A到D的函数。对任意的x

A，有ho(gof)(x)=ho(gof(x))=h(g(f(x)))=(hog)of(x)，所以ho(gof)=(hog)of

。定理

定理

设f和g是函数，gof是f和g的复合函数，于是有：如果f和g都是满射函数，则gof也是满射函数。如果f和g都是单射函数，则gof也是单射函数。如果f和g都是双射函数，则gof也是双射函数。证明(1)若f：A

B，g：B

C，f和g都是满射函数，则对任一z

C，由g是满射函数，必存在y

B，使得g(y)=z。又由于f是满射函数，必存在x

A，使得f(x)=y。因此，gof(x)=g(f(x))=g(y)=z。由z的任意性知gof的值域为C。所以gof是满射函数。(2)由于f是单射函数，所以对任意的x1、x2

A且x1

x2，有f(x1)

f(x2)。又因为g是单射函数，则有g(f(x1))

g(f(x2))，即gof(x1)

gof(x2)。所以，gof是单射函数。(3)由(1)(2)可知，gof既是单射又是满射，因而是双射函数。定理

定理

设f和g是函数，gof是f和g的复合函数，于是有：如果gof是满射函数，则g必定是满射函数。如果gof是单射函数，则f必定是单射函数。如果gof是双射函数，则g必定是满射函数，f是单射函数。证明(1)若f：A

B，g：B

C，gof是A

C的满射函数，则对任一z

C，都有gof(x)=z，即(x，z)

gof。因而必存在y使得(x，y)

f且(y，z)

g。也就是说，对任意z

C都有g(y)=z。因此，g是满射函数。（2）f：A

B，g：B

C，gof是A

C的是单射函数，则对任意的x1、x2

A且x1

x2，有gof(x1)

go

f(x2)，即g(f(x1))

g(f(x2))。按照函数的定义，C中的两个不同元素必定在B中有不同的原像，因而f(x1)

f(x2)。所以，f是单射函数。（3）gof是双射函数，所以gof既是满射函数，又是单射函数。由(1)(2)可知，g是满射函数，f是单射函数。定理

设函数f：A

B，则f=foIA=IBof。证明：

反函数定义

设集合A和B，函数f：A

B是一个双射函数，则称f的逆关系叫做f的反函数(逆映射)，记做f-1，称f是可逆的。例如，R是实数集合，f：R

R，f={(x，x+1)|x

R}。这是一个双射函数，它的反函数为：f-1={(x+1，x)|x

R}定理定理

如果函数f是从A

到B的双射函数，则f

-1是从B到A的双射函数。定理

若f：A

B是双射函数，则(f-1)-1=f证明:对任意(x，y)

f，由于f是双射函数，所以(y，x)

f

-1。又由于f

-1是双射函数，所以(x，y)

(f

-1)-1。因而有f

(f

-1)-1。同理可证(f

-1)-1

f。所以，(f

-1)-1=f。

定理

若f：A

B，g：B

C均为双射函数，则(gof)-1=f

-1

og-1。

集合的基数定义

设A和B是两个集合，如果存在一个双射函数f：A

B，则称A与B是等势的（或等基数），记作A~B。等基数的两个集合的基数相等，所以又记为|A|=|B|。定义

设A和B是两个集合，如果存在一个单射函数f：A

B，则称A的基数小于或等于B的基数，记作|A|

|B|。如果|A|

|B|且|A|≠|B|，则称A的基数小于B的基数，记作|A|<|B|。定义

基数为自然数的集合称为有限基数集合（有限集合），非有限集合称为无限集合。定义

所有与自然数集合等势的集合都称为可数集合或可列集合。可数集合的基数为

0（阿列夫零）。例题验证非负偶数集M是可列集合。证明

要验证非负偶数集是可列集合，也就是验证非负偶数集和自然数集是等势的。在非负偶数集和自然数集之如下的对应关系：N：01234

n

M：02468

2n

显然上述对应关系是一一对应。所以非负偶数集M是可列集合。定理定理有限集合不与它的任何真子集等势。一个集合是无限集合当且仅当它与它的某个真子集等势。如：非负偶数集是自然数集的真子集，即M