离散数学-函数.ppt

《离散数学-函数.ppt》由会员分享，可在线阅读，更多相关《离散数学-函数.ppt（36页珍藏版）》请在三一办公上搜索。

1、1,第6章 函数,2,主要内容,6.1 函数的概念 6.2 复合函数与逆函数6.3 基数的概念6.4 基数的比较,3,6.1 函数的概念,定义 函数一种特殊的关系亦称映射或变换设A和B是非空集合,f是一个从A到B的关系，如果对于每一个aA，均存在唯一的bB，使得f，则称关系f是由A到B的一个函数。记作f:AB。特殊地，当A=B时，称f是A上的函数f通常记作f(x)=y,4,例：判断以下关系是否为函数,5,例,例 设E是全集，A E，那么A的特征函数A是E到0,1的函数：a E，,例设E=a,b,c,d,A=b,dA:E0,1A=,6,设A和B是全集E的任意两个子集,对所有xE,下列关系式成立x

2、(A(x)=0)A=x(A(x)=1)A=Ex(A(x)B(x)ABx(A(x)=B(x)A=B A(x)=1A(x)AB(x)=A(x)B(x)AB(x)=A(x)+B(x)AB(x)AB(x)=AB(x)=A(x)AB(x),7,函数的定义域和值域,设f:XYXf的前域(定义域dom f)Y f的陪域(值域ran f Y)f(x)=yx函数的自变元y自变元x的函数值，也称为x的像dom f=Xran f=f(X)如果f(x)=y1和f(x)=y2,那么y1=y2,8,设f:XYX Xf(X)=y|x(xXf(x)=y)Y称f(X)为X的象称X为f(X)的原象例 f:NN,f(x)=2x.A

3、=N偶=0,2,4,6,=2k|kN,f(A)=0,4,8,12,=4k|kNB=2+4k|kN=2,6,10,14,B的原象=1+2k|kN=1,3,5,7,=N奇,象(image)与原象(preimage),9,例,假定f:a,b,c,d1,2,3,4,f(a)=1;f(a,b)=1,3;f(a,b,c)=1,3;ranf=f(a,b,c,d)=1,3,4;,10,定义 设f:XY,g:WZ,如果X=W,Y=Z,且对每一xX有f(x)=g(x)则称f=g.函数相等的定义和关系相等的定义一致必须有相同的前域与陪域和相等的序偶集合例f:II,f(x)=x2g:1,2,3I,g(x)=x2是两个

4、不同的函数,11,通常用BA表示从集合A到集合B的所有函数的集合,读作B上A BA=f|f:AB设A=m,B=n，共有多少个A到B的函数？BA=nm例：设A a,b,c，B 0,1。则共有个A到B的函数(它们分别是A的个子集的特征函数)，它们是 f1,f2,f3,f4,f5,f6,f7,f8,12,函数是特殊的关系，故也可用关系图或关系矩阵来表示函数 例：集合A 1,2,3,4上的函数f,13,特殊函数类,满射、入射和双射定义6.1.3 设f 是从X到Y的函数如果xx蕴含着f(x)f(x)(即f(x)=f(x),那么x=x),那么f 是入射(injection,单射，一对一的，1-1)如果f(

5、X)=Y,那么f 是满射(surjection,映上的,onto)如果f 既是满射又是入射,那么f 是双射(bijection,1-1,onto)双射常称作一一对应，又称集合同构(set isomorphism),14,例 设A和B是两个集合，若存在b B使得对任意a A皆有f(a)b，则称f是常函数一般说来，常函数不是入射，也不是满射(除非B是一个一元集合)。例6.1.10 设R是一集合X上的等价关系,函数 g:XXR,g(x)=xR 叫做从X到商集XR的规范映射.例 设X=a,b,c,d,Y=0,1,2,3,4,f:XY,f(a)=1,f(b)=0,f(c)=1,f(d)=3f 诱导的X上

6、的等价关系R有等价类a,c,b，d从X到XR的规范映射 g:a,b,c,da,c,b,d g(a)=a,c,g(b)=b g(c)=a,c,g(d)=d,15,定理 若f是到的函数，其中和都是非空有限集，且#，那么：f是一个入射 iff f是一个满射。证明 必要性若f是一个入射，则#f()，故#f()#，而是有限集，故f()，因此，f是一个满射。充分性若f是一个满射，则f()，于是#f()，因为是有限集，故f是一个入射。定理的结论只在有限集的情况下才有效,16,例,A到B存在入射，|A|B|,A到B存在满射，|A|B|,A到B存在双射，|A|=|B|，称A和B等势,17,6.2 复合函数与逆函

7、数,定理 设g:XY和 f:YZ是函数,那么从X到Z的复合关系是一个X到Z的函数，记为fg，定义为对一切xX,(fg)(x)=f(g(x).注意：复合函数gf就是复合关系fg。要注意的是为了方便，当将其看作复合函数时，在其表示记号中颠倒f和g的位置而写成gf 定理 若f是到的函数，则fIAIBf f,18,设集合A=a1,a2,a3,a4,B=b1,b2,b3,b4,b5,Cc1,c2,c3,c4 函数f:AB和g:BC，分别定义为f=,g=,例,gf=,19,定理6.2.3 函数复合是可结合的.即f,g和h都是函数,那么(f g)h=f(gh).定义如果对某集合X,f:XX,那么函数f 能同

8、自身复合任意次.f 的n次复合定义如下:(1)f 0(x)=x(2)f n+1(x)=f(f n(x),nN,20,定理6.2.4 设g:XY和f:YZ是函数,f g是复合函数如果f 和g是满射,那么f g是满射如果f 和g是入射,那么f g是入射如果f 和g是双射,那么f g是双射证明(a):zZ,因为f 是满射,存在yY,使得f(y)=z又g是满射,存在xX,使g(x)=y于是f g(x)=f(g(x)=f(y)=z,即对Z中任一元素都能找到其原像 f g是满射,21,证明(b):设x1,x2X，x1x2g是入射g(x1)g(x2)又f 是入射,且g(x1)g(x2)f g(x1)f g(

9、x2)即f g是入射证明(c):因为f 和g是双射,由(a)和(b)得f g是满射和入射,所以f g是双射,22,例,(a)设E是偶整数集合,M是奇整数集合.双射函数f 和g定义如下:g:IE,g(x)=2x；f:EM,f(x)=x+1 f g:IM,f g(x)=2x+1(b)g:0,1 0,1/2,g(x)=x/2 f:0,1/2(0,1),f(x)=x+1/4 f g:0,1(0,1),f g(x)=x/2+1/4,23,定理的逆命题并不成立,24,定理 设g:XY和f:YZ是函数，f g是复合函数如果f g是满射,那么f 是满射如果f g是入射,那么g是入射如果f g是双射,那么f 是

10、满射而g是入射 证明(a):zZ(只需证明z有原像)f g是X到Z的满射，xX,f g(x)=z记y=g(x)，显然yY，且f(y)=z，说明f 是满射证明(b):假若不然，存在x1,x2X，x1x2，但g(x1)=g(x2)则必有fg(x1)=fg(x2)，与f g是入射矛盾,25,逆函数,函数的逆关系不一定是函数例X=1,2,3,Y=a,b,c f=,是函数 f-1=,不是函数定理6.2.6 设f:XY是一双射函数,那么f 的逆关系 f-1是一双射函数,f-1:YX,26,定理6.2.7 若f是到的双射，则f-1f=IA,f f-1=IB证明：xA,若f(x)=y,则f-1(y)=x 则f

11、-1f(x)=f-1(f(x)=f-1(y)=x 所以,f-1f=IA 类似可证f f-1=IB,27,定理 若f是到的函数，g是到的函数，且gf=IA,f g=IB，则g f-1，f g-1。证明 我们只证明g f-1，f g-1同理可得因为IA和IB都是双射，这样从gf=IA可知f是入射，g是满射；又从f g=IB可知g是入射，f是满射。也即g和f皆是双射。从而：g gIB g(f f-1)(g f)f-1 IA f-1 f-1,28,练习,设A=a,b,c,d,B=1,2,3,4,和均是由到的函数,这些函数的值域分别为 f()=1,2,4,()=1,3,h()=这三个函数中,有逆函数。判

12、断以下函数是否有逆函数f:I,f(i)=3i()g:RR,f(r)=3r(),h,N,Y,29,定义设f是到的函数，若存在到的函数g使得gf=IA，则称f是左可逆的，并称g是f的左逆；类似地，若存在到的函数h使得f h=IB，则称f是右可逆的，并称h是f的右逆；若f既是左可逆的，又是右可逆的，则称f是可逆的。例：设f1、f2、g1、g2是四个上的函数，其中,左逆(右逆、逆)不一定存在；也不一定唯一,30,例,31,定理 f 有左逆元当且仅当f 是入射 f 有右逆元当且仅当f 是满射 f 有左逆元和右逆元当且仅当f 是双射 如果f有左逆g且有右逆h,那么g=h=f-1证明(a)：必要性：假设g是

13、f 的左逆元,gf=IA,IA是双射,f 是入射充分性：用构造性证明.f 是入射，yf(X),必存在唯一的xX使f(x)=y 选取任意元素x0X,定义Y到X的函数g如下:,g是f 的左逆元,32,33,证明(b)：必要性：假设h是f 的右逆元,fh=IB,IB是双射,f 是满射充分性：用构造性证明.f 是满射，构造Y到X的函数h如下:h(y)=x,其中xX且f(x)=y(若X中有多个元素在f作用下的象为y，则可从中任取一个作为y在h作用下的象),34,证明(d)：因为 gf=IA和f h=IB则g=g IB=g(f f-1)=(g f)f-1=IA f-1=f-1 h=IA h=(f-1f)h

14、=f-1(f h)=f-1 IB=f-1以上定理实质上指出了逆函数的存在性、唯一性与相互性唯有双射是可逆的，且其逆关系即是它的左逆兼右逆(称为逆函数或反函数)每个双射的逆函数是唯一的(即是它的逆关系)。逆函数是相互的，即(f-1)-1 f,35,定理 若f是到的双射，g是到的双射。那么(gf)-1=f-1 g-1 由条件证明可得，gf是到的双射。此外，由于(gf)(f-1 g-1)=g(f f-1)g-1=g IB g-1=g g-1=IC和(f-1 g-1)(gf)=f-1(g-1 g)f=f-1 IC f=f-1 f=IA可得(gf)-1=f-1 g-1,36,推论 若f是集合上的双射，n，则(f-1)n(f n)-1这样，我们可定义集合上的双射的负次方幂为f-n(f-1)n(f n)-1，其中n,