第三十五 离散数学（Discrete Mathematics）

离散数学是研究离散量的结构及其相互关系的数学分支，与连续数学（如微积分）相对。它是计算机科学的理论基础，为算法设计、数据结构、数据库、编译原理、密码学等提供了核心数学工具。

一、集合论

1.1 基本概念

集合：一组确定的、互不相同的对象的全体。集合中的对象称为元素。

1.2 集合间的关系

1.3 集合运算

运算律：

$$A \cup B = B \cup A \quad \text{（交换律）}$$ $$A \cap (B \cup C) = (A \cap B) \cup (A \cap C) \quad \text{（分配律）}$$ $$\overline{A \cup B} = \bar{A} \cap \bar{B} \quad \text{（德摩根定律）}$$ $$\overline{A \cap B} = \bar{A} \cup \bar{B} \quad \text{（德摩根定律）}$$

use std::collections::{HashSet, BTreeSet};

fn main() {
    let a: HashSet<i32> = [1, 2, 3, 4].iter().cloned().collect();
    let b: HashSet<i32> = [3, 4, 5, 6].iter().cloned().collect();

    // 并集
    let union: BTreeSet<_> = a.union(&b).cloned().collect();
    println!("A ∪ B = {:?}", union);  // {1, 2, 3, 4, 5, 6}

    // 交集
    let intersection: BTreeSet<_> = a.intersection(&b).cloned().collect();
    println!("A ∩ B = {:?}", intersection);  // {3, 4}

    // 差集
    let difference: BTreeSet<_> = a.difference(&b).cloned().collect();
    println!("A - B = {:?}", difference);  // {1, 2}

    // 对称差
    let sym_diff: BTreeSet<_> = a.symmetric_difference(&b).cloned().collect();
    println!("A △ B = {:?}", sym_diff);  // {1, 2, 5, 6}
}

1.4 幂集

集合 $A$ 的幂集 $\mathcal{P}(A)$ 是 $A$ 的所有子集构成的集合。

$$|\mathcal{P}(A)| = 2^{|A|}$$

fn power_set<T: Clone>(set: &[T]) -> Vec<Vec<T>> {
    let n = set.len();
    let mut result = Vec::new();
    for mask in 0..(1u32 << n) {
        let mut subset = Vec::new();
        for i in 0..n {
            if (mask >> i) & 1 == 1 {
                subset.push(set[i].clone());
            }
        }
        result.push(subset);
    }
    result
}

fn main() {
    let set = vec![1, 2, 3];
    let ps = power_set(&set);
    println!("幂集（共 {} 个子集）:", ps.len());  // 8 = 2³
    for subset in &ps {
        println!("  {:?}", subset);
    }
}

二、图论

2.1 基本概念

图 $G = (V, E)$ 由顶点集 $V$ 和边集 $E$ 组成。

握手定理： 无向图中所有顶点的度数之和等于边数的两倍：

$$\sum_{v \in V} \deg(v) = 2|E|$$

2.2 七桥问题

七桥问题是图论的起源。欧拉证明了：一个图存在一笔画（欧拉路径）的充要条件是：恰好有 0 个或 2 个奇数度的顶点。

• 0 个奇数度顶点 → 欧拉回路（起点和终点相同）
• 2 个奇数度顶点 → 欧拉路径（起点和终点不同）
• 其他情况 → 不存在一笔画

2.3 图的存储与遍历

use std::collections::{HashMap, HashSet, VecDeque};

struct Graph {
    adj: HashMap<i32, Vec<i32>>,
}

impl Graph {
    fn new() -> Self { Graph { adj: HashMap::new() } }

    fn add_edge(&mut self, u: i32, v: i32) {
        self.adj.entry(u).or_default().push(v);
        self.adj.entry(v).or_default().push(u);
    }

    // BFS 求最短路径
    fn shortest_path(&self, start: i32, end: i32) -> Option<Vec<i32>> {
        let mut visited = HashSet::new();
        let mut queue = VecDeque::new();
        let mut parent: HashMap<i32, i32> = HashMap::new();

        visited.insert(start);
        queue.push_back(start);

        while let Some(node) = queue.pop_front() {
            if node == end {
                // 回溯路径
                let mut path = Vec::new();
                let mut current = end;
                while current != start {
                    path.push(current);
                    current = parent[&current];
                }
                path.push(start);
                path.reverse();
                return Some(path);
            }
            if let Some(neighbors) = self.adj.get(&node) {
                for &neighbor in neighbors {
                    if !visited.contains(&neighbor) {
                        visited.insert(neighbor);
                        parent.insert(neighbor, node);
                        queue.push_back(neighbor);
                    }
                }
            }
        }
        None
    }
}

fn main() {
    let mut g = Graph::new();
    g.add_edge(0, 1); g.add_edge(0, 2);
    g.add_edge(1, 3); g.add_edge(2, 3);
    g.add_edge(3, 4);

    if let Some(path) = g.shortest_path(0, 4) {
        println!("最短路径: {:?}", path);  // [0, 1, 3, 4] 或 [0, 2, 3, 4]
    }
}

2.4 图的应用

三、数理逻辑

3.1 命题与逻辑联结词

命题：可以判断真假的陈述句。

蕴含的真值表：

注意： $p \rightarrow q$ 等价于 $\neg p \lor q$。当前提为假时，蕴含式恒为真。

3.2 量词

量词的否定：

$$\neg(\forall x, P(x)) = \exists x, \neg P(x)$$

$$\neg(\exists x, P(x)) = \forall x, \neg P(x)$$

四、组合数学

4.1 加法原理与乘法原理

加法原理： 做一件事有 $n$ 类方法，第 $i$ 类有 $m_i$ 种方法，则总方法数为 $\sum m_i$。

乘法原理： 做一件事分 $n$ 步，第 $i$ 步有 $m_i$ 种方法，则总方法数为 $\prod m_i$。

4.2 排列与组合

$$P(n,m) = \frac{n!}{(n-m)!}$$

$$C(n,m) = \frac{n!}{m!(n-m)!}$$

4.3 鸽巢原理（抽屉原理）

将 $n+1$ 个物品放入 $n$ 个盒子中，至少有一个盒子包含至少 2 个物品。

推论： 367 人中至少两人生日相同（一年最多 366 天）。

4.4 容斥原理

$$|A \cup B| = |A| + |B| - |A \cap B|$$

$$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$$

五、关系

5.1 二元关系

从集合 $A$ 到集合 $B$ 的二元关系是 $A \times B$ 的子集。

5.2 关系的性质

5.3 等价关系

同时满足自反性、对称性、传递性的关系称为等价关系。

等价关系将集合划分为若干等价类，等价类的集合称为商集。

5.4 偏序关系

同时满足自反性、反对称性、传递性的关系称为偏序关系。

偏序关系可以用哈斯图（Hasse Diagram）直观表示。

六、代数结构

应用： 群论是 RSA、ECC 等密码算法的数学基础。有限域上的运算支撑着 AES、椭圆曲线等加密体系。

七、学习资源

八、总结

离散数学是计算机科学的数学语言。从数据结构到算法设计，从数据库到密码学，离散数学的概念无处不在。

练习建议：

1. 用 Rust 实现图的 DFS/BFS 遍历
2. 用容斥原理解决计数问题
3. 判断给定关系是否为等价关系或偏序关系