简介：这份《离散数学（西电第三版）》教材答案是面向计算机科学与信息技术专业学生、考研复习者及授课教师的配套习题解答材料，主要用于对照教材各章练习、核查解题思路并辅助考前复盘。包内仅含1个PDF文件，整体约9.26MB，按教材章节组织内容，涵盖集合论、关系与函数、图论、组合数学、数理逻辑等核心模块，可与书中定义、定理、证明和例题配合使用。读者可借助答案逐题核对集合运算、关系性质、图论模型、排列组合与命题/谓词逻辑等典型题型的推导过程，定位薄弱知识点，形成较完整的复习脉络；单文件形式也方便在电脑、平板或打印后查阅。目前已有403人学习，适合需要课后同步练习、期末梳理或考研基础阶段查漏补缺的读者参考。
1. 先把地图铺开：离散数学到底在考什么
离散数学这门课最容易踩的坑在于，它和高等数学那种“把式子算出来就行”的路子完全不是一回事。五块内容各说各的语言：集合论讲属于与包含，关系和函数讲对应与封闭，图论讲点边结构与判定，组合数学讲数得清不清，数理逻辑讲推得动不动。很多人抱着离散数学第三版的教材答案从第一题抄到最后一题，分数还是上不去，原因是把答案当成了终点，而不是当成校验自己推理链的工具。这份答案覆盖集合论、关系与函数、图论、组合数学、数理逻辑五章，定义、定理、证明、例题与课后习题配套完整，适合两类人：正在系统学、需要一份可对照推理过程的人；以及期末或考研复习、想快速定位自己哪一步推错的人。下面按模块拆开讲，最后收在一份能直接执行的复习清单上。
2. 集合论与关系函数：从定义复写到闭包计算
这一章是后面所有内容的地基。关系本质上是笛卡尔积的子集，函数又是特殊的二元关系，三块共用同一套符号系统。教材答案在这一部分题量最密，原因很实际：定义题、证明题、计算题三种题型都在这里起步，符号写错一个下标，后面图论和逻辑的题会跟着错。复习顺序建议先钉死运算规则，再攻关系性质，最后用函数把“对应”这件事收口。
2.1 集合运算与计数公式：符号规则先钉死
集合运算本身不难，难在符号混用和计数公式记串。交、并、差、补、对称差这几个运算，配合幂集和笛卡尔积，能衍生出大量小题。最容易出问题的是补集：没有明确全集，补集无从谈起；以及对称差，它和“并减交”是同一个东西，只是写法不同。
| 运算 | 符号 | 定义 | 常见误用 |
|---|---|---|---|
| 并 | A∪B | 属于 A 或属于 B | 与对称差混写 |
| 交 | A∩B | 同时属于 A 和 B | 空交集当成空集 |
| 差 | A−B | 属于 A 且不属于 B | 以为满足交换律 |
| 补 | ~A 或 A′ | 全集 U 中不属于 A 的元素 | 忘记先声明全集 |
| 对称差 | A⊕B | (A−B)∪(B−A) | 与并集混为一谈 |
| 幂集 | P(A) | A 的所有子集构成的集合 | 元素个数记成 n 而不是 2^n |
| 笛卡尔积 | A×B | 所有有序对 (a,b) | 元素个数记成加法 |
对应的计数结论要背到条件反射：|P(A)| = 2^|A|，|A×B| = |A|·|B|，n 元集合的子集总数是 2^n，真子集是 2^n − 1，非空真子集再减一。容斥原理的加减交替规律也在这里定型：两个集合相加要减一次交集，三个集合相加要减三次两两交集再加回一次三重交集。
A = {1, 2, 3} B = {2, 3, 4} U = set(range(1, 6)) # 补集必须先有全集 print(A | B, A & B, A - B, U - A) # 并、交、差、补 def power_set(s): res = [set()] for x in s: res += [t | {x} for t in res] # 每加一个元素，子集数翻倍 return res print(len(power_set(A))) # 8，验证 2^3 C = {3, 5} left = len(A | B | C) right = (len(A) + len(B) + len(C) - len(A & B) - len(A & C) - len(B & C) + len(A & B & C)) # 三集合容斥，加回三重交集 print(left == right)这段代码的用途是拿小题验证公式，不是拿来算大题。power_set 里的列表推导会先算出快照再拼接，所以不会出现边遍历边扩容的死循环；时间复杂度是 O(2^n)，n 超过二十就会卡住，这也是为什么考试里幂集题只考计数不考枚举。容斥那段把三项减、一项加的符号顺序写死，做题时照着套，能避免“减了交集忘了加回三重交集”的低级失误。
2.2 二元关系：五个性质与三种闭包
关系部分的复习重点不是背定义，而是把定义、关系矩阵、关系图这三种表示绑在一起看。同一个性质，用逻辑式写、用矩阵看、用图看，判断速度差很多。尤其是考试时间紧的时候，画矩阵比逐对检查快得多。
| 性质 | 形式化定义 | 关系矩阵特征 | 关系图特征 |
|---|---|---|---|
| 自反 | 对任意 x，(x,x)∈R | 主对角线全为 1 | 每个点都有自环 |
| 反自反 | 对任意 x，(x,x)∉R | 主对角线全为 0 | 没有任何自环 |
| 对称 | (x,y)∈R 则 (y,x)∈R | 矩阵关于主对角线对称 | 边成对出现 |
| 反对称 | (x,y) 与 (y,x) 同属 R 则 x=y | 对称位置不同时为 1 | 没有双向边 |
| 传递 | (x,y)、(y,z)∈R 则 (x,z)∈R | R² ⊆ R | 有长度 2 的路必有直达边 |
三种闭包的公式要记牢：自反闭包 r(R) = R ∪ I_A，其中 I_A 是恒等关系；对称闭包 s(R) = R ∪ R⁻¹；传递闭包 t(R) = R ∪ R² ∪ … ∪ Rⁿ，n 是集合元素个数。这里最容易翻车的是传递闭包只算到 R² 就收手，实际上要一直并到 Rⁿ 才稳定。手算小题可以逐次平方法，编程或大矩阵直接用 Warshall。
def warshall(M): n = len(M) R = [row[:] for row in M] # 复制一份，别污染原矩阵 for k in range(n): # k 表示允许经过的中转点 for i in range(n): if R[i][k]: for j in range(n): R[i][j] = R[i][j] or (R[i][k] and R[k][j]) return R M = [[True, True, False], [False, True, True], [False, False, True]] print(warshall(M))参数说明：M 是布尔邻接矩阵，R[i][j] 为真表示从 i 到 j 存在有向边；外层 k 是“当前允许使用的中转点编号”，第 k 轮结束后 R[i][j] 表示只经过编号不超过 k 的点能否从 i 走到 j。三层循环结束，矩阵就是传递闭包。时间复杂度 O(n³)，空间 O(n²)；复制矩阵这一步看着不起眼，但省掉它，很多人在调试时会发现原始矩阵被改得面目全非，这是血泪经验。
关系和函数这一块还有两组对比必须分清：等价关系是自反、对称、传递，它把集合切成一堆互不相交的等价类，这些等价类合起来就是原集合，这叫划分；偏序关系是自反、反对称、传递，它刻画的是“层次”和“先后”，画成哈斯图时要去掉自环、去掉由传递性导出的冗余边、把大的元素放上层。
| 对比项 | 等价关系 | 偏序关系 |
|---|---|---|
| 三条性质 | 自反、对称、传递 | 自反、反对称、传递 |
| 典型例子 | 模 n 同余、同一班级 | 整除关系、集合包含 |
| 图形表示 | 等价类划分 | 哈斯图 |
| 核心结论 | 等价类互不相交，并为全集 | 可求极大元、最大元、上确界 |
| 常见题型 | 求等价类、商集 | 画哈斯图、找极值元 |
2.3 函数：单射、满射、双射的判定链
函数是“每个 x 恰好对应一个 y”的二元关系，这句话里两个限定词都是考点：每个，说明定义域不能有遗漏；恰好一个，说明不能一对多。单射要求不同的 x 对应不同的 y；满射要求值域吃满整个陪域；双射是两者兼备。
有限集上有一条极好用的判定链：当 |A| = |B| 时，单射、满射、双射三者等价，证出一个就能推出另外两个；当 |A| > |B| 时，单射不可能成立；当 |A| < |B| 时，满射不可能成立。计数公式也要顺手记住：从 m 元集到 n 元集的函数总数是 n^m，单射数是 P(n,m)，当 m = n 时双射数是 m!。
复合运算的顺序是另一个高频错误点。g∘f 的意思是先做 f 再做 g，写证明时要按这个顺序展开。双射的复合仍是双射，双射才有逆函数，逆函数的逆是它自己。教材答案在函数这一节的例题通常会给一个具体映射让判断类型，看答案时别只看结论，要看它怎么用反例排除——排除法比正面证明快。
2.4 证明题的结构：答案册里最值得学的东西
这一章真正值得反复看的是证明结构，而不是结果。集合相等用双包含：先证左边包含于右边，再证右边包含于左边；关系性质用定义展开：把自反、对称、传递的量化语句原样写出来，再逐条对照；等价关系先证三条性质，再用等价类收尾；偏序题先画哈斯图，再在图上找极大元与最大元，避免在关系式里绕圈。
一个常被忽略的细节是反例的写法。判断题里说“性质不成立”，光写“不成立”拿不到分，要给出具体的集合、具体的关系、具体的元素。答案册里每个反例都值得抄一遍，因为考场上临时编反例很费时间，平时积累几个标准反例，比如“整除关系是偏序不是等价”“模 n 同余是等价不是偏序”，直接套用。
3. 图论三条主线：度、连通与欧拉哈密顿判定
图论看起来图形多、画得乱，其实考点集中在三条线上：度的算账、连通与树的结构、特殊图的判定。教材答案在这一章的证明题比例明显上升，因为图论的结论大多需要构造或反证。复习策略是先把握手定理用熟，再把各类特殊图的判定条件做成对照表，最后专门练“判断是不是”这类小题，速度提上来。
3.1 度的账本：握手定理与度序列
握手定理是整个图论的算术基础：所有顶点的度数之和等于边数的两倍。它有个立刻能用的推论——奇度顶点的个数一定是偶数。这个推论在判断题里出现的频率极高，比如“是否存在度序列为 3,3,3,3,3 的图”，五个奇数，直接否定，不用画图。
度序列能不能构成简单图，除了握手定理还要看最大值约束：n 个顶点的简单图，每个顶点度数不超过 n−1；度序列排序后，最大度不能超过剩余顶点数。更系统的判定是 Havel-Hakimi 过程：每次取最大度 d，把它后面的 d 个度各减一，删掉这个最大度，重排，重复，直到出现负数则不可图化，全部消完则可行。手算时这套流程比画图试错稳。
有向图里度数分成入度和出度，握手定理的对应形式是所有入度之和等于所有出度之和等于边数。这个对称性在判断题里常被拿来设陷阱，比如给一组入度出度不全相等的序列，问能不能构成有向图，直接看总和是否相等即可。
3.2 连通、树与生成树
连通性这块的核心概念是连通分支、割点、桥。割点是删掉之后连通分支数增加的顶点，桥是删掉之后分支数增加的边。判断割点最直观的办法是逐个删掉再数分支，小题够用；大题会用 DFS 的低位值算法，教材答案里通常给出完整的回溯过程，看的时候重点看“根节点要单独处理”这个分支。
树的等价定义要背成一组：n 个顶点的无向图，下面几条等价——连通且无回路、连通且恰有 n−1 条边、无回路且恰有 n−1 条边、任意两点之间有唯一路径、无回路但加任意一条边就成回路。考试喜欢给其中一条让你推其余几条，答案册里的标准写法是用反证，比如“若有两个不同路径则构成回路”。
生成树是所有连通图都有的结构，最小生成树的两种经典算法各有适用场景：Kruskal 按边权排序，用并查集判环，适合稀疏图；Prim 从一个点出发不断扩展，适合稠密图。这两种算法的步骤在答案册里通常写得很细，复习时不要只记名字，要能手写出每一步选中的边，尤其是 Kruskal 里“加入会成环就跳过”这个判断。
3.3 欧拉、哈密顿与平面图：三组判定的边界
这三类图最容易被混为一谈，因为名字都带人名，条件都涉及“经过所有顶点或边”。实际上它们的判定难度完全不同：欧拉图有充要条件，哈密顿图只有充分条件和必要条件，平面图靠公式和结构排除。
| 类型 | 判定条件 | 性质 | 常见误区 |
|---|---|---|---|
| 欧拉回路 | 连通且所有顶点度数为偶数 | 一笔画回到起点 | 把“连通”漏掉 |
| 欧拉通路 | 恰有 0 个或 2 个奇度顶点 | 两个奇点分别是起点和终点 | 奇点数为 4 也认为可画 |
| 哈密顿回路 | 无简单充要条件，Dirac 条件为每个顶点度数 ≥ n/2 | 经过每个顶点恰好一次 | 把充分条件当充要条件 |
| 平面图 | 连通时满足 n − m + r = 2 | 简单连通且 n ≥ 3 时 m ≤ 3n − 6 | 忘记外部面也算一个面 |
| 二部图 | 不含奇数长度的回路 | 可二着色 | 有偶回路就误判为二部图 |
欧拉图的判定几乎每次必考，记住“0 个或 2 个奇点”这一条就能覆盖大部分小题。哈密顿图要老实承认没有简单充要条件，Dirac 定理只能用来判定“是”，不能用来判定“不是”；要否定哈密顿性，通常靠割点论证——删掉 k 个顶点后连通分支数大于 k，则一定不是哈密顿图。
平面图的欧拉公式 n − m + r = 2 里，r 是面数，包含最外面那个无界面，这一点漏掉就全错。由它推出的边数上界 m ≤ 3n − 6 是证明 K5 非平面的利器；K3,3 则要用二部图的边数上界 m ≤ 2n − 4 来卡。这两个经典反例在答案册里几乎都有完整证明，值得抄一遍。
4. 组合与逻辑：计数模型和推理形式的对照梳理
这一章的两个模块看起来毫不相干，其实共用一种思维：把复杂对象翻译成标准形式再处理。组合数学把“数不清”翻译成排列、组合、递推、生成函数四类模型；数理逻辑把“推不动”翻译成真值表、范式、推理规则三件工具。教材答案在这一章的步骤感最强，每一步都能对应到一个模型或一条规则。
4.1 排列组合：先分类再计数
计数题的失分大多不是公式记错，而是分类标准没定好，导致重复算或漏算。做题前先问三个问题：元素能不能重复？顺序算不算不同？是恰好还是至少。这三问定下来，公式基本就唯一了。
| 模型 | 公式 | 典型场景 |
|---|---|---|
| 无重排列 | P(n,r) = n!/(n−r)! | 从 n 人中选 r 人排队 |
| 无重组合 | C(n,r) = n!/(r!(n−r)!) | 从 n 人中选 r 人成组 |
| 可重排列 | n^r | r 位密码，每位 n 种选择 |
| 可重组合 | C(n+r−1, r) | 把 r 个相同球放进 n 个盒子 |
| 圆排列 | (n−1)! | n 人围桌而坐，旋转视为相同 |
| 错排 | D(n) = n!(1 − 1/1! + 1/2! − … + (−1)ⁿ/n!) | 全不带自己标签的排列 |
“至少一个”这类题的标准做法是补集：总数减去一个都没有的情况，比直接分类加和稳得多。容斥在这里再次出场，比如“1 到 100 中能被 2 或 3 整除的数”，直接相加会把 6 的倍数算两遍，必须减掉。鸽巢原理的题则要先想清楚“盒子”和“物品”分别是什么，很多题的难点就在这个对应关系上，找对了盒子，结论一句话就出来。
4.2 递推与生成函数：把第 n 项降维
递推的核心是把“第 n 项”写成前面若干项的表达式，再用初值往前推。汉诺塔是 2h(n−1) + 1，斐波那契是前两项之和，卡特兰数描述的是括号匹配、二叉树形态这类结构计数。一阶线性递推可以用特征方程求通项，k 阶同理；不方便求通项时，生成函数是另一条路，把数列当成幂级数的系数，用代数变形求出闭式。
from functools import lru_cache @lru_cache(maxsize=None) def hanoi(n): # h(1)=1，h(n)=2h(n-1)+1，闭式解为 2^n - 1 return 1 if n == 1 else 2 * hanoi(n - 1) + 1 print([hanoi(i) for i in range(1, 6)]) # [1, 3, 7, 15, 31]参数说明：n 是圆盘个数，返回值是最少移动次数；lru_cache 负责记忆化，把指数级递归压成线性。这段代码的价值在于对照：手推递推式得到 2^n − 1，程序跑出的序列完全吻合，说明递推式没写错。考试时用递推式求前几项，再用闭式解验证，是自查的固定动作。生成函数的题则要熟记几个基本展开：1/(1−x) 对应全 1 数列，1/(1−x)² 对应自然数数列，这些在答案册的例题里会反复出现。
4.3 命题逻辑：真值表、范式与推理规则
命题逻辑的题分三层：第一层是求真值表，第二层是化主范式，第三层是证明推理有效。真值表是笨办法但最可靠，n 个变元列 2ⁿ 行，考试里变元一般不超过三个，手工列完全可行。
等值演算要背的公式不多，但必须熟：德摩根律、蕴含等值式（p→q 等价于 ¬p∨q）、双重否定、分配律、吸收律、假言易位。主析取范式对应极小项的析取，主合取范式对应极大项的合取，编号按二进制读，变量取真记 1、取假记 0，这个规则写错一位，整道题的分就没了。
| 推理规则 | 形式 | 用途 |
|---|---|---|
| 假言推理 | p→q，p，所以 q | 最常见的正向推导 |
| 拒取式 | p→q，¬q，所以 ¬p | 反向否定 |
| 假言三段论 | p→q，q→r，所以 p→r | 链条传递 |
| 析取三段论 | p∨q，¬p，所以 q | 排除一支 |
| 附加律 | p，所以 p∨q | 引入析取 |
| 化简律 | p∧q，所以 p | 拆开合取 |
from itertools import product def implies(p, q): return (not p) or q # 假言三段论的链式形式：((p→q) ∧ (q→r)) → (p→r) expr = lambda p, q, r: implies(implies(p, q) and implies(q, r), implies(p, r)) print(all(expr(*vals) for vals in product([False, True], repeat=3)))这段代码枚举三个变元的全部 8 种赋值，返回 True 说明该式是重言式。参数说明：product 的 repeat=3 表示三个变元，每个取真假两种值；all 对全部结果取合取。写代码验证的好处是，手算真值表容易在某一行漏写，程序能兜底。类似的模板可以套用到任何等值式的验证上，改一下 expr 就行。
4.4 谓词逻辑：量词、辖域与否定
谓词逻辑比命题逻辑多出两样东西：个体域和量词。考试重点集中在三处：量词否定的写法、量词顺序的差别、自由变元与约束变元的区分。
量词否定律很干脆：¬∀xP(x) 等价于 ∃x¬P(x)，¬∃xP(x) 等价于 ∀x¬P(x)。否定往内推，量词翻转，谓词取反，三步不能少。量词顺序的经典例子是：在整数域上，∀x∃y(x+y=0) 为真，因为对每个 x 都能找到对应的 y；而 ∃y∀x(x+y=0) 为假，因为不存在一个固定的 y 能对所有 x 成立。前者弱、后者强，顺序一换，真假就变。
| 公式 | 含义 | 在整数域上的真假 |
|---|---|---|
| ∀x∃y(x+y=0) | 每个 x 都有对应的 y | 真 |
| ∃y∀x(x+y=0) | 存在一个 y 对全部 x 成立 | 假 |
| ∀x∀y(x+y=y+x) | 加法交换律 | 真 |
| ∃x∀y(x·y=y) | 存在乘法单位元 | 真，x=1 |
辖域题要看清量词管到哪里，括号是唯一依据。换名规则用于避免同名冲突，代入规则要在自由变元上做，这两条在答案册的证明题里经常作为隐含步骤出现，看答案时要专门留意它在哪里换了名。
5. 五个高频易错点：概念、闭包、计数、量词与图判定
复习到这个阶段，很多错误已经不是“不会”，而是“会但写错”。下面这五处是练题时反复冒头的，按“易漏点、为什么漏、怎么补”的顺序整理，建议对着自己的错题本逐条核。
5.1 概念层的三个混淆
易漏点一：幂集的元素是集合，不是元素。为什么漏：平时写集合习惯列举元素，一遇到 P(A) 就下意识把 A 的元素直接搬进去。怎么补：记住 P(A) 的元素个数是 2^|A|，里面每一项本身都是集合，空集和 A 本身都是 P(A) 的元素；写答案时强制给每个元素加一层花括号。
易漏点二：空关系和全域关系的性质判定。为什么漏：平时练的都是有具体元素的关系，空关系这种极端情况被当成“没有意义”跳过。怎么补：单独记一组结论——空关系是反自反的、对称的、反对称的、传递的，但不是自反的（除非集合本身为空）；全域关系是自反、对称、传递的，但不是反对称的（除非集合只有一个元素）。这种边界情况判断题几乎每年都出。
易漏点三：反对称不等于“没有对称”。为什么漏：中文里“反对称”听起来像“对称的反面”，实际定义是“双向都存在则两端相等”，它允许自环，也允许单向边。怎么补：用哈斯图对照，偏序关系里可以有 a 小于 b 的边，但不允许 a 到 b 和 b 到 a 同时存在；写判定时回到形式化定义，不要靠语感。
5.2 计算与证明层的两处翻车
易漏点四：传递闭包只算到 R²。为什么漏：R² 已经能覆盖大部分长度 2 的路径，看起来“差不多了”。怎么补：闭包要并到 Rⁿ，n 是元素个数，因为最长简单路径不超过 n−1 条边；手算时用 Warshall 表格式推进，或者用逐次平方法算到矩阵不再变化为止，判断标准是“这一轮和上一轮完全相同”。
易漏点五：计数题里“至少”直接相加。为什么漏：分类讨论时下意识把几种情况的结果加起来，忘了它们之间有重叠。怎么补：见到“至少”“至多”“或”，先想补集和容斥；把每一类的交集单独列出来，确认没有重复计数再相加。同理，量词否定题里只否定谓词不换量词，也是同一类毛病——规则只执行了一半。
还有一处和图论绑定的注意点：欧拉图的判定必须同时满足“连通”和“奇度顶点数为 0 或 2”，很多人只看了度数就下结论，遇到不连通的图直接翻车。补法是判定前先画一遍连通分支，分支数大于 1 就直接否掉。
6. 复习清单：按模块自查的三轮推进法
复习到最后阶段，最怕的是“感觉都看过，一做题就卡”。下面这张表按五个模块列出自查项，每一项都对应一个可验证的动作，不是“再看看书”这种虚话。
| 模块 | 必须能默写的内容 | 高频题型 | 自查标准 |
|---|---|---|---|
| 集合论 | 幂集与笛卡尔积的计数、容斥公式 | 运算化简、子集计数 | 能不查书画出三集合容斥的符号 |
| 关系与函数 | 五个性质的形式化定义、三种闭包公式 | 性质判定、求等价类、画哈斯图 | 给一个关系能在两分钟内判定全部性质 |
| 图论 | 握手定理、树的三条等价定义、欧拉判定 | 度序列判定、生成树、平面图证明 | 能独立写出 K5 非平面的完整证明 |
| 组合数学 | 六类计数模型、汉诺塔与斐波那契递推 | 排列组合应用题、递推求解 | 见到“至少”能条件反射想补集 |
| 数理逻辑 | 量词否定律、主范式编号规则、六条推理规则 | 求真值表、化范式、证明推理有效 | 能口述 ∀x∃y 与 ∃y∀x 的区别并举例 |
三轮推进的具体安排是这样：第一轮只过定义和反例，合上答案册，把每章的概念用自己的话写一遍，写不出来的地方做记号，这一轮不碰大题；第二轮闭卷重做课后题，只写关键步骤和结论，不写完整过程，写完再对照答案册，重点看自己的步骤和标准答案差在哪一步，是定义没用对还是漏了条件；第三轮只做错题，把错误按“概念错、计算错、表述错”三类归档，概念错回第一轮补，计算错限时重做，表述错抄一遍标准写法。
资料的使用方式上有个顺序问题值得说清楚：先做题，再对答案，最后抄结构。反过来做，抄得再工整也只是把别人的推理过一遍手，考场上还是写不出。这份按五章整理、与课后习题逐题对应的答案册，最大的价值是让你在卡住的时候看到“标准推理长什么样”，而不是替你完成推理。
从那以后我每次复习离散数学，都会先把答案册合上，把证明的关键一步写在自己的草稿纸上，再去对照答案，看差的是定义展开还是反例构造。这个习惯让我的错题本从“抄题”变成了“记差异”，效率完全不一样。希望帮到你。
本文还有配套的精品资源，点击获取
