离散数学-函数

5-1函数的基本概念一.概念定义：X与Y集合，f是从X到Y的关系，如果任何x∈X，都存在唯一y∈Y，使得<x,y>∈f,则称f是从X到Y的函数，(变换、映射)，记作f:X

Y,或XY.

如果f:X

X是函数,也称f是X上的函数.下面给出A={1,2,3}上几个关系，哪些是A到A的函数？1。2。。1。2。。1。2。。1。2。。3333R2R1R3R4.1下面哪些是R到R的函数？f={<x,y>|x,y∈R∧y=}g={<x,y>|x,y∈R∧x2+y2=4}h={<x,y>|x,y∈R∧y=x2}r={<x,y>|x,y∈R∧y=lgx}v={<x,y>|x,y∈R∧y=}__1x√x.22.定义域、值域和陪域(共域)设f:XY,

f的定义域(domain)，记作domf，或Df即

Df=domf={x|x∈X∧y(y∈Y∧<x,y>

f)}=Xf的值域(range)：记作ranf，或Rf

即或f(X)Rf=ranf=f(X)={y|y∈Y∧x(x∈X∧<x,y>

f)}

f的陪域(codomain):即是Y(称之为f的陪域)。.3二.函数的表示方法

有枚举法、关系图、关系矩阵、谓词描述法。

三.从X到Y的函数的集合YX：

YX={f|f:XY}YX：它是由所有的从X到Y函数构成的集合例X={1,2,3}Y={a,b}求所有从X到Y函数．结论：若X、Y是有限集合，且|X|=m，|Y|=n，则|YX|=|Y||X|=nm。从X到Y的关系=|P(XY)|=2nm.规定：从∅到∅的函数只有f=∅。从∅到Y的函数只有f=∅。若X≠∅，则从X到∅的函数不存在。.4四.特殊函数

1.常值函数：函数f:XY，如果y0∈Y,使得对x∈X,有f(x)=y0,即ranf={y0},称f是常值函数。2.恒等函数：恒等关系IX是X到X函数，即IX:XX,称之为恒等函数。显然对于x∈X，有IX(x)=x。五.两个函数相等

设有两个函数f:ABg:AB,f=g当且仅当对任何x∈A，有f(x)=g(x)。

.5六.函数的类型

例子：X1

Y。。。。。123ab。csX

Y。。。。。123ab4。。cgX1

Y1。。。。。123abd。。chX

Y。。。。。123ab4。。cfRf=YRs=YRgYRhY1一对一一对一.6函数的类型1.满射的：f:XY是函数，如果ranf=Y,则称f是满射的。2.入射的：f:XY是函数，如果对于任何x1,x2∈X,如果

x1≠x2

有f(x1)≠f(x2),(或者若f(x1)=f(x2),则x1=x2),则称f是入射的，也称f是单射的，也称f是一对一的。3.双射的：f:XY是函数，如果f既是满射的，又是入射的，则称f是双射的，也称f是一一对应的。特别地：：

Y是单射；：

是双射。

思考题：如果f:XX是入射的函数，则必是满射的，所以f也是双射的。此命题在什么条件下成立吗？.75-2函数的复合

关系的复合：设R是从X到Y的关系，S是从Y到Z的关系，则R和S的复合关系记作R

S。定义为：

R

S={<x,z>|x

X

z

Z

y(y

Y

<x,y>

R

<y,z>

S)}.8函数的复合定义：设f:X

Y,g:W

Z是函数,若f(X)W,则g

f={<x,z>|x

X

z

Z

y(y

Y

<x,y>

f

<y,z>

g)}称为g在f的左边可复合。.9定理：两个函数的复合是一个函数。证明：设f:X

Y,g:W

Z是函数,且f(X)W。（1）对任意的xX，因为f是函数，故存在唯一的序偶<x,y>，使得y=f(x)成立,而f(x)f(X)W,又因为g是函数，故存在唯一的序偶<y,z>，使得z=g(y)成立，根据复合定义，<x,z>g∘f,即domg∘f=X.（2）假设<x,z1>g∘f且<x,z2>g∘f，由复合定义存在y1Yy2Y，使得<x,y1>f<y1,z1>g<x,y2>f<y2,z2>g,由于f、g为函数，所以有，y1=y2，因而z1=z2。由（1）、（2）得g∘f是X到Z的函数。.102023/12/811函数的复合一.定义:f:X

Y,g:Y

Z是函数,则定义g

f={<x,z>|x

X

z

Z

y(y

Y

<x,y>

f

<y,z>

g)}则称g

f

为f与g的复合函数(左复合).结论:g

f(x)=g(f(x))二.复合函数的计算计算方法同复合关系的计算.

.12

例f:X

Y,g:Y

ZX={1,2,3}Y={1,2,3,4,}Z={1,2,3,4,5,}f={<1,2>,<2,4>,<3,1>}g={<1,3>,<2,5>,<3,2>,<4,1>}则g

f＝用关系图复合:三.函数复合的性质定理1（满足可结合性）。f:X

Y,g:Y

Z,h:Z

W是函数,则(h

g)

f=h

(g

f)。3。2。1。3。2。1。4XYZ。3。2。1。4。5。3。2。1。3。2。1。4。5XZg

ffg.13定理2.f:X

Y,g:Y

Z是两个函数,则

⑴如果f和g是满射的，则g

f

也是满射的；

⑵如果f和g是入射的，则g

f

也是入射的；

⑶如果f和g是双射的，则g

f

也是双射的。证明：⑴设f和g是满射的，因g

f:XZ,任取z∈Z,因g:Y

Z是满射的，所以存在y∈Y,使得z=g(y),又因f:X

Y是满射的，所以存在x∈X,使得y=f(x),于是有z=g(y)=g(f(x))=g

f(x),所以g

f

是满射的。⑵设f和g是入射的，因g

f:XZ,任取x1,x2∈X,x1≠x2，因f:X

Y是入射的，f(x1)≠f(x2),而f(x1),f(x2)∈Y，因g:Y

Z是入射的，g(f(x1))≠g(f(x2))

即g

f(x1)≠g

f(x2)所以g

f

也是入射的。

.14定理3⑴如果gf

是满射的，则g是满射的；⑵如果gf

是入射的，则f是入射的；

⑶如果gf

是双射的，则f是入射的和g是满射的。定理4f:X

Y是函数,则

f

IX=f且IY

f=f

。.155-3逆函数R是A到B的关系，其逆关系RC是B到A的关系。

RC={<y,x>|<x,y>R}f:XYfC:YX,是否是函数？。3。2。1。c。b。a。3。2。1。c。b。af:XYfC:YX.16定理1若f是XY的双射，则fC是YX的函数。证明：（1）对任意的y∈Y，由f是双射，得f是满射，所以ranf=Y

故domfC=ranf=Y

（2）对任意的y∈Y，若存在x1∈X，x2∈X使

<y,x1>∈fC

且<y,x2>∈fC

则<x1,y>∈f且<x2,y>∈f

由于f是单射，有x1=x2。由（1）、（2），fC是YX的函数。.17逆函数的定义定义：设f是XY的双射函数，则称fC：YX为f的逆函数，并记f-1。定理：f-1是YX的双射函数。证明：由于ranf-1=domf=X，所以，f-1是满射。对任意x∈X，若存在y1,y2∈Y,使得

<y1,x>∈f-1

且<y2,x>∈f-1

则<x,y1>∈f且<x,y2>∈f，由于f是函数，所以y1=y2，即f-1是单射。因此，f-1是双射。.18二.性质1.定理1设f:XY是双射的函数，则(f-1)-1=f。

2.定理2设f:XY是双射的函数，则有

f-1

f=IX

且f

f-1=IY。证明：先证明定义域、陪域相等。因为f:XY是双射的，f-1:YX也是双射的，所以

f-1

f:X

X,IX:X

X可见f-1

f与IX

具有相同的定义域和陪域。再证它们的对应规律相同：x∈X，因f:XY，yY,使得y=f(x),又f可逆，故f-1(y)=x，于是

f-1

f(x)=f-1(f(x))=f-1(y)=x=IX(x)

同理可证

f

f-1

=IY。

.193.定理3令f:X

Y,g:Y

X是两个函数,如果g

f=IX

且f

g=IY,则g=f-1

。证明：⑴证f和g都可逆。因为g

f=IX，IX是双射的，由关系复合性质3得，f是入射的和g是满射的。同理由

f

g=IY，得g是入射的和f是满射的。所以f和g都可逆。⑵显然f-1和g具有相同的定义域和陪域。X

Y。。。。。123ab。cf。。。123Xf-1。。。123X。。。123XIX.20⑶证明它们的对应规律相同。任取yY，f-1(y)=f-1

IY(y)

=f-1

(f

g)

(y)

=(f-1

f)

g

(y)

=(