離散數學 - 函式

一個函式將集合中的每個元素精確地對映到相關集合中的一個元素。函式在演算法的計算複雜度表示、物件計數、序列和字串的研究等多個領域都有應用，僅舉幾例。本部分的第三章也是最後一章重點介紹了函式的重要方面。

函式 - 定義

函式或對映（定義為 $f: X \rightarrow Y$）是從未空集合 X 的元素到另一個非空集合 Y 的元素的關係。X 稱為函式 ‘f’ 的定義域，Y 稱為函式 ‘f’ 的陪域。

函式 ‘f’ 是 X 和 Y 上的關係，使得對於每個 $x \in X$，都存在唯一的 $y \in Y$ 使得 $(x,y) \in R$。‘x’ 稱為函式 f 的原像，‘y’ 稱為函式 f 的像。

函式可以是一對一或多對一，但不能是一對多。

如果對於每個 $b \in B$，最多存在一個 $a \in A$ 使得 $f(s) = t$，則函式 $f: A \rightarrow B$ 是單射或一對一函式。

這意味著如果 $a_1 \ne a_2$ 則 $f(a1) \ne f(a2)$，則函式 f 是單射的。

如果函式 f 的像等於其值域，則函式 $f: A \rightarrow B$ 是滿射（上對映）的。等價地，對於每個 $b \in B$，都存在某個 $a \in A$ 使得 $f(a) = b$。這意味著對於 B 中的任何 y，都存在 A 中的某個 x 使得 $y = f(x)$。

當且僅當 f 既是單射又是滿射時，函式 $f: A \rightarrow B$ 是雙射或一一對應的。

證明由 $f(x) = 2x – 3$ 定義的函式 $f: R \rightarrow R$ 是雙射函式。

解釋 − 我們必須證明這個函式既是單射又是滿射。

如果 $f(x_1) = f(x_2)$，則 $2x_1 – 3 = 2x_2 – 3$，這意味著 $x_1 = x_2$。

因此，f 是單射的。

這裡，$2x – 3= y$

所以，$x = (y+3)/2$ 屬於 R 且 $f(x) = y$。

因此，f 是滿射的。

由於 f 既是滿射又是單射，所以我們可以說 f 是雙射的。

一一對應函式 $f : A \rightarrow B$ 的反函式是函式 $g : B \rightarrow A$，它具有以下性質：

$f(x) = y \Leftrightarrow g(y) = x$

如果存在反函式 g，則函式 f 稱為可逆的。

函式 $f : Z \rightarrow Z, f(x)=x+5$ 是可逆的，因為它具有反函式 $ g : Z \rightarrow Z, g(x)= x-5$。
函式 $f : Z \rightarrow Z, f(x)=x^2$ 不是可逆的，因為它不是一對一的，因為 $(-x)^2=x^2$。

兩個函式 $f: A \rightarrow B$ 和 $g: B \rightarrow C$ 可以複合得到一個複合函式 $g o f$。這是一個從 A 到 C 的函式，定義為 $(gof)(x) = g(f(x))$

設 $f(x) = x + 2$ 且 $g(x) = 2x + 1$，求 $( f o g)(x)$ 和 $( g o f)(x)$。

$(f o g)(x) = f (g(x)) = f(2x + 1) = 2x + 1 + 2 = 2x + 3$

$(g o f)(x) = g (f(x)) = g(x + 2) = 2 (x+2) + 1 = 2x + 5$

因此，$(f o g)(x) \neq (g o f)(x)$

列印頁面