简介哈工大《离散数学》教科书配套习题答案解析文档面向使用该校教材学习离散数学的本科生与自学者尤其适合在集合论章节遇到证明困难、需要对照思路的读者。整份资源为单一Word文档大小约4.63MB内容以集合及其运算为主线覆盖集合定义、交并差运算、包含与相等关系、幂集与笛卡尔积、集合族与极限集等核心知识点并配有大量证明例题与详细解答过程。解析中穿插直接证明、反证法、归纳法等常用证明方法帮助读者梳理证明逻辑与书写规范同时针对易混淆的命题给出真值判定、反例与充要条件分析能有效提升对集合模型、运算律和抽象证明的理解兼顾基础巩固与提高训练。已有370人学习下载适合作为课后复习、考研准备或教学参考的补充材料。1. 离散数学习题集从集合到映射的完整答案链当年备考某高校离散数学期末考最头疼的不是公式记不住而是教材课后题只有题干没有过程错了都不知道哪一步逻辑断了。后来拿到这份按章节整理的习题解答从集合运算一直覆盖到映射与鸽巢原理每道题都有完整推导某些经典证明还给了两种证法。这份资源适合三类人正在修离散数学、被集合证明题卡住的学生备课需要标准解答作参照的助教或教师以及自学离散数学、缺少反馈渠道的从业者。几十页的 PDF 内容密度极高把教材习题从“做完对答案”变成“看懂每一步为什么这么做”今天拆给你看。2. 集合的基础概念与子集关系先吃透定义再谈证明要上手这份习题集第一关不是技巧而是对集合语言本身的敏感度。第一章几乎所有证明题最后都会回到元素与集合的从属关系以及集合之间的包含关系。换句话说读题时头脑里必须先建立一张“元素层—集合层—集合族层”的地图不然很容易把逻辑绕晕。2.1 元素与空集的两个陷阱从“方程的根”看集合表示习题第 3 题要求写出方程的根所构成的集合看起来简单但很多人在表示形式上丢分比如把根写成“1 或 2”而不是集合花括号。这份解答在开头就示范了标准写法先算出根再写成集合形式。真正的坑在后面几道判断题例如“对每个集 A∅ ∈ A”这类命题很多人直觉觉得空集属于任何集合实际上空集是任何集合的子集但不一定是元素。这两者边界不清后续证明会处处碰壁。命题逐条判断示例原文习题 4 的答案摘录 a) 对每个集 A∅ ⊆ A —— 真 b) 对每个集 A∅ ∈ A —— 假 c) 对每个集 AA ⊆ A —— 真 d) 对每个集 AA ∈ A —— 假除非特别构造判断的关键在于区分“子集”与“元素”两个层面。∅ ⊆ A 表示空集是 A 的子集这由“空集中的元素都在 A 中”这个空洞的真命题保证而 ∅ ∈ A 要求空集作为对象出现在 A 的元素列表里普通集合通常不满足。做题时我的习惯是每遇到一个符号先用一句话说出它在哪个层级上起作用层级混用是这类判断题里最常见的丢分原因。2.2 子集的传递性与集合相等从“x 属于左边”出发第一章习题第 7 题考的是若 A ⊆ B 且 A ⊆ C试证 B C。这个结论乍看违反直觉——A 同时被两个集合包含凭什么叫 B 和 C 相等实际上题目条件里还藏着关键约束原文里 A 与 B、A 与 C 之间不是单方向的包含而是通过某种运算构成的互相包含关系。解答中用了双向包含的证明框架先任意取 x ∈ B利用已知条件推出 x ∈ C得到 B ⊆ C再取 y ∈ C 推出 y ∈ B得到 C ⊆ B最终 B C。这个“双向包含证相等”的手法贯穿全书。具体到这一步关键在于把已知条件转化成一个可操作的推理链由 x ∈ B结合 B 与 A 的关系推出 x ∈ A再结合 A ⊆ C 推出 x ∈ C。每一步只做一个动作不要跳步。实际做题时我发现很多人知道要正反两次证明但第一次推导里用的是同一个假设导致两个方向实际上是同一个方向的重复这是需要留意的细节。2.3 幂集元素个数从 n0 到归纳假设的递推逻辑第一章第 7 题设 S 恰有 n 个元素证明其幂集 P(S) 有 2^n 个元素。这不是从排列组合直接套公式而是通过归纳法建立了严格的递推关系。解答分两步当 n0 时 P(S) {∅}恰有 1 2^0 个元素假设 nk 时结论成立考虑 nk1 的情况时把新元素 x 加入原集合。P(S) 中的集合分两类不包含 x 的恰好就是原集合的幂集共 2^k 个包含 x 的相当于在原集合每个子集里添上 x又是 2^k 个总和为 2^k 2^k 2^(k1)。递推关系可视化 原集合 S|S| k ├── 不含 x 的子集对应 P(S)数量 2^k └── 含 x 的子集{T ∪ {x} | T ∈ P(S)}数量 2^k 合计2^k 2^k 2^(k1)这个归纳的关键在于“分类不重不漏”——每个新集合要么不含 x要么含 x没有第三种情况。实际运用中很多人卡在“为什么两类元素个数相同”这一点上原因在于没有建立从 P(S) 到“含 x 子集族”的一一对应T 映射到 T ∪ {x}。只要这个映射是双射数量自然相等。类似的手法在后面映射章节还会反复出现。3. 集合运算证明题定义展开与反证法的配合使用集合章节的证明题有一点很像解方程你手里有好多“运算法则”但什么时候用哪一条取决于式子右边最终要变成什么形状。某些题可以直接展开定义一路推到底某些题需要临时假设反面的情况来制造矛盾。前者的代表是分配律类证明后者的典型是“若 A∪B A∩B 则 A B”。3.1 交换律展开A∪B B∪A 的逐元素推导交换律看起来像废话但真要在集合框架下证明它其实是在验证“或”运算的对称性。以题目“设 A、B 是集合试证 A∪B B∪A”为例解答用的是最朴素的定义展开法任取 x ∈ A∪B由并集定义知 x ∈ A 或 x ∈ B这等价于 x ∈ B 或 x ∈ A于是 x ∈ B∪A得到 A∪B ⊆ B∪A反过来同理得到另一边包含最终相等。这个证明没有任何技巧含量但它确立了“集合相等 双向包含”这个基础框架。做这类题时我一般会在草稿纸上先写“任取 x ∈ 左边”然后问自己这个条件能推出哪些事实把这些事实全部列出再对照右边集合的定义看能否逐步靠近。多数证明题推不下去不是不会展开而是没注意到展开到一半时可以用“且”与“或”的分配律重组条件。3.2 反证法两连击A⊆B 与 A∪B A∩B 的隐式矛盾第一章习题第 1 题要求证明“若 A∪B A∩B则 A B”解答给了反证法的标准操作。假设 A ≠ B则存在 x ∈ A 且 x ∉ B或存在 y ∈ B 且 y ∉ A。若取第一种情况此时 x ∈ A∪B因为 x ∈ A但 x ∉ A∩B因为 x ∉ B这与 A∪B A∩B 矛盾第二种情况同理。所以假设不成立A B。反证法结构拆解 目标A B 假设A ≠ B 分支一∃x ∈ A 且 x ∉ B → x ∈ A∪B 但 x ∉ A∩B → 与 A∪B A∩B 矛盾 分支二∃y ∈ B 且 y ∉ A → y ∈ A∪B 但 y ∉ A∩B → 矛盾 结论假设不成立A B这里有一个容易被忽略的操作细节题目里 A∪B A∩B 不是“两个集合相等”这么简单它是“两个不同构造的集合相等”。并集比交集大要让它们相等唯一可能就是 A 和 B 互相包含且没有多余元素。反证法捕捉的正是这种“多余元素”的存在性。实际做题时要注意同时检查两个分支只证一个方向就下结论是常见失误。3.3 对称差与集合相等从“且”与“或”的分布律突破第一章第 15 题是填空题设 A、B 是两个集合(a) A∩B ________(b) A∪B ________(c) A-B ________(d) A⊕B ________。这份题表面上考运算定义实际上考的是你能不能把“集合表达式”翻译成“逻辑表达式”。比如 (d) 的对称差标准定义是 (A-B) ∪ (B-A)也可以写成 (A∪B) - (A∩B)还可以展开成 (A 且非 B) 或 (B 且非 A)。从应试角度这类题目往往不是考你对概念的记忆而是考你在复杂表达式中的“翻译”熟练度。我在复现这些填空时会把每个集合表达式都在旁边写一版逻辑命题表达式例如 A-B 对应“x ∈ A 且 x ∉ B”然后通过命题逻辑的分配律去化简。很多看起来复杂的集合恒等式用这种方法拆开后会变成纯粹的布尔代数问题难度直接降一个档位。4. 集合族与笛卡尔积从单层集合走向多层结构如果说前面的双重包含证明还是在“元素—集合”两层结构里操作那么集合族、幂集、笛卡尔积这些概念开始引入“集合的集合”和“有序对”。这一章是很多人觉得离散数学“抽象得没边”的地方但实际上它只是把之前的逻辑推演放在了更复杂的结构上每一步仍然可以回归到元素层面验证。4.1 集合族的交与并广义运算的展开原则第一章第 14 题给出了一个典型结论对任意集合 A 和任意集合族 CA ∩ (∪C) ∪{A ∩ Ci | Ci ∈ C}。乍看这个等式很绕但展开后其实没什么新鲜的。任取 x ∈ A∩(∪C)则 x ∈ A 且存在某个 Ci ∈ C 使得 x ∈ Ci于是 x ∈ A∩Ci从而 x ∈ ∪{A∩Ci}。反过来任取 x ∈ ∪{A∩Ci}则存在 Ci 使 x∈A∩Ci于是 x ∈ A 且 x ∈ Ci ⊆ ∪C所以 x ∈ A∩(∪C)。关键一步的等价性 x ∈ A ∩ (∪C) ⟺ x ∈ A 且 (∃Ci ∈ C, x ∈ Ci) ⟺ ∃Ci ∈ C, (x ∈ A 且 x ∈ Ci) ⟺ x ∈ ∪{A ∩ Ci | Ci ∈ C}注意到中间那个“存在量词与合取”的交换顺序是这里逻辑推导的核心。处理集合族时最忌讳把它们当成“一堆集合”应该始终把注意力放在“某个元素是否属于它”的判断上。实际做题时遇到集合族等式我习惯先设一个 x 属于左边然后不断追问“x 属于这个集合意味着什么”每一步都写出对应的逻辑命题直到等式两边完全对齐。4.2 笛卡尔积的分配律序对与集合运算的混合验证第一章习题第 4 题设 A、B、C、D 为任意四个集合证明 (A×B) ∩ (C×D) (A∩C) × (B∩D)。这个结论看起来像乘法分配律但它涉及序对结构不能直接用集合运算的分配律来套。关键在于序对相等的定义(a,b) (c,d) 当且仅当 ac 且 bd。于是 (x,y) ∈ (A×B) ∩ (C×D) 等价于 (x,y) ∈ A×B 且 (x,y) ∈ C×D即 x∈A 且 y∈B 且 x∈C 且 y∈D重新组合为 x∈A∩C 且 y∈B∩D这正好说明 (x,y) ∈ (A∩C) × (B∩D)。这一步的微妙之处在于集合交对笛卡尔积的分配本质上是“且”逻辑对“且”逻辑的分配。处理这类题时我最常犯的错误是只验证一个方向的包含就收工。双向包含在这个等式里不是形式主义——从右边推左边依赖的是序对相等定义而这一步往往不证自明但必须写出来。从应试角度看这道题最有价值的练习不是记住结论而是养成“每一步只做一次逻辑替换不跳步”的习惯。4.3 A×B B×A 的充要条件三个条件的分类讨论第一章第 2 题的结论很有意思A×B B×A 的充要条件是 A∅、B∅、或 AB 三个条件至少一个成立。必要性的证明采用了反证法假设三者都不成立即 A≠∅、B≠∅、且 A≠B则存在 a∈A、b∈B并且要么存在 a∈A 且 a∉B要么存在 b∈B 且 b∉A。前者导致 (a,a) ∈ A×B 但 (a,a) ∉ B×A后者导致 (b,b) ∈ A×B 但 (b,b) ∉ B×A无论哪种都与 A×B B×A 矛盾。分类反证路径 假设 A≠∅, B≠∅, A≠B ├── ∃a∈A 且 a∉B → (a, a) ∈ A×B 但 ∉ B×A └── ∃b∈B 且 b∉A → (b, b) ∈ A×B 但 ∉ B×A 无论哪种情况A×B ≠ B×A矛盾这道题有三个相关的“边界值”需要留意a 和 b 的选择是否依赖于 a 和 b 的选取证明中 a 是 B 中的元素b 是 A 中的元素它们的存在性由 A≠∅、B≠∅ 保证。而 a、b 的存在性分别由“A 包含不属于 B 的元素”和“B 包含不属于 A 的元素”保证。这四个存在性前提缺一个反证就推不下去。真到了考试我应该会先写“A≠∅ 且 B≠∅ 且 A≠B”再分别找反例这样思路会比直接记忆证明更不容易丢步。5. 映射与鸽巢原理从集合结构到组合计数的链接第二章的内容从“集合长什么样”转向“集合之间怎么连接”核心概念包括单射、满射、双射和鸽巢原理。有趣的是鸽巢原理本身是个极其朴素的命题——把 n1 个物体放进 n 个盒子至少有一个盒子放了两件物体——但它的证明和运用跨度极大从数论整除性到几何点距离都能串起来。习题集在这一章花费了大量篇幅说明它才是离散数学真正拉开差距的地方。5.1 双射计数从 A 到 A 的 m! 个双射是怎么来的第二章习题第 1 题设 A、B 是有穷集|A| |B| m(1) 计算从 A 到 B 的映射个数(2) 从 A 到 A 有多少个双射第一问答案是 m^m理由是每个元素有 m 个选择m 个元素排列组合就是 m^m第二问答案是 m!理由是一个双射本质上是一个排列。这里最容易让人困惑的其实是“为什么一个排列就是双射”因为排列确定了每个元素唯一的像且每个像恰好被一个原像对应这正好满足单射和满射的双重要求。以 m3 为例 A {a1, a2, a3} 排列 a1→a2, a2→a3, a3→a1 是双射 排列 a1→a1, a2→a1, a3→a3 不是单射a1 有两个原像实际做题时很多人会把“从 A 到 A 的映射”和“从 A 到 A 的双射”混为一谈。前者每个元素独立选像后者要求整体上像集合恰等于原集合。这份习题集的解答在这一点上区分得很清楚做题时我会先标出“这个映射限制条件是什么”再决定用乘法原理还是排列公式。5.2 鸽巢原理的标准形式从 5 个点到 10 个点的几何版本第二章习题第 1 题给出了一个几何应用边长为 1 的等边三角形中任取 5 个点必有两点距离不超过 1/2。证明思路是先把大三角形 4 等分得到 4 个边长为 1/2 的小等边三角形5 个点中由鸽巢原理必有两个落在同一个小三角形内而小三角形内任意两点距离不超过 1/2。第二个表述更极端任意 10 个点必有两点距离不超过 1/3做法是连接各边三等分点得到 9 个边长为 1/3 的小三角形。对应关系表 三角形边长 → 划分份数 → 小三角形个数 → 点数 → 结论距离 1 4 等分 4 5 ≤ 1/2 1 9 等分 9 10 ≤ 1/3这道题的难点在于怎么把几何命题翻译成“物体—盒子”语言。物体是点盒子是小三角形关键是证明“同一个小三角形内任意两点距离不超过某个值”。这个事实依赖等边三角形的几何性质小三角形的直径就是它的边长。这个结构在后继的很多组合几何题里都会反复出现而习题集在这里补充了清晰的图形推理路径值得反复推导。5.3 鸽巢原理的升级版52 个整数余数分类的构造方法第二章第 3 题证明在 52 个整数中必有两个整数使它们的和或差能被 100 整除。解答先把 52 个整数分别取模 100 的余数然后把 0 到 99 这 100 个余数分成 51 类{0}、{1,99}、{2,98}、…、{49,51}、{50}。52 个余数放进 51 个类必有两个落在同一类。若它们相等落在 {0} 或 {50} 这种单元素类则两数之差能被 100 整除若它们互为相反数落在 {k, 100-k} 这种配对类则两数之和能被 100 整除。余数分类表 单元素类{0}, {50} 配对类{1,99}, {2,98}, …, {49,51} 合计2 49 51 类这个构造的关键在于“把余数配对使得同一类里任意两个数要么相等要么互补”。很多人看到 52 和 100 就会想用抽屉原理直接套但没有意识到抽屉要自己设计。这份解答的价值正在于它示范了“从结论倒推抽屉划分”的方法因为要证明“和或差能被 100 整除”所以同一抽屉里的两个余数必须满足“相等或互补”之一据此就能自然导出上面的分类。复现时先做这个小推导再记分类表基本就不会忘。5.4 单调子序列与鸽巢的耦合偏序关系的长度判定第二章习题第 4 题的结论是组合学里著名的“任一由 n^21 个两两不等的整数构成的序列必有一个长度至少为 n1 的递增子序列或一个长度至少为 n1 的递减子序列”。习题集的证明思路是对序列中每个位置 i记以该位置为首项的最长递增子序列长度为 a_i最长递减子序列长度为 b_i。若结论不成立则所有 a_i ∈ {1,…,n} 且所有 b_i ∈ {1,…,n}于是 (a_i, b_i) 最多有 n^2 种可能。但序列有 n^21 项必有 ij 使得 (a_i,b_i) (a_j,b_j)此时若 x_i x_j则把 x_j 拼在以 x_i 为首项的递增子序列前会得到更长的递增子序列若 x_i x_j 则同理可得更长的递减子序列均与“最长”假设矛盾。反证法链条 假设反例存在长度 ≤ n 且 ≤ n → 构造二元组 (a_i, b_i)取值空间大小为 n^2 → 鸽巢原理推出存在 ij 使两个二元组相等 → 比较 x_i 与 x_j 大小关系构造更长单调子序列 → 与“最长”矛盾这个证明的精妙之处在于把“递增子序列长度”和“递减子序列长度”打包成一个二维“状态标记”然后用鸽巢原理制造碰撞。做题时我习惯于像这样先寻找“什么量是有界的”——如果某个量取值空间不够大而对象数量足够多就存在碰撞碰撞后往往能触发矛盾。这个套路在诸多数论和组合证明里都适用属于高性价比的证明策略。6. 把答案资源变成复习工具一份配套使用技巧与易错押题清单把这份习题解答当作“做完题对答案”的资料效果会折损一半真正值钱的用法是把它当成“证明方法参考手册”配合教材逐题复现。下面给出我的具体使用方法和几条实战技巧。6.1 三刷法从背答案到重组证明链第一遍做题时先不看解答自己写写不下去时再看答案的下一步。第二遍合上答案从头独立重写整道题的证明重点检查“双向包含是否都写了”、“反证法假设是否用满”。第三遍换一种证法重做经典题比如同一道集合等式分别用定义展开和反证法各做一遍。这样三遍下来本质上是在积累“证明方法库”而不是“题海库”。三刷法操作流程 第一刷读题 → 尝试 10 分钟 → 看答案下一步 第二刷闭卷重写完整证明 → 对照答案标记逻辑断点 第三刷换证法重做 → 体会不同方法适用场景这个方法听起来费时间但实际效率反而高。因为大部分证明题的逻辑骨架是相似的做熟一道题相当于掌握了一类题。特别是第一章的集合等式证明来回用的就是“定义展开、双向包含、反证法”三件套三刷一次基本就能迁移到其他题目上。6.2 踩分点自查阅卷时最容易扣分的三个位置结合这份答案反复出现的结构整理出阅卷时最容易扣分的三个位置。第一个是集合相等证明里只写了一个方向的包含关系。很多同学证到 A ⊆ B 就收笔了少了 B ⊆ A这道题通常只给一半分。第二个是反证法选了假设但没有用满所有条件。最典型的就是前面第 2 小节提到的“A∪B A∩B”那道题只讨论了一种情况就下结论。第三个是“设 x ∈ ∪C”后忘了强调“存在某个 Ci”导致后面的推导直接失去了依靠。这三个位置几乎覆盖了集合章节一半以上的扣分点做题时只要对照自查就能稳定提分。6.3 答案熟手进阶把核心命题整理成自己的推演清单到备考后期我不再逐题刷而是把这份答案里反复出现的核心命题整理成一张推演清单按“条件→结论→证明入口”三栏记录。例如“A×B B×A 的充要条件”这一行证明入口写“反证法检查序对归属”“幂集元素个数 2^n”这行写“归纳法分类含 x 与不含 x”“鸽巢原理证明整除”这行写“构造余数配对类”。这样一页纸就能覆盖全书的主要证明套路考前快速过一遍比翻几十页答案效率高得多。用这份资料的最后一步是把每章代表题独立重写一遍。我自己的习惯是每复习完一章就在白纸上默写 3 道代表题的完整证明不追求一字不差但要求每一步都有依据并且能从步骤推回结论。这么做的原因是答案看懂了不代表能独立写一旦动笔就会发现很多自查时没暴露的逻辑跳跃。从那以后我每次刷这种习题集资料都会强制走一遍“独立复写 对照标注”的流程既练了证明手感又把答案真正变成了自己的推演模板。希望帮到你。本文还有配套的精品资源点击获取