离散数学第二学期9讲函数

1函数内容提要函数(映射)定义象,原象单射,满射,双射,计数问题常数函数,恒等函数,特征函数,单调函数,自然映射复合,逆函数2函数(function)函数:F是函数

F是单值的二元关系F单值:xdomF,y,zranF,xFyxFzy=z函数亦称映射(mapping)F(x)=y<x,y>FxFy是函数,称为空函数常用F,G,H,…,f,g,h,…表示函数.xyz非单值单值3偏函数(partialfunction)偏函数:domFAA到B的偏函数:domFA且ranFB偏函数记作

F:AB,称A为F的前域,A到B的全体偏函数记为ABAB={F|F:AB}4例1例1:设A={a,b},B={1,2},求AB.解:|A|=2,|B|=2,|AB|=4,|P(AB)|=24=16.f0=,f1={<a,1>},f2={<a,2>},f3={<b,1>},f4={<b,2>},f5={<a,1>,<b,1>},f6={<a,1>,<b,2>},f7={<a,2>,<b,1>},f8={<a,2>,<b,2>}.AB={f0,f1,f2,f3,f4,f5,f6,f7,f8}.#非函数:{<a,1>,<a,2>},{<b,1>,<b,2>},{<a,1>,<a,2>,<b,1>},…5全函数(totalfunction)全函数:domF=A全函数记作

F:AB

A到B的全体全函数记为BA或ABBA=AB={F|F:AB}6关于BA的说明BA={F|F:AB}={F|F是A到B全函数}|BA|=|B||A|.当A=时,BA={}当A且B=时,BA=AB=,

但AB={}.7真偏函数(properpartialfunction)真偏函数:domFA,真偏函数记作F:AB,A到B的全体真偏函数记为ABAB={F|F:AB}8例1(续)例1(续):设A={a,b},B={1,2},求AB.解:f0=,f1={<a,1>},f2={<a,2>},f3={<b,1>},f4={<b,2>},f5={<a,1>,<b,1>},f6={<a,1>,<b,2>},f7={<a,2>,<b,1>},f8={<a,2>,<b,2>}.AB={f0,f1,f2,f3,f4}.#9三者关系AB=ABAB

偏函数AB

domFA全函数AB

domF=A真偏函数AB

domFA说明:FABFdomFBFABFdomFB10函数(function)定义定义3.1：X和Y是两个集合，f是X到Y的关系，如果对于任意x∈X，有唯一的y∈Y使得<x,y>∈f，称关系f为函数，记作：f：X→Y或XY。称x为原象,y为象。1.关系;2.X中任何元都有象domf=A;3.唯一象11例1例1:设A={a,b},B={1,2}解:f1={<a,1>},f2={<a,2>,<b,1>},f3={<b,1>,<b,2>,<a,1>},f4={<a,1>,<b,1>},X中任何元都有象domf=A;唯一象12函数相等定义：设函数f:A→B，g:C→D，如果A=C，B=D，且对于所有x∈A和x∈C有f(x)=g(x)，则称函数f和g相等，记作f=g。函数是序偶的集合，故两个函数相等可用集合相等的概念予以定义。

13函数的计数A={0,1,2}，B={a,b}，写出A到B上的所有函数。14函数的计数（续）A={a,b}，B={0,1,2}，写出A到B上的所有函数。15函数的计数规律A到B的全体全函数记为BABA={f|f:AB}一般说来，如果|A|=n，|B|=m，m，n非零，则|BA|=mn16满射定义3.5(1)：对于X→

Y的映射f，如果ranf=Y，即Y的每一个元素是X中一个或多个元素的象，则称这个映射为满射(或到上映射)。

(设f:X→Y是满射，则对y∈Y，必有x∈X使得f(x)=y，即f(X)=Y)17满射18单射定义3.5(2)：对于X→Y的映射f，若X中没有两个元素有相同的象，则称这个映射为入射(单射)。

(设f:X→Y是单射，即是对于任意x1,x2∈X，如果x1≠x2，则f(x1)≠f(x2)或

若f(x1)=f(x2)则x1=x2)19单射20双射定义3.5(3)：从X到Y的一个映射，若既是满射又是单射，则称此映射为双射(或一一映射)21双射22函数性质设f:AB,单射(injection):f是单根的

满射(surjection):ranf=B双射(bijection):f既是单射又是满射,亦称为一一对应(one-to-onemapping).非单射非满射23例判断下述函数是否为单射，满射，双射函数f:N→N，f(n)=2n函数f:N→N，f(2n)=n，f(2n+1)=n函数f:N→N，f(n)=n+1函数f:Z→Z，f(n)=n+1单射但非满射满但非单单射但非满射双射24计数(counting)问题设|A|=n,|B|=m,问AB中有多少单射,满射,双射?单射:P(m,n),m>=n;0,m<n.满射:m!S(n,m),S为第二类Stirling数,m<=n;0,m>n.双射:n!,m=n;0,m!=n.25例2(1)例2:(1)A={a,b},B={1,2,3},f1={<a,1>,<b,2>},f2={<a,1>,<b,3>},f3={<a,2>,<b,1>},f4={<a,2>,<b,3>},f5={<a,3>,<b,1>},f6={<a,3>,<b,2>}.P3226例2（2）例2（2）

:A={a,b,c},B={1,2},f1={<a,1>,<b,1>,<c,2>},f2={<a,1>,<b,2>,<c,1>},f3={<a,2>,<b,1>,<c,1>},f4={<a,1>,<b,2>,<c,2>},f5={<a,2>,<b,1>,<c,2>},f6={<a,2>,<b,2>,<c,1>}.A分成|B|个非空集合的分法=327例2(3)例2:(3)A={a,b,c},B={1,2,3},f1={<a,1>,<b,2>,<c,3>},f2={<a,1>,<b,3>,<c,2>},f3={<a,2>,<b,1>,<c,3>},f4={<a,2>,<b,3>,<c,1>},f5={<a,3>,<b,1>,<c,2>},f6={<a,3>,<b,2>,<c,1>}.28性质性质：若X、Y是有限集，且存在双射f:X→Y，则|X|=|Y|29计数(counting)问题设|A|=n,|B|=m,问AB中有多少单射,满射,双射?n<m时,AB中无满射和双射,单射个数为m(m-1)…(m-n+1)n=m时,AB中双射个数为

n!n>m时,AB中无单射和双射,满射个数为（第二类Stirling数）30象(image),原象(preimage)设f:AB,A’A,B’B象:A’的象是f(A’)={y|x(xA’f(x)=y)

}Bf(A)=ranf原象:B’的原象是f-1(B’)={x|y(yB’f(x)=y)

}AA’f(A’)f-1(B’)B’31象,原象(举例)例:f:NN,f(x)=2x.

A’=N偶={0,2,4,6,…}={2k|kN},

f(A’)={0,4,8,12,…}={4k|kN}

B’={2+4k|kN}={2,6,10,14,…},

f-1(B’)={1+2k|kN}={1,3,5,7,…}=N奇#32特殊函数常数函数:xA,f(x)=bB恒等函数:IA:AA,IA(x)=x特征函数:A:E{0,1},A(x)=1xA单调函数:f:AB,<A,A>,<B,B>偏序集,x,yA,xAyf(x)Bf(y)单调增,单调减,严格单调自然映射:R为A上等价关系,f:AA/R,f(x)=[x]R.33自然映射(举例)例:A={a,b,c,d,e,f},A/R={{a,b},{c,d,e},{f}},[a]=[b]={a,b},[c]=[d]=[e]={c,d,e},[f]={f},F:AA/R,F(x)=[x].F(a)={a,b},F(b)={a,b},F(c)={c,d,e},F(d)={c,d,e},F(e)={c,d,e},F(f)={f}.#abcdef34函数运算复合函数:性质,左(右)单位元逆函数及存在条件35函数复合(composite)定义:设g:AB,f:BC,则g○f={<x,z>|xAzCy(yBy=g(x)z=f(y))}36定理定理：两个函数的复合是一个函数证明：设g:Y→Z，f:X→Ya)存在性,即x∈X，ｚ使<x,z>∈f○g.

x∈X，f为函数，序偶<x,y>∈f使得f(x)=y,而f(x)∈f(X)Y，加上g是函数，故必有z∈Z，z=g(y)成立，从而z=g(f(x))，即<x,z>∈f○g，即X中每个x对应Z中某个zb)唯一性.设f○g中包含序偶<x,z1>和<x,z2>,则必存在y1,y2∈Y，使得<x,y1>,<x,y2>∈f，<y1,z1>、<y2,z2>∈g,因为f是一个函数，故y1=y2,再由g是一个函数，故z1=z237复合的性质定理3.4:设g:AB,f:BC,g○f:AC,则(a)f,g均为满射,则

g○f也是满射.(b)f,g均为单射,则

g○f也是单射.(c)f,g均为双射,则

g○f也是双射.#38复合的性质(续)定理3.5:设g:AB,f:BC,则(1)若g○f为满射,则f是满射.(2)若g○f为单射,则g是单射.(3)若g○f为双射,则g是单射,f是满射.#ggf39复合的左(右)单位元定理3.6:设f:AB,则f=IA○f=f○IB.#AABBIAIBf40复合的单调性定理3.7:设f:RR,g:RR,且f,g按是单调增的,则f○g也是单调增的.证明:xyf(x)f(y)g(f(x))g(f(y)).#41逆函数的存在性与关系相类比逆关系为交换序偶的元素次序<y、x>∈R-1

<x、y>∈R任意给定一个函数，它的逆不一定是函数。例如，函数

其逆为42定理3.9定理3.9：设f:X→Y是一双射函数，那么f-1是Y→X的双射函数。

证明：1.f-1为映射，即任给y∈Y都在X中有唯一象:f为满射，故任给y∈Y，存在x∈X，s.t.f(x)=y,即<x,y>∈f，因此必有<y,x>∈f-1又f是单射，因此满足上述条件的x必唯一，因此f-1必为映射

2.f-1为满射:ranf-1=domf=X

3.f-1为单射:任给y1,y2∈Y，y1≠y2，假设x1=f-1(y1)=f-1(y2)=x2,由映射定义知f(x1)=f(x2)，即y1=y2，矛盾。43逆函数(inversefunction)定义

:若f:AB为双射,则f-1:BA称为f的逆(反)函数.44例4f:Z→Z,n→n+1逆函数f:Z→Z,n→n-1函数f:-π/2，π/2→-1，1，y=sinx，可以定义它的反函数x=arcsiny。45单边逆设f:AB,g:BA左逆:g是f的左逆

g(f(x))=IA,右逆:g是f的右逆

f(g(x))=IB,ABfgIAIB46单边逆(举例)BABgfABAgff(g(x))=IBg(f(x))=IA47单边逆的存在条件定理10:设f:AB,且A,则(1)f

存在左逆

f

是单射;(2)f

存在右逆

f

是满射;(3)f存在左逆,右逆

f是双射.#g(f(x))

f(g(x))

48构造双射及求反函数|A|=m,|B|=n,AB存在双射

n=m|A|=,|B|=,BA,AB存在双射,如f:NN-{0,1,2},f(n)=n+3[0,1](0,1)?R(0,1)?NNN?01234567801234567849NNN双射?50方法1:用自然数性质

nNn0,,N,为奇数,使得n=2例:1=201,2=211,3=203,…,6