函数与关系

函数和关系是连接抽象数学与具体应用的重要桥梁。函数描述输入到输出的映射关系，关系则描述对象之间更一般的联系。在计算机科学中，函数是程序设计的基本概念，关系则是数据库理论、程序验证、人工智能等领域的基础工具。

函数的基本概念

函数的定义

函数（Function）是一种特殊的二元关系，它将一个集合中的每个元素唯一地映射到另一个集合中的元素。

设 $X$ 和 $Y$ 是两个集合，函数 $f: X \to Y$ 是一个规则，对于 $X$ 中的每个元素 $x$，都存在 $Y$ 中唯一确定的元素 $y$ 与之对应。记作 $f(x) = y$ 或 $x \mapsto y$。

三个核心概念：

• 定义域（Domain）：集合 $X$，即函数的输入集合
• 陪域（Codomain）：集合 $Y$，即函数可能输出的集合
• 值域（Range/Image）：函数实际输出的集合，即 $\{f(x) \mid x \in X\} \subseteq Y$

很多人容易混淆陪域和值域。陪域是函数定义时声明的输出集合，而值域是函数实际能取到的输出值的集合。值域是陪域的子集。

函数的形式化定义

在集合论中，函数可以形式化定义为满足特定条件的二元关系。

函数 $f: X \to Y$ 是笛卡尔积 $X \times Y$ 的一个子集，满足：

1. 存在性：对于每个 $x \in X$，存在 $y \in Y$ 使得 $(x, y) \in f$
2. 唯一性：如果 $(x, y_1) \in f$ 且 $(x, y_2) \in f$，则 $y_1 = y_2$

这个定义揭示了函数的本质：函数是一个有序对的集合，每个输入对应唯一的输出。

# Python 中的函数定义
def square(x):
    return x ** 2

# 函数可以看作是有序对的集合
# square = {(0, 0), (1, 1), (2, 4), (3, 9), ...}

函数的表示方法

解析式：用数学表达式描述函数，如 $f(x) = x^2 + 1$

列表法：列出定义域中每个元素及其对应的函数值。适用于定义域有限的情况。

$x$	1	2	3	4	5
$f(x)$	2	5	10	17	26

图像法：在坐标系中绘制函数图像。适用于实数域上的函数。

多元函数

多元函数是接受多个参数的函数。形式上，$f: X_1 \times X_2 \times \cdots \times X_n \to Y$ 是一个从笛卡尔积到 $Y$ 的函数。

例如，加法函数 $+: \mathbb{R} \times \mathbb{R} \to \mathbb{R}$ 接受两个实数，输出它们的和。

# 多元函数
def distance(x, y):
    return (x**2 + y**2) ** 0.5

部分函数与全函数

全函数（Total Function）：定义域中每个元素都有对应的函数值。通常所说的"函数"默认指全函数。

部分函数（Partial Function）：并非定义域中所有元素都有定义。例如，$f(x) = 1/x$ 在 $x = 0$ 处无定义。

在编程中，部分函数很常见。除法运算在除数为零时无定义，数组访问在索引越界时无定义。

# 部分函数示例：除法
def divide(a, b):
    if b == 0:
        raise ValueError("Division by zero")  # 在 b=0 处无定义
    return a / b

函数的类型

根据函数的不同性质，可以将函数分为几种重要类型。

单射（Injective Function）

单射函数保证不同的输入产生不同的输出。如果 $f(x_1) = f(x_2)$，则必有 $x_1 = x_2$。等价地说，如果 $x_1 \neq x_2$，则 $f(x_1) \neq f(x_2)$。

单射也称为"一对一"映射或内射。

判断方法：检查陪域中的每个元素是否至多有一个原像。

# 单射函数示例：f(x) = 2x + 1
def f(x):
    return 2 * x + 1
# 不同的 x 永远产生不同的 f(x)

# 非单射函数示例：f(x) = x^2
def g(x):
    return x ** 2
# g(2) = g(-2) = 4，不是单射

直观理解：想象一个电影院，如果每个座位最多坐一个人（可以有空座），这就是单射。观众到座位的映射是单射。

满射（Surjective Function）

满射函数保证陪域中的每个元素都是某个输入的输出。对于陪域 $Y$ 中的每个元素 $y$，都存在定义域 $X$ 中的元素 $x$ 使得 $f(x) = y$。

满射也称为"映上"映射。

判断方法：检查值域是否等于陪域。

# 满射函数示例：f(x) = x mod 3，定义域为 Z，陪域为 {0, 1, 2}
def mod3(x):
    return x % 3
# {0, 1, 2} 中的每个值都能被取到

# 非满射函数示例：f(x) = x^2，定义域和陪域都是 R
# 负数永远不是平方值，所以不是满射

直观理解：继续电影院比喻，如果每个座位都有人坐（没有空座），这就是满射。观众到座位的映射是满射（假设观众数等于座位数）。

双射（Bijective Function）

双射函数同时是单射和满射。陪域中的每个元素恰好有一个原像。

双射也称为"一一对应"映射。

判断方法：检查是否同时满足单射和满射的条件。

# 双射函数示例：f(x) = 2x，定义域和陪域都是 R
def double(x):
    return 2 * x
# 不同的 x 产生不同的值（单射）
# 任何实数 y 都有原像 y/2（满射）

# 另一个双射示例：将 {0, 1, 2, 3} 映射到 {a, b, c, d}
mapping = {0: 'a', 1: 'b', 2: 'c', 3: 'd'}

直观理解：电影院恰好坐满，每个座位一个人，一个人一个座位。观众到座位的映射是双射。

三种函数类型的关系

双射是最"完美"的函数，它在定义域和陪域之间建立了一一对应关系。

函数的运算

函数的复合

设有两个函数 $f: X \to Y$ 和 $g: Y \to Z$，它们的复合函数 $g \circ f: X \to Z$ 定义为：

$(g \circ f)(x) = g(f(x))$

注意：复合的顺序是从右到左读的。先应用 $f$，再应用 $g$。

def f(x):
    return x + 1

def g(x):
    return x * 2

# 复合函数 g ∘ f
def compose_g_f(x):
    return g(f(x))  # 先 +1，再 *2

# 测试
print(compose_g_f(3))  # (3+1)*2 = 8

# 复合函数 f ∘ g
def compose_f_g(x):
    return f(g(x))  # 先 *2，再 +1

print(compose_f_g(3))  # (3*2)+1 = 7

复合运算满足结合律：$(h \circ g) \circ f = h \circ (g \circ f)$。但不满足交换律：$g \circ f$ 和 $f \circ g$ 通常不相等。

恒等函数

集合 $X$ 上的恒等函数 $id_X: X \to X$ 定义为 $id_X(x) = x$。

恒等函数在函数复合中扮演类似于数字 1 在乘法中的角色：

$f \circ id_X = f = id_Y \circ f$

反函数

如果函数 $f: X \to Y$ 是双射，则存在反函数 $f^{-1}: Y \to X$，满足：

$f^{-1}(f(x)) = x, \quad f(f^{-1}(y)) = y$

只有双射函数才有反函数。单射函数可以定义部分反函数（定义域为原函数的值域）。

# 双射函数及其反函数
def f(x):
    return 2 * x + 3

def f_inverse(y):
    return (y - 3) / 2

# 验证
print(f(f_inverse(7)))    # 7
print(f_inverse(f(5)))    # 5

反函数的性质：

• $(f^{-1})^{-1} = f$
• $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$

关系的基本概念

关系的定义

关系（Relation）描述集合元素之间的联系。设 $X$ 和 $Y$ 是两个集合，从 $X$ 到 $Y$ 的二元关系 $R$ 是笛卡尔积 $X \times Y$ 的一个子集。

如果 $(x, y) \in R$，记作 $xRy$，读作"$x$ 与 $y$ 有关系 $R$"。

当 $X = Y$ 时，$R$ 称为 $X$ 上的二元关系。

# 关系的表示：用有序对的集合
# "小于"关系在 {1, 2, 3} 上
less_than = {(1, 2), (1, 3), (2, 3)}

# 检查关系
print((1, 2) in less_than)  # True
print((2, 1) in less_than)  # False

关系的表示方法

集合表示法：列出所有相关的有序对。如 $R = \{(1, 2), (2, 3), (3, 4)\}$

关系矩阵：用矩阵表示关系。如果 $|X| = m$，$|Y| = n$，则关系矩阵 $M$ 是 $m \times n$ 矩阵，$M_{ij} = 1$ 当且仅当 $(x_i, y_j) \in R$。

例如，设 $X = \{a, b\}$，$Y = \{1, 2, 3\}$，$R = \{(a, 1), (a, 3), (b, 2)\}$：

$M_R = \begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix}$

关系图：用有向图表示关系。顶点表示元素，有向边表示关系。

关系的性质

设 $R$ 是集合 $X$ 上的二元关系。

自反性（Reflexivity）：对于所有 $x \in X$，有 $xRx$。

例如，"等于"关系、"整除"关系（在正整数上）都是自反的。"小于"关系不是自反的。

对称性（Symmetry）：如果 $xRy$，则 $yRx$。

例如，"等于"关系、"同学"关系是对称的。"小于"关系不是对称的。

反对称性（Antisymmetry）：如果 $xRy$ 且 $yRx$，则 $x = y$。

例如，"小于等于"关系、"子集"关系是反对称的。"同学"关系不是反对称的（两个人可以互为同学但不相等）。

注意：对称性和反对称性不是互斥的。一个关系可以同时满足两者（如"等于"关系），也可以都不满足。

传递性（Transitivity）：如果 $xRy$ 且 $yRz$，则 $xRz$。

例如，"小于"关系、"祖先"关系是传递的。"同学"关系通常不是传递的。

# 检查关系的性质
def check_reflexive(relation, elements):
    """检查自反性"""
    for x in elements:
        if (x, x) not in relation:
            return False
    return True

def check_symmetric(relation):
    """检查对称性"""
    for (x, y) in relation:
        if (y, x) not in relation:
            return False
    return True

def check_antisymmetric(relation):
    """检查反对称性"""
    for (x, y) in relation:
        if x != y and (y, x) in relation:
            return False
    return True

def check_transitive(relation):
    """检查传递性"""
    for (x, y) in relation:
        for (a, b) in relation:
            if y == a and (x, b) not in relation:
                return False
    return True

关系的运算

逆关系：$R^{-1} = \{(y, x) \mid (x, y) \in R\}$

关系的复合：设 $R \subseteq X \times Y$，$S \subseteq Y \times Z$，则 $S \circ R = \{(x, z) \mid \exists y \in Y, (x, y) \in R \land (y, z) \in S\}$

# 关系复合
def compose_relations(R, S):
    """计算 S ∘ R"""
    result = set()
    for (x, y) in R:
        for (a, b) in S:
            if y == a:
                result.add((x, b))
    return result

等价关系

等价关系是一类重要的二元关系，它在数学和计算机科学中有着广泛应用。

等价关系的定义

集合 $X$ 上的关系 $R$ 称为等价关系，当且仅当 $R$ 满足：

1. 自反性：对于所有 $x \in X$，$xRx$
2. 对称性：如果 $xRy$，则 $yRx$
3. 传递性：如果 $xRy$ 且 $yRz$，则 $xRz$

等价关系通常用符号 $\sim$ 或 $\equiv$ 表示。

等价关系的例子

等于关系：$=$ 是任何集合上的等价关系。

模 n 同余：在整数集 $\mathbb{Z}$ 上，定义 $a \equiv b \pmod{n}$ 当且仅当 $n | (a - b)$。这是等价关系。

验证三个性质：

• 自反性：$n | (a - a) = 0$，成立
• 对称性：若 $n | (a - b)$，则 $n | (b - a)$，成立
• 传递性：若 $n | (a - b)$ 且 $n | (b - c)$，则 $n | (a - c)$，成立

相似关系：三角形集合上的"相似"关系是等价关系。

同一天生日：人集合上的"同一天生日"关系是等价关系。

等价类

设 $\sim$ 是集合 $X$ 上的等价关系，元素 $x$ 的等价类是所有与 $x$ 等价的元素组成的集合：

$[x] = \{y \in X \mid y \sim x\}$

$x$ 称为等价类的代表元。

等价类的性质：

1. $x \in [x]$（自反性保证）
2. 如果 $y \in [x]$，则 $[y] = [x]$（等价类由其中任意元素唯一确定）
3. 如果 $y \notin [x]$，则 $[y] \cap [x] = \emptyset$（不同等价类不相交）

# 模 3 同余的等价类
def mod3_equivalence_class(n):
    """返回 n 所在的等价类"""
    return [x for x in range(10) if x % 3 == n % 3]

print(mod3_equivalence_class(0))  # [0, 3, 6, 9]
print(mod3_equivalence_class(1))  # [1, 4, 7]
print(mod3_equivalence_class(2))  # [2, 5, 8]

商集

集合 $X$ 关于等价关系 $\sim$ 的商集是所有等价类组成的集合，记作 $X/\sim$：

$X/\sim = \{[x] \mid x \in X\}$

商集是原集合的一种"压缩"或"折叠"——将等价的元素视为同一个。

例如，$\mathbb{Z}/\equiv_3 = \{[0], [1], [2]\}$，其中 $[0] = \{3k \mid k \in \mathbb{Z}\}$，$[1] = \{3k+1 \mid k \in \mathbb{Z}\}$，$[2] = \{3k+2 \mid k \in \mathbb{Z}\}$。

等价关系与分划

等价关系与集合的分划之间存在一一对应关系。

定理：集合 $X$ 上的等价关系确定 $X$ 的一个分划；反之，$X$ 的一个分划确定 $X$ 上的一个等价关系。

这个定理揭示了等价关系的本质：等价关系就是对集合进行分类。每个等价类是一个"类别"，同类元素相互等价，不同类元素不等价。

应用示例：在并查集数据结构中，我们维护一个等价关系，支持动态合并等价类和查询两个元素是否等价。

偏序关系

偏序关系是另一类重要的二元关系，它为集合引入了"顺序"的概念。

偏序关系的定义

集合 $X$ 上的关系 $R$ 称为偏序关系（Partial Order），当且仅当 $R$ 满足：

1. 自反性：对于所有 $x \in X$，$xRx$
2. 反对称性：如果 $xRy$ 且 $yRx$，则 $x = y$
3. 传递性：如果 $xRy$ 且 $yRz$，则 $xRz$

偏序关系通常用符号 $\leq$ 或 $\preceq$ 表示。带有偏序关系的集合 $(X, \leq)$ 称为偏序集（Partially Ordered Set，简称 Poset）。

偏序关系的例子

小于等于：实数集上的 $\leq$ 是偏序关系。

整除关系：正整数集上的"整除"关系 $|$ 是偏序关系。$a|b$ 表示 $a$ 整除 $b$。

验证三个性质：

• 自反性：$a|a$，成立
• 反对称性：若 $a|b$ 且 $b|a$，则 $a = b$，成立
• 传递性：若 $a|b$ 且 $b|c$，则 $a|c$，成立

包含关系：集合 $A$ 的幂集 $\mathcal{P}(A)$ 上的包含关系 $\subseteq$ 是偏序关系。

字典序：字符串集合上的字典序是偏序关系。

全序与偏序

全序（Total Order）：偏序集 $(X, \leq)$ 是全序集，如果对于任意 $x, y \in X$，要么 $x \leq y$，要么 $y \leq x$。

全序要求任意两个元素都可以比较，而偏序允许存在不可比较的元素对。

例子对比：

• 实数集上的 $\leq$ 是全序：任意两个实数都可以比较大小
• 幂集上的 $\subseteq$ 是偏序但不是全序：$\{1, 2\}$ 和 $\{2, 3\}$ 互不包含
• 整除关系是偏序但不是全序：2 不整除 3，3 也不整除 2

哈斯图

哈斯图是偏序集的图形表示，它省略了由传递性和自反性隐含的边，只保留"覆盖关系"。

在哈斯图中：

• 较小的元素画在下方
• 如果 $x < y$ 且不存在 $z$ 使得 $x < z < y$，则在 $x$ 和 $y$ 之间画一条边

例如，集合 $\{1, 2, 3\}$ 的幂集按包含关系排序的哈斯图：

特殊元素

在偏序集 $(X, \leq)$ 中：

最大元和最小元：

• $a$ 是最大元，如果对所有 $x \in X$，都有 $x \leq a$
• $a$ 是最小元，如果对所有 $x \in X$，都有 $a \leq x$

最大元和最小元如果存在则唯一。

极大元和极小元：

• $a$ 是极大元，如果不存在 $x$ 使得 $a < x$
• $a$ 是极小元，如果不存在 $x$ 使得 $x < a$

极大元和极小元可能不唯一。

上界和下界： 设 $A \subseteq X$：

• $u$ 是 $A$ 的上界，如果对所有 $a \in A$，都有 $a \leq u$
• $l$ 是 $A$ 的下界，如果对所有 $a \in A$，都有 $l \leq a$

最小上界（上确界）和最大下界（下确界）：

• $A$ 的最小上界 $\sup(A)$ 是 $A$ 所有上界中的最小元
• $A$ 的最大下界 $\inf(A)$ 是 $A$ 所有下界中的最大元

格

格（Lattice）是一种特殊的偏序集，其中任意两个元素都有最小上界和最大下界。

设 $(L, \leq)$ 是偏序集，如果对于任意 $a, b \in L$：

• $a$ 和 $b$ 的最小上界存在，记作 $a \vee b$（称为"join"）
• $a$ 和 $b$ 的最大下界存在，记作 $a \wedge b$（称为"meet"）

则 $(L, \leq)$ 称为格。

例子：

• 幂集 $\mathcal{P}(S)$ 在包含关系下构成格：$A \vee B = A \cup B$，$A \wedge B = A \cap B$
• 正整数在整除关系下构成格：$a \vee b = \text{lcm}(a, b)$，$a \wedge b = \gcd(a, b)$

函数与关系在计算机科学中的应用

函数与关系是计算机科学中许多核心概念的数学基础。理解这些抽象概念的实际应用，能够帮助程序员设计更好的数据结构和算法。

函数在编程中的本质

在编程语言中，"函数"这个词的含义比数学中的函数更广泛。

纯函数（Pure Function）：完全对应数学中的函数概念。相同的输入总是产生相同的输出，没有副作用。

# 纯函数示例
def square(x):
    return x * x

# 无论调用多少次，square(5) 总是返回 25

非纯函数：可能有副作用，如修改全局状态、进行 I/O 操作等。

# 非纯函数（有副作用）
counter = 0
def increment():
    global counter
    counter += 1
    return counter

# 每次调用 increment() 返回不同的值

函数式编程强调使用纯函数，因为纯函数更容易推理、测试和并行化。理解数学函数的定义，有助于理解为什么函数式编程追求"无副作用"。

双射与加密算法

双射函数在密码学中有重要应用。一个好的加密函数应该是一个双射（在密钥确定的情况下），使得解密成为可能。

替换密码：将字母映射到另一个字母，是一个双射函数。

# 凯撒密码：字母表上的双射
def caesar_encrypt(text, shift):
    result = []
    for char in text:
        if char.isalpha():
            base = ord('A') if char.isupper() else ord('a')
            result.append(chr((ord(char) - base + shift) % 26 + base))
        else:
            result.append(char)
    return ''.join(result)

def caesar_decrypt(text, shift):
    return caesar_encrypt(text, -shift)  # 反函数

message = "HELLO"
encrypted = caesar_encrypt(message, 3)  # KHOOR
decrypted = caesar_decrypt(encrypted, 3)  # HELLO

为什么必须是双射：

• 单射：不同的明文加密成不同的密文，否则无法区分
• 满射：每个可能的密文都是某个明文加密得来，否则解密时会出现无效密文

散列函数的设计考量

散列函数 $h: K \to \{0, 1, \ldots, m-1\}$ 将任意键映射到有限的位置集合。

理想情况：散列函数应该"接近"满射，使得每个位置被均匀使用。

# 简单的散列函数
def hash_string(s, table_size):
    """字符串的散列函数"""
    total = sum(ord(c) for c in s)
    return total % table_size

# 好的散列函数特点：
# 1. 确定性：相同的键总是产生相同的散列值
# 2. 均匀分布：散列值均匀分布在地址空间
# 3. 高效计算：计算散列值的时间复杂度低

碰撞处理：由于定义域（所有可能的键）远大于值域（哈希表大小），碰撞不可避免。这从数学上说明散列函数不可能是单射。

等价关系与数据分类

等价关系在数据分类和去重中有广泛应用。

用户身份识别：确定两个账户是否属于同一用户是一个等价关系问题。

class UserIdentity:
    """用户身份识别系统"""
    def __init__(self):
        # 使用并查集维护等价关系
        self.parent = {}
    
    def find(self, x):
        """找到 x 所在等价类的代表"""
        if x not in self.parent:
            self.parent[x] = x
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        """合并两个等价类：声明 x 和 y 是同一用户"""
        px, py = self.find(x), self.find(y)
        if px != py:
            self.parent[px] = py
    
    def same_user(self, x, y):
        """判断 x 和 y 是否属于同一用户"""
        return self.find(x) == self.find(y)

# 使用示例
identity = UserIdentity()
identity.union("[email protected]", "[email protected]")  # 同一用户的两个邮箱
identity.union("[email protected]", "twitter_handle")  # 绑定社交账号
print(identity.same_user("[email protected]", "twitter_handle"))  # True

数据去重：定义"相同"的等价关系，然后从每个等价类中保留一个代表。

def deduplicate(records, key_func):
    """基于等价关系去重"""
    seen = {}
    for record in records:
        key = key_func(record)  # key 定义了等价关系
        if key not in seen:
            seen[key] = record
    return list(seen.values())

# 示例：按邮箱去重用户
users = [
    {"name": "Alice", "email": "[email protected]"},
    {"name": "Alice Smith", "email": "[email protected]"},  # 同一人
    {"name": "Bob", "email": "[email protected]"}
]
unique = deduplicate(users, lambda u: u["email"])

偏序关系与任务调度

偏序关系在任务调度、依赖管理中至关重要。

依赖关系是偏序关系：如果任务 A 依赖任务 B，B 依赖 C，则 A 也间接依赖 C（传递性）。任务不能直接或间接依赖自己（反对称性）。

class TaskScheduler:
    """基于偏序关系的任务调度器"""
    def __init__(self):
        self.tasks = set()
        self.dependencies = {}  # task -> set of tasks it depends on
    
    def add_task(self, task):
        self.tasks.add(task)
        if task not in self.dependencies:
            self.dependencies[task] = set()
    
    def add_dependency(self, task, depends_on):
        """添加依赖关系：task 依赖于 depends_on"""
        self.add_task(task)
        self.add_task(depends_on)
        self.dependencies[task].add(depends_on)
        
        # 检测环路（违反偏序的反对称性）
        if self._has_cycle():
            raise ValueError("检测到循环依赖")
    
    def _has_cycle(self):
        """检测是否有环"""
        visited = set()
        rec_stack = set()
        
        def dfs(task):
            visited.add(task)
            rec_stack.add(task)
            for dep in self.dependencies.get(task, set()):
                if dep not in visited:
                    if dfs(dep):
                        return True
                elif dep in rec_stack:
                    return True
            rec_stack.remove(task)
            return False
        
        return any(dfs(task) for task in self.tasks if task not in visited)
    
    def schedule(self):
        """拓扑排序，返回执行顺序"""
        in_degree = {t: 0 for t in self.tasks}
        for task in self.tasks:
            for dep in self.dependencies[task]:
                in_degree[dep] = in_degree.get(dep, 0)  # 被依赖者入度不减
        
        # 重新计算入度
        in_degree = {t: 0 for t in self.tasks}
        for task, deps in self.dependencies.items():
            for dep in deps:
                pass  # dep 被依赖，入度不应该增加
        
        # 正确计算：统计每个任务被多少任务依赖
        reverse_deps = {t: set() for t in self.tasks}
        for task, deps in self.dependencies.items():
            for dep in deps:
                reverse_deps[dep].add(task)
        
        in_degree = {t: len(reverse_deps[t]) for t in self.tasks}
        
        # Kahn 算法
        from collections import deque
        queue = deque([t for t in self.tasks if in_degree[t] == 0])
        result = []
        
        while queue:
            task = queue.popleft()
            result.append(task)
            for dependent in reverse_deps[task]:
                in_degree[dependent] -= 1
                if in_degree[dependent] == 0:
                    queue.append(dependent)
        
        return result if len(result) == len(self.tasks) else None

# 使用示例
scheduler = TaskScheduler()
scheduler.add_dependency("测试", "编码")
scheduler.add_dependency("部署", "测试")
scheduler.add_dependency("编码", "设计")
print(scheduler.schedule())  # ['设计', '编码', '测试', '部署']

格与信息检索

格结构在信息检索和分类系统中有应用。

文档分类格：文档可以按多个维度分类，这些分类形成一个格。

# 文档分类格
class DocumentLattice:
    """文档分类格"""
    def __init__(self):
        self.categories = {}
        self.documents = {}
    
    def add_category(self, cat, parent=None):
        """添加分类"""
        self.categories[cat] = {
            'parent': parent,
            'children': []
        }
        if parent and parent in self.categories:
            self.categories[parent]['children'].append(cat)
    
    def add_document(self, doc_id, categories):
        """将文档加入多个分类"""
        self.documents[doc_id] = categories
    
    def find_common_ancestor(self, cat1, cat2):
        """找两个分类的公共祖先（下确界）"""
        ancestors1 = self._get_ancestors(cat1)
        ancestors2 = self._get_ancestors(cat2)
        common = ancestors1 & ancestors2
        # 找最接近的公共祖先
        for cat in [cat1, cat2] + list(ancestors1):
            if cat in common:
                return cat
        return None
    
    def _get_ancestors(self, cat):
        ancestors = set()
        while cat:
            ancestors.add(cat)
            cat = self.categories.get(cat, {}).get('parent')
        return ancestors

数据库中的函数依赖

关系数据库理论中的函数依赖是函数概念在数据建模中的直接应用。

函数依赖定义：在关系 R 中，属性集 A 函数决定属性集 B，记作 $A \to B$，如果对于 R 的任意两个元组，若它们在 A 上的值相同，则在 B 上的值也相同。

def check_functional_dependency(relation, A, B):
    """检查函数依赖 A -> B 是否成立
    
    relation: 元组列表
    A, B: 属性名列表
    """
    seen = {}
    for tuple_data in relation:
        a_values = tuple(tuple_data[attr] for attr in A)
        b_values = tuple(tuple_data[attr] for attr in B)
        
        if a_values in seen:
            if seen[a_values] != b_values:
                return False  # 违反函数依赖
        else:
            seen[a_values] = b_values
    
    return True

# 示例
students = [
    {"student_id": 1, "name": "Alice", "department": "CS"},
    {"student_id": 2, "name": "Bob", "department": "Math"},
    {"student_id": 1, "name": "Alice", "department": "CS"},  # 重复记录
]

print(check_functional_dependency(students, ["student_id"], ["name"]))  # True
print(check_functional_dependency(students, ["department"], ["name"]))  # False

范式与函数依赖：数据库范式是关于函数依赖的约束：

• 第一范式：属性不可再分
• 第二范式：非主属性完全函数依赖于候选键
• 第三范式：非主属性不传递函数依赖于候选键

理解函数依赖，有助于设计规范的数据库模式，避免数据冗余和更新异常。

映射与数据转换

函数作为"映射"的概念在数据转换中随处可见。

ETL（抽取、转换、加载）：本质上是一系列函数的复合。

# ETL 管道：函数的复合
def extract(source):
    """从数据源抽取数据"""
    return source

def transform(data, mapping):
    """根据映射规则转换数据"""
    return [{mapping[k]: v for k, v in row.items()} for row in data]

def load(data, destination):
    """加载数据到目标"""
    destination.extend(data)
    return destination

# 复合函数
def etl_pipeline(source, mapping, destination):
    data = extract(source)
    data = transform(data, mapping)
    return load(data, destination)

小结

本章介绍了函数与关系的基础知识：

1. 函数：定义、定义域、陪域、值域；单射、满射、双射；复合与反函数
2. 关系：定义与表示；自反性、对称性、反对称性、传递性
3. 等价关系：定义、等价类、商集、与分划的对应
4. 偏序关系：定义、全序与偏序、哈斯图、特殊元素、格
5. 实际应用：纯函数、加密算法、散列函数、用户身份识别、任务调度、信息检索、数据库函数依赖、数据转换

函数是特殊的关系——每个输入对应唯一输出的关系。等价关系用于分类，偏序关系用于排序，它们在算法设计、数据结构、程序验证等领域都有重要应用。理解这些数学概念在编程中的具体体现，能够帮助程序员写出更正确、更高效的代码。

练习

1. 设 $f: \mathbb{R} \to \mathbb{R}$，$f(x) = x^2$。判断 $f$ 是否为单射、满射或双射。如果改变陪域为 $\mathbb{R}^+$（非负实数），结论有何变化？

2. 证明：如果 $f: X \to Y$ 是双射，则 $f$ 有唯一的反函数 $f^{-1}: Y \to X$。

3. 设关系 $R = \{(1,1), (1,2), (2,1), (2,2), (3,3)\}$ 在集合 $\{1, 2, 3\}$ 上。判断 $R$ 是否为等价关系。

4. 画出集合 $\{1, 2, 3, 4, 6, 12\}$ 在整除关系下的哈斯图，并找出所有极大元和极小元。

5. 证明：等价关系确定一个分划，分划确定一个等价关系。