离散数学(函数)精ppt课件

.,函数,第八章,.,4.1函数的概念,函数定义函数与关系函数相等特殊函数:单射满射双射,8.1函数的定义与性质,.,函数的定义,设F为二元关系,若xdomF都存在唯一的yranF使xFy成立,则称F为函数对于函数F,如果有xFy,则记作y=F(x),并称y为F在x的值.,x自变元y在F作用下x的像,.,判断下列关系哪个构成函数,1,1,1,.,函数的定义,设F,G为函数,则F=GFGGF如果两个函数F和G相等,一定满足下面两个条件：(1)domF=domG(2)xdomF=domG都有F(x)=G(x),函数F(x)=(x21)/(x+1),G(x)=x1不相等,因为,domFdomG.,.,函数的定义,设A,B为集合,如果f为函数,domf=A,ranfB,则称f为从A到B的函数,记作f：AB.,.,函数的定义,在f中,A,domf,=,定义域,B,ranf,值域,(函数像的集合),例：设X=张三、李四、王五，Y=法国、美国、俄罗斯、英国f=,.,函数与关系,函数的定义域是A,而不是A的某个真子集；一个x只能对应于唯一的y；AB的子集并不都能成为A到B的函数。,.,例,A=a,b,c,B=0,1AB=,|P(AB)|=26,但只有23个子集定义为X到Y的函数.,f0=,f1=,f2=,f7=,.,函数的定义,所有从A到B的函数的集合记作BA,表示为BA=f|f：AB|A|=m,|B|=n,且m,n0,|BA|=nmA=,则BA=B=A且B=,则BA=A=,.,函数的定义,设函数f：AB,A1A,B1B(1)A1在f下的像f(A1)=f(x)|xA1特别的,f(A)称为函数的像(2)B1在f下的完全原像f1(B1)=x|xAf(x)B1注意：函数值与像的区别：函数值f(x)B,像f(A1)B一般说来f1(f(A1)A1,但是A1f1(f(A1),.,例,例设f：NN,且令A=0,1,B=2,那么有f(A)=f1(B)=,f(0,1)=f(0),f(1)=0,2f1(2)=1,4,.,函数的定义,设f：AB,(1)若ranf=B,则称f:AB是满射的(2)若yranf都存在唯一的xA使得f(x)=y,则称f:AB是单射的(3)若f:AB既是满射又是单射的,则称f:AB是双射的,.,例,单射,映射（函数）,双(单、满)射,满射,.,例,判断下面函数是否为单射,满射,双射的?(1)f:RR,f(x)=x2+2x1(2)f:Z+R,f(x)=lnx,Z+为正整数集(3)f:RZ,f(x)=x(4)f:RR,f(x)=2x+1(5)f:R+R+,f(x)=(x2+1)/x,其中R+为正实数集.,.,定理,令A和B是有限集，若A和B的元素个数相同，即|A|=|B|，则f:AB是单射的，当且仅当它是一个满射。,此定理对无限集不一定成立。例如：f:II,f(x)=2x整数映射到偶整数(单射、非满射),.,例,对于给定的集合A和B构造双射函数f:AB(1)A=P(1,2,3),B=0,11,2,3(2)A=0,1,B=1/4,1/2(3)A=Z,B=N(4),B=1,1,.,例,对于给定的集合A和B构造双射函数f:AB(2)A=0,1,B=1/4,1/2,(1,1/2),f(x)=(x+1)/4,.,课堂练习,对于给定的集合A和B构造双射函数f:ABA=-1,1),B=2,7),.,例,对于给定的集合A和B构造双射函数f:AB(3)A=Z,B=N,(3)将Z中元素以下列顺序排列并与N中元素对应：Z：0112233N：0123456这种对应所表示的函数是：,.,函数的定义,(1)设f:AB,如果存在cB使得对所有的xA都有f(x)=c,则称f:AB是常函数.(2)称A上的恒等关系IA为A上的恒等函数,对所有的xA都有IA(x)=x.(3)设,为偏序集，f:AB，如果对任意的x1,x2A,x1x2,就有f(x1)f(x2),则称f为单调递增的；如果对任意的x1,x2A,x1x2,就有f(x1)f(x2),则称f为严格单调递增的.类似的也可以定义单调递减和严格单调递减的函数.,.,函数的定义,(4)设A为集合,对于任意的AA,A的特征函数A:A0,1定义为A(a)=1,aAA(a)=0,aAA(5)设R是A上的等价关系,令g:AA/Rg(a)=a,aA称g是从A到商集A/R的自然映射,.,例,(1)偏序集,R为包含关系,为一般的小于等于关系,令f:P(a,b)0,1,f()=f(a)=f(b)=0,f(a,b)=1,f是,单调递增的,但不是严格单调递增的,(2)A的每一个子集A都对应于一个特征函数,不同的子集对应于不同的特征函数.例如A=a,b,c,则有a,b=,.,例,(3)不同的等价关系确定不同的自然映射,恒等关系确定的自然映射是双射,其他自然映射一般来说只是满射.,A=1,2,3,R=,IAg:AA/R,g(1)=g(2)=1,2,g(3)=3,.,课堂练习,证明f(AB)f(A)f(B),保序性：,ABf(A)f(B),ABAABB,f(AB)f(A)f(AB)f(B),方法1：,f(AB)f(A)f(B),xAf(x)f(A),.,课堂练习,证明f(AB)f(A)f(B),保序性：,xAf(x)f(A),对于y,yf(AB),则x,xAB,使得f(x)=y,方法2：,yf(A)f(B),即xAxB,使得f(x)=y,f(x)f(A)f(x)f(B),.,函数的定义,设f和g是定义域为自然数N上的函数f(n)=O(g(n).若存在正数c和n0使得对一切nn0有0f(n)cg(n)f(n)=(g(n).若存在正数c和n0使得对一切nn0有0cg(n)f(n)f(n)=o(g(n).若对任意正数c存在n0使得对一切nn0有0f(n)cg(n)f(n)=(g(n).若对任意正数c存在n0使得对一切nn0有0cg(n)f(n)f(n)=(g(n)f(n)=O(g(n)且f(n)=(g(n),.,函数的定义,.,函数的定义,1+2+nn+n+n=n2对于n1所以1+2+n=,例：1+2+n,O(n2),又1+2+n1+1+1=n对于n1所以1+2+n=,(n),综上1+2+n=?,.,函数的定义,1+2+n,=(n2),.,4.2逆函数和复合函数,复合函数反函数,8.2函数的复合与反函数,关系与逆关系:R-1R函数与反函数。可能出现的问题：定义域(dom(f-1)A)函数值(一对多),.,函数的复合,设F,G是函数,则FG也是函数,且满足(1)dom(FG)=x|xdomFF(x)domG(2)xdom(FG)有FG(x)=G(F(x),证先证明FG是函数.因为F,G是关系,所以FG也是关系.若对某个xdom(FG)有xFGy1和xFGy2,则FGFGt1(FG)t2(FG)t1t2(t1=t2GG)（F为函数）y1=y2（G为函数）所以FG为函数,.,函数的复合,f:XY,g:WZ,F=,G=,X=1,2,Y=3,4,W=3,6,Z=7,9,FG=,f=,g=,fg=,(1)dom(FG)=x|xdomFF(x)domG,.,函数的复合,推论设f:AB,g:BC,则fg:AC,且xA都有fg(x)=g(f(x),证由上述定理知fg是函数,且dom(fg)=x|xdomff(x)domg=x|xAf(x)B=Aran(fg)rangC因此fg:AC,且xA有fg(x)=g(f(x),.,求,例,fg(1),=g(f(1),=g(p)=b,.,函数的复合,定理设f:AB,g:BC(1)如果f:AB,g:BC满射,则fg:AC也满射(2)如果f:AB,g:BC单射,则fg:AC也单射(3)如果f:AB,g:BC双射,则fg:AC也双射定理设f:AB,则f=fIB=IAf,证(1)任取cC,由g:BC的满射性,bB使得g(b)=c.对于这个b,由f:AB的满射性，aA使得f(a)=b.由合成定理有fg(a)=g(f(a)=g(b)=c从而证明了fg:AC是满射的,.,函数的复合,定理设f:AB,g:BC(2)如果f:AB,g:BC单射,则fg:AC也单射,证(2)假设存在x1,x2A使得fg(x1)=fg(x2)由合成定理有g(f(x1)=g(f(x2)因为g:BC是单射的,故f(x1)=f(x2).又由于f:AB是单射的,所以x1=x2.从而证明fg:AC是单射的.,.,函数的复合,注意：定理逆命题不为真,即如果fg:AC是单射(或满射、双射)的,不一定有f:AB和g:BC都是单射(或满射、双射)的.,.,多个函数可复合,复合函数性质,解:goh=,fo(goh)=,fog=,(fog)oh=,.,逆关系,已知：集合A=1,2,3,B=a,b,c令函数f:ABf=,但函数f的逆关系：,f-1=,不是函数,原函数值域ran(f)=dom(f-1)B,原函数f(多对一),原因,.,反函数,定理设f:AB是双射的,则f1:BA也是双射的.,证明思路：先证明f1:BA，即f1是函数且domf1=B,ranf1=A.再证明f1:BA的双射性质.,.,反函数,证因为f是函数,所以f1是关系,且domf1=ranf=B,ranf1=domf=A对于任意的xB=domf1,假设有y1,y2A使得f1f1成立,则由逆的定义有ff根据f的单射性可得y1=y2,从而证明了f1是函数，且是满射的.,若存在x1,x2B使得f1(x1)=f1(x2)=y,从而有f1f1ffx1=x2对于双射函数f:AB,称f1:BA是它的反函数.,.,反函数,定理(1)设f:AB是双射的,则f1f=IB,ff1=IA(2)对于双射函数f:AA,有f1f=ff1=IA,.,例,求:ff-1及f-1f,解:,f,f-1,f-1f,ff-1,=IA,=IB,例,.,定理是一一,对应函数,则,(双射),定理,均为一一对应函数,则,(双射),定理,定理,.,分段函数的复合,.,4.4基数的概念,自然数集合等势有(无)限集合基数,8.3双射函数与集合的基数,.,定义给定A的后继集为,若为,则,可写成如下形式,自然数集合,可简记为,.,若命名集合为0,则,L,得到自然数集合,自然数集合,自然数集合,(n-1)+=0,1,2,.n-1=n,L,.,定义给定两个集合A与B,当且仅当存在着从A到B的双射函数,称集合A与B是等势的,记为AB.,等势,等势,.,等势,等势,证明:设集合族为S对任意AS,AA.若A,BS,AB,则BA若A,B,CS,AB,BC,则AC,定理在集合族上等势关系是一个等价关系.,(1)IA是从A到A的双射(2)若f:AB是双射，则f1:BA是从B到A的双射.(3)若f:AB，g:BC是双射，则fg:AC是从A到C的双射,.,定义若有一个从集合0,1,n-1到A的双射函数,则称A是有限(穷)的;若A不是有限(穷)的,则它是无限的.,有(无)限集合,有(无)限集合,集合A有限A某个自然数,.,基数,定义(1)对于有限集合A,称与A等势的那个惟一的自然数为A的基数,记作cardA(也可以记作|A|)cardA=nAn,一个集合是有限的当且仅当它与某个自然数等势；,|有限集合|=元素个数|空集|=0,.,等势,等势,例1:试证集合A=a,b,c,d与B=,等势,证明:设f:AB,f(a)=,f(b)=,f(c)=,f(d)=,则f是AB的双射函数,所以AB,.,等势,等势,例2:试证自然数集合N与集合A=2n|nN等势.,证明:设f:NA,且f(n)=2n,n=0,1,2,则f是NA的双射函数,所以NA.,.,等势,等势,例3:设A=(0,1)=x|xR0x1,证明A与实数集合R等势.,.,等势,f是单射的.对于任意的x1和x2,x1,x2(0,1)(2x1-1),(2x2-1)(-,)于是tan(2x1-1)=tan(2x2-1)(2x1-1)=(2x2-1)x1=x2,所以f是单射函数.,2,2,2,2,2,2,2,.,等势,因此AR.,因为f单调，所以f是入射的.,2,.,例4,则f是Z到N的双射函数.从而证明了ZN.,ZN,.,例5,0,1(0,1).其中(0,1)和0,1分别为实数开区间和闭区间.令f:0,1(0,1),.,例6,对任何a,bR,ab,0,1a,b，双射函数f:0,1a,b,f(x)=(ba)x+a类似地可以证明,对任何a,bR,ab,有(0,1)(a,b).,.,定义有限集、或者与自然数集合等势的任意集合称为可数集(可列集),无限可数集的基数用0表示.,可数集,可数集,.,可数集,可数集举例,例A=a,b,c,B=1,3,5,2n+1,C=3,12,27,3(n+1)2,整数集Z,有理数集Q.,.,定理设A是集合,A为可数集的充要条件是可排列成A=a1,a2,.,an,.的形式.,可数集充要条件,一个集合是可数集当且仅当可以将它的所有元素逐个的排成一个序列,使得序列中每个元素都属于这个集合,并且这个集合中的每个元素都在序列中的某个位置出现且仅出现一次.对于任何的可数集,它的元素都可以排列成一个有序图形.换句话说,都可以找到一个“数遍”集合中全体元素的顺序.,可数集充要条件,.,例,NNN.NN中所有的元素排成有序图形,.,例,NQ.双射函数f:NQ,其中f(n)是n下方的有理数.,-2/1,5,-1/1,4,-3/1,18,2/1,10,3/1,11,0/1,0,1/1,1,-2/2,-1/2,3,-3/2,17,2/2,3/2,12,0/2,1/2,2,-2/3,6,-1/3,7,-3/3,2/3,9,3/3,0/3,1/3,8,-2/4,-1/4,15,-3/4,16,2/4,3/4,13,0/4,1/4,14,PLAY,.,例:可数个两两不相交的可数集的并是可数集.,.,可数集,可数集的性质：可数集的任何子集都是可数集.两个可数集的并是可数集.两个可数集的笛卡儿积是可数集.可数个可数集的笛卡儿积仍是可数集.,.,证明是可数集,是可数的.,令,是双射的,故是可数集.,例:Q是可数集.,定理:Q可数集,.,有关势的结果,等势结果NZQNN任何实数区间都与实数集合R等势,不等势的结果:定理(康托定理)(1)NR；(2)对任意集合A都有AP(A)证明思路：(1)只需证明任何函数f:N0,1都不是满射的.任取函数f:N0,1,列出f的所有函数值，然后构造一个0,1区间的小数b，使得b与所有的函数值都不相等.,.,证明,证(1)规定0,1中数的表示.对任意的x0,1,令x=0.x1x2,0xi9规定在x的表示式中不允许在某位后有无数个9的情况.设f:N0,1是任何函数，列出f的所有函数值：f(0)=0.a1(1)a2(1)f(1)=0.a1(2)a2(2)f(n1)=0.a1(n)a2(n)令y的表示式为0.b1b2,并且满足biai(i),i=1,2,那么y0,1,且y与上面列出的任何函数值都不相等.这就推出yranf,即f不是满射的.,.,基数,定义(1