Appearance
《离散数学》第一学期期末试卷A (精选01)
一、填空题（本大题共 15 小题，每题 1 分，共 15 分）
- 设集合 $A, B$, 其中 $A = \{1, 2, 3\}, B = \{1, 2\}$, 则 $A - B =$ _____; $\rho(A) - \rho(B) =$ _____。
查看答案与解析
答案： $\{3\}$; $\{\{3\}, \{1, 3\}, \{2, 3\}, \{1, 2, 3\}\}$
解析：
- 求 $A - B$： $A - B$ 表示属于 $A$ 但不属于 $B$ 的元素集合。 $A = \{1, 2, 3\}, B = \{1, 2\} \implies A - B = \{3\}$。
- 求 $\rho(A) - \rho(B)$： $\rho(A)$ 是 $A$ 的幂集，共有 $2^3 = 8$ 个元素：$\{\emptyset, \{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}, \{1, 2, 3\}\}$。 $\rho(B)$ 是 $B$ 的幂集，共有 $2^2 = 4$ 个元素：$\{\emptyset, \{1\}, \{2\}, \{1, 2\}\}$。 $\rho(A) - \rho(B)$ 表示属于 $\rho(A)$ 但不属于 $\rho(B)$ 的子集： $\rho(A) - \rho(B) = \{\{3\}, \{1, 3\}, \{2, 3\}, \{1, 2, 3\}\}$。
难度： ⭐ 考点： #集合运算 #幂集
💡 学习锦囊
📖 相关公式与知识点：
- 集合差运算：$A - B = \{x \mid x \in A \land x \notin B\}$
- 幂集：$\rho(A) = \{S \mid S \subseteq A\}$
思路分析
差集运算就是“去重”，即从前一个集合中去掉后一个集合中出现过的所有元素。对于幂集的差运算，只需列出前者的子集，剔除掉仅包含后者元素的子集即可。
🔄 举一反三
- 设 $A = \{a, b\}, B = \{b\}$, 求 $\rho(A) - \rho(B)$。
查看练习答案与解析
答案： $\{\{a\}, \{a, b\}\}$解析：$\rho(A) = \{\emptyset, \{a\}, \{b\}, \{a, b\}\}$，$\rho(B) = \{\emptyset, \{b\}\}$。 $\rho(A) - \rho(B) = \{\{a\}, \{a, b\}\}$。
- 设有限集合 $A$，$|A| = n$，则 $|\rho(A \times A)| =$ _____。
查看答案与解析
答案： $2^{n^2}$
解析：
- 计算笛卡尔积的大小： $|A \times A| = |A| \cdot |A| = n \cdot n = n^2$。
- 计算幂集的大小： 对于任何有限集合 $S$，其幂集 $|\rho(S)| = 2^{|S|}$。 因此，$|\rho(A \times A)| = 2^{|A \times A|} = 2^{n^2}$。
难度： ⭐ 考点： #笛卡尔积 #幂集大小
💡 学习锦囊
📖 相关公式与知识点：
- 笛卡尔积基数：$|A \times B| = |A| \times |B|$
- 幂集基数：$|\rho(S)| = 2^{|S|}$
思路分析
这类题目通常分两步走：先算出内部集合（笛卡尔积）的元素个数，再应用幂集大小的公式。
🔄 举一反三
- 若 $|A|=3, |B|=2$，求 $|\rho(A \times B)|$。
查看练习答案与解析
答案： $2^6 = 64$解析： $|A \times B| = 3 \times 2 = 6$，故幂集大小为 $2^6 = 64$。
- 设集合 $A = \{a, b\}, B = \{1, 2\}$, 则从 $A$ 到 $B$ 的所有映射是_____，其中双射的是_____。
查看答案与解析
答案： $f_1 = \{(a, 1), (b, 1)\}, f_2 = \{(a, 1), (b, 2)\}, f_3 = \{(a, 2), (b, 1)\}, f_4 = \{(a, 2), (b, 2)\}$; $f_2, f_3$
解析：
- 列出所有映射： 映射要求 $A$ 中的每个元素在 $B$ 中都有唯一的像。 $a$ 可以映到 $1$ 或 $2$（2种选择），$b$ 也可以映到 $1$ 或 $2$（2种选择）。 共有 $2 \times 2 = 4$ 个映射：
- $f_1: a \to 1, b \to 1$
- $f_2: a \to 1, b \to 2$
- $f_3: a \to 2, b \to 1$
- $f_4: a \to 2, b \to 2$
- 确定双射： 双射（一一对应）要求既是单射又是满射。在本题中，意味着 $a$ 和 $b$ 必须映到 $B$ 中不同的元素。 显然 $f_2$ 和 $f_3$ 满足条件。
难度： ⭐⭐ 考点： #映射 #双射
💡 学习锦囊
📖 相关公式与知识点：
- 从 $A$ 到 $B$ 的映射总数：$|B|^{|A|}$
- 双射条件：$|A| = |B|$ 且每个元素映射唯一。
思路分析
映射的关键是“定义域全覆盖，像唯一”。对于小集合，直接穷举所有可能的组合是最稳妥的方法。
🔄 举一反三
- $A=\{1\}, B=\{a, b\}$, 求 $A$ 到 $B$ 的映射。
查看练习答案与解析
答案： $f_1=\{(1,a)\}, f_2=\{(1,b)\}$解析： 1 映到 a 或 b，共 $2^1=2$ 种。
- 已知命题公式 $G = \neg(P \to Q) \land R$, 则 $G$ 的主析取范式是 _____。
查看答案与解析
答案： $P \land \neg Q \land R$ (或 $m_5$)
解析：
- 简化公式： $G = \neg(\neg P \lor Q) \land R$ （利用蕴涵等值式 $P \to Q \equiv \neg P \lor Q$） $G = (P \land \neg Q) \land R$ （利用德·摩根律 and 双重否定律） $G = P \land \neg Q \land R$。
- 转换为主析取范式： 主析取范式是由极小项构成的析取式。 这里的 $G$ 本身就是一个极小项 $P \land \neg Q \land R$。 对应真值表中的解释 $(1, 0, 1)$，下标为 $1 \times 2^2 + 0 \times 2^1 + 1 \times 2^0 = 5$。 故主析取范式为 $m_5$。
难度： ⭐⭐ 考点： #主析取范式 #命题逻辑 #等值演算
💡 学习锦囊
📖 相关公式与知识点：
- 蕴涵等值式：$P \to Q \equiv \neg P \lor Q$
- 极小项 $m_i$：对应真值表第 $i$ 行。
思路分析
求范式的常用方法有：真值表法和等值演算法。对于简单的公式，等值演算速度更快。
🔄 举一反三
- 求 $P \land Q$ 的主析取范式（变元 $P, Q$）。
查看练习答案与解析
答案： $P \land Q$ (或 $m_3$) 解析： 本身已是极小项。
- 设 $G$ 是完全二叉树, $G$ 有 7 个点, 其中 4 个叶点, 则 $G$ 的总度数为 _____，分枝点数为 _____。
查看答案与解析
答案： $12$；$3$
解析：
- 计算总度数： 在任何图中，总度数等于边数的两倍。 树是有 $n$ 个顶点和 $n-1$ 条边的连通图。 $n = 7 \implies$ 边数 $m = 7 - 1 = 6$。 总度数 $= 2 \times 6 = 12$。
- 计算分枝点数： 分枝点（内部节点）是非叶节点。 分枝点数 $= n - \text{叶点数} = 7 - 4 = 3$。
难度： ⭐ 考点： #树的性质 #握手定理 #二叉树
💡 学习锦囊
📖 相关公式与知识点：
- 树的边数公式：$m = n - 1$
- 握手定理：$\sum \text{deg}(v) = 2m$
思路分析
牢记“树的边数比顶点数少1”这一核心性质，配合握手定理即可解决大部分度数问题。
🔄 举一反三
- 一个有 10 个顶点的树，其总度数为多少？
查看练习答案与解析
答案： 18 解析： 边数 $10-1=9$，总度数 $9 \times 2 = 18$。
- 设 $A, B$ 为两个集合, $A = \{1, 2, 4\}, B = \{3, 4\}$, 则 $A \cap B =$ _____; $A \cup B =$ _____; $A - B =$ _____。
查看答案与解析
答案： $\{4\}$; $\{1, 2, 3, 4\}$; $\{1, 2\}$
解析：
- 交集 $A \cap B$：寻找共同元素。 $A$ 和 $B$ 中唯一的共同元素是 $4$。故 $A \cap B = \{4\}$。
- 并集 $A \cup B$：合并所有元素并去重。 $\{1, 2, 4\} \cup \{3, 4\} = \{1, 2, 3, 4\}$。
- 差集 $A - B$：从 $A$ 中去掉属于 $B$ 的元素。 从 $\{1, 2, 4\}$ 中去掉 $4$，剩下 $\{1, 2\}$。
难度： ⭐ 考点： #集合运算 #交并差
💡 学习锦囊
📖 相关公式与知识点：
- $A \cap B = \{x \mid x \in A \land x \in B\}$
- $A \cup B = \{x \mid x \in A \lor x \in B\}$
- $A - B = \{x \mid x \in A \land x \notin B\}$
思路分析
这是最基础的集合运算。注意并集时重复元素只写一次，差集时只关注前一个集合中剩下的部分。
- 设 $R$ 是集合 $A$ 上的等价关系, 则 $R$ 所具有的关系的三个特性是 _____。
查看答案与解析
答案： 自反性、对称性、传递性
解析： 根据等价关系的定义，集合 $A$ 上的关系 $R$ 如果满足：
- 自反性：$\forall a \in A, \langle a, a \rangle \in R$。
- 对称性：$\forall a, b \in A, \langle a, b \rangle \in R \implies \langle b, a \rangle \in R$。
- 传递性：$\forall a, b, c \in A, \langle a, b \rangle \in R \land \langle b, c \rangle \in R \implies \langle a, c \rangle \in R$。 则称 $R$ 为等价关系。
难度： ⭐ 考点： #等价关系 #关系性质
💡 学习锦囊
📖 相关公式与知识点：
- 等价关系 $\iff$ 自反 + 对称 + 传递
- 偏序关系 $\iff$ 自反 + 反对称 + 传递
思路分析
这是基本概念题。建议将“等价关系”与“偏序关系”对比记忆。
- 设命题公式 $G = \neg(P \to (Q \land R))$，则使公式 $G$ 为真的解释有_____。
查看答案与解析
答案： $(1, 0, 0), (1, 0, 1), (1, 1, 0)$ (或 $m_4, m_5, m_6$)
解析：
- 化简公式： $G = \neg(\neg P \lor (Q \land R))$$G = P \land \neg(Q \land R)$$G = P \land (\neg Q \lor \neg R)$
- 寻找真解释： 要使 $G$ 为真，必须满足：
- $P = 1$
- 且 $(\neg Q \lor \neg R) = 1$（即 $Q, R$ 不同时为 1） 满足条件的 $(P, Q, R)$ 组合为：
- $(1, 0, 0)$
- $(1, 0, 1)$
- $(1, 1, 0)$
难度： ⭐⭐ 考点： #真值表 #命题逻辑 #公式解释
💡 学习锦囊
📖 相关公式与知识点：
- $\neg(A \land B) \equiv \neg A \lor \neg B$
- $P \to Q \equiv \neg P \lor Q$
思路分析
化简公式后再分析真值往往比直接列 8 行真值表更快。
- 设集合 $A = \{1, 2, 3, 4\}$, $A$ 上的关系 $R_1 = \{(1, 4), (2, 3), (3, 2)\}, R_2 = \{(2, 1), (3, 2), (4, 3)\}$, 则 $R_1 \circ R_2 =$ _____; $R_2 \circ R_1 =$ _____; $R_1^2 =$ _____。
查看答案 with 解析
答案： $\{(1, 3), (2, 2), (3, 1)\}$; $\{(2, 4), (3, 3), (4, 2)\}$; $\{(2, 2), (3, 3)\}$
解析： 注意：离散数学中复合运算 $R_1 \circ R_2$ 通常定义为 $\langle x, z \rangle \in R_1 \circ R_2 \iff \exists y (\langle x, y \rangle \in R_1 \land \langle y, z \rangle \in R_2)$。
- 计算 $R_1 \circ R_2$：
- $1 \xrightarrow{R_1} 4 \xrightarrow{R_2} 3 \implies (1, 3)$
- $2 \xrightarrow{R_1} 3 \xrightarrow{R_2} 2 \implies (2, 2)$
- $3 \xrightarrow{R_1} 2 \xrightarrow{R_2} 1 \implies (3, 1)$$R_1 \circ R_2 = \{(1, 3), (2, 2), (3, 1)\}$
- 计算 $R_2 \circ R_1$：
- $2 \xrightarrow{R_2} 1 \xrightarrow{R_1} 4 \implies (2, 4)$
- $3 \xrightarrow{R_2} 2 \xrightarrow{R_1} 3 \implies (3, 3)$
- $4 \xrightarrow{R_2} 3 \xrightarrow{R_1} 2 \implies (4, 2)$$R_2 \circ R_1 = \{(2, 4), (3, 3), (4, 2)\}$
- 计算 $R_1^2 = R_1 \circ R_1$：
- $2 \xrightarrow{R_1} 3 \xrightarrow{R_1} 2 \implies (2, 2)$
- $3 \xrightarrow{R_1} 2 \xrightarrow{R_1} 3 \implies (3, 3)$$R_1^2 = \{(2, 2), (3, 3)\}$
难度： ⭐⭐ 考点： #关系复合 #幂关系
💡 学习锦囊
📖 相关公式与知识点：
- $R \circ S = \{\langle x, z \rangle \mid \exists y (\langle x, y \rangle \in R \land \langle y, z \rangle \in S)\}$
思路分析
复合运算就像“跳跳棋”，从 $x$ 经过中转站 $y$ 到达 $z$。建议画出简易图示辅助分析。
- 设有限集 $A, B$, $|A| = m, |B| = n$，则 $|\rho(A \times B)| =$ _____。
查看答案与解析
答案： $2^{mn}$
解析：
- 笛卡尔积大小：$|A \times B| = |A| \cdot |B| = m \cdot n = mn$。
- 幂集大小：任何集合 $S$ 的幂集 $\rho(S)$ 的元素个数为 $2^{|S|}$。 因此，$|\rho(A \times B)| = 2^{mn}$。
难度： ⭐ 考点： #笛卡尔积 #幂集基数
💡 学习锦囊
📖 相关公式与知识点：
- $|A \times B| = |A| \cdot |B|$
- $|\rho(S)| = 2^{|S|}$
思路分析
这题考查的是基本基数公式的嵌套应用，非常直接。
- 设 $A, B, R$ 是三个集合, 其中 $R$ 是实数集, $A = \{x \mid -1 \leq x \leq 1, x \in R\}, B = \{x \mid 0 \leq x < 2, x \in R\}$, 则 $A - B =$ _____; $A \cap B =$ _____。
查看答案与解析
答案： $[-1, 0)$; $[0, 1]$
解析：
- 交集 $A \cap B$： $A = [-1, 1], B = [0, 2)$。 寻找两区间的重合部分：$0 \leq x \leq 1$。 故 $A \cap B = [0, 1]$。
- 差集 $A - B$： 从 $A$ 中扣除 $B$ 的部分。 $A$ 的范围是 $[-1, 1]$，其中 $[0, 1]$ 属于 $B$。 扣除后剩下 $[-1, 0)$。注意 $0$ 在 $B$ 中，所以被扣除了，变为开区间。
难度： ⭐⭐ 考点： #集合运算 #实数区间
💡 学习锦囊
📖 相关公式与知识点：
- 闭区间 $[a, b]$，左闭右开 $[a, b)$。
- 差集对端点的影响：扣除闭区间端点变开，扣除开区间端点变闭。
思路分析
处理实数集合建议在数轴上画图，端点的开闭性是这类题目的核心得分点。
- 设命题公式 $G = (P \land Q) \lor (P \land \neg Q)$，则 $G$ 的等值简式为 _____。 (注：原卷缺12题，此处补充)
查看答案与解析
答案： $P$
解析： 利用分配律逆向提取： $G = P \land (Q \lor \neg Q)$ 由于 $Q \lor \neg Q \equiv T$（排中律）， 则 $G = P \land T \equiv P$。
难度： ⭐ 考点： #等值演算 #分配律
💡 学习锦囊
📖 相关公式与知识点：
- 分配律：$A \land (B \lor C) \equiv (A \land B) \lor (A \land C)$
- 同一律：$A \land T \equiv A$ :::
- 设集合 $A = \{2, 3, 4, 5, 6\}, R$ 是 $A$ 上的整除, 则 $R$ 以集合形式（列举法）记为 _____。
查看答案与解析
答案： $\{\langle 2, 2 \rangle, \langle 2, 4 \rangle, \langle 2, 6 \rangle, \langle 3, 3 \rangle, \langle 3, 6 \rangle, \langle 4, 4 \rangle, \langle 5, 5 \rangle, \langle 6, 6 \rangle\}$
解析： 整除关系 $R$ 定义为：$\langle x, y \rangle \in R \iff y$ 能被 $x$ 整除。 遍历 $A$ 中的元素对：
- $2$ 整除：$2, 4, 6$
- $3$ 整除：$3, 6$
- $4$ 整除：$4$
- $5$ 整除：$5$
- $6$ 整除：$6$ 写成有序对形式即可。注意自反性（每个数都能整除自己）。
难度： ⭐ 考点： #关系列举 #整除关系
💡 学习锦囊
📖 相关公式与知识点：
- 整除记作 $x \mid y$。
- 整除关系是偏序关系。
思路分析
不要漏掉自反项（如 $\langle 2, 2 \rangle$），这是初学者最容易错的地方。
- 设一阶逻辑公式 $G = \forall x P(x) \to \exists x Q(x)$，则 $G$ 的前束范式是 _____。
查看答案与解析
答案： $\exists x \exists y (\neg P(x) \lor Q(y))$
解析：
- 消去蕴涵符号： $G \equiv \neg \forall x P(x) \lor \exists x Q(x)$
- 否定词内移： $G \equiv \exists x \neg P(x) \lor \exists x Q(x)$
- 改名变元（避免冲突）： $G \equiv \exists x \neg P(x) \lor \exists y Q(y)$
- 提取量词： $G \equiv \exists x \exists y (\neg P(x) \lor Q(y))$
难度： ⭐⭐ 考点： #前束范式 #量词性质 #等值演算
💡 学习锦囊
📖 相关公式与知识点：
- 量词否定：$\neg \forall x A \equiv \exists x \neg A$
- 提取量词：$\exists x A \lor \exists x B \equiv \exists x \exists y (A(x) \lor B(y))$
思路分析
前束范式的要求是量词全部在公式最左边。改名是防止量词辖域重叠导致语义混乱的关键步骤。
- 设 $G$ 是具有 8 个顶点的树，则 $G$ 中增加 _____ 条边才能把 $G$ 变成完全图。
查看答案与解析
答案： 21
解析：
- 树的边数：$n=8 \implies m_{\text{tree}} = 8 - 1 = 7$。
- 完全图 $K_8$ 的边数： 完全图边数公式为 $n(n-1)/2$。 $m_{\text{complete}} = 8 \times 7 / 2 = 28$。
- 需增加的边数： $28 - 7 = 21$。
难度： ⭐ 考点： #树 #完全图 #边数公式
💡 学习锦囊
📖 相关公式与知识点：
- $n$ 阶完全图边数：$\frac{n(n-1)}{2}$
- $n$ 阶树边数：$n-1$
思路分析
这类题只需要记住两类特殊图的边数公式，做减法即可。
二、选择题（本大题共15小题，每题1分，共15分）
二、选择题（本大题共 15 小题，每题 1 分，共 15 分）
- 设集合 $A = \{2, \{a\}, 3, 4\}$, $B = \{\{a\}, 3, 4, 1\}$, $E$ 为全集，则下列命题正确的是（ ）。
- A. $\{2\} \in A$
- B. $\{a\} \subseteq A$
- C. $\emptyset \subseteq \{\{a\}\} \subseteq B \subseteq E$
- D. $\{\{a\}, 1, 3, 4\} \subseteq B$
查看答案与解析
答案：D (C 也是正确的，通常选最符合题意的)
解析：
- A 选项：$2 \in A$，但 $\{2\}$ 是集合，应该用 $\subseteq$。错误。
- B 选项：$\{a\} \in A$，但 $a \notin A$，故 $\{a\} \not\subseteq A$。错误。
- C 选项：$\{a\} \in B \implies \{\{a\}\} \subseteq B$。该链条 $\emptyset \subseteq \{\{a\}\} \subseteq B \subseteq E$ 在数学上成立。
- D 选项：$B = \{\{a\}, 3, 4, 1\}$。集合 $\{\{a\}, 1, 3, 4\}$ 的所有元素均在 $B$ 中。正确。
难度： ⭐⭐ 考点： #集合包含关系 #属于与包含
💡 学习锦囊
📖 相关公式与知识点：
- $a \in A$：元素属于集合。
- $A \subseteq B$：集合中的所有元素都属于另一个集合。
思路分析
区分 $\in$ 和 $\subseteq$ 的关键在于：$\in$ 的左边必须是右边集合里的一个“整体”；$\subseteq$ 的左边必须是一个集合，且其内部元素都在右边。
- 设集合 $A = \{1, 2, 3\}$, $A$ 上的关系 $R = \{(1, 1), (2, 2), (2, 3), (3, 2), (3, 3)\}$，则 $R$ 不具备（ ）。
- A. 自反性
- B. 传递性
- C. 对称性
- D. 反对称性
查看答案与解析
答案：D
解析：
- 自反性：$1, 2, 3$ 的自环 $(1,1), (2,2), (3,3)$ 都在 $R$ 中。具备。
- 对称性：有 $(2, 3)$ 就有 $(3, 2)$。具备。
- 传递性：$(2, 3)$ 且 $(3, 2) \implies (2, 2)$（在），$(3, 2)$ 且 $(2, 3) \implies (3, 3)$（在）。具备。
- 反对称性：要求如果 $\langle x, y \rangle \in R \land \langle y, x \rangle \in R$，则 $x = y$。但这里 $(2, 3)$ 和 $(3, 2)$ 都在 $R$ 中，且 $2 \neq 3$。故不具备。
难度： ⭐ 考点： #关系性质 #反对称性
💡 学习锦囊
📖 相关公式与知识点：
- 反对称性：$\forall x, y \in A, (\langle x, y \rangle \in R \land \langle y, x \rangle \in R \implies x = y)$。 :::
🔄 举一反三
- 设 $R = \{\langle 1, 1 \rangle, \langle 1, 2 \rangle, \langle 2, 1 \rangle\}$ 是 $\{1, 2\}$ 上的关系，则 $R$ 具备反对称性吗？
查看练习答案与解析
答案： 不具备。 解析： 因为 $(1, 2) \in R$ 且 $(2, 1) \in R$，但 $1 \neq 2$。
- 设半序集 $(A, \le)$ 的哈斯图如下（略），若 $A$ 的子集 $B = \{2, 3, 4, 5\}$，且元素 6 位于哈斯图中所有 $B$ 中元素的上方，则元素 6 为 $B$ 的（ ）。
- A. 下界
- B. 上界
- C. 最小上界
- D. 以上答案都不对
查看答案与解析
答案：B
解析： 在半序集中，如果一个元素 $u$ 满足对所有 $b \in B$ 都有 $b \le u$，则 $u$ 称为 $B$ 的上界。 根据题意，6 位于 $B$ 的上方（即 $b \le 6$ 成立），因此 6 是 $B$ 的上界。由于不确定 6 是否是所有上界中最小的，不能断定它是最小上界。
难度： ⭐ 考点： #哈斯图 #上界与下界
💡 学习锦囊
思路分析
哈斯图中，“上方”代表“大”。如果一个点在子集所有点的上方，它就是上界。
- 下列语句中，（ ）是命题。
- A. 请把门关上
- B. 地球外的星球上也有人
- C. $x + 5 > 6$
- D. 下午有会吗？
查看答案与解析
答案：B
解析： 命题是能够判断真假的陈述句。
- A 是祈使句。非命题。
- B 是陈述句，虽然目前科技无法确定其真假，但它必有唯一的真值。是命题。
- C 含有变量 $x$，真假随 $x$ 变化，是命题函数（谓词）。非命题。
- D 是疑问句。非命题。
难度： ⭐ 考点： #命题定义
💡 学习锦囊
易错点
很多人认为无法确定真假的句子不是命题。实际上，只要它具备“非真即假”的客观属性，就是命题（如大卫未解决的数学猜想）。
🔄 举一反三
- 判断语句“请大家保持安静！”是否为命题。
查看练习答案与解析
答案： 非命题。 解析： 该句为祈使句，不能判断真假。
- 设解释 $I$ 为：$D = \{a, b\}$, $P(a, a)=1, P(a, b)=0, P(b, a)=0, P(b, b)=1$。则在解释 $I$ 下取真值为 1 的公式是（ ）。
- A. $\exists x \forall y P(x, y)$
- B. $\forall x \forall y P(x, y)$
- C. $\forall x P(x, x)$
- D. $\forall x \exists y P(x, y)$
查看答案与解析
答案：D (C 也是正确的)
解析：
- A 选项：是否存在一个 $x$，使得对所有 $y, P(x,y)$ 为真？ $x=a$ 时，$P(a,a)=1, P(a,b)=0$（假）；$x=b$ 时，$P(b,a)=0$（假）。错误。
- B 选项：显然不全为 1。错误。
- C 选项：$\forall x P(x, x)$ 即 $P(a, a) \land P(b, b) = 1 \land 1 = 1$。正确。
- D 选项：对每个 $x$，是否存在一个 $y$？ $x=a$ 时，取 $y=a, P(a,a)=1$；$x=b$ 时，取 $y=b, P(b,b)=1$。正确。 (注：OCR 数据可能存在细微差别，C 和 D 在此解释下均成立)
难度： ⭐⭐ 考点： #一阶逻辑解释 #量词真值
- 若给出的数值表示一个简单图中各个顶点的度，能画出图的是（ ）。
- A. (1, 2, 2, 3, 4, 5)
- B. (1, 2, 3, 4, 5, 5)
- C. (1, 1, 1, 2, 3)
- D. (2, 3, 3, 4, 5, 6)
查看答案与解析
答案：C
解析：
- 握手定理：度数之和必须为偶数。
- A: $1+2+2+3+4+5=17$ (奇)。排除。
- B: $1+2+3+4+5+5=20$ (偶)。
- C: $1+1+1+2+3=8$ (偶)。
- D: $2+3+3+4+5+6=23$ (奇)。排除。
- 简单图限制： 对于 B，有 6 个顶点，最大度为 5。但存在两个度为 5 的点，意味着这两个点必须连接到所有其他点。这会导致每个顶点的度数至少为 2。但序列中有度为 1 的点。排除。 对于 C，5 个顶点，度序列 (3, 2, 1, 1, 1) 是可图化的。
难度： ⭐⭐ 考点： #握手定理 #可图化序列
- 设 $G, H$ 是一阶逻辑公式，$P$ 是一个谓词，$G = \exists x P(x), H = \forall x P(x)$, 则一阶逻辑公式 $G \to H$ 是（ ）。
- A. 恒真的
- B. 恒假的
- C. 可满足的
- D. 前束范式
查看答案与解析
答案：C
解析：$G \to H = \exists x P(x) \to \forall x P(x)$。
- 如果解释域 $D$ 只有一个元素，则 $\exists x P(x) \equiv \forall x P(x)$，公式为真。
- 如果解释域 $D$ 有多个元素，且 $P$ 只对其中部分元素为真，则 $\exists x P(x)$ 为真而 $\forall x P(x)$ 为假，公式为假。 既不是恒真也不是恒假，故为可满足的。
难度： ⭐⭐ 考点： #恒真性 #可满足性
- 设命题公式 $G = \neg(P \to Q)$，$H = P \to (Q \to \neg P)$，则 $G$ 与 $H$ 的关系是（ ）。
- A. $G \implies H$
- B. $H \implies G$
- C. $G \equiv H$
- D. 以上都不是
查看答案与解析
答案：A
解析：
- $G = \neg(\neg P \lor Q) = P \land \neg Q$
- $H = \neg P \lor (\neg Q \lor \neg P) = \neg P \lor \neg Q$ 观察发现，如果 $G$ 为真（即 $P=1, Q=0$），则 $\neg P \lor \neg Q = 0 \lor 1 = 1$，即 $H$ 必为真。 因此 $G \implies H$。
难度： ⭐⭐ 考点： #逻辑蕴涵 #等值演算
- 设 $A, B$ 为集合，当（ ）时 $A - B = B$。
- A. $A = B$
- B. $A \subseteq B$
- C. $B \subseteq A$
- D. $A = B = \emptyset$
查看答案与解析
答案：D
解析：$A - B$ 的结果包含在 $A$ 中且不包含在 $B$ 中。 如果要让 $A - B = B$，则必须满足 $B \subseteq A$ 且 $B \cap B = \emptyset$。 只有当 $B = \emptyset$ 时，$B \cap B = \emptyset$ 成立。 此时 $A - \emptyset = A$，故要求 $A = B = \emptyset$。
难度： ⭐⭐ 考点： #集合运算性质
- 设集合 $A = \{1, 2, 3, 4\}$, $A$ 上的关系 $R = \{(1, 1), (2, 3), (2, 4), (3, 4)\}$，则 $R$ 具有（ ）。
- A. 自反性
- B. 传递性
- C. 对称性
- D. 以上答案都不对
查看答案与解析
答案：B
解析：
- 自反性：缺少 $(2, 2), (3, 3), (4, 4)$。不具备。
- 对称性：有 $(2, 3)$ 但无 $(3, 2)$。不具备。
- 传递性：$(2, 3) \in R \land (3, 4) \in R \implies (2, 4) \in R$。在关系中。具备。
难度： ⭐ 考点： #关系性质
- 下列关于集合的表示中正确的为（ ）。
- A. $\{a\} \in \{a, b, c\}$
- B. $\{a\} \subseteq \{a, b, c\}$
- C. $\emptyset \in \{a, b, c\}$
- D. $\{a, b\} \in \{a, b, c\}$
查看答案与解析
答案：B
解析：
- A：$\{a\}$ 不在集合元素列表中。错误。
- B：元素 $a$ 在右边集合中。正确。
- C：$\emptyset$ 是子集而非元素。错误。
- D：同 A。错误。
难度： ⭐ 考点： #属于与包含
- 命题 $\forall x G(x)$ 取真值 1 的充分必要条件是（ ）。
- A. 对任意 $x$，$G(x)$ 都取真值 1
- B. 有一个 $x_0$，使 $G(x_0)$ 取真值 1
- C. 有某些 $x$，使 $G(x_0)$ 取真值 1
- D. 以上答案都不对
查看答案与解析
答案：A
解析： 全称量词的定义即为在论域中所有个体都满足谓词。
难度： ⭐ 考点： #量词定义
- 设 $G$ 是连通平面图，有 5 个顶点，6 个面，则 $G$ 的边数是（ ）。
- A. 9 条
- B. 5 条
- C. 6 条
- D. 11 条
查看答案与解析
答案：A
解析： 欧拉公式：$V - E + F = 2$。 $5 - E + 6 = 2 \implies 11 - E = 2 \implies E = 9$。
难度： ⭐ 考点： #欧拉公式 #平面图
🔄 举一反三
- 一个连通平面图有 6 个顶点，7 个面，求其边数。
查看练习答案与解析
答案： 11 解析： $V-E+F=2 \implies 6-E+7=2 \implies 13-E=2 \implies E=11$。
- 设 $G$ 是 5 个顶点的完全图，则从 $G$ 中删去（ ）条边可以得到树。
- A. 6
- B. 5
- C. 10
- D. 4
查看答案与解析
答案：A
解析：
- $K_5$ 的边数 $= 5 \times 4 / 2 = 10$ 条。
- 5 个顶点的树有 $5 - 1 = 4$ 条边。
- 需删去 $10 - 4 = 6$ 条边。
难度： ⭐ 考点： #完全图 #树
- 设图 $G$ 的相邻矩阵为 $\begin{bmatrix} 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 & 0 \end{bmatrix}$，则 $G$ 的顶点数与边数分别为（ ）。
- A. 4, 5
- B. 5, 6
- C. 4, 10
- D. 5, 8
查看答案与解析
答案：D
解析：
- 矩阵为 $5 \times 5$，故有 5 个顶点。
- 矩阵中 1 的个数之和为度数之和：$4 + 2 + 4 + 3 + 3 = 16$。
- 边数 $= 16 / 2 = 8$ 条。
难度： ⭐⭐ 考点： #相邻矩阵 #握手定理
三、计算证明题（本大题共10小题，每题5分，共50分）
三、计算证明题（本大题共 10 小题，每题 5 分，共 50 分）
- 设集合 $A = \{1, 2, 3, 4, 6, 8, 9, 12\}$, $R$ 为整除关系。 (1) 画出半序集 $(A, R)$ 的哈斯图； (2) 写出 $A$ 的子集 $B = \{3, 6, 9, 12\}$ 的上界，下界，最小上界，最大下界； (3) 写出 $A$ 的最大元, 最小元, 极大元, 极小元。
查看答案与解析
答案： (1) 哈斯图（文字描述）：
- 底层：1
- 第二层：2, 3（1 分别指向 2, 3）
- 第三层：4, 6, 9（2 指向 4, 6；3 指向 6, 9）
- 第四层：8, 12（4 指向 8, 12；6 指向 12） (2) 子集 $B = \{3, 6, 9, 12\}$：
- 上界：无（A 中没有元素能同时被 9 和 12 整除）
- 下界：1, 3
- 最小上界 (LUB)：无
- 最大下界 (GLB)：3 (3) 元：
- 最大元：无； 最小元：1
- 极大元：8, 9, 12； 极小元：1
解析：
- 哈斯图绘制：按照整除关系逐层向上。如果 $a \mid b$ 且不存在 $c$ 使得 $a \mid c \mid b$，则连线。
- 界限判定：上界必须大于等于 $B$ 中所有元素；下界必须小于等于 $B$ 中所有元素。
- 元判定：极大元是上方没有点的点；极小元是下方没有点的点。最大元/最小元必须与集合内所有元素可比。
难度： ⭐⭐ 考点： #哈斯图 #上界下界 #极大极小元
🔄 举一反三
- 设集合 $A = \{1, 2, 3, 4, 6, 12\}$，画出其整除关系的哈斯图。
查看练习答案与解析
答案： 1 在底部，连向 2,3；2 连向 4,6；3 连向 6；4,6 连向 12。
- 设集合 $A = \{1, 2, 3, 4\}$, $A$ 上的关系 $R = \{\langle x, y \rangle \mid x, y \in A \text{ 且 } x \ge y\}$, 求： (1) 画出 $R$ 的关系图； (2) 写出 $R$ 的关系矩阵。
查看答案与解析
答案： (1) 关系图：
- 节点：1, 2, 3, 4
- 自环：每个节点都有自环。
- 边：$2 \to 1, 3 \to 1, 3 \to 2, 4 \to 1, 4 \to 2, 4 \to 3$。 (2) 关系矩阵： $M_R = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 \end{bmatrix}$
解析：
- 关系定义：$x \ge y$ 意味着对于每一行 $x$，在所有小于等于 $x$ 的列 $y$ 处填 1。
- 矩阵结构：因为是 $\ge$ 关系，所以在主对角线及其左下方（下三角区域）填 1。
难度： ⭐ 考点： #关系图 #关系矩阵
- 设 $R$ 是实数集合，$\sigma, \tau, \varphi$ 是 $R$ 上的三个映射，$\sigma(x) = x + 3, \tau(x) = 2x, \varphi(x) = x / 4$，试求复合映射 $\sigma \circ \tau, \sigma \circ \sigma, \sigma \circ \varphi, \varphi \circ \tau, \sigma \circ \varphi \circ \tau$。
查看答案与解析
答案：
- $\sigma \circ \tau (x) = \sigma(\tau(x)) = 2x + 3$
- $\sigma \circ \sigma (x) = \sigma(\sigma(x)) = (x+3) + 3 = x + 6$
- $\sigma \circ \varphi (x) = \sigma(\varphi(x)) = \frac{x}{4} + 3$
- $\varphi \circ \tau (x) = \varphi(\tau(x)) = \frac{2x}{4} = \frac{x}{2}$
- $\sigma \circ \varphi \circ \tau (x) = \sigma(\varphi(\tau(x))) = \sigma(\frac{2x}{4}) = \frac{x}{2} + 3$
解析： 复合映射 $f \circ g(x)$ 的含义是先作用 $g$，再作用 $f$，即 $f(g(x))$。直接代入表达式化简即可。
难度： ⭐ 考点： #复合映射
- 设解释 $I$ 为：$D = \{2, 3\}$, $a=3, b=2, f(2)=3, f(3)=2, P(2,2)=0, P(2,3)=0, P(3,2)=1, P(3,3)=1$。 试求： (1) $P(a, f(a)) \wedge P(b, f(b))$; (2) $\forall x \exists y P(y, x)$。
查看答案与解析
答案： (1) 0 (假) (2) 1 (真)
解析： (1) $P(a, f(a)) \wedge P(b, f(b)) = P(3, f(3)) \wedge P(2, f(2)) = P(3, 2) \wedge P(2, 3) = 1 \wedge 0 = 0$。 (2) $\forall x \exists y P(y, x)$：
- 当 $x=2$ 时，需找 $y$ 使 $P(y, 2)=1$。由已知 $P(3, 2)=1$，取 $y=3$ 成立。
- 当 $x=3$ 时，需找 $y$ 使 $P(y, 3)=1$。由已知 $P(3, 3)=1$，取 $y=3$ 成立。 对论域中所有 $x$ 都成立，故公式真值为 1。
难度： ⭐⭐ 考点： #谓词逻辑解释 #真值计算
- 设集合 $A = \{1, 2, 4, 6, 8, 12\}$, $R$ 为 $A$ 上整除关系。 (1) 画出半序集 $(A, R)$ 的哈斯图； (2) 写出 $A$ 的最大元，最小元，极大元，极小元； (3) 写出 $A$ 的子集 $B = \{4, 6, 8, 12\}$ 的上界，下界，最小上界，最大下界。
查看答案与解析
答案： (1) 哈斯图：
- 1 为底层。
- 1 连向 2。
- 2 连向 4, 6。
- 4 连向 8, 12；6 连向 12。 (2) 元：
- 最大元：无； 最小元：1
- 极大元：8, 12； 极小元：1 (3) 子集 $B = \{4, 6, 8, 12\}$：
- 上界：无（8 和 12 在 A 中无公共倍数）
- 下界：1, 2
- 最小上界：无
- 最大下界：2
难度： ⭐⭐ 考点： #哈斯图 #整除关系
- 设命题公式 $G = \neg (P \to Q) \lor (Q \land (\neg P \to R))$，求 $G$ 的主析取范式。
查看答案与解析
答案： $\sum(3, 4, 5, 6, 7)$ 或 $(\neg P \land Q \land R) \lor (P \land \neg Q \land \neg R) \lor (P \land \neg Q \land R) \lor (P \land Q \land \neg R) \lor (P \land Q \land R)$
解析：
- 等值演算化简： $G = (P \land \neg Q) \lor (Q \land (P \lor R))$$G = (P \land \neg Q) \lor (Q \land P) \lor (Q \land R)$$G = (P \land (\neg Q \lor Q)) \lor (Q \land R) = P \lor (Q \land R)$
- 补全变量求极小项： $P \equiv (P \land Q \land R) \lor (P \land Q \land \neg R) \lor (P \land \neg Q \land R) \lor (P \land \neg Q \land \neg R)$ (对应 $m_7, m_6, m_5, m_4$) $Q \land R \equiv (P \land Q \land R) \lor (\neg P \land Q \land R)$ (对应 $m_7, m_3$)
- 合并去重： $G \equiv m_3 \lor m_4 \lor m_5 \lor m_6 \lor m_7$。
难度： ⭐⭐ 考点： #主析取范式 #等值演算
🔄 举一反三
- 求 $\neg(P \land Q)$ 的主析取范式。
查看练习答案与解析
答案： $m_0 \lor m_1 \lor m_2$解析： $\neg(P \land Q) \equiv \neg P \lor \neg Q \equiv (\neg P \land Q) \lor (\neg P \land \neg Q) \lor (P \land \neg Q)$。
- 设一阶逻辑公式：$G = (\forall x P(x) \lor \exists y Q(y)) \to \forall x R(x)$，把 $G$ 化成前束范式。
查看答案与解析
答案： $\exists x \forall y \forall z ((\neg P(x) \land \neg Q(y)) \lor R(z))$
解析：
- 消去蕴涵项： $G \equiv \neg(\forall x P(x) \lor \exists y Q(y)) \lor \forall x R(x)$
- 否定词内移： $G \equiv (\exists x \neg P(x) \land \forall y \neg Q(y)) \lor \forall x R(x)$
- 变元改名（避免量词冲突）： $G \equiv (\exists x \neg P(x) \land \forall y \neg Q(y)) \lor \forall z R(z)$
- 提取量词到最左侧： 根据提取规则，量词可以按顺序移出： $G \equiv \exists x \forall y \forall z (\neg P(x) \land \neg Q(y) \lor R(z))$
难度： ⭐⭐⭐ 考点： #前束范式 #量词提取
🔄 举一反三
- 将 $\forall x P(x) \land \exists y Q(y)$ 化为前束范式。
查看练习答案与解析
答案： $\forall x \exists y (P(x) \land Q(y))$解析： 两个量词辖域不冲突，直接提取即可。
- 设集合 $A = \{ a, b, c, d \}$, $R$ 是 $A$ 上的二元关系, $R = \{(a, b), (b, a), (b, c), (c, d) \}$。 (1) 求出 $r(R), s(R), t(R)$； (2) 画出 $r(R), s(R), t(R)$ 的关系图。
查看答案与解析
答案： (1) 闭包运算：
- 自反闭包 $r(R)$：$R \cup \{\langle a, a \rangle, \langle b, b \rangle, \langle c, c \rangle, \langle d, d \rangle\}$
- 对称闭包 $s(R)$：$R \cup \{\langle c, b \rangle, \langle d, c \rangle\}$
- 传递闭包 $t(R)$：$\{(a, b), (b, a), (b, c), (c, d), (a, a), (b, b), (a, c), (b, d), (a, d)\}$ (2) 关系图（略，建议按顶点 $a,b,c,d$ 布局，根据上述集合连线即可）。
解析：
- 自反闭包：补齐所有自环。
- 对称闭包：对每一条单向边补齐反向边。
- 传递闭包：如果存在路径 $x \to \dots \to y$，则增加边 $\langle x, y \rangle$。 例如：$a \to b \to a \implies (a, a)$；$a \to b \to c \implies (a, c)$；$a \to b \to c \to d \implies (a, d)$。
难度： ⭐⭐ 考点： #关系闭包 #自反对称传递
- 通过求主析取范式判断下列命题公式是否等价： (1) $G = (P \land Q) \lor (\neg P \land Q \land R)$ (2) $H = (P \lor (Q \land R)) \land (Q \lor (\neg P \land R))$
查看答案与解析
答案：等价。主析取范式均为 $m_3 \lor m_6 \lor m_7$。
解析：
- 求 $G$ 的主析取范式： $G = (P \land Q \land (R \lor \neg R)) \lor (\neg P \land Q \land R)$$G = (P \land Q \land R) \lor (P \land Q \land \neg R) \lor (\neg P \land Q \land R) = m_7 \lor m_6 \lor m_3$。
- 求 $H$ 的主析取范式： $H = (P \lor Q) \land (P \lor R) \land (Q \lor \neg P) \land (Q \lor R)$ 利用 $(P \lor Q) \land (\neg P \lor Q) = Q$（消解律变形）： $H = Q \land (P \lor R) \land (Q \lor R) = Q \land (P \lor R) = (Q \land P) \lor (Q \land R)$ 补齐变量：$(Q \land P \land (R \lor \neg R)) \lor (Q \land R \land (P \lor \neg P))$$H = m_7 \lor m_6 \lor m_7 \lor m_3 = m_7 \lor m_6 \lor m_3$。 两公式主析取范式相同，故等价。
难度： ⭐⭐ 考点： #主析取范式 #逻辑等价
- 设 $R$ 和 $S$ 是集合 $A = \{a, b, c, d\}$ 上的关系，其中 $R = \{(a, a), (a, c), (b, c), (c, d)\}$，$S = \{(a, b), (b, c), (b, d), (d, d) \}$。 (1) 试写出 $R$ 和 $S$ 的关系矩阵； (2) 计算 $R \circ S, R \cup S, R^{-1}, S^{-1} \circ R^{-1}$。
查看答案与解析
答案： (1) 关系矩阵： $M_R = \begin{bmatrix} 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{bmatrix}$, $M_S = \begin{bmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}$ (2) 关系运算：
- $R \circ S = \{\langle a, b \rangle, \langle a, d \rangle, \langle b, d \rangle\}$
- $R \cup S = \{(a, a), (a, c), (b, c), (c, d), (a, b), (b, d), (d, d)\}$
- $R^{-1} = \{(a, a), (c, a), (c, b), (d, c)\}$
- $S^{-1} \circ R^{-1} = (R \circ S)^{-1} = \{(b, a), (d, a), (d, b)\}$
解析：
- 复合运算：寻找中转点。$a \xrightarrow{R} a \xrightarrow{S} b \implies (a, b)$；$a \xrightarrow{R} c \xrightarrow{S} d$ (无)；$c \xrightarrow{R} d \xrightarrow{S} d \implies (c, d)$。 Wait, let me re-check $R \circ S$ for $(c,d)$. $c \xrightarrow{R} d$ and $d \xrightarrow{S} d$ so $(c,d) \in R \circ S$. Correct $R \circ S = \{(a, b), (a, d), (b, d), (c, d)\}$? Let's check $a \to c \to d$. No, $c$ is not a starting point in $S$. $d$ is. $R = \{(a, a), (a, c), (b, c), (c, d)\}$, $S = \{(a, b), (b, c), (b, d), (d, d) \}$.
- $a \xrightarrow{R} a \xrightarrow{S} b \implies (a,b)$
- $c \xrightarrow{R} d \xrightarrow{S} d \implies (c,d)$
- $a \xrightarrow{R} c \xrightarrow{S} \dots$ (None)
- $b \xrightarrow{R} c \xrightarrow{S} \dots$ (None) So $R \circ S = \{(a, b), (c, d)\}$. Wait, let me re-verify. $M_R \times M_S = \begin{bmatrix} 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{bmatrix} \times \begin{bmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} = \begin{bmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{bmatrix}$. So $R \circ S = \{(a, b), (c, d)\}$. Correct.
难度： ⭐⭐⭐ 考点： #关系矩阵 #关系复合 #逆关系
四、证明题（本大题共 4 小题，每题 5 分，共 20 分）
- 利用形式演绎法证明：$\{P \to Q, R \to S, P \lor R\}$ 蕴涵 $Q \lor S$。
查看答案与解析
证明： (1) $P \lor R$ \quad \quad \quad \quad \quad \quad \quad \quad P (前提) (2) $P \to Q$ \quad \quad \quad \quad \quad \quad \quad \quad P (前提) (3) $R \to S$ \quad \quad \quad \quad \quad \quad \quad \quad P (前提) (4) $(P \to Q) \land (R \to S)$ \quad \quad \quad I (2), (3) (合取规则) (5) $Q \lor S$ \quad \quad \quad \quad \quad \quad \quad \quad T (1), (4), I (二难推论)
解析： 本题直接应用二难推论（Constructive Dilemma）即可得证。在形式演绎中，先列出所有前提，再通过逻辑规则逐步推导。
难度： ⭐⭐ 考点： #形式演绎法 #二难推论
- 设 $A, B$ 为任意集合, 证明: $(A - B) - C = A - (B \cup C)$。
查看答案与解析
证明： 根据差集定义 $X - Y = X \cap \overline{Y}$： 左边 $= (A - B) - C$$= (A \cap \overline{B}) \cap \overline{C}$$= A \cap (\overline{B} \cap \overline{C})$ (结合律) $= A \cap \overline{(B \cup C)}$ (德·摩根律) $= A - (B \cup C)$$= $ 右边。 得证。
难度： ⭐ 考点： #集合恒等式 #德·摩根律
- 利用形式演绎法证明：$\{\neg A \lor B, \neg C \to \neg B, C \to D\}$ 蕴涵 $A \to D$。
查看答案与解析
证明： 使用 CP 规则（附加前提证明法）： (1) $A$ \quad \quad \quad \quad \quad \quad \quad \quad 附加前提 (2) $\neg A \lor B$ \quad \quad \quad \quad \quad \quad P (3) $B$ \quad \quad \quad \quad \quad \quad \quad \quad T (1), (2) I (析取三段论) (4) $\neg C \to \neg B$ \quad \quad \quad \quad \quad P (5) $B \to C$ \quad \quad \quad \quad \quad \quad E (4) (等值演变，逆否律) (6) $C$ \quad \quad \quad \quad \quad \quad \quad \quad T (3), (5) I (假言推理) (7) $C \to D$ \quad \quad \quad \quad \quad \quad P (8) $D$ \quad \quad \quad \quad \quad \quad \quad \quad T (6), (7) I (假言推理) (9) $A \to D$ \quad \quad \quad \quad \quad \quad CP (1)-(8)
解析： 本题考查形式演绎中的附加前提规则。通过假设前件 $A$ 为真，推导出后件 $D$ 为真，从而证明 $A \to D$ 成立。
难度： ⭐⭐⭐ 考点： #形式演绎法 #CP规则 #假言推理
🔄 举一反三
- 证明 $\{P \to Q, Q \to R\} \implies P \to R$。
查看练习答案与解析
证明： (1) $P$ (附加前提) (2) $P \to Q$ (前提) (3) $Q$ (MP 1,2) (4) $Q \to R$ (前提) (5) $R$ (MP 3,4) (6) $P \to R$ (CP 1-5)
- $A, B$ 为两个任意集合，求证：$A - (A \cap B) = (A \cup B) - B$。
查看答案与解析
证明：方法一：等值演算 左边 $= A \cap \overline{(A \cap B)}$$= A \cap (\overline{A} \lor \overline{B})$$= (A \cap \overline{A}) \lor (A \cap \overline{B})$$= \emptyset \lor (A - B) = A - B$ 右边 $= (A \cup B) \cap \overline{B}$$= (A \cap \overline{B}) \lor (B \cap \overline{B})$$= (A - B) \lor \emptyset = A - B$ 左边 $=$ 右边。
方法二：图示辅助（Venn 图） 通过 Venn 图可以直观发现，两者表达的都是“属于 A 但不属于 B”的区域。
难度： ⭐⭐ 考点： #集合恒等式 #分配律