《离散数学屈婉玲第八章ppt课件.ppt》由会员分享，可在线阅读，更多相关《离散数学屈婉玲第八章ppt课件.ppt（50页珍藏版）》请在三一办公上搜索。
1、1,第八章 函数,主要内容函数的定义与性质函数定义函数性质函数运算函数的逆函数的合成双射函数与集合的基数,2,8.1 函数的定义与性质,主要内容函数定义与相关概念函数定义函数相等从A到B的函数f:ABBA函数的像与完全原像函数的性质单射、满射、双射函数的定义与实例构造双射函数某些重要的函数,3,函数定义,定义8.1 设 F 为二元关系,若xdomF 都存在唯一的yranF 使 xFy 成立,则称 F 为函数 对于函数F,如果有 xFy,则记作 y=F(x),并称 y 为F 在 x 的值.例 F1=,F2=,F1是函数,F2不是函数,定义8.2 设F,G 为函数,则 F=G FGGF 如果两个函
2、数F 和 G 相等,一定满足下面两个条件：(1)domF=domG(2)xdomF=domG 都有F(x)=G(x)函数F(x)=(x21)/(x+1),G(x)=x1不相等,因为 domFdomG.,4,从A到B的函数,定义8.3 设A,B为集合,如果 f 为函数,domf=A,ranfB,则称 f 为从A到B的函数,记作 f：AB.例 f：NN,f(x)=2x 是从N到N的函数,g：NN,g(x)=2 也是从N到N的函数.,定义8.4 所有从A到B的函数的集合记作BA,符号化表示为 BA=f|f：AB|A|=m,|B|=n,且m,n0,|BA|=nmA=,则BA=B=A且B=,则BA=A=
3、,5,实例,例1 设A=1,2,3,B=a,b,求BA.,解BA=f0,f1,f7,其中 f0=,f1=,f2=,f3=,f4=,f5=,f6=,f7=,6,函数的像和完全原像,定义8.5 设函数 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(0,1)=f(0),f(1)=0,2 f 1(B)=
4、f 1(2)=1,4,7,函数的性质,定义8.6 设 f：AB,(1)若 ranf=B,则称 f:AB是满射的(2)若 yranf 都存在唯一的 xA 使得 f(x)=y,则称 f:AB 是单射的(3)若 f:AB 既是满射又是单射的,则称 f:AB是双射的,例2 判断下面函数是否为单射,满射,双射的,为什么?(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+为正实数集.,8,例题解答,解(1)f:RR,f(x)=x2+2x1 在x=1取得
5、极大值0.既不是单射也不是满射的(2)f:Z+R,f(x)=lnx 是单调上升的,是单射的.但不满射,ranf=ln1,ln2,.(3)f:RZ,f(x)=x 是满射的,但不是单射的,例如f(1.5)=f(1.2)=1(4)f:RR,f(x)=2x+1 是满射、单射、双射的,因为它是单调函数并且ranf=R(5)f:R+R+,f(x)=(x2+1)/x 有极小值 f(1)=2.该函数既不是单射的也不是满射的,9,实例,例3 对于给定的集合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,10,
6、解答,(1)A=,1,2,3,1,2,1,3,2,3,1,2,3.B=f0,f1,f7,其中 f0=,f1=,f2=,f3=,f4=,f5=,f6=,f7=,.令 f:AB,f()=f0,f(1)=f1,f(2)=f2,f(3)=f3,f(1,2)=f4,f(1,3)=f5,f(2,3)=f6,f(1,2,3)=f7,11,(2)令 f:0,11/4,1/2,f(x)=(x+1)/4,(4)令 f:/2,3/21,1 f(x)=sinx,解答,(3)将Z中元素以下列顺序排列并与N中元素对应：Z：011 2 23 3 N：0 1 2 3 4 5 6 这种对应所表示的函数是：,12,某些重要函数,
7、定义8.7(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 为严 格单调递增的.类似的也可以定义单调递减和严格单调递 减的函数,13,(4)设A为集合,对于任意的AA,A的特征函数 A:A0,1定义为 A(a)=1,aA A(a)=0,aAA(5)设R是A上的等价关系,令 g:AA
8、/R g(a)=a,aA称 g 是从 A 到商集 A/R 的自然映射,某些重要函数,14,实例,例4(1)偏序集,R为包含关系,为一般的小于等于关系,令 f:P(a,b)0,1,f()=f(a)=f(b)=0,f(a,b)=1,f 是单调递增的,但不是严格单调递增的,(3)不同的等价关系确定不同的自然映射,恒等关系确定的自然映射是双射,其他自然映射一般来说只是满射.例如 A=1,2,3,R=,IA g:AA/R,g(1)=g(2)=1,2,g(3)=3,(2)A的每一个子集 A都对应于一个特征函数,不同的子集对 应于不同的特征函数.例如A=a,b,c,则有=,，a,b=,15,8.2 函数的复
9、合与反函数,主要内容复合函数基本定理函数的复合运算与函数性质反函数的存在条件反函数的性质,16,复合函数基本定理,定理8.1 设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,则 FGFG t1(FG)t2(FG)t1t2(t1=t2GG（F为函数）y1=y2（G为函数）所以 FG 为函数,17,证明,任取x,xdom(FG)t y(FG)t(xdomFt=F(x)tdomG)x x|xdomF
10、F(x)domG 任取x,xdomFF(x)domG FG FG xdom(FG)FG(x)G(F(x)所以(1)和(2)得证,18,推论,推论1 设F,G,H为函数,则(FG)H和F(GH)都是函数,且(FG)H=F(GH)证 由上述定理和运算满足结合律得证.,推论2 设 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),19,函数复合与函数性质,定理8.2 设f:AB,g:BC(1)如
11、果 f:AB,g:BC是满射的,则 fg:AC也是满射的(2)如果 f:AB,g:BC是单射的,则 fg:AC也是单射的(3)如果 f:AB,g:BC是双射的,则 fg:AC也是双射的,A=a1,a2,B=b1,b2,b3，C=c1,c2.f=,g=,f g=,f:AB 和 f g:AC是单射的,但g:BC不是单射的.A=a1,a2,a3,B=b1,b2,b3,C=c1,c2.f=,g=,f g=,g:BC 和 f g:AC是满射的,但 f:AB不是满射的.,20,反函数,反函数存在的条件(1)任给函数F,它的逆F 1不一定是函数,只是一个二元关系.(2)任给单射函数 f:AB,则f 1是函数
12、,且是从ranf 到A的双 射函数,但不一定是从B到A的双射函数(3)对于双射函数 f:AB,f 1:BA是从B到A的双射函数.,定理8.4 设 f:AB是双射的,则f 1:BA也是双射的.证明思路：先证明 f 1:BA，即f 1是函数，且domf 1=B,ranf 1=A.再证明f 1:BA的双射性质.,21,证明,证 因为 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
13、,x2B使得f 1(x1)=f 1(x2)=y,从而有 f 1f 1 ff x1=x2 对于双射函数f:AB,称 f 1:BA是它的反函数.,22,反函数的性质,定理8.5(1)设 f:AB是双射的,则 f 1f=IB,f f 1=IA(2)对于双射函数 f:AA,有 f 1 f=f f 1=IA 证明思路：根据定理可知 f 1:BA也是双射的,由合成基本定理可知 f 1f:BB,f f 1:AA，且它们都是恒等函数.,例5 设 求 f g,g f.如果f 和 g 存在反函数,求出它们的反函数.,23,解,f:RR不是双射的,不存在反函数.g:RR是双射的,它的反函数是g1:RR,g1(x)=
14、x2,求解,24,8.3 双射函数与集合的基数,主要内容集合的等势及其性质重要的等势或不等势的结果集合的优势及其性质集合的基数可数集,25,则 f 是Z到N的双射函数.从而证明了ZN.,集合的等势,集合等势的实例例6(1)ZN.,定义8.8 设A,B是集合,如果存在着从A到B的双射函数,就称A和B是等势的,记作AB.如果A不与B 等势,则记作AB.,26,集合等势的实例:NNN,NNN.NN中所有的元素排成有序图形,27,-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,
15、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,NQ.双射函数 f:NQ,其中f(n)是n下方的有理数.,集合等势的实例:NQ,28,对任何a,bR,ab,0,1a,b，双射函数 f:0,1a,b,f(x)=(ba)x+a类似地可以证明,对任何a,bR,ab,有(0,1)(a,b).,(4)(0,1)R.其中实数区间(0,1)=x|xR0 x1.令,(5)0,1(0,1).其中(0,1)和0,1分别为实数开区间和闭区间.令 f:0,1(0,1),实数集合的等势,29
16、,等势的性质及结果,定理8.6 设A,B,C是任意集合，(1)AA(2)若AB，则BA(3)若AB，BC，则AC.,不等势的结果:定理8.7(康托定理)(1)N R；(2)对任意集合A都有AP(A),等势结果N Z Q NN任何实数区间都与实数集合R等势,30,集合的优势,定义8.9(1)设A,B是集合,如果存在从A到B的单射函数,就称B优势于A,记作AB.如果B不是优势于A,则记作AB.(2)设A,B是集合,若AB 且 AB,则称 B 真优势于A,记作 AB.如果 B 不是真优势于A,则记作AB.实例 NN,NR,AP(A),RN NR,AP(A),但NN,定理8.8 设 A,B,C是任意的
17、集合,则(1)AA(2)若AB且BA,则AB(3)若AB且BC,则AC,31,集合基数的定义,定义8.10(1)对于有穷集合A,称A的元素个数为A的基数,记作cardA(也可以记作|A|)cardA=n A n(2)自然数集合N的基数记作0,即 cardN=0(3)实数集R的基数记作,即 cardR=,32,基数的相等和大小,定义8.11 设A,B为集合,则(1)cardA=cardB AB(2)cardAcardB AB(3)cardAcardB cardAcardBcardAcardB,根据上一节关于势的讨论不难得到：card Z=card Q=card NN=0 card P(N)=ca
18、rd 2N=card a,b=card(c,d)=0 card Acard P(A)其中2N=0,1N,33,基数的大小,不存在最大的基数.将已知的基数按从小到大的顺序排列就得到：0,1,2,n,0,其中：0,1,2,n,是全体自然数,是有穷基数.0,是无穷基数,0是最小的无穷基数,后面还有更大的基数,如cardP(R)等.,34,可数集,定义8.12 设A为集合,若cardA0,则称A为可数集或可列集.实例：a,b,c,5,整数集Z,有理数集Q,NN等都是可数集,实数集 R不是可数集,与R等势的集合也不是可数集.对于任何的可数集,它的元素都可以排列成一个有序图形.换句话说,都可以找到一个“数
19、遍”集合中全体元素的顺序.,可数集的性质：可数集的任何子集都是可数集.两个可数集的并是可数集.两个可数集的笛卡儿积是可数集.可数个可数集的笛卡儿积仍是可数集.无穷集A的幂集P(A)不是可数集,35,实例,解(1)由T=B,A,S,E,L知 cardT=5(2)由B=,可知 cardB=0.(3)由|A|=4 可知 cardC=cardP(A)=|P(A)|=24=16.,例7 求下列集合的基数(1)T=x|x是单词“BASEBALL”中的字母(2)B=x|xRx2=92x=8(3)C=P(A),A=1,3,7,11,36,例8 设A,B为集合,且 cardA=0,cardB=n,n是自然数,n
20、0.求card AB.,实例,解 方法一 构造双射函数由cardA=0,cardB=n,可知 A,B都是可数集.令 A=a0,a1,a2,B=b0,b1,b2,bn1 对任意的,AB有=i=kj=l 定义函数 f:ABN f()=in+j,i=0,1,j=0,1,n1易见f是AB到N的双射函数,所以 card AB=card N=0,37,方法二 直接使用可数集的性质求解.因为 card A=0,card B=n,所以A,B都是可数集.根据性质(3)可知 AB也是可数集,所以 card AB0 显然当 B时,card A card AB,这就推出 0 card AB综合上述得到 card AB
21、=0.,实例,38,第八章 习题课,主要内容函数，从A到B的函数 f:AB，BA，函数的像与完全原像函数的性质：单射、满射、双射函数重要函数：恒等函数、常函数、单调函数、集合的特征函 数、自然映射集合等势的定义与性质集合优势的定义与性质重要的集合等势以及优势的结果集合基数的定义,39,基本要求,给定 f,A,B,判别 f 是否为从A到B的函数判别函数 f:AB的性质（单射、满射、双射）熟练计算函数的值、像、复合以及反函数证明函数 f:AB的性质（单射、满射、双射）给定集合A,B，构造双射函数 f:AB 能够证明两个集合等势能够证明一个集合优势于另一个集合知道什么是可数集与不可数集会求一个简单集
22、合的基数,40,练习1,1给定A,B 和 f,判断是否构成函数 f:AB.如果是,说明该 函数是否为单射、满射、双射的.并根据要求进行计算.(1)A=1,2,3,4,5,B=6,7,8,9,10,f=,.(2)A,B同(1),f=,.(3)A,B同(1),f=,.(4)A=B=R,f(x)=x3(5)A=B=R+,f(x)=x/(x2+1).(6)A=B=RR,f()=,令 L=|x,yRy=x+1,计算 f(L).(7)A=NN,B=N,f()=|x2y2|.计算f(N0),f 1(0),41,解,解答,(1)能构成 f:AB,f:AB既不是单射也不是满射,因为 f(3)=f(5)=9,且7
23、ranf.(2)不构成 f:AB,因为 f 不是函数.f 且f,与函 数定义矛盾(3)不构成 f:AB,因为dom f=1,2,3,4 A(4)能构成 f:AB,且 f:AB是双射的(5)能构成 f:AB,f:AB既不是单射的也不是满射的.因为该 函数在 x=1取极大值 f(1)=1/2.函数不是单调的,且ranfR+.(6)能构成 f:AB,且 f:AB是双射的.f(L)=|xR=R1(7)能构成 f:AB,f:AB既不是单射的也不是满射的.因为 f()=f()=0,2ranf.f(N0)=n202|nN=n2|nN f1(0)=|nN,42,练习2,2.设 f1,f2,f3,f4RR，且,
24、令Ei 是由 fi 导出的等价关系，i=1,2,3,4，即 xEiy fi(x)=fi(y)(1)画出偏序集的哈斯图，其中T 是加细关系：T x(xR/Eiy(yR/Ej xy)(2)gi:RR/Ei 是自然映射，求gi(0),i=1,2,3,4.(3)对每个i,说明 gi 的性质（单射、满射、双射）.,43,(1)哈斯图如下(2)g1(0)=x|xRx0,g2(0)=0,g3(0)=Z,g4(0)=R(3)g1,g3,g4是满射的；g2是双射的.,解,图1,解答,44,练习3,3对于以下集合A和B，构造从A到B的双射函数 f:AB(1)A=1,2,3，B=a,b,c(2)A=(0,1)，B=
25、(0,2)(3)A=x|xZx0，B=N(4)A=R，B=R+,解(1)f=,(2)f:AB,f(x)=2x(3)f:AB,f(x)=x1(4)f:AB,f(x)=ex,45,4.设 证明 f 既是满射的，也是单射的.,证 任取RR，存在,使得,练习4,因此 f 是满射的对于任意的,RR,有,因此 f 是单射的.,46,证明方法,1.证明 f:AB是满射的方法:任取 yB,找到 x(即给出x的表示)或者证明存在xA，使得f(x)=y.2.证明 f:AB是单射的方法 方法一 x1,x2A,f(x1)=f(x2)x1=x2 推理前提 推理过程 推理结论 方法二 x1,x2A,x1x2 f(x1)f
26、(x2)推理前提 推理过程 推理结论 3.证明 f:AB不是满射的方法：找到 yB,yranf 4.证明 f:AB不是单射的方法：找到 x1,x2A,x1x2,且 f(x1)=f(x2),47,5.设A,B为二集合,证明：如果AB,则P(A)P(B),练习5,证 因为AB，存在双射函数 f:AB，反函数 f 1:BA构造函数 g:P(A)P(B),g(T)=f(T)，TA（f(T)是T在函数 f 的像）证明 g 的满射性.对于任何S B,存在 f 1(S)A,且 g(f 1(S)=f f 1(S)=S 证明g的单射性.g(T1)=g(T2)f(T1)=f(T2)f 1(f(T1)=f 1(f(
27、T2)IA(T1)=IA(T2)T1=T2综合上述得到P(A)P(B).,48,证明集合A与B等势的方法,方法一：直接构造从A到B的双射,即定义一个从A到B的函数 f:AB，证明 f 的满射性，证明 f 的单射性方法二：利用定理8.8，构造两个单射 f:AB 和 g:BA.即 定义函数 f 和 g，证明 f 和 g 的单射性方法三：利用等势的传递性方法四：直接计算A与B的基数，得到card A=card B.注意：以上方法中最重要的是方法一.证明集合A与自然数集合N等势的通常方法是：找到一个“数遍”A中元素的顺序.,49,练习6,6已知A=n7|nN,B=n109|nN,求下列各题：(1)Ca
28、rd A(2)Card B(3)card(AB)(4)card(AB),解(1)构造双射函数 f:NA,f(n)=n7,因此 card A=0(2)构造双射函数 g:NA,g(n)=n109,因此card B=0(3)可数集的并仍旧是可数集，因此card(AB)0,但是 card(AB)card A=0,从而得到 card(AB)=0.(4)因为7与109互素，card(AB)=n7109|nN，与(1)类似得到 card(AB)=0,50,7.已知cardA=0,且cardBcardA,求card(AB),练习7,解 由ABA 得到 card(AB)cardA,即 card(AB)0 由 cardBcardA 可知 B 为有穷集，即存在自然数n使得 cardB=n.假设card(AB)0，那么存在自然数m，使得 card(AB)=m 从而得到 cardA=card(AB)B)n+m，与cardA=0矛盾.因此，card(AB)=0.,
