离散数学及其应用 · 第 8 版
学习指南（基于原书结构与内容的自编导读）

Kenneth H. Rosen · Discrete Mathematics and Its Applications, 8e · 正文 13 章 942 页

76 个小节导学181 个编号定义117 个定理/引理 884 个例题≈4700 道习题88 位数学家传记全书符号速查原文摘录 · 译名备注 · 2026 进展注记

这本书到底教什么？

离散数学研究离散对象（可分离、可计数的对象）上的数学结构，它是计算机科学的数学底座。原书"To the Student"一章用一连串问题回答了这个疑问——学完本书你将能回答：

本页所有页码均为 PDF 页码；印刷页码 = PDF 页码 − 23。奇数号习题答案在 PDF 第 990–1087 页。

五大主题

原书前言明确声明：全书 13 章围绕五个交织的主题组织。读每一章时都可以问自己——这章在练哪个主题？

1. 数学推理 Mathematical Reasoning

逻辑与证明是起点。训练读证明、写证明，理解归纳法为什么有效（第 1、5 章）。

2. 组合分析 Combinatorial Analysis

重点不是背公式，而是分析计数问题的能力（第 6、8 章）。

3. 离散结构 Discrete Structures

集合、排列、关系、图、树、有限状态机——表示离散对象的抽象结构（第 2、9–13 章）。

4. 算法思维 Algorithmic Thinking

算法描述（伪代码）、正确性验证、时间/空间分析（第 3、5 章，贯穿全书 46 个算法）。

5. 应用与建模 Applications & Modeling

CS 与网络为主，兼及化学、生物、语言学、商业。RSA、Huffman、Dijkstra 全部真实落地。

先修要求 Prerequisite

仅要求大学代数。英文原版平均每页约 3300 字符，中文读者建议配合本指南的中文导学降低阅读阻力。

全书知识地图

13 章分为 4 大板块；箭头表示强依赖，虚线弱依赖。先修链条：Ch1 → Ch2 → 其余。

板块一 · 数学语言与证明（Ch1–2）——全书的"字母表"

先学会精确表达（逻辑记号），再掌握基本对象（集合与函数）。所有后续章节都用这两章的语言书写。

Ch1 逻辑与证明 · 120页Ch2 集合/函数/序列/矩阵 · 80页

板块二 · 算法与数论（Ch3–5）——"算法思维"主线

学会描述算法（Ch3）、用数论做实事（Ch4 RSA 密码）、用归纳法证明算法正确（Ch5）。

Ch3 算法与复杂度 · 50页Ch4 数论与密码学 · 80页Ch5 归纳与递归 · 74页

板块三 · 计数与概率（Ch6–8）——"组合分析"主线

从乘法原理到生成函数；习题量全书最密集的板块（≈1618 题）。

Ch6 计数 · 64页Ch7 离散概率 · 58页Ch8 高级计数 · 72页

板块四 · 关系结构与计算理论（Ch9–13）——"离散结构"主线

关系 → 图 → 树 → 布尔代数 → 自动机与图灵机，从数学走向理论计算机科学。

Ch9 关系 · 74页Ch10 图论 · 108页Ch11 树 · 66页Ch12 布尔代数 · 38页Ch13 计算模型 · 58页

学习路径

原书设计支持一学期或两学期课程，模块化程度高。按你的目标选一条：

路线 A · 一学期 CS 导向（4–5 小时/周 × 16 周）

覆盖算法课/数据结构课所需的全部数学基础。Ch4、7、12 按兴趣补充。

Ch1 逻辑证明→Ch2 集合函数→Ch3 算法→Ch5 归纳递归→Ch6 计数→Ch9 关系(选)→Ch10 图→Ch11 树→Ch13 自动机(选)

路线 B · 两学期完整研读（全书）

第一学期：Ch1–5（数学基础 + 数论）；第二学期：Ch6–13（计数概率 + 结构与计算理论）。

第一学期 Ch1→2→3→4→5→第二学期 Ch6→7→8→9→10→11→12→13

路线 C · 密码学 / 安全方向快线

直接面向密码学学习的最小集合。第 4 章是核心，需要 Ch1–3 打底。

Ch1(1.1–1.5)→Ch2(2.1–2.4)→Ch3→Ch4 全章精读→Ch6(计数打底)

路线 D · 考研 / 竞赛复习

重点章节精做习题：Ch1（证明训练）、Ch5（归纳）、Ch6+8（计数）、Ch10（图论）。每章末 Supplementary Exercises 全做。

内容量统计（实测自 PDF 原文）

定义/定理/例题标记由脚本从 PDF 文本层统计；习题数为各节最大题号累加（约数）。点击"已学"勾选框会更新侧边栏进度。

章标题PDF 页页数定义定理例题算法习题≈
1逻辑与证明基础24–1431201511380527
2基本结构144–223804941180381
3算法224–27350463111267
4数论与密码学274–353801519696379
5归纳与递归354–42774864910368
6计数428–491641*13723648
7离散概率492–549581216500224
8高级计数技术550–621723*13591346
9关系622–695742410973403
10图696–8031082216873535
11树804–8696699429264
12布尔代数870–907382*0280146
13计算模型908–96558174440227
合计94218111788446≈4715

* 第 6、8、12 章部分定义以列表/框图排版，未计入行首统计，实际略多。

第 1 章　逻辑与证明基础

The Foundations: Logic and Proofs · PDF 24–143 · 120 页（全书最长）

15 定义138 例题（全书第一）≈527 习题41 个 Extra Example 入口板块一 · 数学语言
这一章是全书的"语法课"：先把自然语言压缩成无歧义的符号系统（命题逻辑、谓词逻辑），再用这套符号学习什么是有效的推理（推理规则），最后进入数学的核心活动——写证明。第 8 版在此章安插了大量谜题、电路和 SAT 应用，让抽象规则立刻有用武之地。学习提示：真值表要亲手画，量词否定要大声念出来，这两件事决定后面所有章节的读题能力。

1.1 命题逻辑 Propositional Logic

PDF p24
  • 命题：能判断真假的陈述句。"几点了？"不是命题；悖论（"这句话是假的"）也不是。
  • 五大联结词及其真值规律：¬p否定、p ∧ q（同真才真）、p ∨ q（同假才假，"或"是可兼的）、p ⊕ q异或（恰一真）、p → q、p ↔ q。
  • 条件语句 p→q 的真值表是最大陷阱：前件为假时整个条件句为真（空真）。"若 1+1=3 则月球是奶酪做的"是真命题。
  • 术语：p 是假设/前件（hypothesis），q 是结论/后件（conclusion）；由 p→q 可派生逆命题 q→p、否命题 ¬p→¬q、逆否命题 ¬q→¬p。
  • 逻辑运算可直接用于位串（0/1 串的按位 ¬∧∨⊕），这是计算机表示逻辑的桥梁。
  • 练习重点：自然语言 ↔ 符号的双向翻译（"除非""只有…才""必要/充分条件"）。
核心定义

命题（proposition）：或真或假、不可兼的真值陈述句。否定 ¬p 读作"not p"；合取读作"p and q"；析取读作"p or q"。

学习提示

优先级从高到低：¬ → ∧ → ∨ → → → ↔。做翻译题先加括号再动手，可以避免 80% 的错误。

应用亮点
  • 自然语言翻译
  • 位运算与掩码
  • 翻译系统规范说明

1.2 命题逻辑的应用 Applications of Propositional Logic

PDF p40
  • 系统规范（specifications）：把"系统应满足的需求"翻译成复合命题，检查一致性（是否所有规范可以同时为真）。
  • 布尔搜索：搜索引擎的 AND / OR / NOT 运算就是命题逻辑。
  • 逻辑谜题：骑士与骗子、说谎者谜题——用真值赋值系统性求解，而不是靠灵感。
  • 逻辑电路：命题 ↔ 电路门（与门/或门/非门），信号 0/1 就是 F/T（第 12 章将全面展开）。
  • SAT 可满足性问题：判断是否存在一组真值使复合命题为真——它是 NPC 问题的代表，也是现代程序验证与芯片验证的基石。
为什么重要

SAT 求解器如今被用于验证航天器控制软件、芯片设计正确性——1.2 节是"逻辑离工业界最近"的一节。

应用亮点
  • 软件需求一致性检查
  • 搜索引擎语法
  • 骑士与骗子谜题
  • 数独与 SAT

1.3 命题等价式 Propositional Equivalences

PDF p49
  • 三类复合命题：永真式（tautology，全真）、矛盾式（contradiction，全假）、偶然式（contingency）。
  • 逻辑等价 p ≡ q 定义为 p ↔ q 是永真式。判断方法：真值表两列完全相同。
  • 必背三大等价：德摩根律 ¬(p∧q) ≡ ¬p∨¬q；蕴涵等价 p→q ≡ ¬p∨q；逆否等价 p→q ≡ ¬q→¬p。
  • 双条件拆解：p↔q ≡ (p→q)∧(q→p)；异或与双条件的关系 p↔q ≡ ¬(p⊕q)。
  • 恒等式表的用法：像代数化简一样"代入化简"复合命题，比真值表快得多（尤其变元多时）。
  • 可满足性：一个命题可满足 ⟺ 其否定不是永真式；不可满足的规范 = 矛盾的系统需求。
关键等价清单

分配律、吸收律 p∨(p∧q)≡p、德摩根律、蕴含等价、双重否定 ¬¬p≡p——原书本节表 6/7/8 建议抄成卡片随身背。

应用亮点
  • 化简系统规范
  • 优化逻辑电路（连接 12 章）
  • ¬(p→q) 型条件的读法

1.4 谓词与量词 Predicates and Quantifiers

PDF p63
  • 谓词 P(x)：带变量的命题函数，代入论域元素后变成命题。"x>3" 单独不是命题。
  • 全称量词 ∀x P(x)："对所有 x"；反例只需一个即可证假。存在量词 ∃x P(x)："存在某个 x"；举证即证真。
  • 量词在有限论域上可展开：∀ 展开为 ∧，∃ 展开为 ∨——这是"量词即压缩的与/或"的直觉。
  • 量词否定（最重要规则）：¬∀x P(x) ≡ ∃x ¬P(x)，¬∃x P(x) ≡ ∀x ¬P(x)。"不是所有人都…" = "有人不…"。
  • 约束变元 vs 自由变元；量词与联结词的优先级：∀x P(x)∧Q(x) 意为 (∀x P(x)) ∧ Q(x)，Q 中的 x 是自由的！
  • 唯一性量词 ∃!（存在且唯一）作为拓展记号出现。
核心定义

论域（domain/universe of discourse）必须先确定：同一谓词在不同论域下真值不同。"∀x(x²≥x)" 在正整数上真，在实数上假。

学习提示

读 ∀ 写"每一个"，读 ∃ 写"至少有一个"——把嵌套量词翻译成中文句子再翻译回去，是本节习题的核心训练。

应用亮点
  • 程序正确性断言（如"x>0"）
  • 翻译数学定理的精确陈述
  • 循环不变量的表达

1.5 嵌套量词 Nested Quantifiers

PDF p83
  • 顺序敏感是本节灵魂：∀x∃y (x+y=0) 真（每个 x 都能找到 −x），但 ∃y∀x (x+y=0) 假（没有万能的 y）。把 ∃∀ 读成"先手选/后手选"。
  • 经典翻译练习："每个人都有朋友" ∀x∃y F(x,y)；"有人是所有人的朋友" ∃y∀x F(x,y)；"没有人信任任何人" ¬∃x∃y T(x,y)。
  • 否定要逐层推进：¬∀x∃y P(x,y) ≡ ∃x∀y ¬P(x,y)——每次只翻最外层一个量词。
  • 嵌套量词的思考循环（Rosen 的"量词循环"）：∀ = loop through all，∃ = 找到一个就提前退出。
  • 与数学定义对接：极限、连续性、无界的精确表述都靠嵌套量词——这是数学分析语言的预演。
易错点

两个量词同型（∀∀ 或 ∃∃）时可交换顺序；异型（∀∃）交换必改变含义。做题前先判断量词类型再翻译。

应用亮点
  • 程序验证中的 ∀/∃ 断言
  • "所有人都能被某服务器服务"类系统性质

1.6 推理规则 Rules of Inference

PDF p96
  • 从"真值"升级到"论证"：有效论证 = 所有前提为真时结论必真（(p₁∧…∧pₙ) → q 永真）。
  • 八条基本规则：假言推理（modus ponens）p→q, p ⊢ q；取拒式 p→q, ¬q ⊢ ¬p；假言三段论；析取三段论；附加、化简、合取、消解（resolution）。
  • 谬误对照：肯定后件（p→q, q ⊬ p）与否定前件（p→q, ¬p ⊬ ¬q）是日常错误推理之王。
  • 带量词的推理规则：全称实例化 ∀x P(x) ⊢ P(c)、全称生成、存在实例化、存在生成。
  • 综合应用：把自然语言论证符号化 → 逐行引用规则构造证明链（这是逻辑证明的"汇编语言"）。
必背

Modus ponens（肯定前件）与 modus tollens（否定后件）是全部证明技术的两条腿；消解规则是自动定理证明（SAT 求解器）的引擎。

应用亮点
  • 自动定理证明
  • Prolog 逻辑编程基础
  • 识别日常谬误

1.7 证明导论 Introduction to Proofs

PDF p107
  • 定理（theorem）/ 引理（lemma）/ 推论（corollary）/ 猜想（conjecture）的分工。
  • 直接证明条件语句 p→q：假设 p 真，用定义、已有定理推出 q。范例："若 n 是奇数则 n² 是奇数"。
  • 间接证明：证明逆否命题 ¬q→¬p；以及反证法（归谬法）：假设结论假，推出矛盾。经典：√2 是无理数。
  • 退化情形：空证明（p 假则 p→q 自动成立）与平凡证明（q 显然真）。
  • 证明中的常见错误：把"任意"偷换成"某特定"、循环论证、遗漏情形。
  • 这节的例题（奇偶、整除、√2）是所有后续证明的模板，值得抄写模仿。
方法地图

目标 p→q：① 直接证；② 证逆否 ¬q→¬p；③ 反证（假设 ¬q 得矛盾）。目标 ∀x P(x)：取任意 c 证 P(c)。含绝对值的结论优先分情况。

写作规范

每行只推进一步；引用前面的行号或定理名；开头声明方法（"我们证明逆否命题"）——数学写作的工程规范。

1.8 证明方法与策略 Proof Methods and Strategy

PDF p119
  • 穷举证明（proof by cases）：把全集切成若干情形分别证明；配套不失一般性（WLOG）的用法。
  • 存在性证明：构造性（直接给出对象）vs 非构造性（反证/计数证明存在）。
  • 唯一性证明：设两个对象都满足，证它们相等。
  • 反例（counterexample）证否 ∀ 命题：一个反例即可。
  • 证明策略论：前向推理 vs 反向分析（要证什么才够）；改述问题；适配已知结论；未证明猜想的警示（开启"开放式问题"话题）。
  • 章节末尾给出拼装证明（ Tilings 拼板问题）等综合案例，训练"猜想 → 验证 → 证明"的完整循环。
策略清单

卡壳时的自查：换逆否？分情况？先证引理？画图？找小例子？换记号？把目标倒着推三步？——这是本章给你的"证明工具箱"。

应用亮点
  • 三角形不等式的分情况证明
  • 无穷素数的经典反证
  • 拼板覆盖问题

📖 本章定义速查（中英对照）

术语一行释义
proposition命题：可判断真假的陈述句
negation ¬p否定：“并非 p”，真值与 p 相反
conjunction p∧q合取：“p 且 q”，同真才真
disjunction p∨q析取：“p 或 q”（可兼或），同假才假
exclusive or p⊕q异或：p、q 恰一真时为真
conditional p→q条件语句：“若 p 则 q”；p 假时自动为真（空真）
converse / contrapositive逆命题 q→p / 逆否命题 ¬q→¬p（与原命题等价）
biconditional p↔q双条件：“p 当且仅当 q”，同真同假
tautology / contradiction永真式（全真）/ 矛盾式（全假）
logical equivalence p≡q逻辑等价：p↔q 为永真式
predicate P(x)谓词：含变量的命题函数，代入元素后成命题
universal / existential quantifier全称量词 ∀x / 存在量词 ∃x
satisfiable可满足：存在一组真值使复合命题为真

📐 定理与关键结论一览

  1. 德摩根律：¬(p∧q) ≡ ¬p∨¬q；¬(p∨q) ≡ ¬p∧¬q
  2. 蕴涵等价：p→q ≡ ¬p∨q；其否定 ¬(p→q) ≡ p∧¬q
  3. 逆否等价：p→q ≡ ¬q→¬p
  4. 量词否定：¬∀x P(x) ≡ ∃x ¬P(x)；¬∃x P(x) ≡ ∀x ¬P(x)
  5. 双条件拆解：p↔q ≡ (p→q)∧(q→p)
  6. 假言推理（modus ponens）：p→q, p ⊢ q——全部推理规则的母版
PDF p26原文摘录 · Short Quotation

“Let p be a proposition. The negation of p, denoted by ¬p … is the statement “It is not the case that p.””

原书对“否定”的定义原文——注意它同时列出 ~p、−p、p′ 等其他常用记号。

🕐 编者注 · 2026 视角（非原书内容）
  • SAT 求解器已高度实用化：工业级实例常达百万变量规模（CDCL 技术），是芯片验证与软件验证的日常工具——最坏情形 NP 完全与实践高效并存。
  • 交互式定理证明器（Lean、Coq、Isabelle）迅速普及，书中“证明必须手写”的图景正在被形式化证明补充与改变。
本章关键词： 命题proposition真值表truth table永真式tautology 逻辑等价logical equivalence德摩根律De Morgan's laws谓词predicate 量词quantifier推理规则rules of inference假言推理modus ponens 反证法proof by contradiction逆否contrapositive穷举证明exhaustive proof 反例counterexample可满足性satisfiability

章末材料 PDF p138：本章复习（关键术语/结果）→ 补充习题 → 计算机课题 → 计算探索 → 写作课题。

第 2 章　基本结构：集合、函数、序列、求和与矩阵

Basic Structures: Sets, Functions, Sequences, Sums, and Matrices · PDF 144–223 · 80 页

49 定义（全书最多）118 例题≈381 习题板块一 · 数学语言
如果说第 1 章是语法，本章就是词汇表：集合是数学的"无序容器"，函数是"带规则的对应"，序列是"排队的数"，矩阵是"排成方阵的数"。它们是后面一切结构（关系、图、树、自动机）的构造材料。49 个编号定义是全书最密集的一章——建议两遍法：先通读建立索引感，做题时再回查精确定义。

2.1 集合 Sets

PDF p144
  • 集合的两种表示：罗列法 {a,b,c} 与描述法 {x | P(x)}；元素属于 ∈、不属于 ∉。
  • 常见数集记号：N、Z、Z⁺、Q、R；区间的集合写法。
  • 子集 ⊆ 与真子集 ⊂ 的区别；两集合相等 ⟺ 互相包含。空集 ∅ 是一切集合的子集。
  • 幂集 P(S)：S 的所有子集构成的集合；|S|=n 时 |P(S)|=2ⁿ。
  • 笛卡尔积 A×B = {(a,b) | a∈A, b∈B}；|A×B|=|A|·|B|。
  • 集合可以作为真值集（truth set）：谓词 P(x) 对应论域中使 P 真的元素集合——与第 1 章谓词直接挂钩。
易错点

{∅} ≠ ∅：前者是"装着空集的袋子"。⊆ 表示"包含于"用于集合间，∈ 用于元素与集合——层次不要混。

应用亮点
  • 数据建模
  • 幂集与子集枚举
  • 乘积空间与网格坐标

2.2 集合运算 Set Operations

PDF p156
  • 并 ∪、交 ∩、补 A̅（相对于论域 U）、差 A−B = A∩B̅、对称差 A⊕B = (A−B)∪(B−A)。
  • 集合恒等式表：德摩根、分配律、吸收律——与命题逻辑恒等式逐条平行，可以互相"翻译"。
  • 三种证明恒等式的方法：逐元素证明、成员表（membership table，真值表翻版）、已知恒等式推导。
  • 证明技巧模板：证 A⊆B 时"任取 x∈A，推出 x∈B"——这是全书出现频率最高的证明骨架。
  • 计算机表示：位向量表示集合（全集固定时），交并补 = 按位与/或/取反——效率极高。
核心恒等式

A∪B̅ = A̅∩B̅（德摩根）　A∩(B∪C) = (A∩B)∪(A∩C)（分配）　A∪(A∩B) = A（吸收）

应用亮点
  • 位向量集合运算
  • 数据库过滤条件组合
  • 容斥原理的舞台（第 8 章）

2.3 函数 Functions

PDF p170
  • 函数 f: A→B 的严格定义：每个 x∈A 恰好对应一个 f(x)∈B。A 是定义域，B 是陪域，f(A) 是像（range）。
  • 三大性质：一对一（injective，单射：x₁≠x₂ ⟹ f(x₁)≠f(x₂)）；映上（surjective，满射：每个 y 都有原像）；一一对应（bijective，双射）。
  • 从 Z 到 Z 的函数一对一 ⟺ 严格单调递增/递减（这是判单射的主力工具）。
  • 反函数 f⁻¹ 存在 ⟺ f 是双射；合成 (f∘g)(x)=f(g(x))，注意顺序。
  • 重要函数清单：下取整 ⌊x⌋、上取整 ⌈x⌉（不等式夹逼是常考点）、阶乘、指数与对数。
  • 部分函数（partial function）与 CS 的"程序未必对所有输入有定义"对应。
核心定义

下取整 ⌊x⌋：≤ x 的最大整数；上取整 ⌈x⌉：≥ x 的最小整数。关键不等式：⌊x⌉±⌊x⌋ 要看 x 是否整数，常用水滴不等式 ⌊x⌋ ≤ x < ⌊x⌋+1。

应用亮点
  • 哈希函数
  • 编译器与解释器中的部分函数
  • ⌊x⌋ 在分页/分组中的应用

2.4 序列与求和 Sequences and Summations

PDF p188
  • 序列 {aₙ}：定义域为整数的函数；几何序列 a·rⁿ、算术序列 a+nd。
  • 递推定义：aₙ 用前面的项表达（Fibonacci 在此首次登场 Fₙ=Fₙ₋₁+Fₙ₋₂）——为第 5、8 章铺路。
  • 求和记号 Σ_{i=m}^{n} aᵢ 与双重求和；等比求和公式 Σ arⁱ = a(rⁿ⁺¹−1)/(r−1)。
  • 常用结果：Σi = n(n+1)/2、Σi² = n(n+1)(2n+1)/6；倒数的平方和收敛于 π²/6（巴塞尔问题，提增视野）。
  • ∑ 的线性性（常数可提出、可拆项）在算法分析（第 3 章）里天天用。
学习提示

把 Σ 当 for 循环读：Σᵢ aᵢ = "for i in m..n: s += aᵢ"。双重求和 = 嵌套循环，交换求和顺序 = 交换循环次序。

应用亮点
  • 程序分析中的循环开销求和
  • 复利与增长模型
  • Fibonacci 与自然现象

2.5 集合的基数 Cardinality of Sets

PDF p202
  • 基数相同 |A|=|B| ⟺ 存在 A→B 的双射——"数个数"被升级为"配对"。
  • 可数集（countable）：与 Z⁺ 基数相同或有限。奇数集、整数集 Z、有理数集 Q 都可数（Q 的对角排列法是经典）。
  • Cantor 对角线法：(0,1) 区间不可数——假设可列出 r₁,r₂,…，构造与每个 rᵢ 第 i 位都不同的新数，矛盾。这是数学史上最漂亮的证明之一。
  • 可数个可数集的并仍可数；实数集 R 与 (0,1) 等势。
  • Schroeder–Bernstein 定理（陈述）：|A|≤|B| 且 |B|≤|A| ⟹ |A|=|B|。
  • 无限 hierarchy 预告：|P(Z⁺)| > |Z⁺|，没有最大的无限。
里程碑定理

"实数不可数"意味着：有些问题根本无法逐一枚举解决——可计算性理论（第 13 章）的精神源头。

应用亮点
  • 证明"几乎所有的实数无法被程序描述"
  • 对角线法在计算理论中的复活

2.6 矩阵 Matrices

PDF p211
  • m×n 矩阵是数表；相等 = 同型且逐项相等；转置 Aᵗ 行列互换；对称矩阵 A=Aᵗ。
  • 矩阵加法（同型逐项）与乘法：(AB)ᵢⱼ = Σₖ aᵢₖbₖⱼ——注意 AB≠BA 一般不成立。
  • 单位矩阵 I、零矩阵；AI=IA=A。
  • 布尔矩阵运算：join ∨、meet ∧ 逐项，布尔积 A⊙B 用 ∨/∧ 替换 +/×——第 9 章关系闭包和第 10 章图邻接矩阵的运算基础。
  • 算法视角：矩阵乘法的朴素复杂度 O(mnk)，为第 3 章复杂度分析提供素材。
为什么要学

邻接矩阵（图）、关系矩阵（第 9 章）、转移矩阵（自动机）都要靠矩阵语言；布尔积直接用于 Warshall 算法。

应用亮点
  • 图的邻接矩阵表示
  • 关系数据库的连接运算
  • 网络流与线性代数衔接

📖 本章定义速查（中英对照）

术语一行释义
set / element集合 / 元素：对象的无序汇集；x∈S
subset A⊆B子集：A 的每个元素都在 B 中；真子集 A⊂B 排除相等
power set P(S)幂集：S 的全部子集构成的集合；|P(S)|=2^|S|
Cartesian product A×B笛卡尔积：{(a,b) | a∈A, b∈B}
union / intersection并 A∪B / 交 A∩B
difference / symmetric difference差 A−B / 对称差 A⊕B=(A−B)∪(B−A)
truth set真值集：论域中使谓词 P(x) 为真的元素集合
function f:A→B函数：每个 x∈A 恰对应一个 f(x)∈B
one-to-one / onto / bijection单射（一对一）/ 满射（映上）/ 双射（一一对应）
inverse function f⁻¹反函数：当且仅当 f 是双射时存在
floor ⌊x⌋ / ceiling ⌈x⌉下取整（≤x 的最大整数）/ 上取整（≥x 的最小整数）
countable set可数集：与 Z⁺ 等势或有限；不可数即无法与 Z⁺ 配对
matrix transpose Aᵗ转置：行列互换；对称矩阵 A=Aᵗ
Boolean product A⊙B布尔积：用 ∨/∧ 替换普通加乘的矩阵乘法

📐 定理与关键结论一览

  1. 对任意集合 S：∅⊆S 且 S⊆S
  2. 等比数列求和：Σ arⁱ = a(rⁿ⁺¹−1)/(r−1)（r≠0）
  3. 两个可数集的并仍可数（先并后重排的构造证明）
  4. Cantor 定理：(0,1) 区间不可数——对角线构造新实数与每个列出者不同
PDF p204原文摘录 · Short Quotation

“You can always get a room at Hilbert’s Grand Hotel!”

希尔伯特大旅馆悖论：无限旅馆“客满”仍能安排新客——直观展示无限集与有限集的本质差别。

PDF p203原文摘录 · Short Quotation

“…the set of real numbers is not countable. … A function is called uncomputable if no computer program can compute it.”

2.5 节把 Cantor 不可数性与“不可计算函数”相连——可数性理论直接通向可计算性。

本章关键词： 幂集power set笛卡尔积Cartesian product对称差symmetric difference 单射one-to-one满射onto双射bijection 反函数inverse function下取整floor可数countable 对角线法diagonalization布尔积Boolean product

章末材料 PDF p218。

第 3 章　算法

Algorithms · PDF 224–273 · 50 页（最短的章之一）

11 个伪代码算法（全书第二）31 例题≈267 习题板块二 · 算法思维
本章只有 3 节，却是"算法思维"主题的起点：什么叫算法、如何描述（伪代码）、如何衡量好坏（大 O 记号与复杂度）。它把前两章的数学语言第一次投放到"计算"这个战场上，也为第 4 章的数论算法、第 5 章的递归算法、第 10–11 章的图算法提供了分析框架。伪代码约定见附录 A3（PDF p976），第一次接触建议先读两页再回来。

3.1 算法 Algorithms

PDF p224
  • 算法的五大性质：输入、输出、精确性、有限性、正确性（+通用性/一般性）——判断"这段流程是不是算法"靠这五条。
  • 书中伪代码风格：类 Pascal（procedure 名、赋值 :=、while/for、缩进块）；带过程与函数两种单元。
  • 首批算法：线性搜索与二分搜索（有序前提、每次减半）；冒泡排序与插入排序。
  • 贪心算法首次亮相：找零钱问题——每步取局部最优；书中给出其正确性依赖于币制的讨论。
  • 算法正确性证明的预告（第 5 章用归纳法与 Hoare 逻辑完成）。
核心定义

算法（algorithm）：一个有限长的精确指令序列，对合法输入在有限步内产生输出并终止。二分搜索每次比较排除一半候选，最多 ⌈log₂n+1⌉ 次比较。

应用亮点
  • 在有序电话簿中查找名字
  • 编译器符号表查找
  • 找零与贪心策略

3.2 函数的增长 The Growth of Functions

PDF p239
  • 大 O 记号：f(x) 是 O(g(x)) ⟺ ∃C,k 使得 |f(x)| ≤ C|g(x)| 对所有 x>k 成立——"最终不超过 g 的常数倍"。
  • 证明 f 是 O(g) 的模板：找 C 和 k（放缩法）；证 f 不是 O(g)：反证/取极限思路。
  • 多项式的增长阶由最高次项决定：7x⁴+3x 是 O(x⁴)。
  • 大 Ω（下界：g 是 O(f)）与大 Θ（同阶：互相 O）——三件套刻画"差不多快"。
  • 增长速度链（必背）：1 < log n < n < n log n < n² < n³ < 2ⁿ < n!。n 很大时指数对多项式是碾压。
  • 常用小工具：log 的换底只差常数因子，故 O(log₂n)=O(log n)。
定理

若 f₁=O(g₁)、f₂=O(g₂)，则 f₁+f₂ = O(max(g₁,g₂) 的阶)，f₁f₂ = O(g₁g₂)——复杂度分析里"逐段估算再合并"的合法性来源。

学习提示

画 log n / n / n log n / n² / 2ⁿ 在 n=10,100,1000 的表格，直观感受"指数爆炸"——这是本章最值得动手做的一件事。

应用亮点
  • 算法横向比较
  • 数据库索引规模估算
  • 密码学参数选择（指数级困难）

3.3 算法的复杂度 Complexity of Algorithms

PDF p254
  • 最坏情形复杂度 W(n)（对规模 n 的所有输入取最大）与平均情形复杂度（需假设输入分布）。
  • 已有算法的复杂度清单：线性搜索 Θ(n)、二分搜索 Θ(log n)、冒泡/插入排序 Θ(n²)。
  • 复杂度单位是基本操作次数（比较、算术运算、位操作），也可细分为时间/空间复杂度。
  • 问题的复杂度 vs 算法的复杂度：可解（tractable，多项式时间）与不可解（intractable）；P 与 NP 的通俗介绍、NP 完全性概念预告。
  • 停机问题（halting problem）不可判定：不存在程序能判断任意程序是否停机——用对角线论证（呼应 2.5 节 Cantor）。
里程碑结果

停机问题不可判定（1936, Turing）：证明与"理发师悖论"同构。它宣告了"计算有天然的边界"——第 13 章图灵机将给出完整舞台。

易错点

Θ(n²) 的算法在 n<50 时可能快于 Θ(n log n) 的算法——大 O 刻画的是渐近行为，常数与低阶项在小规模时仍然重要。

应用亮点
  • 为数据规模选算法
  • 数据库查询计划
  • 理解密码学"困难假设"

📖 本章定义速查（中英对照）

术语一行释义
algorithm算法：有限、精确、通用、正确的指令序列
pseudocode伪代码：介于自然语言与程序之间的算法描述（附录 A3 约定）
linear / binary search线性搜索 O(n) / 二分搜索 O(log n)（需有序）
bubble / insertion sort冒泡排序、插入排序：均 O(n²)
greedy algorithm贪心算法：每步取局部最优（如找零）
f(x) is O(g(x))大 O：∃C,k 使 |f(x)|≤C|g(x)|（x>k）——渐近上界
Ω / Θ大 Ω 渐近下界 / 大 Θ 渐近精确阶
worst / average case最坏情形 / 平均情形复杂度
tractable / intractable可解（多项式时间）/ 不可解（超多项式）
halting problem停机问题：判定程序是否停机——被证明不可判定

📐 定理与关键结论一览

  1. n 次多项式 f(x)=aₙxⁿ+…+a₀ 是 O(xⁿ)——由最高次项主导
  2. 若 f₁=O(g₁)、f₂=O(g₂)，则 f₁+f₂=O(max(g₁,g₂))，f₁·f₂=O(g₁g₂)
  3. 收银员算法（cashier's algorithm）在 25/10/5/1 美分币制下用最少硬币找零（贪心正确性的经典范例）
  4. 停机问题不可判定（Turing 1936）：不存在判定任意程序停机性的程序
PDF p224原文摘录 · Short Quotation

“We will also discuss greedy algorithms, a class of algorithms used to solve optimization problems. Proofs are important in the study of algorithms.”

第 3 章开篇即强调：算法研究离不开证明——本章的每个算法之后都跟着正确性论证。

🕐 编者注 · 2026 视角（非原书内容）
  • 矩阵乘法指数 ω 的纪录已更新：原书引述的 O(n^2.3737)（Le Gall 2014）之后，2023 年 Williams–Xu–Xu–Zhou 将其改进到 ω ≤ 2.371552，2024 年 Le Gall–Urrutia 进一步到 ω < 2.3714；ω 是否等于 2 仍是公开问题。
本章关键词： 伪代码pseudocode贪心算法greedy algorithm二分搜索binary search 大O记号big-O notation大Θbig-Theta最坏情形worst case 不可解intractable停机问题halting problem

章末材料 PDF p267。

第 4 章　数论与密码学

Number Theory and Cryptography · PDF 274–353 · 80 页

19 定理（全书第一）12 个正式证明69 例题≈379 习题板块二
两千年前欧几里得研究的整除、素数与最大公约数，在 1977 年 RSA 公钥密码问世后成了互联网信任体系的数学地基。本章从整除与模运算的基本事实出发，一路推进到"数学如何直接改变世界"的高潮——RSA 加密。这是定理密度最高的一章（19 个），也是把"证明"当正式技能训练的一章：每个定理都有完整证明，建议先自己试证再看答案。

4.1 整除性与模运算 Divisibility and Modular Arithmetic

PDF p274
  • 整除 a∣b ⟺ ∃c, b=ac。基本传递性：a∣b 且 b∣c ⟹ a∣c；a∣b 且 a∣c ⟹ a∣(b+c)。
  • 除法算法（带余除法）：a = dq + r，0≤r<d，其中 d 是除数、a 是被除数、q 是商、r 是余数；q=⌊a/d⌋, r = a mod d。
  • 同余 a ≡ b (mod m) ⟺ m ∣ (a−b)。同余保持加法与乘法：a≡b, c≡d ⟹ a+c≡b+d，ac≡bd。
  • 同余类视角：mod m 把整数分成 m 个"剩余类"，钟表算术是最直观模型。
  • 注意：同余可以相乘但不能随意"约去"：4x≡4·3 (mod 8) 中 x 不必 ≡3。
核心定义

a mod b = a 除以 b 的余数。a ≡ b (mod m) 读作"a 与 b 模 m 同余"。计算机中的取模运算 % 与这里的定义一致（注意负数约定差异）。

应用亮点
  • Hash 取模
  • 时钟/日历算术
  • 校验和

4.2 整数表示与算法 Integer Representations and Algorithms

PDF p283
  • b 进制展开：n = Σ aᵢbⁱ。二进制、八进制、十六进制的展开式与相互转换（除 b 取余法 / 按权展开法）。
  • 进制转换算法的伪代码与复杂度（加法 Θ(n)、乘法 Θ(n²) 朴素）。
  • 模指数（快速幂）：bⁿ mod m 反复平方，复杂度从 Θ(n) 次乘法降到 O(log n) 次——RSA 能实用的关键一步。
  • 整数运算复杂度表：加法/乘法在 n 位整数上的位复杂度，为密码学参数选择提供依据。
学习提示

快速幂例：3⁶⁴⁴ mod 645——写成 644 = 2⁶+2⁷+2⁹，逐次平方 3,9,81,111,…，只需 9 次平方和几次乘法。亲手算一遍胜过看十遍。

应用亮点
  • 计算机二进制存储
  • 颜色码 #FF5733 的十六进制
  • 密码运算的效率

4.3 素数与最大公约数 Primes and Greatest Common Divisors

PDF p294
  • 素数：大于 1 且因子只有 1 和自身；合数反之。1 既非素也非合。
  • 算术基本定理：每个大于 1 的整数都可唯一分解为素数之积——整数系的"DNA 定律"。
  • 素数无穷多（欧几里得反证：设素数有限，构造 p₁p₂…pₙ+1）；Mersenne 素数与 GIMPS 项目。
  • 试除法判素（O(√n)）；Eratosthenes 筛法批量找素数。
  • 欧几里得算法 gcd(a,b) = gcd(b, a mod b)——人类最古老的算法之一，O(log min(a,b))。
  • Bézout 定理：gcd(a,b) 是 ax+by 形式的最小正整数（扩展欧几里得求系数 s,t）；互素、两两互素；lcm(a,b) = ab/gcd(a,b)。
必考定理

算术基本定理（唯一分解）与 Bézout 定理：gcd(a,b) = sa+tb 的最小正线性组合。后者是求模逆元（4.4 节）和证明中国剩余定理可解的核心工具。

学习提示

欧几里得算法要练到不用想就能写：gcd(252,198) → gcd(198,54) → gcd(54,36) → gcd(36,18) → 18。配合回代求 Bézout 系数。

应用亮点
  • 分数化简
  • RSA 密钥生成
  • 周期现象（行星会合）

4.4 求解同余 Solving Congruences

PDF p313
  • 线性同余 ax ≡ b (mod m)：有解 ⟺ d=gcd(a,m) ∣ b；有 d 个模 m 意义下的解。
  • 模逆元 ā：a·ā ≡ 1 (mod m)，存在 ⟺ gcd(a,m)=1，用扩展欧几里得求出——"模世界的除法"。
  • 中国剩余定理（CRT）：同余方程组模数两两互素时在模 M=m₁…mₙ 下有唯一解；逆推法构造解。
  • 费马小定理：p 素且 p∤a ⟹ aᵖ⁻¹ ≡ 1 (mod p)。用于快速计算大幂次的余数。
  • 伪素数与 Carmichael 数：费马小定理的"逆命题"会漏判——合数 n 若 bⁿ⁻¹≡1 (mod n) 称为基 b 伪素数；对所有 b 都"伪装"的是 Carmichael 数（561 最小）。
两大主力定理

费马小定理（模素数幂运算）+ 中国剩余定理（把大模数拆成小模数）——RSA 解密正确性证明的全部零件在本节配齐。

应用亮点
  • 密码学模逆计算
  • 大数幂取余比赛题
  • 同余方程组建模

4.5 同余的应用 Applications of Congruences

PDF p326
  • 哈希函数：h(k) = k mod m——把任意键压进 m 个槽；m 取素数可减少碰撞模式。
  • 伪随机数：线性同余生成器 xₙ₊₁ = (axₙ+c) mod m——"随机"背后的确定性算术。
  • 校验位：ISBN 书号、UPC 商品条码、信用卡号用加权模校验防错。
  • 古典密码热身：凯撒密码（移位）、仿射密码（ax+b mod 26）及其字母频率攻击——为下一节铺路。
学习提示

本节是"数论离生活最近"的一节：你身份证最后一位校验码、扫码支付的条码都在用模算术。找一件身边的编码验证一下。

应用亮点
  • 哈希表
  • 伪随机数生成
  • ISBN/UPC 校验位
  • 古典密码

4.6 密码学 Cryptography

PDF p333
  • 密码学词汇：明文/密文/加密/解密/密钥；密钥密码（对称）vs 公钥密码（非对称）。
  • 字符级密码：移位、仿射、维吉尼亚（多表移位）、一次一密（OTP）及其不可破性与密钥管理难题。
  • RSA 公钥密码系统（重头戏）：① 取大素数 p,q，n=pq，φ(n)=(p−1)(q−1)；② 选 e 与 φ(n) 互素，公钥 (n,e)；③ 求 d ≡ e⁻¹ (mod φ(n))，私钥 d；④ 加密 c = mᵉ mod n，解密 m = cᵈ mod n。
  • RSA 正确性证明依赖费马小定理/欧拉定理；安全性依赖"大整数分解困难"。
  • Diffie–Hellman 密钥交换：双方在公开信道协商出共享密钥（基于离散对数困难）。
  • 延伸：同态加密概念与 Gentry 的突破（2009）——在加密数据上直接计算。
RSA 迷你示例

p=3, q=11, n=33, φ=20；取 e=3（与 20 互素），d=27（3·27=81≡1 mod 20）。消息 m=2：加密 2³ mod 33 = 8；解密 8²⁷ mod 33 = 2 ✓。建议手工跑通这个小例子。

注意

RSA 是"教科书式"介绍：真实系统要加填充（如 OAEP）防攻击。理解数学原理即可，工程实现另有专门课程。

应用亮点
  • HTTPS/TLS 证书
  • 数字签名
  • 安全密钥交换
  • 加密云计算

📖 本章定义速查（中英对照）

术语一行释义
a ∣ b整除：∃c, b=ac
division algorithm带余除法：a=dq+r，0≤r<d；q=⌊a/d⌋
congruence a≡b (mod m)同余：m ∣ (a−b)；同余保持加减乘
prime / composite素数（因子仅 1 与自身）/ 合数
gcd(a,b) / lcm(a,b)最大公约数 / 最小公倍数；lcm·gcd=ab
relatively prime互素：gcd(a,b)=1；两两互素更强
Bézout coefficientsBézout 系数：满足 sa+tb=gcd(a,b) 的 s,t
base-b expansionb 进制展开：n=Σ aᵢbⁱ
pseudoprime / Carmichael伪素数（满足费马同余的合数）/ Carmichael 数（对一切基伪装）
one-time pad一次一密：密钥等长且只用一次——理论不可破
public-key cryptosystem公钥密码：加密钥公开、解密钥保密（如 RSA）

📐 定理与关键结论一览

  1. 整除性质：a∣b 且 a∣c ⟹ a∣(b+c)；a∣b ⟹ a∣bc
  2. 除法算法：q、r 存在且唯一
  3. 算术基本定理：每个大于 1 的整数唯一分解为素数之积
  4. 素数无穷多（欧几里得反证：p₁p₂…pₙ+1 必有新素因子）
  5. Bézout 定理：gcd(a,b) 是 ax+by 的最小正值
  6. 费马小定理：p 素、p∤a ⟹ a^(p−1)≡1 (mod p)
  7. 中国剩余定理：模数两两互素的同余方程组模 M 有唯一解
  8. RSA 正确性：cᵈ=(mᵉ)ᵈ≡m (mod n)（由费马小定理/欧拉定理推出）
PDF p338原文摘录 · Short Quotation

“When such cryptosystems are used, knowing how to send an encrypted message does not help decrypt messages.”

RSA 一节的原文点题句：公钥密码的精髓——会加密不等于会解密。

PDF p294原文摘录 · Short Quotation

“…known that there are infinitely many primes; the proof of this fact, found in the works of Euclid, is famous for its elegance and beauty. We will discuss the distribution of primes among the integers. We will describe some of the results about primes found by mathematicia”

欧

🕐 编者注 · 2026 视角（非原书内容）
  • 最大已知 Mersenne 素数已易主：2^136,279,841 − 1（第 52 个，41,024,320 位，2024 年 10 月 GIMPS/Luke Durant，首个由 GPU 发现的纪录）。
  • 孪生素数有界间隔：原书时代的 246（Polymath8b, 2014）保持纪录逾十年后，2026 年被打破——8 月的预印本改进到 240，其后 AI 辅助（附 Lean 形式化）的更小界（约 186）亦有报道，尚待完全确认；孪生素数猜想本身仍开放。
  • 密码学进入后量子时代：NIST 于 2024 年 8 月发布首批后量子标准 FIPS 203（ML-KEM/Kyber）、FIPS 204（ML-DSA/Dilithium）、FIPS 205（SLH-DSA/SPHINCS+）；RSA 的安全性依赖的“大数分解困难”在大型量子计算机（Shor 算法）下不复存在，业界已开始迁移。
本章关键词： 整除divisibility同余congruence素数prime 算术基本定理fundamental theorem of arithmetic欧几里得算法Euclidean algorithmBézout系数 模逆元modular inverse中国剩余定理Chinese remainder theorem费马小定理Fermat's little theorem 伪素数pseudoprimeRSADiffie–Hellman

章末材料 PDF p347。本章传记：Euclid、Eratosthenes、Fermat、Mersenne、Euler、Goldbach、Carmichael、Rivest、Shamir、Adleman、Cocks、Gentry。

第 5 章　归纳与递归

Induction and Recursion · PDF 354–427 · 74 页

10 个递归算法49 例题≈368 习题板块二
归纳法是离散世界的主引擎：证明对所有自然数成立靠它，定义无限结构（字符串、表达式、树）也靠它。本章把"证明的归纳"（数学归纳法、强归纳、良序）与"构造的归纳"（递归定义、递归算法）合在一处，最后用 Hoare 逻辑证明程序正确性收束——五大主题在此全部交汇。

5.1 数学归纳法 Mathematical Induction

PDF p354
  • 归纳法两步曲：基础步 P(1) 真；归纳步 ∀k，P(k) ⟹ P(k+1)。结论：∀n P(n)。
  • "为什么归纳有效"：反证 + 良序原理（最小反例法）——理解这一点才算真正懂归纳。
  • 标准应用：求和公式 1+2+…+n = n(n+1)/2、不等式（2ⁿ < n!、Bernoulli 不等式）、整除性、集合恒等式。
  • 几何应用：直尺三角剖分、骨牌/拼图覆盖（前向/后向归纳思想）。
  • 归纳谬误案例："所有马同色"——找出归纳步在 n=1→2 处断裂的原因，是本节最有价值的练习。
  • 写归纳证明的三段式模板：声明方法 → 基础步 → 归纳步（明确写出归纳假设 IH）。
弱归纳原理

若 P(1) 成立，且 P(k)⟹P(k+1) 对所有正整数 k 成立，则 P(n) 对所有正整数 n 成立。归纳假设（IH）必须在归纳步中被真正使用。

学习提示

习题建议按"求和 → 不等式 → 整除 → 几何"顺序做，每类至少 3 题；写明"由归纳假设 P(k)…"这句话，防止跳步。

应用亮点
  • 程序循环正确性
  • 递归算法复杂度
  • 组合恒等式证明

5.2 强归纳与良序 Strong Induction and Well-Ordering

PDF p377
  • 强归纳（第二数学归纳法）：归纳假设是"P(1),…,P(k) 全真"，适合递推依赖多个更小情形的问题。
  • 三个经典应用：① 正整数唯一分解（强归纳重构算术基本定理）；② 游戏必胜策略（L 型骨牌覆盖 2ᵏ×2ᵏ 棋盘）；③ 递归定义的良基性。
  • 良序公理：正整数的每个非空子集有最小元。与归纳法等价，常用于反证（最小反例法）。
  • 弱归纳 vs 强归纳 vs 良序：三者等价，选用看哪个的"假设形式"更贴合递推结构。
强归纳原理

若 P(1) 真，且 [P(1)∧P(2)∧…∧P(k)] ⟹ P(k+1)，则 ∀n P(n)。例：每张面值 ≥2 的邮票都能用 4 分和 5 分组合（4,5,8,9,10 起步后连续）。

应用亮点
  • 博弈树必胜证明
  • 递归算法终止性
  • 构造性计数

5.3 递归定义与结构归纳法 Recursive Definitions and Structural Induction

PDF p388
  • 递归定义两件套：基础步给出初始对象 + 递归步由旧对象造新对象。
  • 典型递归定义的集合：字母表 Σ 上的字符串 Σ*（空串 λ 起步；w∈Σ* 且 x∈Σ ⟹ wx∈Σ*）、连接运算 |xy| = |x|+|y|。
  • 良构公式（well-formed formula）：命题逻辑合式公式的递归定义——第 1 章的"括号永远不会不配对"有了严格根据。
  • 递归定义的树：有根树、满二叉树、满二叉树的高度 h(T)——第 11 章的前置语言。
  • 结构归纳法：对递归定义的结构做归纳——基础步对初始对象验证，递归步假设"子结构满足性质"再验证新对象。证明 |w₁w₂| = |w₁|+|w₂| 是模板题。
核心方法

结构归纳法 = 作用在"递归定义结构"上的归纳法。写法："对字符串长度归纳"或"对生成步骤数归纳"均可，本质相同。

应用亮点
  • 编译器语法检查
  • LISP/Scheme 的 S-表达式
  • JSON/XML 文档结构

5.4 递归算法 Recursive Algorithms

PDF p404
  • 递归算法：把问题化为同型更小实例求解 + 基例。正确性 = 基例正确 + 归纳步正确（归纳法证）。
  • 例题阵容：递归幂 bⁿ、gcd 递归版、汉诺塔（2ⁿ−1 步）、二分搜索递归版、归并排序（分治代表）。
  • 递归与迭代互转：尾递归可机械转循环；递归的空间代价（调用栈）与展开技巧。
  • 递归算法复杂度用递推关系表达——直接为第 8 章（线性递推 + 主定理）铺垫。
学习提示

汉诺塔递推 T(n) = 2T(n−1)+1：写前 5 项 (1,3,7,15,31) 猜 T(n)=2ⁿ−1，再用归纳证明——"实验→猜想→证明"的完整示范。

应用亮点
  • 分治排序
  • 树的遍历（第 11 章）
  • 语法分析器

5.5 程序正确性 Program Correctness

PDF p416
  • Hoare 三元组 {p} S {q}：若 S 执行前 p 真且 S 终止，则执行后 q 真——程序规范的形式化。
  • 部分正确性（不管是否终止）vs 完全正确性（部分正确 + 终止性）。
  • 复合赋值规则：{p(x/e)} x := e {p}；条件语句与复合语句的推理规则。
  • 循环不变量（loop invariant）：循环每轮保持真的性质；证明模式 = 进入循环前成立 + 每轮保持 + 退出时得到目标。
  • 用归纳法证"不变量在第 k 轮后成立"——本章证明工具的最终合流。
核心概念

循环不变量示例：证明 while i≤n: s := s+i 计算 Σi——不变量"s = 0+1+…+(i−1)"。这套方法就是工业界形式化验证（如航天软件）的雏形。

应用亮点
  • 形式化验证
  • 编译器优化合法性
  • Hoare 逻辑 → DSL 验证

📖 本章定义速查（中英对照）

术语一行释义
basis / inductive step归纳法基础步 P(1) / 归纳步 P(k)⟹P(k+1)
inductive hypothesis归纳假设（IH）：归纳步中可使用的 P(k)
strong induction强归纳：假设 P(1)…P(k) 全部成立
well-ordering property良序性：正整数非空子集必有最小元
recursively defined set递归定义的集合：基础步 + 递归步（串、良构公式、树）
structural induction结构归纳法：对递归定义结构按“生成方式”归纳
recursive algorithm递归算法：把问题化为同型更小实例 + 基例
Hoare triple {p}S{q}Hoare 三元组：前置条件、程序段、后置条件
loop invariant循环不变量：循环每轮保持为真的性质
partial / total correctness部分正确性（若终止则正确）/ 完全正确性（+终止）

📐 定理与关键结论一览

  1. 数学归纳法原理：P(1) + ∀k(P(k)⟹P(k+1)) ⟹ ∀n P(n)
  2. 强归纳与良序原理均与弱归纳等价
  3. 多边形三角剖分：n 边形恰分为 n−2 个三角形
  4. Lamé 定理：欧几里得算法求 gcd(a,b)（a≥b）所需除法次数 ≤ 5·log₁₀b
  5. 求和公式 1+2+…+n = n(n+1)/2（归纳法第一例）
译名备注

译名备注：well-formed formula 国内标准译名是合式公式（本页“良构公式”即此概念）；strong induction 又称第二数学归纳法；loop invariant 又译循环不变式；well-ordering property 通译良序原理。

本章关键词： 数学归纳法mathematical induction归纳假设inductive hypothesis强归纳strong induction 良序well-ordering递归定义recursive definition良构公式well-formed formula 结构归纳structural induction递归算法recursive algorithmHoare三元组循环不变量loop invariant

章末材料 PDF p421。本章传记：Fibonacci、Dirichlet、Well-ordering 相关的数学史等。

第 6 章　计数

Counting · PDF 428–491 · 64 页

≈648 习题（全书第一）21 个组合证明72 例题板块三 · 组合分析
计数是组合分析的核心训练场：密码个数、车牌个数、比赛场次、中奖概率的分母——都要数。本章从加法/乘法原理出发，经过鸽笼原理的"存在性魔法"，到排列组合、二项式恒等式与广义计数模型。习题量全书第一（≈648 道），是刷题收益最高的一章。Rosen 特别强调：这里练的是"分析问题的能力"，不是背公式。

6.1 计数基础 The Basics of Counting

PDF p428
  • 乘法原理：任务分 r 步、每步 nᵢ 种选法 ⟹ 共 n₁n₂…nᵣ 种。
  • 加法原理：不相交的 r 类各 nᵢ 种 ⟹ 共 n₁+…+nᵣ 种。
  • 减法原理（补集）：|A| = |U| − |A̅|——"至少有一个"型问题先算补集"都没有"。
  • 除法原理：若每个对象被数了 d 次，则对象数 = 总数/d——组合数 C(n,r) 的来历。
  • 树图（tree diagram）辅助小规模枚举；"单射函数个数 n!/(n−m)!"型问题。
  • 复杂问题拆解示范：变量名规则、密码规则、IP 地址块个数——多原理串联。
做题流程

① 识别"有序 or 无序"、"可重复 or 不可重复"→ ② 选原理组合 → ③ 小例子验证（n=3 手数一遍）→ ④ 套公式。跳过 ①③ 是大多数错误的来源。

应用亮点
  • 密码空间大小
  • IP 地址计数
  • 菜单组合问题
  • 比赛赛程

6.2 鸽笼原理 The Pigeonhole Principle

PDF p443
  • 简单形式：N+1 个物品放进 N 个盒子 ⟹ 某盒至少 2 个。例：367 人中必有两人同天生日。
  • 广义鸽笼：N 个物品 k 个盒 ⟹ 某盒至少 ⌈N/k⌉ 个。
  • 经典应用模式："前缀和"技巧——任取 n+1 个数必有两个的差被 n 整除（余数盒子）；"连续子段和被 n 整除"。
  • 照片/序列应用：一列 n²+1 个互异数中必有长度 n+1 的递增或递减子列（Erdős–Szekeres）。
  • 拉姆齐数入门：R(3,3)=6——6 人中必有 3 人互识或互不识。组合存在性的巅峰美学。
定理

广义鸽笼原理：N = kq + r（0≤r<k）个球进 k 盒，则必有盒子至少 q+1 个（当 r>0）。⌈N/k⌉ = q+1。

学习提示

鸽笼题的难点是"设计盒子"：把题目对象映射到"余数/配对/子段"等抽屉。见到"必存在两个…相同"就要条件反射想到鸽笼。

应用亮点
  • 哈希碰撞必然性
  • 生日悖论
  • 社交网络中必存的结构
  • 数据压缩极限

6.3 排列与组合 Permutations and Combinations

PDF p451
  • 排列（有序）：P(n,r) = n!/(n−r)!；P(n,n)=n!。
  • 组合（无序）：C(n,r) = n!/(r!(n−r)!)；对称性 C(n,r)=C(n,n−r)。
  • 何时用哪个：给 n 个人安排座位/排名 → 排列；选委员会/抽手牌 → 组合。
  • 组合即"选子集"：C(n,r) = n 元集合的 r 元子集个数；也等于 n 到 r 元集的"不计序单射"。
  • 带约束混合题：先分组、再排座；"某人必须相邻"用捆绑法，"互不相邻"用插空法。
核心公式

P(n,r) = n(n−1)…(n−r+1)　C(n,r) = P(n,r)/r!　组合 = 排列 ÷ 自身重排。

应用亮点
  • 彩票中奖组合数
  • 扑克牌型
  • 赛程编排

6.4 二项式系数与恒等式 Binomial Coefficients and Identities

PDF p460
  • 二项式定理：(x+y)ⁿ = Σ C(n,k) xᵏyⁿ⁻ᵏ；特殊求和 Σ C(n,k) = 2ⁿ、Σ(−1)ᵏC(n,k) = 0。
  • Pascal 恒等式：C(n+1,k) = C(n,k−1) + C(n,k)——Pascal 三角形的生成规则。
  • Vandermonde 恒等式：C(m+n,r) = Σ C(m,r−j)C(n,j)——"从两队混选 r 人"的双重计数。
  • 组合证明（combinatorial proof）：证明恒等式的利器——同一个量用两种方式数。本书 21 处组合证明示范大多在此章。
  • 推广：ΣC(n,k)² = C(2n,n)（Vandermonde 的对称情形）等经典恒等式家族。
必背恒等式

Σₖ C(n,k) = 2ⁿ（每个子集数一次）；C(n+1,k)=C(n,k−1)+C(n,k)（按"是否含固定元素"分类）——两者都建议写出组合证明而非代数证明。

学习提示

"用两种方法数同一个集合"是组合证明的全部哲学；代数恒等式变形前先问一句"两边各数的是什么"。

应用亮点
  • (a+b)ⁿ 展开
  • 子集计数
  • 路径计数（网格最短路）

6.5 广义排列与组合 Generalized Permutations and Combinations

PDF p468
  • 可重复排列（无限制重复）：nᵣ 个。可重复组合（类型可选多次、不计序）：C(n+r−1, r)——"隔板法"。
  • 多重集排列（重复次数受限）：n 个物体含 n₁ 个 A、n₂ 个 B…（n₁+n₂+…=n），排列数 n!/(n₁!n₂!…nₖ!)。
  • "不可区分物体进可区分盒子"= 多重集排列；"可区分物体进不可区分盒子"引导 Stirling 数（习题层）。
  • 典型场景清单：分发糖果、单词重排（MISSISSIPPI = 11!/(4!4!2!)）、多骰子点数组合。
  • 四大计数模型对照表（是否有序 × 是否可重复）——本书计数体系的总纲，务必自制一遍。
模型速查

① 有序不重复：P(n,r)；② 无序不重复：C(n,r)；③ 有序可重复：nʳ；④ 无序可重复：C(n+r−1,r)；⑤ 物体可分组（有重复标签）：n!/(n₁!…nₖ!)。

应用亮点
  • 多义词袋模型（NLP）
  • 多骰子/抽奖
  • 资源分配

6.6 生成排列与组合 Generating Permutations and Combinations

PDF p480
  • 为什么要"生成"：穷举搜索、测试用例覆盖、组合优化都要按序枚举所有对象。
  • 字典序下一个排列算法：从右找第一个降序位 → 与右边刚大于它的元素交换 → 反转后缀。C++ 的 next_permutation 同款。
  • 下一个 r-组合的字典序算法；r-组合与二进制串/子集的一一对应。
  • 逆序数（inversion）概念引入：排列的"混乱度"度量——第 8 章?（用于排序算法下界）。
  • 复杂度：每个"下一对象"只需 O(n) 时间，总枚举成本与对象数成正比。
学习提示

对 {1,2,3,4} 手工按字典序写出全部 24 个排列，再写出全部 C(4,2)=6 个组合——这 30 分钟投入对理解算法极划算。

应用亮点
  • 全排列搜索（TSP 精确解）
  • 测试组合覆盖
  • 组合博弈枚举

📖 本章定义速查（中英对照）

术语一行释义
product rule乘法原理：r 步各 nᵢ 种 ⟹ 共 Πnᵢ 种
sum rule加法原理：不相交 r 类各 nᵢ 种 ⟹ 共 Σnᵢ 种
subtraction / division rule减法原理（补集计数）/ 除法原理（均摊 d 次则除以 d）
pigeonhole principle鸽笼原理：k+1 个物体进 k 盒必有一盒 ≥2 〔又译：抽屉原理（国内教材更常用）／鸽巢原理〕
permutation P(n,r)排列：有序选取，n!/(n−r)! 〔国内教材常记作 A(n,r)（排列数）〕
combination C(n,r)组合：无序选取，n!/(r!(n−r)!)
binomial coefficient二项式系数 C(n,k)：也计数 n 元集的 k 元子集
combinatorial proof组合证明：用两种方式数同一集合证明恒等式
next permutation字典序下一排列：找降序位→交换→反转后缀

📐 定理与关键结论一览

  1. 鸽笼原理：k+1 物体放入 k 盒 ⟹ 某盒至少 2 个
  2. 广义鸽笼：N 物体入 k 盒 ⟹ 某盒至少 ⌈N/k⌉ 个
  3. Erdős–Szekeres：n²+1 个互异实数必含长 n+1 的严格单调子列
  4. 二项式定理：(x+y)ⁿ = Σ C(n,k)xᵏyⁿ⁻ᵏ；推论 Σ C(n,k)=2ⁿ
  5. Pascal 恒等式：C(n+1,k)=C(n,k−1)+C(n,k)
  6. Vandermonde：C(m+n,r)=Σ C(m,r−j)C(n,j)
  7. Ramsey 数 R(3,3)=6（六人宴会定理）
PDF p444原文摘录 · Short Quotation

“THE PIGEONHOLE PRINCIPLE If k is a positive integer and k + 1 or more objects are placed into k boxes, then there is at least one box containing at least two objects.”

鸽笼原理的原文陈述——全书最“朴素”却应用最广的定理之一。

本章关键词： 乘法原理product rule鸽笼原理pigeonhole principle排列permutation 组合combination二项式定理binomial theoremPascal三角形 Vandermonde恒等式组合证明combinatorial proof隔板法多重集排列字典序

章末材料 PDF p484。本章习题分：练习、补充练习、计算机课题（如生成组合对象）、计算探索、写作课题。

第 7 章　离散概率

Discrete Probability · PDF 492–549 · 58 页

16 定理12 定义50 例题≈224 习题板块三
概率 = 计数的结果除以总可能数。本章把第 6 章的计数能力转化成不确定性推理：从拉普拉斯的古典概率出发，建立公理化概率、条件概率与独立性，经过贝叶斯定理（垃圾邮件过滤的原理），到随机变量、期望与方差。这一章是机器学习、算法随机化（随机快排、蒙特卡洛）的概率第一课。

7.1 离散概率导论 An Introduction to Discrete Probability

PDF p492
  • 试验/样本空间/事件：掷骰子 S={1,…,6}；事件 E ⊆ S。
  • 拉普拉斯概率（等可能模型）：p(E) = |E|/|S|——计数就是概率。
  • 典型题：抽扑克牌型概率、掷两骰点数和、生日问题（23 人中两人同生日概率 >50%）。
  • "等可能"判别失误是主要风险：两孩问题、"至少一个男孩"的条件表述。
  • 概率方法（probabilistic method）初见：用随机性证明存在性（习题/正文引子）。
核心定义

事件 E 的（拉普拉斯）概率 = E 的结果数 ÷ 样本空间结果数，前提是所有结果等可能。p(E̅)=1−p(E) 立即可得。

应用亮点
  • 彩票与赌局
  • 扑克牌型
  • 密码猜中概率

7.2 概率论 Probability Theory

PDF p500
  • 三条公理：非负性 p(E)≥0；归一化 p(S)=1；可加性（互斥事件概率相加）。全部概率论由此推导。
  • 组合事件的概率：容斥的有限形式 p(A∪B)=p(A)+p(B)−p(A∩B)。
  • 条件概率：p(E|F) = p(E∩F)/p(F)（p(F)>0）——"信息更新后的世界"。
  • 独立性：p(E∩F)=p(E)p(F) ⟺ p(E|F)=p(E)。独立 vs 互斥是两回事（互斥事件一般不独立！）。
  • 全概率公式：按划分 {Fᵢ} 分情况 p(E) = Σ p(E|Fᵢ)p(Fᵢ)——贝叶斯的另一半。
  • 伯努利试验与二项分布：n 次独立试验恰 k 次成功的概率 C(n,k)pᵏ(1−p)ⁿ⁻ᵏ。
易错点

"互斥"（不能同时发生）与"独立"（互不影响）经常被混为一谈：互斥事件的発生会改变彼此概率，恰恰不独立。

应用亮点
  • 药物试验分组
  • 蒙特卡洛估算
  • 密码猜测重试模型

7.3 贝叶斯定理 Bayes' Theorem

PDF p517
  • 贝叶斯定理：p(F|E) = p(E|F)p(F) / p(E)——由"果"反推"因"的概率。
  • 语言体系：先验 p(F)（看到证据前）→ 证据 E → 后验 p(F|E)（看到证据后）。贝叶斯主义的核心循环。
  • 多假设版（全概率展开分母）：p(Hᵢ|E) = p(E|Hᵢ)p(Hᵢ)/Σⱼp(E|Hⱼ)p(Hⱼ)。
  • 经典案例：疾病检测的基率谬误——患病率 1%、灵敏度 95% 时，检测阳性者真患病的概率其实不高（分母被大量假阳性稀释）。
  • 应用：垃圾邮件过滤（朴素贝叶斯的骨架）、法庭证据推理、机器学习分类器。
必会计算

垃圾邮件例：垃圾邮件占 50%，"invoice"在垃圾邮件中出现概率 80%、正常邮件 10%。收到含 invoice 的邮件是垃圾的概率 = 0.8×0.5/(0.8×0.5+0.1×0.5) ≈ 0.889。画树状图列全概率分母。

应用亮点
  • 垃圾邮件过滤
  • 医学诊断
  • 自动驾驶传感器融合

7.4 期望与方差 Expected Value and Variance

PDF p526
  • 随机变量 X：样本空间 → 实数的函数；分布 = X 取各值的概率列表。
  • 期望 E(X) = Σ x·p(X=x)（均值）；期望的线性性：E(aX+b)=aE(X)+b，E(X+Y)=E(X)+E(Y)（不需要独立！）——算法分析（随机排序比较次数）的头号工具。
  • 独立时 E(XY)=E(X)E(Y)。方差 V(X)=E(X²)−E(X)²；V(aX+b)=a²V(X)。
  • 几何分布（首次成功）、二项分布的期望 np 与方差 np(1−p)。
  • Chebyshev 不等式：P(|X−μ|≥rσ) ≤ 1/r²——不看分布形状也能给出偏离上界。
定理

期望线性性是"概率方法"证明存在性的引擎：随机排序平均比较 O(n log n) 次 ⟹ 存在这么快的确定性算法——期望给存在性兜底。

应用亮点
  • 随机化算法平均分析
  • 赌博/保险定价
  • A/B 测试期望收益

📖 本章定义速查（中英对照）

术语一行释义
experiment / sample space试验 / 样本空间 S（所有可能结果）
event事件：S 的子集
Laplace probability拉普拉斯概率 p(E)=|E|/|S|（等可能模型）
probability axioms概率三公理：非负、归一、互斥可加
complement rule补事件规则 p(Ē)=1−p(E)
conditional probability p(E|F)条件概率 p(E∩F)/p(F)
independence独立：p(E∩F)=p(E)p(F)（≠互斥！）
random variable / distribution随机变量（样本空间→实数的函数）/ 其分布
expectation E(X)期望：Σ x·p(X=x)；线性性 E(X+Y)=E(X)+E(Y) 无条件成立
variance V(X)方差：E(X²)−E(X)²
Bernoulli / binomial distribution伯努利试验 / 二项分布 B(n,p)：恰 k 次成功
geometric distribution几何分布：首次成功在第 k 次，p=(1−p)^(k−1)p

📐 定理与关键结论一览

  1. 补事件：p(Ē)=1−p(E)
  2. 概率容斥：p(E₁∪E₂)=p(E₁)+p(E₂)−p(E₁∩E₂)
  3. 贝叶斯定理：p(F|E)=p(E|F)p(F)/p(E)
  4. 期望线性性：E(aX+bY)=aE(X)+bE(Y)（不要求独立）
  5. 独立乘积：X,Y 独立 ⟹ E(XY)=E(X)E(Y)、V(X+Y)=V(X)+V(Y)
  6. Chebyshev 不等式：P(|X−μ|≥rσ) ≤ 1/r²
PDF p517原文摘录 · Short Quotation

“…messages that are spam. We will see that we can determine the likelihood that an incoming e-mail message is spam using the occurrence of words in the message. To determine this likelihood, we need to know the percentage of incoming messages that are spam, the percenta”

贝

本章关键词： 样本空间sample space事件event条件概率conditional probability 独立性independence贝叶斯定理Bayes' theorem先验/后验prior/posterior 随机变量random variable期望expectation方差varianceChebyshev不等式伯努利试验Bernoulli trial

章末材料 PDF p543。本章传记：Bayes、Bernoulli、Cardano、Laplace、Chebyshev、Bienaymé。

第 8 章　高级计数技术

Advanced Counting Techniques · PDF 550–621 · 72 页

13 定理59 例题≈346 习题板块三
第 6 章数"静态集合"，本章数"动态过程"：递推关系刻画序列如何演化（Fibonacci、汉诺塔），分治递推刻画算法复杂度，生成函数把整个序列装进一个幂级数里做代数，容斥原理解决"至少一个"型重叠计数。学完本章，你同时拥有了算法复杂度分析（主定理）和组合恒等式机器（生成函数）两件重武器。

8.1 递推关系的应用 Applications of Recurrence Relations

PDF p550
  • 递推关系 = 用前面的项定义当前项；初始条件 + 递推式 = 序列的完整定义。
  • 建模案例：Fibonacci 兔子、汉诺塔 T(n)=2T(n−1)+1、复利、码字不含连续 0 的个数 aₙ=aₙ₋₁+aₙ₋₂。
  • 动态规划视角：递推 + 记忆化 = 高效算法（最长递增子序列等习题模型）。
  • 递推还能定义集合/结构（与 5.3 呼应），本章专注数值型。
学习提示

建模三板斧：定义 aₙ 的含义（至关重要）→ 找"最后一步"的分类 → 每类用更小的 a 表示。写清 aₙ 语义，递推自然浮出。

应用亮点
  • 人口/复利模型
  • 动态规划基础
  • 斐波那契与黄金比例

8.2 求解线性递推关系 Solving Linear Recurrence Relations

PDF p563
  • 线性齐次常系数递推 aₙ = c₁aₙ₋₁ + … + cₖaₙ₋ₖ 的求解三步：写特征方程 rᵏ = c₁rᵏ⁻¹+…+cₖ → 解根 → 通解。
  • 单根情形：aₙ = Σ Aᵢrᵢⁿ，系数由初始条件解线性方程组。Fibonacci：r²=r+1 ⟹ φ 与 ψ，得 Binet 公式。
  • 重根情形：r 的 m 重根贡献 (A₀+A₁n+…+A_{m−1}n^{m−1})rⁿ。
  • 非齐次（带常数项 F(n)）：通解 = 齐次通解 + 一个特解（按 F(n) 形状猜特解）。
  • 验证答案：代回初始条件 + 代回递推式各验一次。
必练例题

aₙ=5aₙ₋₁−6aₙ₋₂，a₀=1,a₁=2：特征方程 r²−5r+6=0 ⟹ r=2,3 ⟹ aₙ=A·2ⁿ+B·3ⁿ ⟹ A=B=? 动手解出并验证。Fibonacci 的 Binet 公式 Fₙ=(φⁿ−ψⁿ)/√5 必须亲手推一遍。

应用亮点
  • 算法封闭复杂度
  • 金融复利闭式
  • 数列竞速题

8.3 分治算法与递推关系 Divide-and-Conquer Algorithms and Recurrence Relations

PDF p576
  • 分治递推：f(n) = a·f(n/b) + g(n)（分 a 份、每份 n/b，合并代价 g(n)）。
  • 实例：二分搜索 f(n)=f(n/2)+1；归并排序 f(n)=2f(n/2)+n；快排期望；大整数乘法 Karatsuba f(n)=3f(n/2)+n。
  • 迭代展开法：逐层代入求和——自己推一遍归并排序的 n log n。
  • 主定理（Master Theorem）：比较 g(n) 与 n^{log_b a} 的阶，三种情形给闭式——算法课必考。
主定理速记

f(n)=af(n/b)+nᵈ：① d>log_b a ⟹ Θ(nᵈ)；② d=log_b a ⟹ Θ(nᵈlog n)；③ d<log_b a ⟹ Θ(n^{log_b a})。代入 (a,b,d)=(2,2,1) 得归并排序 Θ(n log n)。

应用亮点
  • 归并/快速排序
  • 大整数乘法
  • 最近点对

8.4 生成函数 Generating Functions

PDF p586
  • 序列 {aₖ} 的生成函数：G(x) = Σ aₖxᵏ（无穷级数当"编码"用，不关心收敛）。
  • 常用封闭式：1/(1−x) ↔ 全 1 序列；1/(1−x)² ↔ k+1；1/(1−xⁿ) ↔ 周期选票；(1+x)ⁿ ↔ C(n,k)。
  • 卷积 = 多项式乘法：G(x)H(x) 的系数是卷积 Σaᵢb_{k−i}——"两阶段选择合计 k 个"的计数。
  • 三大用途：① 解递推（初始条件当系数约束）；② 证组合恒等式（比较系数）；③ 计数（每种物品的"选票"相乘，隔板法的代数化）。
  • 广义二项式系数 C(u,k) = u(u−1)…(u−k+1)/k!（u 为实数）——牛顿二项式定理。
学习提示

把生成函数当"挂账的账本"：xⁿ 项系数记录"恰好 n 个"的方案数。先练 3 道封闭式互转，再做计数题。

应用亮点
  • 组合恒等式证明机器
  • .partition 计数
  • 概率母函数

8.5 容斥 Inclusion–Exclusion

PDF p602
  • 两集合 |A∪B|=|A|+|B|−|A∩B|；三集合再加回三人交减四人交……
  • 容斥原理：|A₁∪…∪Aₙ| = Σ|Aᵢ| − Σ|Aᵢ∩Aⱼ| + … + (−1)ⁿ⁺¹|A₁∩…∩Aₙ|。
  • 补集形式数"一个都不满足"：|U| − |并集|，正负交错求和。
  • 直觉：每个元素被数 2ⁿ⁻¹ 次，正负相消后恰数 1 次——证明用二项式定理。
记忆法

"加上单、减去双、加回三……"奇数次交带 (−1)^{k+1}。做题画 Venn 图核对前两项再套公式。

应用亮点
  • 素数筛选计数
  • 错排（下节）
  • 多条件并查询

8.6 容斥的应用 Applications of Inclusion–Exclusion

PDF p608
  • 错排（derangement）Dₙ：n 个人帽子全拿错的排列数 Dₙ = n!·Σ(−1)ᵏ/k! ≈ n!/e。帽子检查员问题。
  • 欧拉函数 φ(n)：≤n 且与 n 互素的个数，用容斥按素因子去重 φ(n)=n·Π(1−1/pᵢ)——RSA 里的 φ(n) 在此严密落地。
  • 满射计数：从 m 元集到 n 元集的映上函数个数 = Σ(−1)ᵏC(n,k)(n−k)ᵐ。
  • "没有约束被违反"型的总数 = 无约束总数 − 至少违反一个（容斥）。
名题

帽子检查问题：n→∞ 时无人拿对帽子的概率 → 1/e ≈ 0.368。错排数 D₁₀ = 1334961，可作为练手。

应用亮点
  • RSA 的 φ(n)
  • 任务分配错误率
  • 满射/哈希覆盖

📖 本章定义速查（中英对照）

术语一行释义
recurrence relation递推关系：用前面的项定义 aₙ；初始条件补全定义
linear homogeneous (degree k)线性齐次常系数递推：aₙ=c₁aₙ₋₁+…+cₖaₙ₋ₖ
characteristic equation特征方程：rᵏ=c₁rᵏ⁻¹+…+cₖ——解递推的钥匙
divide-and-conquer分治递推：f(n)=a·f(n/b)+g(n)
master theorem主定理：比较 n^d 与 n^(log_b a) 给三情形闭式 〔又译：主方法（主定理）〕
generating function G(x)生成函数：G(x)=Σ aₖxᵏ——把序列编码成幂级数 〔又译：母函数（国内组合教材常用）〕
extended binomial coefficient广义二项式系数 C(u,k)，u 为实数
inclusion–exclusion容斥原理：|并| = Σ|单|−Σ|双|+…
derangement Dₙ错排：n 元素全不在原位的排列数 〔又译：更列／错位排列〕
Euler phi φ(n)欧拉函数：≤n 且与 n 互素的整数个数

📐 定理与关键结论一览

  1. 二阶单根：r²−c₁r−c₂=0 有两根 r₁,r₂ ⟹ aₙ=α₁r₁ⁿ+α₂r₂ⁿ
  2. 二阶重根：唯一根 r ⟹ aₙ=(α₁+α₂n)rⁿ
  3. k 阶互异根通解：aₙ=Σ αᵢrᵢⁿ
  4. 主定理：f(n)=af(n/b)+nᵈ ⟹ Θ(n^{log_b a}) 或 Θ(nᵈlog n) 或 Θ(nᵈ)
  5. 容斥原理：|A₁∪…∪Aₙ|=Σ|Aᵢ|−Σ|Aᵢ∩Aⱼ|+…+(−1)ⁿ⁺¹|∩Aᵢ|
  6. 错排公式：Dₙ=n!·Σ(−1)ᵏ/k! ≈ n!/e
  7. 欧拉函数：φ(n)=n·Π(1−1/pᵢ)（pᵢ 遍历 n 的素因子）
PDF p586原文摘录 · Short Quotation

“The generating function for the sequence a₀, a₁, … of real numbers is the infinite series G(x)=a₀+a₁x+a₂x²+…”

生成函数的原文定义——把整个序列“装进”一个级数，卷积即多项式乘法。

本章关键词： 递推关系recurrence relation特征方程characteristic equation分治divide-and-conquer 主定理master theorem生成函数generating function卷积convolution 容斥原理inclusion–exclusion错排derangement欧拉函数Euler phi function

章末材料 PDF p615。本章传记：Catalan、Bellman（动态规划）、Hardy 与 Ramanujan（数论分析）等。

第 9 章　关系

Relations · PDF 622–695 · 74 页

24 定义97 例题≈403 习题板块四 · 离散结构
关系 = 笛卡尔积的子集，一句话定义却撑起了庞大的结构世界：数据库的关系模型（SQL 的数学基础）、等价关系与分类、偏序与排序、传递闭包与最短路径。本章从关系的三大性质（自反/对称/传递）出发，一路走到 Hasse 图与拓扑排序。9.2 节的数据库操作是与工程衔接最紧密的几页书之一。

9.1 关系及其性质 Relations and Their Properties

PDF p622
  • 二元关系 R ⊆ A×B；A 上的关系 R ⊆ A×A。xRy ⟺ (x,y)∈R。
  • 五大性质：自反（∀a, aRa）、对称（aRb ⟹ bRa）、反对称（aRb∧bRa ⟹ a=b）、传递（aRb∧bRc ⟹ aRc）、非自反（∀a, ¬aRa）。
  • 注意：对称与反对称不矛盾（可同时成立，如 "="；也可都不成立）。
  • 关系的组合 S∘R：幂 Rⁿ 递归定义（R¹=R，Rⁿ⁺¹=Rⁿ∘R）——为传递闭包铺路。
  • n 元集上共有 2^(n²) 个关系；计数具有某性质关系数是经典习题。
核心定义

自反（reflexive）、对称（symmetric）、反对称（antisymmetric）、传递（transitive）。判别利器：关系矩阵对角线（自反）、矩阵对称性（对称）、有向图自环。

速查表

常见关系性质盘点：=（自反对称传递）；≤（自反反对称传递）；"整除"（同 ≤）；"与…同姓"（自反对称不传递?——对称但未必传递）；<（反对称传递非自反）。

应用亮点
  • 社交图谱（关注关系）
  • 版本依赖
  • 家谱亲缘

9.2 n 元关系及其应用 n-ary Relations and Their Applications

PDF p634
  • n 元关系：A₁×…×Aₙ 的子集；数据库表的数学模型（每行一个 n 元组）。
  • 三大运算：选择 selection σ_C（按条件过滤行）、投影 projection π_{i…}（取列）、连接 join J_p（按键拼表）。
  • 与 SQL 一一对应：SELECT…WHERE ↔ 选择；SELECT 列 ↔ 投影；JOIN ↔ 连接。
  • 数据库主键/组合键、域与属性的数据建模语言。
  • 投影会引入重复元组，需去重——关系代数的工程细节。
为什么要学

这节是"数学直接变成工业标准"的范例：Codd 的关系模型（1970）建立在这几页数学上，催生了 Oracle/MySQL/PostgreSQL 整个产业。

应用亮点
  • SQL 关系代数
  • 数据仓库星型模型
  • Excel 表连接

9.3 关系的表示 Representing Relations

PDF p644
  • 0-1 矩阵表示：mᵢⱼ=1 ⟺ (aᵢ,aⱼ)∈R。自反⟺对角线全 1；对称⟺矩阵对称。
  • 关系运算的矩阵实现：并=∨、交=∧、合成=布尔积 M_{S∘R} = M_R ⊙ M_S（第 2.6 节的布尔积在此兑现）。
  • 有向图表示：顶点=元素，箭头=序偶——关系的可视化；与第 10 章图论无缝衔接。
  • 稀疏关系用邻接表（习题层面）。
学习提示

同一关系画三种表示（序偶集合、0-1 矩阵、有向图）各一遍——性质判断在三种表示下都有"一眼看出"的判据，考题常换表示考同一性质。

应用亮点
  • 社交网络的邻接矩阵
  • 推荐系统共同好友
  • 编译器依赖图

9.4 关系的闭包 Closures of Relations

PDF p651
  • 闭包 = 包含 R 的、具有目标性质的最小关系。自反闭包 R∪Δ（加自环）、对称闭包 R∪R⁻¹（加反向箭头）都容易构造。
  • 传递闭包 R*：可从 a 走到 b ⟺ (a,b)∈R*。"网络中 a 能否经多跳连到 b"的数学本质。
  • R* = R∪R²∪…∪Rⁿ（n 个元素时幂收敛）；矩阵形式 M_R* = M ∨ M² ∨ … ∨ Mⁿ。
  • Warshall 算法：动态规划逐顶点放宽，O(n³) 求传递闭包——与第 10 章 Floyd 最短路同思想。
算法思想

Warshall：Wₖ[i,j]=1 ⟺ i 到 j 存在"中间点只用前 k 个"的路径；Wₖ[i,j] ← W_{k−1}[i,j] ∨ (W_{k−1}[i,k]∧W_{k−1}[k,j])。手算一个 4×4 例子是本节必修。

应用亮点
  • 网络可达性
  • 编译器依赖解析
  • 家谱祖先链

9.5 等价关系 Equivalence Relations

PDF p661
  • 等价关系 = 自反 + 对称 + 传递："≈"式的关系（同余、同余类、同生日）。
  • 等价类 [a]ᵣ = {x | xRa}；等价类要么相等要么不相交——天然把集合切成块。
  • 划分（partition）⟺ 等价关系：一一对应定理。"分类"的严格数学化。
  • 模 m 同余是最重要实例：Z 被切成 m 个剩余类，引出 Zₘ 运算系统。
  • 等价类计数：集合大小 = Σ 类大小；与第 6 章计数、第 10 章连通分量呼应。
结构定理

集合 A 上的等价关系 ↔ A 的划分。证明方向："不同类不相交"用反证 + 对称传递。这是"商集"概念的起点。

应用亮点
  • 数字电路按功能等价分组
  • 哈希分桶
  • 图像连通域

9.6 偏序 Partial Orderings

PDF p673
  • 偏序（poset, ⪯）= 自反 + 反对称 + 传递：整除、包含、字典序、"是…的祖先"。
  • 可比与全序（线序）；良序（每个非空子集有最小元，如 N 与 ≤）。
  • 字典序（lexicographic）：笛卡尔积上的全序构造。
  • Hasse 图：删除自环与传递边、向上画的"骨架图"——画法与读法是必考技能。
  • 极大/极小元（无可比者在上/下）vs 最大/最小元（对所有元素可比）；上界/上确界（lub）与下界/下确界（glb）。
  • 格（lattice）：每对元素都有上确界与下确界的偏序——分配格与布尔代数（第 12 章）的桥。
  • 拓扑排序：偏序相容的线性排列——任务调度/编译依赖的标准解法（贪心取极大/极小元）。
学习提示

Hasse 图三步画法：① 画有向图 ② 去自环与由传递性可推出的边 ③ 边朝上摆。极大元看"顶层"（可多个），最大元要求唯一且统辖全体——两者区别是高频考点。

应用亮点
  • 项目任务排序（甘特图）
  • 编译顺序解析
  • 版本号比较
  • 集合包含体系

📖 本章定义速查（中英对照）

术语一行释义
relation R ⊆ A×B关系：笛卡尔积的子集；xRy ⟺ (x,y)∈R
reflexive自反：∀a, aRa
symmetric / antisymmetric对称：aRb⟹bRa / 反对称：aRb∧bRa⟹a=b
transitive传递：aRb∧bRc⟹aRc
n-ary relationn 元关系：A₁×…×Aₙ 的子集（数据库表）
selection / projection / join数据库三运算：选择（行过滤）、投影（取列）、连接（拼表）
composite S∘R / power Rⁿ关系合成与关系幂（递归定义 R¹=R, Rⁿ⁺¹=Rⁿ∘R）
reflexive/symmetric/transitive closure三类闭包：包含 R 的最小自反/对称/传递关系
equivalence relation / class等价关系（自反+对称+传递）/ 等价类 [a]ᵣ
partition划分：互不相交、并为全集的块族 ⟺ 等价关系
partial order / poset偏序（自反+反对称+传递）与其结构 (A,⪯)
Hasse diagram哈斯图：删自环与传递边的极简表示
maximal / greatest element极大元（无更上者，可多个）/ 最大元（统辖全体，至多一个）
lattice格：任意两元都有上确界与下确界的偏序集
topological sort拓扑排序：与偏序相容的线性排列

📐 定理与关键结论一览

  1. R 传递 ⟺ Rⁿ⊆R 对一切 n≥1 成立
  2. Rⁿ 的 (a,b) 元 ⟺ 存在长为 n 的路径 a→b
  3. 传递闭包等于连通关系 R*=R∪R²∪…∪Rⁿ
  4. 等价关系与划分一一对应（商集定理）
  5. 反对称判别：关系矩阵中 (i,j) 与 (j,i)（i≠j）不同时为 1（配合对角线自环）
PDF p651原文摘录 · Short Quotation

“The transitive closure of a relation R equals the connectivity relation R∗.”

传递闭包 = 连通关系——9.4 节的核心定理，Warshall 算法由此而来。

本章关键词： 二元关系binary relation自反reflexive对称symmetric 反对称antisymmetric传递transitive选择/投影/连接selection/projection/join 传递闭包transitive closureWarshall算法等价关系equivalence relation 等价类equivalence class划分partition偏序partial ordering Hasse图Hasse diagram格lattice拓扑排序topological sort

章末材料 PDF p688。本章传记：Hasse、Warshall（生平框）、Erdős、Hall。

第 10 章　图

Graphs · PDF 696–803 · 108 页（全书第二长）

22 定义 + 16 定理87 例题≈535 习题板块四
图 = 顶点 + 边，再简单不过的结构却建模了整个互联世界：社交网络、通信网、交通网、芯片布线、依赖关系。本章是全书篇幅第二大的章，从图的术语与表示出发，经过连通性、欧拉/哈密顿路径、最短路（Dijkstra）、平面图（欧拉公式、K₃,₃ 与 K₅）直到图着色（四色定理）。这一章与数据结构、算法面试、网络课程直接互认，投入产出比全书最高之一。

10.1 图与图模型 Graphs and Graph Models

PDF p696
  • 图 G=(V,E)：顶点集 V + 边集 E；有向图边是箭头（序偶）。
  • 允许重边/自环的是多重图；计算机科学场景常用简单图。
  • 建模思维训练（本节例题量大）：社交关系（无向）、微博关注（有向）、合作网络（超图/二部）、交通网（带权→第 10.6 节）。
  • 同一种业务问题如何选择"点是什么、边是什么"——建模自由度与约束。
学习提示

给每个应用想清楚两问："顶点代表什么？边代表什么？方向/权重/多重性分别意味着什么？"——图论建模的一半功力在这一问。

应用亮点
  • 社交网络
  • 化学反应网络
  • 通信拓扑
  • 生态食物链

10.2 图的术语与特殊类型的图 Graph Terminology and Special Types of Graphs

PDF p708
  • 基本术语：邻接、邻域 N(v)、度 deg(v)（自环计 2）；入度/出度（有向图）。
  • 握手定理：Σ deg(v) = 2|E| ⟹ 奇度顶点必有偶数个。
  • 特殊图家族：完全图 Kₙ（边数 C(n,2)）、圈图 Cₙ、轮图 Wₙ、n 维超立方体 Qₙ（2ⁿ 顶点、n·2ⁿ⁻¹ 条边）。
  • 二部图 ⟺ 不含奇数长回路（判定定理）；K_{m,n}；匹配问题预告。
  • 正则图（各顶点同度）；Kₙ 是 n−1 正则的。
  • 子图/导出子图；图的同构初步（正式在 10.3）。
必考定理

握手定理及其推论。应用套路：数边数、判断给定度序列是否可能成图（Σ度=偶数且各度≤n−1 是必要条件）。

学习提示

二部图判定"奇圈法"要会证：二分染色沿回路交替，奇数长时回到起点矛盾。员工-任务分配是二部图匹配的原型。

应用亮点
  • 婚配/任务分配
  • 超立方体并行架构
  • NBA 赛程建模

10.3 图的表示与图同构 Representing Graphs and Graph Isomorphism

PDF p726
  • 邻接矩阵：n×n 的 0-1 矩阵（无向图对称）；Aᵏ 的 (i,j) 元 = i 到 j 长为 k 的通路条数（矩阵幂的图论意义！）。
  • 关联矩阵：顶点×边的 0-1 矩阵（每列恰两个 1）。
  • 稀疏图用邻接表：空间 O(V+E)，遍历的效率基础。
  • 同构：双射保邻接 ⟺ "同一个图换了画法"。同构不变量：顶点数、边数、度序列、回路长度谱……
  • 判不同构：找一个不变量不同即可；判同构：构造显式映射。不变量全同仍可能不同构（经典反例对）。
学习提示

先比 n、m，再比度序列，再看圈结构/连通性——按顺序筛。邻接矩阵幂的计数意义（长为 2 的通路 = 共同好友数）是常考的"漂亮结论"。

应用亮点
  • 社交图谱存储
  • 化学结构比对
  • 共同好友推荐

10.4 连通性 Connectivity

PDF p737
  • 通路/回路：无重复顶点的叫简单通路；连通图/连通分量。
  • 顶点删除版鲁棒性：割点（删除后分量增加）与桥；无割点的连通图 = 双连通。
  • 有向图：强连通（任意两顶点互达）vs 弱连通；强连通分量。
  • 定量鲁棒性：点连通度 κ(G) 与边连通度 λ(G)；κ ≤ λ ≤ δ（最小度）。
  • 通路计数的矩阵方法：A+A²+…+A^{n−1} 的非零模式判断连通。
学习提示

"删除谁会让网络瘫痪"是本节的工程读法：割点=单点故障，桥=单链路故障。κ(G)≥k 称为 k 连通，是网络设计的可靠性指标。

应用亮点
  • 网络容错设计
  • 电网/互联网骨干
  • 强连通分量（编译器/网页社区）

10.5 欧拉通路与哈密顿通路 Euler and Hamilton Paths

PDF p751
  • 欧拉回路（每边恰一次）：存在 ⟺ 连通且每个顶点度数都是偶数；欧拉通路（不回起点）：恰有 0 或 2 个奇度顶点。
  • 哥尼斯堡七桥问题的否定解答 = 图论的出生证明（1736, Euler）。
  • 哈密顿通路/回路（每顶点恰一次）：无简单充要条件！NP 完全问题的代表。
  • 充分条件：Dirac（n≥3 简单图，每个 deg ≥ n/2 ⟹ 哈密顿回路）；Ore（每对不相邻顶点 deg u + deg v ≥ n）。
  • 必要条件：删除任意 k 个顶点后分量数 ≤ k（用于证明"无"哈密顿回路）。
  • 旅行商问题（TSP）= 加权完全图最短哈密顿回路——组合优化的圣杯难题。
定理对照

欧拉：判"边"——看奇度顶点个数（充要）；哈密顿：判"点"——只有充分条件与必要条件。这一强一弱的对比是本节灵魂。

应用亮点
  • 邮递员/扫街路线
  • 芯片孔道布线
  • 旅行商与物流

10.6 最短路径问题 Shortest-Path Problems

PDF p766
  • 加权图；两点间最短路径；朴素 Dijkstra 思想：逐个"确定"离起点最近的未定顶点（贪心）。
  • Dijkstra 算法 O(n³) 朴素实现（书中版）/ O((V+E)logV) 堆优化；正确性依赖边权非负。
  • Floyd 算法：动态规划求所有点对最短路 Dᵏ[i,j] = min(D^{k−1}[i,j], D^{k−1}[i,k]+D^{k−1}[k,j])，与 Warshall 同骨架。
  • 应用：两地间最便宜航线、网络路由（OSPF 即 Dijkstra）、依赖调度。
  • 扩展：最长路径（关键路径法 CPM）、负权边为什么破坏 Dijkstra（习题）。
学习提示

手算 Dijkstra 用"表上作业法"：每轮给未确定点标 (候选距离, 前驱)，选最小者划掉。对 5 个顶点的图完整跑一遍，胜过背十遍伪代码。

应用亮点
  • 地图导航
  • 网络路由协议
  • 项目关键路径

10.7 平面图 Planar Graphs

PDF p776
  • 平面图：能在平面上画出且边不相交；画出的连通块区域数 r。
  • 欧拉公式：v − e + r = 2（连通平面图）——拓扑不变量，证明用归纳（删边/缩边）。
  • 推论：简单连通平面图 e ≤ 3v−6；由此立证 K₅ 与 K₃,₃ 非平面。
  • Kuratowski 定理：非平面 ⟺ 包含与 K₅ 或 K₃,₃ 同胚（细分）的子图。
  • 应用：电路布线层数判断（PCB 印证了 K₃,₃ 的必然失败）、地图区域相邻关系。
必会证明

用 e ≤ 3v−6 判非平面：K₅ 有 v=5,e=10 > 3×5−6=9 矛盾；K₃,₃ 用"每个区域至少 4 条边"的版本 e ≤ 2v−4 判定。两个都要会写。

应用亮点
  • PCB 布线
  • 地图着色前置
  • 3 公用设施问题

10.8 图着色 Graph Coloring

PDF p785
  • 着色：相邻顶点不同色；色数 χ(G) 是最少颜色数。
  • 经典色数：二部图 χ=2；Kₙ χ=n；Cₙ 偶圈 2 / 奇圈 3；平面图 χ≤5（五色定理，书中给完整证明）。
  • 四色定理（Appel–Haken 1976，计算机辅助证明）：平面图 χ≤4——第一个重大"机器证明"，引出数学哲学讨论。
  • 求色数是 NP 完全；贪心着色给出上界 Δ+1（Welsh–Powell 改进）。
  • 建模应用：期末排考（课程=顶点、有共同学生=边）、频率分配、寄存器分配。
学习提示

"最少几种 X 使冲突不发生"的题先翻译成图：对象=顶点、冲突=边、资源=颜色。χ 的下界：找最大团 ω(G) ≤ χ；上界：给一个显式着色。

应用亮点
  • 考试排期
  • 无线频谱分配
  • 编译器寄存器分配
  • 地图四色

📖 本章定义速查（中英对照）

术语一行释义
graph G=(V,E)图：顶点集与边集；多重图允许重边/自环
directed graph有向图：边为序偶（箭头）
degree deg(v)度：关联边数（自环计 2）；有向图分入度/出度
complete graph Kₙ完全图：任意两顶点相邻，C(n,2) 条边
bipartite graph二部图：顶点可二分成两个独立集 ⟺ 无奇圈 〔又译：二分图（CS 语境常用）／偶图〕
subgraph / induced subgraph子图 / 导出子图
adjacency / incidence matrix邻接矩阵（点×点）/ 关联矩阵（点×边）
isomorphism同构：保邻接的双射——“同一张图换画法”
path / circuit / connected通路 / 回路 / 连通（分量）
cut vertex / bridge割点 / 桥：删除后连通分量增加
Euler path/circuit欧拉通路/回路：每条边恰经一次
Hamilton path/circuit哈密顿通路/回路：每个顶点恰经一次
planar graph / region平面图 / 平面嵌入的区域
chromatic number χ(G)色数：相邻异色所需最少颜色数

📐 定理与关键结论一览

  1. 握手定理：Σ deg(v) = 2|E|（无向图）
  2. 推论：奇度顶点必有偶数个
  3. 有向图版：Σ deg⁻(v) = Σ deg⁺(v) = |E|
  4. 二部图判定：二部 ⟺ 无奇数长回路
  5. Euler 回路判定：连通且全偶度；Euler 通路：恰 0 或 2 个奇度点
  6. Dirac：n≥3 简单图每个 deg≥n/2 ⟹ 有 Hamilton 回路（Ore 条件为其推广）
  7. Euler 公式：连通平面图 v−e+r=2
  8. 平面图边界：简单连通平面图 e ≤ 3v−6；K₅、K₃,₃ 由此判非平面
  9. Kuratowski：非平面 ⟺ 含 K₅ 或 K₃,₃ 的细分
  10. 五色定理：平面图 χ≤5（四色定理 χ≤4 为机器辅助证明）
PDF p786原文摘录 · Short Quotation

“The four color theorem was originally posed as a conjecture in the 1850s. It was finally proved by the American mathematicians Kenneth Appel and Wolfgang Haken in 1976.”

四色定理的历史原文——第一个主要由计算机完成证明的重大定理。

PDF p751原文摘录 · Short Quotation

“…eenth century seven bridges connected these regions. Figure 1 depicts these regions and bridges. Only five bridges connect Kaliningrad today. Of these, just two remain from Euler’s day. The townspeople took long walks through town on Sundays. They wondered whether it was”

哥

🕐 编者注 · 2026 视角（非原书内容）
  • 四色定理的“机器证明是否可信”之争已有回应：Gonthier 等（2005）在 Coq 定理证明器中完成了四色定理的完整形式化验证——机器辅助证明可以被形式化地核验。
本章关键词： 度degree握手定理handshaking theorem二部图bipartite 邻接矩阵adjacency matrix同构isomorphism割点cut vertex 强连通strongly connected欧拉回路Euler circuit哈密顿回路Hamilton circuit Dijkstra算法欧拉公式Euler's formula平面图planar graph Kuratowski定理色数chromatic number四色定理four color theorem

章末材料 PDF p794。本章传记：Euler、Hamilton、Dirac、Dijkstra、Kuratowski、Kempe（四色证明尝试）。

第 11 章　树

Trees · PDF 804–869 · 66 页

9 个算法（全书第三）42 例题≈264 习题板块四
树 = 无回路连通图，是数据结构课程里半数结构（二叉搜索树、堆、表达式树、哈夫曼树、并查集）的数学本体。本章给出树的等价刻画、有根树与遍历、哈夫曼编码、生成树与最小生成树（Prim/Kruskal）。如果你要学数据结构或准备算法面试，本章是全书与目标重合度最高的一章。

11.1 树导论 Introduction to Trees

PDF p804
  • 树 = 连通无简单回路的图。等价刻画族（要会证互推）：① 连通无回路 ② n 顶点恰 n−1 条边且连通 ③ 无回路但加任一边出回路 ④ 两点恰一条简单通路。
  • 有根树：指定根 + 边方向朝外；父/子/兄弟/叶/内部顶点/深度/高度。
  • m 叉树：内部顶点至多 m 个孩子；满 m 叉树：恰 m 个。关键计数：满 m 叉树 i 个内点 ⟹ n = mi+1，叶 l = (m−1)i+1。
  • 满二叉树高度与叶数关系：l ≤ 2ʰ，h ≥ ⌈log₂l⌉——算法下界的常用事实。
  • 平衡树概念预告（AVL 等）。
核心计数

满 m 叉树：n = mi + 1（总顶点），n = i + l（内部+叶），h ≥ ⌈log_m l⌉。三式联立解 n、i、l 是高频题型（如"满 3 叉树 82 片叶，最少多少内点/多高"）。

应用亮点
  • 组织架构图
  • 文件系统目录
  • 生物分类树

11.2 树的应用 Applications of Trees

PDF p816
  • 二叉搜索树（BST）：左小右大；插入/查找算法；平均复杂度与树的平衡程度相关。
  • 决策树：用一棵树枚举"是/否"回答的决策序列；排序下界 Ω(n log n) 的证明由此而来（叶 ≥ n!）。
  • 前缀码：任何码字都不是另一码字的前缀 ⟺ 对应一棵二叉树（左 0 右 1）。
  • 哈夫曼算法：反复合并频率最小的两片叶，构造平均长度最优前缀码（贪心，正确性证明书中有）。
  • 博弈树：minimax 评估 + α-β 剪枝思想——游戏 AI 的起点。
必练

哈夫曼手工题：频率 {5,9,12,13,16,45}，合并过程画树、编码、算平均码长。决策树排序下界证明：二叉树叶 ≥ n! ⟹ 高 ≥ ⌈log₂n!⌉ = Ω(n log n)。

应用亮点
  • ZIP/JPEG 压缩编码
  • 游戏 AI
  • 排序复杂度下界

11.3 树遍历 Tree Traversal

PDF p831
  • 三种深度优先遍历：前序（根左右）、中序（左根右）、后序（左右根）——递归定义，结构归纳的天然素材。
  • 表达式树：叶=操作数、内部=运算符；中序遍历得中缀、前序得前缀（波兰记法）、后序得后缀（逆波兰 RPN）。
  • 后缀表达式的栈求值算法（不需要括号）；中缀转后缀。
  • 中序遍历 BST 得到升序序列——BST 判定与构造的经典结论。
学习提示

对表达式 (a+b)*c−d 建树，分别写出前中后缀。考题常给两种遍历还原树（前/中配对或后/中配对）。

应用亮点
  • 计算器 RPN
  • 编译器表达式解析
  • 序列化与还原

11.4 生成树 Spanning Trees

PDF p844
  • 生成树：连通图的生成子图且是树（n−1 条边）；连通 ⟺ 有生成树（构造性证明）。
  • 深度优先搜索（DFS）：一路到底再回溯——生成 DFS 树；广度优先搜索（BFS）逐层扩展——生成 BFS 树（含最短路信息，无权图）。
  • 回溯法（backtracking）：DFS 状态空间 + 剪枝——n 皇后、图着色、子集和的系统化解法。
  • DFS/BFS 的复杂度均为 O(V+E)（邻接表）。
学习提示

回溯是本节的思维亮点："系统性穷举 + 提前剪枝"统一解决一大类组合搜索题。建议手工跑一遍 4 皇后回溯过程。

应用亮点
  • 爬虫/迷宫求解
  • 网络广播树
  • 约束求解回溯

11.5 最小生成树 Minimum Spanning Trees

PDF p858
  • MST：边权总和最小的生成树（连通加权图）。
  • Prim 算法：从一点长树，每轮选"跨集合的最小边"——Dijkstra 的孪生结构。
  • Kruskal 算法：边按权排序，依次选不成环的边（并查集判环）。
  • 两算法都属贪心，且都能被"割边最优性"证明正确（cut property）。
  • 复杂度：Prim O(n³) 朴素 / Kruskal O(E log E)。
贪心正确性

切割性质：对任何划分，最小跨边必在某棵 MST 中。理解这个引理，Prim/Kruskal 的证明就只是套用——这是"贪心算法可证明"的最佳教学案例。

应用亮点
  • 电网/光缆铺设
  • 网络拓扑设计
  • 聚类（单链）

📖 本章定义速查（中英对照）

术语一行释义
tree树：连通无简单回路的图
rooted tree有根树：指定根，边方向背离根
parent / child / leaf / internal父 / 子 / 叶（度为1）/ 内部顶点
level / height层（根到顶点路径长）/ 高（最大层数）
m-ary / full m-ary treem 叉树（内点≤m 子）/ 满 m 叉树（恰 m 子）
balanced tree平衡树：叶都在最后两层
binary search tree二叉搜索树：左小右大
decision tree决策树：内点为判定、叶为结局
prefix code前缀码：任何码字不是另一码字前缀 ⟺ 二叉树编码
preorder / inorder / postorder前序（根左右）/ 中序（左根右）/ 后序（左右根）
spanning tree生成树：连通图的树形生成子图（n−1 条边） 〔又译：支撑树〕
minimum spanning tree最小生成树：边权总和最小的生成树 〔又译：支撑树〕

📐 定理与关键结论一览

  1. 等价刻画：无向图是树 ⟺ 任两顶点间有唯一简单路径
  2. 树的基本计数：n 个顶点的树恰有 n−1 条边
  3. 满 m 叉树：i 个内点 ⟹ n=mi+1 个顶点、l=(m−1)i+1 片叶
  4. 满 m 叉树高度：h ≥ ⌈log_m l⌉（叶数下界推出排序下界 Ω(n log n)）
  5. Huffman 编码最优性：贪心合并频率最小的两子树得平均长度最优前缀码
  6. 切割性质：任何划分的最小跨边必属某棵 MST（Prim/Kruskal 正确性）
PDF p804原文摘录 · Short Quotation

“An undirected graph is a tree if and only if there is a unique simple path between any two of its vertices.”

树的等价刻画定理原文——树论的第一块基石。

译名备注

重要译名辨析：Rosen 的 full binary tree（每个内部顶点恰有两个孩子）不能直接等同于国内数据结构教材的“满二叉树”——国内“满二叉树”多指 perfect binary tree（每层都满），而 full binary tree 对应国内的“严格二叉树／正则二叉树”；complete binary tree（完全二叉树）又与两者不同。读英文原书时务必按英文定义理解。

本章关键词： 树tree有根树rooted treem叉树m-ary tree 二叉搜索树binary search tree决策树decision tree前缀码prefix code 哈夫曼编码Huffman coding博弈树game tree前/中/后序preorder/inorder/postorder 逆波兰reverse Polish notation深度优先depth-first search回溯backtracking 生成树spanning treePrim/Kruskal

章末材料 PDF p864。本章传记：Cayley（树的计数）、Huffman、Kruskal、Prim。

第 12 章　布尔代数

Boolean Algebra · PDF 870–907 · 38 页（全书最短章）

28 例题≈146 习题无编号定理（工程导向）板块四
第 1 章的命题逻辑在此"落地成硅"：布尔函数是数字电路的数学模型，逻辑门是其物理实现。本章教你把"要实现的功能"写成布尔函数，化成积之和，再用卡诺图或 Quine–McCluskey 方法化到最简。这是全书最短、最工程化的一章，也是理解 CPU 如何由"与或非"搭出来的一章。

12.1 布尔函数 Boolean Functions

PDF p870
  • 布尔代数 {B, ∨, ∧, ¬, 0, 1}；布尔函数 F: Bⁿ → B。
  • 布尔恒等式与命题逻辑恒等式平行（对偶原理：交换 ∨/∧ 与 0/1 仍成立）。
  • n 元布尔函数共 2^(2ⁿ) 个；真值表与表达式的互转。
  • 由真值表读出积之和：对每个输出 1 的行取最小项再相或——任意布尔函数可由 ∧∨¬ 表达（函数完备性）。
核心概念

对偶（dual）：把表达式中 ∨↔∧、0↔1 互换。布尔代数的每个恒等式的对偶仍是恒等式——一次证明，两条定理。

应用亮点
  • 电路综合
  • SQL/编程语言的三值逻辑

12.2 布尔函数的表示 Representing Boolean Functions

PDF p878
  • 文字/最小项/最大项：最小项 mᵢ（所有变量的积、恰好一行真）、最大项 Mᵢ（所有变量的和）。
  • 任何函数 = 其最小项之和（主析取范式）；= 最大项之积（主合取范式）。
  • 函数完备集：{∧,∨,¬} 完备；{∧,¬}、{∨,¬} 完备；NAND（↑）单独完备——这就是 NAND 闪存与门电路的统治性来源。
  • 与非/或非的相互表达：x↑y = ¬(x∧y)。
关键定理

NAND 功能完备：¬x = x↑x，x∧y = (x↑y)↑(x↑y)，x∨y = (x↑x)↑(y↑y)。一种门就能造出计算机的一切——面试与课程双高频。

应用亮点
  • NAND 闪存
  • 电路标准单元库

12.3 逻辑门 Logic Gates

PDF p881
  • 三种基本门的图形符号：非门（三角+圈）、与门（D 形）、或门（盾形）；组合门电路 ↔ 布尔表达式 ↔ 真值表三位一体。
  • 组合电路 = 无记忆电路：输出仅由当前输入决定。
  • 半加器：x⊕y（和）与 xy（进位）；全加器：两个半加器 + 或门处理低位进位。
  • 多路复用器（MUX）概念：用选择位挑数据。
  • 加法器级联 = 逐位进位加法器（ripple-carry adder），复杂度随位数线性增长。
必练

给一位全加器写出 s = x⊕y⊕cᵢₙ、cₒᵤₜ = xy ∨ cᵢₙ(x⊕y)，画出门级电路并填真值表——这 8 行真值表就是"计算机如何做加法"的全部秘密。

应用亮点
  • ALU 加法器
  • 多路选择器
  • 译码器

12.4 电路化简 Minimization of Circuits

PDF p887
  • 化简动机：门数少 = 更便宜、更快、更省电。
  • 卡诺图（K-map）：真值表的二维重排，相邻格相差一个变量；圈 2ᵏ 相邻的 1 消去 k 个变量。
  • 卡诺图技巧：圈越大越好、圈数越少越好、每个 1 至少被圈一次、允许环绕相邻。
  • 无碍项（don't care）：输入组合不会出现，可任意取值帮助化简。
  • Quine–McCluskey 方法：系统化的表格化简法，可编程（适合变量多、机器执行），两步：找素蕴涵项 + 素蕴涵项图表选最小覆盖。
学习提示

四变量卡诺图手工题至少做 5 道（含环绕相邻与无碍项）。卡诺图 = 人用的快捷方式，Quine–McCluskey = 机器用的等价算法——EDA 工具的鼻祖。

应用亮点
  • 芯片综合工具（逻辑综合）
  • FPGA 逻辑优化

📖 本章定义速查（中英对照）

术语一行释义
Boolean algebra (B,∨,∧,¬,0,1)布尔代数：满足十条恒等式的二元/一元运算系统
Boolean function布尔函数 F:Bⁿ→B；n 元共 2^(2ⁿ) 个
dual对偶式：∨↔∧、0↔1 互换所得表达式
literal / minterm / maxterm文字 / 最小项（全变量积）/ 最大项（全变量和）
sum-of-products / product-of-sums积之和（主析取范式）/ 和之积（主合取范式）
functionally complete函数完备集：能表达一切布尔函数（{∧,∨,¬}、{↑}） 〔又译：功能完备集／全功能集〕
NAND x↑y与非：¬(x∧y)——单独即完备
gate / combinatorial circuit逻辑门 / 组合电路（无记忆，输出仅依赖当前输入）
half / full adder半加器（x⊕y, xy）/ 全加器（含进位输入）
Karnaugh map卡诺图：真值表的二维重排，相邻合并消变量
don't care condition无碍项：不会出现的输入组合，可任意取值 〔国内通行译名：无关项〕
prime implicant素蕴涵项：不能再扩大的 1-块覆盖

📐 定理与关键结论一览

  1. 对偶原理：布尔恒等式取对偶仍是恒等式
  2. 任何布尔函数都可表示为最小项之和（真值表直读）
  3. NAND 完备性：¬x=x↑x，x∧y=(x↑y)↑(x↑y)，x∨y=(x↑x)↑(y↑y)
  4. 吸收律、德摩根律等十条恒等式构成布尔代数公理
  5. 卡诺图正确性：2ᵏ 相邻格合并可消去 k 个变量（环绕相邻有效）
PDF p870原文摘录 · Short Quotation

“A Boolean algebra is a set B with two binary operations ∨ and ∧, elements 0 and 1, and a unary operation ¬ …”

布尔代数的公理化定义原文——从第 1 章的逻辑运算升格为代数结构。

🕐 编者注 · 2026 视角（非原书内容）
  • 工业界的电路化简已普遍转向以 SAT 求解器为内核的精确/近似逻辑综合，卡诺图保留其教学价值，Quine–McCluskey 的思想在 EDA 工具中以现代形态延续。
本章关键词： 布尔函数Boolean function对偶dual最小项minterm 函数完备functionally completeNAND逻辑门logic gate 半加器/全加器half/full adder卡诺图Karnaugh map无碍项don't careQuine–McCluskey

章末材料 PDF p902。本章传记：Boole（第 1 章已出场）、Karnaugh、McCluskey。

第 13 章　计算模型

Modeling Computation · PDF 908–965 · 58 页

17 定义44 例题≈227 习题板块四 · 通往理论计算机科学
收官之章回答一个根本问题："计算"本身能否被数学建模？文法刻画语言的生成（编译器的 BNF），有限状态机刻画有穷记忆的处理（电路与协议），图灵机界定"可计算"的边界（停机问题）。本章是编译原理、形式语言与可计算性理论 course 的入口；读完它，"计算机为什么能计算、又有什么做不到"将从直觉变成定理。

13.1 语言与文法 Languages and Grammars

PDF p908
  • 词汇表（字母表）V、串、空串 λ、语言 = V* 的子集；串的连接与 Kleene 闭包运算。
  • 短语结构文法 G=(V,T,S,P)：非终结符/终结符/开始符号/产生式；派生 ⟹ 关系；生成的语言 L(G)。
  • 文法的类型（Chomsky 层级）：0 型（无限制）、1 型（上下文有关）、2 型（上下文无关 CFG）、3 型（正则）——能力逐级递减，识别机逐级简单。
  • BNF 记法（Backus–Naur Form）：程序设计语言语法的标准写法；派生树（语法树）。
  • 例：标识符文法、回文文法、{0ⁿ1ⁿ} 文法——最后一例是"CFG 超出正则"的经典。
核心定义

文法 G=(V,T,S,P)：S→w 的有限次派生产生语言 L(G) = {w∈T* | S ⟹* w}。巴科斯范式把"::="当"→"用，如 ⟨digit⟩ ::= 0|1|…|9。

应用亮点
  • 编译器语法分析
  • 配置文件/协议语法
  • 自然语言形式化

13.2 带输出的有限状态机 Finite-State Machines with Output

PDF p920
  • FSM M=(S,I,O,f,g,s₀)：状态集、输入/输出字母表、转移函数 f、输出函数 g、初始状态。
  • Mealy 机：输出依赖"当前状态+当前输入"（每条弧标 输入/输出）。
  • Moore 机：输出只依赖当前状态（状态上标输出）。
  • 经典例子：单位延迟机（输出上一位输入）、售货机、奇偶校验机、模 3 计数器。
  • 读 FSM 状态图/状态表、写输出串是基本功课。
学习提示

拿到 FSM 题先列状态表再画状态图，按输入串逐步走并记录输出。自己设计"检测 111"的序列检测器是检验理解的好题。

应用亮点
  • 自动售货机
  • 交通灯控制器
  • 协议状态机（TCP）

13.3 不带输出的有限状态机 Finite-State Machines with No Output

PDF p927
  • 有限状态自动机（FSA/DFA）M=(S,I,f,s₀,F)：终态集 F 取代输出——读完全部输入停在终态则接受。
  • 自动机的语言：所有被接受的串；状态图终态用双圈表示。
  • 构造练习：识别"以 00 结尾""含 111""偶数个 1"的自动机。
  • 正则文法 ⟺ 有限自动机（同层语言）：3 型语言的两种面孔。
  • 非确定自动机（NFA）：同输入可有多条转移；NFA 与 DFA 识别能力相同（子集构造，在下一节展开）。
设计套路

设计 DFA："状态 = 读到当前位置时需要记住的信息"。如偶数个 1 只需 2 个状态（奇/偶）。先问"机器需要记住什么"，状态自动浮现。

应用亮点
  • 词法分析器（正则引擎）
  • 硬件控制单元
  • 文本搜索（grep 的理论内核）

13.4 语言识别 Language Recognition

PDF p940
  • 正则表达式：由 ∅、λ、字母经 ∪、·、* 组合的式子——模式匹配的数学本体。
  • Kleene 定理：一个集合是正则的 ⟺ 它能被有限自动机识别——正则表达式、正则文法、FSA 三位一体。
  • 非确定 → 确定：子集构造法（每个 DFA 状态 = NFA 状态集的一个子集）。
  • 泵引理（pumping lemma）证明非正则：{0ⁿ1ⁿ | n≥0} 不是正则语言——有限状态记不住"数到 n"。
  • 正则之外：上下文无关语言由下推自动机识别（预告编译课程）。
里程碑定理

Kleene 定理：正则表达式 = 正则文法 = 有限自动机。它是"文本编辑器正则搜索"合法性的数学保证；泵引理则划出了这些机器的能力边界。

应用亮点
  • grep/正则库
  • 网络入侵检测模式
  • 编译器词法分析

13.5 图灵机 Turing Machines

PDF p950
  • 图灵机 T=(S,I,δ,s₀)：无限带 + 读写头 + 转移函数 δ(状态,符号)=(新符号,方向 L/R,新状态)。
  • 识别语言：停机于终态即接受；图灵机可计算"部分函数"（带输出）。
  • 例：识别 {0ⁿ1ⁿ}（FSA 做不到的事）、二进制加一。
  • Church–Turing 论题："可有效计算" ⟺ 图灵机可计算——一个论题（thesis）而非定理，是全部可计算性理论的公理基石。
  • 不同等价模型（多带、双向无限带）计算能力相同；图灵机彼此模拟的思想。
  • 边界结果：停机问题不可判定（呼应 3.3 节）；存在定义明确但不可计算的函数——计算有极限，且极限可以被证明。
里程碑

图灵机（1936）比电子计算机早诞生近十年——它先回答了"什么是计算"，人类才动手造计算机。全书在这条时间线上闭环：从逻辑（Ch1）出发，抵达计算的边界（Ch13）。

应用亮点
  • 可计算性理论
  • 复杂度类（P/NP）的定义平台
  • λ 演算与函数式编程的等价性

📖 本章定义速查（中英对照）

术语一行释义
alphabet / string / language字母表 V / 串（含空串 λ）/ 语言（V* 的子集）
Kleene closure A*Kleene 闭包：A 中串的全体有限连接
phrase-structure grammar G=(V,T,S,P)短语结构文法：非终结符、终结符、开始符、产生式
derivation ⟹ / L(G)派生 / 文法生成的语言
type 0–3 grammarsChomsky 层级：无限制/上下文有关/上下文无关/正则
Backus–Naur formBNF：产生式 ::= 的标准写法
finite-state machine M=(S,I,O,f,g,s₀)带输出有限状态机（Mealy 型）
Moore machineMoore 机：输出仅依赖当前状态
finite-state automaton (S,I,f,s₀,F)有限状态自动机：终态集 F 决定接受
regular expression / regular set正则表达式 / 正则集合（可由正则式表达）
nondeterministic FSA非确定自动机：同一输入可有多个转移
Turing machine (S,I,δ)图灵机：无限带 + 读写头 + 转移函数
Church–Turing thesisChurch–Turing 论题：可有效计算 = 图灵机可计算

📐 定理与关键结论一览

  1. NFA 与 DFA 等价：子集构造把非确定机转为确定机
  2. Kleene 定理：集合是正则的 ⟺ 被某有限自动机识别
  3. 正则文法 ⟺ 正则集合（文法与自动机在 3 型层面等价）
  4. 泵引理可证 {0ⁿ1ⁿ} 非正则——有限状态记不住无界计数
  5. 停机问题不可判定（与 3.3 节对角线论证呼应）
PDF p950原文摘录 · Short Quotation

“Basically, a Turing machine consists of a control unit … that can both read and write symbols on a tape …”

图灵机的原文速写——比电子计算机早十年诞生的“纸上计算机”。

译名备注

译名备注：pumping lemma 又译抽运引理／泵浦引理；Mealy/Moore 机通译米利机／穆尔机；Kleene 译作克林（Kleene star 常直接称 Kleene 星）。

🕐 编者注 · 2026 视角（非原书内容）
  • 形式化数学浪潮：Lean 数学库与“液态张量实验”（2021，PNT 局部形式化）等项目把“用机器写证明”推进到研究前沿；2026 年素数间隔的 AI 辅助新纪录即以 Lean 形式化背书——图灵机划定的能力边界未变，但“人与机器协作做数学”的方式正在演变。
本章关键词： 字母表alphabet串stringKleene闭包Kleene closure 短语结构文法phrase-structure grammarBNFChomsky层级 Mealy/Moore机有限状态自动机finite-state automaton正则表达式regular expression 泵引理pumping lemma图灵机Turing machineChurch–Turing论题

章末材料 PDF p961。本章传记：Backus、Chomsky、Kleene、Turing、Church。

附录 · 答案 · 索引（PDF 966–1118）

88 位数学家传记

原书在正文穿插 88 位数学家的小传（配肖像，索引计 88 条，含 Carroll/Dodgson 同人两名），从古希腊到当代。第 8 版新增 Wiles、Bhaskaracharya、de la Vallée-Poussin、Hadamard、张益唐、Gentry 六人。下方人物墙收录 85 张卡片（少量为合传），星标为对 CS 读者尤其相关的人物。

Alan Turing 图灵图灵机 · 可计算性（Ch13）
Claude Shannon 香农信息论 · 布尔电路（Ch12）
Donald Knuth 高德纳算法分析（Ch3）
Grace Hopper编译器先驱（Ch13）
Rivest · Shamir · AdlemanRSA 三人组（Ch4）
Edsger Dijkstra最短路径（Ch10）
David Huffman哈夫曼编码（Ch11）
Stephen CookNP 完全性（Ch3）
Noam Chomsky文法层级（Ch13）
John BackusBNF · Fortran（Ch13）
Terence Tao 陶哲轩当代数学（数论节）
张益唐素数间隔突破（Ch4）
Andrew Wiles费马大定理（Ch4 相关）
Craig Gentry同态加密（Ch4）
Aristotle 亚里士多德逻辑学奠基（Ch1）
Euclid 欧几里得几何原本 · gcd 算法（Ch4）
Eratosthenes素数筛（Ch4）
Fibonacci兔子数列（Ch5/8）
al-Khowarizmi 花拉子米"算法"词源（Ch3）
Augusta Ada Lovelace第一位程序员（Ch2）
George Boole 布尔逻辑代数（Ch1/12）
Augustus De Morgan德摩根律（Ch1）
Georg Cantor 康托尔集合论 · 对角线法（Ch2）
Leonhard Euler 欧拉哥尼斯堡七桥（Ch10）
Karl Friedrich Gauss 高斯数论王子（Ch4）
Pierre de Fermat 费马小定理（Ch4）
Marin MersenneMersenne 素数（Ch4）
Christian Goldbach哥德巴赫猜想（Ch4）
Étienne BézoutBézout 定理（Ch4）
Robert CarmichaelCarmichael 数（Ch4）
Clifford Cocks英国版 RSA（Ch4）
Charles-Jean de la Vallée-Poussin素数定理证明（Ch4）
Jacques Hadamard素数定理证明（Ch4）
Bhaskaracharya古印度数学（Ch4 新增）
Srinivasa Ramanujan数论天才（Ch8）
Godfrey Hardy数论分析（Ch8）
James StirlingStirling 数（Ch6 习题）
Blaise Pascal 帕斯卡帕斯卡三角（Ch6）
Jacob Bernoulli 伯努利概率论（Ch7）
Thomas Bayes 贝叶斯贝叶斯定理（Ch7）
Pierre-Simon Laplace概率定义（Ch7）
Girolamo Cardano概率先驱（Ch7）
Pafnuty ChebyshevChebyshev 不等式（Ch7）
Irenée-Jules Bienaymé不等式合作者（Ch7）
Eugène CatalanCatalan 数（Ch8）
Richard Bellman动态规划（Ch8）
Gabriel Lamé欧几里得算法分析（Ch4）
Edmund Landau素数定理（Ch4）
Paul Bachmann大 O 记号（Ch3）
G. Lejeune Dirichlet鸽笼原理命名（Ch5/6）
René Descartes 笛卡尔笛卡尔积（Ch2）
David Hilbert 希尔伯特无穷旅馆（Ch2）
Bertrand Russell 罗素罗素悖论（Ch2）
Lewis Carroll（Dodgson）爱丽丝作者 · 逻辑（Ch1）
Charles Sanders Peirce逻辑记号（Ch1）
Henry ShefferSheffer 竖线 NAND（Ch12）
Willard QuineQuine–McCluskey（Ch12）
Maurice Karnaugh卡诺图（Ch12）
Edward McCluskey逻辑化简（Ch12）
Helmut HasseHasse 图（Ch9）
Stephen WarshallWarshall 算法（Ch9）
Paul Erdős 埃尔德什组合学传奇（Ch9/10）
Philip Hall婚配定理（Ch10）
William Rowan Hamilton哈密顿回路（Ch10）
Gabriel Dirac图论定理（Ch10）
Julius PetersenPetersen 图（Ch10）
Kazimierz Kuratowski平面图判定（Ch10）
Alfred Kempe四色证明尝试（Ch10）
Frank Ramsey拉姆齐数（Ch6）
Arthur Cayley树的计数（Ch11）
Joseph KruskalMST 算法（Ch11）
Robert PrimMST 算法（Ch11）
Jan Łukasiewicz波兰记法（Ch11）
Øystein Ore哈密顿条件（Ch10）
Neil SloaneOEIS 整数序列库（Ch8）
Raymond Smullyan逻辑谜题大师（Ch1）
Stephen Kleene正则语言（Ch13）
Alonzo Churchλ 演算（Ch13）
John McCarthyLisp · AI（Ch13）
Peter NaurBNF 的 N（Ch13）
John Tukey"bit" 一词发明者（Ch1）
Alexandre VandermondeVandermonde 恒等式（Ch6）
John Venn维恩图（Ch2）
Archimedes 阿基米德附录一出场
Grace Brewster Murray HopperCobol · 编译（Ch13）

全书符号速查表

按主题分组的常用记号及其首见小节。完整版见原书末尾 List of Symbols（PDF p1115–1118）；国内教材个别记号习惯不同（如排列数用 A(n,r)），差异已在译名备注中说明。

符号含义首见
逻辑与证明
¬p否定（not p）1.1
p∧q合取（and）1.1
p∨q析取（or）1.1
p⊕q异或（xor）1.1
p→q条件（if…then）1.1
p↔q双条件（iff）1.1
p ≡ q逻辑等价1.3
T / F真 / 假1.1
∀x / ∃x全称量词 / 存在量词1.4
∴所以（推理符号）1.6
集合与函数
x∈S / x∉S属于 / 不属于2.1
∅空集2.1
A⊆B / A⊂B子集 / 真子集2.1
P(S)幂集2.1
A∪B / A∩B并 / 交2.2
A−B / A⊕B差 / 对称差2.2
A̅补集（关于论域 U）2.2
|A|基数（元素个数）2.1
A×B笛卡尔积2.1
f:A→B从 A 到 B 的函数2.3
f⁻¹ / f∘g反函数 / 函数合成2.3
⌊x⌋ / ⌈x⌉下取整 / 上取整2.3
Σᵢ₌ₘⁿ aᵢ求和记号2.4
aₙ / {aₙ}序列第 n 项 / 序列2.4
Aᵗ / A⊙B转置 / 布尔积2.6
整数与数论
a∣ba 整除 b4.1
a mod ba 除以 b 的余数4.1
a ≡ b (mod m)模 m 同余4.1
gcd(a,b) / lcm(a,b)最大公约数 / 最小公倍数4.3
φ(n)欧拉函数（≤n 互素个数）8.6
Z / N / Q / R整数 / 自然 / 有理 / 实数集2.1
计数与概率
P(n,r)排列数6.3
C(n,r) 或 (n r)组合数/二项式系数6.3
n! / n!!阶乘 / 双阶乘2.3,6
C(u,k)广义二项式系数8.4
p(E)事件概率7.1
p(E|F)条件概率7.2
E(X) / V(X)期望 / 方差7.4
关系与序
R ⊆ A×B关系9.1
Rⁿ关系的幂9.1
R*传递闭包/连通关系9.4
[a]ᵣ等价类9.5
a ⪯ b偏序关系9.6
a ≺ b严格偏序9.6
图与树
G=(V,E)图（顶点集、边集）10.1
deg(v) / deg⁻(v) / deg⁺(v)度 / 入度 / 出度10.2
Kₙ / K_{m,n} / Cₙ / Wₙ / Qₙ完全图/完全二部图/圈图/轮图/超立方体10.2
N(v)顶点 v 的邻域10.2
κ(G) / λ(G)点连通度 / 边连通度10.4
χ(G)色数10.8
n(T) / i(T) / l(T) / h(T)树的顶点数/内点数/叶数/高11.1
x₁x₂…xₙ 树形前缀码（叶码字）11.2
计算模型
V* / λ串的全集 / 空串13.1
S ⟹ w文法派生13.1
AB / A∪B / A*语言连接/并/Kleene闭包13.3-13.4
::=BNF 定义符13.1
M=(S,I,f,s₀,F)有限自动机五元组13.3

阅读与刷题 FAQ

Q1：英文原版读不动怎么办？
按"本页导学 → 原文对应小节 → 例题 → 奇数题"的顺序：先用本页中文建立框架，再读英文就能"对号入座"。术语表（每章关键词）可当中英对照字典用。

Q2：习题怎么刷效率最高？
每节先做奇数号基础题（能对答案），再挑 5–10 道进阶题；章末 Supplementary Exercises 限时模拟。全书 ≈4700 题不需要全做——按路线选 1/3 即可覆盖全部考点。

Q3：伪代码看不懂？
先读附录 A3（PDF p976–981）的伪代码约定，再看第 3 章开头两个例子。书上伪代码是类 Pascal 风格，与 C/Python 只有语法差异。

Q4：如何核对印刷页码？
印刷页码 = PDF 页码 − 23。本页所有页码标注均为 PDF 页码（供阅读器跳转用）。

Q5：每章学完如何自测？
① 合上书写出本章关键词表；② 说出每个定义并各举一例；③ 完成"Supplementary Exercises"前 20 题；④ 能向别人讲清楚本章一个"应用亮点"。四项全过再勾选小节的"已学"。

Q6：进度数据存在哪里？
浏览器 localStorage（本机），清缓存会丢失；换浏览器/设备不共享。

Q7：页面里的【原文摘录】和【编者注】是什么？
【原文摘录】是原书关键段落的简短英文引文（各处仅 1–3 句，标注 PDF 页码），供对照原文语境；【编者注 · 2026 视角】是原书（2018 年第 8 版）出版后该知识点的最新进展，与原书内容严格区分。完整内容请阅读原书。

Q8：术语翻译可靠吗？
术语以国内通行译法为准，与原书英文可能存在差异处以【译名备注】标明（如 pigeonhole＝抽屉原理、full binary tree≠国内“满二叉树”等重要辨析）。

没有匹配的小节，试试其他关键词，如 “鸽笼” “Bayes” “图着色”