离散数学：从形式逻辑到计算模型

“离散数学是算法与程序设计的灵魂。” —— 本专题涵盖命题逻辑、集合论、代数系统与图论，重点探讨这些抽象理论如何转化为计算机中的二进制运算与高效数据结构。

---

🪜 练习阶梯与评价标准

等级	难度目标	核心考察点	期望达成
● Level A	符号化与化简	范式转换、布尔代数化简	熟练掌握逻辑等价变换
● Level B	建模与证明	关系性质判定、自然推理证明	能够进行严谨的数学逻辑推导
● Level C	计算模型应用	图论建模 (SCC)、布尔电路设计	将离散结构转化为 C++ 算法实现

---

🎯 跨学科考点矩阵 (Knowledge Matrix)

知识模块	数学核心	计算机落地 (CS/CP)	关联习题
数理逻辑	命题演算, 一阶谓词	条件判定、布尔电路化简	练习 1, 2
集合与关系	二元关系, 等价/偏序	数据库范式, 并查集 (DSU)	练习 3, 4
代数系统	群/环/域, 陪集分解	密码学 (ECC/AES), 纠错码	练习 5
图论	连通性, 匹配, 拓扑序	社交网络分析, 编译器依赖检查	练习 6, 7

---

📂 核心习题库

Level A：数理逻辑与布尔代数

练习 1：布尔表达式的最简化 (Logic Optimization)

题目描述：代数化简布尔表达式 $f = \overline{(A + B)} + \bar A B$。

Check Solution (Formal Proof)

推导过程：

1. 德摩根律：$\overline{A+B} = \bar A \cdot \bar B$。
2. 替换原式：$f = (\bar A \bar B) + \bar A B$。
3. 分配律逆向：$f = \bar A (\bar B + B)$。
4. 互补律：由于 $\bar B + B = 1$，故 $f = \bar A \cdot 1$。
5. 单位律：$f = \bar A$。

工程应用：在编译器优化中，类似的逻辑化简可以减少 CPU 指令数或逻辑门的使用。

---

Level B：集合、关系与建模

练习 2：等价关系与并查集 (Union-Find)

题目描述：设 $A = \{1, 2, \dots, n\}$，定义关系 $R$ 为等价关系。证明：等价关系 $R$ 对 $A$ 的划分与并查集（Union-Find）维护的连通分量是一一对应的。

Check Solution (Modeling)

思维链 (Thought Chain)：

1. 等价类定义：等价类 $[x]_R = \{y \in A \mid (x, y) \in R\}$。
2. 并查集逻辑：并查集通过 find(x) == find(y) 判定连通性。连通性具有自反性、对称性和传递性，因此是一种典型的等价关系。
3. 结论：并查集中的每个“树”对应一个等价类，find 操作对应的代表元即为等价类的代表元素。

---

Level C：图论与计算模型

练习 3：强连通分量 (SCC) 的 Tarjan 算法实现

题目描述：在有向图中，如果两个顶点 $u, v$ 之间双向可达，则称其为强连通。实现 Tarjan 算法，寻找图中所有的强连通分量。

Check Solution (C++ Implementation)

数学原理： 利用深度优先搜索 (DFS) 的搜索树性质，通过 dfn (发现时间) 和 low (能回溯到的最小 dfn) 来判定 SCC。当 dfn[u] == low[u] 时，栈中从 $u$ 之后的所有元素构成一个 SCC。

C++ 代码实现：

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

const int N = 100010;
vector<int> adj[N];
int dfn[N], low[N], timestamp;
stack<int> stk;
bool in_stack[N];
int scc_cnt, id[N];

void tarjan(int u) {
    dfn[u] = low[u] = ++timestamp;
    stk.push(u);
    in_stack[u] = true;

    for (int v : adj[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (in_stack[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }

    if (dfn[u] == low[u]) {
        scc_cnt++;
        int y;
        do {
            y = stk.top();
            stk.pop();
            in_stack[y] = false;
            id[y] = scc_cnt;
        } while (y != u);
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    while (m--) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
    }
    for (int i = 1; i <= n; i++)
        if (!dfn[i]) tarjan(i);
    
    cout << "Number of SCCs: " << scc_cnt << endl;
    return 0;
}

练习 4：二部图匹配与霍尔定理 (Hall's Marriage Theorem)

题目描述：证明霍尔定理：二部图 $G=(V_1 \cup V_2, E)$ 存在 $V_1$ 到 $V_2$ 的完备匹配，当且仅当对任意 $S \subseteq V_1$，其邻集 $N(S)$ 满足 $|N(S)| \ge |S|$。

Check Solution (Graph Theory Proof)

证明概要：

1. 必要性：显然，若有完备匹配，每个元素至少匹配一个唯一邻居，邻集大小必不小于原集。
2. 充分性：可利用最大流最小割定理 (Max-Flow Min-Cut) 证明。构造源点 $s$ 连向 $V_1$（容量 1），$V_2$ 连向汇点 $t$（容量 1），原边容量 $\infty$。由 $|N(S)| \ge |S|$ 推导最小割必为 $|V_1|$，从而最大流为 $|V_1|$，对应一个完备匹配。

---

🏆 训练建议

1. 逻辑严密性：离散数学的学习重点在于“证明”而非“直觉”。尝试对每个算法背后的离散结构进行形式化描述。
2. 代码转换能力：能够将数学定义（如等价关系、闭包、格）转化为相应的数据结构（如并查集、邻接表、位向量）。
3. 关注底层：理解布尔代数如何通过逻辑门转化为现代 CPU 的算术逻辑单元 (ALU)。