离散数学：练习题和考试题

计算机科学和一切证明的数学基础：命题逻辑与量词、集合、关系与函数、含最短路径和生成树的图论，以及直到 RSA 的数论。考试要求给出精确答案，因此仔细的表格或图示比计算器更重要。

免费练习本课程练习本课程参加模拟考试每天 5 道免费题目，无需绑定银行卡。

速成包（PDF）公式表、方法步骤和附完整解答的练习题，可直接打印。

本课程的主题

离散数学考试技巧

写出真值表或维恩图：大多数错误都来自漏掉一行或一个区域。
要推翻一个命题，一个反例就够了；要证明它，则必须检验所有情形或给出一般性论证。
在模运算中，每一步之后都要取余，并使余数保持在 0 到 n − 1 之间。

例题详解

命题逻辑与证明简单

真值表中恰有一行使 ¬(p ∨ q) → q 为假。点选这一行。

¬(p ∨ q) → q

1p = 1, q = 1
2p = 1, q = 0
3p = 0, q = 1
4p = 0, q = 0

显示提示

a → b 只有在 a = 1 且 b = 0 时才为 0。 ¬a 把值取反。 a ∨ b 只有在两者都为 0 时才为 0。
先确定主联结词：要使整个公式为 0，它的两边必须是什么？
给每个部分单独一列：p ∨ q; ¬(p ∨ q); ¬(p ∨ q) → q。

显示答案和解析

真值表：含 n 个不同变量的公式有 2ⁿ 行，每一行对应真值的一种组合（1 = 真，0 = 假）。由内向外进行，给每个子公式单独一列。¬a 把值取反；a ∧ b 只有在两者都为 1 时才为 1；a ∨ b 只有在两者都为 0 时才为 0；a → b 只有在 a = 1 且 b = 0 时才为 0；a ↔ b 在两边相等时为 1。

逐行写出真值表

p = 1, q = 1: p ∨ q = 1, ¬(p ∨ q) = 0, ¬(p ∨ q) → q = 1

p = 1, q = 0: p ∨ q = 1, ¬(p ∨ q) = 0, ¬(p ∨ q) → q = 1

p = 0, q = 1: p ∨ q = 1, ¬(p ∨ q) = 0, ¬(p ∨ q) → q = 1

p = 0, q = 0: p ∨ q = 0, ¬(p ∨ q) = 1, ¬(p ∨ q) → q = 0

该行

p = 0, q = 0 → ¬(p ∨ q) → q = 0

答案

p = 0, q = 0

集合、关系与函数中等

在 53 名一年级学生中，35 人通过了数学 (M)，28 人通过了物理 (P)，29 人通过了化学 (C)。20 人通过了 M 和 P，18 人通过了 M 和 C，10 人通过了 P 和 C，6 人三门都通过了。有多少属于三个集合中的任何一个都不属于？

|U| = 53

求： |(M ∪ P ∪ C)′|

显示提示

从中心向外填写维恩图：先是三者都属于的，再是两两的，然后是单个集合。
只属于 M 和 P（不属于 C）：20 − 6 = 14。只属于 M：35 − 14 − 12 − 6 = 3。
至少属于一个集合：35 + 28 + 29 − 20 − 18 − 10 + 6 = 50。

显示答案和分步解答

集合与维恩图：A ∪ B 包含属于 A 或 B（或两者）的元素，A ∩ B 包含同时属于两者的元素，A − B 包含属于 A 但不属于 B 的元素，补集 A′ 是 U 中不属于 A 的一切元素。在维恩图中，每个集合表达式都是若干区域的并集，所以要逐个区域地计数。容斥原理：|A ∪ B| = |A| + |B| − |A ∩ B|，以及 |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|。

中心与两两交

M ∩ P ∩ C: 6

M ∩ P 仅: 20 − 6 = 14

M ∩ C 仅: 18 − 6 = 12

P ∩ C 仅: 10 − 6 = 4

单个集合

M 仅: 35 − 14 − 12 − 6 = 3

P 仅: 28 − 14 − 4 − 6 = 4

C 仅: 29 − 12 − 4 − 6 = 7

答案

|M ∪ P ∪ C| = 50

|(M ∪ P ∪ C)′| = 53 − 50 = 3

答案

|(M ∪ P ∪ C)′| = 3

练习方式

“练习本课程”会混合出该课程所有主题的题目，就像真正的考试一样。
每道题的数值都不同，让你掌握方法，而不是记住答案。
卡住了？先打开一个小提示，需要时再查看完整解析。
模拟考试限时且没有提示，结束后你会得到分数和完整的回顾。