离散数学 · 核心章节
离散数学 · 核心章节
计算机科学的基础数学：逻辑 → 集合 → 关系/函数 → 图论 → 代数系统 → 组合计数。
1. 数理逻辑
命题逻辑
| 联结词 | 记号 | 读法 |
|---|---|---|
| 否定 | ¬p | 非 p |
| 合取 | p∧q | p 且 q |
| 析取 | p∨q | p 或 q |
| 蕴含 | p→q | 若 p 则 q |
| 等价 | p↔q | p 当且仅当 q |
注意：p→q 只有 p 真 q 假 时为假；p→q ≡ ¬p∨q。
等值式（常用）
双重否定：¬¬p ≡ p
德摩根：¬(p∧q) ≡ ¬p∨¬q；¬(p∨q) ≡ ¬p∧¬q
吸收律：p∨(p∧q) ≡ p
蕴涵等值式：p→q ≡ ¬p∨q推理规则
假言推理（MP）：p→q，p ⇒ q
拒取式（MT）：p→q，¬q ⇒ ¬p
析取三段论：p∨q，¬p ⇒ q
假言三段论：p→q，q→r ⇒ p→r谓词逻辑
∀x P(x)：全称量词；∃x P(x)：存在量词
¬∀x P(x) ≡ ∃x ¬P(x)；¬∃x P(x) ≡ ∀x ¬P(x)2. 集合论
运算
并 A∪B；交 A∩B；差 A−B；补 ∁A
对称差 A⊕B = (A−B)∪(B−A)恒等式
德摩根：∁(A∩B) = ∁A∪∁B；∁(A∪B) = ∁A∩∁B
A∪(B∩C) = (A∪B)∩(A∪C)（分配律）基数
|A∪B| = |A|+|B|−|A∩B|
|A∪B∪C| = |A|+|B|+|C|−|A∩B|−|A∩C|−|B∩C|+|A∩B∩C|（容斥）3. 关系
二元关系性质
| 性质 | 定义 |
|---|---|
| 自反 | 所有 x，(x,x)∈R |
| 反自反 | 所有 x，(x,x)∉R |
| 对称 | (x,y)∈R ⇒ (y,x)∈R |
| 反对称 | (x,y)∈R 且 (y,x)∈R ⇒ x=y |
| 传递 | (x,y),(y,z)∈R ⇒ (x,z)∈R |
等价关系与划分
自反 + 对称 + 传递 = 等价关系
等价类 [x] = {y | xRy}；等价类集合构成集合的划分偏序关系
自反 + 反对称 + 传递 = 偏序（≤）
哈斯图（Hasse 图）画法：去掉自反环与传递边
极大/极小元、最大/最小元、上/下界、上/下确界关系闭包
自反闭包 r(R) = R ∪ E
对称闭包 s(R) = R ∪ R⁻¹
传递闭包 t(R) = R ∪ R² ∪ R³ ∪ …（Warshall 算法）4. 函数
f: A → B
单射（一一）：不同自变量 → 不同函数值
满射（到上）：值域 = B
双射：既单又满鸽巢原理：n+1 个物体放入 n 个盒子，至少一个盒子 ≥ 2 个。
5. 图论
基本概念
G = (V, E)；无向图 / 有向图
握手定理：Σdeg(v) = 2|E|（无向）
有向图：Σdeg⁺ = Σdeg⁻ = |E|特殊图
| 图 | 判定 |
|---|---|
| 完全图 Kₙ | n(n−1)/2 条边 |
| 二部图 | 顶点可二分，边只跨部（无奇圈） |
| 欧拉图 | 所有顶点度数为偶（有向：出入相等） |
| 哈密顿图 | 必要条件（割点/度条件），充分条件 Dirac：deg ≥ n/2 |
树
n 个顶点的树：n−1 条边，连通无圈
生成树：连通图包含全部顶点的树
最小生成树：Prim（加点）/ Kruskal（加边，并查集判环）平面图
欧拉公式：V − E + F = 2（连通平面图）
K₅ 与 K₃,₃ 是非平面图图着色
四色定理：平面图 4 色足够
图着色 = 相邻顶点不同色，最少色数 χ(G)6. 代数系统
| 系统 | 公理 | 例子 |
|---|---|---|
| 半群 | 封闭 + 结合 | (N,+) |
| 独异点 | 半群 + 单位元 | (N,·) |
| 群 | 独异点 + 逆元 | (Z,+)、(Zₙ,+) |
| 阿贝尔群 | 群 + 交换 | (Z,+) |
| 环 | (R,+) 阿贝尔群 + 乘法结合/分配 | (Z,+,·) |
| 域 | 环 + 乘法可逆（除零外） | (R,+,·)、(Zₚ,+,·) p 素数 |
拉格朗日定理：有限群中子群的阶整除群的阶。
7. 组合计数
排列与组合
P(n,r) = n!/(n−r)!
C(n,r) = n!/[r!(n−r)!]常用恒等式
C(n,r) = C(n, n−r)
C(n+1,r) = C(n,r) + C(n,r−1)（帕斯卡）
Σ C(n,k) = 2ⁿ计数技巧
- 隔板法：
n个相同物分k组非空：C(n−1, k−1)； - 错排数：
Dₙ = n!·Σ(−1)^k/k!，如D₃=2, D₄=9； - 生成函数 / 母函数处理受限组合。
8. 考研 / 机试常考题型
- 命题公式等值演算与主范式；
- 关系性质判断、等价类与划分；
- 哈斯图与偏序元；
- 图论：握手定理、欧拉/哈密顿判定、着色；
- 最小生成树（Prim/Kruskal）与最短路（Dijkstra/Floyd）；
- 群判定与子群；
- 排列组合与容斥、错排。
例题速览
例 1：证明 (p→q) ∧ p ⇒ q（假言推理）：
p→q ≡ ¬p∨q；(¬p∨q)∧p ≡ q∧p ⇒ q例 2：K₅ 的边数：
5·4/2 = 10例 3：4 封信全装错信封的方法数：
D₄ = 4!·(1 − 1 + 1/2 − 1/6 + 1/24) = 99. 易错点清单
- 蕴含联结词
→与日常“因果“含义不同； - 自反/反自反、对称/反对称不互斥；
- 握手定理两边都算；
- 欧拉图关注“一笔画“，哈密顿关注“回路遍历所有顶点“；
- 群必须封闭、结合、有单位元、有逆元四条件齐备；
- 错排与隔板法别套错模型。
上一篇：概率论