离散数学 - 函数

一个函数将集合中的每个元素精确地映射到相关集合中的一个元素。函数在算法的计算复杂度表示、对象计数、序列和字符串的研究等多个领域都有应用，仅举几例。本部分的第三章也是最后一章重点介绍了函数的重要方面。

函数 - 定义

函数或映射（定义为 $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)$

打印页面