离散数学函数.ppt

第一页，共十五页，2022年，8月28日 §5.1 函数的定义和性质 高等数学课程中详细研究了函数的概念和性质，但这些函数概念一般不好直接应用地计算机科学。如数据结构，开关理论，自动机等。计算机科学要求推广以往的函数概念。 第二页，共十五页，2022年，8月28日 函数：设F为二元关系， 如 F1 = {x1,y1, x2,y1, x3,y2}是函数 F2 = {x1,y1, x1,y2, x2,y1, x3,y2}不是函数 若对任意的x?domF都存在唯一的y?ranF，使得xFy成立，则F为函数，y是F在x的函数值。 第三页，共十五页，2022年，8月28日 从A到B的函数：设A、B是集合， 如果函数f 满足以下条件 (1) domf = A (2) ranf ? B 则称 f 是从A到B的函数，记作：f：A?B 集A 在 f 下的象：设 f ：A?B，A?A， 则f [A]是A在f 下的象。 则 f (A) = {f (x) | x?A}= f [A]， ? 第四页，共十五页，2022年，8月28日 设函数 f：A?B (1) 若ranf = B，则说f 具有满射性； (2) 若对于任何x1, x2?A，x1?x2都有 f (x1)?f (x2)，则说f具有单射性； (3) 若f 既具有满射性，又具有单射性，则说f 具有双射性。 函数的性质 第五页，共十五页，2022年，8月28日 例5.1 判断以下函数的单射、满射和双射性。 (1) f：R?R? R?R，R为实数集 f (x,y) = x+y, x?y? 解： (1) 先说f 是单射的。 这要证明对任取x,y，u,v?R?R。 反证，如果x+y, x?y = u+v,u?v，则， x+y = u+v 且x?y = u?v。 x,y ? u,v时, x+y, x?y ? u+v,u?v； 第六页，共十五页，2022年，8月28日 解关于x, y的方程组知：x = u 且 y = v， 故x,y = u, v 与已知矛盾。 再说f是满射的。这只要让对任意的(u,v)?R?R，可以找到x,y?R?R, 使得f (x,y) = u,v就可以了。 由f 的定义有 x+y = u 和 x?y = v 综上所述，f 是双射的。 第七页，共十五页，2022年，8月28日 (2) f：N?N?N，N为自然数集(0?N) f (x,y) = | x2 ? y2 | 解： f 不是单射，因为f (2,2)= f (1,1) = 0； f 不是满射，因为找不到自然数x和y满足 | x2?y2 | = 2，所以2?ranf 第八页，共十五页，2022年，8月28日 特征函数：设A为集合， XA (a) = 1 a?A 0 a?A?A 如A = {a,b,c}，A = {a}，则 XA(a) = 1，XA(b) = XA(c) = 0 对于任意的A?A，A的特征函数XA：A?{0，1} 定义为： 第九页，共十五页，2022年，8月28日 自然映射：设R是A上的等价关系， 如：A = {1,2,3}，R = {1,2,2,1}∪IA 则有 g(1) = g(2) = {1,2}，g(3) = {3} 称g为从A到A/R的自然映射。 定义一个从A到A/R的函数g：A?A/R 且 g(a) = [a]，它把A中的元素a映到a的等价类[a]。 第十页，共十五页，2022年，8月28日 §5.2 函数的运算 由定义可知：只有当 f ：A?B是双射函数时，它才有逆函数. 函数的逆：关系 f 是从A到B的一个函数，如果 f 的逆关系f ?1也是一个函数(B到A的)，这个函数称之为f 的逆函数，记作f ?1 ：B ? A。 第十一页，共十五页，2022年，8月28日