简介山东大学《离散数学》复习题含答案是一份面向计算机相关专业学生的备考资料适用于期末复习、考研复试或自学巩固。内容覆盖集合论、命题与谓词逻辑、图论、组合数学、布尔代数、递归与归纳、形式语言与自动机等离散数学主干知识点其中集合论涉及关系与函数逻辑部分涵盖真值表与量词推理图论包含欧拉路径与生成树等经典问题组合数学涉及鸽巢原理与容斥原理覆盖面较广。复习题配有参考答案不仅给出结果还体现常见解题路径方便学习者自测后对照复盘、举一反三。资源仅含1个PDF文件压缩包约1.94MB体积小巧便于在电脑或移动设备上阅读。目前已有905人学习下载适合正在系统梳理离散数学概念、提升解题能力的同学使用。1. 离散数学这门课到底在考什么拿到这份《离散数学》复习题先别急着对答案。很多同学刷题时有个错觉觉得离散数学就是一堆零散知识点的拼盘——今天集合、明天图论、后天布尔代数互相之间没什么关系背住定义就能过关。实际上离散数学是计算机科学真正的“底层语法”考研、保研、复试上机甚至后面学数据结构、算法设计、数据库原理全都在用这里面的概念。你在这份复习题里看到的每一个证明题、每一个等价变形、每一道图的遍历题都是在为后续课程铺路。我见过太多学生在这门上翻车不是不努力而是把复习做成了“背答案”而不是“练思路”。这份复习题含答案本意是让你最后阶段自检但如果只拿着它反复看答案、背结论那性价比极低。真正的用法是把每道题当作一个知识点入口搞清楚它背后连着哪些概念、哪些定理以及那道题的解法能不能推广到别的题上。本文我就顺着离散数学的核心模块——集合与关系、命题逻辑与谓词逻辑、图论、代数系统——把这份复习题背后的核心考点和常见陷阱拆开讲清楚帮你把“会做这一题”变成“会做这一类题”。2. 集合与关系看似送分陷阱全在细节里2.1 集合基本运算判定、幂集与计数公式集合这块在复习题里通常以小题出现但它是后面所有内容的地基。你首先要确认自己能不能闭眼写出下面这几个结论两个有限集 $|A \cup B| |A| |B| - |A \cap B|$三个集合的容斥原理对应的展开式$A \subseteq B$ 与 $A \subset B$ 的区别幂集 $P(A)$ 的元素个数是 $2^{|A|}$。这些结论属于离散数学的“算术题”一旦记混后面的计数问题、概率问题全都会跟着错。我一般建议学生把集合运算当成“逻辑推理题”来练而不是“套公式题”。比如看到 $A \cap (B \cup C)$别急着画 Venn 图先想清楚它等价于 $(A \cap B) \cup (A \cap C)$——分配律。复习题里经常会让判断两个集合表达式是否相等这时候最可靠的办法是取一个具体元素 $x$通过逻辑符号一步步推演。比如判断 $A - (B \cap C)$ 是否等于 $(A - B) \cup (A - C)$用 $x \in A \land x \notin (B \cap C)$等价于 $x \in A \land (x \notin B \lor x \notin C)$再拆开就是 $(x \in A \land x \notin B) \lor (x \in A \land x \notin C)$。能自己推出来比背结论扎实得多。2.2 关系的性质判定自反、反自反与对称的边界关系这部分是复习题的重点也最容易出现“看着都会一考就错”的情况。核心考点是判断一个关系是否满足自反性、反自反性、对称性、反对称性和传递性。这里有个经典陷阱自反性要求的是所有元素都满足只要有一个元素不满足就不是自反关系但对称性要求的是“只要有有序对 $aRb$就有 $bRa$”空关系没有任何有序对反而满足对称性。复习题答案里常常会把空关系拿来当反例你务必要理解这背后的逻辑——全称判断和存在判断在离散数学里的地位完全不同。另外传递性的判定不要只看三元素关系。一个关系 $R$ 满足传递性意思是“只要 $aRb$ 且 $bRc$就一定有 $aRc$”。反例往往藏在需要经过两步才能回到起点的结构里。比如集合 ${1,2,3}$ 上的关系 ${(1,2),(2,3)}$因为 $1R2$ 且 $2R3$但没有 $(1,3)$所以不传递。很多同学栽在这里是因为只盯着二元关系看忘了传递性本质上是“路径可达性”的抽象——这恰好是后面学图论时闭包运算的雏形。2.3 等价关系与偏序关系哈斯图的画法等价关系和偏序关系是关系部分的两个高潮。等价关系要抓住“自反、对称、传递”三性同时成立它会把集合划分成若干等价类商集就是把等价类当成新元素。复习题里常见题型是给一个关系让你证明它是等价关系或反过来给定划分让你构造等价关系。这里的通法是先找自反性这是最直观的再找对称性看有没有“单向箭头”最后验证传递性。三个条件缺一不可。偏序关系考查的重点则是哈斯图。画哈斯图时很多人直接把关系图拿来删箭头结果画成一团乱麻。正确的画法是先去掉自环自反性再去掉因传递性而隐含的边传递闭包压缩最后把所有边改成自下而上的方向去掉箭头。这样得到的图才能一眼看出 Hasse 图的层级结构。复习题里如果让你找极大元、极小元、最大元、最小元记住口诀最大/最小元必须和所有元素都可比极大/极小元只是局部最高/最低。这个区别是高频丢分点。3. 命题逻辑与谓词逻辑等价变形比背真值表更值钱3.1 命题公式的判定从真值表到等值演算命题逻辑部分复习题通常包含两类题一是给一个公式让你判断是重言式、矛盾式还是可满足式二是让你证明两个公式逻辑等价。第一类题最稳妥的办法是画真值表但公式变量一多画真值表就变成体力活还容易抄错。我更推荐用等值演算来快速判断。比如 $p \to (q \to p)$先用蕴含等值式 $A \to B \Leftrightarrow \neg A \lor B$ 展开得到 $\neg p \lor (\neg q \lor p)$再用结合律和交换律整理成 $(\neg p \lor p) \lor \neg q$显然等价于 $T \lor \neg q$也就是重言式。整个过程只需要几步等价变形比画八行真值表快而且不容易出错。复习题答案里给的证明通常也是等值演算路线但你要注意答案不唯一。只要每一步都有定理依据怎么变形都对。我一般要求学生把 16 组基本等值式背熟尤其是德摩根律、蕴含等值式、假言易位和归谬论。这些看着基础实际是后面所有证明题的“工具箱”。3.2 范式与主范式为什么主析取范式比普通析取范式更重要命题逻辑还有一个必考点是求公式的主析取范式和主合取范式。很多学生不理解为什么要搞主范式——普通范式不也是“与或式”吗主范式的意义在于它是唯一的标准形一个公式的主析取范式是唯一的不考虑变元顺序和项顺序因此可以用来判断两个公式是否逻辑等价、判断公式是可满足还是矛盾。复习题里如果直接给公式让你求主范式我建议先化成普通范式再用“补缺变元”的技巧补成主范式。比如 $(p \land q) \lor (\neg p \land r)$第一个项里缺 $r$就变成 $(p \land q \land r) \lor (p \land q \land \neg r)$以此类推。补缺变元时注意别漏漏一项主范式就错了。这一步看起来机械但对后续学数字电路、逻辑综合很有帮助——主析取范式对应最小项之和主合取范式对应最大项之积本质上就是硬件描述语言里真值表的两种标准写法。复习题里把这块放在前面其实是在帮你建立“逻辑函数”的视角。3.3 谓词逻辑与量词否定、辖域与多个体变量谓词逻辑比命题逻辑难是因为多了个体变元、谓词和量词。复习题里常见的题型是将自然语言命题符号化或者对带量词的公式做否定。后者有个非常实用的规则否定一个量词全称变存在、存在变全称然后否定辖域内的公式。比如 $\neg \forall x (P(x) \to Q(x))$先变成 $\exists x \neg(P(x) \to Q(x))$再把蕴含拆掉得到 $\exists x (P(x) \land \neg Q(x))$。这里要注意$\neg(P(x) \to Q(x))$ 等价于 $P(x) \land \neg Q(x)$不要只把 $Q(x)$ 取反那是新手常犯的错误。另外多个量词连用时的解释也是高频考点。$\forall x \exists y R(x,y)$ 和 $\exists y \forall x R(x,y)$ 含义完全不同前者指“对任意 $x$都存在一个可能依赖于 $x$的 $y$ 使关系成立”后者指“存在一个固定的 $y$对任意 $x$ 都成立这种关系”。复习题如果让你判断两个公式在某个模型下是否同真同假注意量词的顺序不可随便交换。我见过太多学生在“每个人都有一个妈妈”和“有一个人是所有人的妈妈”之间栽跟头——前者是 $\forall x \exists y$后者是 $\exists y \forall x$这俩逻辑上完全不等价。4. 图论从概念到应用的完整复习路径4.1 基本术语与握手定理别小看计数题图论是离散数学里面最接近“应用”的模块也是复习题中占分最多的大题来源。基础概念包括度、路径、回路、连通、树、二部图、欧拉图、哈密顿图等。复习题第一道图论题往往很温柔给定一个简单图让你算各顶点度数或判断是否存在欧拉回路。这里必须掌握握手定理所有顶点的度数之和等于边数的两倍。由此可以推出一个常见结论——任何图中度数为奇数的顶点个数必然是偶数。这个结论在证明“某个图不存在”时非常好用比如复习题可能问“是否存在每顶点度数都为3且奇数个顶点的图”答案直接就是否定的因为5个奇度顶点违背了偶数个奇度点的结论。另一个易错点“简单图”和“多重图”的区分。如果题目明确说是简单图那么任意两点之间最多一条边顶点度数上限是 $n-1$如果没写默认按简单图处理。复习题答案中为了保证严密性通常会按“简单图无向”来讨论。你做题时要先确认这个前提否则度数序列的可图性判断会出错。4.2 欧拉图与哈密顿图判定条件别用混欧拉图和哈密顿图是一对极易混淆的概念。欧拉图看的是边的遍历一个连通图存在欧拉回路当且仅当所有顶点的度数都是偶数存在欧拉通路但无回路当且仅当恰好有两个奇度顶点。这个判定条件是充要条件所以可以直接做题。哈密顿图看的是顶点的遍历但它的判定条件复杂得多——目前只有充分条件比如 Dirac 定理$n \ge 3$ 且每个顶点度数至少 $n/2$ 时是哈密顿图和必要条件如删除 $k$ 个顶点后连通分量不超过 $k$没有简单的充要条件。复习题如果让你判断某个图是否是欧拉图直接数度数就行如果让你判断哈密顿图多半是让你用“若存在哈密顿回路则必然满足必要条件”来证明某个图不是哈密顿图。这里我要提醒一句必要条件只是必要不充分不能用“满足必要条件”来证明一个图是哈密顿图。比如很多学生看到删除几个点后还连通就断言是哈密顿图这在逻辑上站不住脚。复习题答案里如果出现这种推理你要警惕——要么题目本身有特殊条件要么答案不够严谨。4.3 树的等价定义与最小生成树Kruskal 与 Prim 的选择树是图论里的“乖孩子”考点非常明确。树的等价定义至少有五个无回路连通图、任意两点间恰有一条路径、边数等于顶点数减一、无回路且添加任意一条边后产生回路、连通且删除任意一条边后不连通。复习题常让你利用这些等价定义来互相推证比如给一个无回路且 $ev-1$ 的图证明它连通。这时用反证法假设不连通则分成 $k$ 个连通分量每个分量内部无回路所以每个分量是树就有 $e_i v_i - 1$对所有分量求和得到 $e v - k$与 $e v - 1$ 矛盾所以 $k1$即连通。这种证明思路在答案里很典型刷题时别只记结论要顺着这个推演过程把“边数和点数的关系”彻底内化。最小生成树是图论应用题里常考的一类。Kruskal 算法按边权从小到大选边不成环就加入适合稀疏图Prim 算法从一个顶点出发逐步扩展连通分支适合稠密图。复习题里如果给一个带权图让你求最小生成树我建议用 Kruskal 算法画步骤因为每一步“选一条最小边并检查是否成环”很直观不容易错。但要注意当存在两条同权边时最小生成树可能不唯一只要总权值一样就算对。4.4 图的着色与二部图判定实际应用与算法意识图的着色问题是离散数学中少有的“算法题”给顶点着色使得相邻顶点颜色不同求最少颜色数。一般图的最少着色数是 NP 难的但二部图的色数是2或1若无边。复习题通常让你判断某个图是否是二部图然后用“二部图色数不超过2”来着色。判断二部图的最快方法是广度优先搜索BFS染色从一个顶点开始染1色邻接点染2色再邻接点染1色如果过程中发现某个顶点的邻接点已经被涂成同色则图不是二部图说明存在奇数环否则是二部图。这个判断方法在复习题答案里通常用“图是否含奇环”来表述因为无向图是二部图的充要条件是不含奇环。你做题时如果看到“证明该图不含长度为奇数的回路”就要立刻想到二部图着色判断。反过来如果让你证明某个图不是二部图只需要找出一个奇环比如三角形即可。5. 代数系统群论入门的三道必考题5.1 运算封闭性与结合律最容易被忽略的验证代数系统在离散数学复习题里通常占最后一大题核心是群的基本概念。很多学生一看到“证明 $G$ 构成群”就头大觉得要验证的东西太多。其实群的定义就四条非空集合、二元运算、封闭性、结合律、单位元、逆元。注意封闭性常常被忽略因为运算表看起来“都落在集合内”似乎天然满足但复习题特别喜欢拿“偶数在乘法下是否封闭”这类题来考你。比如正偶数集合在加法下不封闭因为两个正偶数相加仍为正偶数但集合 ${0}$ 在加法下封闭吗答案是封闭而且这是一个群单位元是0逆元是0自己。所以做这类题不要凭直觉严格检查每一步。结合律的验证最繁琐因为要穷举所有可能的三元组。如果群的运算定义为常见运算矩阵乘法、模 $n$ 加法等结合律通常可以直接引用已知结论如果定义的是自定义运算比如 $a \ast b a b k$$k$ 是常数就一定要老老实实算两边$(a \ast b) \ast c$ 和 $a \ast (b \ast c)$。展开后比较结果是否一致。复习题答案里经常略写结合律因为“显然”或“由实数加法结合律可得”但你考试时别省写一句“由已知运算性质结合律成立”就算完整得分。5.2 单位元与逆元的计算从运算表里找规律给一个有限集合和运算表让你判断它是否为群是经典考题。这时可以直接查表单位元是某个元素 $e$使得 $e$ 所在的行和列都等于表头本身即 $e \ast a a \ast e a$ 对所有 $a$ 成立。找到单位元后再看每个元素所在的行和列有没有恰好等于单位元——那个位置对应的列头元素就是它的逆元。这里有个隐蔽的坑逆元必须左右都满足但有限群里只要运算满足结合律“左逆”即“右逆”可以直接验证一个方向。如果题目没说明运算可结合则左右逆都要验证。复习题答案如果直接说“由表可知2 是单位元1 的逆元是 3”你要回去对着表确认一行和一列。我建议你把运算表当作“查字典”来练先找单位元再对每个元素找逆元最后看有没有哪个元素找不到逆元那就是非群。这种方法比硬背定义高效得多。5.3 子群判定与循环群两条关键定理子群的判定有两条常用定理一是非空子集 $H$ 是子群的充要条件是对任意 $a,b \in H$有 $a \ast b^{-1} \in H$单步检验法二是如果 $H$ 非空且有限只需检验封闭性即可因为有限子半群必为群。复习题常给一个群和一个子集让你判断是否构成子群。如果 $H$ 是有限集我建议直接用封闭性检验任取 $a,b \in H$计算 $a \ast b$看是否还在 $H$ 里。比如在模 6 加群 $\mathbb{Z}_6$ 中集合 ${0,2,4}$ 是否构成子群算 $246 \equiv 0$、$448 \equiv 2$运算都落在集合内封闭所以是子群。循环群是群论里最“友好”的一类群由一个元素的所有幂次或加法下的整数倍构成。判断一个群是否为循环群关键找生成元。在有限群里从单位元出发不断用某个元素运算自己看能不能覆盖所有元素。复习题里如果问“模 $n$ 加法群 $\mathbb{Z}_n$ 的生成元有哪些”答案是与 $n$ 互质的那些元素比如 $\mathbb{Z}_8$ 的生成元是 $1,3,5,7$。这道题基本是送分题但前面不熟练就容易卡壳所以平时练习时一定要自己算一遍$1$ 的倍数模 8 能生成 0 到 7 所有数$2$ 的倍数只能生成偶数所以 2 不是生成元。6. 常见错误与避坑指南刷题时最容易掉进去的五个坑6.1 坑一自反性没验证“所有元素”一道经典错题关系 $R {(1,1),(2,2),(3,3),(1,2)}$ 在集合 ${1,2,3}$ 上很多学生一看有 $(1,1),(2,2),(3,3)$就写“自反”。这题没错因为所有元素都有环。但如果题目改成 $R {(1,1),(2,2),(1,2)}$集合还是 ${1,2,3}$那就不是自反$(3,3)$ 不在 $R$ 里。现象学生只看“常见的几个元素有没有环”忽略覆盖全部元素。原因把自反性理解为“存在环”而不是“所有元素都有环”。解决把条件写成 $\forall x \in A, (x,x) \in R$做题时逐个元素检查不要凭印象。6.2 坑二传递性只看“两步直达”不看中间元素传递性要求 $aRb$ 且 $bRc$ 时必有 $aRc$但很多学生检查时只盯“有没有一步到位的边”忽略需要寻找中间桥梁。比如 ${(1,2),(2,3),(1,3),(3,1)}$ 是否传递表面看 $(1,2)$ 和 $(2,3)$ 有 $(1,3)$ 收尾$(2,3)$ 和 $(3,1)$ 呢要有 $(2,1)$ 才行但 $(2,1)$ 不存在所以不传递。现象漏查了某些组合。原因没有系统枚举所有“两步组合”。解决把关系写成表格逐对检查“箭头的前后连接”或者画有向图沿着边跳两步看终点是否可达。6.3 坑三量词否定时只否定谓词不翻转量词“$\neg \forall x P(x)$”的正确转换是“$\exists x \neg P(x)$”但常有人写成“$\forall x \neg P(x)$”。在复习题里如果让给“并非所有 S 都是 P”符号化很多人写 $\forall x (S(x) \land \neg P(x))$这完全不对——要表达“存在一个 S 且不是 P”应该是 $\exists x(S(x) \land \neg P(x))$。现象否定放错位置量词没翻转。原因对量词否定规则不熟凭语感做题。解决背下规则——否定量词必换量词否定辖域多做题检验“所有人都会死”的否定是“有人不会死”不是“所有人不会死”。6.4 坑四等价关系只验证“对称传递”就以为自反等价关系要求三个性质都成立但有些关系可以对称且传递却仍然不自反。比如集合 ${1,2,3}$ 上的关系 ${(1,1),(2,2),(1,2),(2,1)}$它自反吗缺 $(3,3)$所以不自反。有的题目反例更隐蔽关系 ${(1,2),(2,1),(1,1),(2,2)}$ 在 ${1,2,3}$ 上仍是缺 $(3,3)$。现象做题时想着“前两个性质都满足第三个应该也满足”直接判等价关系。原因没有独立验证自反性。解决把三性分别列举标号验证自反性最容易被忽视务必单独检查。6.5 坑五树的最小生成树只顾选小边忘了查环用 Kruskal 求最小生成树时常见错法是按权值从小到大依次选边不加“查环”步骤最后选出来的边数可能超过 $v-1$甚至出现回路。比如三角形三条边权重分别为 1、2、3直接选权重 1 和 2 没问题但如果再加权重 3 就成环了。现象多选一条边生成树变成“生成子图”。原因只盯权重忽略树的无环性。解决每选一条边前检查该边的两个端点是否已经在同一个连通分量中可以用并查集思维维护一个“已连接集合”如果是则跳过。这个习惯一定要在平时刷题时养成考试时手画也要先画“已连顶点集合”再考虑下一条边。7. 一份高效自检清单照着做考前两周也能救人到了复习后期别再无差别刷题了。你要做的是按模块快速自检把弱项补上。以下是我带过的学生普遍觉得管用的“四步自检法”你可以直接照着执行。第一步把复习题答案里你真正会做的题做个标记会做不看答案能独立写出过程。如果一整套复习题里超过四成不需要看答案说明基础还算扎实如果低于三成建议回到教材把每章的定义重新抄一遍——手抄定义是强化记忆最笨但最有效的方法。第二步针对每个模块的记录三道题一道概念题比如“列出树的五个等价定义”、一道计算题比如“求某个关系的主析取范式”、一道证明题比如“证明某个运算是群”。然后用完全空白纸写这三题写完后对着答案用红笔标出每一步的依据。别小看这一步它逼你把“知道”变成“会证”。第三步用表格整理你的高频错因。我建议你建一个像下面这样的“错题画像表”把做错的题和错因归类你会发现大多数错误集中在极少数几个知识点上模块高频错误点解决办法集合与关系自反性漏检传递性没两步跳逐元素验证画有向图辅助命题逻辑量词否定忘翻转主范式补缺漏项背规则多练补缺变元谓词逻辑量词顺序理解反每个公式写自然语言翻译再对照图论手滑把欧拉图和哈密顿图混了写判定条件卡片贴墙上代数系统封闭性忘记验证结合律没算完运算表逐个检查定义四条写全最后一步做两道综合题。离散数学考试往往在最后放一道“大综合”把图论和代数系统串起来比如“证明一个有向图的强连通分支构成一个偏序关系”或者“从群的角度解释凯莱图”。你如果没有时间系统刷题至少做两道这种综合题不要只看答案一定要逼自己用下意识反应做一遍。我的习惯是在复习后期每天翻一下错题画像表再重做一道“上次做错”的题。这个习惯帮我带过的很多学生在考前两周内把丢分点补救回来。回头想想离散数学的逻辑并不难难的是把规则内化到“不假思索就能用”的程度。如果你发现自己复习时反复在同一个坑里翻车不要急着刷更多题先停下来把那个坑填平。希望这份复习路径能帮你把一套复习题的知识密度全部榨干——别把答案当终点那只是你梳理思路的起点。希望帮到你。本文还有配套的精品资源点击获取