《离散数学》第一学期期末试卷A (精选05)
一、填空题（本大题共 10 小题，每题 3 分，共 30 分）
- 命题公式 $(\neg p \wedge q) \rightarrow \neg r$ 在赋值 $011$ 下的真值为 ________。
查看答案与解析
答案：$0$
解析： 本题考查命题公式真值的计算。
- 识别赋值：赋值 $011$ 表示变量的取值为：$p=0, q=1, r=1$。
- 代入公式：
- 首先计算括号内：$\neg p \wedge q = \neg 0 \wedge 1 = 1 \wedge 1 = 1$。
- 计算后件：$\neg r = \neg 1 = 0$。
- 最终运算：$(\neg p \wedge q) \rightarrow \neg r = 1 \rightarrow 0 = 0$。
根据蕴涵式 $1 \rightarrow 0$ 为假的定义，最终结果为 $0$。
难度: ⭐ 考点: #命题逻辑 #真值计算 #蕴涵式
💡 学习锦囊
📖 相关公式与知识点:
- 蕴涵运算 $P \rightarrow Q$：仅当 $P$ 为真且 $Q$ 为假时，结果为 $0$；其余情况均为 $1$。
- 否定 $\neg$、合取 $\wedge$ 的基本真值表。
思路分析
遇到此类题目，直接将给定的二进制序列按顺序对应命题变项，依次计算各层逻辑联结词的结果即可。注意运算优先级：括号 > $\neg$ > $\wedge, \vee$ > $\rightarrow$。
🔄 举一反三
- 求 $(p \vee q) \leftrightarrow \neg r$ 在 $101$ 下的真值。
查看练习答案与解析
答案：$0$解析：$p=1, q=0, r=1 \Rightarrow (1 \vee 0) \leftrightarrow \neg 1 = 1 \leftrightarrow 0 = 0$。
- 含 3 个命题变项的命题公式的主合取范式为 $M_0 \wedge M_3 \wedge M_4 \wedge M_6 \wedge M_7$ ，则它的主析取范式为 ________。（表示成 $m_1 \vee m_2 \vee m_5$ 的形式）
查看答案与解析
答案：$m_1 \vee m_2 \vee m_5$
解析： 本题考查主析取范式（PDNF）与主合取范式（PCNF）的互补关系。
- 确定全集：含有 3 个命题变项的公式，其极小项和极大项的下标范围均为 $0 \sim 2^3 - 1$，即 $0, 1, 2, 3, 4, 5, 6, 7$。
- 互补原理：若公式的主合取范式由下标集 $I$ 中的极大项组成，则其主析取范式必由下标集 $\{0, 1, \dots, 7\} \setminus I$ 中的极小项组成。
- 计算补集：已知 PCNF 的下标集为 $\{0, 3, 4, 6, 7\}$。 则 PDNF 的下标集为 $\{0, 1, 2, 3, 4, 5, 6, 7\} \setminus \{0, 3, 4, 6, 7\} = \{1, 2, 5\}$。
- 得出结论：其主析取范式为 $m_1 \vee m_2 \vee m_5$。
难度: ⭐ 考点: #主范式 #主析取范式 #主合取范式 #极小项
💡 学习锦囊
📖 相关公式与知识点:
- $A \equiv \sum m_i \equiv \prod M_j$，其中 $i \notin \{j\}$。
- 极小项 $m_i$ 对应真值为 $1$ 的行，极大项 $M_i$ 对应真值为 $0$ 的行。
思路分析
主范式之间的转换只需关注下标。所有的极小项和极大项共同构成了真值表的所有行。公式主范式中缺失的下标，就是其对偶主范式所包含的下标。
🔄 举一反三
- 若主析取范式为 $m_0 \vee m_1$，求主合取范式（3 变项）。
查看练习答案与解析
答案：$M_2 \wedge M_3 \wedge M_4 \wedge M_5 \wedge M_6 \wedge M_7$解析：排除下标 0 和 1 即可。
- “有的学生学习努力”符号化为 __________。（设 $P(x)$：$x$ 是学生；$Q(x)$：$x$ 学习努力）
查看答案与解析
答案：$\exists x (P(x) \wedge Q(x))$
解析： 本题考查谓词逻辑的符号化。
- 识别量词：关键词“有的”对应存在量词 $\exists$。
- 确定逻辑关系：在谓词逻辑符号化中，存在量词通常与合取联结词 $\wedge$ 搭配使用，表示“存在一个个体，既满足 $P$ 又满足 $Q$”。
- 组合公式：$\exists x (P(x) \wedge Q(x))$。
难度: ⭐ 考点: #谓词逻辑 #符号化 #存在量词
💡 学习锦囊
📖 相关公式与知识点:
- “所有 A 都是 B” $\rightarrow \forall x (A(x) \rightarrow B(x))$
- “有的 A 是 B” $\rightarrow \exists x (A(x) \wedge Q(x))$
易错点
初学者常将“有的”误用蕴涵式符号化为 $\exists x (P(x) \rightarrow Q(x))$。实际上，该式在 $P(x)$ 为假时恒真，不能表达“有的学生”这一含义。
🔄 举一反三
- 将“所有学生都不及格”符号化（$P(x)$：学生，$S(x)$：及格）。
查看练习答案与解析
答案：$\forall x (P(x) \rightarrow \neg S(x))$解析：全称量词搭配蕴涵项，且结论是否定的。
- $A = \{a, b, c\}$，则 $A$ 的幂集 $P(A) = $ __________。
查看答案与解析
答案：$\{\emptyset, \{a\}, \{b\}, \{c\}, \{a, b\}, \{a, c\}, \{b, c\}, \{a, b, c\}\}$
解析： 本题考查幂集的定义。
- 理解幂集：集合 $A$ 的幂集 $P(A)$ 是以 $A$ 的所有子集为元素的集合。
- 枚举子集：
- 空集：$\emptyset$
- 单元素子集：$\{a\}, \{b\}, \{c\}$
- 双元素子集：$\{a, b\}, \{a, c\}, \{b, c\}$
- 三元素子集（自身）：$\{a, b, c\}$
- 计算元素个数：若 $|A| = n$，则 $|P(A)| = 2^n$。此处 $n=3$，元素数应为 $2^3 = 8$。
难度: ⭐ 考点: #集合论 #幂集 #子集
💡 学习锦囊
📖 相关公式与知识点:
- $P(A) = \{ S \mid S \subseteq A \}$
- 注意空集 $\emptyset$ 和集合本身 $A$ 总是幂集的元素。
思路分析
书写幂集时，建议按照子集元素的个数从小到大排列，即从 0 元集（空集）一直写到 $n$ 元集（自身），这样可以避免遗漏。
🔄 举一反三
- 若 $A = \{ \emptyset, 1 \}$，求 $P(A)$。
查看练习答案与解析
答案：$\{\emptyset, \{\emptyset\}, \{1\}, \{\emptyset, 1\}\}$解析：元素分别为 $\emptyset$ 和 $1$，构造子集即可。
- 设 $R$ 是 $A$ 上的二元关系，若 $R$ 是自反的、对称的和传递的，则 $R$ 是 $A$ 上的等价关系的条件。
查看答案与解析
答案：充分必要条件
解析： 本题考查等价关系的定义。
- 回顾定义：在集合 $A$ 上的二元关系 $R$ 称为 等价关系，当且仅当它满足以下三个性质：
- 自反性：$\forall x \in A, \langle x, x \rangle \in R$。
- 对称性：$\forall x, y \in A, \langle x, y \rangle \in R \implies \langle y, x \rangle \in R$。
- 传递性：$\forall x, y, z \in A, (\langle x, y \rangle \in R \wedge \langle y, z \rangle \in R) \implies \langle x, z \rangle \in R$。
- 逻辑关系：根据定义，满足这三个性质是作为等价关系的定义性要求，因此是充要条件。
难度: ⭐ 考点: #关系 #等价关系 #自反性 #对称性 #传递性
💡 学习锦囊
📖 相关公式与知识点:
- 等价关系的重要意义在于它可以导出一个 划分（Partition）。
- 等价类：$[x]_R = \{ y \mid \langle x, y \rangle \in R \}$。
思路分析
这是离散数学中的核心定义之一。掌握三种性质的判断方法（关系矩阵、关系图或逻辑表达式）是解题的关键。
- $A = \{1, 2, 3\}$，$S = \{\langle 1, 2 \rangle, \langle 2, 1 \rangle, \langle 3, 3 \rangle\}$，$R = \{\langle 1, 3 \rangle, \langle 2, 2 \rangle, \langle 3, 2 \rangle\}$，则 $S \circ R =$ __________。
查看答案与解析
答案：$\{\langle 1, 2 \rangle, \langle 2, 3 \rangle, \langle 3, 2 \rangle\}$
解析： 本题考查关系的复合运算。
- 定义：$S \circ R = \{ \langle x, z \rangle \mid \exists y (\langle x, y \rangle \in S \wedge \langle y, z \rangle \in R) \}$。注意运算顺序是从 $S$ 到 $R$。
- 逐元寻找中间项：
- 对于 $S$ 中的 $\langle 1, 2 \rangle$：寻找 $R$ 中以 $2$ 开头的序偶，找到 $\langle 2, 2 \rangle$，得到结果 $\langle 1, 2 \rangle$。
- 对于 $S$ 中的 $\langle 2, 1 \rangle$：寻找 $R$ 中以 $1$ 开头的序偶，找到 $\langle 1, 3 \rangle$，得到结果 $\langle 2, 3 \rangle$。
- 对于 $S$ 中的 $\langle 3, 3 \rangle$：寻找 $R$ 中以 $3$ 开头的序偶，找到 $\langle 3, 2 \rangle$，得到结果 $\langle 3, 2 \rangle$。
- 汇总：$S \circ R = \{\langle 1, 2 \rangle, \langle 2, 3 \rangle, \langle 3, 2 \rangle\}$。
难度: ⭐⭐ 考点: #关系 #复合运算
💡 学习锦囊
📖 相关公式与知识点:
- 关系矩阵表示：$M_{S \circ R} = M_S \odot M_R$（布尔乘法）。
- 复合运算满足结合律，但不满足交换律。
易错点
注意复合运算的顺序。不同教材对 $S \circ R$ 的定义顺序可能不同（有的先做左边有的先做右边），本题采用常规定义：先执行 $S$ 再执行 $R$。
- 设公式 $A(x)$ 含自由出现的个体变项 $x$，$B$ 不含 $x$ 的出现，则由量词收缩与扩张等值式 $\forall x (A(x) \rightarrow B) \Leftrightarrow$ __________。
查看答案与解析
答案：$(\exists x A(x)) \rightarrow B$
解析： 本题考查量词的收缩与扩张等值式。
- 转化含义：$\forall x (A(x) \rightarrow B) 意为“对于所有的 $x$，如果 $A(x)$ 成立，则 $B$ 成立”。
- 逻辑推导： $\forall x (A(x) \rightarrow B) \equiv \forall x (\neg A(x) \vee B)$ 由于 $B$ 不含 $x$，可以将全称量词移入内层（分配律）： $\forall x (\neg A(x) \vee B) \equiv (\forall x \neg A(x)) \vee B$ 利用德·摩根律（量词否定转换）： $(\forall x \neg A(x)) \vee B \equiv \neg (\exists x A(x)) \vee B$ 再次转换回蕴涵式： $\neg (\exists x A(x)) \vee B \equiv (\exists x A(x)) \rightarrow B$
- 结论：等值式为 $(\exists x A(x)) \rightarrow B$。
难度: ⭐⭐ 考点: #谓词逻辑 #等值式 #量词扩张
💡 学习锦囊
📖 相关公式与知识点:
- $\forall x (A(x) \vee B) \Leftrightarrow (\forall x A(x)) \vee B$
- $\exists x (A(x) \wedge B) \Leftrightarrow (\exists x A(x)) \wedge B$
- 特别注意：全称量词在蕴涵式前件时，转换后变为存在量词。
思路分析
“全称变存在”是因为蕴涵项的前件带有隐藏的否定。只要记住 $\forall x (A \rightarrow B) \equiv (\exists x A) \rightarrow B$ 和 $\exists x (A \rightarrow B) \equiv (\forall x A) \rightarrow B$ 这两个最容易出错的公式即可。
- $T = \{ x \mid x \text{ 是单词 “student” 中的字母} \}$，则 $T$ 的基数为 ________。
查看答案与解析
答案：$6$
解析： 本题考查集合的描述法与基数（势）的概念。
- 解析集合元素：单词 “student” 中包含的字母有：s, t, u, d, e, n, t。
- 集合的互异性：根据集合定义，元素必须互不相同。字母 't' 出现了两次，只能计入一次。 因此，$T = \{s, t, u, d, e, n\}$。
- 计算基数：$|T| = 6$。
难度: ⭐ 考点: #集合 #基数 #元素互异性
💡 学习锦囊
📖 相关公式与知识点:
- 有限集的基数即为集合中不同元素的个数。
思路分析
看到此类题目，一定要注意检查重复元素，集合中重复的元素在计算大小时只能算一个。
- 设在有向图 $G$ 中顶点的度数之和为 $n$，边数为 $m$，则 $n$ 和 $m$ 的关系为 ________。
查看答案与解析
答案：$n = 2m$
解析： 本题考查图论中的基本定理——握手定理（Handshaking Lemma）。
- 基本原理：在任何图中，每一条边都有两个端点，因此在计算所有顶点的度数之和时，每一条边都被计算了两次。
- 公式表达：$\sum_{v \in V} d(v) = 2|E|$。
- 结论：题目给定度数之和为 $n$，边数为 $m$，故 $n = 2m$。
难度: ⭐ 考点: #图论 #握手定理 #顶点度数
💡 学习锦囊
📖 相关公式与知识点:
- 对于有向图，所有顶点的入度之和 = 所有顶点的出度之和 = 边数 $m$。
- 度数之和 = 入度之和 + 出度之和 = $m + m = 2m$。
思路分析
握手定理是图论的基石。无论是无向图还是有向图，总度数一定是边数的两倍。
- 一棵无向树 $T$ 有 5 片树叶，3 个 2 度分支点，其余的分支点都是 3 度顶点，则 $T$ 的顶点个数为 ________。
查看答案与解析
答案：$11$
解析： 本题考查树的性质及度数平衡公式。
- 设变量：设 3 度顶点的个数为 $k$。则总顶点数 $n = 5 + 3 + k = 8 + k$。
- 利用树的边数公式：树的边数 $m = n - 1 = (8 + k) - 1 = 7 + k$。
- 应用握手定理：度数之和 = $2 \times$ 边数。
- 度数之和 = $5 \times 1 + 3 \times 2 + k \times 3 = 11 + 3k$。
- $2 \times$ 边数 = $2 \times (7 + k) = 14 + 2k$。
- 解方程： $11 + 3k = 14 + 2k$$k = 3$。
- 计算总顶点数：$n = 8 + 3 = 11$。
难度: ⭐⭐ 考点: #树 #顶点度数 #树的性质
💡 学习锦囊
📖 相关公式与知识点:
- 树的边数 $m = n - 1$。
- 叶子节点度数为 1。
- $\sum d(v) = 2(n-1)$。
思路分析
对于树的度数问题，最稳妥的方法就是设未知数，利用“度数和等于边数两倍”以及“边数等于顶点数减一”建立方程求解。
二、解答题（本大题共 7 小题，每题 10 分，共 70 分）
11. 求公式 $(p \rightarrow \neg q) \leftrightarrow r$ 的主析取范式和主合取范式。
查看答案与解析
答案：
- 主析取范式：$m_1 \vee m_3 \vee m_5 \vee m_6$
- 主合取范式：$M_0 \wedge M_2 \wedge M_4 \wedge M_7$
解析： 本题考查主范式的求解方法。
第一步：列出真值表 通过计算所有可能的变项赋值（$2^3=8$ 种），得出公式在各赋值下的真值：
| $p$ | $q$ | $r$ | $p \rightarrow \neg q$ | $(p \rightarrow \neg q) \leftrightarrow r$ | 极小项 | 极大项 |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 0 | - | $M_0$ |
| 0 | 0 | 1 | 1 | 1 | $m_1$ | - |
| 0 | 1 | 0 | 1 | 0 | - | $M_2$ |
| 0 | 1 | 1 | 1 | 1 | $m_3$ | - |
| 1 | 0 | 0 | 1 | 0 | - | $M_4$ |
| 1 | 0 | 1 | 1 | 1 | $m_5$ | - |
| 1 | 1 | 0 | 0 | 1 | $m_6$ | - |
| 1 | 1 | 1 | 0 | 0 | - | $M_7$ |
第二步：提取主范式
- 主析取范式：提取真值为 $1$ 的行对应的极小项。 结果为：$m_1 \vee m_3 \vee m_5 \vee m_6$。
- 主合取范式：提取真值为 $0$ 的行对应的极大项。 结果为：$M_0 \wedge M_2 \wedge M_4 \wedge M_7$。
难度: ⭐⭐⭐ 考点: #主析取范式 #主合取范式 #真值表
💡 学习锦囊
📖 相关公式与知识点:
- $A \equiv \sum m_i$
- $A \equiv \prod M_j$
- 极小项 $m_i$ 的下标 $i$ 等于使其为真的赋值对应的十进制数。
思路分析
真值表法是求主范式最稳健的方法，尤其在变项数量不多（3个及以下）时。注意在写最终结果时，下标一定要从小到大排列。
🔄 举一反三
- 求 $(p \vee q) \rightarrow r$ 的主析取范式。
查看练习答案与解析
答案：$m_0 \vee m_1 \vee m_3 \vee m_5 \vee m_7$解析： 通过真值表或等价演算分析： $(p \vee q) \to r \equiv \neg(p \vee q) \vee r \equiv (\neg p \wedge \neg q) \vee r$
- 当 $p=0, q=0$ 时，无论 $r$ 取何值公式都为真 $\to m_0, m_1$。
- 当 $r=1$ 时，无论 $p, q$ 取何值公式都为真 $\to m_1, m_3, m_5, m_7$。 汇总去重后得到下标：0, 1, 3, 5, 7。
12. 演绎证明：
前提：$\neg q \vee p, r \vee \neg p, r \rightarrow s$ 结论：$q \rightarrow s$
查看答案与解析
证明： 本题采用形式演绎证明，主要利用蕴涵式的转化和传递性质。
- $\neg q \vee p$ (前提)
- $q \rightarrow p$ (由 1 及蕴涵等值式得出)
- $r \vee \neg p$ (前提)
- $\neg p \vee r$ (由 3 交换律)
- $p \rightarrow r$ (由 4 及蕴涵等值式得出)
- $r \rightarrow s$ (前提)
- $q \rightarrow r$ (由 2, 5 假言三段论)
- $q \rightarrow s$ (由 7, 6 假言三段论)
结论得证。
难度: ⭐⭐ 考点: #命题逻辑 #演绎证明 #假言三段论
💡 学习锦囊
📖 相关公式与知识点:
- 蕴涵等值式：$A \rightarrow B \equiv \neg A \vee B$
- 假言三段论（传递律）：$(A \rightarrow B) \wedge (B \rightarrow C) \implies (A \rightarrow C)$
思路分析
观察前提和结论：结论是一个蕴涵式 $q \rightarrow s$。这提示我们尝试建立从 $q$ 到 $s$ 的逻辑链条。通过前提将析取式转化为蕴涵式后，逻辑链条 $q \rightarrow p \rightarrow r \rightarrow s$ 非常清晰，直接应用传递律即可。
🔄 举一反三
- 前提：$p \rightarrow q, \neg r \rightarrow \neg q$，结论：$p \rightarrow r$。
查看练习答案与解析
证明：
- $p \rightarrow q$ (前提)
- $\neg r \rightarrow \neg q \equiv q \rightarrow r$ (等值演算)
- $p \rightarrow r$ (1, 2 假言三段论)
13. 给出 $A = \{a, b, c\}$ 上所有的等价关系。
查看答案与解析
答案： 集合 $A = \{a, b, c\}$ 共有 5 个等价关系，分别对应其 5 个不同的划分：
- 划分 $\pi_1 = \{\{a, b, c\}\}$关系 $R_1 = A \times A$
- 划分 $\pi_2 = \{\{a\}, \{b\}, \{c\}\}$关系 $R_2 = I_A$
- 划分 $\pi_3 = \{\{a, b\}, \{c\}\}$关系 $R_3 = I_A \cup \{ \langle a,b \rangle, \langle b,a \rangle \}$
- 划分 $\pi_4 = \{\{a, c\}, \{b\}\}$关系 $R_4 = I_A \cup \{ \langle a,c \rangle, \langle c,a \rangle \}$
- 划分 $\pi_5 = \{\{b, c\}, \{a\}\}$关系 $R_5 = I_A \cup \{ \langle b,c \rangle, \langle c,b \rangle \}$
解析：
- 原理：集合 $A$ 上的等价关系与 $A$ 的 划分 是一一对应的。
- 操作步骤：
- 列出集合 $A$ 的所有可能划分。
- 对每一个划分，根据“属于同一个子块的元素之间有关系”的原则写出关系集合。
- 注意等价关系必须满足自反性（包含所有对角元）、对称性和传递性。
难度: ⭐⭐⭐ 考点: #等价关系 #划分 #等价类
💡 学习锦囊
📖 相关公式与知识点:
- 贝尔数（Bell Number） $B_n$ 表示 $n$ 元集的划分总数。$B_3 = 5$。
- 划分的性质：各块不为空，交集为空，并集为全集。
思路分析
本题的关键是不要遗漏。建议按划分中子块的数量进行枚举：1个子块（全集）、2个子块（2+1模式，共3种）、3个子块（单元素集模式，共1种）。
🔄 举一反三
- 给出 $A = \{1, 2\}$ 上的所有等价关系。
查看练习答案与解析
答案：
- $R_1 = \{ \langle 1,1 \rangle, \langle 2,2 \rangle \}$ (对应划分 $\{\{1\}, \{2\}\}$)
- $R_2 = \{ \langle 1,1 \rangle, \langle 2,2 \rangle, \langle 1,2 \rangle, \langle 2,1 \rangle \}$ (对应划分 $\{\{1,2\}\}$)
14. $A = \{1, 2, 3, 4\}$，$R = \{\langle 1, 2 \rangle, \langle 2, 1 \rangle, \langle 2, 3 \rangle\}$，求闭包 $r(R), s(R), t(R)$ 及其关系阵、关系图。
查看答案与解析
答案： 1. 自反闭包 $r(R)$$r(R) = R \cup I_A = \{\langle 1, 1 \rangle, \langle 2, 2 \rangle, \langle 3, 3 \rangle, \langle 4, 4 \rangle, \langle 1, 2 \rangle, \langle 2, 1 \rangle, \langle 2, 3 \rangle\}$关系阵 $M_{r(R)} = \begin{bmatrix} 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}$
2. 对称闭包 $s(R)$$s(R) = R \cup R^{-1} = \{\langle 1, 2 \rangle, \langle 2, 1 \rangle, \langle 2, 3 \rangle, \langle 3, 2 \rangle\}$关系阵 $M_{s(R)} = \begin{bmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix}$
3. 传递闭包 $t(R)$$t(R) = R \cup R^2 \cup R^3 = \{\langle 1, 1 \rangle, \langle 1, 2 \rangle, \langle 1, 3 \rangle, \langle 2, 1 \rangle, \langle 2, 2 \rangle, \langle 2, 3 \rangle\}$关系阵 $M_{t(R)} = \begin{bmatrix} 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix}$
关系图描述：
- $r(R)$：在 $R$ 的图基础上，每个顶点增加一个自环。
- $s(R)$：将 $R$ 的所有单向边变为双向边（增加 $\langle 3, 2 \rangle$）。
- $t(R)$：在 $R$ 的图基础上，补齐所有可达路径。
解析：
- 自反闭包：补齐所有对角线元素。
- 对称闭包：补齐所有反向序偶。
- 传递闭包：
- $R = \{\langle 1, 2 \rangle, \langle 2, 1 \rangle, \langle 2, 3 \rangle\}$
- $R^2 = R \circ R = \{\langle 1, 1 \rangle, \langle 2, 2 \rangle, \langle 1, 3 \rangle\}$
- $t(R) = R \cup R^2 = \{\langle 1, 1 \rangle, \langle 1, 2 \rangle, \langle 1, 3 \rangle, \langle 2, 1 \rangle, \langle 2, 2 \rangle, \langle 2, 3 \rangle\}$
难度: ⭐⭐⭐ 考点: #关系闭包 #自反闭包 #对称闭包 #传递闭包 #关系矩阵
💡 学习锦囊
📖 相关公式与知识点:
- $r(R) = R \cup I_A$
- $s(R) = R \cup R^{-1}$
- $t(R) = \bigcup_{i=1}^n R^i$
思路分析
求传递闭包时，注意 1 和 2 构成了一个环，因此 1 可以到达 1, 2, 3，2 也可以到达 1, 2, 3。元素 4 是孤立点。
🔄 举一反三
- 若 $R = \{ \langle 1, 2 \rangle, \langle 2, 3 \rangle \}$，求 $t(R)$。
查看练习答案与解析
答案：$\{ \langle 1, 2 \rangle, \langle 2, 3 \rangle, \langle 1, 3 \rangle \}$解析：添加从 1 经 2 到 3 的传递边。
15. 已知偏序集 $\langle A, R \rangle$ 的哈斯图如下，求 $A$ 和 $R$ 的集合表达式，并指出该偏序集的极大元、极小元、最大元、最小元。
查看答案与解析
答案：
- 集合 $A$：$A = \{1, 2, 3, 4, 5\}$
- 关系 $R$： $R = \{ \langle 1,1 \rangle, \langle 2,2 \rangle, \langle 3,3 \rangle, \langle 4,4 \rangle, \langle 5,5 \rangle, \langle 1,3 \rangle, \langle 1,4 \rangle, \langle 1,5 \rangle, \langle 2,3 \rangle, \langle 2,4 \rangle, \langle 2,5 \rangle, \langle 3,5 \rangle, \langle 4,5 \rangle \}$
- 特殊元分析：
- 极大元：$5$
- 极小元：$1, 2$
- 最大元：$5$
- 最小元：无
解析：
- 读取哈斯图：底部为 1, 2；中间为 3, 4；顶部为 5。
- 构建关系 $R$：根据偏序性质（自反、反对称、传递）补全。
- 判定特殊元：
- $5$ 在最顶层且唯一，是极大元也是最大元。
- $1, 2$ 在最底层且互不可比，均是极小元，故无最小元。
难度: ⭐⭐⭐ 考点: #偏序集 #哈斯图 #极大元 #最小元 #最大元
💡 学习锦囊
📖 相关公式与知识点:
- 极大元/极小元：可能不唯一。
- 最大元/最小元：若存在则必唯一。
思路分析
只要底部有多个互不可比的元素，就一定没有最小元。
🔄 举一反三
- 若哈斯图为一条直线 $1-2-3$（3在顶），指出特殊元。
查看练习答案与解析
答案：
- 最大元/极大元：3
- 最小元/极小元：1
16. 求下图的邻接矩阵并求 $v_2$ 到 $v_4$ 长度为 1, 2, 3, 4 的通路数。
查看答案与解析
答案： 1. 邻接矩阵 $A$$A = \begin{bmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 \end{bmatrix}$
2. 长度为 $k$ 的通路数 通路数对应 $A^k$ 矩阵中第 2 行第 4 列的元素 $(A^k)_{24}$：
- 长度为 1：$0$
- 长度为 2：$1$
- 长度为 3：$2$
- 长度为 4：$4$
解析：
- $A^2 = \begin{bmatrix} 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 2 \end{bmatrix} \implies a_{24}^{(2)} = 1$
- $A^3 = A \times A^2 \implies a_{24}^{(3)} = 2$
- $A^4 = A \times A^3 \implies a_{24}^{(4)} = 4$
难度: ⭐⭐⭐⭐ 考点: #邻接矩阵 #通路数 #矩阵乘法
💡 学习锦囊
📖 相关公式与知识点:
- $A^k$ 的元素 $a_{ij}^{(k)}$ 表示从 $v_i$ 到 $v_j$ 长度为 $k$ 的通路数。
思路分析
邻接矩阵构建要看准箭头。矩阵幂次运算虽然繁琐，但结论可靠。
🔄 举一反三
- 若邻接矩阵为 $\begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}$，求 $v_1$ 到 $v_2$ 长度为 2 的通路数。
查看练习答案与解析
答案：0 解析：$A^2 = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}$，故 $a_{12}^{(2)} = 0$。
17. 在通信中要传输字母 a, b, c, d, e, f, g，它们出现的频率分别为 a: 35%, b: 20%, c: 15%, d: 10%, e: 10%, f: 5%, g: 5%，设计一个传输上述字母的最佳前缀码。
查看答案与解析
答案： 采用 哈夫曼编码：
- a: $11$
- b: $00$
- c: $101$
- d: $010$
- e: $011$
- f: $1000$
- g: $1001$
解析：
- 构建哈夫曼树：从小到大合并。
- 分配编码：左 0 右 1。
- 验证前缀性：没有任何编码是另一个编码的前缀。
难度: ⭐⭐⭐ 考点: #哈夫曼编码 #最优前缀码
💡 学习锦囊
📖 相关公式与知识点:
- 平均码长：$\sum w_i l_i$。
思路分析
贪心合并最小权重。
🔄 举一反三
- 权重为 {1, 2, 3}，求最优编码。
查看练习答案与解析
答案：{0, 10, 11} (或类似) 解析：1 和 2 合并为 3。3 和 3 合并。