河南大学计算机与信息工程学院期末考试#

《 离散数学 1 》试卷#

考试方式： 闭卷 考试时间： 120 分钟 卷面总分： 100 分 适用专业： 计算机科学与技术 / 软件工程 / 网络工程 / 人工智能

---

一、 判断题（本题共 10 小题，每小题 2 分，共 20 分）#

1. $\{\neg, \to\}$ 不是极小全功能集。 ( )

2. 封闭的公式在任何解释下都变成命题。 ( )

3. $\exists x(F(x) \wedge G(x)) \Leftrightarrow \exists x F(x) \wedge \exists x G(x)$ ( )

4. 设 $A、B、C$ 为任意集合，则 $(A \cap B) \cup (B - A) = B$。 ( )

5. 在一个偏序关系中，一定存在惟一的一个最大元或最小元。 ( )

---

6. 设 $V_1 = \langle S_1, * \rangle, V_2 = \langle S_2, *' \rangle$ 是两个具有二元运算的代数系统，$\varphi$ 是 $V_1$ 到 $V_2$ 的同态，若 $*$ 是可交换的，则 $*'$ 在 $V_2$ 中也是可交换的。 ( )

7. 循环群的子群一定是循环群。 ( )

8. 一个有向图是强连通的充要条件是存在经过每个顶点的回路。 ( )

9. 图 $G$ 的对偶图 $G^*$ 的对偶图 $G^{**}$ 一定与 $G$ 同构。 ( )

10. 设 $n$ 阶无向连通 $G$ 有 $m$ 条边，则 $m \ge n-1$。 ( )

---

二、 单项选择题（本题共 10 小题，每小题 2 分，共 20 分）#

1. 令 $p$：今天下雪了，$q$：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为______。 [ ]

• A. $p \wedge \neg q$
• B. $p \vee \neg q$
• C. $p \wedge q$
• D. $p \to \neg q$

2. 一个命题公式或一阶逻辑公式的______是不惟一的。 [ ]

• A. 主析取范式
• B. 主合取范式
• C. 前束范式
• D. 对偶式

3. 设 $X, Y, Z$ 是集合，下列结论不正确的是______。 [ ]

• A. 若 $X \subseteq Y$，则 $X \cap Y = X$
• B. $(X-Y)-Z = X-(Y \cap Z)$
• C. $X \oplus X = \emptyset$
• D. $X-Y = X \cap (\sim Y)$

4. $X = \{a, b, c, d, e\}$，$Y = \{1, 2, 3, 4\}$，$f$ 从 $X$ 到 $Y$ 的映射，其中 $f(a)=2, f(b)=4, f(c)=2, f(d)=3, f(e)=2$，则 $f$ 是______。 [ ]

• A. 双射
• B. 满射
• C. 单射
• D. 不是单射也不是满射

5. 设 $V = \langle \mathbf{Z}, + \rangle$，其中“+”是普通加法。$\forall x \in \mathbf{Z}$，令 $\varphi_1(x)=x$，$\varphi_2(x)=-x$，$\varphi_3(x)=x+5$，$\varphi_4(x)=2x$，其中有______个自同构。 [ ]

• A. 1
• B. 2
• C. 3
• D. 4

---

6. 设 $\langle L, \wedge, \vee \rangle$ 是一个格，则它不满足______。 [ ]

• A. 交换律
• B. 结合律
• C. 消去律
• D. 吸收律

7. 3 个顶点 2 条边的非同构的有向简单图共有______个。 [ ]

• A. 1
• B. 2
• C. 3
• D. 4

8. 对于任意的 $p (p \ge 2)$ 个连通分支的平面图 $G$，有 $n-m+r =$______。 [ ]

• A. $p + 1$
• B. $p - 1$
• C. $2p + 1$
• D. $2p - 1$

9. 关于无向树的描述，不正确的是______。 [ ]

• A. 无向树是连通图、没有回路，每个边都是桥
• B. 无向树是连通图、没有回路，每个顶点都是割点
• C. 无向树是连通图、没有回路，每条边都是割边
• D. 无向树是连通图、边数比顶点数少 1，任意两个顶点的路径惟一

10. 一颗二叉树后序遍历的结果是 bdeca，中序遍历的结果是 badce，则根结点的右子树有______个结点。 [ ]

• A. 1
• B. 2
• C. 3
• D. 4

---

三、 填空题（本题共 5 小题，每小题 3 分，共 15 分）#

1. $((p \vee q) \wedge \neg q) \to p$ 从公式的类型看，它属于____________式。

2. $A = \{a, b\}$，则 $A$ 的幂集 $P(A)$ 到自身的双射有____________个。

3. 6 阶循环群有____________个子群。

4. 已知 $n$ 阶无向图 $G$ 中有 $m$ 条边，各顶点的度数均为 3。又已知 $2n-3=m$，则 $m =$____________。

5. 最优 2 元树有 $n$ 片树叶，则它有____________个分支点。

---

四、 计算题（本题共 4 小题，共 25 分）#

1. (6 分) 用等值演算法求公式 $((p \vee q) \to r) \to p$ 的主析取范式。

2. (6 分) $R_1 = \{\langle 1,2 \rangle, \langle 1,3 \rangle, \langle 2,3 \rangle\}$，$R_2 = \{\langle 2,2 \rangle, \langle 2,3 \rangle, \langle 3,4 \rangle\}$，求： (1) $R_1 - R_2$； (2) $R_1^{-1}$； (3) 求 $R_2 \circ R_1$。

3. (7 分) 设 $\langle A, R \rangle$ 为一个偏序集，其中 $A = \{1, 2, 3, 4, 6, 9, 12, 24\}$，$R$ 是 $A$ 上的整除关系。 (1) 画出 $R$ 的哈斯图； (2) 求 $A$ 的极大元和极小元； (3) 求 $B = \{4, 6\}$ 的上确界和下确界。

4. (6 分) 画一棵带权为 $2, 2, 2, 3, 3, 4, 5, 8$ 的最优二叉树 $T$，并计算它的权 $W(T)$。

---

五、 综合题（本题共 2 小题，每小题 10 分，共 20 分）#

1. (10 分) 给出下列证明的推理过程： 前提：$p \to (q \to s)$，$q$，$p \vee \neg r$ 结论：$r \to s$

2. (10 分) 已知 $\langle M_n(\mathbf{Z}), + \rangle$（即整数集上 2 阶方阵构成的集合关于矩阵的加法）构成群，$H = \left\{ \begin{pmatrix} a & 0 \\ 0 & a \end{pmatrix} \;\middle|\; a \in \mathbf{Z} \right\}$。 (1) $\langle M_n(\mathbf{Z}), + \rangle$ 的单位元是什么？$\begin{pmatrix} 1 & -2 \\ 3 & 4 \end{pmatrix}$ 的逆元是什么？ (2) 证明：$H$ 是 $\langle M_n(\mathbf{Z}), + \rangle$ 的子群。