离散数学CH08函数.ppt

本章说明,本章的主要内容 函数的定义 函数的性质 函数的逆 函数的合成 本章与后续各章的关系 是代数系统的基础,8.1 函数的定义与性质 8.2 函数的复合与反函数 8.3 一个电话系统的描述实例 本章小结 习题 作业,本章内容,8.1 函数的定义与性质,定义8.1 设F为二元关系，若xdom F，都存在唯一的yran F 使xFy成立，则称F为函数(function)(或称作映射(mapping)。 对于函数F，如果有 xFy，则记作yF(x)，并称y为F在x的值。,举例 判断下列关系是否为函数 F1, F2,是函数 不是函数,说明,函数是特殊的二元关系。 函数的定义域为dom F，而不是它的真子集。 一个x只能对应唯一的y。,定义8.2 设 F,G 为函数，则 FG FGGF,由定义可知，两个函数F和G相等, 一定满足下面两个条件： （1）dom Fdom G （2）xdom Fdom G，都有 F(x)G(x),例如 函数F(x)(x21)/(x+1)，G(x)x1不相等, 因为 dom Fx|xRx -1 dom GR 显然， dom Fdom G，所以两个函数不相等。,函数相等,定义8.3 设A,B为集合，如果 f 为函数，dom fA，ran fB，则称 f 为从A到B的函数，记作 f：AB。 例如： f：NN，f(x)2x是从N到N的函数， g：NN，g(x)2也是从N到N的函数。,定义8.4 所有从A到B的函数的集合记作BA，读作“B上A”，符号化表示为 BAf |f：AB 。,从A到B的函数,例8.2 设A1,2,3，Ba,b，求BA。,解答 BA f0, f1, f2, f3, f4, f5, f6, f7 。其中,f 0, f 1, f 2, f 3,f 4, f 5, f 6, f 7,例8.2,说明,若|A|m，|B|n，且m,n0，则|BA|nm。 当A或B至少有一个集合是空集时： A且B，则BA。 A且B，则BAB。 A且B，则BAA。,定义8.5 设函数f：AB，A1A，B1B。 （1）令f(A1)f(x)|xA1，称 f(A1)为A1在f 下的像(image)。 特别地，当A1A时，称 f(A)为函数的像。 （2）令f 1(B1)x|xAf(x)B1，称f 1(B1)为B1在 f 下的完全原像(preimage) 。,说明,函数的像和完全原像,注意区别函数的值和像两个不同的概念。 函数值f(x)B，而函数的像f(A1)B。,讨论,设 B1B，显然B1在 f 下的原像 f-1(B1)是A的子集。 设 A1A，那么 f(A1)B。 f(A1)的完全原像就是 f-1(f(A1)。 一般来说， f-1(f(A1)A1，但是A1 f-1(f(A1)。 例如函数 f:1,2,30,1，满足 f(1)f(2)0，f(3)1 令A11，那么 f-1(f(A1) f-1(f(1) f-1(0)1,2 这时，A1是f-1(f(A1)的真子集。,例8.3 设f:NN，且 令A0,1，B2，求f(A)和 f1(B)。,解答 f(A)f(0, 1)f(0), f(1)0, 2 f 1(B) f 1(2)1, 4 (因为 f(1)2, f(4)2),例8.3,定义8.6 设f:AB， （1）若ran fB，则称f:AB是满射(surjection)的。 （2）若yran f 都存在唯一的xA使得f(x)y，则称 f:AB是单射(injection)的。 （3）若f 既是满射又是单射的，则称f:AB是双射(bijection)的(一一映像(one-to-one mapping) 。,说明,满射、入射、双射,如果f:AB是满射的，则对于任意的yB，都存在xA，使得f(x)y。 如果f:AB是单射的，则对于x1、x2A且x1x2，一定 有f(x1)f(x2)。 换句话说，如果对于x1、x2A有f(x1)f(x2)，则一定有x1x2。,不同类型的对应关系的示例,单射,不是函数,双射,函数,满射,例8.4 判断下面函数是否为单射、满射、双射的，为什么? (1) f：RR，f(x)= -x2+2x-1 (2) f：Z+R，f(x)=ln x，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.4,（1）f 在x=1取得极大值0。既不是单射也不是满射的。 （2）f 是单调上升的，是单射的，但不满射。ran f=ln1, ln2, 。 （3）f 是满射的， 但不是单射的，例如f(1.5)=f(1.2)=1。 （4）f 是满射、单射、双射的，因为它是单调函数并且ran f=R。 （5）f 有极小值f(1)=2。 该函数既不是单射的，也不是满射的。,分析,实数集合上函数性质的判断方法,例8.5,例8.5 对于以下各题给定的A,B和 f，判断是否构成函数f:AB。如果是，说明 f:AB是否为单射、满射和双射的，并根据要求进行计算。 (1)A1,2,3,4,5，B6,7,8,9,10， f, 能构成f:AB， f 不是满射的，因为7ran f。 f 不是单射的，因为f(3)f(5)9, (1)A1,2,3,4,5，B6,7,8,9,10， f, 不能构成f:AB，因为f 且f 。,例8.5,(3)A1,2,3,4,5，B6,7,8,9,10， f, 不能构成f:AB，因为dom f1,2,3,4A。 (4)ABR，f(x)x 能构成f:AB， 且 f 是双射的 。 (5)ABR+，f(x)x/(x2+1)（xR+ ） 能构成f:AB， 但 f 既不是单射的也不是满射的。 因为该函数在 x1 取得极大值 f(1)1/2，函数不是单调的，且ran f R+。,例8.5,(6)ABRR，f () 令L|x,yRyx+1，计算 f(L)。 能构成 f:AB，且 f 是双射的。 f(L)|xR |xRR-1 (7)ANN，BN，f()|x2-y2| 计算f(N0),f-1(0)。 能构成f:AB， 但 f 既不是单射也不是满射的。 因为f()f()0，且2ran f。 f(N0)n2-02|nNn2|nN f-1(0)|nN,例8.6,例8.6 对于给定的集合A和B构造双射函数 f:AB。 （1）AP(1,2,3), B0,11,2,3 （2）A0,1, B1/4,1/2 （3）AZ, BN （4）A/2,3/2, B1,1,例8.6的解答,（1）AP(1,2,3), B0,11,2,3 A,1,2,3,1,2,1,3,2,3,1,2,3。 Bf0,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,例8.6的解答,（2） A0,1, B1/4,1/2 令f: AB, f(x)(x+1)/4。 （3） AZ, BN 将Z中元素以下列顺序排列并与N中元素对应： Z：01 1 2233 N：0 12 3 4 5 6 则这种对应所表示的函数是：,（4） A=/2,3/2, B=1,1 令f: AB ，f(x)sin x。,常用函数常函数和恒等函数,设f：AB，如果存在cB，使得对所有的xA都有f(x)c，则称f：AB是常函数。 设f：AB，对所有的xA都有IA(x)x，称IA为A上的恒等函数。,常用函数单调递增函数,设， 为偏序集，f：AB，如果对任意的x1, x2A， x1x2，就有f(x1) f(x2)，则称f为单调递增的； 如果对任意的x1, x2A, x1x2, 就有f(x1) f(x2), 则称f为严格单调递增的。 类似的也可以定义单调递减和严格单调递减的函数。 举例：f: RR, f(x)x+1是严格单调递增的。 偏序集， R为包含关系，为一般的小于等于关系。 令f：P(a,b)0,1， f()f(a)f(b)0， f(a,b)=1， f是单调递增的, 但不是严格单调递增的。,常用函数特征函数,设A为集合，对于任意的AA，A的特征函数 A : A0,1定义为,举例: A的每一个子集A都对应于一个特征函数，不同的子集对应于不同的特征函数。 例如Aa,b,c, 则有 ,， a , a,b ,常用函数自然映射,设R是A上的等价关系， 令 g：AA/R g(a)=a，aA 称g是从A到商集A/R的自然映射。,给定集合A和A上的等价关系R，就可以确定一个自然映射g：AA/R。 例如A1,2,3，R,IA g(1)g(2)1,2, g(3)3 不同的等价关系确定不同的自然映射，其中恒等关系所确定的自然映射是双射， 而其他的自然映射一般来说只是满射。,定义在自然数集合上的计数函数,对于给定规模为n的输入，计算算法所做基本运算的次数，将这个次数表示为输入规模的函数。 排序和检索问题的基本运算是比较。 矩阵乘法的基本运算是元素的相乘。 估计算法在最坏情况下所做基本运算的次数记为W(n)。 估计算法在平均情况下所做基本运算的次数记为A(n)。 设f是定义在自然数集合上的函数，当n变得很大时，函数值f(n)的增长取决于函数的阶。阶越高的函数，算法的复杂度就越高，同时意味着算法的效率越低。 算法分析的主要工作就是估计复杂度函数的阶。阶可以是： n，n2，n3，nlog n，log n，2n ,定义在自然数集合上的计数函数,若存在正数c和n0，使得对一切nn0，有0f(n)cg(n)，记作 f(n)O(g(n)。 若存在正数c和n0，使得对一切nn0，有0cg(n)f(n)，记作 f(n)(g(n)。 若f(n)O(g(n)且 f(n)(g(n)，则f(n)(g(n)。 例如 f(n)1/2 n2-3n，则 f(n)(n2) g(n)6n3，则 g(n)(n3),8.2 函数的复合与反函数,函数的复合就是关系的右复合，一切和关系右复合有关的定理都适用于函数的复合。本节重点考虑在复合中特有的性质。,定理8.1(复合函数基本定理),定理8.1 设F, G是函数，则FG 也是函数，且满足 （1）dom (FG)x|xdom FF(x)dom G （2）xdom (FG)，有FG(x)G(F(x),证明： 先证明FG是函数。 因为F、G是关系，所以FG也是关系。 若对某个xdom (FG)，若有xFGy1和 xFGy2， 则 FG FG t1(FG)t2(FG) t1t2(t1t2GG) （F为函数） y1y2 （G为函数） 所以FG为函数。,定理8.1的证明,定理8.1的证明,任取x，(要证明dom (FG)x|xdom FF(x)dom G) xdom (FG) ty(F G) t(xdom F tF(x) tdom G) xx|xdom F F(x)dom G 所以（1）得证。 任取x， （要证明xdom (FG)，有FG(x)G(F(x)） xdom F F(x)dom G F G FG xdom(FG) FG(x)G(F(x) 所以（2）得证。,推论1 设F, G, H为函数，则(FG)H和F(GH)都是函数， 且(FG) H=F(GH) 证明：由定理8.1（复合函数基本定理）和定理7.2（关系合成具有结合性）得证。,定理8.1的推论1,推论2 设f：AB，g：BC，则fg：AC，且xA都有fg(x)=g(f(x)。 证明：由定理8.1（复合函数基本定理）可知fg是函数，且 dom (fg) x|xdom f f(x)dom g x|xA f(x)B A ran (fg) ran g C 因此 fg：AC，且xA有 fg(x)g(f(x)。,定理8.1的推论2,定理8.2 设 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也 是双射的。 分析,说明,函数的复合运算的性质,该定理说明函数的复合能够保持函数单射、满射、双射的性质。,定理8.2的证明,(1)如果f：AB，g：BC都是满射的，则fg：AC也 是满射的。 证明： 任取cC， 由g：BC的满射性，所以 bB使得g(b)=c。 对于这个b，由f：AB的满射性，所以aA使得f(a)=b。 由合成定理有 fg(a) g(f(a)g(b)c 所以，fg：AC是满射的。,定理8.2的证明,(2)如果f：AB，g：BC都是单射的，则fg：AC也是 单射的。 证明：假设存在x1, x2A使得 fg(x1)fg(x2)，由合成定理有 g(f(x1)=g(f(x2) 因为g：BC是单射的，故f(x1)f(x2)。 又由于f：AB也是单射的，所以x1x2。 所以，fog：AC是单射的。,(3)如果f：AB， g：BC都是双射的，则fg：AC也 是双射的。 证明：由（1）和（2）得证。,定理8.2之逆不为真,考虑集合Aa1,a2,a3， Bb1,b2,b3,b4，Cc1,c2,c3。 令 f , g, 则 fg=, 那么 f: AB和fg: AC都是单射的，但g: BC不是单射的。 考虑集合A=a1,a2,a3，B=b1,b2,b3，C=c1,c2。 令 f, g , 则 fg, 那么g: BC和fg: AC是满射的，但f : AB不是满射的。,定理8.3,定理8.3 设 f：AB，则 f f o IB IAof 证明：由定理8.1的推论2可知 f o IB ：AB 和 IAof ：AB 任取，,f f yB f IB f o IB 所以， f f o IB, f o IB t( f IB ) f t=y f 所以， f o IB f,所以， f f o IB 同理可证f IAof,什么样的函数 f：AB，它的逆f 1是从B到A的函数呢？ 任给函数F, 它的逆F 1不一定是函数, 只是一个二元关系。 F， F -1， 任给单射函数f：AB, 则f 1是函数, 且是从ran f到A的双射函数, 但不一定是从B到A的双射函数。 因为对于某些yBran f，f -1没有值与之对应。 任给满射函数f：AB，则f 1不一定是函数。 对于双射函数f：AB, f 1：BA是从B到A的双射函数。,反函数,定理8.4 设f：AB是双射的，则f 1：BA也是双射的。 证明： 先证明f- 1：BA是函数，且dom f 1B，ran f 1A。 因为 f 是函数，所以 f 1 是关系，且 dom f 1 ran f B , ran f 1dom f A， 对于任意的xB dom f 1， 假设有y1, y2A，使得f 1f 1成立， 则由逆的定义有，ff。 根据 f 的单射性，可得y1y2。 所以，f- 1是函数。,反函数存在的条件,再证明f- 1：BA的双射性质。 （证明单射）若存在x1, x2B，使得f 1 (x1)= f 1 (x2)=y， 从而有f 1f 1 ff x1x2 （因为 f 是函数） 所以， f- 1 是单射的。 （证明满射）对于任意的 yA ，因为f 是双射的， 所以必存在 xB ，使得f，所以f 1， 所以， f 1 是满射的。 综上所述， f 1 是双射函数。,说明,定理8.4的证明,对于双射函数f：AB，称f- 1：BA是它的反函数。,反函数的性质,定理8.5 设f：AB是双射的， 则f- 1f = IB， f f-1 = IA 证明：根据定理可知f- 1：BA也是双射的， 且 f- 1f：BB， f f- 1：AA。 任取, f 1f t( f 1 f ) t( f f ) x=y x, y B IB 所以， f- 1f IB, IB xy x, y B t( f f ) t( f 1 f ) f- 1f 所以，IB f- 1f,综上所述， f- 1f IB。同理可证 f f-1 IA,例8.8,例8.8 设 f：RR, g：RR 求fg，gf。如果 f 和 g 存在反函数，求出它们的反函数。 解答,g：RR是双射的，它的反函数是 g1：RR，g1(x)=x2,本章主要内容,函数的基本概念与性质（单射，满射，双射）。 函数的合成与反函数。,本章学习要求,掌握函数、A到B的函数、集合在函数下的像、集合在函数下的完全原像的概念及表示法；当A与B都是有穷集时，会求A到B的函数的个数。 掌握A到B的函数是单射、满射、和双射的定义及证明方法。 掌握常函数、恒等函数、单调函数、特征函数、自然映射等概念。 掌握合成函数的主要性质和求合成函数的方法。 掌握反函数的概念及主要性质。,对于任意的, RR, 有,证明： 任取RR，存在 RR，使得,因此f是满射的。,因此f是单射的。,例题,证明f 既是满射的，也是单射的。其中,例题,令Xx1,x2,xm，Y=y1,y2,yn，问 （1） 有多少不同的由X到Y的关系？ （2） 有多少不同的X到Y的映射？ （3） 有多少不同的由X到Y的单射、双射？,解：（1） 有2mn不同的由X到Y的关系。 （2） 有nm不同的X到Y的映射。 （3） X到Y的单射个数为：,若mn，有0个单射。 若m