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

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

1、函 数,第 八 章,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=G FGGF 如果两个函数F 和 G 相等,一定满足下面两个条件：(1)domF=domG(2)xdomF=domG 都有F(x)=G(x),函数F(x)=(x21)/(

2、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；A B 的子集并不都能成为 A 到 B 的函数。,例,A=a,b,c,B=0,1 AB=,|P(AB)|=26,但只有 23 个子集定义为 X 到 Y 的函数.,f0=,f1=,f2=

3、,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 下的完全原像 f 1(B1)=x|xAf(x)B1注意：函数值与像的区别：函数值 f(x)B,像f(A1)B一般说来 f 1(f(A1)A1,但是A1f 1(f(A1),例,例 设 f：NN,且令A=0,1,B=2,那么有 f(A)=f 1(B)=,f(0,1)=f(0),f(1

4、)=0,2 f 1(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 是有限集，若

5、A 和 B 的元素个数相同，即|A|=|B|，则 f:A B是单射的，当且仅当它是一个满射。,此定理对无限集不一定成立。例如：f:I I,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:AB A=-1,1),B=2,7),例,对于给定的集合A和B构造双射函

6、数 f:AB(3)A=Z,B=N,(3)将Z中元素以下列顺序排列并与N中元素对应：Z：011 2 23 3 N：0 1 2 3 4 5 6 这种对应所表示的函数是：,函数的定义,(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 为严格单调递增的.类似的也可以定义单调递减和严格单调递减的

7、函数.,函数的定义,(4)设A为集合,对于任意的AA,A的特征函数 A:A0,1定义为 A(a)=1,aA A(a)=0,aAA(5)设R是A上的等价关系,令 g:AA/R g(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)不同的等价关系确定不同的自然映射,恒等关系确定的自然映射是双射,

8、其他自然映射一般来说只是满射.,A=1,2,3,R=,IA g:AA/R,g(1)=g(2)=1,2,g(3)=3,课堂练习,证明 f(AB)f(A)f(B),保序性：,A B f(A)f(B),AB A AB B,f(AB)f(A)f(AB)f(B),方法1：,f(AB)f(A)f(B),x A f(x)f(A),课堂练习,证明 f(AB)f(A)f(B),保序性：,x A f(x)f(A),对于y,y f(AB),则 x,x AB,使得f(x)=y,方法2：,y f(A)f(B),即 x A x B,使得f(x)=y,f(x)f(A)f(x)f(B),函数的定义,设f和g是定义域为自然数N

9、上的函数f(n)=O(g(n).若存在正数c和n0使得对一切nn0 有 0 f(n)cg(n)f(n)=(g(n).若存在正数c和n0使得对一切nn0有 0 cg(n)f(n)f(n)=o(g(n).若对任意正数c存在n0使得对一切nn0有 0 f(n)cg(n)f(n)=(g(n).若对任意正数c存在n0使得对一切nn0有 0 cg(n)f(n)f(n)=(g(n)f(n)=O(g(n)且 f(n)=(g(n),函数的定义,函数的定义,1+2+n n+n+n=n2 对于n 1 所以 1+2+n=,例：1+2+n,O(n2),又1+2+n 1+1+1=n 对于n 1 所以 1+2+n=,(n)

10、,综上 1+2+n=?,函数的定义,1+2+n,=(n2),4.2 逆函数和复合函数,复合函数反函数,8.2 函数的复合与反函数,关系与逆关系:R-1 R函数与反函数。可能出现的问题：定义域(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)有xF Gy1和 xFGy2,则 FGFGt1(FG)t2(FG)t1t2(t1=t2GG)（F为函数）y1=y2（G为函数）所以 FG

11、 为函数,函数的复合,f:X Y,g:W Z,F=,G=,X=1,2,Y=3,4,W=3,6,Z=7,9,F G=,f=,g=,f g=,(1)dom(F G)=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=A ran(fg)rang C因此 fg:AC,且xA有 fg(x)=g(f(x),求,例,f g(1),=g(f(1),=g(p)=b,函数的复合,定理 设f:AB,g:BC(1)如果 f:AB,g:BC满

12、射,则 fg:AC也满射(2)如果 f:AB,g:BC单射,则 fg:AC也单射(3)如果 f:AB,g:BC双射,则 fg:AC也双射定理 设 f:AB,则 f=f IB=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使得 f g(x1)=f g(x2)由合成定理有 g(f(x1)=g(f(x2)因为g:BC

13、是单射的,故 f(x1)=f(x2).又由于f:AB是单射的,所以x1=x2.从而证明f g:AC是单射的.,函数的复合,注意：定理逆命题不为真,即如果f g:AC是单射(或满射、双射)的,不一定有 f:AB 和 g:BC都是单射(或满射、双射)的.,多个函数可复合,复合函数性质,解:g o h=,f o(g o h)=,f o g=,(f o g)o h=,逆关系,已知：集合 A=1,2,3,B=a,b,c令函数 f:A B f=,但函数 f的逆关系：,f-1=,不是函数,原函数值域ran(f)=dom(f-1)B,原函数f(多对一),原因,反函数,定理 设 f:AB是双射的,则f 1:BA

14、也是双射的.,证明思路：先证明 f 1:BA，即f 1是函数且domf 1=B,ranf 1=A.再证明f 1:BA的双射性质.,反函数,证 因为 f 是函数,所以 f 1是关系,且 dom f 1=ranf=B,ran f 1=domf=A对于任意的 xB=dom f 1,假设有y1,y2A使得 f 1f 1成立,则由逆的定义有 ff根据 f 的单射性可得y1=y2,从而证明了f 1是函数，且是满射的.,若存在x1,x2B使得f 1(x1)=f 1(x2)=y,从而有 f 1f 1 ff x1=x2 对于双射函数f:AB,称 f 1:BA是它的反函数.,反函数,定理(1)设 f:AB是双射的

15、,则 f 1f=IB,f f 1=IA(2)对于双射函数 f:AA,有 f 1 f=f f 1=IA,例,求:f f-1 及f-1 f,解:,f,f-1,f-1 f,f f-1,=IA,=IB,例,定理 是一一,对应函数,则,(双射),定理,均为一一对应函数,则,(双射),定理,定理,分段函数的复合,4.4 基数的概念,自然数集合等势有(无)限集合基数,8.3 双射函数与集合的基数,定义 给定 A的后继集为,若 为,则,可写成如下形式,自然数集合,可简记为,若命名集合 为0,则,L,得到自然数集合,自然数集合,自然数集合,(n-1)+=0,1,2,.n-1=n,L,定义 给定两个集合A 与 B

16、,当且仅当存在着从 A 到 B 的双射函数,称集合A 与B 是等势的,记为A B.,等势,等势,等势,等势,证明:设集合族为S 对任意 A S,A A.若 A,B S,A B,则B A若 A,B,C S,A B,B C,则 A C,定理 在集合族上等势关系是一个等价关系.,(1)IA是从A到A的双射(2)若 f:AB是双射，则f 1:BA是从B到A的双射.(3)若 f:AB，g:BC是双射，则fg:AC是从A到C的双射,定义 若有一个从集合 0,1,n-1 到A 的双射函数,则称A 是有限(穷)的;若A 不是有限(穷)的,则它是无限的.,有(无)限集合,有(无)限集合,集合A 有限 A 某个自

17、然数,基数,定义(1)对于有限集合A,称与A等势的那个惟一的自然数为A的基数,记作cardA(也可以记作|A|)cardA=n A n,一个集合是有限的当且仅当它与某个自然数等势；,|有限集合|=元素个数|空集|=0,等势,等势,例1:试证集合 A=a,b,c,d 与 B=,等势,证明:设 f:A B,f(a)=,f(b)=,f(c)=,f(d)=,则 f 是 A B 的双射函数,所以A B,等势,等势,例2:试证自然数集合 N 与 集合 A=2n|n N 等势.,证明:设 f:N A,且 f(n)=2n,n=0,1,2,则 f 是 N A 的双射函数,所以 N A.,等势,等势,例3:设 A

18、=(0,1)=x|x R 0 x 1,证明 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,等势,因此 A R.,因为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,

19、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,.的形式.,可数集充要条件,一个集合是可数集当且仅当可以将它的所有元素逐个的排成一个序列,使得序列中每个元素都属于这个集合,并且这个集合中的每个元素都在序列中的某个位置出现且仅出现一次.对于任何的可

20、数集,它的元素都可以排列成一个有序图形.换句话说,都可以找到一个“数遍”集合中全体元素的顺序.,可数集充要条件,例,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,例:可数个两两不相交的可数集的并

21、是可数集.,可数集,可数集的性质：可数集的任何子集都是可数集.两个可数集的并是可数集.两个可数集的笛卡儿积是可数集.可数个可数集的笛卡儿积仍是可数集.,证明 是可数集,是可数的.,令,是双射的,故 是可数集.,例:Q是可数集.,定理:Q可数集,有关势的结果,等势结果N Z Q NN任何实数区间都与实数集合R等势,不等势的结果:定理(康托定理)(1)N R；(2)对任意集合A都有AP(A)证明思路：(1)只需证明任何函数 f:N0,1都不是满射的.任取函数 f:N0,1,列出 f 的所有函数值，然后构造一个0,1区间的小数b，使得b与所有的函数值都不相等.,证明,证(1)规定0,1中数的表示.对

22、任意的x0,1,令 x=0.x1 x2,0 xi 9规定在 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,并且满足bi ai(i),i=1,2,那么y0,1,且y与上面列出的任何函数值都不相等.这就推出yranf,即 f 不是满射的.,基数,定义(1)对于有限集合A,称与A等势的那个惟一的自然数为A的基数,记作cardA(也可以记作|A|)cardA=n A n(2)自然数集合N的基数记作0,即 cardN=

23、0(3)实数集R的基数记作,即 cardR=,一个集合是有限的当且仅当它与某个自然数等势；,定义,定义,定义(1)设A,B是集合,如果存在从A到B的单射函数,就称B优势于A,记作AB.如果B不是优势于A,则记作AB.(2)设A,B是集合,若AB 且 AB,则称 B 真优势于A,记作AB.如果 B 不是真优势于A,则记作AB.,定理 设 A,B,C是任意的集合,则(1)AA(2)若AB且BA,则AB(3)若AB且BC,则AC,定义,定义,定义 设A,B为集合,则(1)cardA=cardB AB(2)cardAcardB AB(3)cardAcardB cardAcardBcardAcardB,

24、例,1)0,1)(0,1)2)(0,1)R,例,f:(0,1)0,1),f(x)=x,g:0,1)(0,1),重要结论,定义,card Z=card Q=card NN=0 card P(N)=card 2N=card a,b=card(c,d)=card R=其中2N=0,1N,任一无限集必与其某个真子集等势.,连续统假设,连续统假设,不存在介于0和之间的基数,即 是大于0的最小基数.,基数排序0,1,2,n,0,其中:0,1,2,n,是全体自然数,是有穷基数.0,是无穷基数,0是最小的无穷基数.,定理,若A是有限集合,则card A0.若A是无限集合,则 0 card A.设 A 是一个集合,则 card A card P(A).,定理,第 二 篇,完,