Appearance
《离散数学》第一学期期末试卷B (精选02)
一、填空题（本大题共5个空，每空2分，总计10分）
- 实数集合 $\mathbb{R}$ ______（是/不是）可数的。
查看答案与解析
答案：不是
解析：
本题考查集合论中关于集合基数（势）的基本概念。
第一步：理解可数集合定义
一个集合如果是可数的，意味着它要么是有限集，要么与自然数集 $\mathbb{N}$ 等势（即基数为 $\aleph_0$）。
第二步：分析实数集的基数
根据康托尔（Cantor）的对角线证明法，实数集 $\mathbb{R}$ 的基数是 $c$（连续统基数），且 $c = 2^{\aleph_0} > \aleph_0$。
第三步：得出结论
由于 $\mathbb{R}$ 的基数大于自然数集的基数，因此实数集是不可数集合。
难度: ⭐
考点: #集合论 #可数集 #实数集基数
💡 学习锦囊
📖 相关公式与知识点:
- 自然数集 $\mathbb{N}$、整数集 $\mathbb{Z}$、有理数集 $\mathbb{Q}$ 都是可数的。
- 实数集 $\mathbb{R}$、复数集 $\mathbb{C}$、任意区间的实数集（如 $[0, 1]$）都是不可数的。
- 康托尔定理：$|\mathbb{R}| = 2^{|\mathbb{N}|}$。
思路分析
这类题目属于离散数学的基础概念题。考生只需记住常见集合的基数性质：离散分布的通常可数，连续分布的通常不可数。
易错点
- 误以为有理数集 $\mathbb{Q}$ 是不可数的（其实是有理数可以与自然数建立一一对应）。
- 误以为有限区间内的实数是可数的。
学习建议
掌握康托尔的“对角线法”，这是证明集合不可数的核心思想，也是考试中经常涉及的理论背景。
🔄 举一反三
- 有理数集合 $\mathbb{Q}$ 是可数的吗？
查看练习答案与解析
答案：是。
解析：有理数可以表示为分母不为零的分数形式，可以通过一种确定的排列方式（如蛇形排列法）与自然数建立一一对应，故 $\mathbb{Q}$ 是可数的。 - 闭区间 $[0, 1]$ 内的实数集合是可数的吗？
查看练习答案与解析
答案：不是。
解析：虽然区间长度有限，但其内部包含无限个实数，且其基数与 $\mathbb{R}$ 相同，均为连续统基数 $c$，因此不可数。
- 设 $A$ 和 $B$ 为有限集，$|A|=m, |B|=n$，则有______个从 $A$ 到 $B$ 的关系，有______个从 $A$ 到 $B$ 的函数，其中当 $m \leq n$ 时有______个入射，当 $m=n$ 时，有______个双射。
查看答案与解析
答案：$2^{mn}$；$n^m$；$P_n^m$ (或 $n(n-1)\dots(n-m+1)$)；$n!$
解析：
本题考查集合间关系与函数的计数问题。
第一步：计算关系个数
从 $A$ 到 $B$ 的关系是笛卡尔积 $A \times B$ 的所有可能子集。 $|A \times B| = |A| \cdot |B| = m \cdot n$。 由于每个子集对应一种关系，而 $k$ 个元素的集合有 $2^k$ 个子集，故关系个数为 $2^{mn}$。
第二步：计算函数个数
函数定义要求 $A$ 中的每一个元素在 $B$ 中有且仅有一个对应的像。 对于 $A$ 中第 1 个元素，有 $n$ 种映射选择； 对于 $A$ 中第 2 个元素，依然有 $n$ 种选择（允许重复映射）； ... 以此类推，共 $m$ 个元素，总数为 $n \times n \times \dots \times n = n^m$。
第三步：计算入射（单射）个数
入射要求 $A$ 中不同的元素必须映射到 $B$ 中不同的元素。 这相当于从 $n$ 个元素中取出 $m$ 个进行有顺序的排列： 第一个元素有 $n$ 种选择，第二个有 $n-1$ 种，...，第 $m$ 个有 $n-m+1$ 种。 总数为 $P_n^m = \frac{n!}{(n-m)!}$。
第四步：计算双射个数
双射要求 $m=n$，且既是单射又是满射。 这相当于对 $n$ 个元素进行全排列，总数为 $n!$。
难度: ⭐⭐
考点: #计数问题 #二元关系 #函数 #单射与双射
💡 学习锦囊
📖 相关公式与知识点:
- 关系数：$2^{|A| \cdot |B|}$
- 函数数：$|B|^{|A|}$
- 单射数（$m \leq n$）：$P_{|B|}^{|A|}$
- 双射数（$m = n$）：$|A|!$
思路分析
区分“关系”与“函数”的关键：
- 关系：没有任何限制，矩阵中每个格子都可以是 0 或 1。
- 函数：矩阵每一行必须有且仅有一个 1。
- 单射：矩阵每一列最多只能有一个 1。
易错点
- 混淆 $n^m$ 和 $m^n$。记住是“靶子”的“箭”次方（$|B|^{|A|}$）。
- 计算单射时忘记前提条件 $m \leq n$，若 $m > n$ 则单射数为 0。
🔄 举一反三
- 设 $|A|=3, |B|=2$，求从 $A$ 到 $B$ 的满射个数。
查看练习答案与解析
答案：6。
解析：总函数数为 $2^3 = 8$。其中不是满射的情况只有两种：所有元素都映射到 $B$ 中的第一个元素，或都映射到第二个元素。故满射数为 $8 - 2 = 6$。 - 设 $|A|=4$，求 $A$ 上的自反关系个数。
查看练习答案与解析
答案：$2^{12}$。
解析：$A$ 上的关系总数为 $2^{4 \times 4} = 2^{16}$。自反关系要求关系矩阵对角线上的 4 个元素必须为 1，其余 $16-4=12$ 个元素可选 0 或 1，故为 $2^{12}$。
二、计算题（本大题共2小题，每小题10分，总计20分）
- 用推导法求下列公式的主合取范式和主析取范式： $((\neg P \lor Q) \rightarrow R)$
查看答案与解析
答案：
- 主析取范式 (PDNF)：$(P \land \neg Q \land R) \lor (P \land \neg Q \land \neg R) \lor (P \land Q \land R) \lor (\neg P \land Q \land R) \lor (\neg P \land \neg Q \land R)$，即 $m_1 \lor m_3 \lor m_4 \lor m_5 \lor m_7$。
- 主合取范式 (PCNF)：$(P \lor Q \lor R) \land (P \lor \neg Q \lor R) \land (\neg P \lor \neg Q \lor R)$，即 $M_0 \land M_2 \land M_6$。 (注：二进制编码以 P, Q, R 为序，111 对应 $m_7$)
解析：
本题考查命题逻辑中范式的转换。
第一步：公式简化
利用等价式 $A \rightarrow B \equiv \neg A \lor B$：
根据德·摩根律和双重否定律：
第二步：求主析取范式 (PDNF)
利用分配律补全缺失变量： $(P \land \neg Q) \lor R$$\equiv (P \land \neg Q \land (R \lor \neg R)) \lor (R \land (P \lor \neg P) \land (Q \lor \neg Q))$$\equiv (P \land \neg Q \land R) \lor (P \land \neg Q \land \neg R) \lor (P \land Q \land R) \lor (P \land \neg Q \land R) \lor (\neg P \land Q \land R) \lor (\neg P \land \neg Q \land R)$ 合并重复项并排序： $\equiv m_5 \lor m_4 \lor m_7 \lor m_3 \lor m_1$ 即 $\sum(1, 3, 4, 5, 7)$。
第三步：求主合取范式 (PCNF)
方法：利用 PDNF 结果，从全集 $\{0, 1, \dots, 7\}$ 中找出未出现的编码 $\{0, 2, 6\}$。 对应的极大项分别为：
- $M_0 = P \lor Q \lor R$
- $M_2 = P \lor \neg Q \lor R$
- $M_6 = \neg P \lor \neg Q \lor R$ 故 PCNF 为：$(P \lor Q \lor R) \land (P \lor \neg Q \lor R) \land (\neg P \lor \neg Q \lor R)$。
故 PCNF 为：$(P \lor Q \lor R) \land (P \lor \neg Q \lor R) \land (\neg P \lor \neg Q \lor R)$。
难度: ⭐⭐⭐
考点: #命题逻辑 #主析取范式 #主合取范式 #逻辑等价
💡 学习锦囊
📖 相关公式与知识点:
- $A \rightarrow B \equiv \neg A \lor B$
- 极小项 $m_i$：对应真值表中结果为 1 的行。
- 极大项 $M_i$：对应真值表中结果为 0 的行。
思路分析
如果公式变量较少（如 2-3 个），画真值表求范式是最稳妥的方法。如果变量较多，利用等价变换补全变量更快。
易错点
- 极大项符号反向：在 $M_i$ 中，变量取值为 1 时带否定号，取值为 0 时不带。这与极小项 $m_i$ 的规则正好相反。
- 缺失变量：补全变量时别漏了 $(X \lor \neg X)$。
- 利用分配律 $A \equiv A \land (B \lor \neg B)$ 来补齐缺失变量。
- 极大项与 PCNF：
- 利用分配律 $A \equiv A \lor (B \land \neg B)$ 来补齐缺失变量。
- 或者利用 PDNF 的补集快速求得下标，再写出极大项。
- 互补律：PDNF 涉及的下标集与 PCNF 涉及的下标集互为补集。
故 PDNF 为 $\sum(1, 3, 4, 5, 7)$，PCNF 为 $\prod(0, 2, 6)$。 选 PDNF: $\sum(1, 3, 4, 5, 7)$, PCNF: $\prod(0, 2, 6)$。
难度: ⭐⭐⭐
考点: #命题逻辑 #主析取范式 #主合取范式 #逻辑等价
💡 学习锦囊
📖 相关公式与知识点:
- $A \to B \equiv \neg A \lor B$
- PDNF（极小项之和）：对应真值为 1 的行。
- PCNF（极大项之积）：对应真值为 0 的行。
- 极小项 $m_i$ 与 极大项 $M_i$ 的关系：$M_i = \neg m_i$。
思路分析
- 先化简：将所有 $\to, \leftrightarrow$ 去掉。
- 列真值表（可选）：如果推导法容易出错，可以列出 8 行真值表，找到结果为 1 的行即得 PDNF。
- 巧用互补：PDNF 涉及的下标和 PCNF 涉及的下标正好凑齐全集 $\{0, 1, \dots, 2^n-1\}$。
易错点
- 编码顺序：P, Q, R 的顺序决定了下标。通常 $111$ 对应 $m_7$。
- 极大项符号：在 $M_i$ 中，变量为 1 对应 $\neg$，为 0 对应原变量（与极小项相反）。
🔄 举一反三
- 求 $(P \land Q) \lor \neg R$ 的主析取范式。
查看练习答案与解析
答案：$(P \land Q \land R) \lor (P \land Q \land \neg R) \lor (P \land \neg Q \land \neg R) \lor (\neg P \land Q \land \neg R) \lor (\neg P \land \neg Q \land \neg R)$。
解析：$(P \land Q \land (R \lor \neg R)) \lor (\neg R \land (P \lor \neg P) \land (Q \lor \neg Q))$ 展开并合并即可。
- 设 $A = \{1, 2, 3, 4\}$，$A$ 上二元关系 $R = \{<1, 1>, <2, 3>, <2, 4>, <3, 2>, <3, 4>\}$，求其自反闭包、对称闭包、传递闭包。
查看答案与解析
答案：
- 自反闭包 $r(R)$：$R \cup \{<2, 2>, <3, 3>, <4, 4>\}$
- 对称闭包 $s(R)$：$R \cup \{<4, 2>, <4, 3>\}$
- 传递闭包 $t(R)$：$\{<1, 1>, <2, 2>, <2, 3>, <2, 4>, <3, 2>, <3, 3>, <3, 4>\}$
解析：
本题考查二元关系的闭包运算。
第一步：求自反闭包 $r(R)$
公式：$r(R) = R \cup I_A$。 $I_A = \{<1, 1>, <2, 2>, <3, 3>, <4, 4>\}$。 由于 $R$ 中已含 $<1, 1>$，故需增加其余对角线元素。 $r(R) = R \cup \{<2, 2>, <3, 3>, <4, 4>\}$。
第二步：求对称闭包 $s(R)$
公式：$s(R) = R \cup R^{-1}$。 $R^{-1} = \{<1, 1>, <3, 2>, <4, 2>, <2, 3>, <4, 3>\}$。 对比 $R$ 和 $R^{-1}$，发现 $R^{-1}$ 中新增的元素为 $\{<4, 2>, <4, 3>\}$。 故 $s(R) = R \cup \{<4, 2>, <4, 3>\}$。
第三步：求传递闭包 $t(R)$
利用 $t(R) = R \cup R^2 \cup R^3 \cup \dots$。
- $R = \{11, 23, 24, 32, 34\}$ (简写)
- $R^2 = R \circ R$:
- $23 \circ 32 \to 22$
- $23 \circ 34 \to 24$ (已有)
- $32 \circ 23 \to 33$
- $32 \circ 24 \to 34$ (已有)
- $11 \circ 11 \to 11$ (已有)
- $R^2 = \{11, 22, 24, 33, 34\}$
- $R \cup R^2 = \{11, 22, 23, 24, 32, 33, 34\}$ 经验证，该集合已满足传递性，即为 $t(R)$。
难度: ⭐⭐
考点: #二元关系 #自反闭包 #对称闭包 #传递闭包
💡 学习锦囊
📖 相关公式与知识点:
- $r(R) = R \cup \Delta$
- $s(R) = R \cup R^{-1}$
- $t(R)$ 的矩阵解法：使用 Warshall 算法。
思路分析
- 自反：对角线全 1。
- 对称：矩阵转置后相加。
- 传递：找路径。如果存在 $a \to b$ 和 $b \to c$，必须有 $a \to c$。
易错点
- 对称闭包：不要重复添加 $R$ 中已有的元素（如 $<3, 2>$ 的对称项 $<2, 3>$ 已经在 $R$ 中了）。
- 传递闭包：最容易漏掉 $R^2$ 产生的自环元素（如 $<2, 2>, <3, 3>$）。
🔄 举一反三
- 若 $R = \{<1, 2>, <2, 3>\}$，求 $t(R)$。
查看练习答案与解析
答案：$\{<1, 2>, <2, 3>, <1, 3>\}$。
解析：因为有 1 到 2 且 2 到 3，根据传递性必须增加 1 到 3。
三、证明题（本大题共2小题，第1小题5分，第2小题10分，总计15分）
- 设 $A, B, C$ 是三个集合，证明： $(A - B) - C = (A - C) - B$
查看答案与解析
解析：
本题考查集合运算的基本定义和性质。
证明步骤： 利用集合差运算的定义：$A - B = A \cap \overline{B}$。
左边 (LHS)：
根据交法的结合律和交换律：
右边 (RHS)：
结论： 由于 LHS = RHS，故 $(A - B) - C = (A - C) - B$ 得证。
难度: ⭐
考点: #集合论 #集合恒等式 #差集定义
💡 学习锦囊
📖 相关公式与知识点:
- 差集定义：$A - B = \{x \mid x \in A \land x \notin B\}$
- 集合恒等式：$A - B = A \cap \overline{B}$
- 交法结合律：$(A \cap B) \cap C = A \cap (B \cap C)$
思路分析
证明集合相等最常用的方法是将“差集”转换为“交集与补集”的形式，然后利用交集的结合律和交换律进行整理。
易错点
- 差集展开错误：误以为 $A - (B - C) = (A - B) - C$。注意差集不满足结合律。
- 括号处理：展开补集时，务必注意括号对 $\cap$ 和 $\cup$ 的影响。
🔄 举一反三
- 证明 $A - (B \cup C) = (A - B) \cap (A - C)$。
查看练习答案与解析
解析： $A - (B \cup C) = A \cap \overline{(B \cup C)}$ 根据德·摩根律：$= A \cap (\overline{B} \cap \overline{C})$ 根据幂等律和结合律：$= (A \cap \overline{B}) \cap (A \cap \overline{C})$$= (A - B) \cap (A - C)$。
- 证明等价式： $(\forall x)(A(x)\to B)\Leftrightarrow (\exists x)A(x)\to B$
查看答案与解析
解析：
本题考查谓词逻辑中的量词分配律与等价变换。注意此处 $B$ 中不含自由变量 $x$。
证明步骤： 我们将等价号两边都化为不含蕴涵符号的形式。
左边 (LHS)：
利用 $P \to Q \equiv \neg P \lor Q$：
由于 $B$ 中不含 $x$，利用量词分配律：
右边 (RHS)：
利用 $P \to Q \equiv \neg P \lor Q$：
利用量词转换律（德·摩根律）：
结论： 因为 LHS 和 RHS 逻辑等价于同一个公式，故等价式成立。
难度: ⭐⭐
考点: #谓词逻辑 #量词转换 #等价式证明
💡 学习锦囊
📖 相关公式与知识点:
- 蕴涵等价式：$P \to Q \equiv \neg P \lor Q$
- 量词转换律：$\neg (\exists x)A(x) \equiv (\forall x)\neg A(x)$
- 量词分配律：若 $x$ 不在 $B$ 中出现，则 $(\forall x)(A(x) \lor B) \equiv (\forall x)A(x) \lor B$
思路分析
处理谓词逻辑等价证明的“万能钥匙”：
- 消除蕴涵符号 $\to$。
- 移动否定符号 $\neg$ 到谓词前面。
- 利用量词分配律处理不含变量 $x$ 的项。
易错点
- 量词转换规则：$\neg (\exists x)A(x) \iff (\forall x)\neg A(x)$。初学者常忘记转换量词。
- 作用域误判：当 $x$ 离开量词作用域时，必须确认该变量在该项中不含自由变量 $x$。
🔄 举一反三
- 证明 $(\forall x)(B \to A(x)) \Leftrightarrow B \to (\forall x)A(x)$。
查看练习答案与解析
解析： LHS: $(\forall x)(\neg B \lor A(x)) \equiv \neg B \lor (\forall x)A(x)$。 RHS: $B \to (\forall x)A(x) \equiv \neg B \lor (\forall x)A(x)$。 两者一致，得证。
四、推理题（本大题共15分）
将下列命题推理符号化并给出形式证明： 已知今天下雨或刮风；如果今天下雨，那么我在家看书；如果今天刮风，那么我去放风筝；今天我没有在家看书。所以今天刮风并且我去放风筝了。
查看答案与解析
解析：
本题考查命题逻辑的形式证明（自然演绎系统）。
第一步：命题符号化
设：
- $P$：今天下雨
- $Q$：今天刮风
- $R$：我在家看书
- $S$：我去放风筝
前提：
- $P \lor Q$
- $P \to R$
- $Q \to S$
- $\neg R$
结论： $Q \land S$
第二步：形式证明
(1) $P \to R$ & 前提引入
(2) $\neg R$ & 前提引入
(3) $\neg P$ & (1)(2) 拒取式 (MT)
(4) $P \lor Q$ & 前提引入
(5) $Q$ & (3)(4) 析取三段论 (DS)
(6) $Q \to S$ & 前提引入
(7) $S$ & (5)(6) 肯定前件 (MP)
(8) $Q \land S$ & (5)(7) 合取引入 (Conj)
结论： 推理有效。
难度: ⭐⭐⭐
考点: #命题逻辑 #形式证明 #自然演绎 #符号化
💡 学习锦囊
📖 相关公式与知识点:
- 肯定前件 (MP)：$A \to B, A \Rightarrow B$
- 拒取式 (MT)：$A \to B, \neg B \Rightarrow \neg A$
- 析取三段论 (DS)：$A \lor B, \neg A \Rightarrow B$
- 假言三段论 (HS)：$A \to B, B \to C \Rightarrow A \to C$
思路分析
- 精准建模：先将自然语言翻译为逻辑符号。
- 逆向思维：观察结论 $Q \land S$，发现需要分别证明 $Q$ 和 $S$。
- 寻找路径：
- 证明 $Q$：利用 $P \lor Q$。由于已知 $\neg R$ 且 $P \to R$，可得 $\neg P$，进而得 $Q$。
- 证明 $S$：有了 $Q$ 和 $Q \to S$，立刻得 $S$。
易错点
- 前提漏掉：推理题必须注明每一步的依据（如由哪几行公式通过哪个规则得出）。
- 结论写错：符号化时注意“或” ($\lor$) 与 “且” ($\land$) 的区别。
学习建议
掌握常见的推理规则名缩写（MP, MT, DS, HS, Conj），在答题时标注清楚能显著提高得分率。
🔄 举一反三
- 若前提变为 $P \to Q, R \to S, P \lor R$，证明结论 $Q \lor S$。
查看练习答案与解析
解析： 这是典型的构造性二难推理。 (1) $P \to Q$ (前提) (2) $R \to S$ (前提) (3) $P \lor R$ (前提) (4) $Q \lor S$ (由(1)(2)(3) 构造性二难 CD)
五、证明题（本大题共10分）
设正整数集合 $\mathbb{I}_{+}$ 上的二元关系 $R = \{< x, y> \mid x, y \in \mathbb{I}_{+}, \frac{x - y}{2} \in \mathbb{Z}\}$，证明：$R$ 为等价关系。
查看答案与解析
解析：
证明一个二元关系是等价关系，需要依次证明其满足：自反性、对称性和传递性。
证明步骤：
自反性： 对于任意 $x \in \mathbb{I}_{+}$，有 $x - x = 0$。 因为 $\frac{x - x}{2} = \frac{0}{2} = 0 \in \mathbb{Z}$， 所以 $<x, x> \in R$，即 $R$ 满足自反性。
对称性： 对于任意 $x, y \in \mathbb{I}_{+}$，若 $<x, y> \in R$， 则 $\frac{x - y}{2} = k \in \mathbb{Z}$。 那么 $\frac{y - x}{2} = - \frac{x - y}{2} = -k$。 由于 $k \in \mathbb{Z}$，故 $-k \in \mathbb{Z}$， 所以 $<y, x> \in R$，即 $R$ 满足对称性。
传递性： 对于任意 $x, y, z \in \mathbb{I}_{+}$，若 $<x, y> \in R$ 且 $<y, z> \in R$， 则存在 $k_1, k_2 \in \mathbb{Z}$，使得 $\frac{x - y}{2} = k_1$ 且 $\frac{y - z}{2} = k_2$。 那么 $\frac{x - z}{2} = \frac{(x - y) + (y - z)}{2} = \frac{x - y}{2} + \frac{y - z}{2} = k_1 + k_2$。 由于 $k_1, k_2 \in \mathbb{Z}$，故 $k_1 + k_2 \in \mathbb{Z}$， 所以 $<x, z> \in R$，即 $R$ 满足传递性。
结论： 由于 $R$ 满足自反性、对称性和传递性，故 $R$ 是 $\mathbb{I}_{+}$ 上的等价关系。
难度: ⭐⭐
考点: #二元关系 #等价关系证明 #代数性质
💡 学习锦囊
📖 相关公式与知识点:
- 等价关系三要素：自反、对称、传递。
- 模运算本质：本题 $R$ 实际上是模 2 同余关系 $x \equiv y \pmod 2$。
思路分析
这类证明题有固定套路：
- 自反：令 $y=x$，看结果是否成立。
- 对称：交换 $x, y$，看表达式是否依然属于该集合。
- 传递：利用 $x-z = (x-y) + (y-z)$ 这个桥梁进行推导。
易错点
- 描述不完整：证明传递性时，必须明确写出 $k_1, k_2 \in \mathbb{Z}$ 且其和也属于 $\mathbb{Z}$。
- 自反性漏掉：虽然自反性最简单，但在证明题中如果不写会扣分。
🔄 举一反三
- 设 $R = \{<x, y> \mid x, y \in \mathbb{Z}, x + y \text{ 是偶数}\}$，证明 $R$ 是等价关系。
查看练习答案与解析
解析：
- 自反：$x+x=2x$ 是偶数。
- 对称：$x+y=y+x$，对称成立。
- 传递：若 $x+y$ 为偶，$y+z$ 为偶，则 $(x+y)+(y+z) = x+z+2y$ 为偶，推出 $x+z$ 为偶。
- 证明集合 $A = \{1, 2, 3, 4\}$ 上的模 3 同余关系是等价关系。
查看练习答案与解析
解析： 模 $n$ 同余关系 $x \equiv y \pmod n$ 定义为 $n \mid (x-y)$。
- 自反：$3 \mid (x-x)=0$，成立。
- 对称：若 $3 \mid (x-y)$，则 $3 \mid -(x-y)=(y-x)$，成立。
- 传递：若 $3 \mid (x-y)$ 且 $3 \mid (y-z)$，则 $3 \mid ((x-y)+(y-z))=(x-z)$，成立。
六、证明题（本大题10分）
证明：若 $A \approx B$ 和 $C \approx D$，则 $A \times C \approx B \times D$。
查看答案与解析
解析：
本题考查集合基数相等（等势）的证明。
证明步骤：
背景分析： $A \approx B$ 意味着存在一个双射函数 $f: A \to B$。 $C \approx D$ 意味着存在一个双射函数 $g: C \to D$。
构造映射： 构造映射 $h: A \times C \to B \times D$，定义为： 对于任意 $(a, c) \in A \times C$，有 $h(a, c) = (f(a), g(c))$。
证明 $h$ 是双射：
- 单射性：设 $h(a_1, c_1) = h(a_2, c_2)$， 则 $(f(a_1), g(c_1)) = (f(a_2), g(c_2))$。 由有序对相等性质得 $f(a_1) = f(a_2)$ 且 $g(c_1) = g(c_2)$。 因为 $f, g$ 均为单射，所以 $a_1 = a_2, c_1 = c_2$。 故 $(a_1, c_1) = (a_2, c_2)$，$h$ 是单射。
- 满射性：对于任意 $(b, d) \in B \times D$， 因为 $f: A \to B$ 是满射，故存在 $a \in A$ 使得 $f(a) = b$。 因为 $g: C \to D$ 是满射，故存在 $c \in C$ 使得 $g(c) = d$。 所以对于 $(b, d)$，存在 $(a, c) \in A \times C$ 使得 $h(a, c) = (b, d)$。 故 $h$ 是满射。
结论： 由于存在双射 $h: A \times C \to B \times D$，故 $A \times C \approx B \times D$。
难度: ⭐⭐
考点: #集合论 #等势 #双射 #笛卡尔积
💡 学习锦囊
📖 相关公式与知识点:
- 集合等势：$|A| = |B| \iff \exists f: A \to B$ 是双射。
- 笛卡尔积映射性质。
思路分析
证明 $A \approx B$ 的唯一核心就是构造双射。看到笛卡尔积，通常就利用分量上的已知映射来合成一个新的映射。
易错点
- 双射证明不全：只构造了映射 $h$ 但不证明它是单射和满射。
- 元素形式错误：笛卡尔积的元素是有序对 $(a, c)$，映射值也是有序对。
学习建议
深刻理解“势”的概念。对于无限集，不能通过数数，只能通过“是否存在双射”来判定。
🔄 举一反三
- 设 $A \approx B$，证明：$A \times A \approx B \times B$。
查看练习答案与解析
答案： 利用已知双射 $f: A \to B$，构造 $h(a_1, a_2) = (f(a_1), f(a_2))$，证明 $h$ 是双射即可。 解析： 与本题思路完全一致，将两个分量上的同一双射组合即可得到笛卡尔积上的双射。
七、证明题（本大题10分）
设集合 $G = \{5^n \mid n \in \mathbb{Z}\}$，$\times$ 是普通乘法，证明：$< G, \times >$ 是一个群。
查看答案与解析
解析：
证明一个代数系统是群，需要验证其满足：封闭性、结合律、单位元存在性以及逆元存在性。
证明步骤：
封闭性： 对于任意 $a, b \in G$，设 $a = 5^n, b = 5^m$（其中 $n, m \in \mathbb{Z}$）。 则 $a \times b = 5^n \times 5^m = 5^{n+m}$。 因为 $n, m \in \mathbb{Z}$，所以 $n+m \in \mathbb{Z}$。 故 $a \times b \in G$，封闭性成立。
结合律： 因为 $G$ 是实数集的子集，且普通乘法在实数集上满足结合律， 所以乘法在 $G$ 上自然满足结合律。 即对于任意 $a, b, c \in G$，$(a \times b) \times c = a \times (b \times c)$。
单位元： 令 $e = 5^0 = 1$。显然 $e \in G$（因为 $0 \in \mathbb{Z}$）。 对于任意 $a = 5^n \in G$，有 $1 \times 5^n = 5^n \times 1 = 5^n$。 故单位元为 $1$。
逆元： 对于任意 $a = 5^n \in G$，令 $a^{-1} = 5^{-n}$。 因为 $n \in \mathbb{Z}$，所以 $-n \in \mathbb{Z}$，故 $a^{-1} \in G$。 且 $5^n \times 5^{-n} = 5^{n-n} = 5^0 = 1 = e$。 故 $G$ 中每个元素都存在逆元。
结论： 由于满足上述四个条件，$< G, \times >$ 是一个群。
难度: ⭐⭐
考点: #代数系统 #群论 #群的定义
💡 学习锦囊
📖 相关公式与知识点:
- 群的四个性质：封闭、结合、单位元、逆元。
- 阿贝尔群（交换群）：若还满足交换律。
思路分析
本题属于群论的入门级证明题。重点在于清楚地写出四个步骤，并注意说明为什么结果仍然属于集合 $G$（通常是因为指数 $n$ 仍然是整数）。
易错点
- 忽略封闭性：很多同学默认运算结果一定在集合内，但在群论中，封闭性是第一步。
- 单位元未验证：必须证明 $a \times e = e \times a = a$。
🔄 举一反三
- 证明所有偶数构成的集合对加法构成群。
查看练习答案 with 解析
解析：
- 封闭：偶数+偶数=偶数。
- 结合：加法满足。
- 单位元：0 是偶数。
- 逆元：若 $2k$ 是偶数，则 $-2k$ 也是偶数。
八、证明题（本大题10分）
设正实数集合 $\mathbb{R}_{+}$ 和实数集合 $\mathbb{R}$，$\cdot$ 和 $+$ 分别是普通乘法和加法。定义映射 $f: \mathbb{R}_{+} \to \mathbb{R}$，$\forall x \in \mathbb{R}_{+}, f(x) = \ln x$。证明 $f$ 是从 $\langle \mathbb{R}_{+}, \cdot \rangle$ 到 $\langle \mathbb{R}, + \rangle$ 的同构。
查看答案与解析
解析：
证明两个代数系统同构，需要证明映射 $f$ 满足：
- $f$ 是双射（单射且满射）。
- $f$ 保持运算（同态性）。
证明步骤：
证明 $f$ 是双射：
- 单射性：设 $f(x_1) = f(x_2)$，即 $\ln x_1 = \ln x_2$。 根据对数函数的性质（单调性），可得 $x_1 = x_2$。
- 满射性：对于任意 $y \in \mathbb{R}$，取 $x = e^y$。 因为 $e^y > 0$，所以 $x \in \mathbb{R}_{+}$。 且 $f(x) = \ln(e^y) = y$。 故 $f$ 是满射。 因此，$f$ 是从 $\mathbb{R}_{+}$ 到 $\mathbb{R}$ 的双射。
证明 $f$ 保持运算（同态）： 对于任意 $x_1, x_2 \in \mathbb{R}_{+}$： 左边运算后的映射值为：$f(x_1 \cdot x_2) = \ln(x_1 \cdot x_2)$。 右边映射值运算结果为：$f(x_1) + f(x_2) = \ln x_1 + \ln x_2$。 根据对数公式 $\ln(ab) = \ln a + \ln b$，有：
$$f(x_1 \cdot x_2) = f(x_1) + f(x_2)$$这说明 $f$ 保持了运算关系。
结论： 由于 $f$ 是双射且满足同态性质，故 $f$ 是从 $\langle \mathbb{R}_{+}, \cdot \rangle$ 到 $\langle \mathbb{R}, + \rangle$ 的同构。
难度: ⭐⭐⭐
考点: #代数系统 #同构 #同态 #对数函数
💡 学习锦囊
📖 相关公式与知识点:
- 同态定义：$f(a \ast b) = f(a) \circ f(b)$。
- 同构：双射同态。
- 对数基本性质：$\ln(xy) = \ln x + \ln y$。
思路分析
同构证明题的关键在于：
- 验证“运算保持”：这是最核心的一步，本题本质就是对数的运算性质。
- 验证“一一对应”：说明映射是一对一且填满目标空间的。
易错点
- 满射性证明遗漏：只证明了单射（通过单调性），忘记证明 $\mathbb{R}$ 中每个值都有原像。
- 符号混乱：注意 $\mathbb{R}_{+}$ 和 $\mathbb{R}$ 上的运算分别是乘法和加法，不要写错。
学习建议
同构在代数中表示两个结构“本质相同”。理解了这一点，就能明白为什么对数映射能把复杂的乘法运算转化为简单的加法运算。
🔄 举一反三
- 证明 $f(x) = 2x$ 是从 $\langle \mathbb{R}, + \rangle$ 到其自身的同构。
查看练习答案 with 解析
解析：
- 双射：直线 $y=2x$ 是双射。
- 保持运算：$f(x_1 + x_2) = 2(x_1 + x_2) = 2x_1 + 2x_2 = f(x_1) + f(x_2)$。