离散数学精讲 本讲义面向大学二年级学生，依照耿素云、屈婉玲、张立昂编著的《离散数学（第六版）》（清华大学出版社，2021）编排章节顺序与内容范围，覆盖数理逻辑、集合论、图论、组合分析初步、代数结构及形式语言与自动机初步六大模块。每个概念都配有定义、定理、例题与易错点提示，帮助你从理解走向掌握。
标注说明 本讲义在正文标注了重难点与高频考点，格式约定如下：
下划线加粗 重难点 ，理解难度大或为后续内容的基础支撑下划线加粗斜体 高频必考点 ，期末/考研反复出现，务必熟练下划线斜体 易错提示 ，考试中常见失分点已有的"易错点"标注保持不变 目录 第一篇 数理逻辑 数理逻辑是用数学方法研究推理的学科，它是离散数学的基石，也是计算机科学中程序验证、逻辑电路、自动推理的理论源头。本篇分命题逻辑与一阶逻辑两层，从"句子层面的真值推理"逐步上升到"带量词的精细推理"。
第1章 命题逻辑 1.1 命题符号化及联结词 命题 （proposition）是能判断真假的陈述句。它要么真（T/1），要么假（F/0），不能两者皆是，也不能无法判断。
判断一个句子是否命题的关键不是"它事实上是否为真"，而是"它是否具有唯一的真假值"。例如"2026 年人类将登上火星"目前无法证实，但它在逻辑上要么为真要么为假，因此仍是命题；而"这句话是假的"导致悖论，不是命题。
简单命题（原子命题）用小写字母 p , q , r , … p, q, r, \dots p , q , r , …
联结词 符号 读法 p ¬ p p\ \neg\!p p ¬ p 否定 ¬ p \neg p ¬ p 非 p p p T → F , F → T T\to F,\ F\to T T → F , F → T 合取 p ∧ q p\land q p ∧ q p p p q q q 同真才真 析取 p ∨ q p\lor q p ∨ q p p p q q q 同假才假 蕴涵 p → q p\to q p → q 若 p p p q q q 仅 T → F T\to F T → F 等价 p ↔ q p\leftrightarrow q p ↔ q p p p q q q 同真同假为真
例（真题） 判断下列语句是否为命题，若是指出其真值：
"2 是偶数。" "请勿喧哗！" "x + 1 > 2 x+1>2 x + 1 > 2 "太阳从西方升起。" 解 (1) 是命题，真值为 T。(2) 不是命题（祈使句，无真假）。(3) 不是命题（含变元，无法判断真假）。(4) 是命题，真值为 F。
易错点 ：日常语言里的"或"有时是"不可兼或"（排斥或，如"要么左要么右"）。命题逻辑中的 ∨ \lor ∨ 可兼或 （inclusive or），排斥或需写成 ( p ∨ q ) ∧ ¬ ( p ∧ q ) (p\lor q)\land\neg(p\land q) ( p ∨ q ) ∧ ¬ ( p ∧ q ) p → q p\to q p → q p p p q q q 1 + 1 = 3 → 1+1=3 \to 1 + 1 = 3 →
1.2 命题公式及分类 命题变元 是取值 T/F 的变量；命题公式 （合式公式，well-formed formula）由变元、联结词与括号递归构成。优先级从高到低：¬ > ∧ > ∨ > → ↔ \neg > \land > \lor > \to \leftrightarrow ¬ > ∧ > ∨ >→↔
对公式中每个变元赋一组真值，公式便有一个确定的真值。列出所有赋值下公式的真值，即得真值表 。n n n 2 n 2^n 2 n
若公式在所有赋值下均为真，称为永真式 （重言式，tautology）； 若均为假，称为永假式 （矛盾式，contradiction）； 若至少有一组赋值使其为真、至少有一组使其为假，称为可满足式 （satisfiable）。 易错点 ："p → q p\to q p → q p → ¬ q p\to\neg q p → ¬ q p ∧ ¬ q p\land\neg q p ∧ ¬ q
1.3 等值演算 本节为高频必考点，期末/考研反复出现等值化简题
若两个公式 A , B A, B A , B A A A B B B 等值 ，记 A ⇔ B A \Leftrightarrow B A ⇔ B A ↔ B A\leftrightarrow B A ↔ B
双重否定：¬ ( ¬ p ) ⇔ p \neg(\neg p)\Leftrightarrow p ¬ ( ¬ p ) ⇔ p 德摩根：¬ ( p ∧ q ) ⇔ ¬ p ∨ ¬ q \neg(p\land q)\Leftrightarrow \neg p\lor\neg q ¬ ( p ∧ q ) ⇔ ¬ p ∨ ¬ q ¬ ( p ∨ q ) ⇔ ¬ p ∧ ¬ q \neg(p\lor q)\Leftrightarrow \neg p\land\neg q ¬ ( p ∨ q ) ⇔ ¬ p ∧ ¬ q 蕴涵等值：p → q ⇔ ¬ p ∨ q ⇔ ¬ q → ¬ p p\to q \Leftrightarrow \neg p\lor q \Leftrightarrow \neg q\to\neg p p → q ⇔ ¬ p ∨ q ⇔ ¬ q → ¬ p 等价等值：p ↔ q ⇔ ( p → q ) ∧ ( q → p ) p\leftrightarrow q \Leftrightarrow (p\to q)\land(q\to p) p ↔ q ⇔ ( p → q ) ∧ ( q → p ) 分配律：p ∨ ( q ∧ r ) ⇔ ( p ∨ q ) ∧ ( p ∨ r ) p\lor(q\land r)\Leftrightarrow(p\lor q)\land(p\lor r) p ∨ ( q ∧ r ) ⇔ ( p ∨ q ) ∧ ( p ∨ r ) p ∧ ( q ∨ r ) ⇔ ( p ∧ q ) ∨ ( p ∧ r ) p\land(q\lor r)\Leftrightarrow(p\land q)\lor(p\land r) p ∧ ( q ∨ r ) ⇔ ( p ∧ q ) ∨ ( p ∧ r ) 吸收律：p ∧ ( p ∨ q ) ⇔ p p\land(p\lor q)\Leftrightarrow p p ∧ ( p ∨ q ) ⇔ p p ∨ ( p ∧ q ) ⇔ p p\lor(p\land q)\Leftrightarrow p p ∨ ( p ∧ q ) ⇔ p 同一律/零律：p ∨ F ⇔ p p\lor F\Leftrightarrow p p ∨ F ⇔ p p ∧ T ⇔ p p\land T\Leftrightarrow p p ∧ T ⇔ p p ∧ F ⇔ F p\land F\Leftrightarrow F p ∧ F ⇔ F p ∨ T ⇔ T p\lor T\Leftrightarrow T p ∨ T ⇔ T 幂等律：p ∨ p ⇔ p p\lor p\Leftrightarrow p p ∨ p ⇔ p p ∧ p ⇔ p p\land p\Leftrightarrow p p ∧ p ⇔ p 等值演算就是反复套用这些律，把公式化成所需形式，比真值表更高效。
例（真题） 用等值演算法判断公式 p → ( q → r ) p\to(q\to r) p → ( q → r ) ( p ∧ q ) → r (p\land q)\to r ( p ∧ q ) → r
解
p → ( q → r ) ⇔ ¬ p ∨ ( q → r ) ⇔ ¬ p ∨ ( ¬ q ∨ r ) ⇔ ( ¬ p ∨ ¬ q ) ∨ r ⇔ ¬ ( p ∧ q ) ∨ r ⇔ ( p ∧ q ) → r . p\to(q\to r)\Leftrightarrow \neg p\lor(q\to r)\Leftrightarrow \neg p\lor(\neg q\lor r)\Leftrightarrow(\neg p\lor\neg q)\lor r\Leftrightarrow \neg(p\land q)\lor r\Leftrightarrow(p\land q)\to r. p → ( q → r ) ⇔ ¬ p ∨ ( q → r ) ⇔ ¬ p ∨ ( ¬ q ∨ r ) ⇔ ( ¬ p ∨ ¬ q ) ∨ r ⇔ ¬ ( p ∧ q ) ∨ r ⇔ ( p ∧ q ) → r .
故两公式等值。这也是 CP 规则（附加前提证明法）的理论依据。
例 化简 p ∨ ( ¬ p ∧ q ) p\lor(\neg p\land q) p ∨ ( ¬ p ∧ q )
p ∨ ( ¬ p ∧ q ) ⇔ ( p ∨ ¬ p ) ∧ ( p ∨ q ) ⇔ T ∧ ( p ∨ q ) ⇔ p ∨ q . p\lor(\neg p\land q)\Leftrightarrow(p\lor\neg p)\land(p\lor q)\Leftrightarrow T\land(p\lor q)\Leftrightarrow p\lor q. p ∨ ( ¬ p ∧ q ) ⇔ ( p ∨ ¬ p ) ∧ ( p ∨ q ) ⇔ T ∧ ( p ∨ q ) ⇔ p ∨ q .
1.4 范式 本节为高频必考点，求主析取范式/主合取范式是期末必考题型
把公式化为标准形式便于比较与判断永真永假。两类基本形式：
析取范式 （DNF）：有限个合取项 的析取，即 ⋁ i ( ⋀ j l i j ) \bigvee_i(\bigwedge_j l_{ij}) ⋁ i ( ⋀ j l ij ) l i j l_{ij} l ij 合取范式 （CNF）：有限个析取项 的合取，即 ⋀ i ( ⋁ j l i j ) \bigwedge_i(\bigvee_j l_{ij}) ⋀ i ( ⋁ j l ij ) 更具规范性的标准形式是主范式 。设公式含 n n n p 1 , … , p n p_1,\dots,p_n p 1 , … , p n
极小项 （minterm）m k m_k m k 恰好出现一次 的合取式。n n n 2 n 2^n 2 n k k k 极大项 （maxterm）M k M_k M k 下标约定（关键） m k m_k m k M k M_k M k 相反 ，这是最容易记混的地方，务必对照真值表。
主析取范式 （PDNF）：公式所有成真赋值对应的极小项之析取：A = ⋁ m k i A=\bigvee m_{k_i} A = ⋁ m k i 主合取范式 （PCNF）：公式所有成假赋值对应的极大项之合取：A = ⋀ M k j A=\bigwedge M_{k_j} A = ⋀ M k j 任一非永真永假公式都有唯一的主析取范式和唯一的主合取范式。永真式主析取范式为 ⋁ k = 0 2 n − 1 m k = T \bigvee_{k=0}^{2^n-1}m_k=T ⋁ k = 0 2 n − 1 m k = T T T T
例 求 p → q p\to q p → q ¬ p ∨ q \neg p\lor q ¬ p ∨ q n = 2 n=2 n = 2
真值表（下标按 p p p k = 2 p + q k=2p+q k = 2 p + q
p p p q q q k k k p → q p\to q p → q 极小项 极大项 0 0 0 1 m 0 = ¬ p ∧ ¬ q m_0=\neg p\land\neg q m 0 = ¬ p ∧ ¬ q — 0 1 1 1 m 1 = ¬ p ∧ q m_1=\neg p\land q m 1 = ¬ p ∧ q — 1 0 2 0 — M 2 = ¬ p ∨ q M_2=\neg p\lor q M 2 = ¬ p ∨ q 1 1 3 1 m 3 = p ∧ q m_3=p\land q m 3 = p ∧ q —
成真赋值对应 k = 0 , 1 , 3 k=0,1,3 k = 0 , 1 , 3
主析取范式 = m 0 ∨ m 1 ∨ m 3 = ( ¬ p ∧ ¬ q ) ∨ ( ¬ p ∧ q ) ∨ ( p ∧ q ) . \text{主析取范式}=m_0\lor m_1\lor m_3=(\neg p\land\neg q)\lor(\neg p\land q)\lor(p\land q). 主析取范式 = m 0 ∨ m 1 ∨ m 3 = ( ¬ p ∧ ¬ q ) ∨ ( ¬ p ∧ q ) ∨ ( p ∧ q ) .
成假赋值对应 k = 2 k=2 k = 2
主合取范式 = M 2 = ¬ p ∨ q . \text{主合取范式}=M_2=\neg p\lor q. 主合取范式 = M 2 = ¬ p ∨ q .
验证：M 2 M_2 M 2 p = 1 → ¬ p p=1\to\neg p p = 1 → ¬ p q = 0 → q q=0\to q q = 0 → q ¬ p ∨ q \neg p\lor q ¬ p ∨ q
例（真题） 求公式 A = ( p ∧ q ) → r A=(p\land q)\to r A = ( p ∧ q ) → r
解 A A A p , q , r p,q,r p , q , r 2 3 = 8 2^3=8 2 3 = 8 A ⇔ ¬ ( p ∧ q ) ∨ r ⇔ ¬ p ∨ ¬ q ∨ r A\Leftrightarrow \neg(p\land q)\lor r\Leftrightarrow \neg p\lor\neg q\lor r A ⇔ ¬ ( p ∧ q ) ∨ r ⇔ ¬ p ∨ ¬ q ∨ r
列真值表（下标 k = 4 p + 2 q + r k=4p+2q+r k = 4 p + 2 q + r
p p p q q q r r r k k k A A A 极小项/极大项 0 0 0 0 1 m 0 m_0 m 0 0 0 1 1 1 m 1 m_1 m 1 0 1 0 2 1 m 2 m_2 m 2 0 1 1 3 1 m 3 m_3 m 3 1 0 0 4 1 m 4 m_4 m 4 1 0 1 5 1 m 5 m_5 m 5 1 1 0 6 0 M 6 M_6 M 6 1 1 1 7 1 m 7 m_7 m 7
成真赋值对应 k = 0 , 1 , 2 , 3 , 4 , 5 , 7 k=0,1,2,3,4,5,7 k = 0 , 1 , 2 , 3 , 4 , 5 , 7
A = m 0 ∨ m 1 ∨ m 2 ∨ m 3 ∨ m 4 ∨ m 5 ∨ m 7 . A=m_0\lor m_1\lor m_2\lor m_3\lor m_4\lor m_5\lor m_7. A = m 0 ∨ m 1 ∨ m 2 ∨ m 3 ∨ m 4 ∨ m 5 ∨ m 7 .
成假赋值对应 k = 6 k=6 k = 6 A = M 6 = ¬ p ∨ ¬ q ∨ r A=M_6=\neg p\lor\neg q\lor r A = M 6 = ¬ p ∨ ¬ q ∨ r
可由主范式直接读出：成真赋值为 ( 000 , 001 , 010 , 011 , 100 , 101 , 111 ) (000,001,010,011,100,101,111) ( 000 , 001 , 010 , 011 , 100 , 101 , 111 ) ( 110 ) (110) ( 110 )
1.5 联结词全功能集 本节为重难点，理解全功能集的概念与判定是逻辑电路设计的基础
在实际应用（尤其是逻辑电路设计）中，并非所有联结词都需要独立使用。如果一个联结词集合能够表示所有可能的命题公式（即能表达任一真值函数），则称该集合为全功能集 （functionally complete）。
{ ¬ , ∧ , ∨ } \{\neg, \land, \lor\} { ¬ , ∧ , ∨ }
p → q ⇔ ¬ p ∨ q p\to q \Leftrightarrow \neg p\lor q p → q ⇔ ¬ p ∨ q p ↔ q ⇔ ( p → q ) ∧ ( q → p ) ⇔ ( ¬ p ∨ q ) ∧ ( ¬ q ∨ p ) p\leftrightarrow q \Leftrightarrow (p\to q)\land(q\to p) \Leftrightarrow (\neg p\lor q)\land(\neg q\lor p) p ↔ q ⇔ ( p → q ) ∧ ( q → p ) ⇔ ( ¬ p ∨ q ) ∧ ( ¬ q ∨ p ) 进一步可以缩减：
{ ¬ , ∧ } \{\neg, \land\} { ¬ , ∧ } p ∨ q ⇔ ¬ ( ¬ p ∧ ¬ q ) p\lor q\Leftrightarrow \neg(\neg p\land\neg q) p ∨ q ⇔ ¬ ( ¬ p ∧ ¬ q ) { ¬ , ∨ } \{\neg, \lor\} { ¬ , ∨ } p ∧ q ⇔ ¬ ( ¬ p ∨ ¬ q ) p\land q\Leftrightarrow \neg(\neg p\lor\neg q) p ∧ q ⇔ ¬ ( ¬ p ∨ ¬ q ) 极小全功能集 ：不能再去掉任一联结词仍保持全功能性的集合。{ ¬ , ∧ } \{\neg, \land\} { ¬ , ∧ } { ¬ , ∨ } \{\neg, \lor\} { ¬ , ∨ }
在实际电路中更常用的是单一联结词全功能集 ，即仅用一个联结词即可表示所有公式：
与非 （NAND）：p ↑ q = ¬ ( p ∧ q ) p \uparrow q = \neg(p\land q) p ↑ q = ¬ ( p ∧ q ) 或非 （NOR）：p ↓ q = ¬ ( p ∨ q ) p \downarrow q = \neg(p\lor q) p ↓ q = ¬ ( p ∨ q ) { ↑ } \{\uparrow\} { ↑ } { ↓ } \{\downarrow\} { ↓ } { ↑ } \{\uparrow\} { ↑ }
¬ p = p ↑ p \neg p = p \uparrow p ¬ p = p ↑ p p ∧ q = ¬ ( p ↑ q ) = ( p ↑ q ) ↑ ( p ↑ q ) p\land q = \neg(p\uparrow q) = (p\uparrow q)\uparrow(p\uparrow q) p ∧ q = ¬ ( p ↑ q ) = ( p ↑ q ) ↑ ( p ↑ q ) p ∨ q = ¬ p ↑ ¬ q = ( p ↑ p ) ↑ ( q ↑ q ) p\lor q = \neg p\uparrow \neg q = (p\uparrow p)\uparrow(q\uparrow q) p ∨ q = ¬ p ↑ ¬ q = ( p ↑ p ) ↑ ( q ↑ q ) 易错点 ：{ ∧ , ∨ } \{\land, \lor\} { ∧ , ∨ } ¬ \neg ¬
例（真题） 证明 { ˉ } \{\bar{}\} { ˉ } p → q p\to q p → q
解 先恢复否定与各联结词：
¬ p = p ↑ p , p ∧ q = ( p ↑ q ) ↑ ( p ↑ q ) , p ∨ q = ( p ↑ p ) ↑ ( q ↑ q ) . \neg p=p\uparrow p,\quad p\land q=(p\uparrow q)\uparrow(p\uparrow q),\quad p\lor q=(p\uparrow p)\uparrow(q\uparrow q). ¬ p = p ↑ p , p ∧ q = ( p ↑ q ) ↑ ( p ↑ q ) , p ∨ q = ( p ↑ p ) ↑ ( q ↑ q ) .
故 { ↑ } \{\uparrow\} { ↑ }
p → q ⇔ ¬ p ∨ q ⇔ ( p ↑ p ) ↑ ( q ↑ q ) . p\to q\Leftrightarrow \neg p\lor q\Leftrightarrow (p\uparrow p)\uparrow(q\uparrow q). p → q ⇔ ¬ p ∨ q ⇔ ( p ↑ p ) ↑ ( q ↑ q ) .
1.6 组合电路 命题逻辑的直接工程应用是组合电路 （combinational circuit）。组合电路由逻辑门（与门、或门、非门、与非门、或非门、异或门等）构成，输出仅取决于当前输入，无记忆功能。
每个逻辑门对应一个联结词，电路的输入输出关系可用命题公式描述。设计组合电路的典型流程：
分析问题，确定输入变元与输出； 列真值表； 由真值表写出主析取范式（所有输出为 1 的行对应极小项之析取）； 用等值演算或卡诺图化简； 选定逻辑门实现。 例 设计一个三人表决电路：三人 A , B , C A,B,C A , B , C F = 1 F=1 F = 1
真值表中 F = 1 F=1 F = 1 011 , 101 , 110 , 111 011, 101, 110, 111 011 , 101 , 110 , 111 m 1 , m 2 , m 3 m_1, m_2, m_3 m 1 , m 2 , m 3 A B C ABC A B C k = 4 A + 2 B + C k=4A+2B+C k = 4 A + 2 B + C m 3 , m 5 , m 6 , m 7 m_3, m_5, m_6, m_7 m 3 , m 5 , m 6 , m 7
主析取范式：
F = m 3 ∨ m 5 ∨ m 6 ∨ m 7 = A ˉ B C ∨ A B ˉ C ∨ A B C ˉ ∨ A B C . F=m_3\lor m_5\lor m_6\lor m_7=\bar A BC\lor A\bar B C\lor AB\bar C\lor ABC. F = m 3 ∨ m 5 ∨ m 6 ∨ m 7 = A ˉ B C ∨ A B ˉ C ∨ A B C ˉ ∨ A B C .
化简：
F = A B ∨ A C ∨ B C . F=AB\lor AC\lor BC. F = A B ∨ A C ∨ B C .
即"任意两人同意即通过"，可用两个与门和一个或门（再加非门取反输入）实现。
卡诺图 （Karnaugh map）是化简少变元布尔表达式的图示工具，将 2 n 2^n 2 n
例（真题） 设计一个组合逻辑电路：输入 A , B , C A,B,C A , B , C F = 1 F=1 F = 1
解 质数对应的输入为 A , B , C = ( 0 , 1 , 0 ) , ( 0 , 1 , 1 ) , ( 1 , 0 , 1 ) , ( 1 , 1 , 1 ) A,B,C=(0,1,0),(0,1,1),(1,0,1),(1,1,1) A , B , C = ( 0 , 1 , 0 ) , ( 0 , 1 , 1 ) , ( 1 , 0 , 1 ) , ( 1 , 1 , 1 ) m 2 , m 3 , m 5 , m 7 m_2,m_3,m_5,m_7 m 2 , m 3 , m 5 , m 7
主析取范式 F = m 2 ∨ m 3 ∨ m 5 ∨ m 7 = A ˉ B C ∨ A ˉ B C ∨ A B ˉ C ∨ A B C F=m_2\lor m_3\lor m_5\lor m_7=\bar A BC\lor \bar A BC\lor A\bar B C\lor ABC F = m 2 ∨ m 3 ∨ m 5 ∨ m 7 = A ˉ B C ∨ A ˉ B C ∨ A B ˉ C ∨ A B C
F = A ˉ B ∨ A C . F=\bar A B\lor AC. F = A ˉ B ∨ A C .
即"B B B A A A A A A C C C
1.7 推理理论 本节为高频必考点，推理证明是期末/考研必考的解答大题
推理形式 ：前提 A 1 , … , A k A_1,\dots,A_k A 1 , … , A k B B B A 1 , … , A k ⊢ B A_1,\dots,A_k\vdash B A 1 , … , A k ⊢ B ( A 1 ∧ ⋯ ∧ A k ) → B (A_1\land\dots\land A_k)\to B ( A 1 ∧ ⋯ ∧ A k ) → B
推理规则（关键的有效推理形式）：
名称 形式 含义 假言推理（MP） p , p → q ⊢ q p,\ p\to q \vdash q p , p → q ⊢ q 肯定前件 拒取式（MT） ¬ q , p → q ⊢ ¬ p \neg q,\ p\to q\vdash \neg p ¬ q , p → q ⊢ ¬ p 否定后件 假言三段论 p → q , q → r ⊢ p → r p\to q,\ q\to r \vdash p\to r p → q , q → r ⊢ p → r 蕴涵传递 析取三段论 p ∨ q , ¬ p ⊢ q p\lor q,\ \neg p\vdash q p ∨ q , ¬ p ⊢ q 排除一支 构造性二难 p → q , r → s , p ∨ r ⊢ q ∨ s p\to q,\ r\to s,\ p\lor r\vdash q\lor s p → q , r → s , p ∨ r ⊢ q ∨ s 二难 化简 p ∧ q ⊢ p p\land q\vdash p p ∧ q ⊢ p 合取分解 附加 p ⊢ p ∨ q p\vdash p\lor q p ⊢ p ∨ q 析取引入
构造证明的常用方法：直接证明法、附加前提证明法（CP 规则，用于结论为蕴涵式时把结论前件当额外前提）、反证法（归谬，假设结论不成立推出矛盾）与归谬赋值法（判断有效性）。
例 证明 p → q , ¬ q ⊢ ¬ p p\to q,\ \neg q\vdash \neg p p → q , ¬ q ⊢ ¬ p
反证法：设结论 ¬ p \neg p ¬ p p p p p → q p\to q p → q p p p q q q ¬ q \neg q ¬ q ¬ p \neg p ¬ p
例（真题） 在自然推理系统中构造下面推理的证明：
前提：p ∨ q , p → r , q → r p\lor q,\ p\to r,\ q\to r p ∨ q , p → r , q → r r r r
解
步骤 公式 理由 (1) p ∨ q p\lor q p ∨ q 前提 P (2) p → r p\to r p → r 前提 P (3) q → r q\to r q → r 前提 P (4) ¬ p → q \neg p\to q ¬ p → q 由(1)蕴含等值式 (5) ¬ p → r \neg p\to r ¬ p → r 由(4)(3)假言三段论 (6) p → r p\to r p → r 即(2) (7) r r r 由(5)(6)构造性二难
故 r r r
第2章 一阶逻辑 命题逻辑以整句为单位，无法表达"所有""存在"等内部量词结构。一阶逻辑（又称谓词逻辑）把句子拆成个体词与谓词，引入量词，推理能力更强。
2.1 一阶逻辑基本概念 本节为高频必考点，一阶逻辑命题符号化是考试常出题
个体词 （常量或变量）指论域（个体域）中的对象；谓词 刻画个体具有的性质或关系。一元谓词 P ( x ) P(x) P ( x ) x x x P P P n n n P ( x 1 , … , x n ) P(x_1,\dots,x_n) P ( x 1 , … , x n ) x 1 , … , x n x_1,\dots,x_n x 1 , … , x n P P P
两个量词：
全称量词 ∀ x P ( x ) \forall x\, P(x) ∀ x P ( x ) x x x P P P 存在量词 ∃ x P ( x ) \exists x\, P(x) ∃ x P ( x ) x x x P P P 例 符号化"所有人都会死"。
设论域为全人类，M ( x ) M(x) M ( x ) x x x D ( x ) D(x) D ( x ) x x x ∀ x ( M ( x ) → D ( x ) ) \forall x(M(x)\to D(x)) ∀ x ( M ( x ) → D ( x )) ∀ x D ( x ) \forall x\,D(x) ∀ x D ( x )
易错点 ：量词的辖域 （作用范围）必须用括号界定，移动或省略括号会改变含义。例如 ∀ x ( P ( x ) → Q ( x ) ) \forall x(P(x)\to Q(x)) ∀ x ( P ( x ) → Q ( x )) ( ∀ x P ( x ) ) → Q ( x ) (\forall x\,P(x))\to Q(x) ( ∀ x P ( x )) → Q ( x ) Q ( x ) Q(x) Q ( x ) x x x
例（真题） 将下列语句符号化：
"每个实数都大于它的平方。"（论域：实数集） "有些人既聪明又勤奋。"（论域：全人类） 解 (1) 设 G ( x ) G(x) G ( x ) x > x 2 x>x^2 x > x 2 ∀ x G ( x ) \forall x\,G(x) ∀ x G ( x )
(2) 设 S ( x ) S(x) S ( x ) x x x D ( x ) D(x) D ( x ) x x x ∃ x ( S ( x ) ∧ D ( x ) ) \exists x(S(x)\land D(x)) ∃ x ( S ( x ) ∧ D ( x ))
易错点 ：全称量词配蕴涵 ∀ x ( P ( x ) → Q ( x ) ) \forall x(P(x)\to Q(x)) ∀ x ( P ( x ) → Q ( x )) ∃ x ( P ( x ) ∧ Q ( x ) ) \exists x(P(x)\land Q(x)) ∃ x ( P ( x ) ∧ Q ( x )) ∃ x ( P ( x ) → Q ( x ) ) \exists x(P(x)\to Q(x)) ∃ x ( P ( x ) → Q ( x )) P ( x ) P(x) P ( x )
2.2 一阶逻辑合式公式及解释 一阶逻辑合式公式 （简称公式）由谓词、个体词（常量、变量、函数）、量词、联结词递归构成：
原子公式 P ( t 1 , … , t n ) P(t_1,\dots,t_n) P ( t 1 , … , t n ) t i t_i t i 若 A A A ¬ A \neg A ¬ A 若 A , B A,B A , B A ∧ B , A ∨ B , A → B , A ↔ B A\land B, A\lor B, A\to B, A\leftrightarrow B A ∧ B , A ∨ B , A → B , A ↔ B 若 A A A ∀ x A \forall x\,A ∀ x A ∃ x A \exists x\,A ∃ x A 变元的某次出现若在某量词的辖域内，称为约束出现 （约束变元），否则为自由出现 （自由变元）。
约束变元换名 ：可把 ∀ x P ( x ) \forall x\,P(x) ∀ x P ( x ) ∀ y P ( y ) \forall y\,P(y) ∀ y P ( y ) y y y P P P 自由变元代入 ：可对自由变元做替换，但须避免新的变元被原量词捕获。解释 （赋值）：给公式一个解释，需要指定：论域 D D D D D D D D D D D D 闭公式 ）有确定的真假值。
2.3 一阶逻辑等值式与前束范式 本节为高频必考点，求前束范式与量词否定转移是考试必考题型
一阶逻辑中命题逻辑的等值式继续适用，另加量词相关等值式。设 A ( x ) A(x) A ( x ) x x x B B B x x x
量词否定（量词德摩根）： ¬ ∀ x A ( x ) ⇔ ∃ x ¬ A ( x ) \neg\forall x\,A(x)\Leftrightarrow \exists x\,\neg A(x) ¬∀ x A ( x ) ⇔ ∃ x ¬ A ( x ) ¬ ∃ x A ( x ) ⇔ ∀ x ¬ A ( x ) \neg\exists x\,A(x)\Leftrightarrow \forall x\,\neg A(x) ¬∃ x A ( x ) ⇔ ∀ x ¬ A ( x ) 量词辖域扩张/收缩（B B B x x x ∀ x ( A ( x ) ∧ B ) ⇔ ∀ x A ( x ) ∧ B \forall x(A(x)\land B)\Leftrightarrow \forall x\,A(x)\land B ∀ x ( A ( x ) ∧ B ) ⇔ ∀ x A ( x ) ∧ B ∃ x ( A ( x ) ∧ B ) ⇔ ∃ x A ( x ) ∧ B \exists x(A(x)\land B)\Leftrightarrow \exists x\,A(x)\land B ∃ x ( A ( x ) ∧ B ) ⇔ ∃ x A ( x ) ∧ B ∀ x ( A ( x ) ∨ B ) ⇔ ∀ x A ( x ) ∨ B \forall x(A(x)\lor B)\Leftrightarrow \forall x\,A(x)\lor B ∀ x ( A ( x ) ∨ B ) ⇔ ∀ x A ( x ) ∨ B ∃ x ( A ( x ) ∨ B ) ⇔ ∃ x A ( x ) ∨ B \exists x(A(x)\lor B)\Leftrightarrow \exists x\,A(x)\lor B ∃ x ( A ( x ) ∨ B ) ⇔ ∃ x A ( x ) ∨ B 量词分配（注意不可任意换）： ∀ x ( A ( x ) ∧ B ( x ) ) ⇔ ∀ x A ( x ) ∧ ∀ x B ( x ) \forall x(A(x)\land B(x))\Leftrightarrow \forall x\,A(x)\land\forall x\,B(x) ∀ x ( A ( x ) ∧ B ( x )) ⇔ ∀ x A ( x ) ∧ ∀ x B ( x ) ∃ x ( A ( x ) ∨ B ( x ) ) ⇔ ∃ x A ( x ) ∨ ∃ x B ( x ) \exists x(A(x)\lor B(x))\Leftrightarrow \exists x\,A(x)\lor\exists x\,B(x) ∃ x ( A ( x ) ∨ B ( x )) ⇔ ∃ x A ( x ) ∨ ∃ x B ( x ) 一般地 ∀ x ( A ( x ) ∨ B ( x ) ) \forall x(A(x)\lor B(x)) ∀ x ( A ( x ) ∨ B ( x )) 不 等值于 ∀ x A ( x ) ∨ ∀ x B ( x ) \forall x\,A(x)\lor\forall x\,B(x) ∀ x A ( x ) ∨ ∀ x B ( x ) ∃ x ( A ( x ) ∧ B ( x ) ) \exists x(A(x)\land B(x)) ∃ x ( A ( x ) ∧ B ( x )) 不 等值于 ∃ x A ( x ) ∧ ∃ x B ( x ) \exists x\,A(x)\land\exists x\,B(x) ∃ x A ( x ) ∧ ∃ x B ( x ) 前束范式 ：所有量词都放在公式最前（前缀），后跟不含量词的矩阵（母式）。形如 Q 1 x 1 ⋯ Q n x n B ( x 1 , … , x n ) Q_1 x_1\cdots Q_n x_n\, B(x_1,\dots,x_n) Q 1 x 1 ⋯ Q n x n B ( x 1 , … , x n ) Q i ∈ { ∀ , ∃ } Q_i\in\{\forall,\exists\} Q i ∈ { ∀ , ∃ } B B B
任一一阶公式都可化为前束范式。步骤：换名消除变元冲突 → 用德摩根把否定深入至谓词前 → 用等值式把量词逐步提到最前。
例 化 ∀ x P ( x ) ∨ ¬ ∃ x ( R ( x ) ∧ Q ( x ) ) \forall x\,P(x)\lor\neg\exists x(R(x)\land Q(x)) ∀ x P ( x ) ∨ ¬∃ x ( R ( x ) ∧ Q ( x ))
先换名：∀ x P ( x ) ∨ ¬ ∃ y ( R ( y ) ∧ Q ( y ) ) \forall x\,P(x)\lor\neg\exists y(R(y)\land Q(y)) ∀ x P ( x ) ∨ ¬∃ y ( R ( y ) ∧ Q ( y ))
否定深入：¬ ∃ y ( R ( y ) ∧ Q ( y ) ) ⇔ ∀ y ( ¬ R ( y ) ∨ ¬ Q ( y ) ) \neg\exists y(R(y)\land Q(y))\Leftrightarrow\forall y(\neg R(y)\lor\neg Q(y)) ¬∃ y ( R ( y ) ∧ Q ( y )) ⇔ ∀ y ( ¬ R ( y ) ∨ ¬ Q ( y ))
提量词（辖域扩张）：得前束范式
∀ x ∀ y ( P ( x ) ∨ ¬ R ( y ) ∨ ¬ Q ( y ) ) . \forall x\,\forall y\,\bigl(P(x)\lor\neg R(y)\lor\neg Q(y)\bigr). ∀ x ∀ y ( P ( x ) ∨ ¬ R ( y ) ∨ ¬ Q ( y ) ) .
例（真题） 求公式 ¬ ∀ x ( P ( x ) → Q ( x ) ) \neg\forall x(P(x)\to Q(x)) ¬∀ x ( P ( x ) → Q ( x ))
解
¬ ∀ x ( P ( x ) → Q ( x ) ) ⇔ ∃ x ¬ ( P ( x ) → Q ( x ) ) ⇔ ∃ x ( P ( x ) ∧ ¬ Q ( x ) ) . \neg\forall x(P(x)\to Q(x))\Leftrightarrow \exists x\,\neg(P(x)\to Q(x))\Leftrightarrow \exists x(P(x)\land\neg Q(x)). ¬∀ x ( P ( x ) → Q ( x )) ⇔ ∃ x ¬ ( P ( x ) → Q ( x )) ⇔ ∃ x ( P ( x ) ∧ ¬ Q ( x )) .
前束范式为 ∃ x ( P ( x ) ∧ ¬ Q ( x ) ) \exists x(P(x)\land\neg Q(x)) ∃ x ( P ( x ) ∧ ¬ Q ( x ))
2.4 一阶逻辑推理 本节为高频必考点，谓词逻辑推理证明是考研/期末压轴大题
一阶逻辑保留命题逻辑的推理规则，并增加四条涉及量词的规则：
规则 形式 要点 UI（全称例化） ∀ x A ( x ) ⊢ A ( y ) \forall x\,A(x)\vdash A(y) ∀ x A ( x ) ⊢ A ( y ) y y y 从"所有"到"任一" EI（存在例化） ∃ x A ( x ) ⊢ A ( c ) \exists x\,A(x)\vdash A(c) ∃ x A ( x ) ⊢ A ( c ) c c c 从"存在"到"某个特定"，c c c UG（全称泛化） 对任意 y y y A ( y ) ⊢ ∀ x A ( x ) A(y)\vdash \forall x\,A(x) A ( y ) ⊢ ∀ x A ( x ) y y y EG（存在泛化） A ( c ) ⊢ ∃ x A ( x ) A(c)\vdash \exists x\,A(x) A ( c ) ⊢ ∃ x A ( x ) 从"某个"到"存在"
使用顺序约束：消去时先 EI 后 UI，引入时先 UG 后 EG。
例 经典三段论："所有人都会死，苏格拉底是人，所以苏格拉底会死。"
设 M ( x ) M(x) M ( x ) x x x D ( x ) D(x) D ( x ) x x x s s s
∀ x ( M ( x ) → D ( x ) ) \forall x(M(x)\to D(x)) ∀ x ( M ( x ) → D ( x )) M ( s ) M(s) M ( s ) 由 UI 得 M ( s ) → D ( s ) M(s)\to D(s) M ( s ) → D ( s ) 由 MP（M ( s ) M(s) M ( s ) M ( s ) → D ( s ) M(s)\to D(s) M ( s ) → D ( s ) D ( s ) D(s) D ( s ) 例（真题） 证明：∀ x ( P ( x ) → Q ( x ) ) , ∃ x ( P ( x ) ∧ R ( x ) ) ⊢ ∃ x ( R ( x ) ∧ Q ( x ) ) \forall x(P(x)\to Q(x)),\ \exists x(P(x)\land R(x))\vdash \exists x(R(x)\land Q(x)) ∀ x ( P ( x ) → Q ( x )) , ∃ x ( P ( x ) ∧ R ( x )) ⊢ ∃ x ( R ( x ) ∧ Q ( x ))
解
步骤 公式 理由 (1) ∀ x ( P ( x ) → Q ( x ) ) \forall x(P(x)\to Q(x)) ∀ x ( P ( x ) → Q ( x )) 前提 P (2) ∃ x ( P ( x ) ∧ R ( x ) ) \exists x(P(x)\land R(x)) ∃ x ( P ( x ) ∧ R ( x )) 前提 P (3) P ( c ) ∧ R ( c ) P(c)\land R(c) P ( c ) ∧ R ( c ) 由(2) EI，c c c (4) P ( c ) → Q ( c ) P(c)\to Q(c) P ( c ) → Q ( c ) 由(1) UI (5) P ( c ) P(c) P ( c ) 由(3)化简 (6) Q ( c ) Q(c) Q ( c ) 由(4)(5) MP (7) R ( c ) R(c) R ( c ) 由(3)化简 (8) R ( c ) ∧ Q ( c ) R(c)\land Q(c) R ( c ) ∧ Q ( c ) 由(7)(6)合取引入 (9) ∃ x ( R ( x ) ∧ Q ( x ) ) \exists x(R(x)\land Q(x)) ∃ x ( R ( x ) ∧ Q ( x )) 由(8) EG
第二篇 集合论 集合论是离散数学的语言底座：关系、函数、图、代数结构几乎都建立在集合之上。本篇对齐教材第3-4章，从集合运算与计数出发，深入到关系性质的判定（等价关系、偏序），再到函数的分类，这是后续图论与代数的前提。
第3章 集合的基本概念和运算 3.1 集合的基本概念 集合是无序且互异的对象的总体，对象称为元素 。a ∈ A a\in A a ∈ A a a a A A A { a , b , c } \{a,b,c\} { a , b , c } { x ∣ P ( x ) } \{x\mid P(x)\} { x ∣ P ( x )} N \mathbb N N Z \mathbb Z Z Q \mathbb Q Q R \mathbb R R
若 A A A B B B A A A B B B 子集 ，记 A ⊆ B A\subseteq B A ⊆ B B B B A A A A ⊊ B A\subsetneq B A ⊊ B ∅ \varnothing ∅ 基数 （元素个数）记 ∣ A ∣ |A| ∣ A ∣ # A \#A # A
幂集 ：集合 A A A P ( A ) \mathcal P(A) P ( A ) 2 A 2^A 2 A ∣ A ∣ = n |A|=n ∣ A ∣ = n ∣ P ( A ) ∣ = 2 n |\mathcal P(A)|=2^n ∣ P ( A ) ∣ = 2 n
易错点 ："∈ \in ∈ ⊆ \subseteq ⊆ 1 ∈ { 1 , 2 } 1\in\{1,2\} 1 ∈ { 1 , 2 } { 1 } ⊆ { 1 , 2 } \{1\}\subseteq\{1,2\} { 1 } ⊆ { 1 , 2 } { 1 } ∈ { 1 , 2 } \{1\}\in\{1,2\} { 1 } ∈ { 1 , 2 }
例（真题） 设 A = { 1 , 2 , 3 } A=\{1,2,3\} A = { 1 , 2 , 3 } A A A P ( A ) \mathcal P(A) P ( A ) A A A
解 ∣ P ( A ) ∣ = 2 3 = 8 |\mathcal P(A)|=2^3=8 ∣ P ( A ) ∣ = 2 3 = 8
P ( A ) = { ∅ , { 1 } , { 2 } , { 3 } , { 1 , 2 } , { 1 , 3 } , { 2 , 3 } , { 1 , 2 , 3 } } . \mathcal P(A)=\{\varnothing,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}. P ( A ) = { ∅ , { 1 } , { 2 } , { 3 } , { 1 , 2 } , { 1 , 3 } , { 2 , 3 } , { 1 , 2 , 3 }} .
真子集为除 { 1 , 2 , 3 } \{1,2,3\} { 1 , 2 , 3 } ∅ \varnothing ∅ A A A P ( A ) \mathcal P(A) P ( A )
3.2 集合的基本运算 集合的基本运算（U U U
运算 记号 定义 并 A ∪ B A\cup B A ∪ B { x ∣ x ∈ A ∨ x ∈ B } \{x\mid x\in A\lor x\in B\} { x ∣ x ∈ A ∨ x ∈ B } 交 A ∩ B A\cap B A ∩ B { x ∣ x ∈ A ∧ x ∈ B } \{x\mid x\in A\land x\in B\} { x ∣ x ∈ A ∧ x ∈ B } 差 A − B A-B A − B { x ∣ x ∈ A ∧ x ∉ B } \{x\mid x\in A\land x\notin B\} { x ∣ x ∈ A ∧ x ∈ / B } 补 A ˉ \bar A A ˉ U − A U-A U − A { x ∣ x ∉ A } \{x\mid x\notin A\} { x ∣ x ∈ / A } 对称差 A ⊕ B A\oplus B A ⊕ B ( A − B ) ∪ ( B − A ) (A-B)\cup(B-A) ( A − B ) ∪ ( B − A )
集合运算律：交换律、结合律、分配律、吸收律、德摩根律 A ∪ B ‾ = A ˉ ∩ B ˉ \overline{A\cup B}=\bar A\cap\bar B A ∪ B = A ˉ ∩ B ˉ A ∩ B ‾ = A ˉ ∪ B ˉ \overline{A\cap B}=\bar A\cup\bar B A ∩ B = A ˉ ∪ B ˉ A ˉ ˉ = A \bar{\bar A}=A A ˉ ˉ = A A ∩ A ˉ = ∅ A\cap\bar A=\varnothing A ∩ A ˉ = ∅ A ∪ A ˉ = U A\cup\bar A=U A ∪ A ˉ = U
笛卡儿积 ：A × B = { ⟨ a , b ⟩ ∣ a ∈ A , b ∈ B } A\times B=\{\langle a,b\rangle\mid a\in A, b\in B\} A × B = {⟨ a , b ⟩ ∣ a ∈ A , b ∈ B } A = B A=B A = B n n n n n n
易错点 ：A − B A-B A − B B − A B-A B − A A × B ≠ B × A A\times B\ne B\times A A × B = B × A A = B A=B A = B
3.3 集合中元素的计数 本节为高频必考点，容斥原理应用题是考试常出题型
利用集合运算可以对元素进行计数，核心工具是容斥原理 （包含排斥原理）。
对两个集合：∣ A ∪ B ∣ = ∣ A ∣ + ∣ B ∣ − ∣ A ∩ B ∣ |A\cup B|=|A|+|B|-|A\cap B| ∣ A ∪ B ∣ = ∣ A ∣ + ∣ B ∣ − ∣ A ∩ B ∣
对三个集合：
∣ A ∪ B ∪ C ∣ = ∣ A ∣ + ∣ B ∣ + ∣ C ∣ − ∣ A ∩ B ∣ − ∣ A ∩ C ∣ − ∣ B ∩ C ∣ + ∣ A ∩ B ∩ C ∣ . |A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|. ∣ A ∪ B ∪ C ∣ = ∣ A ∣ + ∣ B ∣ + ∣ C ∣ − ∣ A ∩ B ∣ − ∣ A ∩ C ∣ − ∣ B ∩ C ∣ + ∣ A ∩ B ∩ C ∣.
一般地，n n n n n n ( − 1 ) n + 1 (-1)^{n+1} ( − 1 ) n + 1
欧拉函数 φ ( n ) \varphi(n) φ ( n ) n n n n n n n n n p 1 , … , p k p_1,\dots,p_k p 1 , … , p k
φ ( n ) = n ( 1 − 1 p 1 ) ⋯ ( 1 − 1 p k ) . \varphi(n)=n\left(1-\frac1{p_1}\right)\cdots\left(1-\frac1{p_k}\right). φ ( n ) = n ( 1 − p 1 1 ) ⋯ ( 1 − p k 1 ) .
例 求 φ ( 30 ) \varphi(30) φ ( 30 ) 30 = 2 × 3 × 5 30=2\times3\times5 30 = 2 × 3 × 5
φ ( 30 ) = 30 × 1 2 × 2 3 × 4 5 = 8. \varphi(30)=30\times\frac12\times\frac23\times\frac45=8. φ ( 30 ) = 30 × 2 1 × 3 2 × 5 4 = 8.
验证：{ 1 , 7 , 11 , 13 , 17 , 19 , 23 , 29 } \{1,7,11,13,17,19,23,29\} { 1 , 7 , 11 , 13 , 17 , 19 , 23 , 29 }
例（真题） 某班 50 人，参加数学建模 20 人，参加数学竞赛 15 人，参加英语竞赛 12 人。同时参加数学建模和数学竞赛 5 人，同时参加数学建模和英语 3 人，同时参加数学竞赛和英语 4 人，三项全参加 2 人。求至少参加一项竞赛的人数及都不参加的人数。
解 由容斥原理：
∣ M ∪ P ∪ E ∣ = 20 + 15 + 12 − 5 − 3 − 4 + 2 = 37. |M\cup P\cup E|=20+15+12-5-3-4+2=37. ∣ M ∪ P ∪ E ∣ = 20 + 15 + 12 − 5 − 3 − 4 + 2 = 37.
至少参加一项竞赛 37 人，三项都不参加 50 − 37 = 13 50-37=13 50 − 37 = 13
易错点 ：容斥原理中"求都不满足"时，用全集减去"至少满足一个"的并集，而非直接相减。顺序是：先求并集大小（容斥），再用 ∣ U ∣ − ∣ ∪ A i ∣ |U|-|\cup A_i| ∣ U ∣ − ∣ ∪ A i ∣
第4章 二元关系和函数 4.1 集合的笛卡儿积与二元关系 A × B A\times B A × B R R R A A A B B B 二元关系 。当 A = B A=B A = B R R R A A A ⟨ a , b ⟩ ∈ R \langle a,b\rangle\in R ⟨ a , b ⟩ ∈ R a R b aRb a R b
若 ∣ A ∣ = m , ∣ B ∣ = n |A|=m, |B|=n ∣ A ∣ = m , ∣ B ∣ = n A A A B B B 2 m n 2^{mn} 2 mn A A A 2 n 2 2^{n^2} 2 n 2
关系的常用表示：
集合表示 ：列举或描述有序对；关系矩阵 ：m × n m\times n m × n M R M_R M R M R [ i , j ] = 1 ⇔ a i R b j M_R[i,j]=1\Leftrightarrow a_iRb_j M R [ i , j ] = 1 ⇔ a i R b j 关系图 ：以点表示元素，有向边 ⟨ a , b ⟩ \langle a,b\rangle ⟨ a , b ⟩ a R b aRb a R b 4.2 关系的运算 设 R ⊆ A × B , S ⊆ B × C R\subseteq A\times B, S\subseteq B\times C R ⊆ A × B , S ⊆ B × C
逆关系 R − 1 = { ⟨ b , a ⟩ ∣ ⟨ a , b ⟩ ∈ R } R^{-1}=\{\langle b,a\rangle\mid\langle a,b\rangle\in R\} R − 1 = {⟨ b , a ⟩ ∣ ⟨ a , b ⟩ ∈ R } M R M_R M R 复合关系 R ∘ S = { ⟨ a , c ⟩ ∣ ∃ b ( ⟨ a , b ⟩ ∈ R ∧ ⟨ b , c ⟩ ∈ S ) } R\circ S=\{\langle a,c\rangle\mid\exists b(\langle a,b\rangle\in R\land\langle b,c\rangle\in S)\} R ∘ S = {⟨ a , c ⟩ ∣ ∃ b (⟨ a , b ⟩ ∈ R ∧ ⟨ b , c ⟩ ∈ S )} 限制、像、定义域 dom ( R ) \text{dom}(R) dom ( R ) ran ( R ) \text{ran}(R) ran ( R ) fld ( R ) \text{fld}(R) fld ( R ) 等。集合运算（并、交、补、差）可直接用于关系（因关系即集合）。 矩阵刻画：R − 1 R^{-1} R − 1 M R T M_R^T M R T M R ⊙ M S M_R\odot M_S M R ⊙ M S R 0 = I A R^0=I_A R 0 = I A R n + 1 = R n ∘ R R^{n+1}=R^n\circ R R n + 1 = R n ∘ R
4.3 关系的性质 本节为高频必考点，判断关系五条性质是考试必考题
设 R R R A A A
性质 定义（∀ \forall ∀ 矩阵特征 关系图特征 自反 ∀ a , a R a \forall a,\ aRa ∀ a , a R a 主对角全 1 每点有自环 反自反 ∀ a , ¬ a R a \forall a,\ \neg aRa ∀ a , ¬ a R a 主对角全 0 每点无自环 对称 a R b ⇒ b R a aRb\Rightarrow bRa a R b ⇒ b R a 矩阵对称 边成对双向 反对称 a R b ∧ b R a ⇒ a = b aRb\land bRa\Rightarrow a=b a R b ∧ b R a ⇒ a = b 若 M [ i , j ] = M [ j , i ] = 1 M[i,j]=M[j,i]=1 M [ i , j ] = M [ j , i ] = 1 i = j i=j i = j 无双向边（可有自环） 传递 a R b ∧ b R c ⇒ a R c aRb\land bRc\Rightarrow aRc a R b ∧ b R c ⇒ a R c M R 2 M_R^2 M R 2 M R M_R M R 路径两端也有边
易错点 ："对称"与"反对称"不是非此即彼：一个关系可以同时既对称又反对称（如恒等关系 I A I_A I A A = ∅ A=\varnothing A = ∅
例（真题） 设 A = { 1 , 2 , 3 } A=\{1,2,3\} A = { 1 , 2 , 3 } R = { ⟨ 1 , 1 ⟩ , ⟨ 2 , 2 ⟩ , ⟨ 3 , 3 ⟩ , ⟨ 1 , 2 ⟩ , ⟨ 2 , 1 ⟩ } R=\{\langle1,1\rangle,\langle2,2\rangle,\langle3,3\rangle,\langle1,2\rangle,\langle2,1\rangle\} R = {⟨ 1 , 1 ⟩ , ⟨ 2 , 2 ⟩ , ⟨ 3 , 3 ⟩ , ⟨ 1 , 2 ⟩ , ⟨ 2 , 1 ⟩} R R R
解
自反：是，每个元素都有自环 ⟨ i , i ⟩ ∈ R \langle i,i\rangle\in R ⟨ i , i ⟩ ∈ R 对称：是，⟨ 1 , 2 ⟩ \langle1,2\rangle ⟨ 1 , 2 ⟩ ⟨ 2 , 1 ⟩ \langle2,1\rangle ⟨ 2 , 1 ⟩ 反对称：否，因 ⟨ 1 , 2 ⟩ \langle1,2\rangle ⟨ 1 , 2 ⟩ ⟨ 2 , 1 ⟩ \langle2,1\rangle ⟨ 2 , 1 ⟩ 1 ≠ 2 1\ne2 1 = 2 传递：是，检查 ⟨ 1 , 2 ⟩ , ⟨ 2 , 1 ⟩ \langle1,2\rangle,\langle2,1\rangle ⟨ 1 , 2 ⟩ , ⟨ 2 , 1 ⟩ ⟨ 1 , 1 ⟩ ∈ R \langle1,1\rangle\in R ⟨ 1 , 1 ⟩ ∈ R ⟨ 2 , 1 ⟩ , ⟨ 1 , 2 ⟩ \langle2,1\rangle,\langle1,2\rangle ⟨ 2 , 1 ⟩ , ⟨ 1 , 2 ⟩ ⟨ 2 , 2 ⟩ ∈ R \langle2,2\rangle\in R ⟨ 2 , 2 ⟩ ∈ R 故 R R R
4.4 关系的闭包 本节为高频必考点，求自反/对称/传递闭包是考试常出计算题
对给定关系 R R R R R R R R R 闭包 ：
自反闭包 r ( R ) = R ∪ I A r(R)=R\cup I_A r ( R ) = R ∪ I A 对称闭包 s ( R ) = R ∪ R − 1 s(R)=R\cup R^{-1} s ( R ) = R ∪ R − 1 传递闭包 t ( R ) = ⋃ i = 1 ∞ R i t(R)=\bigcup_{i=1}^{\infty} R^i t ( R ) = ⋃ i = 1 ∞ R i ∣ A ∣ = n |A|=n ∣ A ∣ = n t ( R ) = R ∪ R 2 ∪ ⋯ ∪ R n t(R)=R\cup R^2\cup\dots\cup R^n t ( R ) = R ∪ R 2 ∪ ⋯ ∪ R n Warshall 算法 可高效计算传递闭包：依次以每个顶点作"中间点"，若 M [ i , k ] = 1 M[i,k]=1 M [ i , k ] = 1 M [ k , j ] = 1 M[k,j]=1 M [ k , j ] = 1 M [ i , j ] = 1 M[i,j]=1 M [ i , j ] = 1 O ( n 3 ) O(n^3) O ( n 3 )
例（真题） 设 A = { 1 , 2 , 3 } A=\{1,2,3\} A = { 1 , 2 , 3 } R = { ⟨ 1 , 2 ⟩ , ⟨ 2 , 3 ⟩ } R=\{\langle1,2\rangle,\langle2,3\rangle\} R = {⟨ 1 , 2 ⟩ , ⟨ 2 , 3 ⟩} r ( R ) , s ( R ) , t ( R ) r(R),s(R),t(R) r ( R ) , s ( R ) , t ( R )
解
r ( R ) = R ∪ I A = { ⟨ 1 , 2 ⟩ , ⟨ 2 , 3 ⟩ , ⟨ 1 , 1 ⟩ , ⟨ 2 , 2 ⟩ , ⟨ 3 , 3 ⟩ } r(R)=R\cup I_A=\{\langle1,2\rangle,\langle2,3\rangle,\langle1,1\rangle,\langle2,2\rangle,\langle3,3\rangle\} r ( R ) = R ∪ I A = {⟨ 1 , 2 ⟩ , ⟨ 2 , 3 ⟩ , ⟨ 1 , 1 ⟩ , ⟨ 2 , 2 ⟩ , ⟨ 3 , 3 ⟩} s ( R ) = R ∪ R − 1 = { ⟨ 1 , 2 ⟩ , ⟨ 2 , 3 ⟩ , ⟨ 2 , 1 ⟩ , ⟨ 3 , 2 ⟩ } s(R)=R\cup R^{-1}=\{\langle1,2\rangle,\langle2,3\rangle,\langle2,1\rangle,\langle3,2\rangle\} s ( R ) = R ∪ R − 1 = {⟨ 1 , 2 ⟩ , ⟨ 2 , 3 ⟩ , ⟨ 2 , 1 ⟩ , ⟨ 3 , 2 ⟩} t ( R ) = R ∪ R 2 ∪ R 3 t(R)=R\cup R^2\cup R^3 t ( R ) = R ∪ R 2 ∪ R 3 R 2 = { ⟨ 1 , 3 ⟩ } R^2=\{\langle1,3\rangle\} R 2 = {⟨ 1 , 3 ⟩} ⟨ 1 , 2 ⟩ ∘ ⟨ 2 , 3 ⟩ \langle1,2\rangle\circ\langle2,3\rangle ⟨ 1 , 2 ⟩ ∘ ⟨ 2 , 3 ⟩ R 3 = ∅ R^3=\varnothing R 3 = ∅ t ( R ) = { ⟨ 1 , 2 ⟩ , ⟨ 2 , 3 ⟩ , ⟨ 1 , 3 ⟩ } t(R)=\{\langle1,2\rangle,\langle2,3\rangle,\langle1,3\rangle\} t ( R ) = {⟨ 1 , 2 ⟩ , ⟨ 2 , 3 ⟩ , ⟨ 1 , 3 ⟩} 4.5 等价关系和偏序关系 本节为高频必考点，等价关系证明与哈斯图求特殊元素是考试必考大题
等价关系 ：若 R R R a ∈ A a\in A a ∈ A 等价类 [ a ] R = { x ∈ A ∣ x R a } [a]_R=\{x\in A\mid xRa\} [ a ] R = { x ∈ A ∣ x R a }
a ∈ [ a ] R a\in[a]_R a ∈ [ a ] R a R b ⇔ [ a ] R = [ b ] R aRb\Leftrightarrow [a]_R=[b]_R a R b ⇔ [ a ] R = [ b ] R 不同等价类要么相等要么不相交。 A A A R R R A A A 划分 （partition）：两两不相交、并集为 A A A 商集 A / R = { [ a ] R ∣ a ∈ A } A/R=\{[a]_R\mid a\in A\} A / R = {[ a ] R ∣ a ∈ A }
例 A = { 0 , 1 , … , 8 } A=\{0,1,\dots,8\} A = { 0 , 1 , … , 8 } R R R [ 0 ] = { 0 , 3 , 6 } , [ 1 ] = { 1 , 4 , 7 } , [ 2 ] = { 2 , 5 , 8 } [0]=\{0,3,6\},\ [1]=\{1,4,7\},\ [2]=\{2,5,8\} [ 0 ] = { 0 , 3 , 6 } , [ 1 ] = { 1 , 4 , 7 } , [ 2 ] = { 2 , 5 , 8 } A A A
例（真题） 设 A = { 1 , 2 , 3 , 4 , 6 , 12 } A=\{1,2,3,4,6,12\} A = { 1 , 2 , 3 , 4 , 6 , 12 } R R R A A A a R b ⇔ a ∣ b aRb\Leftrightarrow a\mid b a R b ⇔ a ∣ b
证明 R R R 画出哈斯图； 求 A A A 解 (1) 整除关系自反（a ∣ a a\mid a a ∣ a a ∣ b a\mid b a ∣ b b ∣ a b\mid a b ∣ a a = b a=b a = b a ∣ b a\mid b a ∣ b b ∣ c b\mid c b ∣ c a ∣ c a\mid c a ∣ c
(2) 覆盖关系：1 ≺ 2 , 1 ≺ 3 , 2 ≺ 4 , 2 ≺ 6 , 3 ≺ 6 , 4 ≺ 12 , 6 ≺ 12 1\prec2,1\prec3,2\prec4,2\prec6,3\prec6,4\prec12,6\prec12 1 ≺ 2 , 1 ≺ 3 , 2 ≺ 4 , 2 ≺ 6 , 3 ≺ 6 , 4 ≺ 12 , 6 ≺ 12
(3) 极大元：{ 12 } \{12\} { 12 } { 1 } \{1\} { 1 } 12 12 12 1 1 1
偏序关系 ：若 R R R R R R ≤ \le ≤ ⟨ A , ≤ ⟩ \langle A,\le\rangle ⟨ A , ≤ ⟩
可比 a ≤ b a\le b a ≤ b b ≤ a b\le a b ≤ a 全序 （线序）。覆盖 ：a < b a<b a < b c c c a < c < b a<c<b a < c < b a ≺ b a\prec b a ≺ b 哈斯图 （Hasse diagram）：去掉自环、去掉由传递性可得的边，只画覆盖关系 ≺ \prec ≺ 偏序集中的特殊元素：
名称 定义 极大元 不存在 x x x a < x a<x a < x 极小元 不存在 x x x x < a x<a x < a 最大元 ∀ x , x ≤ a \forall x,\ x\le a ∀ x , x ≤ a 最小元 ∀ x , a ≤ x \forall x,\ a\le x ∀ x , a ≤ x 上界 / 下界 子集 B B B ∀ b ∈ B , b ≤ m \forall b\in B, b\le m ∀ b ∈ B , b ≤ m b ≥ m b\ge m b ≥ m 上确界 / 下确界 最小上界 / 最大下界，记 sup B \sup B sup B inf B \inf B inf B
易错点 ：极大/极小元不唯一，最大/最小元若存在则唯一；上/下界不要求属于子集 B B B
4.6 函数的定义和性质 设 f f f A A A B B B a ∈ A a\in A a ∈ A b ∈ B b\in B b ∈ B ⟨ a , b ⟩ ∈ f \langle a,b\rangle\in f ⟨ a , b ⟩ ∈ f f f f A A A B B B 函数 （映射），记 f : A → B f:A\to B f : A → B f ( a ) = b f(a)=b f ( a ) = b A A A B B B f ( A ) = { f ( a ) ∣ a ∈ A } f(A)=\{f(a)\mid a\in A\} f ( A ) = { f ( a ) ∣ a ∈ A } ∣ A ∣ = m , ∣ B ∣ = n |A|=m,|B|=n ∣ A ∣ = m , ∣ B ∣ = n A A A B B B n m n^m n m
类型 条件 充要（用像） 单射（入射，injection） a 1 ≠ a 2 ⇒ f ( a 1 ) ≠ f ( a 2 ) a_1\ne a_2\Rightarrow f(a_1)\ne f(a_2) a 1 = a 2 ⇒ f ( a 1 ) = f ( a 2 ) f ( a 1 ) = f ( a 2 ) ⇒ a 1 = a 2 f(a_1)=f(a_2)\Rightarrow a_1=a_2 f ( a 1 ) = f ( a 2 ) ⇒ a 1 = a 2 满射（surjection） f ( A ) = B f(A)=B f ( A ) = B ∀ b ∈ B , ∃ a , f ( a ) = b \forall b\in B,\exists a,\ f(a)=b ∀ b ∈ B , ∃ a , f ( a ) = b 双射（一一对应，bijection） 既单又满 存在逆函数
单射要求 ∣ A ∣ ≤ ∣ B ∣ |A|\le|B| ∣ A ∣ ≤ ∣ B ∣ ∣ A ∣ ≥ ∣ B ∣ |A|\ge|B| ∣ A ∣ ≥ ∣ B ∣ ∣ A ∣ = ∣ B ∣ |A|=|B| ∣ A ∣ = ∣ B ∣ 双射函数必有逆函数 f − 1 : B → A f^{-1}:B\to A f − 1 : B → A f − 1 ∘ f = I A f^{-1}\circ f=I_A f − 1 ∘ f = I A f ∘ f − 1 = I B f\circ f^{-1}=I_B f ∘ f − 1 = I B 例（真题） 设 f : R → R f:\mathbb R\to\mathbb R f : R → R f ( x ) = 2 x − 3 f(x)=2x-3 f ( x ) = 2 x − 3 g : R → R g:\mathbb R\to\mathbb R g : R → R g ( x ) = x 2 g(x)=x^2 g ( x ) = x 2 f f f g g g g ∘ f g\circ f g ∘ f
解
f f f 2 x 1 − 3 = 2 x 2 − 3 ⇒ x 1 = x 2 2x_1-3=2x_2-3\Rightarrow x_1=x_2 2 x 1 − 3 = 2 x 2 − 3 ⇒ x 1 = x 2 ∀ y ∈ R , x = ( y + 3 ) / 2 \forall y\in\mathbb R,\ x=(y+3)/2 ∀ y ∈ R , x = ( y + 3 ) /2 f f f g g g g ( 1 ) = g ( − 1 ) = 1 g(1)=g(-1)=1 g ( 1 ) = g ( − 1 ) = 1 g g g ( g ∘ f ) ( x ) = g ( f ( x ) ) = g ( 2 x − 3 ) = ( 2 x − 3 ) 2 = 4 x 2 − 12 x + 9 (g\circ f)(x)=g(f(x))=g(2x-3)=(2x-3)^2=4x^2-12x+9 ( g ∘ f ) ( x ) = g ( f ( x )) = g ( 2 x − 3 ) = ( 2 x − 3 ) 2 = 4 x 2 − 12 x + 9 4.7 函数的复合和反函数 复合函数 ：f : B → C , g : A → B f:B\to C,\ g:A\to B f : B → C , g : A → B f ∘ g : A → C f\circ g:A\to C f ∘ g : A → C ( f ∘ g ) ( a ) = f ( g ( a ) ) (f\circ g)(a)=f(g(a)) ( f ∘ g ) ( a ) = f ( g ( a )) g g g f f f f , g f,g f , g ⇒ f ∘ g \Rightarrow f\circ g ⇒ f ∘ g ⇒ f ∘ g \Rightarrow f\circ g ⇒ f ∘ g ⇒ f ∘ g \Rightarrow f\circ g ⇒ f ∘ g 反向结论：f ∘ g f\circ g f ∘ g ⇒ g \Rightarrow g ⇒ g f f f f ∘ g f\circ g f ∘ g ⇒ f \Rightarrow f ⇒ f g g g 反函数 （逆函数）仅对双射函数存在。( f ∘ g ) − 1 = g − 1 ∘ f − 1 (f\circ g)^{-1}=g^{-1}\circ f^{-1} ( f ∘ g ) − 1 = g − 1 ∘ f − 1 例 设 f , g : Z → Z f,g:\mathbb Z\to\mathbb Z f , g : Z → Z f ( x ) = 2 x + 1 f(x)=2x+1 f ( x ) = 2 x + 1 g ( x ) = x − 3 g(x)=x-3 g ( x ) = x − 3 f ∘ g f\circ g f ∘ g
( f ∘ g ) ( x ) = f ( g ( x ) ) = f ( x − 3 ) = 2 ( x − 3 ) + 1 = 2 x − 5 (f\circ g)(x)=f(g(x))=f(x-3)=2(x-3)+1=2x-5 ( f ∘ g ) ( x ) = f ( g ( x )) = f ( x − 3 ) = 2 ( x − 3 ) + 1 = 2 x − 5 f ∘ g f\circ g f ∘ g 2 x − 5 2x-5 2 x − 5 Z \mathbb Z Z
第三篇 图论 图论研究"点与连"构成的结构，是离散数学中应用最广的部分：网络、数据结构、调度、地图着色都源于此。本篇对齐教材第5-7章，从基本概念与矩阵表示出发，经特殊图（二部图、欧拉图、哈密顿图、平面图）到树，串起图的核心定理。
第5章 图的基本概念 5.1 无向图及有向图 图 G = ⟨ V , E ⟩ G=\langle V,E\rangle G = ⟨ V , E ⟩ V V V E E E E E E { u , v } \{u,v\} { u , v } ( u , v ) (u,v) ( u , v ) u v uv uv ⟨ u , v ⟩ \langle u,v\rangle ⟨ u , v ⟩
有限图 ：V , E V,E V , E n n n ∣ V ∣ = n |V|=n ∣ V ∣ = n 简单图 ：无环（自环）、无重边（多重边）。多重图 ：允许重边（无自环）；伪图 ：允许环与重边。完全图 K n K_n K n n n n ( n 2 ) = n ( n − 1 ) / 2 \binom{n}{2}=n(n-1)/2 ( 2 n ) = n ( n − 1 ) /2 子图、生成子图、补图 G ˉ \bar G G ˉ G ˉ \bar G G ˉ G G G 顶点 v v v 度 deg ( v ) \deg(v) deg ( v ) 入度 deg − ( v ) \deg^-(v) deg − ( v ) 出度 deg + ( v ) \deg^+(v) deg + ( v ) Δ \Delta Δ δ \delta δ
握手定理 ∑ v ∈ V deg ( v ) = 2 ∣ E ∣ \sum_{v\in V}\deg(v)=2|E| ∑ v ∈ V deg ( v ) = 2∣ E ∣ ∑ deg + = ∑ deg − = ∣ E ∣ \sum\deg^+=\sum\deg^-=|E| ∑ deg + = ∑ deg − = ∣ E ∣ 推论：度数为奇数的顶点个数为偶数。
例（真题） 9 人聚会，每人认识恰好 5 人，是否可能？由握手定理，度数和 9 × 5 = 45 9\times5=45 9 × 5 = 45 = 2 ∣ E ∣ =2|E| = 2∣ E ∣
例（真题） 无向图 G G G 5 , 4 , 4 , 3 , 2 , 2 5,4,4,3,2,2 5 , 4 , 4 , 3 , 2 , 2 G G G
解 度数和 = 5 + 4 + 4 + 3 + 2 + 2 = 20 =5+4+4+3+2+2=20 = 5 + 4 + 4 + 3 + 2 + 2 = 20 2 ∣ E ∣ = 20 2|E|=20 2∣ E ∣ = 20 ∣ E ∣ = 10 |E|=10 ∣ E ∣ = 10
易错点 ：K 4 K_4 K 4
5.2 通路、回路和图的连通性 途径 ：顶点-边交替序列 v 0 e 1 v 1 ⋯ e k v k v_0e_1v_1\cdots e_kv_k v 0 e 1 v 1 ⋯ e k v k 迹 ，顶点互异为路（path） 。回路（圈/cycle） ：首尾相接且除首尾外顶点互异的闭迹。C n C_n C n n n n 连通 ：无向图任两顶点有路相通。连通分量 是极大连通子图。有向图：强连通 （任两点互相可达）、单侧连通（任两点至少一方可达）、弱连通（底图连通）。 点割集、边割集、连通度 ：点连通度 κ ( G ) \kappa(G) κ ( G ) λ ( G ) \lambda(G) λ ( G ) Whitney 不等式 ：κ ( G ) ≤ λ ( G ) ≤ δ ( G ) \kappa(G)\le\lambda(G)\le\delta(G) κ ( G ) ≤ λ ( G ) ≤ δ ( G ) 5.3 图的矩阵表示 本节为高频必考点，邻接矩阵 A k A^k A k
图可以用矩阵简洁地存储和计算，这是计算机处理图的基础。
邻接矩阵 （adjacency matrix）：A = ( a i j ) n × n A=(a_{ij})_{n\times n} A = ( a ij ) n × n a i j = 1 ⇔ v i a_{ij}=1\Leftrightarrow v_i a ij = 1 ⇔ v i v j v_j v j A k A^k A k ( i , j ) (i,j) ( i , j ) v i v_i v i v j v_j v j k k k
易错点 ：A k A^k A k k k k k k k P = A ∨ A 2 ∨ ⋯ ∨ A n − 1 P=A\lor A^2\lor\cdots\lor A^{n-1} P = A ∨ A 2 ∨ ⋯ ∨ A n − 1
关联矩阵 （incidence matrix）：M = ( m i j ) n × m M=(m_{ij})_{n\times m} M = ( m ij ) n × m m i j = 1 ⇔ m_{ij}=1\Leftrightarrow m ij = 1 ⇔ v i v_i v i e j e_j e j − 1 -1 − 1
可达矩阵 （reachability matrix）：P = ( p i j ) P=(p_{ij}) P = ( p ij ) p i j = 1 ⇔ p_{ij}=1\Leftrightarrow p ij = 1 ⇔ v i v_i v i v j v_j v j ≥ 1 \ge1 ≥ 1 P = ⋁ k = 1 n − 1 A k P=\bigvee_{k=1}^{n-1} A^k P = ⋁ k = 1 n − 1 A k A k A^k A k
例 设无向图 G G G
A = ( 0 1 1 1 0 1 1 1 0 ) A=\begin{pmatrix}0&1&1\\1&0&1\\1&1&0\end{pmatrix} A = 0 1 1 1 0 1 1 1 0
（即 K 3 K_3 K 3 A 2 A^2 A 2 A 3 A^3 A 3
例（真题） 设有向图 G G G
A = ( 0 1 0 0 0 1 1 0 0 ) A=\begin{pmatrix}0&1&0\\0&0&1\\1&0&0\end{pmatrix} A = 0 0 1 1 0 0 0 1 0
求 A 2 A^2 A 2 A 3 A^3 A 3 P P P
解
A 2 = ( 0 0 1 1 0 0 0 1 0 ) , A 3 = ( 1 0 0 0 1 0 0 0 1 ) = I . A^2=\begin{pmatrix}0&0&1\\1&0&0\\0&1&0\end{pmatrix},\quad A^3=\begin{pmatrix}1&0&0\\0&1&0\\0&0&1\end{pmatrix}=I. A 2 = 0 1 0 0 0 1 1 0 0 , A 3 = 1 0 0 0 1 0 0 0 1 = I .
A 3 = I A^3=I A 3 = I P = A ∨ A 2 = ( 0 1 1 1 0 1 1 1 0 ) P=A\lor A^2=\begin{pmatrix}0&1&1\\1&0&1\\1&1&0\end{pmatrix} P = A ∨ A 2 = 0 1 1 1 0 1 1 1 0
5.4 最短路径、关键路径和着色 本节为高频必考点，Dijkstra 求最短路径与关键路径计算是考试必考大题
最短路径 ：带权图中求两顶点间权值和最小的路径。
Dijkstra 算法
初始化：源点 s s s d ( s ) = 0 d(s)=0 d ( s ) = 0 d ( v ) = ∞ d(v)=\infty d ( v ) = ∞ S = ∅ S=\varnothing S = ∅ 选未确定集中 d d d u u u S S S 对 u u u v v v d ( v ) = min ( d ( v ) , d ( u ) + w ( u , v ) ) d(v)=\min(d(v), d(u)+w(u,v)) d ( v ) = min ( d ( v ) , d ( u ) + w ( u , v )) 重复 2-3 直到所有顶点确定。 复杂度 O ( n 2 ) O(n^2) O ( n 2 ) O ( ( n + m ) log n ) O((n+m)\log n) O (( n + m ) log n )
易错点 ：Dijkstra 不能处理负权边。有负权时需用 Bellman-Ford 算法。
例（真题） 用 Dijkstra 算法求下图从 v 1 v_1 v 1 v 1 v 2 = 4 , v 1 v 3 = 1 , v 3 v 2 = 2 , v 2 v 4 = 1 , v 3 v 4 = 5 v_1v_2=4,v_1v_3=1,v_3v_2=2,v_2v_4=1,v_3v_4=5 v 1 v 2 = 4 , v 1 v 3 = 1 , v 3 v 2 = 2 , v 2 v 4 = 1 , v 3 v 4 = 5
解
步骤 确定点 d ( v 2 ) d(v_2) d ( v 2 ) d ( v 3 ) d(v_3) d ( v 3 ) d ( v 4 ) d(v_4) d ( v 4 ) 初始 v 1 v_1 v 1 4 1 ∞ \infty ∞ 1 v 1 → v 3 ( 1 ) v_1\to v_3(1) v 1 → v 3 ( 1 ) 4 1(确定) ∞ \infty ∞ 2 经v 3 v_3 v 3 v 2 , v 4 v_2,v_4 v 2 , v 4 min ( 4 , 1 + 2 ) = 3 \min(4,1+2)=3 min ( 4 , 1 + 2 ) = 3 1 min ( ∞ , 1 + 5 ) = 6 \min(\infty,1+5)=6 min ( ∞ , 1 + 5 ) = 6 2 确定v 2 ( 3 ) v_2(3) v 2 ( 3 ) 3(确定) 1 6 3 经v 2 v_2 v 2 v 4 v_4 v 4 3 1 min ( 6 , 3 + 1 ) = 4 \min(6,3+1)=4 min ( 6 , 3 + 1 ) = 4 3 确定v 4 ( 4 ) v_4(4) v 4 ( 4 ) 3 1 4(确定)
最短路径：v 1 → v 3 → v 2 → v 4 v_1\to v_3\to v_2\to v_4 v 1 → v 3 → v 2 → v 4 1 + 2 + 1 = 4 1+2+1=4 1 + 2 + 1 = 4
关键路径 （AOV/AOE 网）：用有向无环图（DAG）表示工程计划，顶点表示事件，有向边表示活动，边权表示活动耗时。
AOE 网 （Activity On Edge）：边带权，只有一个源点（入度为 0）和一个汇点（出度为 0）。关键路径 ：从源点到汇点最长的路径（权值和最大），其上的活动为关键活动 ，任一关键活动延误都会推迟整个工程。求法：先拓扑排序，正序求最早发生时间 v e v_e v e 最迟发生时间 v l v_l v l v e v_e v e v e = v l v_e=v_l v e = v l 图的着色 ：
顶点着色 ：相邻顶点不同色。最少颜色数称为色数 χ ( G ) \chi(G) χ ( G ) χ ( K n ) = n \chi(K_n)=n χ ( K n ) = n χ ≤ 2 \chi\le2 χ ≤ 2 Welsh–Powell 贪心 ：按度递减依次给每点染不冲突的最小色号，上界 χ ≤ Δ + 1 \chi\le\Delta+1 χ ≤ Δ + 1 Brooks 定理 ：χ ≤ Δ \chi\le\Delta χ ≤ Δ G G G 面着色 （平面图）：等价于对偶图的顶点着色。四色定理 ：平面图面可 4 着色。第6章 特殊的图 6.1 二部图 本节为高频必考点，二部图判定（无奇圈）与 Hall 定理是考试常考点
若无向图 G G G V 1 , V 2 V_1, V_2 V 1 , V 2 G G G 二部图 （二分图，bipartite graph）。完全二部图 K m , n K_{m,n} K m , n m n mn mn
判定定理 ：G G G ⇔ \Leftrightarrow ⇔ G G G
易错点 ：判定二部图不需要找划分，只需检查有无奇圈。树一定是二部图（无圈，自然不含奇圈）。K 3 , 3 K_{3,3} K 3 , 3
例（真题） 判断下列图是否为二部图：(1) C 6 C_6 C 6 C 5 C_5 C 5
解 (1) C 6 C_6 C 6 V 1 = { v 1 , v 3 , v 5 } , V 2 = { v 2 , v 4 , v 6 } V_1=\{v_1,v_3,v_5\},V_2=\{v_2,v_4,v_6\} V 1 = { v 1 , v 3 , v 5 } , V 2 = { v 2 , v 4 , v 6 }
(2) C 5 C_5 C 5
二部图的应用：匹配问题。匹配 （matching）是边集中两两边不相交的子集。最大匹配 是边数最多的匹配。完美匹配 覆盖所有顶点。
Hall 定理 ：二部图 G = ⟨ V 1 , V 2 , E ⟩ G=\langle V_1, V_2, E\rangle G = ⟨ V 1 , V 2 , E ⟩ V 1 V_1 V 1 V 2 V_2 V 2 V 1 V_1 V 1 ⇔ \Leftrightarrow ⇔ S ⊆ V 1 S\subseteq V_1 S ⊆ V 1 ∣ N ( S ) ∣ ≥ ∣ S ∣ |N(S)|\ge|S| ∣ N ( S ) ∣ ≥ ∣ S ∣ N ( S ) N(S) N ( S ) S S S
6.2 欧拉图 本节为高频必考点，欧拉图判定条件是考试必考填空/选择题
欧拉迹 是经过每条边恰好一次 的迹，首尾相接的为欧拉回路 。存在欧拉回路的图称欧拉图 。
判定（无向连通图）：
存在欧拉回路 ⇔ \Leftrightarrow ⇔ 存在欧拉迹（非回路）⇔ \Leftrightarrow ⇔ 易错点 ：欧拉图要求"每边一次"，不是"每点一次"——后者是哈密顿图。K n K_n K n n n n n − 1 n-1 n − 1 n n n
例（真题） 判断下列图是否存在欧拉回路或欧拉迹：
K 5 K_5 K 5 K 3 , 3 K_{3,3} K 3 , 3 解 (1) K 5 K_5 K 5 K 5 K_5 K 5
(2) K 3 , 3 K_{3,3} K 3 , 3
6.3 哈密顿图 本节为重难点，哈密顿图无简单充要条件，充分/必要条件的方向判断是考试难点
哈密顿路 经过每个顶点恰好一次的路；首尾相接为哈密顿回路 。存在哈密顿回路的图称哈密顿图 。
与欧拉图不同，哈密顿图的充要判定至今没有简单的多项式充要条件，只有充分条件与必要条件。
必要条件（删点）：若 G G G S ⊂ V S\subset V S ⊂ V S S S ω ( G − S ) ≤ ∣ S ∣ \omega(G-S)\le|S| ω ( G − S ) ≤ ∣ S ∣
充分条件：
Dirac 定理 ：n ≥ 3 n\ge3 n ≥ 3 δ ( G ) ≥ n / 2 \delta(G)\ge n/2 δ ( G ) ≥ n /2 G G G Ore 定理 （更广）：n ≥ 3 n\ge3 n ≥ 3 u , v u,v u , v deg ( u ) + deg ( v ) ≥ n \deg(u)+\deg(v)\ge n deg ( u ) + deg ( v ) ≥ n G G G 闭包定理 （Bondy–Chvátal）：反复对不相邻且度和 ≥ n \ge n ≥ n 易错点 ：Dirac/Ore 是充分不必要，满足时理论保证存在但不一定能"看出"回路；不满足时图也可能仍哈密顿。K n ( n ≥ 3 ) K_n(n\ge3) K n ( n ≥ 3 ) K m , n K_{m,n} K m , n m = n m=n m = n m ≠ n m\ne n m = n
例（真题） 判断下列图是否为哈密顿图：(1) K 5 K_5 K 5 K 3 , 3 K_{3,3} K 3 , 3
解 (1) K 5 K_5 K 5 n = 5 , δ = 4 ≥ 5 / 2 n=5,\delta=4\ge5/2 n = 5 , δ = 4 ≥ 5/2
(2) K 3 , 3 K_{3,3} K 3 , 3 m = n = 3 m=n=3 m = n = 3 m = n m=n m = n
(3) Petersen 图：3-正则图，n = 10 , δ = 3 < 5 n=10,\delta=3<5 n = 10 , δ = 3 < 5
6.4 平面图 本节为高频必考点，欧拉公式 v − e + f = 2 v-e+f=2 v − e + f = 2
若图能画在平面上使边除端点外不相交，称为平面图 。K 5 K_5 K 5 K 3 , 3 K_{3,3} K 3 , 3 ⇔ \Leftrightarrow ⇔ K 5 K_5 K 5 K 3 , 3 K_{3,3} K 3 , 3
连通平面图的面 f f f v v v e e e 欧拉公式 ：
v − e + f = 2. v-e+f=2. v − e + f = 2.
推论（边数上界）：n ≥ 3 n\ge3 n ≥ 3 e ≤ 3 n − 6 e\le 3n-6 e ≤ 3 n − 6 e ≤ 2 n − 4 e\le 2n-4 e ≤ 2 n − 4 K 5 K_5 K 5 e = 10 > 9 e=10>9 e = 10 > 9 K 3 , 3 K_{3,3} K 3 , 3 e = 9 > 8 e=9>8 e = 9 > 8
例（真题） 判断 K 5 K_5 K 5 K 3 , 3 K_{3,3} K 3 , 3
解 (1) K 5 K_5 K 5 n = 5 , e = 10 n=5, e=10 n = 5 , e = 10 e ≤ 3 n − 6 = 9 e\le3n-6=9 e ≤ 3 n − 6 = 9 10 > 9 10>9 10 > 9 K 5 K_5 K 5
(2) K 3 , 3 K_{3,3} K 3 , 3 n = 6 , e = 9 n=6, e=9 n = 6 , e = 9 e ≤ 2 n − 4 = 8 e\le2n-4=8 e ≤ 2 n − 4 = 8 9 > 8 9>8 9 > 8 K 3 , 3 K_{3,3} K 3 , 3
例（真题） 一个连通平面图有 6 个顶点、8 条边，求面数 f f f
解 由欧拉公式 v − e + f = 2 v-e+f=2 v − e + f = 2 6 − 8 + f = 2 6-8+f=2 6 − 8 + f = 2 f = 4 f=4 f = 4 = 2 e = 16 =2e=16 = 2 e = 16 = 16 / 4 = 4 =16/4=4 = 16/4 = 4
极大平面图 ：再加任一边即非平面。n ≥ 3 n\ge3 n ≥ 3 e = 3 n − 6 e=3n-6 e = 3 n − 6 对偶图 G ∗ G^* G ∗ G G G G ∗ G^* G ∗ G ∗ G^* G ∗ G G G G ∗ G^* G ∗ 格雷码 ：平面图嵌入的应用之一，用二进制序列编码，相邻码恰差一位，对应超立方体的哈密顿回路。第7章 树 7.1 无向树及生成树 本节为高频必考点，树的等价定义与最小生成树（Kruskal/Prim）是考试必考题
树 是连通无圈无向图。无圈（不一定连通）的图称为森林 ，每个连通分量为树。树叶是度为 1 的顶点。
树的等价刻画（任一可作定义）：n n n T T T ⇔ \Leftrightarrow ⇔
T T T T T T n − 1 n-1 n − 1 T T T n − 1 n-1 n − 1 T T T 基本计数 ：n n n n n − 2 n^{n-2} n n − 2
例（真题） 下列哪些图是树？(1) K 4 K_4 K 4 C 5 C_5 C 5 G G G v = 5 , e = 4 v=5, e=4 v = 5 , e = 4 K 1 , 4 K_{1,4} K 1 , 4
解 (1) K 4 K_4 K 4 C 5 C_5 C 5 e = v − 1 = 4 e=v-1=4 e = v − 1 = 4 K 1 , 4 K_{1,4} K 1 , 4
例（真题） 用 Kruskal 算法求带权连通图 G G G v 1 , … , v 6 v_1,\dots,v_6 v 1 , … , v 6 ( v 1 , v 2 , 1 ) , ( v 3 , v 5 , 2 ) , ( v 1 , v 3 , 3 ) , ( v 4 , v 5 , 4 ) , ( v 2 , v 3 , 5 ) , ( v 4 , v 6 , 5 ) , ( v 5 , v 6 , 6 ) , ( v 2 , v 4 , 7 ) (v_1,v_2,1),(v_3,v_5,2),(v_1,v_3,3),(v_4,v_5,4),(v_2,v_3,5),(v_4,v_6,5),(v_5,v_6,6),(v_2,v_4,7) ( v 1 , v 2 , 1 ) , ( v 3 , v 5 , 2 ) , ( v 1 , v 3 , 3 ) , ( v 4 , v 5 , 4 ) , ( v 2 , v 3 , 5 ) , ( v 4 , v 6 , 5 ) , ( v 5 , v 6 , 6 ) , ( v 2 , v 4 , 7 )
解 按权递增选边：
( v 1 , v 2 , 1 ) (v_1,v_2,1) ( v 1 , v 2 , 1 ) ( v 3 , v 5 , 2 ) (v_3,v_5,2) ( v 3 , v 5 , 2 ) ( v 1 , v 3 , 3 ) (v_1,v_3,3) ( v 1 , v 3 , 3 ) ( v 4 , v 5 , 4 ) (v_4,v_5,4) ( v 4 , v 5 , 4 ) 已选 4 条，n − 1 = 5 n-1=5 n − 1 = 5 ( v 4 , v 6 , 5 ) (v_4,v_6,5) ( v 4 , v 6 , 5 ) 最小生成树边权 1 + 2 + 3 + 4 + 5 = 15 1+2+3+4+5=15 1 + 2 + 3 + 4 + 5 = 15
生成树 ：连通图 G G G G G G G G G
最小生成树 （MST）：边带权连通图中权和最小的生成树。算法：
Kruskal （避圈法）：按权递增选边，不与已选边成圈则加入，直到 n − 1 n-1 n − 1 Prim （加点法）：从一点出发，每次加入连接"已选集"与"未选集"的最小权边。两者都贪心，保证最优。MST 不一定唯一，但所有 MST 权和相同。
7.2 根树及其应用 本节为高频必考点，二叉树遍历与哈夫曼树/前缀码是考试必考大题
给树指定一个顶点为根 ，得根树 。根树引入父子、深度、高度、内部点、叶、子树等概念。
m m m m m m 满 m m m ：每个内部点恰有 m m m 二叉树 ：m = 2 m=2 m = 2 遍历 ：前序、中序、后序、层序。最优二叉树（哈夫曼树） ：带权叶的二叉树中带权路径长最小者，用于最优前缀编码。构造：将权集合建成森林，反复合并两最小权根，直到一棵树。二叉树性质 ：设 n n n n 0 n_0 n 0 n 2 n_2 n 2 n 0 = n 2 + 1 n_0=n_2+1 n 0 = n 2 + 1 m m m l = ( m − 1 ) i + 1 l=(m-1)i+1 l = ( m − 1 ) i + 1 i i i
前缀码
例（真题） 设字符 A , B , C , D , E A,B,C,D,E A , B , C , D , E 5 , 10 , 15 , 20 , 50 5, 10, 15, 20, 50 5 , 10 , 15 , 20 , 50
解 将频率从小到大排序，反复合并两最小：
合并 A ( 5 ) A(5) A ( 5 ) B ( 10 ) B(10) B ( 10 ) A B ( 15 ) AB(15) A B ( 15 ) 合并 A B ( 15 ) AB(15) A B ( 15 ) C ( 15 ) C(15) C ( 15 ) A B C ( 30 ) ABC(30) A B C ( 30 ) 合并 D ( 20 ) D(20) D ( 20 ) A B C ( 30 ) ABC(30) A B C ( 30 ) D A B C ( 50 ) DABC(50) D A B C ( 50 ) 合并 E ( 50 ) E(50) E ( 50 ) D A B C ( 50 ) DABC(50) D A B C ( 50 ) E D A B C ( 100 ) EDABC(100) E D A B C ( 100 ) 编码（左 0 右 1，频率高离根近）：
E E E D D D C C C A A A B B B 平均码长 = 0.50 × 1 + 0.20 × 2 + 0.15 × 3 + 0.05 × 4 + 0.10 × 4 = 2.25 =0.50\times1+0.20\times2+0.15\times3+0.05\times4+0.10\times4=2.25 = 0.50 × 1 + 0.20 × 2 + 0.15 × 3 + 0.05 × 4 + 0.10 × 4 = 2.25
例（真题） 给定二叉树的前序遍历序列 ABDHECFG 和中序遍历序列 DHBEAFCG，重建二叉树。
解 前序首元素 A 为根。在中序中，A 左侧 DHBE 为左子树，右侧 FCG 为右子树。
左子树前序 BDHE，中序 DHBE：根 B，左侧 DHE 为左子树（中序 DHE，前序 DHE），根 D，右子树 HE（中序 HE，前序 HE），根 H，右子树 E。
右子树前序 CFG，中序 FCG：根 C，左子树 F，右子树 G。
最终树：A(B(D,H(E)),C(F,G))（节点：左/右）。
第四篇 组合分析初步 组合分析研究"有多少种方式"——离散对象的计数。本篇对齐教材第8章，覆盖加法与乘法法则、排列组合计数及递推方程求解，并将容斥原理与生成函数列为拓展阅读。
第8章 组合分析初步 8.1 加法法则和乘法法则 加法法则（分类） ：做一件事有 n n n i i i m i m_i m i ∑ m i \sum m_i ∑ m i 乘法法则（分步） ：做一件事分 k k k i i i m i m_i m i ∏ m i \prod m_i ∏ m i 易错点 ：判定用加法还是乘法，看方案是"并列（或）"还是"分步（且）"。并列且互斥用加法，分步且独立用乘法。若既分类又分步，则先分类每类内分步，再加总。
8.2 基本排列组合的计数方法 本节为高频必考点，排列组合计数与隔板法是考试必考计算题
n n n r r r
模型 公式 含义 排列 P ( n , r ) P(n,r) P ( n , r ) n ! ( n − r ) ! \dfrac{n!}{(n-r)!} ( n − r )! n ! 有序、不重复 组合 C ( n , r ) = ( n r ) C(n,r)=\binom nr C ( n , r ) = ( r n ) n ! r ! ( n − r ) ! \dfrac{n!}{r!(n-r)!} r ! ( n − r )! n ! 无序、不重复 可重排列 n r n^r n r 有序、可重复 可重组合 H n r H_n^r H n r ( n + r − 1 r ) \binom{n+r-1}{r} ( r n + r − 1 ) 无序、可重复（隔板法） 圆排列 ( n − 1 ) ! (n-1)! ( n − 1 )! n n n n n n 环上无固定起点 多重集排列 n ! n 1 ! n 2 ! ⋯ n k ! \dfrac{n!}{n_1!n_2!\cdots n_k!} n 1 ! n 2 ! ⋯ n k ! n ! 含重复元素的排列
隔板法 （可重组合）：把 r r r n n n H n r = ( n + r − 1 r ) H_n^r=\binom{n+r-1}{r} H n r = ( r n + r − 1 ) ( r − 1 n − 1 ) \binom{r-1}{n-1} ( n − 1 r − 1 )
例 5 本相同书分给 3 人，每人至少 1 本，几种？隔板法：( 5 − 1 3 − 1 ) = ( 4 2 ) = 6 \binom{5-1}{3-1}=\binom42=6 ( 3 − 1 5 − 1 ) = ( 2 4 ) = 6 ( 5 + 3 − 1 3 − 1 ) = ( 7 2 ) = 21 \binom{5+3-1}{3-1}=\binom72=21 ( 3 − 1 5 + 3 − 1 ) = ( 2 7 ) = 21
例（真题） 用 0,1,2,3,4,5 组成无重复数字的四位数，求：(1) 共多少个？(2) 其中偶数多少个？
解 (1) 四位数首位非 0：首位 5 选（1-5），其余 3 位从剩下 5 个数选排列 P ( 5 , 3 ) = 60 P(5,3)=60 P ( 5 , 3 ) = 60 5 × 60 = 300 5\times60=300 5 × 60 = 300
(2) 偶数末位为 0,2,4：末位 0 时首位 5 选、中间 P ( 4 , 2 ) = 12 P(4,2)=12 P ( 4 , 2 ) = 12 5 × 12 = 60 5\times12=60 5 × 12 = 60 P ( 4 , 2 ) = 12 P(4,2)=12 P ( 4 , 2 ) = 12 2 × 4 × 12 = 96 2\times4\times12=96 2 × 4 × 12 = 96 60 + 96 = 156 60+96=156 60 + 96 = 156
例（真题） 求 ( x + y + z ) 6 (x+y+z)^6 ( x + y + z ) 6 x 2 y 3 z x^2y^3z x 2 y 3 z
解 多项式定理，系数为 6 ! 2 ! 3 ! 1 ! = 720 12 = 60 \frac{6!}{2!3!1!}=\frac{720}{12}=60 2 ! 3 ! 1 ! 6 ! = 12 720 = 60
二项式定理 ：( x + y ) n = ∑ k = 0 n ( n k ) x n − k y k (x+y)^n=\sum_{k=0}^n\binom nk x^{n-k}y^k ( x + y ) n = ∑ k = 0 n ( k n ) x n − k y k x = y = 1 x=y=1 x = y = 1 ∑ ( n k ) = 2 n \sum\binom nk=2^n ∑ ( k n ) = 2 n
对称：( n k ) = ( n n − k ) \binom nk=\binom n{n-k} ( k n ) = ( n − k n ) 递推（Pascal）：( n k ) = ( n − 1 k − 1 ) + ( n − 1 k ) \binom nk=\binom{n-1}{k-1}+\binom{n-1}k ( k n ) = ( k − 1 n − 1 ) + ( k n − 1 ) 求和（曲棍球）：∑ k = r n ( k r ) = ( n + 1 r + 1 ) \sum_{k=r}^n\binom kr=\binom{n+1}{r+1} ∑ k = r n ( r k ) = ( r + 1 n + 1 ) 范德蒙德：∑ k = 0 r ( m k ) ( n r − k ) = ( m + n r ) \sum_{k=0}^r\binom mk\binom n{r-k}=\binom{m+n}{r} ∑ k = 0 r ( k m ) ( r − k n ) = ( r m + n ) 8.3 递推方程的求解与应用 本节为高频必考点，特征方程法求解线性常系数递推是考试必考计算题
递推关系 用前若干项定义后项，如斐波那契 F n = F n − 1 + F n − 2 , F 0 = 0 , F 1 = 1 F_n=F_{n-1}+F_{n-2},F_0=0,F_1=1 F n = F n − 1 + F n − 2 , F 0 = 0 , F 1 = 1
线性常系数齐次递推 ：a n + c 1 a n − 1 + ⋯ + c k a n − k = 0 a_n+c_1a_{n-1}+\cdots+c_ka_{n-k}=0 a n + c 1 a n − 1 + ⋯ + c k a n − k = 0 特征方程 r k + c 1 r k − 1 + ⋯ + c k = 0 r^k+c_1r^{k-1}+\cdots+c_k=0 r k + c 1 r k − 1 + ⋯ + c k = 0
若特征根 r 1 , … , r k r_1,\dots,r_k r 1 , … , r k a n = ∑ C i r i n a_n=\sum C_i r_i^n a n = ∑ C i r i n 若 r r r m m m ( C 1 + C 2 n + ⋯ + C m n m − 1 ) r n (C_1+C_2 n+\cdots+C_m n^{m-1})r^n ( C 1 + C 2 n + ⋯ + C m n m − 1 ) r n 复根 α ± β i \alpha\pm\beta i α ± β i r n ( A cos n θ + B sin n θ ) r^n(A\cos n\theta+B\sin n\theta) r n ( A cos n θ + B sin n θ ) 常数由初值代入通解联立解出。
例 a n = a n − 1 + 2 a n − 2 , a 0 = 0 , a 1 = 1 a_n=a_{n-1}+2a_{n-2},a_0=0,a_1=1 a n = a n − 1 + 2 a n − 2 , a 0 = 0 , a 1 = 1
特征方程 r 2 = r + 2 ⇒ r = 2 , − 1 r^2=r+2\Rightarrow r=2,-1 r 2 = r + 2 ⇒ r = 2 , − 1 a n = C 1 ⋅ 2 n + C 2 ( − 1 ) n a_n=C_1\cdot2^n+C_2(-1)^n a n = C 1 ⋅ 2 n + C 2 ( − 1 ) n
代入初值：C 1 + C 2 = 0 C_1+C_2=0 C 1 + C 2 = 0 2 C 1 − C 2 = 1 2C_1-C_2=1 2 C 1 − C 2 = 1 C 1 = 1 / 3 , C 2 = − 1 / 3 C_1=1/3,C_2=-1/3 C 1 = 1/3 , C 2 = − 1/3 a n = 2 n − ( − 1 ) n 3 a_n=\frac{2^n--1^n}{3} a n = 3 2 n − ( − 1 ) n
例（真题） 求解递推 a n = 4 a n − 1 − 4 a n − 2 , a 0 = 1 , a 1 = 4 a_n=4a_{n-1}-4a_{n-2},\ a_0=1,\ a_1=4 a n = 4 a n − 1 − 4 a n − 2 , a 0 = 1 , a 1 = 4
解 特征方程 r 2 − 4 r + 4 = 0 ⇒ ( r − 2 ) 2 = 0 r^2-4r+4=0\Rightarrow(r-2)^2=0 r 2 − 4 r + 4 = 0 ⇒ ( r − 2 ) 2 = 0 r = 2 r=2 r = 2 a n = ( C 1 + C 2 n ) ⋅ 2 n a_n=(C_1+C_2 n)\cdot2^n a n = ( C 1 + C 2 n ) ⋅ 2 n
代入初值：C 1 = 1 C_1=1 C 1 = 1 ( 1 + C 2 ) ⋅ 2 = 4 ⇒ C 2 = 1 (1+C_2)\cdot2=4\Rightarrow C_2=1 ( 1 + C 2 ) ⋅ 2 = 4 ⇒ C 2 = 1 a n = ( 1 + n ) ⋅ 2 n a_n=(1+n)\cdot2^n a n = ( 1 + n ) ⋅ 2 n
验证：a 2 = 4 ⋅ 4 − 4 ⋅ 1 = 12 a_2=4\cdot4-4\cdot1=12 a 2 = 4 ⋅ 4 − 4 ⋅ 1 = 12 ( 1 + 2 ) ⋅ 4 = 12 (1+2)\cdot4=12 ( 1 + 2 ) ⋅ 4 = 12
例（真题） 汉诺塔的递推 T n = 2 T n − 1 + 1 , T 0 = 0 T_n=2T_{n-1}+1,\ T_0=0 T n = 2 T n − 1 + 1 , T 0 = 0 T n T_n T n
解 先求特解：设 T n ∗ = A T_n^*=A T n ∗ = A A = 2 A + 1 ⇒ A = − 1 A=2A+1\Rightarrow A=-1 A = 2 A + 1 ⇒ A = − 1 r − 2 = 0 ⇒ r = 2 r-2=0\Rightarrow r=2 r − 2 = 0 ⇒ r = 2 T n = C ⋅ 2 n − 1 T_n=C\cdot2^n-1 T n = C ⋅ 2 n − 1 T 0 = 0 T_0=0 T 0 = 0 C − 1 = 0 ⇒ C = 1 C-1=0\Rightarrow C=1 C − 1 = 0 ⇒ C = 1 T n = 2 n − 1 T_n=2^n-1 T n = 2 n − 1
非齐次递推 ：a n + c 1 a n − 1 + ⋯ = f ( n ) a_n+c_1a_{n-1}+\cdots=f(n) a n + c 1 a n − 1 + ⋯ = f ( n ) f ( n ) f(n) f ( n )
递推建模 ：汉诺塔 T n = 2 T n − 1 + 1 → 2 n − 1 T_n=2T_{n-1}+1\to 2^n-1 T n = 2 T n − 1 + 1 → 2 n − 1 C n = 1 n + 1 ( 2 n n ) C_n=\frac{1}{n+1}\binom{2n}{n} C n = n + 1 1 ( n 2 n )
易错点 ：特征方程法只适用于线性常系数齐次 递推，非线性递推（如 a n = a n − 1 2 a_n=a_{n-1}^2 a n = a n − 1 2 n n n C ⋅ r n C\cdot r^n C ⋅ r n
8.4 拓展阅读：容斥原理与生成函数 以下内容超出教材第8章范围，但在组合计数中极为重要，作为拓展补充。
容斥原理 ：n n n
∣ ⋃ i = 1 n A i ∣ = ∑ ∣ A i ∣ − ∑ ∣ A i ∩ A j ∣ + ⋯ + ( − 1 ) n + 1 ∣ A 1 ∩ ⋯ ∩ A n ∣ . \left|\bigcup_{i=1}^n A_i\right|=\sum|A_i|-\sum|A_i\cap A_j|+\cdots+(-1)^{n+1}|A_1\cap\cdots\cap A_n|. i = 1 ⋃ n A i = ∑ ∣ A i ∣ − ∑ ∣ A i ∩ A j ∣ + ⋯ + ( − 1 ) n + 1 ∣ A 1 ∩ ⋯ ∩ A n ∣.
经典应用：错排公式 D n = n ! ∑ k = 0 n ( − 1 ) k k ! D_n=n!\sum_{k=0}^n\frac{(-1)^k}{k!} D n = n ! ∑ k = 0 n k ! ( − 1 ) k
例（真题） 求 4 封信全部装错信封的装法数。
解 错排公式 D 4 = 4 ! ( 1 − 1 + 1 2 − 1 6 + 1 24 ) = 24 × 3 8 = 9 D_4=4!\left(1-1+\frac12-\frac16+\frac1{24}\right)=24\times\frac38=9 D 4 = 4 ! ( 1 − 1 + 2 1 − 6 1 + 24 1 ) = 24 × 8 3 = 9
也可用容斥直接算：∣ A i ∣ |A_i| ∣ A i ∣ i i i ∣ A i ∣ = 3 ! = 6 |A_i|=3!=6 ∣ A i ∣ = 3 ! = 6 ∑ ∣ A i ∣ = 4 × 6 = 24 \sum|A_i|=4\times6=24 ∑ ∣ A i ∣ = 4 × 6 = 24 ∣ A i ∩ A j ∣ = 2 ! = 2 |A_i\cap A_j|=2!=2 ∣ A i ∩ A j ∣ = 2 ! = 2 ( 4 2 ) × 2 = 12 \binom42\times2=12 ( 2 4 ) × 2 = 12 ∣ A i ∩ A j ∩ A k ∣ = 1 |A_i\cap A_j\cap A_k|=1 ∣ A i ∩ A j ∩ A k ∣ = 1 ( 4 3 ) = 4 \binom43=4 ( 3 4 ) = 4 ∣ A 1 ∩ A 2 ∩ A 3 ∩ A 4 ∣ = 1 |A_1\cap A_2\cap A_3\cap A_4|=1 ∣ A 1 ∩ A 2 ∩ A 3 ∩ A 4 ∣ = 1
D 4 = 4 ! − 4 ⋅ 3 ! + 6 ⋅ 2 ! − 4 ⋅ 1 ! + 1 = 24 − 24 + 12 − 4 + 1 = 9. D_4=4!-4\cdot3!+6\cdot2!-4\cdot1!+1=24-24+12-4+1=9. D 4 = 4 ! − 4 ⋅ 3 ! + 6 ⋅ 2 ! − 4 ⋅ 1 ! + 1 = 24 − 24 + 12 − 4 + 1 = 9.
生成函数 ：数列 { a n } \{a_n\} { a n } G ( x ) = ∑ a n x n G(x)=\sum a_n x^n G ( x ) = ∑ a n x n G ( x ) = x 1 − x − x 2 G(x)=\frac{x}{1-x-x^2} G ( x ) = 1 − x − x 2 x
第五篇 代数结构 代数结构研究带运算的集合，关心运算的封闭性与各种"律"。本篇对齐教材第9章，以"代数系统简介"的深度介绍二元运算、代数系统及几个典型代数系统（半群、群、环、域、格、布尔代数），不展开深入证明。
第9章 代数系统简介 9.1 二元运算及其性质 设 S S S f : S 2 → S f:S^2\to S f : S 2 → S S S S 二元运算 ，常记 ∗ \ast ∗ + + + ∗ \ast ∗ S S S 封闭 ：∀ a , b ∈ S , a ∗ b ∈ S \forall a,b\in S,\ a\ast b\in S ∀ a , b ∈ S , a ∗ b ∈ S
二元运算可具有的性质：
性质 条件（∀ \forall ∀ 交换律 a ∗ b = b ∗ a a\ast b=b\ast a a ∗ b = b ∗ a 结合律 ( a ∗ b ) ∗ c = a ∗ ( b ∗ c ) (a\ast b)\ast c=a\ast(b\ast c) ( a ∗ b ) ∗ c = a ∗ ( b ∗ c ) 分配律（两种运算间） a ∗ ( b ∘ c ) = ( a ∗ b ) ∘ ( a ∗ c ) a\ast(b\circ c)=(a\ast b)\circ(a\ast c) a ∗ ( b ∘ c ) = ( a ∗ b ) ∘ ( a ∗ c ) 单位元 e e e e ∗ a = a ∗ e = a e\ast a=a\ast e=a e ∗ a = a ∗ e = a 零元 θ \theta θ θ ∗ a = a ∗ θ = θ \theta\ast a=a\ast\theta=\theta θ ∗ a = a ∗ θ = θ 逆元 a − 1 a^{-1} a − 1 a ∗ a − 1 = a − 1 ∗ a = e a\ast a^{-1}=a^{-1}\ast a=e a ∗ a − 1 = a − 1 ∗ a = e
唯一性 ：若左单位元与右单位元同时存在则相等且唯一；零元同理。逆元针对确定的单位元而言，结合运算下若左逆与右逆都存在则相等且唯一。
易错点 ：单位元 e e e 所有 元素满足 e ∗ a = a ∗ e = a e\ast a=a\ast e=a e ∗ a = a ∗ e = a
9.2 代数系统 一个代数系统 （代数）记作 ⟨ S , ∗ 1 , … , ∗ n ⟩ \langle S,\ast_1,\dots,\ast_n\rangle ⟨ S , ∗ 1 , … , ∗ n ⟩
子代数 ：若 S ′ ⊆ S S'\subseteq S S ′ ⊆ S ⟨ S ′ , ∗ 1 , … ⟩ \langle S',\ast_1,\dots\rangle ⟨ S ′ , ∗ 1 , … ⟩ ⟨ S , ∗ 1 , … ⟩ \langle S,\ast_1,\dots\rangle ⟨ S , ∗ 1 , … ⟩ 同态 ：映射 φ : S → S ′ \varphi:S\to S' φ : S → S ′ φ ( a ∗ b ) = φ ( a ) ∗ ′ φ ( b ) \varphi(a\ast b)=\varphi(a)\ast'\varphi(b) φ ( a ∗ b ) = φ ( a ) ∗ ′ φ ( b ) 同构 ，两代数"结构相同"。9.3 几个典型的代数系统 本节为高频必考点，群的判定与运算表分析是考试必考题
以下由弱到强列出常见代数系统，每步增加一条性质：
代数系统 定义要点 典型例子 半群 封闭+结合律 ⟨ N , + ⟩ \langle\mathbb N,+\rangle ⟨ N , + ⟩ 独异点 （含幺半群）半群+单位元 ⟨ N , ⋅ ⟩ \langle\mathbb N,\cdot\rangle ⟨ N , ⋅ ⟩ 1 1 1 群 独异点+每个元素有逆元 ⟨ Z , + ⟩ \langle\mathbb Z,+\rangle ⟨ Z , + ⟩ ⟨ R ∗ , ⋅ ⟩ \langle\mathbb R^*,\cdot\rangle ⟨ R ∗ , ⋅ ⟩ 交换群 （Abel 群）群+交换律 ⟨ Z , + ⟩ \langle\mathbb Z,+\rangle ⟨ Z , + ⟩
群 的基本性质（a , b ∈ G a,b\in G a , b ∈ G
单位元唯一，逆元唯一； 消去律：a ∗ b = a ∗ c ⇒ b = c a\ast b=a\ast c\Rightarrow b=c a ∗ b = a ∗ c ⇒ b = c ( a ∗ b ) − 1 = b − 1 ∗ a − 1 (a\ast b)^{-1}=b^{-1}\ast a^{-1} ( a ∗ b ) − 1 = b − 1 ∗ a − 1 子群 H ≤ G H\le G H ≤ G Lagrange 定理 ∣ H ∣ ∣ ∣ G ∣ |H|\mid|G| ∣ H ∣ ∣ ∣ G ∣ 循环群 ⟨ a ⟩ \langle a\rangle ⟨ a ⟩ n n n ≅ ⟨ Z n , + ⟩ \cong\langle\mathbb Z_n,+\rangle ≅ ⟨ Z n , + ⟩ 同态基本定理 G / ker φ ≅ im φ G/\ker\varphi\cong\text{im}\varphi G / ker φ ≅ im φ 环 ⟨ R , + , ⋅ ⟩ \langle R,+,\cdot\rangle ⟨ R , + , ⋅ ⟩ ⟨ R , + ⟩ \langle R,+\rangle ⟨ R , + ⟩ ⟨ R , ⋅ ⟩ \langle R,\cdot\rangle ⟨ R , ⋅ ⟩ 整环 ；每个非零元有乘法逆元的交换含幺环为域 。
结构 关键性质 环 加群+乘半群+分配律 整环 交换含幺环+无零因子+消去律 域 整环+非零元有逆
格 与布尔代数 ：
格 ：偏序集中任两元素有上下确界。等价地，⟨ L , ∧ , ∨ ⟩ \langle L,\land,\lor\rangle ⟨ L , ∧ , ∨ ⟩ 布尔代数 ：有补分配格。补元唯一，满足德摩根律 a ∧ b ‾ = a ˉ ∨ b ˉ \overline{a\land b}=\bar a\lor\bar b a ∧ b = a ˉ ∨ b ˉ ⟨ { 0 , 1 } , ∧ , ∨ , ′ , 0 , 1 ⟩ \langle\{0,1\},\land,\lor,',0,1\rangle ⟨{ 0 , 1 } , ∧ , ∨ , ′ , 0 , 1 ⟩ 易错点 ：环的乘法不要求消去律、不要求无零因子。不要把群中自动成立的消去律误用到环的乘法上。布尔代数要求补元唯一，一般有补格补元不一定唯一。
例（真题） 设 G = { 1 , 2 , 3 , 4 , 5 , 6 } G=\{1,2,3,4,5,6\} G = { 1 , 2 , 3 , 4 , 5 , 6 } ∗ \ast ∗ a ∗ b = a b m o d 7 a\ast b=ab\mod 7 a ∗ b = ab mod 7 ⟨ G , ∗ ⟩ \langle G,\ast\rangle ⟨ G , ∗ ⟩
解 先验证 G G G { 1 , … , 6 } \{1,\dots,6\} { 1 , … , 6 } 1 − 1 = 1 , 2 − 1 = 4 , 3 − 1 = 5 , 4 − 1 = 2 , 5 − 1 = 3 , 6 − 1 = 6 1^{-1}=1,2^{-1}=4,3^{-1}=5,4^{-1}=2,5^{-1}=3,6^{-1}=6 1 − 1 = 1 , 2 − 1 = 4 , 3 − 1 = 5 , 4 − 1 = 2 , 5 − 1 = 3 , 6 − 1 = 6
求生成元：2 1 = 2 , 2 2 = 4 , 2 3 = 1 2^1=2,2^2=4,2^3=1 2 1 = 2 , 2 2 = 4 , 2 3 = 1 3 1 = 3 , 3 2 = 2 , 3 3 = 6 , 3 4 = 4 , 3 5 = 5 , 3 6 = 1 3^1=3,3^2=2,3^3=6,3^4=4,3^5=5,3^6=1 3 1 = 3 , 3 2 = 2 , 3 3 = 6 , 3 4 = 4 , 3 5 = 5 , 3 6 = 1 ∣ G ∣ |G| ∣ G ∣ 3 3 3 ⟨ G , ∗ ⟩ = ⟨ 3 ⟩ \langle G,\ast\rangle=\langle3\rangle ⟨ G , ∗ ⟩ = ⟨ 3 ⟩ ≅ Z 6 \cong\mathbb Z_6 ≅ Z 6
例（真题） 设 S = { a , b , c } S=\{a,b,c\} S = { a , b , c } ∗ \ast ∗ ⟨ S , ∗ ⟩ \langle S,\ast\rangle ⟨ S , ∗ ⟩
∗ a b c a a b c b b c a c c a b \begin{array}{c|ccc}\ast&a&b&c\\\hline a&a&b&c\\b&b&c&a\\c&c&a&b\end{array} ∗ a b c a a b c b b c a c c a b
解 (1) 封闭：表中元素均在 S S S a a a a a a a − 1 = a a^{-1}=a a − 1 = a b ∗ c = a b\ast c=a b ∗ c = a c − 1 = b c^{-1}=b c − 1 = b Z 3 \mathbb Z_3 Z 3 a = 0 , b = 1 , c = 2 a=0,b=1,c=2 a = 0 , b = 1 , c = 2 ⟨ S , ∗ ⟩ \langle S,\ast\rangle ⟨ S , ∗ ⟩
第六篇 形式语言与自动机初步 形式语言与自动机是理论计算机科学的基础，研究"语言"的数学描述与"机器"的计算能力。本篇对齐教材第10章（第六版重点改写内容），覆盖文法与语言、有限自动机、正则表达式、图灵机，并介绍正则文法与上下文无关文法的应用及语法分析树。
第10章 形式语言和自动机初步 10.1 文法和语言 10.1.1 文法的基本概念 字母表 Σ \Sigma Σ 字母 。Σ \Sigma Σ 字符串 （字）是字母的有限序列，空串记 ε \varepsilon ε Σ \Sigma Σ Σ ∗ \Sigma^* Σ ∗ ε \varepsilon ε Σ + \Sigma^+ Σ + Σ ∗ \Sigma^* Σ ∗ Σ \Sigma Σ 语言 。
文法 （grammar）是一个四元组 G = ⟨ V N , V T , P , S ⟩ G=\langle V_N, V_T, P, S\rangle G = ⟨ V N , V T , P , S ⟩
V N V_N V N V T V_T V T V N ∩ V T = ∅ V_N\cap V_T=\varnothing V N ∩ V T = ∅ P P P α → β \alpha\to\beta α → β α \alpha α S ∈ V N S\in V_N S ∈ V N 推导 ：若 α → β ∈ P \alpha\to\beta\in P α → β ∈ P γ α δ \gamma\alpha\delta γ α δ α \alpha α β \beta β γ β δ \gamma\beta\delta γ β δ γ α δ ⇒ γ β δ \gamma\alpha\delta\Rightarrow\gamma\beta\delta γ α δ ⇒ γ β δ ⇒ ∗ \Rightarrow^* ⇒ ∗ S S S G G G 语言 L ( G ) = { w ∈ V T ∗ ∣ S ⇒ ∗ w } L(G)=\{w\in V_T^*\mid S\Rightarrow^* w\} L ( G ) = { w ∈ V T ∗ ∣ S ⇒ ∗ w }
易错点 ：语言是终结符串的集合，非终结符不能出现在最终的"字"中。推导的方向是"从左到右替换"，α → β \alpha\to\beta α → β α \alpha α β \beta β
10.1.2 文法的分类（Chomsky 体系） 本节为重难点，Chomsky 四类文法的产生式限制与对应自动机是考试核心
Chomsky 按产生式形式将文法分为四类（层级递进，0 型最宽泛）：
类型 产生式限制 对应语言 对应自动机 0 型 （无限制）α → β \alpha\to\beta α → β α \alpha α 递归可枚举语言 图灵机 1 型 （上下文有关）∣ α ∣ ≤ ∣ β ∣ |\alpha|\le|\beta| ∣ α ∣ ≤ ∣ β ∣ 上下文有关语言 线性有界自动机 2 型 （上下文无关）A → β A\to\beta A → β A ∈ V N A\in V_N A ∈ V N 上下文无关语言 下推自动机 3 型 （正则）A → a B A\to aB A → a B A → a A\to a A → a A → B a A\to Ba A → B a A → a A\to a A → a 正则语言 有限自动机
类型从 0 到 3 逐级收紧 ：3 型 ⊂ \subset ⊂ ⊂ \subset ⊂ ⊂ \subset ⊂
易错点 ：正则文法的产生式右边至多含一个非终结符，且位置固定（右线性在最右，左线性在最左），不能两边混合。上下文无关文法的产生式左部恰为一个非终结符（不是"上下文有关"——那要求左部含上下文）。
例（真题） 指出下列文法的 Chomsky 类型：
G 1 G_1 G 1 S → A B , A → a A ∣ a , B → b B ∣ b S\to AB,\ A\to aA\mid a,\ B\to bB\mid b S → A B , A → a A ∣ a , B → b B ∣ b G 2 G_2 G 2 S → a S b ∣ a b S\to aSb\mid ab S → a S b ∣ ab G 3 G_3 G 3 S → a S ∣ a , S → b S\to aS\mid a,\ S\to b S → a S ∣ a , S → b 解 (1) G 1 G_1 G 1
(2) G 2 G_2 G 2 S → a S b S\to aSb S → a S b { a n b n ∣ n ≥ 1 } \{a^nb^n\mid n\ge1\} { a n b n ∣ n ≥ 1 }
(3) G 3 G_3 G 3 S → a S S\to aS S → a S S → a S\to a S → a S → b S\to b S → b
10.1.3 正则文法与上下文无关文法 正则文法 （3 型）：产生式形如 A → a B A\to aB A → a B A → B a A\to Ba A → B a A → a A\to a A → a A → ε A\to\varepsilon A → ε 正则语言 。
例 G = ⟨ { S } , { 0 , 1 } , P , S ⟩ G=\langle\{S\},\{0,1\},P,S\rangle G = ⟨{ S } , { 0 , 1 } , P , S ⟩ P = { S → 0 S , S → 1 S , S → 0 , S → 1 } P=\{S\to0S,\ S\to1S,\ S\to0,\ S\to1\} P = { S → 0 S , S → 1 S , S → 0 , S → 1 } { 0 , 1 } + \{0,1\}^+ { 0 , 1 } +
上下文无关文法 （2 型）：产生式左部恰为一个非终结符，右部为任意串。生成的语言称为上下文无关语言 。
例 生成"括号匹配语言" { w ∈ { ( , ) } ∗ ∣ w \{w\in\{(,)\}^*\mid w { w ∈ {( , ) } ∗ ∣ w } \} }
G = ⟨ { S } , { ( , ) } , { S → S S , S → ( S ) , S → ε } , S ⟩ . G=\langle\{S\},\{(,)\},\{S\to SS,\ S\to(S),\ S\to\varepsilon\},S\rangle. G = ⟨{ S } , {( , )} , { S → S S , S → ( S ) , S → ε } , S ⟩ .
此语言不是正则语言（不能用有限状态机识别），但可用上下文无关文法生成。
10.1.4 正则文法与上下文无关文法的应用 正则文法的应用 ：
词法分析 ：编译器中用正则文法描述标识符、数字、关键字等词法单元（token），配合有限自动机实现词法扫描器。模式匹配 ：正则表达式本质上是正则文法的简洁表示，广泛用于文本搜索、输入验证。协议描述 ：通信协议中简单的状态转换可用正则文法刻画。上下文无关文法的应用 ：
语法分析 ：编程语言的语法结构（表达式、语句、函数定义等）通常用上下文无关文法描述（如 BNF 范式）。编译器的语法分析器（parser）据此将源代码构建为语法树。JSON/XML 数据格式 ：嵌套结构天然适合上下文无关文法描述。自然语言建模 ：部分自然语言结构（如嵌套从句）可用上下文无关文法近似。易错点 ：正则语言不能处理"嵌套配对"（如 a n b n a^nb^n a n b n
10.1.5 语法分析树 语法分析树 （派生树）是推导过程的树形表示：
根节点为起始符 S S S 每个内部节点标以非终结符，其子节点对应所用产生式的右部符号（从左到右）； 叶节点标以终结符或 ε \varepsilon ε 最左推导 ：每步替换最左边的非终结符；最右推导 ：每步替换最右边的非终结符。同一棵语法分析树可对应多个推导，但最左推导（或最右推导）与分析树一一对应。
二义性 ：若文法 G G G w ∈ L ( G ) w\in L(G) w ∈ L ( G ) G G G 二义文法 。注意，二义性是文法的性质，不是语言的性质——同一语言可能既有二义文法也有无二义文法。
易错点 ：文法的二义性与语言的固有二义性不同。固有二义语言指任何文法都是二义的；大多数编程语言语法可改写为无二义文法（如改写悬空 else 的优先级）。
例（真题） 文法 G G G S → S + S ∣ S ∗ S ∣ a ∣ b S\to S+S\mid S*S\mid a\mid b S → S + S ∣ S ∗ S ∣ a ∣ b a + b ∗ a a+b*a a + b ∗ a G G G
解 推导 1（先归约第一个 + + + S ⇒ S + S ⇒ a + S ⇒ a + S ∗ S ⇒ a + b ∗ S ⇒ a + b ∗ a S\Rightarrow S+S\Rightarrow a+S\Rightarrow a+S*S\Rightarrow a+b*S\Rightarrow a+b*a S ⇒ S + S ⇒ a + S ⇒ a + S ∗ S ⇒ a + b ∗ S ⇒ a + b ∗ a
推导 2（先归约 ∗ * ∗ S ⇒ S ∗ S ⇒ S + S ∗ S ⇒ a + S ∗ S ⇒ a + b ∗ S ⇒ a + b ∗ a S\Rightarrow S*S\Rightarrow S+S*S\Rightarrow a+S*S\Rightarrow a+b*S\Rightarrow a+b*a S ⇒ S ∗ S ⇒ S + S ∗ S ⇒ a + S ∗ S ⇒ a + b ∗ S ⇒ a + b ∗ a
两棵分析树结构不同（推导 1 中 + + + ∗ * ∗ G G G
10.2 有限自动机 有限自动机是识别正则语言的计算模型，状态数有限，无外部存储。
10.2.1 确定性有限自动机（DFA） DFA 是五元组 M = ⟨ Q , Σ , δ , q 0 , F ⟩ M=\langle Q,\Sigma,\delta,q_0,F\rangle M = ⟨ Q , Σ , δ , q 0 , F ⟩
Q Q Q Σ \Sigma Σ δ : Q × Σ → Q \delta:Q\times\Sigma\to Q δ : Q × Σ → Q q 0 ∈ Q q_0\in Q q 0 ∈ Q F ⊆ Q F\subseteq Q F ⊆ Q M M M 接受 字符串 w = a 1 a 2 ⋯ a n w=a_1a_2\cdots a_n w = a 1 a 2 ⋯ a n q 0 , q 1 , … , q n q_0,q_1,\dots,q_n q 0 , q 1 , … , q n δ ( q i − 1 , a i ) = q i \delta(q_{i-1},a_i)=q_i δ ( q i − 1 , a i ) = q i q n ∈ F q_n\in F q n ∈ F M M M L ( M ) = { w ∣ M L(M)=\{w\mid M L ( M ) = { w ∣ M w } w\} w }
10.2.2 非确定性有限自动机（NFA） 本节为高频必考点，NFA 与 DFA 的等价性转换（子集构造法）是考试常出题
NFA 与 DFA 的区别在于转移函数：δ : Q × ( Σ ∪ { ε } ) → 2 Q \delta:Q\times(\Sigma\cup\{\varepsilon\})\to 2^Q δ : Q × ( Σ ∪ { ε }) → 2 Q ε \varepsilon ε
NFA 接受 w w w q 0 q_0 q 0 w w w
等价性 ：对任一 NFA，存在等价的 DFA 接受同一语言（子集构造法：DFA 的状态为 NFA 状态集的子集）。因此 DFA 与 NFA 识别能力相同，都识别正则语言。
易错点 ：NFA 不是"不确定的自动机"，而是"非确定的"——它允许多个后继。NFA 接受字符串只需一条路径成功，不是所有路径都成功。ε \varepsilon ε
例（真题） 将下列 NFA 转换为等价的 DFA。
NFA M = ⟨ { q 0 , q 1 , q 2 } , { 0 , 1 } , δ , q 0 , { q 2 } ⟩ M=\langle\{q_0,q_1,q_2\},\{0,1\},\delta,q_0,\{q_2\}\rangle M = ⟨{ q 0 , q 1 , q 2 } , { 0 , 1 } , δ , q 0 , { q 2 }⟩ δ ( q 0 , 0 ) = { q 0 , q 1 } \delta(q_0,0)=\{q_0,q_1\} δ ( q 0 , 0 ) = { q 0 , q 1 } δ ( q 0 , 1 ) = { q 0 } \delta(q_0,1)=\{q_0\} δ ( q 0 , 1 ) = { q 0 } δ ( q 1 , 1 ) = { q 2 } \delta(q_1,1)=\{q_2\} δ ( q 1 , 1 ) = { q 2 } δ ( q 2 , 0 ) = { q 2 } \delta(q_2,0)=\{q_2\} δ ( q 2 , 0 ) = { q 2 } δ ( q 2 , 1 ) = { q 2 } \delta(q_2,1)=\{q_2\} δ ( q 2 , 1 ) = { q 2 }
解 用子集构造法。DFA 状态为 NFA 状态集的子集：
DFA 状态 输入 0 输入 1 是否终态 { q 0 } \{q_0\} { q 0 } { q 0 , q 1 } \{q_0,q_1\} { q 0 , q 1 } { q 0 } \{q_0\} { q 0 } 否 { q 0 , q 1 } \{q_0,q_1\} { q 0 , q 1 } { q 0 , q 1 } \{q_0,q_1\} { q 0 , q 1 } { q 0 , q 2 } \{q_0,q_2\} { q 0 , q 2 } 否 { q 0 , q 2 } \{q_0,q_2\} { q 0 , q 2 } { q 0 , q 1 , q 2 } \{q_0,q_1,q_2\} { q 0 , q 1 , q 2 } { q 0 , q 2 } \{q_0,q_2\} { q 0 , q 2 } 是 { q 0 , q 1 , q 2 } \{q_0,q_1,q_2\} { q 0 , q 1 , q 2 } { q 0 , q 1 , q 2 } \{q_0,q_1,q_2\} { q 0 , q 1 , q 2 } { q 0 , q 2 } \{q_0,q_2\} { q 0 , q 2 } 是
DFA 初态 { q 0 } \{q_0\} { q 0 } q 2 q_2 q 2 { q 0 , q 2 } , { q 0 , q 1 , q 2 } \{q_0,q_2\},\{q_0,q_1,q_2\} { q 0 , q 2 } , { q 0 , q 1 , q 2 }
10.2.3 有限自动机与正则文法的等价性 定理 ：对任一右线性正则文法 G G G M M M L ( M ) = L ( G ) L(M)=L(G) L ( M ) = L ( G )
文法到自动机：非终结符对应状态，起始符对应初态，每条产生式 A → a B A\to aB A → a B δ ( A , a ) ∋ B \delta(A,a)\ni B δ ( A , a ) ∋ B A → a A\to a A → a 自动机到文法：状态对应非终结符，转移 δ ( A , a ) = B \delta(A,a)=B δ ( A , a ) = B A → a B A\to aB A → a B A A A A → ε A\to\varepsilon A → ε 10.3 正则表达式 本节为高频必考点，正则表达式与有限自动机的等价转换是考试常出题
正则表达式 （regular expression）是描述正则语言的简洁代数表示。在字母表 Σ \Sigma Σ
∅ \varnothing ∅ ε \varepsilon ε a ∈ Σ a\in\Sigma a ∈ Σ 若 r , s r,s r , s r ∣ s r|s r ∣ s r s rs r s r ∗ r^* r ∗ 括号可改变优先级，优先级：∗ > ^* > ∗ > > ∣ > | > ∣ 每个正则表达式表示一个语言（正则语言），运算含义：
r ∣ s r|s r ∣ s L ( r ) ∪ L ( s ) L(r)\cup L(s) L ( r ) ∪ L ( s ) r s rs r s L ( r ) ⋅ L ( s ) L(r)\cdot L(s) L ( r ) ⋅ L ( s ) L ( r ) L ( s ) = { x y ∣ x ∈ L ( r ) , y ∈ L ( s ) } L(r)L(s)=\{xy\mid x\in L(r),y\in L(s)\} L ( r ) L ( s ) = { x y ∣ x ∈ L ( r ) , y ∈ L ( s )} r ∗ r^* r ∗ L ( r ) ∗ = ⋃ k = 0 ∞ L ( r ) k L(r)^*=\bigcup_{k=0}^\infty L(r)^k L ( r ) ∗ = ⋃ k = 0 ∞ L ( r ) k ε \varepsilon ε r + r^+ r + L ( r ) + = ⋃ k = 1 ∞ L ( r ) k L(r)^+=\bigcup_{k=1}^\infty L(r)^k L ( r ) + = ⋃ k = 1 ∞ L ( r ) k ε \varepsilon ε 例 在 Σ = { 0 , 1 } \Sigma=\{0,1\} Σ = { 0 , 1 }
0*：所有由 0 组成的串（含空串）{ ε , 0 , 00 , 000 , … } \{\varepsilon,0,00,000,\dots\} { ε , 0 , 00 , 000 , … } (0|1)*：所有 0-1 串（Σ ∗ \Sigma^* Σ ∗ 0(0|1)*1：以 0 开头以 1 结尾的任意 0-1 串；(00|11)*：偶数个相同字符组成的串。等价定理 正则表达式、有限自动机与正则文法三者的描述能力等价
易错点 ：r ∗ r^* r ∗ ε \varepsilon ε r + r^+ r + (0|1)* 不是正则表达式——括号和 | 是合法的。但 (ab)* 表示"零个或多个 ab"，不是"零个或多个 a 后跟 b"——连接优先于选择但低于闭包。
例（真题） 写出描述下列语言的正则表达式（Σ = { 0 , 1 } \Sigma=\{0,1\} Σ = { 0 , 1 }
含子串 11 的所有串； 不含 11 的所有串； 以 0 开头以 1 结尾的串。 解 (1) ( 0 ∣ 1 ) ∗ 11 ( 0 ∣ 1 ) ∗ (0|1)^*11(0|1)^* ( 0∣1 ) ∗ 11 ( 0∣1 ) ∗
(2) ( 0 ∣ 10 ) ∗ ( 1 ∣ ε ) (0|10)^*(1|\varepsilon) ( 0∣10 ) ∗ ( 1∣ ε )
(3) 0 ( 0 ∣ 1 ) ∗ 1 0(0|1)^*1 0 ( 0∣1 ) ∗ 1
例（真题） 构造接受语言 L = { w ∈ { 0 , 1 } ∗ ∣ w 中含 01 } L=\{w\in\{0,1\}^*\mid w\text{ 中含 }01\} L = { w ∈ { 0 , 1 } ∗ ∣ w 中含 01 }
解 三状态：q 0 q_0 q 0 q 1 q_1 q 1 q 2 q_2 q 2
δ ( q 0 , 0 ) = q 1 , δ ( q 0 , 1 ) = q 0 \delta(q_0,0)=q_1,\ \delta(q_0,1)=q_0 δ ( q 0 , 0 ) = q 1 , δ ( q 0 , 1 ) = q 0 δ ( q 1 , 0 ) = q 1 , δ ( q 1 , 1 ) = q 2 \delta(q_1,0)=q_1,\ \delta(q_1,1)=q_2 δ ( q 1 , 0 ) = q 1 , δ ( q 1 , 1 ) = q 2 δ ( q 2 , 0 ) = q 2 , δ ( q 2 , 1 ) = q 2 \delta(q_2,0)=q_2,\ \delta(q_2,1)=q_2 δ ( q 2 , 0 ) = q 2 , δ ( q 2 , 1 ) = q 2 10.4 图灵机 本节为重难点，图灵机是可计算性的理论基准，停机问题是不可判定性的核心结果
图灵机（Turing machine, TM）是最强的计算模型，识别所有递归可枚举语言（0 型语言），是可计算性的理论基准。第六版简化了图灵机内容，此处简要介绍。
图灵机 M = ⟨ Q , Σ , Γ , δ , q 0 , B , F ⟩ M=\langle Q,\Sigma,\Gamma,\delta,q_0,B,F\rangle M = ⟨ Q , Σ , Γ , δ , q 0 , B , F ⟩
Q Q Q Σ \Sigma Σ Σ ⊂ Γ \Sigma\subset\Gamma Σ ⊂ Γ B B B Γ \Gamma Γ B B B δ : Q × Γ → Q × Γ × { L , R } \delta:Q\times\Gamma\to Q\times\Gamma\times\{L,R\} δ : Q × Γ → Q × Γ × { L , R } q 0 q_0 q 0 B B B F ⊆ Q F\subseteq Q F ⊆ Q 图灵机有一条无限双向带和一个读写头。每步：读当前格符号，按 δ \delta δ δ \delta δ
Church-Turing 论题 ：任何直觉上"可计算"的函数都能被图灵机计算。图灵机与其他计算模型（递归函数、λ \lambda λ
停机问题 ：不存在一个图灵机能判定任意图灵机 M M M w w w
例（真题） 设计一个图灵机 M M M Σ = { 0 , 1 } \Sigma=\{0,1\} Σ = { 0 , 1 } 0 n 1 n ( n ≥ 1 ) 0^n1^n(n\ge1) 0 n 1 n ( n ≥ 1 )
解 思路：反复将一个 0 改写为 X X X Y Y Y
状态集 Q = { q 0 , q 1 , q 2 , q a c c , q r e j } Q=\{q_0,q_1,q_2,q_{acc},q_{rej}\} Q = { q 0 , q 1 , q 2 , q a cc , q r e j } Γ = { 0 , 1 , X , Y , B } \Gamma=\{0,1,X,Y,B\} Γ = { 0 , 1 , X , Y , B }
q 0 q_0 q 0 X X X q 1 q_1 q 1 Y Y Y q 0 q_0 q 0 B B B q a c c q_{acc} q a cc q 1 q_1 q 1 Y Y Y q 1 q_1 q 1 Y Y Y q 2 q_2 q 2 q 2 q_2 q 2 Y Y Y q 2 q_2 q 2 X X X q 0 q_0 q 0 若 q 0 q_0 q 0 q 0 q_0 q 0 q 1 q_1 q 1 B B B
易错点 ：图灵机的带是无限 的，与有限自动机的有限状态、无存储形成本质区别。DFA/NFA 只能识别正则语言，下推自动机识别上下文无关语言，图灵机识别所有递归可枚举语言——计算能力依次增强。
高频考点速查表 下表汇总全讲义标注的高频考点与重难点，按模块排列，下划线加粗斜体 下划线加粗
数理逻辑 考点 难度 类型 所在章节 等值演算与化简 ★★★ 计算题 1.3 主析取范式/主合取范式 ★★★ 计算题 1.4 推理证明（直接/反证/CP规则） ★★★★ 证明题 1.7 一阶逻辑命题符号化 ★★★ 填空/简答 2.1 前束范式与量词否定转移 ★★★ 计算题 2.3 谓词逻辑推理证明 ★★★★ 证明题 2.4 极小项/极大项下标约定 ★★★ 易错 1.4 蕴涵联结词真值（前件假则真） ★★ 易错 1.1
集合论 考点 难度 类型 所在章节 容斥原理应用 ★★★ 计算题 3.3 关系五条性质判断 ★★★ 判断/选择 4.3 求自反/对称/传递闭包 ★★★ 计算题 4.4 等价关系证明与划分 ★★★★ 证明题 4.5 哈斯图与特殊元素 ★★★ 计算题 4.5 对称与反对称可共存 ★★★ 易错 4.3 Warshall 算法求传递闭包 ★★★ 重难点 4.4
图论 考点 难度 类型 所在章节 握手定理应用 ★★ 计算题 5.1 邻接矩阵 A k A^k A k ★★★ 计算题 5.3 Dijkstra 最短路径 ★★★ 计算题 5.4 关键路径（AOE 网） ★★★ 计算题 5.4 二部图判定（无奇圈） ★★★ 判断题 6.1 欧拉图判定 ★★ 填空/选择 6.2 欧拉公式 v − e + f = 2 v-e+f=2 v − e + f = 2 ★★★ 计算题 6.4 平面图判定 ★★★ 计算题 6.4 最小生成树（Kruskal/Prim） ★★★ 计算题 7.1 二叉树遍历与重建 ★★★ 计算题 7.2 哈夫曼树/前缀码 ★★★ 计算题 7.2 哈密顿图充分/必要条件方向 ★★★★ 重难点 6.3 Kuratowski 定理（K 5 K_5 K 5 K 3 , 3 K_{3,3} K 3 , 3 ★★★ 重难点 6.4 Cayley 公式 n n − 2 n^{n-2} n n − 2 ★★ 重难点 7.1
组合分析初步 考点 难度 类型 所在章节 排列组合计数与隔板法 ★★★ 计算题 8.2 特征方程法解递推方程 ★★★ 计算题 8.3 错排公式 D n D_n D n ★★★ 拓展 8.4 重根通解需乘 n n n ★★★ 易错 8.3
代数结构 考点 难度 类型 所在章节 群的判定与运算表分析 ★★★ 计算题 9.3 循环群的判定与生成元 ★★★ 计算题 9.3 同态映射的判断 ★★★ 计算题 9.3 Lagrange 定理（∣ H ∣ ∣ ∣ G ∣ |H| \mid |G| ∣ H ∣ ∣ ∣ G ∣ ★★★ 重难点 9.3 同态基本定理（G / ker φ ≅ im φ G/\ker\varphi\cong\text{im}\varphi G / ker φ ≅ im φ ★★★★ 重难点 9.3 群中消去律 vs 环乘法消去律 ★★★ 易错 9.3
形式语言与自动机初步 考点 难度 类型 所在章节 NFA 与 DFA 等价性转换 ★★★ 计算题 10.2.2 正则表达式与自动机等价 ★★★ 计算题 10.3 Chomsky 四类文法分类 ★★★ 重难点 10.1.2 二义文法判定 ★★★ 重难点 10.1.5 图灵机与停机问题 ★★★ 重难点 10.4
结语与学习建议 离散数学六大模块环环相扣：数理逻辑提供推理语言，集合论是结构基础，关系与函数把集合论推向图论与代数，图论与组合分析处理结构与计数，代数结构抽象运算规律，形式语言与自动机将前三者综合应用于计算理论。学习时建议把握三条主线：
定义要精确 ——离散数学的概念区分极其细腻（自反 vs 反自反、对称 vs 反对称、欧拉 vs 哈密顿、正则 vs 上下文无关），一字之差全盘不同，做题前先把概念抠准。定理要会用方向 ——很多定理是"充分不必要"（Dirac、Ore）或"必要不充分"（哈密顿删点条件），分清方向才能判断能否下结论。文法四类的包含关系也要记清方向。方法要成体系 ——逻辑的等值演算与范式、关系的闭包与等价/偏序、图的矩阵表示与算法、组合的递推与计数、代数的同态与同构、语言的文法与自动机，都要练到"看见题型就知道用哪套工具"。每学完一章，用真值表、关系矩阵、哈斯图、邻接矩阵、语法分析树这几样"手工工具"各跑一个例题，比单纯背诵有效得多。祝学习顺利。
