离散数学（五）—

离散数学（五）——函数

在关系的基础上，定义一类特殊的关系，称为函数，也称为映射。

一、函数的定义

定义 1.（函数）

$𝑓 : 𝐴 \to 𝐵$ 表示函数 $𝑓$ 是集合 $𝐴$ 到集合 $𝐵$ 的一种关系，是笛卡尔积 $𝐴 \times 𝐵$ 的子集。称 $𝐴$ 为函数的定义域，称 $𝐵$ 为函数的陪域。对于定义域中的任一元素 $𝑎 \in 𝐴$ ，都必须存在唯一的 $𝑏 \in 𝐵$ 与之对应，即 $⟨ 𝑎, 𝑏 ⟩ \in 𝑓$ 。

既然 $𝑏$ 存在且唯一，那么总能记 $𝑏 = 𝑓 (𝑎)$ ，称 $𝑏$ 是 $𝑎$ 的像或函数值，而 $𝑎$ 是 $𝑏$ 的原像。

在离散数学中，函数运算记号 $𝑓 (?)$ 的括号中不仅能填入定义域中的一个元素，也能填入定义域的一个子集。即若 $𝑆 \subseteq 𝐴$ ，那么称 $𝑓 (𝑆)$ 为 $𝑆$ 在 $𝑓$ 下的像集，它运算得到一个集合，集合中的元素是 $𝑆$ 中的元素的函数值，因此这个集合也必是陪域 $𝐵$ 的子集：

𝑓 (𝑆) = {𝑓 (𝑥) \in 𝐵 | 𝑥 \in 𝑆} \subseteq 𝐵

当 $𝑆 = 𝐴$ 时，称 $𝑓 (𝐴)$ 为函数的值域，记为 $ran (𝑓)$ 。

同样地，取函数的逆关系 $𝑓^{- 1}$ ，若 $𝑇 \subseteq 𝐵$ ，那么称 $𝑓^{- 1} (𝑇)$ 为 $𝑇$ 在 $𝑓$ 下的逆像集，它也必是定义域 $𝐴$ 的子集：

𝑓^{- 1} (𝑇) = {𝑥 \in 𝐴 | 𝑓 (𝑥) \in 𝑇} \subseteq 𝐴

既然函数是特殊的关系，那么一些特殊关系也能产生特殊函数。例如，以空集为定义域的函数称为空函数；由恒等关系 $Δ_{𝐴}$ 产生的函数称为 $𝐴$ 的恒等函数，记为 ${id}_{𝐴}$ 。

二、函数的运算

基于关系的运算我们得到函数的运算。

1.子集与函数

命题 1.（函数保持子集关系）

假如有函数

𝑓 : 𝐴 \to 𝐵

，并且

𝑆 \subseteq 𝑇 \subseteq 𝐴

，那么亦有

𝑓 (𝑆) \subseteq 𝑓 (𝑇)

。

现在假设函数 $𝑓 : 𝐴 \to 𝐵$ ，并且 $𝑆, 𝑇 \subseteq 𝐴$ ，还存在：

𝑓 (𝑆 \cap 𝑇) \subseteq 𝑓 (𝑆) \cap 𝑓 (𝑇)

2.函数的复合

假设两个函数 $𝑓 : 𝐴 \to 𝐵, 𝑔 : 𝐵 \to 𝐶$ ，那么两个函数的复合产生的新函数是 $𝐴 \times 𝐶$ 上的关系，记为 $𝑔 ⚬ 𝑓$ 。由于 $𝑓$ 的陪域就是 $𝑔$ 的定义域，因此：

\forall 𝑥 \in 𝐴, (𝑔 ⚬ 𝑓) (𝑥) = 𝑔 (𝑓 (𝑥))

既然函数的复合就是关系的复合，那么关系复合的一些性质是可以完全挪用的。例如，函数复合有结合律：

ℎ ⚬ (𝑔 ⚬ 𝑓) = (ℎ ⚬ 𝑔) ⚬ 𝑓

函数与恒等函数的复合还是函数自身。假如 $𝑓 : 𝐴 \to 𝐵$ ，那么 ${id}_{𝐵} ⚬ 𝑓 = 𝑓 = 𝑓 ⚬ {id}_{𝐴}$ 。

3.函数的反函数

现在假设函数 $𝑓 : 𝐴 \to 𝐵$ 以及 $𝑔 : 𝐵 \to 𝐴$ 。假如 $𝑔 ⚬ 𝑓 = {id}_{𝐴}$ ，那么称 $𝑔$ 是函数 $𝑓$ 的左逆；假如 $𝑓 ⚬ 𝑔 = {id}_{𝐵}$ ，那么称 $𝑔$ 是函数 $𝑓$ 的右逆。

函数作为关系自然具有逆关系，由逆关系定义的函数称为逆函数、或称反函数，记为 $𝑓^{- 1}$ ，定义为：

𝑓^{- 1} = {⟨ 𝑦, 𝑥 ⟩ \in 𝐵 \times 𝐴 | ⟨ 𝑥, 𝑦 ⟩ \in 𝑓} = {⟨ 𝑦, 𝑥 ⟩ | 𝑓 (𝑥) = 𝑦}

然而由于函数作为关系的特殊性，一个函数要具有反函数，就不能存在定义域上的元素对应多个陪域中的元素。也就是，函数必须是双函数。这就涉及到函数性质的讨论，也就是接下来的内容。

三、函数的性质

接下来假定函数 $𝑓 : 𝐴 \to 𝐵$ 。必要时引入函数 $𝑔 : 𝐵 \to 𝐶$ 。

1.单函数

定义 2.（单函数）

对函数

𝑓

，如果任意

𝑥, 𝑦 \in 𝐴

都有

𝑓 (𝑥) = 𝑓 (𝑦) \to 𝑥 = 𝑦

，也就是任意定义域上不同的元素必有不同的函数值，那么就称函数

𝑓

为单函数。

单函数的复合还是单函数，也就是若 $𝑓, 𝑔$ 都是单函数，那么 $𝑔 ⚬ 𝑓$ 还是单函数。

若函数 $𝑓$ 是单函数，那么 $𝑓$ 必存在左逆；若函数 $𝑓$ 存在左逆，那么 $𝑓$ 必是单函数。

若函数 $𝑓$ 是单函数，并且 $𝑆, 𝑇$ 是定义域的子集，那么 $𝑓 (𝑆 \cap 𝑇) = 𝑓 (𝑆) \cap 𝑓 (𝑇)$ 。反之亦然。

2.满函数

定义 3.（满函数）

如果对于任意陪域中的元素

𝑦 \in 𝐵

，都存在

𝑥 \in 𝐴

使

𝑓 (𝑥) = 𝑦

成立，也就是陪域就是值域，

ran (𝑓) = 𝐵

，那么就称函数

𝑓

为满函数。

满函数的复合还是满函数，也就是若 $𝑓, 𝑔$ 都是满函数，那么 $𝑔 ⚬ 𝑓$ 还是满函数。

若函数 $𝑓$ 是满函数，那么 $𝑓$ 必存在右逆；若函数 $𝑓$ 存在右逆，那么 $𝑓$ 必是满函数。

3.双函数

如果函数 $𝑓$ 既是单函数、又是满函数，那么就称 $𝑓$ 为双函数。也就是说，不仅如普通函数那样，有且仅有唯一一个陪域中的元素与定义域中的元素对应，双函数还有且仅有唯一一个定义域中的元素与陪域中的元素对应。

双函数的复合还是双函数，也就是若 $𝑓, 𝑔$ 都是双函数，那么 $𝑔 ⚬ 𝑓$ 还是双函数。

一个函数只有是双函数的情况下才有反函数。并且，由于双函数既是单函数、又是满函数，它必同时有左逆和右逆，并且都等于反函数。

同时，因为双函数是单函数，它亦存在 $𝑓 (𝑆 \cap 𝑇) = 𝑓 (𝑆) \cap 𝑓 (𝑇)$ 的性质。

四、函数的增长

我们使用大 $𝑂$ 记号来刻画函数的增长。对于两个数集上的函数 $𝑓, 𝑔$ ，如果存在常数 $𝐶 > 0$ 和 $𝑘$ ，使当 $𝑥 > 𝑘$ 时总有 $| 𝑓 (𝑥) | \leq 𝐶 | 𝑔 (𝑥) |$ ，那么称 $𝑓$ 是 $𝑂 (𝑔)$ ，并称 $𝐶$ 和 $𝑘$ 是 $𝑓$ 是 $𝑂 (𝑔)$ 的见证。 $𝑂 (𝑔)$ 事实上是以函数 $𝑔$ 为代表的、以函数为元素的集合，因此我们时常将“ $𝑓$ 是 $𝑂 (𝑔)$ ”记为 $𝑓 \in 𝑂 (𝑔)$ 。

例如对于多项式函数：

𝑓 (𝑥) = 𝑎_{𝑛} 𝑥^{𝑛} + 𝑎_{𝑛 - 1} 𝑥^{𝑛 - 1} + \dots + 𝑎_{1} 𝑥^{1} + 𝑎_{0}

无论系数取值如何，都必是 $𝑂 (𝑥^{𝑛})$ ，甚至 $𝑂 (𝑥^{𝑛 + 1}), 𝑂 (𝑥^{𝑛 + 2}) \dots$ ，但当 $𝑎_{𝑛} \neq 0$ 时，必不是 $𝑂 (𝑥^{𝑛 - 1})$ 。一些常见的函数增长如下：

log 𝑛 \in 𝑂 (𝑛) 𝑛 \in 𝑂 (𝑛 log 𝑛) 𝑛 log 𝑛 \in 𝑂 (𝑛^{2}) 𝑛^{2} \in 𝑂 (2^{𝑛}) 2^{𝑛} \in 𝑂 (𝑛!)

大 $𝑂$ 记号具有传递性。若 $𝑓 \in 𝑂 (𝑔), 𝑔 \in 𝑂 (ℎ)$ ，那么 $𝑓 \in 𝑂 (ℎ)$ 。

当 $𝑓, 𝑔 \in 𝑂 (ℎ)$ ，那么 $max {𝑓, 𝑔} \in 𝑂 (ℎ)$ 。

当 $𝑓_{1} \in 𝑂 (𝑔_{1}), 𝑓_{1} \in 𝑂 (𝑔_{2})$ ，那么 $𝑓_{1} + 𝑓_{2} \in 𝑂 (max {𝑔_{1}, 𝑔_{2}})$ ， $𝑓_{1} \cdot 𝑓_{2} \in 𝑂 (𝑔_{1} \cdot 𝑔_{2})$