离散数学·从命题逻辑到代数系统

参考教材：Kenneth H. Rosen《离散数学及其应用》第6版（中文版，第1–12章）。GitHub 配套课本：github.com/goodisok/ChinaTextbook

---

离散数学是计算机科学的数学基础。与连续的高等数学不同，离散数学研究的是可数的、分离的结构——逻辑的真假、集合的元素、图的节点、树的层次。本文覆盖 Rosen 教材第 6 版全部 12 章，按”概念直觉→定义→手算例子→工程应用”的路径，用一张表看懂整个离散数学。

一、逻辑与证明——推理的基石

概念直觉

计算机只认 0 和 1，逻辑只认真和假。命题逻辑就是把自然语言的推理变成机械化的符号运算——你不需要”理解”一句话的意思，只需要按规则操作真值表，结论自动出来。

定义

命题：非真即假的陈述句。”2+2=4”是命题（真），”你好吗？”不是。

五种基本逻辑联结词：

联结词	符号	含义	真值条件
否定	$\neg p$	非 $p$	$p$ 假时为真
合取	$p \land q$	$p$ 且 $q$	两者同真
析取	$p \lor q$	$p$ 或 $q$	至少一真
异或	$p \oplus q$	$p$ 异或 $q$	恰有一真
蕴含	$p \to q$	若 $p$ 则 $q$	$p$ 假或 $q$ 真
双条件	$p \leftrightarrow q$	$p$ 当且仅当 $q$	同真或同假

谓词逻辑引入了量词：

• 全称量词 $\forall x P(x)$：”对所有 $x$，$P(x)$ 为真”
• 存在量词 $\exists x P(x)$：”存在某个 $x$ 使 $P(x)$ 为真”

这是命题逻辑的”升级版”——可以从”苏格拉底是人”推出”苏格拉底会死”，因为 $\forall x (\text{人}(x) \to \text{会死}(x))$。

重要推理规则

规则	形式	例子
假言推理	$p \to q,\ p \implies q$	若下雨则地湿；下雨了 → 地湿
取拒式	$p \to q,\ \neg q \implies \neg p$	若下雨则地湿；地没湿 → 没下雨
假言三段论	$p \to q,\ q \to r \implies p \to r$	若A则B，若B则C → 若A则C
归谬法	假设 $\neg p$ 推出矛盾 → $p$	假设 $\sqrt{2}$ 是有理数 → 矛盾

手算例子

验证 $(p \to q) \land (q \to r) \to (p \to r)$ 是永真式：

$p$	$q$	$r$	$p \to q$	$q \to r$	$(p \to q)\land(q \to r)$	$p \to r$	最终
T	T	T	T	T	T	T	T
T	T	F	T	F	F	F	T
T	F	T	F	T	F	T	T
T	F	F	F	T	F	F	T
F	T	T	T	T	T	T	T
F	T	F	T	F	F	T	T
F	F	T	T	T	T	T	T
F	F	F	T	T	T	T	T

最后一列全为 T，证毕。

工程应用

• 程序正确性证明：Hoare 逻辑 $\{P\}C\{Q\}$ —— 前置条件 $P$ 下执行代码 $C$ 后保证后置条件 $Q$
• 模型检查：硬件设计的状态空间用时序逻辑公式检验，Intel 用此法避免了 Pentium FDIV bug 重演
• Prolog 与逻辑编程：直接以 Horn 子句（$P_1 \land P_2 \land \cdots \land P_n \to Q$）为程序
• 类型系统：$\forall \alpha.\ \text{List}(\alpha) \to \text{Int}$ 是 Hindley-Milner 的全称量化

---

二、集合、函数与序列——离散世界的砖块

概念直觉

如果把连续数学比作光滑的曲线，离散数学就是一堆分离的”砖块”。集合是最基本的砖块容器，函数是砖块之间的映射管道，序列是砖块的排队方式。

定义

集合：确定对象的汇集。$A = \{1, 3, 5, 7\}$，$B = \{x \mid x \text{ 是质数且 } x < 10\}$。

核心运算：

运算	定义	文氏图含义
并 $A \cup B$	$\{x \mid x \in A \lor x \in B\}$	两圆合并
交 $A \cap B$	$\{x \mid x \in A \land x \in B\}$	两圆重叠区
差 $A - B$	$\{x \mid x \in A \land x \notin B\}$	$A$ 圆中挖掉 $B$
补 $\overline{A}$	$\{x \mid x \notin A\}$	框内圆外
幂集 $\mathcal{P}(A)$	$A$ 的所有子集的集合	含 $2^{|A|}$ 个元素

容斥原理（两个集合的情况）：

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

函数 $f: A \to B$：对每个 $a \in A$，指派唯一的 $b \in B$。

三种关键性质：

$$\text{单射（一对一）} \quad \text{满射（覆盖每个 }b\text{）} \quad \text{双射（一一对应）}$$

序列：定义域为自然数集的函数。等比序列 $a_n = a r^{n-1}$，等差数列 $a_n = a + (n-1)d$。

求和公式速查：

$$\sum_{k=1}^{n} k = \frac{n(n+1)}{2}, \quad \sum_{k=1}^{n} k^2 = \frac{n(n+1)(2n+1)}{6}, \quad \sum_{k=0}^{\infty} ar^k = \frac{a}{1-r}\ (|r|<1)$$

手算例子

求 $\sum_{k=1}^{100} k$：

$$\sum_{k=1}^{100} k = \frac{100 \cdot 101}{2} = 5050$$

图：集合运算文氏图 — 并集、交集、差集、补集的直观表示

（高斯 8 岁时的算法：首尾配对，$1+100=101$，$2+99=101$，共 50 对。）

工程应用

• 数据库：关系代数（选择 $\sigma$、投影 $\pi$、连接 $\bowtie$）直接基于集合运算
• 哈希表：$f(x) = x \bmod m$ 是集合 $\{0,\ldots,m-1\}$ 上的函数；冲突处理本质是容斥原理的工程实现
• 密码学：RSA 加密要求 $e$ 和 $\phi(n)$ 互质——纯集合/数论问题
• 信息检索：TF-IDF 中的词频统计就是序列上的加权求和

---

三、算法、整数与矩阵——离散计算的基础设施

概念直觉

程序可以写成中文、英文、Python——但算法关心的是做事的步骤本身。而离散世界里最重要的”原材料”是整数和矩阵。

算法复杂度

大 $O$ 记号：$f(x)$ 是 $O(g(x))$，如果存在常数 $C$ 和 $k$ 使得 $|f(x)| \leq C|g(x)|$ 对所有 $x > k$ 成立。

常见复杂度排序（从快到慢）：

$$O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2) < O(2^n) < O(n!)$$

数论基础

整除：$a \mid b$ 表示 $b = a \cdot c$（某个整数 $c$）。

模运算：$a \equiv b \pmod{m}$ 表示 $m \mid (a-b)$。

欧几里得算法求 $\gcd(a, b)$：

$$\gcd(a, b) = \gcd(b, a \bmod b),\quad \text{直到余数为 0}$$

贝祖定理：存在整数 $s, t$ 使得 $\gcd(a, b) = sa + tb$。

矩阵运算

布尔矩阵（元素只取 0 或 1，运算用 $\land$ 代替 $\times$、$\lor$ 代替 $+$）：

$$A \odot B \text{ 的 } (i,j) \text{ 元} = \bigvee_{k}(a_{ik} \land b_{kj})$$

布尔矩阵乘法直接对应关系复合和图的传递闭包。

手算例子

求 $\gcd(252, 105)$：

$$\begin{aligned} 252 &= 2 \cdot 105 + 42 \\ 105 &= 2 \cdot 42 + 21 \\ 42 &= 2 \cdot 21 + 0 \end{aligned}$$

所以 $\gcd(252, 105) = 21$。

工程应用

• RSA 加密：基于大整数分解的困难性；扩展欧几里得算法求模逆 $d \equiv e^{-1} \pmod{\phi(n)}$
• 哈希函数：SHA-256 内部大量使用位运算和模加——整数论每天都在保护你的密码
• 伪随机数生成：线性同余生成器 $X_{n+1} = (aX_n + c) \bmod m$
• 图像处理：卷积核本质上是矩阵在像素上的离散滑动运算

---

四、归纳与递归——用自己定义自己

概念直觉

“第一个多米诺骨牌被推倒，而且每一块倒下的骨牌都会推倒下一块 → 所有骨牌都会倒下。”这就是数学归纳法。递归是它的”构造版”——用自己来定义自己。

数学归纳法

第一原理（弱归纳）：

1. 基础步骤：证明 $P(1)$ 为真
2. 归纳步骤：假设 $P(k)$ 为真，证明 $P(k+1)$ 为真

第二原理（强归纳）：假设 $P(1), P(2), \ldots, P(k)$ 全为真，证明 $P(k+1)$ 为真。

递归定义

递归函数：用自身的较小实例来定义。斐波那契数列：

$$f_0 = 0,\ f_1 = 1,\ f_n = f_{n-1} + f_{n-2}\ (n \geq 2)$$

递归与迭代：任何递归都可以转化为迭代（用栈模拟），但递归表达更自然。

分治算法的递推式：

$$T(n) = aT\!\left(\frac{n}{b}\right) + f(n)$$

主定理给出闭合解：

$$T(n) = \begin{cases} \Theta(n^{\log_b a}) & \text{若 } f(n) = O(n^{\log_b a - \varepsilon}) \\[2pt] \Theta(n^{\log_b a} \log n) & \text{若 } f(n) = \Theta(n^{\log_b a}) \\[2pt] \Theta(f(n)) & \text{若 } f(n) = \Omega(n^{\log_b a + \varepsilon}) \end{cases}$$

手算例子

证明 $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$：

• 基础：$n=1$ 时，$1 = \frac{1 \cdot 2}{2}$ ✓
• 归纳：假设 $\sum_{i=1}^{k} i = \frac{k(k+1)}{2}$，则

$$\sum_{i=1}^{k+1} i = \sum_{i=1}^{k} i + (k+1) = \frac{k(k+1)}{2} + (k+1) = \frac{(k+1)(k+2)}{2}$$

工程应用

• 归并排序：$T(n) = 2T(n/2) + O(n)$ → 主定理：$O(n \log n)$
• 动态规划：斐波那契自底向上 $O(n)$，用记忆化递归避免指数爆炸
• 编译器解析：递归下降 parser 直接对应 BNF 文法规则
• 分形天线：Koch 雪花递归生成——小型化宽带天线设计

---

五、计数与离散概率——有多少种可能

概念直觉

密码有多少种可能？52 张扑克牌有多少种排列？从 10 人中选 3 人组队，有多少种选法？计数回答”有多少”的问题，离散概率回答”有多大概率”。两者紧密相连。

基本计数原理

规则	公式	例子
乘法原理	任务分 $k$ 步，各有 $n_1,\ldots,n_k$ 种 → $n_1 n_2 \cdots n_k$	4 位 PIN 码：$10^4 = 10000$
加法原理	任务有 $k$ 种互斥方式 → $n_1 + \cdots + n_k$	选 1 男生或 1 女生：$20+15=35$
排列 $P(n,r)$	$n$ 取 $r$ 有序排列	$\frac{n!}{(n-r)!}$
组合 $C(n,r)$	$n$ 取 $r$ 无序选择	$\frac{n!}{r!(n-r)!} = \binom{n}{r}$

鸽巢原理：$n$ 只鸽子放进 $m < n$ 个巢 → 至少一巢有 $\lceil n/m \rceil$ 只以上。简单到荒谬，强大到无敌——存在性证明的利器。

离散概率

样本空间 $S$ 是等可能的有限集时：

$$P(E) = \frac{|E|}{|S|}$$

条件概率：$P(A \mid B) = \frac{P(A \cap B)}{P(B)}$

贝叶斯定理——从”果”推”因”：

$$P(A \mid B) = \frac{P(B \mid A) \cdot P(A)}{P(B)}$$

期望：$E(X) = \sum_s P(s)X(s)$；方差：$V(X) = E(X^2) - [E(X)]^2$

手算例子

52 张扑克牌中抽 5 张，全是同花的概率：

$$P = \frac{4 \cdot \binom{13}{5}}{\binom{52}{5}} = \frac{4 \cdot 1287}{2598960} \approx 0.00198$$

（约 0.2%，505 把才出 1 把同花。）

工程应用

• 朴素贝叶斯分类器：垃圾邮件过滤——$P(\text{垃圾} \mid \text{廉价,伟哥,点击}) \propto P(\text{廉价} \mid \text{垃圾})P(\text{伟哥} \mid \text{垃圾})\cdots$
• 马尔可夫链：PageRank 的随机游走模型；MCMC 采样
• 信息熵：$H = -\sum p_i \log_2 p_i$ —— 离散概率的直接应用，压缩算法的理论基础
• 蒙特卡洛仿真：无人机避障中的随机采样路径规划（RRT）——每一帧都在用概率

---

六、高级计数与关系——更精密的计数工具

6.1 高级计数技术

容斥原理（一般形式）

$$\left|\bigcup_{i=1}^{n} A_i\right| = \sum_{i}|A_i| - \sum_{i<j}|A_i \cap A_j| + \sum_{i<j<k}|A_i \cap A_j \cap A_k| - \cdots + (-1)^{n+1}|A_1 \cap \cdots \cap A_n|$$

记忆方法：加单、减双、加三、减四……

生成函数

把一个序列 $\{a_n\}$ 打包成幂级数：

$$G(x) = \sum_{n=0}^{\infty} a_n x^n$$

四则运算对应序列的加减、卷积。解递推关系时，把递推式转化为 $G(x)$ 的方程，解出 $G(x)$ 再展开回序列。

例子：斐波那契的生成函数：

$$G(x) = \frac{x}{1 - x - x^2}$$

展开即可得到斐波那契数的闭式公式：

$$f_n = \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n\right]$$

6.2 关系——元素之间的连线

概念直觉

“大于””等于””父子””同事”——这些都是关系。离散数学把关系抽象成有序对的集合：$(a,b)$ 在关系中表示 $a$ 与 $b$ 有关系。

定义

$n$ 元关系：$A_1 \times A_2 \times \cdots \times A_n$ 的子集。

二元关系的三种核心性质：

性质	定义	例子	反例
自反	$\forall a: (a,a) \in R$	$\leq$, 集合的包含	$<$, “父子”
对称	$(a,b) \in R \Rightarrow (b,a) \in R$	$=$, 平行	$\leq$, “父子”
传递	$(a,b),(b,c) \in R \Rightarrow (a,c) \in R$	$\leq$, 祖先	“朋友”（不一定）

两种关键关系

等价关系（自反 + 对称 + 传递）：把集合划分成等价类。”模 $m$ 同余”是最经典的等价关系。

偏序关系（自反 + 反对称 + 传递）：定义”大小””包含”等层次结构。Hasse 图可视化偏序集——去掉自环和传递边，用高低表示顺序。

关系的矩阵表示

$$M_R[i,j] = \begin{cases} 1 & \text{若 } (a_i, b_j) \in R \\ 0 & \text{否则} \end{cases}$$

关系的复合对应布尔矩阵乘法。

手算例子

判断 $R = \{(1,1), (2,2), (3,3), (1,2), (2,1)\}$ 的性质：

• 自反：$(1,1),(2,2),(3,3)$ 都在 ✓
• 对称：$(1,2)$ 在 → $(2,1)$ 也在 ✓
• 传递：$(1,2)$ 和 $(2,1)$ 在 → $(1,1)$ 需在 ✓（确实在）
• 反对称：$(1,2)$ 和 $(2,1)$ 都在 → 不成立 ✗

结论：$R$ 是等价关系（自反 + 对称 + 传递），等价类为 $\{1,2\}$ 和 $\{3\}$。

工程应用

• 关系数据库：每张表就是一个关系；SQL JOIN = 关系的自然连接
• 拓扑排序：偏序 → 任务调度（先修课 → 后续课）
• 等价类测试：软件测试中的等价类划分法——每个等价类只取一个测试用例
• 编译器优化：数据流分析用格的偏序结构；支配树用偏序的 Hasse 图

---

七、图与树——离散世界的网络

7.1 图论基础

概念直觉

一个图就是节点 + 边。节点是实体（路由器、人、城市），边是关系（网线、友谊、公路）。图论把整个网络抽象成数学对象，然后用定理分析它的性质。

定义

图 $G = (V, E)$，其中 $V$ 为顶点集，$E$ 为边集。边是顶点的无序对（无向图）或有序对（有向图）。

握手定理：所有顶点的度数之和 = 边数的两倍：

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

推论：奇度顶点的个数必为偶数。

图的分类速查

类型	条件	性质	例子
完全图 $K_n$	每对顶点间都有边	$\frac{n(n-1)}{2}$ 条边	全连接网络
二分图	顶点可分成两集合，边只跨集合	无奇环	推荐系统：用户-商品
欧拉图	存在经过每条边恰好一次的回路	所有顶点度数为偶数	邮递员送信路线
哈密顿图	存在经过每个顶点恰好一次的回路	无充要条件（NP 完全）	旅行商问题（TSP）
平面图	可画在平面上无边交叉	$m \leq 3n - 6$（$n \geq 3$）	PCB 布线

图的着色

色数 $\chi(G)$：使相邻顶点不同色的最少颜色数。四色定理：任何平面图 $\chi(G) \leq 4$。

7.2 树——最简单的连通图

定义

树：连通且无简单回路的无向图。有根树：指定了根的树，有父子层级。

等价刻画：$n$ 个顶点的树有 $n-1$ 条边；任意两点间有唯一简单路径。

生成树与最小生成树

• 生成树：包含所有顶点的树的子图
• 最小生成树（MST）：边权之和最小的生成树

Kruskal 算法：按权从小到大加边，不形成回路则加入。Prim 算法：从任意点开始，每次加连接已选集合的最小边。

二叉树的应用

• 二叉搜索树（BST）：左 < 根 < 右，查找平均 $O(\log n)$
• 哈夫曼树：最优前缀编码——频率高的字符给短编码。平均码长达到信息熵的下界
• 堆排序：基于完全二叉树的优先级队列

手算例子

Kruskal 求 MST（5 个顶点 7 条边）：

边：(1,2,1) (2,3,2) (1,3,3) (3,4,1) (2,4,4) (4,5,2) (1,5,5)

按权排序：$(1,2,1)$ → $(3,4,1)$ → $(2,3,2)$ → $(4,5,2)$ → $(1,3,3)$（形成回路，跳过）

MST 总权 = $1 + 1 + 2 + 2 = 6$，包含边 $(1,2), (3,4), (2,3), (4,5)$。

工程应用

• 网络路由：OSPF 协议用 Dijkstra 算法算最短路径（本质是图的单源最短路）
• 编译器：抽象语法树（AST）是有根树；寄存器分配用图着色算法
• 电路设计：PCB 布线是平面图问题；时钟树综合是有根树的平衡问题
• 路径规划：无人机三维栅格地图中，A* 搜索在带权图上找最短无碰路径

---

图：图论核心概念 — 一般图、最小生成树(MST)、二叉搜索树

八、布尔代数与代数系统——逻辑的代数化

8.1 布尔代数

概念直觉

1854 年，George Boole 出版《思维定律的研究》，把逻辑推理变成了代数运算。所有数字电路——从加法器到 CPU——都是布尔代数的物理实现。

定义

布尔代数是一个集合 $B = \{0, 1\}$ 以及两种二元运算：

运算	记号	等价逻辑	真值表
和（OR）	$x + y$（或 $x \lor y$）	析取	$1+1=1$（布尔代数中！）
积（AND）	$x \cdot y$（或 $x \land y$）	合取	$1 \cdot 0 = 0$
补	$\overline{x}$（或 $x'$）	否定	$\overline{0}=1,\ \overline{1}=0$

在布尔代数中：

$$x + x = x,\quad x \cdot x = x,\quad x + \overline{x} = 1,\quad x \cdot \overline{x} = 0$$

德·摩根律：

$$\overline{x + y} = \overline{x} \cdot \overline{y},\qquad \overline{x \cdot y} = \overline{x} + \overline{y}$$

记忆：”掰开杠，改符号“——把补号分给每个变量，AND 变 OR，OR 变 AND。

布尔函数与逻辑门

任何布尔函数都可用**积之和（SOP）或和之积（POS）**形式表示。卡诺图（Karnaugh Map）是手工化简布尔函数的图像化方法。

8.2 代数系统——群、环、域

概念直觉

自然数 → 整数 → 有理数 → 实数 → 复数——每一次扩展都增加了新的代数结构。群、环、域就是对这些结构做公理化抽象。

群（Group）

定义：非空集合 $G$ 和二元运算 $*$，满足：

1. 封闭性：$a,b \in G \implies a * b \in G$
2. 结合律：$(a*b)*c = a*(b*c)$
3. 单位元：存在 $e$ 使 $e*a = a*e = a$
4. 逆元：每个 $a$ 有 $a^{-1}$ 使 $a*a^{-1} = a^{-1}*a = e$

阿贝尔群：还满足 $a*b = b*a$（交换律）。

例子：$(\mathbb{Z}, +)$ 是群，$(\mathbb{Z}_n, +)$ 是有限阿贝尔群。

环（Ring）

集合 $R$ 上有两种运算（加法+和乘法·），$(R, +)$ 是阿贝尔群，乘法满足结合律，满足分配律。

例子：$(\mathbb{Z}, +, \cdot)$ 是环。

域（Field）

环 $F$ 中非零元对乘法也构成群（即每个非零元有乘法逆）。

例子：$(\mathbb{R}, +, \cdot)$、$(\mathbb{Q}, +, \cdot)$ 是域。有限域 $\mathbb{F}_p$（$p$ 为质数）在密码学中至关重要。

手算例子

验证 $(\mathbb{Z}_4, \oplus_4)$ 是群（模 4 加法）：

$\oplus_4$	0	1	2	3
0	0	1	2	3
1	1	2	3	0
2	2	3	0	1
3	3	0	1	2

每行每列都有 0，每元有逆——是群。又是交换群（对称矩阵）。

工程应用

• 数字电路：加法器、乘法器、ALU 全部用布尔门构建——CPU 就是 $10^9$ 个布尔函数并行计算
• 密码学：椭圆曲线密码学（ECC）的底层是有限域上的群运算——点加 + 标量乘
• 纠错码：Reed-Solomon 码基于有限域 $\mathbb{F}_{2^m}$ 上的多项式。你的二维码（QR Code）就在用它
• 对称性：晶体的空间群分类 → 固体物理的基础；分子对称群 → 化学光谱分析
• 机器人运动规划：SO(3) 是三维旋转群，四元数乘法构成李群——无人机姿态控制的数学基石

---

核心公式速查卡

公式	含义
$p \to q \equiv \neg p \lor q$	蕴含的等价转换
$\neg(p \land q) \equiv \neg p \lor \neg q$	德·摩根律——把 AND 的否定变成 OR
$|A \cup B| = |A| + |B| - |A \cap B|$	两个集合的容斥原理
$\sum_{k=1}^{n} k = \frac{n(n+1)}{2}$	等差求和——高斯公式
$\gcd(a,b) = \gcd(b, a \bmod b)$	欧几里得算法核心递推
$P(n,r) = \frac{n!}{(n-r)!},\ C(n,r) = \binom{n}{r}$	排列 vs 组合
$P(A \mid B) = \frac{P(B \mid A)P(A)}{P(B)}$	贝叶斯定理——机器学习的心脏
$\sum \deg(v) = 2|E|$	握手定理
$m \leq 3n - 6$	平面图的边数上界
$x + \overline{x} = 1,\ x \cdot \overline{x} = 0$	布尔代数的互余律

---

推荐学习路线

1. 逻辑与证明（Ch1）→ 所有后续章节的语言基础，先过真值表和推理规则
2. 集合、函数与序列（Ch2）→ 离散世界的”词汇表”，手算 10 个求和公式
3. 算法与整数（Ch3）→ 欧几里得算法和模运算，为密码学做准备
4. 归纳与递归（Ch4）→ 证明递推式和分治复杂度——用 Python 验证
5. 计数（Ch5）→ 排列组合，动手算”彩票中奖概率”
6. 离散概率（Ch6）→ 期望 + 贝叶斯，用实际数据跑一次朴素贝叶斯分类
7. 高级计数（Ch7）→ 容斥原理和生成函数——抽象但强大
8. 关系（Ch8）→ 等价关系 == 分类；偏序 == 层次
9. 图（Ch9）→ 画 10 个图，手动运行 BFS/DFS/Dijkstra
10. 树（Ch10）→ 实现一个二叉搜索树 + Huffman 编码
11. 布尔代数（Ch11）→ 用卡诺图化简 5 个逻辑表达式
12. 代数系统（Ch12）→ 群论是抽象代数的入口，联系密码学和对称性

推荐资源：

• Rosen《Discrete Mathematics and Its Applications》—— 最完整的教材
• MIT 6.042J《Mathematics for Computer Science》（OCW）—— 优秀的视频课程
• Susanna Epp《Discrete Mathematics with Applications》—— 更适合自学的入门书
• Knuth《具体数学》（Concrete Mathematics）—— 进阶阅读，计数与求和的经典

---

参考文献

1. Rosen, K. H. (2007). Discrete Mathematics and Its Applications. 6th ed. McGraw-Hill.
2. Epp, S. S. (2010). Discrete Mathematics with Applications. 4th ed. Cengage Learning.
3. Graham, R. L., Knuth, D. E., & Patashnik, O. (1994). Concrete Mathematics: A Foundation for Computer Science. 2nd ed. Addison-Wesley.
4. Boole, G. (1854). An Investigation of the Laws of Thought. Walton and Maberly.
5. Shannon, C. E. (1938). “A Symbolic Analysis of Relay and Switching Circuits”. Transactions of the American Institute of Electrical Engineers, 57(12), 713–723.
6. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms. 3rd ed. MIT Press.

图：六种基本逻辑门 — AND、OR、NOT、XOR、NAND、NOR 的符号与代数表达式