《离散数学》期末试卷A (精选08)
一、填空题（20 分，每空 2 分）
- $A \times B = \{\langle 1, 1 \rangle, \langle 2, 2 \rangle, \langle 3, 1 \rangle, \langle 3, 2 \rangle, \langle 1, 2 \rangle, \langle 2, 1 \rangle\}$，$P(B)$ 是 $B$ 的幂集，则 $P(B) =$ ________，$|P(P(B))| =$ ________。
查看答案与解析
答案：$P(B) = \{\emptyset, \{1\}, \{2\}, \{1, 2\}\}$；$|P(P(B))| = 16$
解析：
- 求集合 B：根据笛卡尔积定义，$A \times B$ 的元素是由 $A$ 中的元素作为第一分量、$B$ 中的元素作为第二分量组成的有序对。从给定的集合中提取所有第二分量，得到 $B = \{1, 2\}$。
- 求幂集 $P(B)$：幂集是所有子集构成的集合。$B$ 的子集有 $\emptyset$（空集）、$\{1\}$、$\{2\}$、$\{1, 2\}$。
- 求幂集的势：$|B|=2 \implies |P(B)|=2^2=4$。以此类推，$|P(P(B))|=2^{|P(B)|}=2^4=16$。
难度：⭐
考点：#笛卡尔积 #幂集 #集合的势
💡 学习锦囊
📖 相关公式：
- $|P(S)| = 2^{|S|}$
- $A \times B = \{\langle a, b \rangle \mid a \in A \land b \in B\}$
思路分析
计算嵌套幂集的元素个数时，遵循从内向外的原则：先算底层集合的大小，再逐层应用 $2^n$ 公式。
🔄 举一反三
- 若 $A = \{a, b, c\}$，求 $|P(P(A))|$。
查看练习答案与解析
答案：256。
解析：$|A|=3 \implies |P(A)|=2^3=8 \implies |P(P(A))|=2^8=256$。
- 设集合 $A = \{x \mid x \text{ 是 book 中的字母}\}$，$B = \{x \mid x \text{ 是 black 中的字母}\}$，则 $A \cap B =$ ________，$A - B =$ ________。
查看答案与解析
答案：$A \cap B = \{b, k\}$；$A - B = \{o\}$
解析：
- 元素列举：
- $A = \{b, o, k\}$（注意：集合元素具有互异性，'o' 虽然在单词中出现两次，但在集合中只计一次）。
- $B = \{b, l, a, c, k\}$。
- 交集运算：找出两集合的公共元素，即 $b, k$。
- 差集运算：从 $A$ 中剔除所有属于 $B$ 的元素。$A$ 中的 $b$ 和 $k$ 在 $B$ 中，而 $o$ 不在。故剩余 $\{o\}$。
难度：⭐
考点：#集合运算 #交集 #差集
💡 学习锦囊
📖 相关公式：
- $A \cap B = \{x \mid x \in A \land x \in B\}$
- $A - B = \{x \mid x \in A \land x \notin B\}$
思路分析
处理自然语言描述的集合时，第一步必须是将描述转化为显式的元素列举，并严格执行“去重”。
🔄 举一反三
- 设 $S = \{1, 2\}, T = \{2, 3\}$，求 $S \oplus T$。
查看练习答案与解析
答案：$\{1, 3\}$。
解析：$S \oplus T = (S \cup T) - (S \cap T) = \{1, 2, 3\} - \{2\} = \{1, 3\}$。
- 设 $P$：我今天进城，$Q$：今天下雨，则命题“我今天进城，除非下雨。”可符号化为 ________。
查看答案与解析
答案：$\neg Q \to P$（或 $P \lor Q$）
解析：
- 逻辑结构分析：“$A$ 除非 $B$”的标准逻辑含义是“如果不 $B$，则 $A$”。
- 符号化：代入已知命题，得 $\neg Q \to P$。
- 等价化简：依据蕴涵等值式 $\neg Q \to P \equiv \neg(\neg Q) \lor P \equiv Q \lor P$。
难度：⭐⭐
考点：#命题符号化 #联结词
💡 学习锦囊
📖 相关公式：
- 蕴涵等值式：$X \to Y \equiv \neg X \lor Y$
- “除非”结构：$P$ 除非 $Q \equiv \neg Q \to P$
思路分析
日常语言中的“除非”容易引起混淆。记住口诀：除非后面的命题取非作为前提。
🔄 举一反三
- 将“只有你努力，你才能及格”符号化（$P$：你努力，$Q$：你及格）。
查看练习答案与解析
答案：$Q \to P$。
解析：“只有 $A$ 才 $B$”是必要条件，翻译为 $B \to A$。
- 设 $A = \{1, 2, 3\}$，$P(A)$ 是 $A$ 的幂集，代数系统 $\langle P(A), \cup \rangle$ 的幺元为 ________，零元为 ________。
查看答案与解析
答案：$\emptyset$；$A$
解析：
- 幺元（Identity Element）：满足 $X \cup e = X$。在并运算中，只有并上空集 $\emptyset$ 元素才保持不变。
- 零元（Zero Element）：满足 $X \cup z = z$。在并运算中，任何子集并上全集 $A$ 都会变成全集 $A$。
难度：⭐
考点：#代数系统 #幺元 #零元
💡 学习锦囊
📖 相关公式：
- $\cup$ 运算：幺元 $\emptyset$，零元 全集。
- $\cap$ 运算：幺元 全集，零元 $\emptyset$。
思路分析
幺元是“不干涉元”，零元是“同化元”。
🔄 举一反三
- 在 $\langle P(A), \cap \rangle$ 中，零元是什么？
查看练习答案与解析
答案：$\emptyset$。
- 无向图 $G = \langle V, E \rangle$ 如图 1 所示，则该无向图的点连通度 $\kappa(G) =$ ________，边连通度 $\lambda(G) =$ ________。节点 $v_1$ 到 $v_1$ 的长度小于等于 3 的回路的数目 $=$ ________。
图 1
查看答案与解析
答案：2；2；4
解析：
- 点连通度 $\kappa(G)$：观察图中，去掉 $\{v_2, v_5\}$ 后图变为不连通。由于最小度为 2，且无法通过去掉 1 个点使其不连通，故 $\kappa(G)=2$。
- 边连通度 $\lambda(G)$：依据定理 $\kappa(G) \leq \lambda(G) \leq \delta(G)$。图中 $\delta(G)=2$（如顶点 $v_3, v_6$），故 $\lambda(G)=2$。
- 回路计数：长度 $\leq 3$ 的回路只能是长度为 3 的圈（无自环和重边）。包含 $v_1$ 的 3 圈有：
- $v_1 \to v_2 \to v_5 \to v_1$
- $v_1 \to v_5 \to v_2 \to v_1$
- $v_1 \to v_3 \to v_5 \to v_1$
- $v_1 \to v_5 \to v_3 \to v_1$ 共计 4 条路径。
难度：⭐⭐
考点：#连通度 #通路与回路
💡 学习锦囊
📖 相关公式：
- 惠特尼不等式：$\kappa(G) \leq \lambda(G) \leq \delta(G)$。
思路分析
计算路径数时，不同的中间节点顺序代表不同的路径。
🔄 举一反三
- 若图 $G$ 是完全图 $K_4$，其点连通度是多少？
查看练习答案与解析
答案：3。
解析：完全图 $K_n$ 的点连通度为 $n-1$。
二、判断题（20 分，每题 2 分）
- $\neg Q \lor P \Leftrightarrow P \to Q$ （ ）
查看答案与解析
答案：F
解析：根据蕴涵等值式，$P \to Q \equiv \neg P \lor Q$。而题目给出的 $\neg Q \lor P \equiv Q \to P$。
难度：⭐
考点：#蕴涵等值式
💡 学习锦囊
📖 相关公式：$P \to Q \equiv \neg P \lor Q$。
思路分析
注意 $P$ 和 $Q$ 的位置，蕴涵式不满足交换律。
🔄 举一反三
- $\neg P \lor Q \Leftrightarrow P \to Q$。
查看练习答案与解析
答案：T。
- 命题函数是命题。 （ ）
查看答案与解析
答案：F
解析：命题函数含有变元，其真值不确定。只有当变元被具体值取代或被量词约束后，才成为命题。
难度：⭐
考点：#命题定义
💡 学习锦囊
思路分析
命题必须有确定的真值（非真即假）。
🔄 举一反三
- “$x > 5$”是一个命题。
查看练习答案与解析
答案：F。
解析：真值取决于 $x$ 的值。
- $\emptyset = \{x \mid P(x) \land \neg P(x)\}$，其中 $P(x)$ 是任意谓词。 （ ）
查看答案与解析
答案：T
解析：$P(x) \land \neg P(x)$ 是一对矛盾式，其真值永远为假。因此没有任何元素能满足该条件，集合为空。
难度：⭐
考点：#空集 #矛盾式
💡 学习锦囊
📖 相关公式：矛盾律：$A \land \neg A \equiv \text{False}$。
🔄 举一反三
- $\{x \mid P(x) \lor \neg P(x)\}$ 等于全集。
查看练习答案与解析
答案：T。
- $A$ 和 $B$ 为两个不相等的非空集合，则一定有 $A \times B \neq B \times A$。 （ ）
查看答案与解析
答案：T
解析：笛卡尔积满足交换律当且仅当 $A=B$ 或其中一个为空集。题目条件排除了这些情况。
难度：⭐
考点：#笛卡尔积性质
💡 学习锦囊
📖 相关公式：$A \times B = B \times A \iff A = B \lor A = \emptyset \lor B = \emptyset$。
🔄 举一反三
- 若 $A = \{1\}, B = \{1, 2\}$，则 $A \times B = B \times A$ 是否成立？
查看练习答案与解析
答案：不成立。
- 若 $R$ 为集合 $A$ 上的关系，且 $R$ 不是对称的，则 $R$ 一定是反对称的。 （ ）
查看答案与解析
答案：F
解析：对称与反对称不是对立关系。有些关系既不对称也不反对称，如 $R = \{\langle 1,2 \rangle, \langle 2,1 \rangle, \langle 1,3 \rangle\}$。
难度：⭐
考点：#关系的性质
💡 学习锦囊
思路分析
关系性质的判定通常需要通过定义逐项核对，不能通过“否定 A”推导出“肯定 B”。
🔄 举一反三
- 恒等关系 $I_A$ 既是对称的又是反对称的。
查看练习答案与解析
答案：T。
- 无向完全图 $K_n (n > 2)$ 一定是汉密尔顿图。 （ ）
查看答案与解析
答案：T
解析：$K_n$ 的每个顶点的度数为 $n-1$。对于 $n > 2$，$n-1 \geq n/2$ 恒成立。根据 Dirac 定理，它是汉密尔顿图。
难度：⭐
考点：#汉密尔顿图 #完全图
💡 学习锦囊
📖 相关公式：Dirac 定理：对于 $n \geq 3$ 的简单图，若所有顶点的度数 $d(v) \geq n/2$，则该图是汉密尔顿图。
🔄 举一反三
- $K_2$ 是汉密尔顿图吗？
查看练习答案 with 解析
答案：不是。
解析：不满足 $n \geq 3$ 的前提。
- 在代数系统中，若元素 $a$ 既有左逆元，又有右逆元，则 $a$ 一定有逆元。 （ ）
查看答案与解析
答案：T
解析：在满足结合律的情况下（代数系统讨论逆元通常默认为半群或群），设左逆为 $a_L$，右逆为 $a_R$，则 $a_L = a_L(aa_R) = (a_La)a_R = a_R$。两者相等，故存在唯一逆元。
难度：⭐⭐
考点：#逆元存在性
💡 学习锦囊
思路分析
利用结合律进行“左移右移”证明是代数中的经典技巧。
🔄 举一反三
- 若 $a$ 的左逆不等于右逆，说明该系统不满足什么律？
查看练习答案与解析
答案：结合律。
- 存在不同构的 8 元布尔格。 （ ）
查看答案与解析
答案：F
解析：有限布尔格的阶必为 $2^n$。所有同阶（如 8 元，$2^3$）的有限布尔格都是同构的。
难度：⭐⭐
考点：#布尔格同构
💡 学习锦囊
📖 相关公式：阶数为 $2^n$ 的布尔格只有一个同构类。
🔄 举一反三
- 存在多少个不同构的 2 元布尔格？
查看练习答案与解析
答案：1 个。
- 有补格一定是有界格且每个元素都存在一个或多个补元。 （ ）
查看答案与解析
答案：T
解析：这正是“有补格”定义的直接表述。
难度：⭐
考点：#有补格定义
💡 学习锦囊
📖 相关公式：有补格 $\iff$ 有界格 $\land$ $\forall a \exists a' (a \lor a' = I \land a \land a' = 0)$。
🔄 举一反三
- 在布尔格中，补元是唯一的吗？
查看练习答案与解析
答案：是。
解析：因为布尔格还是分配格。
- 结点的度全为偶数的无向简单图一定可以一笔画。 （ ）
查看答案与解析
答案：F
解析：欧拉回路（一笔画且回到原点）的充要条件是：图连通且所有顶点的度数均为偶数。题目缺少"连通"这一前提条件。反例：两个不相交的三角形（$C_3 \cup C_3$），每个顶点度数均为 2（偶数），但图不连通，无法一笔画。
难度：⭐⭐
考点：#欧拉图 #连通性
💡 学习锦囊
📖 相关公式：欧拉回路充要条件：连通且所有顶点度数为偶数。欧拉路径充要条件：连通且恰有 0 个或 2 个奇度顶点。
易错点
判断欧拉图时，连通性是容易被忽略的前提条件。务必先检查图的连通性。
🔄 举一反三
- 具有 2 个奇度顶点的连通图能否一笔画？
查看练习答案与解析
答案：可以。
解析：从一个奇度点出发，终点为另一个奇度点。 - 一个连通图中所有顶点度数均为偶数，该图是否一定是欧拉图？
查看练习答案与解析
答案：是。
解析：连通 + 全偶度 = 欧拉图，这是充要条件。
三、解答题（40 分，每题 10 分）
- 已知命题公式 $A = \neg (P \to Q) \lor (P \lor Q)$ （1）请写出该命题公式的真值表。 （2）请求出该命题公式的主合取范式及主析取范式。
查看答案与解析
答案： （1）真值表：
| $P$ | $Q$ | $P \to Q$ | $\neg(P \to Q)$ | $P \lor Q$ | A |
|---|---|---|---|---|---|
| T | T | T | F | T | T |
| T | F | F | T | T | T |
| F | T | T | F | T | T |
| F | F | T | F | F | F |
（2）
- 主析取范式：$(P \land Q) \lor (P \land \neg Q) \lor (\neg P \land Q)$ 或 $\sum(1, 2, 3)$。
- 主合取范式：$P \lor Q$ 或 $M_0$。
解析：
- 真值表计算：
- 公式 $\neg(P \to Q)$ 在 $P=T, Q=F$ 时为 T，其余为 F。
- 公式 $P \lor Q$ 在除 $P=F, Q=F$ 外均为 T。
- 最终两部分进行析取（或运算），仅在 $P=F, Q=F$ 时为 F。
- 范式提取：
- 主析取：取真值为 T 的行。
- 主合取：取真值为 F 的行并取反（极大项格式）。
难度：⭐⭐
考点：#真值表 #范式转换
💡 学习锦囊
📖 相关公式：
- $P \to Q \equiv \neg P \lor Q$
- 极小项 $m_i$ 与 极大项 $M_i$。
思路分析
先求出真值表，再直接按规则写范式，比通过等值演算推导要稳健得多。
🔄 举一反三
- 求 $P \oplus Q$ 的主合取范式。
查看练习答案与解析
答案：$(\neg P \lor \neg Q) \land (P \lor Q)$。
解析：$P, Q$ 同号时真值为 F，异号时为 T。
- $A = \{1, 2, 3, 6, 12\}$，$R$ 是 $A$ 上的整除关系。 （1）请写出关系 $R$。 （2）请画出关系 $R$ 的哈斯图。 （3）请写出 $B = \{2, 3, 6\}$ 的极大元、最小元、上确界、下界。
查看答案与解析
答案： （1）$R = \{\langle 1,1 \rangle, \langle 2,2 \rangle, \langle 3,3 \rangle, \langle 6,6 \rangle, \langle 12,12 \rangle, \langle 1,2 \rangle, \langle 1,3 \rangle, \langle 1,6 \rangle, \langle 1,12 \rangle, \langle 2,6 \rangle, \langle 2,12 \rangle, \langle 3,6 \rangle, \langle 3,12 \rangle, \langle 6,12 \rangle\}$
（2）哈斯图：
graph BT
1((1)) --> 2((2))
1 --> 3((3))
2 --> 6((6))
3 --> 6
6 --> 12((12))（3）
- 极大元：6（$B$ 中没有任何元素整除 6 且不等于 6）。
- 最小元：无（2 和 3 都是极小元，且两者互不整除）。
- 上确界：6（$B$ 的上界集为 $\{6, 12\}$，其中最小者为 6）。
- 下界：1（唯一能同时整除 2, 3, 6 的 $A$ 中元素）。
解析：
- 关系列举：遵循 $x$ 整除 $y$ 的定义。
- 哈斯图绘制：反映覆盖关系。注意 1 是最小值，12 是最大值。
- 元项判定：注意子集的极小元如果不仅一个，则没有最小元。
难度：⭐⭐
考点：#偏序关系 #哈斯图 #格论
💡 学习锦囊
📖 相关公式：
- 哈斯图：省去自环、传递边，并将方向朝上。
- 上确界：最小的上界。
思路分析
哈斯图是解决此类题目最直观的工具，画好图后，极大极小元一目了然。
🔄 举一反三
- 同样的集合 $A$ 下，求子集 $\{1, 2\}$ 的下确界。
查看练习答案与解析
答案：1。
- 集合 $A = \{\emptyset, \{a\}, \{b\}, \{a, b\}, \{b, c\}, \{a, b, c\}\}$，$R$ 为 $A$ 中包含关系。 （1）求 $\{a\}$ 的补元。 （2）求 $(\{a\} \lor \{b\}) \land \{b, c\}$。 （3）求 $(\{a\} \land \{b, c\}) \lor (\{b\} \land \{b, c\})$。 （4）该有界格是否为分配格？是否为有补格？
查看答案与解析
答案： （1）$\{b, c\}$ （2）$\{b\}$ （3）$\{b\}$ （4）是分配格；不是有补格。
解析：
- 补元计算：补元 $x$ 需满足 $\{a\} \cup x = \{a, b, c\}$ 且 $\{a\} \cap x = \emptyset$。观察集合 $A$，$\{b, c\}$ 符合此要求。
- 运算 (2)：$\{a\} \lor \{b\} = \{a, b\}$；$\{a, b\} \land \{b, c\} = \{b\}$。
- 运算 (3)：$\{a\} \land \{b, c\} = \emptyset$；$\{b\} \land \{b, c\} = \{b\}$；$\emptyset \lor \{b\} = \{b\}$。
- 格性质分析：
- 分配格：根据 (2) 和 (3) 相等，且经全量检查不含钻石格 $M_3$ 或五角格 $N_5$。
- 有补格：检查元素 $\{b\}$，其补元需满足与 $\{b\}$ 的交为空，即补元必须 $\subseteq \{a, c\}$。在 $A$ 中仅有 $\emptyset$ 和 $\{a\}$ 满足条件。但这两者与 $\{b\}$ 的并集都无法达到全集 $\{a, b, c\}$。故 $\{b\}$ 无补元。
难度：⭐⭐⭐
考点：#补元 #分配格 #有补格判定
💡 学习锦囊
📖 相关公式：
- 分配律：$x \land (y \lor z) = (x \land y) \lor (x \land z)$。
- 补元存在的两个条件：并为 I，交为 0。
🔄 举一反三
- 若格 $L$ 是分配格且每个元素都有补元，则 $L$ 叫什么？
查看练习答案与解析
答案：布尔格。
- 有向图 $G = \langle V, E \rangle$ 如图 2 所示，请给出下列问题的答案： （1）写出图 $G$ 的邻接矩阵 $A$。 （2）通过矩阵运算求出图 $G$ 对应的可达性矩阵 $P$。
图 2
查看答案与解析
答案： （1）邻接矩阵 $A$：
（2）可达性矩阵 $P$：
解析：
- 邻接矩阵：直接根据图中箭头的起始与指向进行填充。
- 可达性判定：
- 观察发现存在回路 $v_1 \to v_3 \to v_2 \to v_1$，且 $v_4$ 与此三点也互达，构成强连通块。强连通块内的点可达阵子块全为 1。
- $v_5$ 作为汇点，被前 4 个点可达。
- 注意对角线元素必须全为 1。
难度：⭐⭐
考点：#邻接矩阵 #可达性矩阵 #强连通
💡 学习锦囊
📖 相关公式：$P = I \lor A \lor A^2 \lor \dots \lor A^{n-1}$。
🔄 举一反三
- 若一个 2 阶图仅有一条边 $v_1 \to v_2$，其可达阵是？
查看练习答案与解析
答案：$\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$。
四、证明题（20 分，每题 10 分）
- 请根据给定原子命题翻译下列前提和结论，并运用命题逻辑推理理论证明结论。 $P$：小张努力工作。$Q$：小李高兴。$R$：小陈高兴。$S$：小赵高兴。 前提：如果小张努力工作，那么小李或小陈高兴。 如果小陈高兴，那么小赵高兴。 如果小赵高兴，那么小张不努力工作。 结论：如果小张努力工作，则小李高兴。
查看答案与解析
答案： 翻译：
- 前提：$P \to (Q \lor R), R \to S, S \to \neg P$
- 结论：$P \to Q$
证明： (1) $P$ （附加前提） (2) $P \to (Q \lor R)$ （前提） (3) $Q \lor R$ （分离规则 (1)(2)） (4) $R \to S$ （前提） (5) $S \to \neg P$ （前提） (6) $R \to \neg P$ （假言三段论 (4)(5)） (7) $P \to \neg R$ （等值演算 (6)） (8) $\neg R$ （分离规则 (1)(7)） (9) $Q$ （析取三段论 (3)(8)） (10) $P \to Q$ （CP 规则 (1)-(9) 得证）
难度：⭐⭐
考点：#命题推理理论 #CP规则
💡 学习锦囊
📖 相关公式：
- 假言三段论：$(A \to B) \land (B \to C) \Rightarrow A \to C$。
- 析取三段论：$(A \lor B) \land \neg A \Rightarrow B$。
🔄 举一反三
- 证明 $P \lor Q, \neg P \vdash Q$。
查看练习答案 with 解析
解析：直接应用析取三段论。
- 已知集合 $A \neq \emptyset$，$P(A)$ 是 $A$ 的幂集，试证明代数系统 $\langle P(A), \oplus \rangle$ 是阿贝尔群。
查看答案与解析
答案： 证明：
- 封闭性：对于任意 $X, Y \in P(A)$，$X \oplus Y = (X-Y) \cup (Y-X) \in P(A)$。
- 结合律：依据集合运算性质，对称差满足 $(X \oplus Y) \oplus Z = X \oplus (Y \oplus Z)$。
- 幺元：存在 $\emptyset \in P(A)$，使得 $X \oplus \emptyset = X$。
- 逆元：对于任意 $X \in P(A)$，其逆元为 $X$ 本身，即 $X \oplus X = \emptyset$。
- 交换律：$X \oplus Y = Y \oplus X$。 综上所述，它是阿贝尔群。
难度：⭐⭐
考点：#群论证明 #对称差
💡 学习锦囊
📖 相关公式：群的四要素：封闭、结合、幺元、逆元。
思路分析
对称差是一个特殊的运算，它让集合的幂集构成一个布尔环，其加法部分正是阿贝尔群。
🔄 举一反三
- 在该群中，每个元素的阶是多少？
查看练习答案与解析
答案：2（除幺元外）。
解析：因为 $X \oplus X = \emptyset$。