离散数学第5章课件.pptVIP

第五章 映射与无限集 映射(函数) 计算机科学通过研究映射的性质获取描述处理对象的技术. 所谓映射, 其实是一个集合到另一个集合元素之间所对应关系的一种指定规则. 映射也称为函数。 由于映射有很多情形,概括的说有四类： ①多对一; ②一对一; ③多对多; ④一对多 映射定义 一个映射函数f:X→Y是一个满足下列两个条件的关系： 1.对每个x∈X，必存在y∈Y，使得(x,y)∈f 2.对每个x∈X，仅存在一个y，使(x,y)∈f 我们把y称为x在映射f下的象 把x称为y的原象 映射表示方法 表示映射的方法： 1. f: X→Y 2.X → Y 3.Y=f(x)={f(x)|x∈X} 实例 f：N→N, f(x)=2x 是从 N 到 N 的函数 g：N→N, g(x)=2也是从 N 到 N 的函数 例1 X={x1,x2,x3} Y={y1,y2} F1={x1,y1,x2,y2,x3,y2} F2={x1,y1,x1,y2} F3={x1,y2,x3,y2} F1是函数, F2不是函数, F3不是函数 例2 R为实数的集合，X=Y=R，并设 f={(x,y)|x,y∈R,y=x2} g={(x,y)|x,y∈R,y2=x} f是X到Y的映射 g不是映射，违反唯一性 函数相等 定义 设F, G为函数, 则  F = G ? F(x)=G(x) 如果两个函数 F 和 G 相等, 一定满足下面两个条件： (1) D(F) = D(G)  (2) ?x [x∈D(F)∧x∈D(G )]都有 F(x) = G(x)  实例 函数 F(x)=(x2?1)/(x+1), G(x)=x?1 不相等, 因为x=-1，F(-1)=0, G(-1)=-2. 函数的性质 练习： 练习（续） 一一对应 定义：集合X和Y间，存在从X到Y上的双射，则称集合X和Y一一对应。 集合X和Y一一对应，则： 1.X中每个元素在Y中有唯一的象。 2.X中不同元素的象各不相同。 3.Y中每个元素在X上都有原象。 实例 判断从{a,b,c,d}到{1,2,3,4,5}是否一一对应。 f为：f(a)=4, f(b)=5,f(c)=1,f(d)=3 不是一一对应的关系。虽然是单射，但不是满射。所以不是双射。所以不是一一对应的关系。 映射(函数)的复合 对关系而言，有关系的复合；函数是关系，所以函数也是可复合的。 已知映射：f:X→Y，和g:Y→Z， 由这两个映射可构成新映射：h，记为g?f, 称为f和g的复合映射。 h= g?f=g(f(x)) {(x,z)|?x∈X,?z∈Z, ?y∈Y, y=f(x),z=g(y)} 映射(函数)的复合 例：X={x1,x2,x3}, Y={y1,y2}, Z={z1,z2} f:X→Y，g:Y→Z，h= g?f 函数复合运算的性质 练习： 1.下列哪些关系可以构成函数？ a. f={(x,y)|x,y∈N, x+y10} b. f={(x,y)|x,y∈R, x2=y} 2.判断下列函数是单射、满射或双射？ a. f:N→N, f(x)=x+2; b. f:N→N, f(x)=x (mod 2); c. f:N→ρ(N), f(x)={x}; 练习： 3.已知：f:X→Y, g:Y→Z, h= g°f , f是满射，h是单射，求证g是单射。 证明3：已知：f:X→Y, g:Y→Z, h= g°f , f是满射，h是单射. 求证g是单射。 证：假设g不是单射， 1.则存在y1≠y2,而 g(y1)=g(y2)； 2.而f是满射，每个y都一定有对应的x，所以对于y1和y2，必存在y1=f(x1), y2=f(x2) 3.y1≠y2 所以f(x1)≠f(x2)，所以x1≠x2 ; 4.h(x1)=g(f(x1))=g(y1) h(x2)=g(f(x2))=g(y2) 所以h(x1)=h(x2) 对于不同的x，h函数具有相同值，显然就不是单射了，与已知条件矛盾！ 所以原假设不成立！ 逆函数(反函数) 对关系R来说，都存在逆关系； 但是对映射(函数)来说，不一定存在逆函数！ 需要依据一定的条件来判断！ 反函数存在的条件 反函数的性质 反函数的性质 定理 设 f：A→B是双射的, 则f ?1°f = IA , f°f ?1 = IB  对于双射函数 f：A→A, 有f ?1°f = f°f ?1 = IA 例题： 构造下列函数的反函数： 1.f(x)=sinx 2.f(x)=x2 , x∈(-∞，0) 3.A={1,2,3},B