离散数学，
从一句判断到一个结构。
沿屈婉玲、耿素云、张立昂《离散数学（第2版）》的全书结构，分 19 章学习核心概念、推导和例子，再用实验与自测检查理解。
每章 1 个实验、2 道自测，共 19 个实验和 38 道自测。先弄清条件和反例，再记符号。
六条主线怎样连接
第一次阅读建议顺序走；复习可以直接选章。每章顶部会标前置章节，例如格要先理解偏序，群要先理解运算与函数。
先做一个 30 秒检查
如果“p→q 为什么在 p 假时为真”还不清楚，从第1章开始。如果命题逻辑熟悉、量词顺序容易混，从第4章开始。如果只差考试复习，就先挑能明确说出前提与反例的一章。
全书目录
来源、约定与补充说明
主要依据：用户提供的《离散数学（第2版）》，屈婉玲、耿素云、张立昂；本次文件413页。已核对全书目录及各领域关键定义，未声称审校全书所有定理和习题。
保留本书同级联结词左结合、关系与函数复合先左后右、Fibonacci f₀=f₁=1、Catalan hₙ=Cₙ₋₁、环不自动含幺等约定。涉及同态保幺元的过宽表述，在第9章补足像内/满射条件。有限一阶模型检验不冒充普遍证明。
Stirling 补充边界参考 NIST DLMF §26.8；该站第一类采用带符号数，本页与教材使用无符号第一类。RSA 算例与实际密码编码的区别可对照 RFC 8017。
数理逻辑 · 第 1 章 · 教材 p3 / PDF 第 13 页起
命题逻辑的基本概念
把一句话写成可以逐行检查的逻辑公式。
程序的 if 条件、一个证明的前提，都需要先区分“句子表达了什么”和“它这一次是真是假”。命题逻辑先把不可再拆的判断抽成变量，再研究组合规则。
核心概念与条件
命题与赋值
命题是有确定真值的陈述句。p 可以表示“下雨”，赋值才指定这次 p 为真还是假；命题变量本身不是永真句。疑问句、命令句不作为命题。
联结词表达真值关系
¬p 是否定；p∧q 要两个都真；p∨q 只要至少一个真；p→q 只在 p 真而 q 假时为假；p↔q 要两者同真同假。逻辑的“或”默认允许同时成立。
公式与语法树
先按结构拆公式，再由内向外计算。书中优先级：括号、¬、∧、∨、→、↔；同级按从左到右结合。容易歧义的式子主动补括号。
沿着问题推导
- 第 1 步
要检验“若下雨则地湿”，先找唯一违背承诺的情形：下雨而地不湿。
- 第 2 步
这个反例条件是 p∧¬q，因此原命题真值等于 ¬(p∧¬q)。
- 第 3 步
德摩根律把它改写为 ¬p∨q，得到蕴涵的真值规则；p 假时的真并不宣称现实因果。
完整小例子
p=“通过笔试”，q=“通过面试”。要求至少过一项，但不能同时过。
至少一项：p∨q。排除同时通过：¬(p∧q)。把两个要求用∧连接。
(p∨q)∧¬(p∧q)：赋值 01、10 为真，00、11 为假。
动手检验这一章
常见误区
先自己判断，再看反馈
1. p 假、q 假时，p→q 是？
2. 本书中 p→q→r 怎样补括号？
本章小节索引与原书位置
本页讲解各章核心结构，小节索引用于回到原书继续阅读。页码先列印刷页，再列从1开始的PDF页。
- 1.1 命题与联结词：p3 / PDF 13
- 1.2 命题公式及其赋值：p9 / PDF 19
数理逻辑 · 第 2 章 · 教材 p19 / PDF 第 29 页起
命题逻辑等值演算
把“看着不同”的公式化成同一个真值函数。
真值表能判定等值，但复杂公式逐行枚举很慢。等值演算允许每一步换成意义相同的局部结构；范式则提供一种可比较、可处理的统一表示。
核心概念与条件
等值替换
A≡B 表示对全部赋值真值相同。交换、结合、分配、吸收、德摩根以及消去蕴涵都能用于子公式替换。等值不是“这一次恰好一样”。
主析取与主合取范式
每个真行贡献一个极小项，或起来得主析取范式；每个假行贡献一个极大项，与起来得主合取范式。每项都含全部变量一次。一般范式与主范式要区分。
完备集与消解
{¬,∧} 能表达∨，进而表达任意真值函数，是联结词完备集。合取范式也适合消解：由含 p 与含 ¬p 的两个子句推出消解子句。它是逻辑后果，不能一般当成等值替换。
沿着问题推导
- 第 1 步
取 p→q 的四行赋值，只有 10 为假。
- 第 2 步
真行 00、01、11 分别给 ¬p∧¬q、¬p∧q、p∧q；三项相或。
- 第 3 步
唯一假行 10 给极大项 ¬p∨q，已经是主合取范式。两种形式在每行都等于原式。
完整小例子
用子句 p∨q、¬p、¬q 判断能否同时为真。
前两句对 p 消解，得到 q；再与 ¬q 消解，得到空子句。
不可满足。空子句表示假，空子句集则表示没有约束，二者不要混淆。
动手检验这一章
常见误区
先自己判断，再看反馈
1. 公式的主析取范式怎样取行？
2. 由两个子句得到消解子句，一般属于？
本章小节索引与原书位置
本页讲解各章核心结构，小节索引用于回到原书继续阅读。页码先列印刷页，再列从1开始的PDF页。
- 2.1 等值式：p19 / PDF 29
- 2.2 析取范式与合取范式：p26 / PDF 36
- 2.3 联结词的完备集：p36 / PDF 46
- 2.4 可满足性问题与消解法：p38 / PDF 48
数理逻辑 · 第 3 章 · 教材 p46 / PDF 第 56 页起
命题逻辑的推理理论
区分“结论刚好为真”和“结论由前提必然推出”。
证明研究的是：只要接受所有前提，是否还能让结论为假。找到一个这样的赋值就能推翻论证；找不到则需要完整判定或演绎证明。
核心概念与条件
推理的有效性
Γ⊨B 要求所有使 Γ 中每个公式都真的赋值也使 B 真。结论本身不必永真。前提不可能同时真时，这个语义蕴涵仍成立。
自然推理
从前提和允许的临时假设开始，按规则写每一步理由。假言推理、合取引入/消去等规则保持真。临时假设必须记录何时引入、何时撤销。
附加前提与反证
若 Γ,A⊢B，则 Γ⊢A→B；撤销 A 得到的是条件句。反证法临时加入结论的否定，推出矛盾，再撤销该假设。消解证明法检查 Γ∧¬B 是否不可满足。
沿着问题推导
- 第 1 步
假设 p→q 与 q→r 都成立，目标是 p→r。
- 第 2 步
临时假设 p；由 p→q 得 q，再由 q→r 得 r。
- 第 3 步
撤销临时的 p，得到 p→r。这没有证明无条件的 r。
完整小例子
论证：p→q，q，所以 p。
取 p=0、q=1：第一个前提为真，第二个前提也为真，但结论 p 为假。
推理无效，这是肯定后件。一个反例足够否定“所有赋值均保持真”。
动手检验这一章
常见误区
先自己判断，再看反馈
1. p→q，¬q 能推出什么？
2. Γ,A⊢B，撤销 A 后得到？
本章小节索引与原书位置
本页讲解各章核心结构，小节索引用于回到原书继续阅读。页码先列印刷页，再列从1开始的PDF页。
- 3.1 推理的形式结构：p46 / PDF 56
- 3.2 自然推理系统P：p50 / PDF 60
- 3.3 消解证明法：p56 / PDF 66
数理逻辑 · 第 4 章 · 教材 p60 / PDF 第 70 页起
一阶逻辑基本概念
把“所有、存在、某个固定对象”分开。
“每位学生都有一本书”和“有一本书属于所有学生”在命题逻辑里可能各是一整块。一阶逻辑把对象、性质和对象之间的关系展开，量词顺序因而变得可见。
核心概念与条件
个体、谓词与论域
先指定非空论域，再解释常量、函数和谓词。S(x) 表示一个性质，R(x,y) 表示一个关系。若论域是全部人，“每位学生都到场”要写成 ∀x(S(x)→P(x))。
自由与约束变元
变元是否受某个量词约束由辖域决定。同一字母可以在不同位置有不同身份。没有自由变元的是闭式；开公式的真假还依赖自由变元赋值。
量词顺序就是依赖关系
∀x∃yR(x,y) 允许给不同 x 选择不同 y。∃y∀xR(x,y) 要先选同一个 y，再同时适配所有 x。解释是论域加符号含义，不是只给字母填数字。
沿着问题推导
- 第 1 步
论域 {0,1}，R(x,y) 定义为 x=y。
- 第 2 步
每个 x 都可以选 y=x，因此 ∀x∃yR(x,y) 真。
- 第 3 步
但固定 y=0 不适配 x=1，固定 y=1 不适配 x=0，所以 ∃y∀xR(x,y) 假。
完整小例子
把“每位学生都选了某门课”符号化，论域是全部人和课程。
引入 S(x)：x 是学生，C(y)：y 是课程，E(x,y)：x 选 y。学生条件用蕴涵，存在课程的条件用合取。
∀x(S(x)→∃y(C(y)∧E(x,y)))。若量词次序反过来，就要求同一门课。
动手检验这一章
常见误区
先自己判断，再看反馈
1. ∀x∃y 中的 y 可以随 x 改变吗？
2. 开公式真假通常还需要？
本章小节索引与原书位置
本页讲解各章核心结构，小节索引用于回到原书继续阅读。页码先列印刷页，再列从1开始的PDF页。
- 4.1 一阶逻辑命题符号化：p60 / PDF 70
- 4.2 一阶逻辑公式及其解释：p65 / PDF 75
数理逻辑 · 第 5 章 · 教材 p73 / PDF 第 83 页起
一阶逻辑等值演算与推理
安全地移动量词，并保留推理规则的条件。
量词也能变形，但改名和移动时必须防止变量被意外绑定。命题层的等值规则仍有用，只是替换进去的“一整句”现在可能含变量和量词。
核心概念与条件
否定量词与分配
“不是人人有选择”变成“有人没有选择”。∀ 可分配到∧，∃可分配到∨；∀对∨、∃对∧一般不能这样分配。
前束范式与换名
先消去→/↔，把否定向内推；将约束变元换成新名字，避免捕获；在满足自由变元条件时逐个把量词外提。前束范式一般不唯一。
一阶推理的限制
全称实例化可以取合适项；全称引入必须对任意对象成立。存在实例化引入新鲜见证，不能把它当预先固定的任意对象，也不能把见证擅自带出证明范围。
沿着问题推导
- 第 1 步
否定 ∀x∃yR(x,y)：先把外层“所有”变成“存在一个反例”。
- 第 2 步
得到 ∃x¬∃yR(x,y)，再把内部否定存在改成全称否定。
- 第 3 步
所以 ¬∀x∃yR(x,y) ≡ ∃x∀y¬R(x,y)：有人对任何 y 都不满足 R。
完整小例子
把 (∀xP(x))∨(∃xQ(x)) 化为前束形式。
两个 x 是不同约束，先将后者改成 y，得到 (∀xP(x))∨(∃yQ(y))。
非空域下可化为 ∀x∃y(P(x)∨Q(y))；换名保留各自原来的辖域。
动手检验这一章
常见误区
先自己判断，再看反馈
1. ¬∀x∃yR(x,y) 等值于？
2. ∃x(P(x)∧Q(x)) 能直接拆成两个存在式的等值吗？
本章小节索引与原书位置
本页讲解各章核心结构，小节索引用于回到原书继续阅读。页码先列印刷页，再列从1开始的PDF页。
- 5.1 一阶逻辑等值式与置换规则：p73 / PDF 83
- 5.2 一阶逻辑前束范式：p77 / PDF 87
- 5.3 一阶逻辑的推理理论：p79 / PDF 89
集合论 · 第 6 章 · 教材 p91 / PDF 第 101 页起
集合代数
用“一个元素是否属于”推导集合恒等式与计数。
集合把一批对象当成整体。与其凭图形直觉背公式，不如挑一个任意元素，用属于或不属于翻译成逻辑判断，再调用已经学过的逻辑律。
核心概念与条件
元素、子集与幂集
a∈A 判断一个对象是不是元素；A⊆B 判断 A 的每个元素是否都在 B 中。∅ 是每个集合的子集；幂集 P(A) 收集 A 的全部子集。
并交差补
并对应∨，交对应∧。差 A\B 保留在 A 不在 B 的元素；补集必须先约定全集 U。集合相等可证双向包含，或证任意元素的隶属条件等值。
有穷集计数
并集直接相加会重复交集，先加后减。三个集合要减两两交，再补回三重交。笛卡儿积的元素是有序对，大小相乘。
沿着问题推导
- 第 1 步
任取 x，x∈A∩(B∪C) 当且仅当 x∈A 且 (x∈B 或 x∈C)。
- 第 2 步
逻辑分配律给出 (x∈A且x∈B) 或 (x∈A且x∈C)。
- 第 3 步
这正是 x∈(A∩B)∪(A∩C)，任意元素都一致，所以集合相等。
完整小例子
A={1,2,3}，B={3,4}，全集 U={1,2,3,4}。
交为 {3}，并为 {1,2,3,4}；A\B={1,2}，Aᶜ={4}。
并集大小 3+2−1=4。交集元素 3 在前两项中被数了两次。
动手检验这一章
常见误区
先自己判断，再看反馈
1. P(∅) 有几个元素？
2. |A|=4，|B|=5，|A∩B|=2，并集大小为？
本章小节索引与原书位置
本页讲解各章核心结构，小节索引用于回到原书继续阅读。页码先列印刷页，再列从1开始的PDF页。
- 6.1 集合的基本概念：p91 / PDF 101
- 6.2 集合的运算：p94 / PDF 104
- 6.3 有穷集的计数：p96 / PDF 106
- 6.4 集合恒等式：p100 / PDF 110
集合论 · 第 7 章 · 教材 p110 / PDF 第 120 页起
二元关系
把关系看成可运算的有序对集合。
先修关系、相等关系、可达关系都能画成箭头，但它们满足的性质不同。关系矩阵让性质检查、复合、闭包成为具体运算。
核心概念与条件
关系与复合
R⊆A×B。对 A 上的关系，可用 n×n 布尔矩阵表示，行是起点、列是终点。本书 R∘S 表示先走 R，再走 S；矩阵对应布尔乘法。
四个性质与闭包
自反看对角；对称看转置；反对称禁止不同点双向；传递检查两步箭头能否合成一步。自反、对称、传递闭包分别补上最少的必要有序对。
等价与偏序
等价关系要自反、对称、传递，对应非空、不交、覆盖全集的划分。偏序要自反、反对称、传递，不要求任意两点可比较。Hasse 图只画覆盖边，省略自环和传递边。
沿着问题推导
- 第 1 步
若有 0R1、1R2，但没有 0R2，传递性失败。
- 第 2 步
补 0R2 可以修复这个三元组；再检查新增边会不会带来新的两步路径。
- 第 3 步
不断补到没有新边，得到传递闭包。只有出现正长度回路时才会因此补出某些对角项。
完整小例子
在 {0,1,2,3} 上定义 xRy 当且仅当 x、y 同奇偶。
每个数与自身同奇偶；交换顺序不变；同奇偶也可传递。
这是等价关系，划分为 {0,2}、{1,3}。它不是偏序，因为 0R2 且 2R0、0≠2。
动手检验这一章
常见误区
先自己判断，再看反馈
1. R∘S 按本书约定先走哪个？
2. 对称且反对称的关系一定不存在吗？
本章小节索引与原书位置
本页讲解各章核心结构，小节索引用于回到原书继续阅读。页码先列印刷页，再列从1开始的PDF页。
- 7.1 有序对与笛卡儿积：p110 / PDF 120
- 7.2 二元关系：p112 / PDF 122
- 7.3 关系的运算：p114 / PDF 124
- 7.4 关系的性质：p121 / PDF 131
- 7.5 关系的闭包：p126 / PDF 136
- 7.6 等价关系与划分：p131 / PDF 141
- 7.7 偏序关系：p135 / PDF 145
集合论 · 第 8 章 · 教材 p145 / PDF 第 155 页起
函数
检查一个对应是否是函数，再判断单射、满射与可逆性。
函数是受约束的关系：定义域每个输入都恰有一个输出。固定陪域后，是否覆盖全部输出、能否唯一反推输入才有明确答案。
核心概念与条件
函数、像与原像
f:A→B 必须对每个 a∈A 给唯一的 f(a)∈B。像 f(A) 可能小于陪域 B；原像 f⁻¹(C) 对任何函数都能定义，它不等于已经有了反函数。
单射、满射、双射
单射不把不同输入压到同一输出；满射覆盖整个陪域；双射兼具两者，才存在真正的双侧反函数。空定义域到任意陪域有唯一空函数。
复合、基数与应用
本书 f∘g 是先 f 再 g，所以 (f∘g)(x)=g(f(x))。双射建立等势；无限可数集可与 N 双射，可数也包括有限集。电话分机到用户的映射可用于区分多对一和一对一。
沿着问题推导
- 第 1 步
若想由 y 唯一恢复 x，首先每个 y∈B 得有人映到它，即满射。
- 第 2 步
若一个 y 来自两个不同 x，恢复便不唯一，所以还要单射。
- 第 3 步
两者同时成立才能给每个 y 定义唯一 f⁻¹(y)，并得到两边的恒等映射。
完整小例子
f:{0,1,2}→{0,1,2}，f(x)=x+1 mod 3。
输出序列 [1,2,0] 没有重复且覆盖陪域。反函数输出 [2,0,1]。
按书的顺序：f⁻¹∘f=I_B，f∘f⁻¹=I_A。若 A=B 这次字面相同，仍应理解类型。
动手检验这一章
常见误区
先自己判断，再看反馈
1. 任意函数都有集合原像 f⁻¹(C) 吗？
2. 3 个输入映到 4 个陪域元素，可能满射吗？
本章小节索引与原书位置
本页讲解各章核心结构，小节索引用于回到原书继续阅读。页码先列印刷页，再列从1开始的PDF页。
- 8.1 函数的定义与性质：p145 / PDF 155
- 8.2 函数的复合与反函数：p152 / PDF 162
- 8.3 双射函数与集合的基数：p156 / PDF 166
- 8.4 一个电话系统的描述实例：p164 / PDF 174
代数结构 · 第 9 章 · 教材 p177 / PDF 第 187 页起
代数系统
从运算表读出代数结构，而不是按数字名称猜。
集合相同，运算不同，结构可能完全不同。把“有哪些元素、做哪些运算、满足什么公理”一起给出，才能讨论单位元、逆元与结构之间的映射。
核心概念与条件
二元运算与算律
二元运算是 S×S→S 的函数：每对输入的结果唯一且仍在 S。结合律比较 (a*b)*c 与 a*(b*c)，交换律比较 a*b 与 b*a，它们互不替代。
单位元与逆元
双侧单位元 e 同时满足 e*a=a*e=a；双侧吸收元 θ 满足 θ*a=a*θ=θ。逆元相对于单位元定义。运算表的有限枚举可以精确判定这一个有限结构。
子代数、同态与同构
子代数对所列运算封闭，并保留签名中的常数。同态保持对应运算，同构再要求双射。仅保二元运算的同态，一般只保证源单位元映成像内单位元；整个目标的单位元还需附加条件。
沿着问题推导
- 第 1 步
要找单位元 e，先看第 e 行是否按列返回每个元素。
- 第 2 步
再看第 e 列是否按行返回每个元素，确认是双侧单位元。
- 第 3 步
找到 e 后，查每个元素是否在自己的行、列与同一个伙伴配对得到 e；最后仍要检查结合律，才能判断群。
完整小例子
比较 Z₃ 上的加法 mod 3 和乘法 mod 3。
加法的单位元是 0，各元素逆元为 0、2、1。乘法单位元是 1，但 0 找不到乘法逆元。
前者是群，后者是幺半群而不是群。同一元素“0”在两种运算里的作用不同。
动手检验这一章
常见误区
先自己判断，再看反馈
1. 结合律需要比较几元输入的两种括号？
2. 一般保二元运算的同态必把单位元映成目标整体单位元吗？
本章小节索引与原书位置
本页讲解各章核心结构，小节索引用于回到原书继续阅读。页码先列印刷页，再列从1开始的PDF页。
- 9.1 二元运算及其性质：p177 / PDF 187
- 9.2 代数系统：p185 / PDF 195
- 9.3 代数系统的同态与同构：p188 / PDF 198
代数结构 · 第 10 章 · 教材 p194 / PDF 第 204 页起
群与环
沿“加一条公理”区分半群、群、环和域。
代数不是一串结构名称。群抽取可逆运算，环同时组织加法与乘法，域再保证非零除法。每层多出的条件决定了可以合法进行哪些变形。
核心概念与条件
半群、幺半群与群
半群有结合律；幺半群再有单位元；群再要求每个元素可逆。群不默认交换。子群判据可用非空且 ab⁻¹∈H；仅说运算封闭一般不够。
陪集、元素阶与循环群
有限群由子群的陪集划分，得 |G|=|H|[G:H]。元素阶是最小正整数 t 使 aᵗ=e。循环群由一个元素生成；Zₙ 加法群中 g 的阶为 n/gcd(n,g)。
环与域
本书环：加法交换群、乘法半群、左右分配；不自动要求乘法单位元或交换。整环再要求乘法交换、有幺、无零因子；域至少两元素且每个非零元有乘法逆元。实验限制 n≥2。
沿着问题推导
- 第 1 步
在 Z₆ 加法群中从 0 连续加 2：0→2→4→0。
- 第 2 步
访问到 {0,2,4}，元素 2 的阶是 3；这是一个 3 阶子群。
- 第 3 步
换生成元 5 可遍历全部 6 个元素，因为 gcd(5,6)=1；乘法中 2·3=0 mod 6 则说明有零因子。
完整小例子
Z₅ 中求 2 的乘法逆元，并与 Z₆ 比较。
2·3=6≡1 mod 5，所以逆元为 3。在 mod 6 下 2 的倍数只会是偶数剩余类，不可能等于 1。
素数模下每个非零剩余类可逆；合数模下只有与模数互素的剩余类是单位。
动手检验这一章
常见误区
先自己判断，再看反馈
1. 群必须交换吗？
2. Z₆ 中 2 有乘法逆元吗？
本章小节索引与原书位置
本页讲解各章核心结构，小节索引用于回到原书继续阅读。页码先列印刷页，再列从1开始的PDF页。
- 10.1 群的定义及性质：p194 / PDF 204
- 10.2 子群与群的陪集分解：p198 / PDF 208
- 10.3 循环群与置换群：p205 / PDF 215
- 10.4 环与域：p210 / PDF 220
代数结构 · 第 11 章 · 教材 p220 / PDF 第 230 页起
格与布尔代数
把“共同上界/下界”变成可计算的两种运算。
在包含关系或整除关系里，两个元素通常有很多上界。格要求存在其中最小的一个，以及下界中最大的一个，因而把偏序与代数运算连起来。
核心概念与条件
格与确界
格的每一对元素都有最小上界 join 和最大下界 meet。只要求二元，不自动等于任意子集都有确界的完备格。最小上界属于这个偏序集合本身。
格的算律
交换、结合、吸收律刻画格的两种运算；幂等律可由它们导出。偏序与算律能互相恢复。子格要求对原格的 meet/join 封闭。
有补分配格
有界格先有最小元 0 和最大元 1。补元 b 要同时满足 a∧b=0、a∨b=1；一般格里补元未必唯一。有补再加分配律才是布尔代数。
沿着问题推导
- 第 1 步
正因子集合 D₆={1,2,3,6} 按整除排序。
- 第 2 步
2 与 3 的最大公共因子是 1、最小公倍数是 6，分别是 meet 和 join。
- 第 3 步
2 与 3 互补，1 与 6 互补；该整除格分配且每元有补，因此是布尔代数。
完整小例子
D₁₂={1,2,3,4,6,12} 中为 2 找补元。
若 gcd(2,b)=1，候选只有 1、3；lcm(2,1)=2，lcm(2,3)=6，都达不到顶元 12。
2 没有补元。这个正因子格仍是分配格，却不是布尔代数；底元这里是数字 1。
动手检验这一章
常见误区
先自己判断，再看反馈
1. 正因子整除格中的 meet 是？
2. 有界且有补就一定是布尔代数吗？
本章小节索引与原书位置
本页讲解各章核心结构，小节索引用于回到原书继续阅读。页码先列印刷页，再列从1开始的PDF页。
- 11.1 格的定义与性质：p220 / PDF 230
- 11.2 分配格、有补格与布尔代数：p227 / PDF 237
组合数学 · 第 12 章 · 教材 p237 / PDF 第 247 页起
基本的组合计数公式
先辨认对象是否有序、能否重复，再选计数公式。
大多数计数错误来自把不同的对象当成同一种对象。选人组成小组、给人排座位、反复选一种口味，是三个不同的集合，不能只看 n 和 k 套公式。
核心概念与条件
加法与乘法
互不重叠的分类可以相加；分步构造可用乘法，但每条前置路径的后续选择数须对应所乘的数量。类别重叠时用容斥或重新划分。
排列、组合与重复
不重复有序选 k 个：P(n,k)；无序选：C(n,k)。可重复有序长度 k 序列：nᵏ。库存无限或足够时，重复组合为 C(n+k−1,k)。
二项式与多项式系数
展开式的系数计数各因子中选项的位置。把 n 个不同位置分到各类，类大小 n₁…nᵣ 的多项式系数为 n!/(n₁!⋯nᵣ!)，其中各 nᵢ≥0 且总和 n。
沿着问题推导
- 第 1 步
从 5 个不同的人里依次选队长、副队长：5×4=20。
- 第 2 步
若只选两人小组，每组在有序选法里出现 2!=2 次。
- 第 3 步
所以共有 20/2=10 组；一般每个 k 人集合被排列 k! 次，得到组合公式。
完整小例子
3 种口味买 4 个冰淇淋，同口味不可区分，库存足够。
用 x₁+x₂+x₃=4、xᵢ≥0 表示每种数量。4 颗星中插入 2 个隔板，共 6 个位置选 2 个。
共有 C(6,2)=15 种。若按购买顺序记录，则是 3⁴=81 种，问题对象已经改变。
动手检验这一章
常见误区
先自己判断，再看反馈
1. 5 人选 2 人无职务小组共有？
2. 3 种符号组成长度 4 可重复序列，共有？
本章小节索引与原书位置
本页讲解各章核心结构，小节索引用于回到原书继续阅读。页码先列印刷页，再列从1开始的PDF页。
- 12.1 加法法则与乘法法则：p237 / PDF 247
- 12.2 排列与组合：p239 / PDF 249
- 12.3 二项式定理与组合恒等式：p243 / PDF 253
- 12.4 多项式定理：p248 / PDF 258
组合数学 · 第 13 章 · 教材 p253 / PDF 第 263 页起
递推方程与生成函数
从分解对象得到递推，再把序列编码成生成函数。
不容易一次数完时，先按最后一步或第一个分解点缩小问题。递推记录子问题的依赖，生成函数把整条序列放进一个代数对象，方便利用移位与卷积。
核心概念与条件
递推与初值
k 阶递推通常需要 k 个初值。常系数齐次线性递推可试 qⁿ 得到特征方程；重根 q 的重数为 e 时需 n⁰qⁿ…nᵉ⁻¹qⁿ。初值决定线性组合系数。
普通与指数生成函数
普通 G=Σaₙxⁿ，乘法把系数作卷积；指数 E=Σaₙxⁿ/n! 适合带标号对象。形式幂级数操作不要求给 x 赋数值，若实际代值才另讨论收敛。
Catalan 与两类 Stirling
本书 h₁=1，hₙ=Σhₖhₙ₋ₖ，等于常用 Cₙ₋₁。无符号第一类 c(n,k) 数 k 个轮换的置换；第二类 S(n,k) 数 k 个非空、无标号块的划分。
沿着问题推导
- 第 1 步
长度 n 的 1/2 步走法按最后一步分成：最后走 1 步，前面是 n−1；最后走 2 步，前面是 n−2。
- 第 2 步
两类不交，fₙ=fₙ₋₁+fₙ₋₂，空走法与一步走法都各 1。
- 第 3 步
令 G=Σfₙxⁿ，由移位得 G−1−x=x(G−1)+x²G，故 G=1/(1−x−x²)。
完整小例子
求把 4 个不同元素划成 2 个非空无标号块的方案数。
新增元素 4 要么独占一块：S(3,1)=1；要么加入已有 2 块之一：2S(3,2)=2×3。
S(4,2)=7。第一类 c(4,2)=11 数的是置换轮换，不是同一个问题。
动手检验这一章
常见误区
先自己判断，再看反馈
1. 按本书 f₀=f₁=1，f₅ 是？
2. S(4,2)=7 数的是？
本章小节索引与原书位置
本页讲解各章核心结构，小节索引用于回到原书继续阅读。页码先列印刷页，再列从1开始的PDF页。
- 13.1 递推方程的定义及实例：p253 / PDF 263
- 13.2 递推方程的迭代解法：p255 / PDF 265
- 13.3 递推方程的其他解法：p260 / PDF 270
- 13.4 生成函数及其应用：p268 / PDF 278
- 13.5 指数生成函数及其应用：p277 / PDF 287
- 13.6 Catalan数与Stirling数：p279 / PDF 289
图论 · 第 14 章 · 教材 p293 / PDF 第 303 页起
图的基本概念
把网络的连接、行走和矩阵表达互相转换。
图把对象抽象为点、联系抽象为边。先说明允许什么边、什么行走，才能用度数、连通性与矩阵回答网络问题。
核心概念与条件
图与度
一般图可有自环和重边，简单图排除两者；有向边区分起终点。无向自环给度数贡献 2，有向自环分别贡献一个入度和出度。下面实验使用无向简单图。
通路、路径与连通
本书“通路”允许重复点、边；简单通路不重复边；初级通路/路径不重复点（闭合情形允许首尾相同）。连通要求任意两点可达；有向图还要区分强、弱连通。
矩阵与图运算
邻接矩阵记录点对之间的边；简单无向图矩阵对称、对角为 0。A 的幂记录允许重复的行走，不是在数简单路径。补图、并、删点/删边等操作必须在指定顶点集下定义。
沿着问题推导
- 第 1 步
每条无向边有两个端点，因此在度数总和里被数两次。自环两个端点在同一顶点，仍贡献两次。
- 第 2 步
矩阵乘法 (A²)ᵢⱼ=ΣₖAᵢₖAₖⱼ：每个中间点 k 对应一段两步走法。
- 第 3 步
递推相乘便得到任意长度的计数，但其中允许走回来，所以不能解释成不重复点的路径。
完整小例子
4 环 0—1—2—3—0。
每点度为 2，总度 8=2×4。从 0 两步回到 0 可走 0→1→0 或 0→3→0。
(A²)₀₀=2，即 deg(0)。这两条都重复了顶点，说明矩阵幂不只统计初级路径。
动手检验这一章
常见误区
先自己判断，再看反馈
1. 无向自环对度数贡献？
2. A³ 统计的三步行走允许重复顶点吗？
本章小节索引与原书位置
本页讲解各章核心结构，小节索引用于回到原书继续阅读。页码先列印刷页，再列从1开始的PDF页。
- 14.1 图：p293 / PDF 303
- 14.2 通路与回路：p301 / PDF 311
- 14.3 图的连通性：p302 / PDF 312
- 14.4 图的矩阵表示：p308 / PDF 318
- 14.5 图的运算：p311 / PDF 321
图论 · 第 15 章 · 教材 p316 / PDF 第 326 页起
欧拉图与哈密顿图
分清“每边一次”和“每点一次”这两个旅行目标。
清扫每条街和访问每座城市看似相近，约束对象却不同。欧拉问题看边，哈密顿问题看点，前者有简单奇偶判据，后者一般更难。
核心概念与条件
欧拉通路与回路
欧拉通路恰好经过每条边一次；闭合时是欧拉回路。本书还要求全图连通，孤立点也影响“欧拉图”判断。连通无向图：0 个奇点有回路，2 个奇点有非闭合通路。
哈密顿圈
哈密顿圈经过所有顶点一次并回到起点，不要求用完所有边。不要从度数全偶推出哈密顿性。Dirac/Ore 等是带规模条件的充分条件，不是必要条件。
三类优化目标
最短路找两点之间最便宜的路；中国邮递员要覆盖每条边且可重复；货郎担要访问每个点，通常求最小权哈密顿圈。Dijkstra 要求非负边权。
沿着问题推导
- 第 1 步
在闭合的逐边旅行里，每次从某点进来都需要离开，这些边可以成对。
- 第 2 步
所以每点度必须为偶。连通性保证不能有无法到达的另一块。
- 第 3 步
若旅行有不同的起终点，它们各多一个出/入边，恰好成为两个奇点；其余点仍偶。
完整小例子
K₄ 有 4 个顶点，每点连向另外 3 点。
每点度为 3，共 4 个奇点，因而没有欧拉通路；但顺次沿 0→1→2→3→0 就访问每点一次。
K₄ 是哈密顿图，却不是欧拉图。两个三角形只共享中心的“蝴蝶结”则相反。
动手检验这一章
常见误区
先自己判断，再看反馈
1. 欧拉回路要求每个什么经过一次？
2. K₄ 是否有哈密顿圈？
本章小节索引与原书位置
本页讲解各章核心结构，小节索引用于回到原书继续阅读。页码先列印刷页，再列从1开始的PDF页。
- 15.1 欧拉图：p316 / PDF 326
- 15.2 哈密顿图：p320 / PDF 330
- 15.3 最短路问题、中国邮递员问题与货郎担问题：p323 / PDF 333
图论 · 第 16 章 · 教材 p329 / PDF 第 339 页起
树
用“连通且无环”理解树，再逐步构造最小生成树。
网络要连通而不想留冗余环，树就是最小的骨架。边权表示成本后，问题变为选择一棵总成本最低的生成树，而非分别找每个点的最短路。
核心概念与条件
无向树的等价性质
树是连通无环的无向图。n 点树有 n−1 边，任意两点恰一条路径。仅有 n−1 边不能单独推出是树，还要连通或无环。非平凡树至少两片叶。
生成树与贪心
生成树保留全部顶点，选取原图的一部分边。Kruskal 按权从小到大扫描，若连接不同分量便接受；成环则跳过。可以有负权；原图不连通时得到最小生成森林。
根树与二叉树
根把父子方向和层次固定，根层为 0、高度按边数。二叉树是每个结点至多两个孩子，满的情形才是每个内部结点恰两个；非平凡二叉树 n₀=n₂+1。
沿着问题推导
- 第 1 步
从 n 个单点分量开始，接受一条不成环的边，就把分量数减少 1。
- 第 2 步
接到 n−1 条时若已连通，恰好变成一棵树。
- 第 3 步
Kruskal 每次在当前某分量与外界之间选择可用的轻边，交换论证说明可保留一棵最优解与已选边兼容。
完整小例子
边权：01=1，02=4，03=6，12=2，23=3。
依序选 01、12、23，分别连起新的分量，总权 1+2+3=6。其余边会产生环。
得到一棵最小生成树。若某些权相同，可以有不同形状的最优树，但总最优权相同。
动手检验这一章
常见误区
先自己判断，再看反馈
1. 4 点 3 边就一定是树吗？
2. Kruskal 遇到负权边怎么办？
本章小节索引与原书位置
本页讲解各章核心结构，小节索引用于回到原书继续阅读。页码先列印刷页，再列从1开始的PDF页。
- 16.1 无向树及其性质：p329 / PDF 339
- 16.2 生成树：p331 / PDF 341
- 16.3 根树及其应用：p335 / PDF 345
图论 · 第 17 章 · 教材 p344 / PDF 第 354 页起
平面图
区分一个画法交叉与一个图无法无交叉嵌入。
把线画得交叉可能只是画法不巧。平面性问是否存在某种无交叉画法；欧拉公式与边数界提供强约束，但必要条件通过并不代表一定可画。
核心概念与条件
平面图、面与外部面
平面图是存在无边内交叉的平面嵌入的图；给定无交叉画法是平面嵌入。面包括无限的外部面，桥在一个面的边界中可能被计两次。
边数界与判别
简单平面图 V≥3 时 E≤3V−6；若无三角形则 E≤2V−4。违反界可判非平面，满足界不能直接判平面。Kuratowski 定理涉及与 K₅/K₃,₃ 同胚的子图，不能只找字面原图。
对偶图
固定平面嵌入后，把每个面变成对偶顶点，每条原边两侧的面连一条对偶边。桥的两侧属于同一面，所以在对偶中给出自环；对偶依赖嵌入。
沿着问题推导
- 第 1 步
树可以画成无交叉且只有一个面：V−E+1=V−(V−1)+1=2。
- 第 2 步
在保持连通的平面画法中加一条产生环的边，会把一个面一分为二，E 和 F 同时加 1。
- 第 3 步
因此 V−E+F 保持 2。若有 c 个分量，加入 c−1 条桥连接它们不增面，可推出 1+c。
完整小例子
K₃,₃：6 个顶点、9 条边。
普通界给 9≤3×6−6=12，检查通过但无法判平面。它是二部图，没有三角形，可用更强界 9≤2×6−4=8。
更强界被违反，所以非平面。K₅ 则直接违反 10≤3×5−6=9。
动手检验这一章
常见误区
先自己判断，再看反馈
1. E≤3V−6 能保证简单图平面吗？
2. 两个不相连点，无边，平面面数是多少？
本章小节索引与原书位置
本页讲解各章核心结构，小节索引用于回到原书继续阅读。页码先列印刷页，再列从1开始的PDF页。
- 17.1 平面图的基本概念：p344 / PDF 354
- 17.2 欧拉公式：p346 / PDF 356
- 17.3 平面图的判断：p349 / PDF 359
- 17.4 平面图的对偶图：p351 / PDF 361
图论 · 第 18 章 · 教材 p356 / PDF 第 366 页起
支配集、覆盖集、独立集、匹配与着色
明确覆盖的对象与极大/最大的区别，再用匹配和着色组织资源。
分配任务要求每人至多一个对象，安排时段要求冲突的任务不同色。匹配、覆盖、独立集和着色回答不同的资源问题，先说清楚“选点还是选边、覆盖谁”。
核心概念与条件
支配、覆盖、独立
支配集让每个未选点邻接某选点；点覆盖让每条边至少有一个选中端点；点独立集内部没有边。边覆盖选边覆盖全部顶点，有孤点便不存在边覆盖。
匹配与 Hall 条件
匹配的边两两没有公共端点。极大表示不能再加一条，最大表示边数最多。二部图匹配覆盖左部 X 的充要条件是每个 S⊆X 都有 |N(S)|≥|S|，不能只逐点看。
点着色、地图与边着色
点着色要求相邻点不同色；边着色要求共享端点的边不同色。二部图有边时点色数为 2，无边非空图为 1。简单图边色数在 Δ 与 Δ+1 之间；二部图边色数等于 Δ。简单平面图至多需要四种点色。
沿着问题推导
- 第 1 步
若点覆盖 C 的补集里有一条边，该边两个端点都没进 C，便漏盖，所以补集必独立。
- 第 2 步
反过来，补集独立意味着每条边不可能两个端点都在补集，必有端点在 C。
- 第 3 步
Hall 条件看一组左点共同拥有的可用右点；若邻居更少，鸽巢原理保证无法给每个左点分到不同右点。
完整小例子
左点 L0、L1 都只连 R0；L2 连 R1、R2。
逐点看每个左点都有邻居，但 S={L0,L1} 只有一个邻居 R0，|N(S)|=1<2。
不能覆盖全部左点，最大匹配只有 2 条。每点各有邻居不足以保证完整分配。
动手检验这一章
常见误区
先自己判断，再看反馈
1. Hall 条件必须检查哪些集合？
2. 点覆盖的补集是什么？
本章小节索引与原书位置
本页讲解各章核心结构，小节索引用于回到原书继续阅读。页码先列印刷页，再列从1开始的PDF页。
- 18.1 支配集、点覆盖集与点独立集：p356 / PDF 366
- 18.2 边覆盖集与匹配：p358 / PDF 368
- 18.3 二部图中的匹配：p360 / PDF 370
- 18.4 点着色：p362 / PDF 372
- 18.5 地图着色与平面图的点着色：p364 / PDF 374
- 18.6 边着色：p365 / PDF 375
初等数论 · 第 19 章 · 教材 p371 / PDF 第 381 页起
初等数论
从整除与最大公因数走到模逆、同余方程和一个加密算例。
计算机经常只关心除法余数。模运算里加减乘仍可做，但除法需要单位；欧几里得算法和互素条件说明什么时候能合法消去一个因子。
核心概念与条件
整除、素数与 gcd
素数分解是整数结构的基础。欧几里得算法用 gcd(a,b)=gcd(b,a mod b) 逐步缩小；Bézout 等式把 gcd 写成整数线性组合。实验限制正数与模数 m≥2。
一次同余与模逆
ax≡b mod m 有解当且仅当 d=gcd(a,m) 整除 b，有解时在 mod m 下恰 d 个剩余类。a 可逆当且仅当 gcd(a,m)=1，此时逆元模 m 唯一。
Euler、Fermat 与 RSA
互素时 a^φ(m)≡1 mod m；素数 p 且 p∤a 时 a^(p−1)≡1 mod p。RSA 教学例选不同素数 p,q，n=pq、ed≡1 mod φ(n)；非互素消息的恢复还需分别模 p、q 论证。
沿着问题推导
- 第 1 步
求 3 在 mod 40 下的逆元：40=13×3+1。
- 第 2 步
移项得 1=40−13×3，所以 (−13)×3≡1 mod 40。
- 第 3 步
−13≡27 mod 40，故逆元为 27。把这一过程一般化便是扩展欧几里得算法。
完整小例子
小型 RSA：p=5、q=11、n=55、φ(n)=40，取 e=3、d=27。
消息 7 加密得 7³ mod 55=13，解密 13²⁷ mod 55=7。消息 5 虽与 n 不互素，仍有 5→15→5。
这是小整数算术演示，不是安全加密方案；实际编码与协议还需专门标准，不能把无填充教材公式直接用于保密。
动手检验这一章
常见误区
先自己判断，再看反馈
1. a 在 mod m 下有逆元的条件？
2. 8x≡4 mod 6 有几个剩余类解？
本章小节索引与原书位置
本页讲解各章核心结构，小节索引用于回到原书继续阅读。页码先列印刷页，再列从1开始的PDF页。
- 19.1 素数：p371 / PDF 381
- 19.2 最大公约数与最小公倍数：p375 / PDF 385
- 19.3 同余：p377 / PDF 387
- 19.4 一次同余方程：p380 / PDF 390
- 19.5 欧拉定理和费马小定理：p382 / PDF 392
- 19.6 初等数论在计算机科学技术中的几个应用：p383 / PDF 393