《离散数学》函数

第五章函数《离散数学及应用》第五章函数§5.1函数的定义§5.2函数的性质§5.3函数的复合§5.4逆函数§5.5计算机科学中的常用函数*§5.6双射函数及集合的势2函数A

和B

为非空集合设

f

为

A

到

B

的二元关系,若对于任意x

Dom(f)都存在唯一的

y

Ran(f)使得

(x,y)

f成立，则称

f

为函数(function)。函数也称作映射（mapping）或变换（transformation）3函数{(1,1),(2,3),(4,1),(3,5),(5,3)}是一个函数{(1,1),(1,3),(4,1),(3,5),(5,3)}不是函数4函数假设A

到

B

的二元关系

f

为函数如果

aDom(

f)，那么

f(a)=Ø如果

f(a)={b}，习惯上使用元素b来表示集合

{b}

并且写作f(a)=bf可以被描述为有序对的集合{(a,f(a))|aDom(f)}5函数f={(1,1),(2,3),(4,1),(3,5),(5,3)}是一个函数f(1)=1,f(2)=3,f(4)=1,f(3)=5,f(5)=3它也可以写作

{(1,f(1)),(2,f(2)),(4,f(4)),

(3,f(3)),(5,f(5))}6函数7xy=f(x)ABf

函数假设A

到

B

的二元关系

f

为函数y=f(x)

中，x

称为自变量（argument），y

为

f在

x的值（value）或

x在

f作用下的像（image）。8ab=f(a)AB函数例

A=

B=

9函数设

A、B

是非空集合，f是

A

到

B

的一个关系，如果对每个

x

A，存在唯一的

y

B

，使得

(x,y)

f，则称

f

为A到B的函数，记作

f:A→B。对于

A到

B的函数

f

，

Dom(f)=A，Ran(f)

B。10函数例

A=

B=

11A到B的函数？函数12f:A

Ba

b

a

b=f(a)函数设

A

是一个任意非空集合.A

上的恒等函数表示为1A，其定义为1A(a)=a13第五章函数§5.1函数的定义§5.2函数的性质§5.3函数的复合§5.4逆函数§5.5计算机科学中的常用函数*§5.6双射函数及集合的势14函数的性质设函数

f:A→B，若

Ran(f)

=B，则称

f

是满射

（surjection）或映上的（onto）；若任意

y

Ran(f)

都存在唯一的

x

A使得

f(x)=y，则称

f:A→B是单射(injection)或一一的（one-to-one）；若

f

既是满射又是单射，则称

f

是双射（bijection）或一一对应（one-to-onecorrespondence）。15函数的性质f

是满射意味着：对于任意

y

B，都存在

x

A使得

f(x)=y

f

是单射另有如下两个等价定义：对于任意

a,b

A

满足

a≠b

，均有f(a)≠f(b)如果

a,b

A

满足

f(a)=f(b)，则

a=b16函数的性质17函数的性质18函数的性质19函数的性质例设

A

是非空集合，A

上的恒等函数

1A

既是单射又是满射，从而是双射函数

g:

→

，定义为

g(x)=x2

2x+1g

不是单射——

g(0)=g(2)=1g

也不是满射——

g

在

x=1

取得最小值

0从而

g

不是双射。2021函数的性质练习f：

+

→

+

，f(1)=1，f(n)=

n–1(n>1)

单射?满射?双射?函数的性质对于有限集合上的函数，有如下主要结果：定理

假设

A

和

B

是两个有限集合且满足

|A|=|B|，则函数

f:A

B

是单射当且仅当

f

是满射。22函数的性质定理

假设

A

和

B

都是有限集合，则：(a)若

|A|<|B|，则必然存在从

A

到

B

的单射函数、必然不存在从

A

到

B

的满射函数；(b)若

|A|>|B|，则必然存在从

A

到

B

的满射函数、必然不存在从

A

到

B

的单射函数；(c)若

|A|=|B|，则必然存在从

A

到

B

的双射函数。23函数的性质推论

假设

A

是有限集合，B

是无限集合，则：(a)必然不存在从

A

到

B

的满射函数(b)必然不存在从

B

到

A

的单射函数24第五章函数§5.1函数的定义§5.2函数的性质§5.3函数的复合§5.4逆函数§5.5计算机科学中的常用函数*§5.6双射函数及集合的势25函数的复合定理1

设

A,B,C是集合，f

是

A

到

B

的关系，g

是

B

到

C

的关系。若

f,g

是函数，则：g◦f

也是函数，且满足Dom(g◦f)={x|x

Dom(f)

且

f(x)

Dom(g)}对于任意

x

Dom(g◦f)有

g◦f(x)=g(f(x))26函数A

和B

为非空集合设

f

为

A

到

B

的二元关系,若对于任意x

Dom(f)都存在唯一的

y

Ran(f)使得

(x,y)

f成立，则称

f

为函数(function)。27函数的复合证明：（反证法）令

x

Dom(g◦f)，若存在y1,y2Ran(g◦f)

且(x,y1)

g◦f,(x,y2)

g◦f

。则存在t1

Dom(g)使得

(x,t1)

f

且(t1,y1)

g存在t2

Dom(g)

使得

(x,t2)

f

且(t2,y2)

g由于

f

是一个函数，因此

t1=t2由于g

是一个函数，因此

y1=y2于是

g◦f

是一个函数

28函数的复合(g◦f)(x)=g(f(x))29xy=f(x)ABz=g(y)

=(g◦f

)(x)C函数的复合30例f：

→

，f(x)=x+1，g：

→

，g(x)=2x+1,h：

→

，h(x)=x2+1,

g◦f(x)=g(f(x))=2f(x)+1=2(x+1)+1=2x+3f◦g(x)=f(g(x))=g(x)+1=2x+1+1=2x+2h◦g◦f(x)=h(g(f(x)))=4x2+12x+10=(2x+3)2+1函数的复合定理2

假设

A、B、C

为非空集合，函数

f:A→B,g:B→C，则(a)如果

g

和

f

都是满射，则

g◦f

也是满射(b)如果

g

和

f

都是单射，则

g◦f

也是单射(c)如果

g

和

f

都是双射，则

g◦f

也是双射

31函数的复合32函数的复合但是反过来，定理2的逆定理并不全部成立，而只是部分成立。定理3

假设

A、B、C

为非空集合，函数

f:A→B,g:B→C，则(a)若

g◦f是单射，则

f

是单射(b)若

g◦f是满射，则

g

是满射(c)若

g◦f是双射，则

f是单射，g

是满射33函数的复合34函数的复合定理4

假设

A、B

为集合，函数

f:A

B，则

f=f◦1A

=1B◦f

。35第五章函数§5.1函数的定义§5.2函数的性质§5.3函数的复合§5.4逆函数§5.5计算机科学中的常用函数*§5.6双射函数及集合的势36逆函数R={(1,1),(3,1),(2,2)}是一个函数R

1={(1,1),(1,3),(2,2)}不是一个函数37逆函数假设

A、B为集合，如果函数

f:A

B作为关系的逆关系

f

1是

B

到

A

的函数，则称之为可逆的（invertible），此时称

f

1为

f

的反函数或逆函数（inversefunction）。38逆函数定理

假设

A、B

为集合，设

f:A→B，若函数

f

1

存在则；(a)f

1◦f=1A(b)

f◦f

1

=1B39逆函数证明

（

f

1◦f=1A

）假设函数

f

1

存在。对于任意

x

A，由于

f

是

A

到

B

的函数，因此存在

y

B，使得

(x,y)

f于是

(x,x)

f

1◦f

，即得

1A

f

1◦f

又由于

f

和

f

1

都是函数，因此f

1◦f

也是函数对于任意

x

A

，若还存在

y

A

使得

(x,y)

f

1◦f，则必然有

y=x，即

f

1◦f=1A40逆函数下面一个定理给出了逆函数存在的充要条件：定理

假设

A、B

为非空集合，函数

f:A

B，则(a)f

可逆当且仅当

f

是双射(b)f

的逆函数若存在则也是双射41逆函数证明.（充分性）若

f

是双射，则

f

1

是

B

到

A

的函数。f

1是一个关系，且由

f

是双射有

Dom(f

1)=Ran(f)=B， Ran(f

1)=Dom(f)=A对于任意的

b

B，若存在

a1,a2

A

使得

(b,a1)

f

1

且

(b,a2)

f

1则由关系逆的定义有

(a1,b)

f

且

(a2,b)

f

，根据

f

是单射可得

a1=a2

42逆函数证明.（必要性）假设

f

可逆，以下分两个步骤证明

f

是双射：①

f

是单射：由

f

1◦f=1A

及1A是单射，知f是单射。②

f

是满射：由

f◦f

1=1B

及1B是满射，知f是满射。43逆函数证明.下面证明

f

1也是双射：①

f

1

是满射：由

f

1◦f=1A

及1A是满射，知f

1

是满射。②

f

1

是单射：由

f◦f

1=1B

及1B是单射，知f

1

是单射。44逆函数例h:

→

，h(x)=2x+1是双射，因此可逆，逆函数是

h

1(x)=(x

1)/2g:

→

，g(x)=

x2+2x

1不是双射因此不存在

g

的逆函数4546逆函数定理3

若函数

f:A

B

和g:B

A

满足g◦f=1A

和f◦g=1B

，则f是一个

A

到

B

的双射，g

是一个

B

到

A

的双射，而且

f

和

g

互为逆函数。

逆函数由此逆函数也可以等价地定义为：假设

A、B

为集合，对于函数

f:A

B若存在函数

f

1

使得

f

1◦f=1A且

f◦f

1=1B。则称

f为可逆的，此时称

f

1为

f

的反函数或逆函数。47第五章函数§5.1函数的定义§5.2函数的性质§5.3函数的复合§5.4逆函数§5.5计算机科学中的常用函数*§5.6双射函数及集合的势48使用序列表示集合如何在计算机中表示序列？使用数组、线性表如何在计算机中表示集合和进行集合的运算？49使用序列表示集合设

U

为全集，对于任意集合

A

U，可定义

A

的特征函数（characteristicfunction）

A:U→{0,1}为50Ifx

A.

0Ifx

A

1

A(x)=使用序列表示集合例U={0,1,…,9},A={0,1,2,3},B={1,3,5,7,9}A∪B={0,1,2,3,5,7,9}A∩B={1,3}A

B={0,2}A={4,5,6,7,8,9}B={0,2,4,6,8}A

B={0,2,5,7,9}51使用序列表示集合52U={0,1,…,9},A={0,1,2,3},B={1,3,5,7,9}0123456789

A1111000000

A

B0101010101

B

A∩B

A∪B

A-B

A

B使用序列表示集合53U={0,1,…,9},A={0,1,2,3},B={1,3,5,7,9}0123456789

A1111000000

A0000111111

B0101010101

B1010101010

A∩B

A∪B

A-B

A

B使用序列表示集合54U={0,1,…,9},A={0,1,2,3},B={1,3,5,7,9}0123456789

A1111000000

A

B0101010101

B

A∩B0101000000

A∪B

A-B

A

B使用序列表示集合55U={0,1,…,9},A={0,1,2,3},B={1,3,5,7,9}0123456789

A1111000000

A

B0101010101

B

A∩B

A∪B1111010101

A-B

A

B使用序列表示集合56U={0,1,…,9},A={0,1,2,3},B={1,3,5,7,9}0123456789

A1111000000

A

B0101010101

B

A∩B

A∪B

A-B1010000000

A

B使用序列表示集合57U={0,1,…,9},A={0,1,2,3},B={1,3,5,7,9}0123456789

A1111000000

A

B0101010101

B

A∩B

A∪B

A-B

A

B使用序列表示集合58U={0,1,…,9},A={0,1,2,3},B={1,3,5,7,9}0123456789

A1111000000

A

B0101010101

B

A∩B

A∪B

A-B

A

B1010010101使用序列表示集合对于所有

x

U，特征函数满足以下等式：(a)

A(x)=

1

A(x)(b)

A∩B(x)=

A(x)

B(x)(c)

A∪B(x)=

A(x)+

B(x)

A(x)

B(x)(d)

A

B(x)=

A(x)+

B(x)

2

A(x)

B(x)(e)

A

B(x)=

A(x)(1

B(x))59使用序列表示集合一般情况下，假设全集

U的基数是

n且其元素有一个确定的顺序于是每一个全集的子集都一一对应着一个

n

维0-1向量，集合运算可以转化为0-1向量之间的运算60地板函数与天花板函数定义在

上的地板函数（floorfunction），也称作下取整函数或者高斯函数，其值是不超过自变量

x

的最大整数，记作

floor(x)

或

x

定义在

上的天花板函数（ceilingfunction），也称作上取整函数，其值是不小于

x

的最小整数，记做

ceiling(x)或

x

61

x

x

x

地板函数与天花板函数下取整函数

和

上取整函数（图片来自WolframMathWorld）62地板函数与天花板函数例

5

=5,

2.4

=2,

2.4

=

3,

=

4

5

=5,

2.4

=3,

2.4

=

2,

=

363地板函数与天花板函数上取整函数和下取整函数具有如下性质：设

n

为任意整数，x

为实数，则(a1)

x

=n当且仅当

n

≤x<n+1(a2)

x

=n当且仅当

n

1<x≤n(a3)

x

=n当且仅当

x

1<n≤x(a4)

x

=n当且仅当

x

≤n<x+1(b1)

x+n

=

x

+n

(b2)

x+n

=

x

+n64地板函数与天花板函数上取整函数和下取整函数具有如下性质：(c)x

1<

x

≤x≤

x

<x+1(d1)

x

=

x

(d2)

x

=

x

65置换假设非空有限集合

S

包含

n

个元素，S

上的一个双射称为

S

的一个

n元置换或简称置换（permutation），表示为其中

xi表示

S

中互异元素。n

称为置换的阶（order）。66

=x1x2…xnf(x1)f(x2)…f(xn)置换置换的表示形式是不唯一的，例如：67

=123321

=132312

=213231

=231213

=312132

=321123置换集合

S={1,2,3}上的置换（双射函数）有

3!=6

个，分别为：68

1

=123123

2

=123132

3

=123213

4

=123231

5

=123312

6

=123321置换一般地讲，假设

S

是有

n

个元素的有限集，则(a)S

的任一个置换都有

n!

种不同的表示(b)S

共有

n!

个彼此不同的置换69置换假设有限集合

S

包含

n

个元素，则称

S

上的恒等函数为

S

的恒等置换或不变置换。置换存在逆置换置换可以进行复合也称作置换的乘积或积70置换例71

1

=123312

2

=123213(

1)1

=123231

2◦

1

=123321(

2)1

=123213

1◦

2

=123132置换假设

是集合

S

的一个置换，则可定义

的幂为：(1)

0=1S，(2)

n=

n

1◦

，n

1。注：易见(

1)n=(

n)

1。72置换假设

是集合

S

的一个置换，使得

k=1S成立的最小正整数

k

称作

的周期（period），记作per(

)。73置换例

1=

3=1S因此

的周期为374

=123312

2

=123231置换定理

假设

是有限集合

S的一个置换，则

的周期必定存在。75置换证明

考察无限序列

1,

2,

3,…由于有限集合

S

的置换只有有限个因此必定存在

1

i<j使得

i

=

j于是

j

i=(

j)◦(

i)

1=1S即序列

1,

2,

3,…,

j

i中必定存在最小正整数

k

使得

k=1S，其即为

的周期。

76轮换假设有限集合

S

包含

n

个元素，以

(a1,a2,…,ar)

表示

S

的一个如下置换：将

a1

映射为

a2

，将

a2映射为

a3，......，将

ar

1

映射为

ar

，将

ar映射为

a1

，同时将其它元素映射到自身。(a1,a2,…,ar)称为一个r-轮换或简称轮换（cyclepermutation），r

称作该轮换的长度。2-轮换也称作对换。通常将

1S

写作轮换(1)。77轮换例78

1

=123123

2

=123132

3

=123213

4

=123231

5

=123312

6

=123321可写作(1)可写作(2,3)可写作(1,2)可写作(1,2,3)可写作(1,3,2)可写作(1,3)轮换若两个轮换

1=(a1,a2,…,ar)和

2=(b1,b2,…,bs)满足{a1,a2,…,ar}∩{b1,b2,…,bs}=

，则称它们是不相交的轮换。容易证明，不相交轮换对于复合运算是可换的。定理

任一置换可唯一（不计轮换的次序）表示成若干不相交轮换的复合（积）。79轮换(1,2,3,5,8)801234567823578461轮换(1,2,3,5,8)81467746(4,7,6)哈希函数设

A

为有限集合，n

为一确定正整数，则

A

到

An

的函数

H:A*→An可称作一个哈希函数（hashfunction）。82哈希函数哈希函数也称散列函数

或杂凑函数可以将任意长度的输入数据（字符串）打乱、混合、压缩，映射成一个定长的输出字符串于是创建一个叫做“摘要”的数字“指纹”，使得数据量变小，并将数据格式固定下来83哈希函数并非所有这样的函数都是“好”的、

适合实际应用的哈希函数一个好的哈希函数一般要满足以下两个要求：(a)冲突尽可能少H必定不是单射必定存在不同的自变量产生相同的哈希值这种现象称为冲突(Collision)或碰撞好的哈希函数应尽可能减少冲突的出现(b)散列值应尽可能均匀地分布在整个

值域范围内84哈希函数设

A={0,1,2,…,9}，则每一个非负整数都可以看作

A*中的一个元素，对于给定的正整数

m，可定义函数

f

为：

f(x)=x

modm则

f

是

A*

到

An的哈希函数（不一定是满射），其中

n=

log10m

85哈希函数对于密码学中使用的安全哈希函数，有如下要求：快速性：已知

m，计算

H(m)

是容易的。单向性：已知

c=H(m)，求

m在计算上是不可行的。弱抗碰撞性：对给定的消息

m1

，找到另一个与之不同的消息

m2，使得

H(m1)=H(m2)在计算上是不可行的。强抗碰撞性：找到两个不同的消息

m1

和

m2，使得

H(m1)=H(m2)

在计算上是不可行的。敏感性：c=H(m)，c

的每一比特都与

m

的每一比特相关，并有高度敏感性，即每改变

m

的一比特，都将对

c

产生明显影响。86第五章函数§5.1函数的定义§5.2函数的性质§5.3函数的复合§5.4逆函数§5.5计算机科学中的常用函数*§5.6双射函数及集合的势87集合的势1638年，伽利略（GalileoGalilei）在《关于两种新科学的对话》中借三个中世纪的学者的对话指出：对于每个自然数，都有且只有一个平方数与之对应881

12

43

94

16

n

n2

集合的势于是产生一个问题：自然数和自然数的平方哪个多？部分和全体哪个多？当时它不仅困惑了伽利略，也使许多数学家束手无策。89集合的势1874-1894年间，康托（Cantor，1845-1918）圆满地解决了这个问题，其基本思想是“一一对应”。假设

A

和

B

是两个集合，如果存在

A

到

B

的双射，则称集合

A

与集合

B

是等势的，记作

A

B；或称

A

和

B

的基数相等，记作

|A|=|B|。90集合的势定理

集合族（即集合的集合）上的等势关系是一个等价关系。91集合的势例A={a,b,c}和

B={刘备,关羽,张飞}

等势如果两个有限集合的元素个数相同，它们一定等势如果两个有限集合的元素个数不同，它们一定不等势因此对于有限集合，可以按其元素个数划分为不同的等价类92集合的势定理

有限集合不能与其任意真子集等势自然数集合和自然数的平方集合等势双射函数为

f(x)=x2可以证明任意无限集必与其某个真子集等势这给出了无限集的本质经常用来作为无限集合的定义93集合的势哪个线段上的点多?94实轴上所有闭区间都等势类似地可以证明实轴上所有开区间都等势集合的势线段和直线，哪个上面的点多?95集合的势线段和直线，哪个上面的点多?双射：tan函数96实轴上所有开区间都与实数集合等势集合的势自然数集

={0,1,2,…}和整数集

是等势的。双射函数为97集合的势98…-5-4-3-2-1012345…012345678910……集合的势自然数集

和

是等势的。99(0,0)(0,1)(0,2)(1,0)(1,1)(1,2)(2,0)(2,1)(0,3)(3,0)……………集合的势开区间(0,1)与闭区间[0,1]是等势的其他的数对应到自己100集合的势开区间

(0,1)

与

(0,1)

(0,1)

等势将每一个实数

x

(0,1)

表示成无限小数形式

x=x1x2…xi…0.5可表示成0.4999……，0.781可表示为0.780999……。建立

(0,1)与

(0,1)

(0,1)之间的双射：1010.x1x2x3x4x5x6……0.x1x3x5……0.x2x4x6……

集合的势实数集

与复数集

是等势的

与

等势

与

等势102集合的势自然数集

和闭区间[0,1]不等势证明：（反证法）假设存在一个双射函数

f:

→[0,1]，则[0,1]中的元素必与

中的元素一一对应那么[0,1]中的元素必可排列成如下的形式：Ran(f)=[0,1]={x0,x1,x2,x3,…}103集合的势设每个

xi的小数形式是：0.ai0ai1ai2…aij…，aij

{0,1,…,9}则有由

f

是双射，任一[0,1]中的实数均应出现在上表中的某一行下面按照对角线构造一个新的小数

y

=0.

b0b1b2…bj…，使得

bi

aii

且

bi

9

避免出现0.79999999....等类似情况那么显然有

y[0,1]，而又不在上表中因为

y与上表中任一项都至少存在一位不同

因此

f不可能是满射，更不可能是双射

104f(0)=x0=0.a00a01a02…a0j…，f(1)=x1=0.a10a11a12…a1j…，f(2)=x2=0.a20a21a22…a2j…，……f(i)=xi=0.ai0ai1ai2…aij…，……集合的势定理(康托定理，1890)自然数集

和实数集

不等势。105集合的势假设

A

和

B

是两个集合，(a)如果存在

A

到

B

的单射，

则称集合

A劣势于集合

B

，记作

A

B；或称

A

的基数小于等于

B

的基数，记作

|A|

|B|。(b)如果存在

A

到

B

的单射，但不存在

A

到

B

的双射，则称集合

A

严格劣势于集合

B

，记作

A<B；或称

A

的基数小于

B

的基数，记作

|A|<|B|。106集合的势与自然数集合或其子集等势的集合称为可数（countable）集合或可列集合，自然数集合的基数记为

0(读作阿列夫零)；否则称作不可数（uncountable）集合或不可列集合。换言