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

关系可以进行复合运算，函数是一种特殊的二元关系，所以也可以进行复合运算。复合是获得新函数的常用方法之一。

定义4.4.1 设 f : X → Y f: X \to Y f:X→Y ， g : Y → Z g: Y\to Z g:Y→Z 是函数，令： g ⋄ f = { ⟨ x , z ⟩ ∣ x ∈ X ∧ z ∈ Z ∧ ( ∃ y ) ( y ∈ Y ∧ f ( x ) = y ∧ g ( y ) = z ) } g\diamond f = \{ \langle x, z\rangle \mid x\in X \land z \in Z \land (\exist y)(y \in Y \land f(x) = y \land g(y) = z)\} g⋄f={⟨x,z⟩∣x∈X∧z∈Z∧(∃y)(y∈Y∧f(x)=y∧g(y)=z)} 则称 g ⋄ f g\diamond f g⋄f 为 f f f 与 g g g 的复合函数，称 ⋄ \diamond ⋄ 为复合运算。

注意， f f f 与 g g g 的函数复合表示为 g ⋄ f g \diamond f g⋄f ，而 f f f 与 g g g 的关系复合表示为 f ∘ g f \circ g f∘g ，二者的结合顺序恰好相反，函数复合采用的是从右往左复合的方式，简称左复合。复合函数 g ⋄ f g \diamond f g⋄f 与复合关系 f ∘ g f\circ g f∘g 的次序不一样的原因是，为了和微积分中复合函数的习惯记法保持一致，如 sin ⁡ ln ⁡ x \sin \ln x sinlnx 中先求 ln ⁡ x \ln x lnx ，再求 sin ⁡ ( ln ⁡ x ) \sin (\ln x) sin(lnx) 。

定理4.4.1 设 f : X → Y f : X\to Y f:X→Y ， g : Y → Z g: Y\to Z g:Y→Z 是函数，则 g ⋄ f g\diamond f g⋄f 是从 X X X 到 Z Z Z 的函数。 证明 g ⋄ f g \diamond f g⋄f 显然是从 X X X 到 Z Z Z 的二元关系，现证明任取 x ∈ Z x \in Z x∈Z ，存在唯一的 z ∈ Z z \in Z z∈Z 使得 ⟨ x , z ⟩ ∈ g ⋄ f \langle x, z\rangle \in g\diamond f ⟨x,z⟩∈g⋄f 。 任取 x ∈ X x \in X x∈X ，因为 f f f 是从 X X X 到 Y Y Y 的函数，所以存在唯一的 y ∈ Y y \in Y y∈Y 满足 f ( x ) = y f(x) = y f(x)=y ，即 ⟨ x , y ⟩ ∈ f \langle x, y\rangle \in f ⟨x,y⟩∈f 。又因为 g g g 是从 Y Y Y 到 Z Z Z 的函数，所以存在唯一的 z ∈ Z z \in Z z∈Z 满足 g ( y ) = z g(y) = z g(y)=z ，即 ⟨ y , z ⟩ ∈ g \langle y, z \rangle \in g ⟨y,z⟩∈g 。因此，对任一 x ∈ X x \in X x∈X ，均存在唯一的 z ∈ Z z \in Z z∈Z ，使得 ⟨ x , z ⟩ ∈ g ⋄ f \langle x, z\rangle \in g \diamond f ⟨x,z⟩∈g⋄f 。所以，复合函数 g ⋄ f g \diamond f g⋄f 是从 X X X 到 Z Z Z 的函数。

为了方便，如果 f : X → Y ,   g : Y → Z f: X \to Y,\ g: Y\to Z f:X→Y, g:Y→Z 是函数，则 ⟨ x , z ⟩ ∈ g ⋄ f \langle x, z\rangle \in g \diamond f ⟨x,z⟩∈g⋄f ，记为 ( g ⋄ f ) ( x ) = g ( f ( x ) ) = z (g \diamond f)(x) = g(f(x)) = z (g⋄f)(x)=g(f(x))=z 。

【例1】设 X = { 1 , 2 , 3 } ,   Y = { p , q } ,   Z = { a , b } X = \{1, 2, 3\}, \ Y = \{p, q\},\ Z = \{a, b\} X={1,2,3}, Y={p,q}, Z={a,b} 。从 X X X 到 Y Y Y 的函数 f = { ⟨ 1 , p ⟩ , ⟨ 2 , p ⟩ , ⟨ 3 , q ⟩ } f = \{ \langle 1, p\rangle, \langle 2, p\rangle, \langle 3, q\rangle \} f={⟨1,p⟩,⟨2,p⟩,⟨3,q⟩} ，从 Y Y Y 到 Z Z Z 的函数 g = { ⟨ p , b ⟩ , ⟨ q , b ⟩ } g = \{ \langle p, b\rangle, \langle q, b\rangle \} g={⟨p,b⟩,⟨q,b⟩} 。求 g ⋄ f g \diamond f g⋄f 。 解：如下图所示，可得： g ⋄ f = { ⟨ 1 , b ⟩ , ⟨ 2 , b ⟩ , ⟨ 3 , b ⟩ } g \diamond f = \{ \langle 1, b\rangle, \langle 2, b\rangle, \langle 3, b\rangle \} g⋄f={⟨1,b⟩,⟨2,b⟩,⟨3,b⟩}

【例2】设 R R R 为实数集合，对 x ∈ R x \in \R x∈R 有 f ( x ) = x + 2 ,   g ( x ) = x − 1 f(x) = x+2,\ g(x) = x - 1 f(x)=x+2, g(x)=x−1 ，求 g ⋄ f g\diamond f g⋄f 。 解：任取 x ∈ R x \in \R x∈R ， x x x 在函数 f f f 下的映像 f ( x ) = x + 2 f(x) = x + 2 f(x)=x+2 ，而 x + 2 x+2 x+2 在函数 g g g 下的映像为 g ( x + 2 ) = x + 2 − 1 = x + 1 g(x+2) = x+2 - 1= x+1 g(x+2)=x+2−1=x+1 。所以 g ⋄ f ( x ) = x + 1 g\diamond f (x) = x+1 g⋄f(x)=x+1 。

【例3】设 f : { 0 , 1 , 2 } → N ,   f ( x ) = x + 1 f: \{0,1 , 2\}\to \N,\ f(x) = x + 1 f:{0,1,2}→N, f(x)=x+1 ， g : N → N ,   g ( x ) = 3 x + 2 g: \N \to \N,\ g(x) = 3x+2 g:N→N, g(x)=3x+2 ，求 g ⋄ f g\diamond f g⋄f 和 f ⋄ g f\diamond g f⋄g 。 解：显然， g ⋄ f ( x ) = g ( f ( x ) ) = g ( x + 1 ) = 3 ( x + 1 ) + 2 = 3 x + 5 g\diamond f(x) = g(f(x)) = g(x+1) = 3(x + 1) + 2 = 3x + 5 g⋄f(x)=g(f(x))=g(x+1)=3(x+1)+2=3x+5 ， f ⋄ g f\diamond g f⋄g 无定义。

与二元关系一样，函数的复合运算也不满足交换律，即 g ⋄ f ≠ f ⋄ g g\diamond f \ne f\diamond g g⋄f​=f⋄g ，但满足结合律，有 h ⋄ ( g ⋄ f ) = ( h ⋄ g ) ⋄ f h \diamond (g \diamond f) = (h \diamond g)\diamond f h⋄(g⋄f)=(h⋄g)⋄f ，具体定理和证明见下。

定理4.4.2 设 f : X → Y ,   g : Y → Z ,   h : Z → W f: X\to Y,\ g: Y \to Z,\ h: Z \to W f:X→Y, g:Y→Z, h:Z→W 是函数，则有 h ⋄ ( g ⋄ f ) = ( h ⋄ g ) ⋄ f h\diamond (g \diamond f) = (h\diamond g) \diamond f h⋄(g⋄f)=(h⋄g)⋄f 证明 由于关系的复合运算满足结合律，因此函数的复合运算也满足结合律，证明留作练习。也可直接由函数相等的定义来证明——因为 h ⋄ ( g ⋄ f ) ,   ( h ⋄ g ) ⋄ f h\diamond (g \diamond f),\ (h\diamond g) \diamond f h⋄(g⋄f), (h⋄g)⋄f 都是从 X X X 到 W W W 的函数，所以对任一 x ∈ X x \in X x∈X ，可知： h ⋄ ( g ⋄ f ) ( x ) = h ( g ⋄ f ( x ) ) = h ( g ( f ( x ) ) = ( h ⋄ g ) ( f ( x ) ) = ( h ⋄ g ) ⋄ f ( x ) h\diamond (g\diamond f)(x) = h(g\diamond f(x)) = h(g(f(x)) = (h \diamond g)(f(x)) = (h\diamond g)\diamond f(x) h⋄(g⋄f)(x)=h(g⋄f(x))=h(g(f(x))=(h⋄g)(f(x))=(h⋄g)⋄f(x) 由于元素 x x x 的任意性，有 h ⋄ ( g ⋄ f ) = ( h ⋄ g ) ⋄ f h\diamond (g \diamond f) = (h\diamond g) \diamond f h⋄(g⋄f)=(h⋄g)⋄f 。

有了函数的复合运算，现在可以定义函数的幂次。设 f : X → X f : X\to X f:X→X ，有： （1） f 0 = I X f^0 = I_X f0=IX​ . （2） f n + 1 = f ⋄ f n f^{n+1} = f\diamond f^n fn+1=f⋄fn .

定理4.4.3 设 f : X → Y ,   g : Y → Z f : X\to Y,\ g: Y\to Z f:X→Y, g:Y→Z 是函数， g ⋄ f g\diamond f g⋄f 是 f f f 与 g g g 的复合函数。 （1）若 f f f 和 g g g 都是满射的，则 g ⋄ f g\diamond f g⋄f 是满射的。 （2）若 f f f 和 g g g 都是单射的，则 g ⋄ f g\diamond f g⋄f 是单射的。 （3）若 f f f 和 g g g 都是双射的，则 g ⋄ f g\diamond f g⋄f 是双射的。 证明 g ⋄ f g\diamond f g⋄f 是从 X X X 到 Z Z Z 的函数。 （1）任取 z ∈ Z z \in Z z∈Z ，因为 g g g 是满射的，所以存在 y ∈ Y y \in Y y∈Y 使得 g ( y ) = z g(y) = z g(y)=z 。又因为 f f f 是满射的，所以存在 x ∈ X x\in X x∈X 使得 f ( x ) = y f(x) = y f(x)=y 。因此有 g ⋄ f ( x ) = g ( f ( x ) ) = g ( y ) = z g\diamond f(x) = g(f(x)) = g(y) = z g⋄f(x)=g(f(x))=g(y)=z ，即 z z z 在 X X X 中存在原像 x x x ，故 g ⋄ f g\diamond f g⋄f 是满射的。 （2）任取 x 1 , x 2 ∈ X x_1, x_2 \in X x1​,x2​∈X ，设 x 1 ≠ x 2 x_1 \ne x_2 x1​​=x2​ ，因为 f f f 是单射的，所以 f ( x 1 ) ≠ f ( x 2 ) f(x_1) \ne f(x_2) f(x1​)​=f(x2​) 。又因为 g g g 是单射的，所以有 g ( f ( x 1 ) ) ≠ g ( f ( x 2 ) ) g(f(x_1)) \ne g(f(x_2)) g(f(x1​))​=g(f(x2​)) ，于是有 g ⋄ f ( x 1 ) ≠ g ⋄ f ( x 2 ) g\diamond f(x_1) \ne g\diamond f(x_2) g⋄f(x1​)​=g⋄f(x2​) ，故 g ⋄ f g\diamond f g⋄f 是单射的。 （3）由(1)、(2)直接得出。

定理4.4.4 设 f : X → Y ,   g : Y → Z f: X\to Y,\ g: Y\to Z f:X→Y, g:Y→Z 是函数， g ⋄ f g\diamond f g⋄f 是 f f f 与 g g g 的复合函数。 （1）若 g ⋄ f g\diamond f g⋄f 是满射的，则 g g g 是满射的。 （2）若 g ⋄ f g\diamond f g⋄f 是单射的，则 f f f 是单射的。 （3）若 g ⋄ f g\diamond f g⋄f 是双射的，则 g g g 是满射的且 f f f 是单射的。 证明 （1）若 g ⋄ f g\diamond f g⋄f 是满射的，则任取 z ∈ Z z\in Z z∈Z ，存在 x ∈ X x\in X x∈X 使得 g ⋄ f ( x ) = z g\diamond f(x) = z g⋄f(x)=z ，即 g ( f ( x ) ) = z g(f(x))= z g(f(x))=z 。设 f ( x ) = y ∈ Y f(x) = y \in Y f(x)=y∈Y ，因此存在 y y y 使得 g ( y ) = z g(y) = z g(y)=z 。由于 z z z 是任意的，所以 g g g 是满射的。 （2）若 g ⋄ f g \diamond f g⋄f 是单射的，则任取 x 1 , x 2 ∈ X x_1, x_2 \in X x1​,x2​∈X ，设 x 1 ≠ x 2 x_1 \ne x_2 x1​​=x2​ ，则 g ⋄ f ( x 1 ) ≠ g ⋄ f ( x 2 ) g\diamond f(x_1) \ne g\diamond f(x_2) g⋄f(x1​)​=g⋄f(x2​) ，即 g ( f ( x 1 ) ≠ g ( f ( x 2 ) ) g(f(x_1) \ne g(f(x_2)) g(f(x1​)​=g(f(x2​)) 。又设 f ( x 1 ) = y 1 ∈ Y ,   f ( x 2 ) = y 2 ∈ Y f(x_1) = y_1 \in Y,\ f(x_2) = y_2 \in Y f(x1​)=y1​∈Y, f(x2​)=y2​∈Y ，所以有 g ( y 1 ) ≠ g ( y 2 ) g(y_1) \ne g(y_2) g(y1​)​=g(y2​) 。由函数定义可知，显然 y 1 ≠ y 2 y_1 \ne y_2 y1​​=y2​ ，即 f ( x 1 ) ≠ f ( x 2 ) f(x_1) \ne f(x_2) f(x1​)​=f(x2​) 。由于 x 1 , x 2   ( x 1 ≠ x 2 ) x_1, x_2\ (x_1 \ne x_2) x1​,x2​ (x1​​=x2​) 是任意的，所以 f f f 是单射的。

（或者用反证法） g ⋄ f g \diamond f g⋄f 是单射的，假设 f f f 不是单射的，则存在 x 1 , x 2 ∈ X ,   x 1 ≠ x 2 x_1, x_2 \in X, \ x_1 \ne x_2 x1​,x2​∈X, x1​​=x2​ 且 f ( x 1 ) = f ( x 2 ) f(x_1) = f(x_2) f(x1​)=f(x2​) 。又因为 g g g 是函数，所以存在 z z z 使得 g ( f ( x 1 ) = g ( f ( x 2 ) ) = z g(f(x_1) = g(f(x_2)) = z g(f(x1​)=g(f(x2​))=z ，即 g ⋄ f ( x 1 ) = g ⋄ f ( x 2 ) = z g\diamond f(x_1) = g\diamond f(x_2) = z g⋄f(x1​)=g⋄f(x2​)=z 。这与 g ⋄ f g\diamond f g⋄f 是单射的前提相矛盾。所以 f f f 是单射的。

（3）可由(1)、(2)直接得出。

【例4】设 f : X → Y f:X\to Y f:X→Y 和 g : Y → Z g: Y\to Z g:Y→Z 是函数，已知 f f f 和 g g g 的复合函数 g ⋄ f g\diamond f g⋄f 是一个单射函数。 （a）证明：若 f f f 是满射的，则 g g g 是单射的。 （b）若 f f f 不是满射的， g g g 一定是单射的吗？证明你的结论。 证明： （a）假设 g g g 不是一个单射函数，如下图所示，则存在 y 1 , y 2 ∈ Y , y 1 ≠ y 2 y_1, y_2 \in Y, y_1\ne y_2 y1​,y2​∈Y,y1​​=y2​ 且 g ( y 1 ) = g ( y 2 ) g(y_1) = g(y_2) g(y1​)=g(y2​) 。因为 f f f 是满射的，对于 y 1 , y 2 y_1, y_2 y1​,y2​ 必存在 x 1 , x 2 x_1, x_2 x1​,x2​ ，使得 f ( x 1 ) = y 1 ,   f ( x 2 ) = y 2 f(x_1) = y_1,\ f(x_2) = y_2 f(x1​)=y1​, f(x2​)=y2​ 。因为 f f f 是函数，所以当 f ( x 1 ) ≠ f ( x 2 ) f(x_1) \ne f(x_2) f(x1​)​=f(x2​) 时 x 1 ≠ x 2 x_1 \ne x_2 x1​​=x2​ 。现在考虑 x 1 , x 2 x_1, x_2 x1​,x2​ 在复合函数 g ⋄ f g\diamond f g⋄f 下的值： g ⋄ f ( x 1 ) = g ( f ( x 1 ) ) = g ( y 1 ) = g ( y 2 ) = g ( f ( x 2 ) ) = g ⋄ f ( x 2 ) g\diamond f(x_1) = g(f(x_1)) = g(y_1) = g(y_2) = g(f(x_2)) = g\diamond f(x_2) g⋄f(x1​)=g(f(x1​))=g(y1​)=g(y2​)=g(f(x2​))=g⋄f(x2​)

这与 g ⋄ f g\diamond f g⋄f 是单射函数矛盾，故 g g g 是单射的。 （b）若 f f f 不是满射的，则 g g g 不一定是单射的。例如，定义函数映射 f : R + → R ,   f ( x ) = x f: \R^+ \to \R,\ f(x) = x f:R+→R, f(x)=x 和 g : R → R ,   g ( x ) = x 2 g: \R\to \R,\ g(x) = x^2 g:R→R, g(x)=x2 ，则 g ⋄ f g\diamond f g⋄f 是单射的， f f f 不是满射的，但 g g g 不是单射的。

任何一个二元关系都有逆关系，但一个函数的逆关系不一定是一个函数，只有双射函数才有逆函数。

定义4.4.2 设 f : X → Y f: X\to Y f:X→Y 是一个双射函数，称 f f f 的逆关系 f − 1 = { ⟨ y , x ⟩ ∣ ⟨ x , y ⟩ ∈ f } f^{-1} = \{ \langle y, x\rangle \mid \langle x, y\rangle \in f\} f−1={⟨y,x⟩∣⟨x,y⟩∈f} 为 f f f 的逆函数 inverse function 。

不难证明，逆函数是函数，并且是双射函数。

【例5】设 A = { 1 , 2 , 3 } ,   B = { a , b , c } A = \{1, 2, 3\}, \ B = \{a, b, c\} A={1,2,3}, B={a,b,c} ， f : A → B f: A\to B f:A→B 是映射， f = { ⟨ 1 , a ⟩ , ⟨ 2 , c ⟩ , ⟨ 3 , b ⟩ } f = \{ \langle 1, a\rangle, \langle 2, c\rangle, \langle 3, b\rangle \} f={⟨1,a⟩,⟨2,c⟩,⟨3,b⟩} ，求 f − 1 f^{-1} f−1 。 解： f − 1 = { ⟨ a , 1 , ⟩ , ⟨ c , 2 ⟩ , ⟨ b , 3 ⟩ } f^{-1} = \{ \langle a, 1, \rangle, \langle c, 2\rangle , \langle b, 3\rangle \} f−1={⟨a,1,⟩,⟨c,2⟩,⟨b,3⟩} 。

定义4.4.3 设 f : X → Y f : X\to Y f:X→Y 是一个函数， Y ′ ⊆ Y Y' \subseteq Y Y′⊆Y ，那么称 f − 1 ( Y ′ ) = { x ∣ f ( x ) ∈ Y ′ } f^{-1}(Y')= \{ x \mid f(x) \in Y'\} f−1(Y′)={x∣f(x)∈Y′} 为 f f f 下 Y ′ Y' Y′ 的逆像或前像。

定理4.4.5 设双射函数 f : X → Y f: X \to Y f:X→Y ， f − 1 f^{-1} f−1 是 f f f 的逆函数，则有： （1） ( f − 1 ) − 1 = f (f^{-1})^{-1} = f (f−1)−1=f （2） f − 1 ⋄ f = I X f^{-1} \diamond f = I_X f−1⋄f=IX​ （3） f ⋄ f − 1 = I Y f \diamond f^{-1} = I_Y f⋄f−1=IY​ 证明留作练习。

定理4.4.6 若 f : X → Y ,   g : Y → Z f: X\to Y, \ g: Y\to Z f:X→Y, g:Y→Z 均为双射函数，则有： ( g ⋄ f ) − 1 = f − 1 ⋄ g − 1 (g\diamond f)^{-1} = f^{-1} \diamond g^{-1} (g⋄f)−1=f−1⋄g−1 证明（？） （1）因为 f : X → Y f: X\to Y f:X→Y 和 g : Y → Z g: Y\to Z g:Y→Z 为双射函数，所以 f − 1 : Y → X ,   g − 1 : Z → Y f^{-1} : Y\to X,\ g^{-1} : Z\to Y f−1:Y→X, g−1:Z→Y 也是双射函数，因此 f − 1 ⋄ g − 1 f^{-1} \diamond g^{-1} f−1⋄g−1 是从 Z Z Z 到 X X X 的双射函数。因为 g ⋄ f g\diamond f g⋄f 是从 X X X 到 Z Z Z 的双射函数，所以 ( g ⋄ f ) − 1 (g \diamond f)^{-1} (g⋄f)−1 是从 Z Z Z 到 X X X 的双射函数。 （2）任取 z ∈ Z z \in Z z∈Z ，存在唯一 y ∈ Y y \in Y y∈Y ，使得 g ( y ) = z g(y)= z g(y)=z ；对于 y ∈ Y y \in Y y∈Y ，存在唯一 x ∈ X x\in X x∈X ，使得 f ( x ) = y f(x) = y f(x)=y 。所以 ( f − 1 ⋄ g − 1 ) ( z ) = f − 1 ( g − 1 ( z ) ) = f − 1 ( y ) = x (f^{-1} \diamond g^{-1}) (z) = f^{-1} ( g^{-1} (z)) = f^{-1} (y) = x (f−1⋄g−1)(z)=f−1(g−1(z))=f−1(y)=x 。而 ( g ⋄ f ) ( x ) = g ( f ( x ) ) = g ( y ) = z (g \diamond f) (x) = g(f(x)) = g(y) = z (g⋄f)(x)=g(f(x))=g(y)=z ，故 ( g ⋄ f ) − 1 ( z ) = x (g\diamond f)^{-1} (z) = x (g⋄f)−1(z)=x 。因此对任一 z ∈ Z z \in Z z∈Z ，有 ( g ⋄ f ) − 1 ( z ) = ( f − 1 ⋄ g − 1 ) ( z ) (g \diamond f)^{-1} (z)= (f^{-1} \diamond g^{-1})(z) (g⋄f)−1(z)=(f−1⋄g−1)(z) 。 由(1)、(2)可知， ( g ⋄ f ) − 1 = f − 1 ⋄ g − 1 (g\diamond f)^{-1} = f^{-1}\diamond g^{-1} (g⋄f)−1=f−1⋄g−1 。