本节对应原书 PDF 第 137–143 页。定义、定理、公式、例题及其原解答逐字取自原书；解释性文字为 AI 通俗化改写；标有「解读」的引用块为 AI 补充的额外直觉。

函数可以进行各种运算，复合运算和求反函数的运算是最重要的运算.

5.2.1 函数的复合

函数的复合就是关系的合成，所有关系合成的性质对于函数复合都是成立的，这里只讨论有关函数复合的一些特殊性质. 先给出关于函数复合运算的定理. 这个定理说明两个函数复合以后还是函数，同时给出了复合函数的定义域与函数值的计算规则.

定理 5.1 设 f,g 是函数，则 f\circ g 也是函数，且满足

(1) \mathrm{dom}(f\circ g)=\{x\mid x\in \mathrm{dom} f\wedge f(x)\in \mathrm{dom} g\}.

(2) \forall x\in \mathrm{dom}(f\circ g) 有 f\circ g(x)=g(f(x)).

证明 先证明 f\circ g 是函数. 因为 f，g 是关系，所以 f\circ g 也是关系. 若对某个 x\in \mathrm{dom}(f\circ g) 有 x f\circ g y_1 和 x f\circ g y_2，则

\langle x,y_1\rangle\in f\circ g\wedge\langle x,y_2\rangle\in f\circ g
\Rightarrow\exists t_1(\langle x,t_1\rangle\in f\wedge\langle t_1,y_1\rangle\in g)\wedge\exists t_2(\langle x,t_2\rangle\in f\wedge\langle t_2,y_2\rangle\in g)
\Rightarrow\exists t_1\exists t_2(t_1=t_2\wedge\langle t_1,y_1\rangle\in g\wedge\langle t_2,y_2\rangle\in g)\qquad(f\text{为函数})
\Rightarrow y_1=y_2\qquad(g\text{为函数})

所以 f\circ g 为函数.

再证明结论(1)和结论(2). 任取 x，

x\in \mathrm{dom}(f\circ g)
\Rightarrow\exists t\exists y(\langle x,t\rangle\in f\wedge\langle t,y\rangle\in g)
\Rightarrow\exists t(x\in \mathrm{dom} f\wedge t=f(x)\wedge t\in \mathrm{dom} g)
\Rightarrow x\in \{x\mid x\in \mathrm{dom} f\wedge f(x)\in \mathrm{dom} g\}

任取 x，

x\in \mathrm{dom} f\wedge f(x)\in \mathrm{dom} g
\Rightarrow\langle x,f(x)\rangle\in f\wedge\langle f(x),g(f(x))\rangle\in g
\Rightarrow\langle x,g(f(x))\rangle\in f\circ g
\Rightarrow x\in \mathrm{dom}(f\circ g)\wedge f\circ g(x)=g(f(x))

所以(1)和(2)得证.

从这个定理可知，复合函数 f\circ g 的定义域可能小于 f 的定义域，而它的值域也可能小于 g 的值域. 它们之间的关系满足：

\mathrm{dom}(f\circ g)\subseteq \mathrm{dom} f,\mathrm{ran}(f\circ g)\subseteq \mathrm{ran} g

解读：定理 5.1 的顺序容易被记反——f\circ g 是"先 f 后 g"，取值时才写成 g(f(x))。判断 x 能否进入定义域，要先过 f：不仅 x\in \mathrm{dom} f，还要求 f(x) 落在 \mathrm{dom} g 里，两关都过才算数。

推论 1 设 f,g,h 为函数，则 (f\circ g)\circ h 和 f\circ(g\circ h) 都是函数，且

(f\circ g)\circ h=f\circ(g\circ h)

证明 由上述定理和关系合成运算的可结合性得证.

推论 2 设 f:A\to B，g:B\to C，则 f\circ g:A\to C，且 \forall x\in A 都有 f\circ g(x)=g(f(x)).

证明 由上述定理知 f\circ g 是函数，且

\mathrm{dom}(f\circ g)=\{x\mid x\in \mathrm{dom} f\wedge f(x)\in \mathrm{dom} g\}
=\{x\mid x\in A\wedge f(x)\in B\}=A
\mathrm{ran}(f\circ g)\subseteq \mathrm{ran} g\subseteq C

因此 f\circ g:A\to C，且 \forall x\in A 有 f\circ g(x)=g(f(x)).

下面考虑函数的单射、满射、双射的性质与函数复合运算之间的关系.

定理 5.2 设 f:A\to B，g:B\to C.

(1) 如果 f:A\to B，g:B\to C 都是满射的，则 f\circ g:A\to C 也是满射的.

(2) 如果 f:A\to B，g:B\to C 都是单射的，则 f\circ g:A\to C 也是单射的.

(3) 如果 f:A\to B，g:B\to C 都是双射的，则 f\circ g:A\to C 也是双射的.

证明 (1) 任取 c\in C，由 g:B\to C 的满射性，\exists b\in B 使得 g(b)=c. 对于这个 b，由 f:A\to B 的满射性，\exists a\in A 使得 f(a)=b. 由合成定理有

f\circ g(a)=g(f(a))=g(b)=c

从而证明了 f\circ g:A\to C 是满射的.

(2) 假设存在 x_1，x_2\in A 使得

f\circ g(x_1)=f\circ g(x_2)

由合成定理有

g(f(x_1))=g(f(x_2))

因为 g:B\to C 是单射的，故 f(x_1)=f(x_2). 又由于 f:A\to B 也是单射的，所以 x_1=x_2. 从而证明 f\circ g:A\to C 是单射的.

(3) 由(1)和(2)得证.

定理 5.2 说明函数的复合运算能够保持函数单射、满射、双射的性质. 但这个定理的逆命题不为真，即如果 f\circ g:A\to C 是单射(或满射、双射)的，不一定有 f:A\to B 和 g:B\to C 都是单射(或满射、双射)的. 考虑集合 A=\{a_1,a_2,a_3\}，B=\{b_1,b_2,b_3,b_4\}，C=\{c_1,c_2,c_3\}. 令

f=\{\langle a_1,b_1\rangle,\langle a_2,b_2\rangle,\langle a_3,b_3\rangle\}
g=\{\langle b_1,c_1\rangle,\langle b_2,c_2\rangle,\langle b_3,c_3\rangle,\langle b_4,c_3\rangle\}
f\circ g=\{\langle a_1,c_1\rangle,\langle a_2,c_2\rangle,\langle a_3,c_3\rangle\}

那么 f:A\to B 和 f\circ g:A\to C 都是单射的，但 g:B\to C 不是单射的. 考虑集合 A=\{a_1,a_2,a_3\}，B=\{b_1,b_2,b_3\}，C=\{c_1,c_2\}. 令

f=\{\langle a_1,b_1\rangle,\langle a_2,b_2\rangle,\langle a_3,b_2\rangle\}
g=\{\langle b_1,c_1\rangle,\langle b_2,c_2\rangle,\langle b_3,c_2\rangle\}
f\circ g=\{\langle a_1,c_1\rangle,\langle a_2,c_2\rangle,\langle a_3,c_2\rangle\}

那么 g:B\to C 和 f\circ g:A\to C 是满射的，但 f:A\to B 不是满射的.

解读：两个反例各用一次"复合可以掩盖缺陷"：第一个反例里 g 把 b_3,b_4 都映到 c_3，但 b_4 根本不在 f 的值域中，缺陷被 f 挡住了；第二个反例里 f 漏掉了 b_3，但 g 把 b_2,b_3 映到同一个 c_2，漏掉的那个点看不出来。所以定理 5.2 只能"由内向外"推，不能反向。

下面考虑恒等函数在复合运算中的作用.

定理 5.3 设 f:A\to B，则 f=f\circ I_B=I_A\circ f.

定理 5.3 的证明可以采用集合相等的证明方法，这个证明留给读者思考.

推论 设 f:A\to A，则 f=f\circ I_A=I_A\circ f.

任何 A 上的函数 f 与 I_A 进行复合都等于 f，就像普通加法与 0 相加或者普通乘法与 1 相乘一样. 这里的 0，1 和 I_A 都叫做相关运算的单位元，关于单位元的性质将在后面第 14 章给出详细的介绍. 推论说明了 I_A 是 A 上的函数复合运算的单位元.

5.2.2 反函数

下面考虑函数的求逆运算. 任给函数 f，它的逆 f^{-1} 不一定是函数，只是一个二元关系. 任给单射函数 f:A\to B，则 f^{-1} 是函数，且是从 \mathrm{ran} f 到 A 的双射函数，但不一定是从 B 到 A 的双射函数. 对于双射函数 f:A\to B，容易证明 f^{-1}:B\to A 是从 B 到 A 的双射函数.

定理 5.4 设 f:A\to B 是双射的，则 f^{-1}:B\to A 也是双射的.

证明 因为 f 是函数，所以 f^{-1} 是关系，且

\mathrm{dom} f^{-1}=\mathrm{ran} f=B,\qquad \mathrm{ran} f^{-1}=\mathrm{dom} f=A

对于任意的 x\in B=\mathrm{dom} f^{-1}，假设有 y_1，y_2\in A 使得 \langle x,y_1\rangle\in f^{-1}\wedge\langle x,y_2\rangle\in f^{-1} 成立. 则由逆的定义有 \langle y_1,x\rangle\in f\wedge\langle y_2,x\rangle\in f. 根据 f 的单射性可得 y_1=y_2，从而证明了 f^{-1} 是函数，且由 \mathrm{ran} f^{-1}=A 知 f^{-1} 是满射的.

若存在 x_1，x_2\in B 使得 f^{-1}(x_1)=f^{-1}(x_2)=y，从而有

\langle x_1,y\rangle\in f^{-1}\wedge\langle x_2,y\rangle\in f^{-1}
\Rightarrow\langle y,x_1\rangle\in f\wedge\langle y,x_2\rangle\in f\Rightarrow x_1=x_2\qquad(\text{因为} f \text{是函数})

从而证明了 f^{-1} 的单射性.

对于双射函数 f:A\to B，称 f^{-1}:B\to A 是它的反函数.

解读：f^{-1} 要成为函数，唯一的障碍是"一个自变量对应两个值"；而对 f^{-1} 来说，自变量是 B 中的元素，所以恰恰要用 f 的单射性来排除。至于满射性，管的是 f^{-1} 的值域能否铺满 A，由 \mathrm{ran} f^{-1}=\mathrm{dom} f=A 自动成立。两个条件各管一头，缺一不可。

例 5.9 设 f:\mathbf{R}\to\mathbf{R}，g:\mathbf{R}\to\mathbf{R}

f(x)=\begin{cases}x^2 & x\geqslant 3\\-2 & x<3\end{cases}
g(x)=x+2

求 f\circ g，g\circ f. 如果 f 和 g 存在反函数，求出它们的反函数.

解

f\circ g:\mathbf{R}\to\mathbf{R}
f\circ g(x)=\begin{cases}x^2+2 & x\geqslant 3\\0 & x<3\end{cases}
g\circ f:\mathbf{R}\to\mathbf{R}
g\circ f(x)=\begin{cases}(x+2)^2 & x\geqslant 1\\-2 & x<1\end{cases}

f:\mathbf{R}\to\mathbf{R} 不是双射的，不存在反函数；g:\mathbf{R}\to\mathbf{R} 是双射的，它的反函数是

g^{-1}:\mathbf{R}\to\mathbf{R},\qquad g^{-1}(x)=x-2

解读：求 f\circ g(x)=g(f(x)) 时要把 f 的分段条件整体平移：f 的分界点是 x=3，经过 g 之后在 g\circ f 中分界点变成 x=1（因为 g 把 x 先加了 2）。分段函数复合最容易错的就是分界点没有跟着移动。

函数 f 的反函数具有下述性质.

定理 5.5 设 f:A\to B 是双射的，则

f^{-1}\circ f=I_B,\qquad f\circ f^{-1}=I_A

证明 根据定理 5.4 可知 f^{-1}:B\to A 也是双射的. 由合成基本定理可知 f^{-1}\circ f:B\to B，f\circ f^{-1}:A\to A，且它们都是恒等函数.

对于双射函数 f:A\to A，根据上述定理有 f^{-1}\circ f=f\circ f^{-1}=I_A.

关系和函数是离散数学的基本概念，在离散系统建模中有着重要的应用. 下面给出几个例子.

例 5.10 关系代数(relation algebra)

关系代数是关系数据库的基础. 一个通信录可以看作是一个简单的关系数据库，其中的分组，如同学组、同事组、朋友组等都可以看作是不同的关系. 每个关系都是若干元组的集合，元组 \langle A_1,A_2,\cdots,A_n\rangle 代表该关系有 n 个属性. 例如，通信录的朋友组 R 可能含有下述信息：\langle 2,李明,50,融创大厦 A 座 502,13341556347,liming@hotmail.com.cn\rangle，该信息是由编号、姓名、年龄、地址、手机号、电子邮箱 6 条属性构成的六元组. 表 5.1 给出了具有 4 条信息的关系 R.

表 5.1

编号姓名年龄地 址手 机Email
1张晓光34科斯公司市场部13520145678zhxg@gmail.com.cn
2李 明50融创大厦 A 座 50213341556347liming@hotmail.com.cn
3王 恒43求实中学13124567336wheng@qq.com.cn
4石海生27大华公司网络中心13822253689Shihs@hotmail.com.cn

为了得到相关的查询结果，数据库中定义了几种基本操作：并、交、差、笛卡儿积、选择、投影. 设 R 与 S 是具有相同属性的 m 元关系，其中的 m 个属性记作 A_1,A_2,\cdots,A_m，这些基本操作说明如下：

R\cup S 的元组既含有 R 的元组，也含有 S 的元组；

R\cap S 的元组是同时存在于 R 和 S 中的元组；

R-S 的元组只在 R 中但不在 S 中.

投影 \pi_{A_{i_1},A_{i_2},\cdots,A_{i_n}}(R) 是从 m 阶笛卡儿积 A_1\times A_2\times\cdots\times A_m 到 n 阶笛卡儿积 A_{i_1}\times A_{i_2}\times\cdots\times A_{i_n} 的部分映射，\pi_{A_{i_1},A_{i_2},\cdots,A_{i_n}}(R) 表示只选取 R 中属性为 A_{i_1},A_{i_2},\cdots,A_{i_n} 的列. 例如，对表 5.1 中的关系 R 进行投影运算，\pi_{\text{姓名},\text{手机},\text{Email}}(R) 的查询结果如表 5.2 所示.

表 5.2

姓名手 机Email
张晓光13520145678zhxg@gmail.com.cn
李 明13341556347liming@hotmail.com.cn
王 恒13124567336wheng@qq.com.cn
石海生13822253689Shihs@hotmail.com.cn

选择操作可以看作是对关系的限制，它是从 R 的所有元组中选出满足某个约束条件的元组. 表达式 \pi_{\text{年龄}<50}(R) 要求查询输出 R 中年龄小于 50 的人，查询结果如表 5.3 所示.

表 5.3

编号姓名年龄地 址手 机Email
1张晓光34科斯公司市场部13520145678zhxg@gmail.com.cn
3王恒43求实中学13124567336wheng@qq.com.cn
4石海生27大华公司网络中心13822253689Shihs@hotmail.com.cn

设关系 R 是形如 \langle A_1,A_2,\cdots,A_m\rangle 的 m 元组构成的集合，关系 S 是形如 \langle B_1,B_2,\cdots,B_n\rangle 的 n 元组构成的集合，这里的 A_1,\cdots,A_m,B_1,\cdots,B_n 都是属性. 那么笛卡儿积 R\times S 是由 m\times n 个形如 \langle A_1,\cdots,A_m,B_1,\cdots,B_n\rangle 的 m+n 元组构成的集合. 每个 R 中的 m 元组与每个 S 中的 n 元组都可以构成一个 m+n 元组. 例如关系 R 的属性是商品标号与名称，S 的属性是商品名称、价格与规格. 其中

R=\{\langle 1,abc\rangle,\langle 2,cabel\rangle\},\quad S=\{\langle cabel,300,25\rangle,\langle \sin,190,15\rangle,\langle cod,60,5\rangle\},

那么

R\times S=\{\langle 1,abc,cabel,300,25\rangle,\langle 1,abc,\sin,190,15\rangle,\langle 1,abc,cod,60,5\rangle,
\langle 2,cabel,cabel,300,25\rangle,\langle 2,cabel,\sin,190,15\rangle,\langle 2,cabel,cod,60,5\rangle\}

如果 R 与 S 有相同的属性，上述定义中的关系的笛卡儿积包含了较多的冗余信息，因此可以定义连接(join)操作，此操作仅仅对 R 与 S 中的公共属性值相同的元组配对. 例如，上述例子中的 R 与 S 的自然连接的结果是 \{\langle 2,cabel,300,25\rangle\}. 如果加上选择条件，还可以定义更复杂的 \theta 连接操作. 限于篇幅，这里不再赘述. 关系代数是关系数据库的理论基础，其基本性质可以用集合、关系和映射来描述.

解读：投影对应 SQL 的 SELECT 列，选择对应 WHERE 行，笛卡儿积对应不带条件的两表相乘；而"自然连接"就是把笛卡儿积的结果按公共属性值相同这一条件筛一遍，所以表 5.2 的列、表 5.3 的行都是关系（集合），不是函数。

例 5.11 工作流系统的网模型.

工作流是为业务流程建模而引入的技术，目前已经广泛应用于办公自动化、工业流程控制等众多领域. Aalst 用工作流网 WF_net 对工作流进行建模，它的基础就是 Petri 网. 下面给出 WF_net 的定义.

WF_net 是三元组 \langle P,T,F\rangle，其中，P 是库所(place)集合，T 是变迁(transition)集合，F 称为流关系. 它们之间满足以下条件：

(1) P\cap T=\varnothing;

(2) P\cup T\neq\varnothing;

(3) F\subseteq P\times T\cup T\times P;

(4) \mathrm{dom} F\cup \mathrm{ran} F=P\cup T，其中

\mathrm{dom} F=\{x\mid\exists y(\langle x,y\rangle\in F)\},\mathrm{ran} F=\{y\mid\exists x(\langle x,y\rangle\in F)\};

(5) 存在起始库所 i\in P，使得 {}^{\bullet}i=\varnothing，这里 {}^{\bullet}i=\{j\mid\langle j,i\rangle\in F\}，称为 i 的前集;

(6) 存在终止库所 o\in P，使得 o^{\bullet}=\varnothing，这里 o^{\bullet}=\{j\mid\langle o,j\rangle\in F\}，称为 o 的后集;

(7) 每个结点 x\in P\cup T，都处在从 i 到 o 的一条路径上.

前面 4 个条件是一般 Petri 网所满足的条件. 条件(1)表明库所和变迁是两类不同的元素. 条件(2)说明网中至少含有 1 个元素. 条件(3)是关于流关系的基本性质，流关系反映的是资源的流动. 资源可以从库所到变迁，也可以从变迁到库所，同一类元素之间没有流动. 不属于 \mathrm{dom} F\cup \mathrm{ran} F 的库所或变迁是孤立结点，不参与资源流动. 条件(4)表示网中没有孤立结点. 最后 3 个条件是工作流网所特有的. 对于任意库所 p，p 的前集 {}^{\bullet}p 指的是有边通向 p 的全体变迁的集合，p 的后集 p^{\bullet} 指的是从 p 出发的边所指向的全体变迁的集合.

条件(5)～条件(7)说明起始库所 i 没有进入边，终止库所 o 没有出发边，并且网中没有冗余的结点. 与实际业务流程对应，变迁代表流程中的活动. 活动之间通过库所连接，库所起到流程控制的作用. 活动之间的逻辑关系可以是顺序、分支等多种结构. 起始库所 i 中的托肯(token，也称作"令牌"，用小黑点表示)代表一个案例.

在 WF_net 中变迁分成 4 类："与分支(and-split)"、"或分支(or-split)"、"与连接(and-join)"和"或连接(or-join)"，分别用图 5.2 中的 4 种符号表示.

原书图5.2

图 5.2

"与分支"变迁发生后，其后集中的所有库所都有托肯；"或分支"变迁发生后，根据发生的结果，其后集中只有一个库所有托肯；"与连接"变迁发生的前提条件是：其前集的所有库所都有托肯；"或连接"变迁发生的前提条件是：其前集中的某一个库所有托肯.

一个论文评审的工作流网模型如图 5.3 所示. 其中，14 个变迁的含义分别是：

T_1：收到论文，邀请三个评审人；

T_2：在预定时间内得到第一份评审意见；

T_3：在预定时间内没得到第一份评审意见；

T_4：在预定时间内得到第二份评审意见；

T_5：在预定时间内没得到第二份评审意见；

T_6：在预定时间内得到第三份评审意见；

T_7：在预定时间内没得到第三份评审意见；

T_8：汇总评审意见；

T_9：决定是否接受论文；

T_{10}：接受论文；

T_{11}：不接受论文；

T_{12}：再邀请其他评审人；

T_{13}：在预定时间收到评审意见；

T_{14}：在预定时间没收到评审意见.

原书图5.3

图 5.3

采用集合、关系的概念可以对上述工作流网给出形式化描述，设该工作流网为 WF_net=\langle P,T,F\rangle，其中

P=\{i,o,p_1,p_2,\cdots,p_9\},
T=\{T_1,T_2,\cdots,T_{14}\},
\begin{aligned} F=\{&\langle i,T_1\rangle,\langle T_1,p_1\rangle,\langle T_1,p_2\rangle,\langle T_1,p_3\rangle,\langle p_1,T_2\rangle,\\ &\langle p_1,T_3\rangle,\langle p_2,T_4\rangle,\langle p_2,T_5\rangle,\langle p_3,T_6\rangle,\langle p_3,T_7\rangle,\\ &\langle T_2,p_4\rangle,\langle T_3,p_4\rangle,\langle T_4,p_5\rangle,\langle T_5,p_5\rangle,\langle T_6,p_6\rangle,\\ &\langle T_7,p_6\rangle,\langle p_4,T_8\rangle,\langle p_5,T_8\rangle,\langle p_6,T_8\rangle,\langle T_8,p_8\rangle,\\ &\langle p_8,T_9\rangle,\langle T_9,p_9\rangle,\langle p_9,T_{10}\rangle,\langle p_9,T_{11}\rangle,\langle p_9,T_{12}\rangle,\\ &\langle T_{12},p_7\rangle,\langle p_7,T_{13}\rangle,\langle p_7,T_{14}\rangle,\langle T_{13},p_8\rangle,\\ &\langle T_{14},p_8\rangle,\langle T_{10},o\rangle,\langle T_{11},o\rangle\}. \end{aligned}

{}^{\bullet}i=\varnothing;o^{\bullet}=\varnothing;每个结点都恰好在一条从 i 到 o 的路径上.

依照流程，首先发生变迁 T_1(收到论文，邀请三个评审人). 这是一个"与分支"变迁，其后集中的库所 p_1、p_2 和 p_3 都有托肯. T_2、T_3 表示第一个评审人的评审结果：收到评审意见或者没收到评审意见. 类似地，T_4、T_5、T_6、T_7 表示另外 2 份评审结果. T_8 将评审意见汇总，T_9 提交编辑部决定是否接受该论文. T_{10} 表示接受论文，T_{11} 表示拒绝论文，T_{12} 表示需要再找人评审. 与前面类似，评审结果有两种：及时收到评审意见(T_{13})，没收到评审意见(T_{14}). 这些仍旧需要提交编辑部再次讨论决定. 只要到达接受论文或者拒绝论文，这都将导致处理流程的结束.

建立了基于 Petri 网的工作流模型，并利用 Petri 网的描述能力和分析方法对流程的某些性质进行分析，就可以对流程进行化简，还可以进行计算机模拟.

解读：把 WF_net 的 7 个条件分成两组看更清楚——(1)–(4) 只是说"库所和变迁互不相干、边只跨两类元素、没有孤立点"，任何 Petri 网都满足；(5)–(7) 才是工作流的额外要求：必须有一个只出不进的起点 i 和一个只进不出的终点 o，并且每个结点都夹在 i 到 o 的路上，这排除了永远走不到终点的"死枝"。