《离散数学-5.1-2函数.ppt》由会员分享，可在线阅读，更多相关《离散数学-5.1-2函数.ppt（31页珍藏版）》请在三一办公上搜索。
1、1,第5章 函数,2,第5章 函数,5.1 函数定义及其性质5.2 函数的复合与反函数,3,5.1 函数定义及其性质,5.1.1 函数的定义函数定义从A到B的函数5.1.2 函数的像与完全原像5.1.3 函数的性质函数的单射、满射、双射性构造双射函数,4,函数定义,定义5.1 设 f 为二元关系,若 xdomf 都存在唯一的yranf 使 x f y 成立,则称 f为函数.对于函数f,如果有 x f y,则记作 y=f(x),并称 y 为 f 在 x 的值.例如 f1=,f2=,f1是函数,f2不是函数,5,函数相等,定义5.2 设f,g为函数,则 f=g fggf 如果两个函数 f 和 g
2、相等,一定满足下面两个条件：(1)domf=domg(2)xdomf=domg 都有 f(x)=g(x)实例 函数 f(x)=(x21)/(x+1),g(x)=x1不相等,因为 domfdomg.,6,从A到B的函数,定义5.3 设A,B为集合,如果(1)f 为函数(2)domf=A(3)ranf B,则称 f 为从A到B的函数,记作 f:AB.实例 f:NN,f(x)=2x 是从 N 到 N 的函数 g:NN,g(x)=2也是从 N 到 N 的函数,7,B上A,定义5.4 所有从A到B的函数的集合记作BA,读作“B上A”符号化表示为 BA=f|f:AB 计数：|A|=m,|B|=n,且m,n
3、0,|BA|=nm.A=,则 BA=B=.A且B=,则 BA=A=.,8,实例,解BA=f0,f1,f7,其中 f0=,f1=,f2=,f3=,f4=,f5=,f6=,f7=,例1 设A=1,2,3,B=a,b,求BA.,9,重要函数的定义,定义5.5(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,
4、就有 f(x1)f(x2),则称 f 为严格单调递增的.类似的也可以定义单调递减和严格单调递减的函数.,10,重要函数的定义(续),(4)设 A 为集合,对于任意的 A A,A 的特征函数 A:A0,1 定义为,实例：设A=a,b,c,A的每一个子集 A都对应于一个特征函数,不同的子集对应于不同的特征函数.如=,，a,b=,.,11,(5)设 R 是 A 上的等价关系,令g:AA/Rg(a)=a,aA称 g 是从 A 到商集 A/R 的自然映射.,重要函数的定义(续),12,实例,给定集合 A 和 A 上的等价关系 R,就可以确定一个自然映射 g:AA/R.不同的等价关系确定不同的自然映射,其
5、中恒等关系所确定的自然映射是双射,而其他的自然映射一般来说只是满射.例如：A=1,2,3,等价关系:R1=,IA自然映射：g1(1)=g1(2)=1,2,g1(3)=3等价关系：IA自然映射：g2(1)=1,g2(2)=2,g2(3)=3,13,重要函数的定义(续),W:Z+Z+作为算法的时间复杂度函数W(n)的含义：对于规模为 n 的输入，该算法在最坏情况下所执行的基本运算次数是W(n).复杂度函数 f(n)的阶的表示：f(n)=O(g(n)f(n)的阶不超过g(n)的阶 f(n)=(g(n)f(n)=O(g(n)且g(n)=O(f(n)例如:f(n)=n2+n=(n2),g(n)=nlog
6、n=O(n2)其中 logn 是 log2n 的简写算法：二分搜索 W(n)=O(logn)归并排序 W(n)=O(nlogn),14,函数的像与完全原像,定义5.6 设函数 f:AB,A1A,B1B,称 f(A1)=f(x)|xA1 为A1 在 f 下的像，f(A)称为函数的像.f1(B1)=x|xA f(x)B1 为B1 在 f 下的完全原像注意:函数的像与值的区别：函数值 f(x)B,像 f(A1)B.A1f1(f(A1)，f(f1(B1)B1.实例 11,2=f1(a)=f1(f(1)f(f1(b,c)=f(3)=bb,c,15,实例,1.设 f:NN,且令A=0,1,B=2,那么有
7、f(A)=f(0,1)=f(0),f(1)=0,2 f(B)=f(2)=1 2.A=1,2,3,B=a,b,c,f=,，则 f1(a,b)=1,2,3,f1(b,c)=3,16,函数的性质,定义5.7 设 f:AB,（1）若ranf=B,则称 f:AB是满射的.（2）若 yranf 都存在唯一的 xA使得 f(x)=y,则称 f:AB是单射的.（3）若 f:AB既是满射又是单射的,则称 f:AB是双射的f 满射意味着：y B,都存在 xA 使得 f(x)=y.f 单射意味着：f(x1)=f(x2)x1=x2,17,实例,例2 判断下面函数是否为单射,满射,双射的,为什么?（1）f:RR,f(x
8、)=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+为正实数集.,18,解(1)f:RR,f(x)=x2+2x1(2)f:Z+R,f(x)=lnx(3)f:RZ,f(x)=x(4)f:RR,f(x)=2x+1(5)f:R+R+,f(x)=(x2+1)/x,实例(续),在x=1取得极大值0.既不是单射也不是满射的.,单调上升,是单射的.但不满射,ranf=ln1,ln2,.,是满射的,但不是单射的,例如 f(1.5)=f(1.2)=1.,是满射、单射、双射的,因为它
9、是单调函数并且ranf=R.,有极小值f(1)=2.该函数既不是单射的也不是满射的.,19,构造从A到B的双射函数,有穷集之间的构造例3 A=P(1,2,3),B=0,11,2,3解 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,20,实数区间之间构造双射构造方法：直线方程例4 A=0,1 B=1/4,1/2构造双射 f:AB,构造从
10、A到B的双射函数(续),解 令 f:0,11/4,1/2 f(x)=(x+1)/4,21,A与自然数集合之间构造双射方法：将A中元素排成有序图形，然后从第一个元素开始 按照次序与自然数对应,构造从A到B的双射函数(续),例5 A=Z,B=N，构造双射 f:AB,将Z中元素以下列顺序排列并与N中元素对应：Z：011 2233 N：0 1 2 3 4 5 6 则这种对应所表示的函数是：,22,5.2 函数的复合与反函数,5.2.1 函数的复合函数复合的基本定理及其推论函数复合的性质5.2.2 反函数反函数存在的条件反函数的性质,23,函数复合的基本定理,定理5.1 设f,g是函数,则fg也是函数,
11、且满足(1)dom(fg)=x|xdomf f(x)domg(2)xdom(fg)有 fg(x)=g(f(x)证 先证明 fg 是函数.因为 f,g 是关系,所以 fg 也是关系.若对某个 xdom(fg)，xfgy1和 xfgy2,则 fg fg t1(f g)t2(f g)t1t2(t1=t2 g g)y1=y2 所以 fg 为函数.,24,证明,再证明结论(1)和(2).任取x,xdom(f g)t y(fg)t(xdomf t=f(x)tdomg)x x|xdomf f(x)domg 任取x,xdomf f(x)domg f g fg xdom(fg)fg(x)g(f(x)所以(1)和
12、(2)得证.,25,推论,推论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|xdomf f(x)domg=x|xA f(x)B=A ran(fg)rang C因此 fg:AC,且xA 有 fg(x)=g(f(x).,26,函数复合的性质,定理5.2 设 f:AB,g:BC.(1)如果 f:AB,g:BC都是满射的,则 fg:AC也是满射的.(2)如果 f:AB,g:BC都是单
13、射的,则 fg:AC也是单射的.(3)如果 f:AB,g:BC都是双射的,则 fg:AC也是双射的.,27,证明,(1)任取 cC,由g:BC的满射性,bB 使得 g(b)=c.对于这个b,由 f:AB 的满射性，aA 使得 f(a)=b.由定理5.1 有 fg(a)=g(f(a)=g(b)=c 从而证明了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是单射的.,28,函数复合的性质(续),定理5.3
14、设 f:AB，则 f=f IB=IAf 定理5.3 的证明可以采用集合相等的证明方法,29,反函数的存在条件及定义,定理5.4 设 f:AB是双射的,则f1:BA也是双射的.证 因为 f 是函数,所以 f 1是关系,且 dom f 1=ranf=B,ran f 1=domf=A,对于任意的 xB,假设有 y1,y2A 使得 f 1f 1 成立,则由逆的定义有 f f.根据 f 的单射性可得 y1=y2,从而证明了f 1是函数，且是满射的.若存在 x1,x2B使得 f 1(x1)=f 1(x2)=y,从而有f 1f 1 f f x1=x2 因为 f 是函数）从而证明了f 1的单射性.对于双射函数f:AB,称f 1:BA是它的反函数.,30,实例,例1 设 f:RR,g:RR,求 f g,gf.如果 f 和 g 存在反函数,求出它们的反函数.,解,f:RR不存在反函数；g:RR的反函数是g1:RR,g1(x)=x2,31,关于反函数的定理,定理5.5 设 f:AB是双射的,则f 1f=IB,ff 1=IA 证 根据定理5.4可知 f 1:BA也是双射的.由定理5.1 可知 f 1f:BB,ff 1:AA，且它们都是恒等函数.对于双射函数 f:AA,根据上述定理有 f 1f=ff 1=IA.,
