《离散数学(函数)课件.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),函
2、数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 ； A B 的子集并不都能成为 A 到 B 的函数。,例,A=a,b,c, B=0,1 AB=, |P(AB)|=26, 但
3、只有 23 个子集定义为 X 到 Y 的函数.,f0 = ,f1 = ,f2 = ,f7 = ,函数的定义,所有从A到B的函数的集合记作BA, 表示为 BA = f | f：AB |A|=m, |B|=n, 且m, n0, |BA|=nm A=, 则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
4、)A1, 但是A1f 1(f(A1),例,例 设 f：NN, 且 令A=0,1, B=2, 那么有 f(A) = f 1(B) =, f( 0,1) = f(0), f(1)=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:
5、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: 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
6、=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构造双射函数 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
7、上的恒等关系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, aA A(a)=0, aAA (5) 设R是A上的等价关系, 令 g:AA/R g(a)=a, aA 称 g 是从 A 到商集 A/R 的自然
8、映射,例,(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=,IA g: AA/R,g(1)=g(2)=1,2, g(3)=3,课堂练习,证明 f(AB) f(A) f(B),保序性：,A B f(A)
9、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上的函数 f(n)=O(g(n). 若存在正数c和n0使得对一切nn0 有 0 f(n)cg(n) f(n) =(g(n). 若存在正数c
10、和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),综上 1+2+ n = ?,函数的定义,1+2+n,=(n2),4.
11、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, 则 FGFG t1(FG)t2(FG) t1t2(t1=t2GG) （F为函数） y1=y2 （G为函数） 所以 FG 为函数
12、,函数的复合,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(
13、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 = 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,
14、 g:BC单射, 则 fg:AC也单射,证 (2) 假设存在x1, x2A使得 f g(x1)=f g(x2) 由合成定理有 g(f(x1)=g(f(x2) 因为g:BC是单射的, 故 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 = , , ,逆关系,
15、已知：集合 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也是双射的.,证明思路： 先证明 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是双射的, 则 f 1f = IB, f f 1 = IA (2) 对于双射函数 f:AA, 有 f 1 f = f f 1 = IA,例,求: f f -1 及f -1
