3.1 函数的定义与性质
本章目录 · 1 节
本章导读
函数是一种满足唯一输出条件的二元关系。本节沿用前章的有序对、定义域和值域概念,并分别讨论函数是否存在、输出是否唯一、实际值域是否覆盖陪域;这三件事不能混成同一个条件。
定义3.1.1:二元关系 若对每个 都存在唯一的 使 ,称为函数,记 。同一输入不能同时对应两个不同输出;不同输入可以对应相同输出。空关系也满足唯一性条件,是定义域为空的函数。
【例3.1.1】,,判断是否为函数,其中列出的不同下标对象互异。
解: 是函数,虽然 输出相同,但每个输入都只有一个输出。 不是函数,因为 对应不同的 。
定义3.1.2:函数作为有序对集合相等,即 ,当且仅当定义域相同,且对定义域的每个 都有 。不能只在共同定义的部分化简出相同表达式便宣布相等。例如 的自然定义域排除 , 的自然定义域为全部实数,故这两个函数不同。
定义3.1.3:若 为函数, 且 ,称 为从 到 的函数,记 。 是定义域, 是指定的陪域, 是实际输出集合。对从 到 的函数,底集 中的每个元素都必须有输出。例如 与常函数 都是函数,前者不输出奇数,后者只输出2。
定义3.1.4:全部从 到 的函数组成函数集 。这一记号表示函数集合,不是把每个 当成普通数进行幂运算。
【例3.1.2】,求 。
解:用有序三元组 简记每个函数,依次有 、、、、、、、,共8个。每个三元组对应唯一的三对函数图,例如 。
有限非空集合满足 时,每个输入独立选择 个输出之一,故 。空集情形需单独理解: 时,唯一函数为空函数,所以 ,包括 也为空的情形; 时没有函数,所以 。在函数计数的语境中, 是与空函数一致的组合约定,并非所有分析学极限的约定。
定义3.1.5:对 ,像与原像分别为
函数值 是陪域中的一个元素;像 是陪域的子集。原像对任意函数和任意陪域子集都存在,不要求反函数存在。总有 ,等号未必成立。例如 ,则 。这表示先取像会遗失“同一输出来自哪一个输入”的信息。
【例3.1.3】,偶数 时 ,奇数 时 ,求 、。
解:,故像为 。输出2的偶数输入满足 ,得4;奇数输入满足 ,得1。因此原像为 ,两种分支都必须检查。
定义3.1.6:若 ,称满射;若 必有 ,称单射;既单射又满射,称双射或一一映射。满射针对指定陪域,单射针对输入能否由输出唯一恢复。验证单射不能只检验几个输入,验证满射应对任意 构造或证明存在原像。
【例3.1.4】判断以下五个函数的单射、满射、双射性质。
解:(1):既不单射也不满射,因为 ,且值域为 。(2):单射,因为严格递增;不满射,例如所有负数都没有原像。(3):满射,每个整数 的原像包含 ;不单射,因为同一 中的数都输出 。(4):双射,对任意 唯一解为 。(5):值域为 ,由 得到下界2;,所以不单射、不满射。不能仅凭“不是单调函数”就对任意函数断言不单射,本例的反例才直接证明了不单射。
【例3.1.5】对以下给定底集和对应规则,判断是否为从 到 的函数,并判断其性质、计算指定像或原像。
解:(1),:是函数;3和5输出相同,故不单射;7无原像,故不满射。(2)同样底集,:不是所要求的函数,输入1有两个不同输出,输入3缺失,且输出5不在陪域中;任意一项都已足以否定。(3):作为其实际定义域上的关系可为函数,但不是从给定 出发的函数,因为缺少输入5。
(4):双射,任意实数有唯一实立方根。(5):不单射, 和 输出相同;值域为 ,故不满射。(6):双射,输出 的唯一输入为 。若 ,则 。
(7):是函数,但不单射,因为不同对角输入都输出0;也不满射,因为平方模4只能为0或1,平方差绝对值不可能为2。,。
【例3.1.6】对四组集合构造双射。
解:(1)。把三个输出按1、2、3排成二进制三元组,将 依次记作 。按教材的对应, 依次映到 ;左右各8个且没有重复,故双射。这是任意选定的配对,不要把这一特定配对误认为后文逐元素定义的特征函数配对。
(2),取 ,严格递增且端点分别对应,逆为 。(3),取 (),()。非负整数依次映到偶数,负整数依次映到奇数,彼此不冲突,且覆盖全部自然数。(4),取 ;在该闭区间严格递减且连续,端点为1、,故双射。
【例3.1.7】,其中 ,求从 到 的满射函数数目。
解:全部函数有 个。令 表示没有输出 的函数集合;漏掉指定的 个输出时有 个函数。由容斥,满射数为
若 ,不可能用少于 个输入覆盖 个输出,结果为0;若 ,满射必为双射,结果为 。该公式这里明确要求正整数 ;不能未经空函数约定便向 的式子中直接代入。
定义3.1.7依次介绍五类常用函数。常函数 满足存在固定 ,使全部 ;恒等函数 ;偏序集间的单调递增函数保持 ,严格单调递增保持 ,递减则反转输出的顺序。一般偏序中的不可比元素没有因此被强制变成可比,不能把实数全序的全部直觉直接推广过去。
子集 的特征函数为 ,在 上取1,其余取0。不同子集对应不同特征函数,因此 与 存在自然双射。例如 , 的输出为 , 为 , 为 。
等价关系 决定自然映射 。它总为满射,因为商集的每个元素本来就是某个元素的类;它单射当且仅当 。例如 ,则 。
函数也用于刻画算法代价。顺序检索的最坏比较次数为 ;平均比较次数 还需要说明输入分布,不能在没有概率假设时给出唯一平均值。对最终非负的函数,以最终非负的 为比较对象, 表示存在 ,使全部 满足 ; 反向给出下界;同时满足两者记 。符号中的等号是常用的渐近记法,并非普通函数恒等。
二分检索必须先保证数组按可比较键有序。设下标从1到 ,初始 ;只要 ,取 ,若目标等于 返回 ;若目标小于它,置 ,否则置 ;循环结束返回0表示不存在。终止条件必须是 ,不可误写成不随右界缩小的 。每轮剩余区间大约减半,最坏复杂度为 (),并非无条件适用于无序数组;如果先排序,还要计算排序成本。
【例3.1.8】按教材顺序比较常见函数的增长阶,以下 均以2为底。
解:从高到低依次为
含 时可先沿 、整数 比较,以免非整数阶乘的定义含混。几个等阶或恒等关系有 ,,,,以及 ()。另有 。阶乘、指数、幂次及对数的不同增长速度,解释了同一问题中算法规模可行性为什么差别巨大。
