简介：这份《离散数学（西电第三版）》教材答案资料，面向高校计算机、信息技术及相关专业学生，尤其适合正在学习集合论、关系与函数、图论、组合数学、数理逻辑等章节，需要课后核对答案、梳理证明思路与复习考点的读者。压缩包内共1个PDF文件，大小约9.26MB，内容围绕教材课后习题展开，可按章节对照定义、定理和例题复盘解题过程，帮助定位概念盲区、理解推导步骤，并用于作业检查、章节知识框架整理与考前查漏补缺。预览页可见“课后答案网”水印，使用前建议先核对教材版本、章节编号与习题顺序是否匹配。目前已有403人学习下载，文件轻便、查阅直接，适合作为课堂之外的辅助参考，对课程期末复习与研究生入学考试复习也有一定帮助，但不宜替代教材原文和独立推导。

1. 知识地图：五块积木和彼此的衔接

离散数学第三版把内容切成五块：数理逻辑、集合论、关系与函数、图论、组合数学。这五块之间是承接关系，并非并列关系：逻辑给出证明的语言，集合论给出讨论的对象，关系是集合上的结构，图是关系的图形化，组合数学则在前几块之上做计数。很多人复习时按章节线性推进，学完图论，回头连集合恒等式怎么证都忘了；问题就出在没有记住它们之间的衔接处——证明题的落点在逻辑与集合，结构题的落点在关系与图，带「多少种」的题落点在计数。配套的教材答案是这套地图的校验层，它给结果不给思路，所以对答案的姿势决定它是拐杖还是尺子。这份梳理适合已经把教材过了一遍、准备期末或考研复试前系统回炉的人。

2. 逻辑与集合：从联结词真值表到恒等式的证明套路

数理逻辑和集合论在教材里分成两章，考卷上却常常合成一道大题：先用逻辑符号翻译一段陈述，再用集合语言改写，最后证一个恒等式。这两块共用的底层是布尔运算，联结词 ∧∨¬ 与集合运算 ∩∪~ 一一对应，把这张对应关系记住，很多题本质上只是符号替换。重点不在背定义，而在两件事：命题符号化时量词和联结词的次序不写错，集合恒等式证明时知道该用元素法还是代数法。配套答案里这两类题通常只写结论或跳步，跳掉的部分恰恰最容易在考场上卡住。

2.1 命题符号化：量词顺序决定真值

五个联结词里真正容易出错的是蕴含。p→q 只在 p 真 q 假时为假，于是「若 2 是奇数则雪是白的」是真命题，判断重言式时这一点经常被直觉带偏。记忆方式：蕴含是「不许前件真、后件假」的承诺，前件为假时承诺自动兑现。

量词嵌套是第二个容易出错的地方。∀x∃y(y>x) 与 ∃y∀x(y>x) 看着只换了顺序，真值可能相反：前者在整数域为真（取 y=x+1），后者为假（不存在比所有整数都大的整数）。符号化时先划出量词的辖域，再确认每个变元受哪个量词约束，最后才套联结词，顺序反了必然写错。

否定的写法当作公式来记：¬∀xP(x) ⇔ ∃x¬P(x)，¬∃xP(x) ⇔ ∀x¬P(x)，否定进入量词辖域后量词翻转、谓词取反。题目里出现「并非所有」「没有」「不都存在」这类措辞，先机械地翻成量词再化简，比凭语感硬写稳得多。

注意：自然语言里的「或者」有时是异或，题目没写明「可兼或」时按相容或处理，答案对不上先回看这一句。

2.2 主范式：编号规则与它的实际用途

求主析取范式的流程固定：写真值表，找成真赋值，每个成真赋值对应一个极小项，最后全部析取起来。编号规则容易记反：变量按字母序排列，赋值中 0 对应否定形式、1 对应原形式，编号就是把该赋值当二进制读出的十进制。三个变量时赋值 011 对应 ¬p∧q∧r，编号 3。

主合取范式取成假赋值，极大项里 0 取原形式、1 取否定形式，与极小项正好相反，这一反是最常见的抄错来源。

用途有三处。判断两个公式是否等值，比较主析取范式的编号集合；判断公式类型，编号集合覆盖全部 2^n 个极小项就是重言式，为空就是矛盾式；数二元联结词的个数，n 元真值表有 2^(2^n) 种，二元是 16 种。

from itertools import product # 变量顺序锁定 p, q, r，成真赋值直接映射为极小项编号 def minterms(expr, n=3): res = [] for bits in product([0, 1], repeat=n): if expr(*bits): # p 视为最高位：三位赋值 011 对应编号 3，与教材约定一致 idx = sum(b << (n - 1 - i) for i, b in enumerate(bits)) res.append((idx, "".join(map(str, bits)))) return res f = lambda p, q, r: (not p or q) and (not q or r) # (p→q)∧(q→r) print(minterms(f)) # [(0, '000'), (1, '001'), (3, '011'), (7, '111')]

这段把真值表枚举和小项编号绑在一起，输出即 Σm(0,1,3,7)。变量个数改成 2 或 4 只需改 n，但变量顺序必须与教材一致——有的版本把 p 当最低位，编号会整体反过来，对答案对不上先查这一点，而不是怀疑公式推错。手算时建议先列全真值表再编号，直接拼极小项容易漏掉某个成真赋值。

2.3 常用等值式：背到条件反射的九条

等值式是后面所有证明的工具箱，考试不给表，只能靠熟。下面这些出现频率最高，建议按「名字、公式、什么时候用」三列记，而不是孤立地背公式。

集合侧有一一对应的版本，把 ∧∨¬ 换成 ∩∪~ 就是集合恒等式。这个平行关系并非巧合：两边都是布尔代数，逻辑里的化简套路可以平移过去。

2.4 集合恒等式：元素法与代数法怎么选

集合等式证明只有两条路。元素法是万能路线：任取元素 x，从「x∈左式」推「x∈右式」，再反向推一遍，得到双向包含。写的时候要显式写出「任取 x」和「反之」两段，缺一段就是半个证明，判卷时按半对扣。代数法用已知恒等式逐步替换，快，但要求对公式熟，且每一步注明用了哪条律。

选择标准很实际：等号两边结构差别大（一边并一边交）用元素法；结构相似只差顺序或重复项用代数法；题目里出现幂集、笛卡尔积的用元素法，因为这两类运算没有可套的代数律。

计数的几个结论顺手记：|P(A)| = 2^|A|，|A×B| = |A|·|B|，n 元集合的子集总数是 2^n，其中包含空集和自身。P(∅) = {∅}，元素个数是 1 而不是 0；∅∈{∅} 与 ∅⊆{∅} 同时成立，这类题几乎每套卷子都有一道。

提示：元素法证明的最后一步必须落回定义，写成「故 x∈A∩B」这种形式；只写「显然成立」是答案里最常见的跳步。

3. 关系与函数：矩阵、闭包与等价划分的三条主线

关系这块题量不大，但连锁性极强：关系矩阵算错，闭包、等价类、哈斯图全跟着错。教材把它拆成关系的性质、复合、闭包、等价关系、偏序、函数几节，复习时最好按三条主线重组：表示与运算、闭包与传递性、等价与偏序这两个特殊关系。函数部分在有些版本里篇幅很轻，重点是单射、满射、双射的判定以及复合是否保持性质。

3.1 三种表示与复合的运算顺序

同一个关系有三种写法：集合列举、0-1 矩阵、关系图，考试按题型挑一种。矩阵的最大好处是把复合变成布尔乘积，关系图的好处是看传递性、自反性一眼就够。

复合的方向最容易出错。R∘S 在不同教材里定义相反，一个读作「先 R 后 S」，另一个读作「先 S 后 R」，矩阵乘法顺序也跟着反过来。做复合题之前先翻到自己教材的定义处确认一次，或者用「结果矩阵 = 前一个矩阵 ⊙ 后一个矩阵」这种保守写法，对答案时先比方向再比数值。

对称和反对称不互斥，恒等关系同时满足两者，这个反直觉的点是选择题常客。

3.2 闭包：手算的并集视角与机算的 Warshall

三种闭包定义很短：自反闭包 r(R) = R ∪ I_A，对称闭包 s(R) = R ∪ R⁻¹，传递闭包 t(R) = R ∪ R² ∪ … ∪ R^n。传递闭包这条公式的要点是上限到 n 次幂为止，因为 n 个顶点的图上任何路径长度超过 n-1 必有重复顶点，可以截断。手算时很多人只算到 R² 就停，答案少了几条边正是这个原因。

机算用 Warshall，三重循环，k 放在最外层表示「允许经过顶点 k 中转」。

def warshall(n, edges): # M[i][j]=1 表示 i 到 j 有边；不预设自反，对角线初始为 0 M = [[0] * n for _ in range(n)] for u, v in edges: M[u][v] = 1 for k in range(n): # k 必须最外层：第 k 轮放开顶点 k 作中转 for i in range(n): if M[i][k]: for j in range(n): M[i][j] = M[i][j] or M[k][j] return M print(warshall(4, [(0, 1), (1, 2), (2, 3)])) # 第 0 行最终为 [0,1,1,1]：顶点 0 可经 1、2 到达 3

循环顺序不能换。把 k 放到最内层，等于只允许用同一轮的信息，结果会漏路径。复杂度 O(n³)，顶点数在十几以内都能快速算出，用来验证手算结果很实用。返回值里对角线仍是 0，需要自反闭包时再把对角线置 1，这一步漏掉会让等价关系判定失败。

3.3 等价关系与划分：一一对应是解题钥匙

等价关系的三性（自反、对称、传递）判定完，通常接两问：求等价类、求商集。等价类 [a] = {x | xRa}，商集是全体等价类作为元素的集合。教材反复强调「等价关系与划分一一对应」，用处在于换视角：给一个划分就能反写出等价关系「同块内元素相关联」，给一个等价关系就能把集合切块。

模 n 同余是最标准的例子，把整数分成 n 个剩余类，商集有 n 个元素。容易错的两处：等价类里的元素是原集合的元素，商集的元素是等价类（集合的集合），写商集时少一层花括号；等价类的个数等于划分的块数，但没人保证每块大小相同，验证时按块数清点而不是把元素个数平均分。

3.4 偏序、哈斯图与三个易混的极值概念

偏序只要求自反、反对称、传递，允许元素之间不可比，这一点与全序的区别就是能不能画出「横着的点」。哈斯图画法三步：去掉自环、去掉由传递性隐含的边、把不可比的点并排画。判分点在于有没有把可比的点画在同一层，层次画错整张图就废了。

极值概念是本节最大的易错点：极大元是「没有比它更大的」，最大元是「它比所有元素都大」。最大元若存在必唯一，极大元可以有多个，且最大元一定是唯一的极大元。极小元与最小元同理。上界、下界、上确界（最小上界）再叠一层，做题时先用文字把每个候选元念一遍再选，别凭图感。

这部分和后面的拓扑排序是同一件事：偏序集上的拓扑排序就是不断取极小元、取完删掉、重复到空。手算时按哈斯图从下往上剥，得到的序列不唯一，答案给了其中一个就算对。

4. 图论与组合计数：握手定理、欧拉判定与递推式的着力点

图论和组合数学在教材里分开，考试里经常放在一起考：给一个图问生成树有几棵、给一个染色方案问有多少种、给一个递推关系问通项。图论提供结构，计数提供数量，两块共用的工具是分类讨论与容斥。复习顺序建议先图后计数，因为握手定理、树的性质这些结论会直接变成计数题的边界条件。

4.1 握手定理与度序列：先验证再动手

握手定理一句话：所有顶点度数之和等于边数的两倍。推论是奇度顶点个数必为偶数。这两条在选择题里以「下列度序列能否构成无向图」的形式出现，几乎每年都有。

判定流程：度数之和为偶数 → 最大度不超过 n-1 → 排序后用 Havel-Hakimi 逐次削去最大度。前两条能筛掉大部分错误选项，第三条才需要动笔。简单图还有一条硬约束：边数不超过 n(n-1)/2，度数之和不超过 n(n-1)。

注意：有向图版本是「入度之和 = 出度之和 = 边数」，别把无向图的 2|E| 套上去。

4.2 欧拉图与哈密顿图：一个能判，一个只能试

这一节最容易混，因为两个名字都带人名、都跟「走遍」有关。区别在于欧拉走遍的是边，哈密顿走遍的是点。

欧拉判定要先确认连通性，孤立点会让「所有顶点度为偶数」成立但图不连通，这是标准陷阱。哈密顿的否定证明更常考，工具是：图中有割点则无哈密顿回路；二部图两侧顶点数不等则无哈密顿回路；某顶点度数为 1 时它关联的边必须用，从而限制邻居的选择。

def euler_type(n, edges): deg = [0] * n for u, v in edges: deg[u] += 1 deg[v] += 1 if sum(deg) != 2 * len(edges): # 握手定理自检，防手抄边表漏项 return "数据不一致" odd = sum(d % 2 for d in deg) # 连通性需另行 BFS/DFS 判定，这里只体现度数条件 return {0: "欧拉回路", 2: "欧拉通路"}.get(odd, "非欧拉图") print(euler_type(4, [(0, 1), (1, 2), (2, 3), (3, 0)])) # 欧拉回路

度数条件只是必要条件的一半，连通性必须单独跑一次遍历，注释里专门标出这一句，是因为漏判连通是最高频的错误。手算时先画图数度，再用连通性复核，两步都过才写结论。

4.3 树：三条等价定义与生成树的手算流程

树的定义有三个等价说法：n 个顶点 n-1 条边且连通；无回路且连通；任意两点间恰有一条路径。考试常给其中两条让你推第三条，答题时按「边数 → 连通 → 无回路」的顺序串一遍最省事。

最小生成树手算流程：把边按权升序排，逐条取，加入后成环就跳过，取到 n-1 条为止。每一步检查的是「两端点是否已连通」而不是「是否已有边」，在纸上给连通分量编号最快。同一张图可能有多棵最小生成树（存在等权边时），题目问

本文还有配套的精品资源，点击获取