本文属于「离散数学」系列文章之一。这一系列着重于离散数学的学习和应用。由于内容随时可能发生更新变动，欢迎关注和收藏离散数学系列文章汇总目录一文以作备忘。此外，在本系列学习文章中，为了透彻理解数学知识，本人参考了诸多博客、教程、文档、书籍等资料。以下是本文的不完全参考目录，在后续学习中还会逐渐补充：

• （国外经典教材）离散数学及其应用 第七版 Discrete Mathematics and Its Applications 7th ，作者是 Kenneth H.Rosen ，袁崇义译，机械工业出版社
• 离散数学 第二版，武波等编著，西安电子科技大学出版社，2006年
• 离散数学 第三版，方世昌等编著，西安电子科技大学出版社，2013年
• （经典参考书及其题解）离散数学/离散数学——理论•分析•题解，左孝凌、李为鉴、刘永才编著，上海科学技术文献出版社
• 离散数学习题集：数理逻辑与集合论分册，耿素云；图论分册，耿素云；抽象代数分册， 张立昂。北京大学出版社

---

4.1 函数

高等数学中从变量的角度提出了函数的概念，而且是在实数集合上讨论函数，这种函数一般是连续或间断连续的。现在，我们将连续函数的概念，推广到离散变量上，即将函数看作一种特殊的二元关系。这时，我们之前讨论的有关集合或关系的运算和性质，也完全适用于函数。

函数的概念，在日常生活和计算机科学中都非常重要，各种高级编程语言中大量使用函数，而计算机的任何输出，都可看做是某个函数作用于某些输入上的结果。

4.1.1 函数的定义

定义4.1.1 设 $X$ 和 $Y$ 是集合，$f$ 是从 $X$ 到 $Y$ 上的二元关系，如果对于每个 $x\in X$ 都有唯一的 $y\in Y$ ，使得 $⟨x,y⟩\in f$ ，则称 $f$ 为从 $X$ 到 $Y$ 的函数 a function from X to Y ，记为$f:X\to Y$ 。函数的形式化定义为：
$$f:X\to Y\iff \forall x(x\in X\to \exists y(y\in Y\wedge ⟨x,y⟩\in f\wedge \forall z(z\in Y\wedge ⟨x,z⟩\in f\to y=z)))$$

函数又称作映射 mapping 或变换 transformation 。

定义4.1.2 设 $f$ 为从集合 $X$ 到 $Y$ 的函数，任取 $x\in X$ ，若 $⟨x,y⟩\in f$ ，则称 $y$ 为在 $f$ 下 $x$ 的函数值 value 或像 image ，记为 $f(x)=y$ ，而 $x$ 则称为 $y$ 的原像 preimage 。若 $X^{\prime }\subseteq X$ ，称 f ( X ′ ) = { f ( x ) ∣ x ∈ X ′ } f(X') = \{ f(x) \mid x \in X'\} f(X′)={ f(x)∣x∈X′} 为函数 $f$ 下 $X^{\prime }$ 的像。特别地，称整个前域 $X$ 的像 $f(X)$ 为函数的值域。

设 $f$ 为从集合 $X$ 到 $Y$ 的函数，下图描述了函数 $f$ 的基本特征。其中函数 $f$ 的前域 $X$ 为集合 $X$ ，陪域为集合 $Y$ ，函数 $f$ 的定义域 $\text{dom}f=X$ ，值域 ran f = f ( X ) = { f ( x ) ∣ x ∈ X } \textrm{ran} f = f(X) = \{ f(x) \mid x \in X\} ranf=f(X)={ f(x)∣x∈X} ，显然有 $\text{ran}f\subseteq f$ 。

$X$ 到 $Y$ 的函数实质上是一个从 $X$ 到 $Y$ 的二元关系，反过来则不一定，从 $X$ 到 $Y$ 的二元关系不一定是 $X$ 到 $Y$ 的函数。区别于一般二元关系，函数有以下两个特征：

• （点点有定义）函数 $f$ 的定义域 $\text{dom}f=X$ （即函数的定义域是 $X$ ，而不能是 $X$ 的某个真子集）；
• （值唯一性/单值性）对于每个 $x\in X$ ，在 $Y$ 中有且仅有唯一的一个元素 $y$ ，满足 $⟨x,y⟩\in f$ ，即对 $y_1,y_2\in Y$ ，有
  $$f(x)=y_1\wedge f(x)=y_2\Rightarrow y_1=y_2$$

一个关于某个具体函数的描述，如果满足函数的定义，则称这个函数描述是良定义的 well defined 。

【例1】判断下图所示的四个关系中，哪些能构成函数。

解：(a)不是函数，因为 $x_2$ 没有像；(b)也不是函数，因为 $x_2$ 有两个像；其他两个都是函数。

【例2】判断下列关系中，哪些能构成函数。
（1）$f$ 是 $\mathbb{N}$ 上的二元关系，且 f = { ⟨ x 1 , x 2 ⟩ ∣ x 1 , x 2 ∈ N ,   x 1 + x 2 < 10 } f = \{ \langle x_1, x_2 \rangle \mid x_1, x_2 \in \N,\ x_1 + x_2 < 10\} f={ ⟨x1​,x2​⟩∣x1​,x2​∈N, x1​+x2​<10}
（2）$f$ 是 $\mathbb{R}$ 上的二元关系，且 f = { ⟨ y 1 , y 2 ⟩ ∣ y 1 , y 2 ∈ R ,   y 2 2 = y 1 } f = \{ \langle y_1, y_2 \rangle \mid y_1, y_2 \in \R,\ y_2^2 = y_1 \} f={ ⟨y1​,y2​⟩∣y1​,y2​∈R, y22​=y1​}
（3）$f$ 是 $\mathbb{N}$ 上的二元关系，且 f = { ⟨ x 1 , x 2 ⟩ ∣ x 1 , x 2 ∈ N ,   x 2 为 小 于 x 1 的 素 数 个 数 } f = \{ \langle x_1, x_2 \rangle \mid x_1, x_2 \in \N, \ x_2为小于x_1的素数个数\} f={ ⟨x1​,x2​⟩∣x1​,x2​∈N, x2​为小于x1​的素数个数}
解：
（1）不能，因为 $\text{dom}f\ne \mathbb{N}$ ，且存在 $x_1$ 对应多个 $x_2$ 。
（2）不能。若 $y_1>0$ ，则 $y_2$ 可取 $\pm \sqrt{y_1}$ 两个元素；若 $y_1<0$ ，则 $y_2$ 无解。
（3）能，因为 $\text{dom}f=\mathbb{N}$ ，且对每个 $x_1\in \mathbb{N}$ 都有唯一的元素 $x_2\in \mathbb{N}$ 与之对应。

【例3】以下哪些关于函数的描述是良定义的？
（1）$f:\mathbb{N}\to \mathbb{Q},f(x)=\frac{1}{x}$
（2） g : { 1 , 2 , 3 } → { p , q , r } ,   g = { ⟨ 1 , q ⟩ , ⟨ 2 , r ⟩ , ⟨ 3 , p ⟩ } g:\{1, 2, 3\} \to \{ p, q, r\},\ g = \{ \langle 1, q\rangle, \langle 2, r\rangle, \langle 3, p\rangle \} g:{ 1,2,3}→{ p,q,r}, g={ ⟨1,q⟩,⟨2,r⟩,⟨3,p⟩}
（3）$f:\mathbb{N}\to \mathbb{Z},(f(x){)}^2=x+1$
（4）$h:\mathbb{R}\times \mathbb{R}\to \mathbb{R}\times \mathbb{R},h(⟨x,y⟩)=⟨y+1,x+1⟩$
解：
（1）不是良定义的，它在 $0$ 处无定义。
（2）是良定义的；
（3）不是良定义的，每个 $x\in \mathbb{N}$ 存在 $\pm \sqrt{x+1}$ 两个元素与之对应；
（4）是良定义的。

设 $X,Y$ 都是有限集合，且有 $|X|=m,|Y|=n$ 。根据函数的定义，对于集合 $X$ 中的每个元素，在 $Y$ 中有且仅有一个元素与之对应。考虑这样一类 $X$ 到 $Y$ 的二元关系 $f$ ：
f = { ⟨ x 1 , □ ⟩ , ⟨ x 2 , □ ⟩ , … , ⟨ x m , □ ⟩ } f = \{ \langle x_1, \Box\rangle, \langle x_2, \Box\rangle, \dots, \langle x_m, \Box\rangle \} f={ ⟨x1​,□⟩,⟨x2​,□⟩,…,⟨xm​,□⟩}

对于每个 $\square$ 所在的位置，可用集合 $Y$ 中的任何一个元素替代，即有 $n$ 种不同的取法，这样的组合共有 $n^m$ 种，因此 $X$ 到 $Y$ 上有 $2^{m\times n}$ 种不同的二元关系，却只有 $n^m$ 个不同的函数。一般来说，我们用 $Y^X$ 表示 $X$ 到 $Y$ 的所有函数构成的集合，即 Y X = { f ∣ f : X → Y } Y^X = \{ f\mid f: X\to Y\} YX={ f∣f:X→Y} ，且 $|Y^X|=n^m=|Y{|}^{|X|}$ 。

定义4.1.3 $f:A\to B,g:C\to D$ ，如果 $A=C,B=D$ ，且对于所有的 $x\in A$ ，有 $f(x)=g(x)$ ，则称函数 $f$ 和 $g$ 相等 ，记为 $f=g$ 。

由定义4.1.3可见，「函数相等的定义」与「关系相等的定义」是一致的，它们都要求相同的前域与陪域和相同的对应关系。如函数 $f_1:I\to I,f_1(x)=x^2$ 和函数 f 2 : { 1 , 2 , 3 } → I ,   f 2 ( x ) = x 2 f_2: \{1, 2, 3\} \to I,\ f_2(x)= x^2 f2​:{ 1,2,3}→I, f2​(x)=x2 ，它们是两个不同的函数。

定义4.1.4 当函数 $f$ 的前域 $X$ 是 $n$ 个集合的笛卡尔积时，即 $X={⨉}_{i=1}^n{X}_i$ 时，称 $f$ 为 $n$ 元函数，$⟨x_1,x_2,\dots ,x_n⟩\in X$ ，在函数 $f$ 下的映像记为 $f(x_1,x_2,\dots ,x_n)$ 。

【例4】设函数 $f:\mathbb{N}\times \mathbb{N}\to \mathbb{N}$ ，$f(x,y)=x+2y+1$ 。
（1）求 $⟨2,0⟩$ 在函数 $f$ 下的像；
（2）求 $\text{dom}f$ 和 $\text{ran}f$ 。
解：
（1）$f(2,0)=2+2\times 0+1=3$ .
（2）$\text{dom}f=\mathbb{N}\times \mathbb{N}$ ，不存在 $⟨x,y⟩\in \mathbb{N}\times \mathbb{N}$ 使得 $f(x,y)=0$ ，则 $\text{ran}f={\mathbb{Z}}^{+}$ .

---

4.1.2 递归定义的函数

当函数的前域是用归纳定义的集合时，可以采用递归定义 recursive definitions 的方法定义函数。递归定义的规则是：用「已知元素的函数值」和「给定的函数」，计算新元素的函数值。

特别地，递归定义的函数不一定是归纳的，因为归纳法要求从较小元素的函数值确定较大元素的函数值，而递归定义则不一定遵守这种顺序。

【例5】给出自然数集合 $\mathbb{N}$ 上的阶乘函数 $f(n)=n!$ 的递归定义。
解：设 $f:\mathbb{N}\to \mathbb{N}$ 。
（a）（基础）$f(0)=1$ .
（b）（归纳）$n\in \mathbb{N},f(n+1)=(n+1)f(n)$ .

【例6】给出自然数集合 $\mathbb{N}$ 上的斐波那契函数的递归定义。
解：设 $f:\mathbb{N}\to \mathbb{N}$ 是斐波那契函数。
（a）（基础）$f(0)=0,f(1)=1$ .
（b）（归纳）$n\in \mathbb{N},f(n+2)=f(n+1)+f(n)$ .

【例7】以下是麦卡锡91函数，它是递归定义的。设 $f:\mathbb{N}\to \mathbb{N}$ ，已知
$$f(x)=\{\begin{array}{ll}x-10& \text{if}x>100\\ f(f(x+11))& \text{if}0\le x\le 100\end{array}$$

求 $f$ 的函数值。
解：由题意可知：$$\begin{gathered} f(90)=f(f(101))=f(91)=f(f(102))=f(92)=\cdots =f(99) \\ =f(f(110))=f(100)=f(f(111))=f(101)=91 \end{gathered}$$ 因此：

• 当 $90\le x\le 100$ 时有 $f(x)=91$ 。
• 当 $0\le x<90$ 时，存在 $k\in {\mathbb{Z}}^{+}$ ，使得 $90\le x+11k\le 100$ ，因此 $$f(x)=f(f(x+11))=\cdots =f^{k+1}(x+11k)=f^k(f(x+11k))$$ 因为 $90\le x+11k\le 100$ ，所以 $f(x+11k)=91$ ，故 $$f(x)=f^k(f(x+11k))=f^k(91)=f^{k-1}(f(91))=f^{k-1}(91)=\cdots =f(91)=91$$

综上可得：
$$f(x)=\{\begin{array}{ll}x-10& \text{if}x>100\\ 91& \text{if}0\le x\le 100\end{array}$$

【例8】阿克曼函数 Ackerman $f:{\mathbb{N}}^2\to \mathbb{N}$ 的递归定义如下：
$$\{\begin{array}{ll}f(0,n)=n+1& \text{if}n\ge 0\\ f(m,0)=f(m-1,1)& \text{if}m>0\\ f(m,n)=f(m-1,f(m,n-1))& \text{if}m>0,n>0\end{array}$$

（1）求 $f(2,1)$ .
（2）证明 $f(2,n)=2n+3$ .
解：（1）
① $f(2,1)=f(1,f(2,0))$
② $f(2,0)=f(1,1)$
③ $f(1,1)=f(0,f(1,0))$
④ $f(1,0)=f(0,1)=2$
⑤ $f(1,1)=f(0,2)=3$
⑥ $f(2,0)=3$
⑦ $f(2,1)=f(1,3)$
⑧ $f(1,3)=f(0,f(1,2))$
⑨ $f(1,2)=f(0,f(1,1))=f(0,3)=4$
⑩ $f(1,3)=f(0,4)=5$
⑪ $f(2,1)=5$
（2）证明如下：
① 当 $m=0,n\ge 0$ 时，$f(0,n)=n+1$ 。
② 当 $m=1$ 时，有

• 若 $n=0$ ，则 $f(1,0)=f(0,1)=2$ ；
• 若 $n=1$ ，则 $f(1,1)=f(0,f(1,0))=f(1,0)+1=3$ ；

假设 $n=k(k\ge 1)$ 时，有 $f(1,k)=k+2$ 。若 $n=k+1$ ，则 $$f(1,k+1)=f(0,f(1,k))=f(1,k)+1=(k+2)+1=(k+1)+2$$ 因此，当 $m=1$ 时有 $f(1,n)=n+2$ 。

③ 当 $m=2$ 时，有

• 若 $n=0$ ，则 $f(2,0)=f(1,1)=3=2\times 0+3$
• 若 $n=1$ ，则 $f(2,1)=f(1,f(2,0))=f(1,3)=5=2\times 1+3$

假设 $n=k(k\ge 1)$ 时，有 $f(2,k)=2k+3$ 。若 $n=k+1$ ，则
$$f(2,k+1)=f(1,f(2,k))=f(2,k)+2=2k+3+2=2(k+1)+3$$

因此，当 $m=2$ 时有 $f(2,n)=2n+3$ 。

不过，当 $m=3$ 时，$f(3,n)=2^{n+3}-3$ ——这一规律就不是那么好发现的。总的来说，假设 $m$ 为层数（主序，即认为每一层 $m$ 确定、$n$ 变化），$n$ 为列数：

• $f(0,n)=n+1$ 给出了 $m=0$ 时的归纳基础（最基础的归纳边界）；
• $f(m,0)=f(m-1,1)$ 给出了 $m>0,n=0$ 时 $f(m,0)$ 对上一层函数的依赖（归纳）；
• $f(m,n)=f(m-1,f(m,n-1))$ 给出了 $m>0,n>0$ 时 $f(m,n)$ 对前式和上一层函数的依赖（归纳）

在归纳定义的集合上进行函数的递归定义时，所得未必是一个函数，特别是当前域的归纳定义使得某些元素可由多种方法构造时，更容易出现这种情况。因此，用递归定义函数时，常需要证明这个函数定义是良定义的。

【例9】设 Σ = { a , b , c } \Sigma = \{a, b, c\} Σ={ a,b,c} ，集合 ${\Sigma }^{+}$ 的定义如下：
（1）（基础）$a\in {\Sigma }^{+},b\in {\Sigma }^{+},c\in {\Sigma }^{+}$ 。
（2）（归纳）如果 $x\in {\Sigma }^{+},y\in {\Sigma }^{+}$ ，那么 $xy\in {\Sigma }^{+}$ 。
（3）（极小性）${\sum }^{+}$ 是满足条款(1)、(2)的最小集合。
设 $f$ 是从 ${\Sigma }^{+}$ 到自然数集合 $\mathbb{N}$ 上的一个函数，$f$ 的递归定义如下：
（a）（基础）$f(a)=2,f(b)=1,f(c)=3$ 。
（b）（归纳）$x,y\in {\Sigma }^{+}$ ，$f(xy)=f(x{)}^{f(y)}$ 。
试证明 $f$ 不是良定义的。

证明：对于串 $abc\in {\Sigma }^{+}$ ，它可以有以下两种不同的构造方法：
（a）令 $x=a,y=bc$ ，则 $xy=abc$ 。
（b）令 $x=ab,y=c$ ，则 $xy=abc$ 。
根据 $f$ 的递归定义，求 $abc$ 在 $f$ 下的值：
$$f(abc)=f(a{)}^{f(bc)}=2^{1^3}=2,f(abc)=f(ab{)}^{f(c)}=(2^1{)}^3=8$$ 所以 $f$ 不是良定义的。