《离散数学》部分期末题目题解¶

18-19 A¶

一、判断题（共10小题，每小题1分，共10分）¶

1. 若 \(|A|+|B|=|A∪B|\) ，则 \(A∩B=∅\) （）

对。说明并集没有删元素，所以是交集是空集。

1. 若 \(A⊆B\) ，则 \(A - B=∅\) （）

对。集合的差就是排除操作。A-B 就是把 B 的所有元素排除出 A。

1. 自然数的小于关系是等价关系 （）

错。等价关系满足自反性，对称性和传递性。但是小于不满足自反性和对称性。

1. 存在6个顶点，16条边的简单无向图 （）

错。6 个顶点形成的图里面，边数最少的是链，6 条边；最多的是 6 阶完全图，6 * 5 / 2 = 15 条边。

1. 非同构的3个结点的有向树的个数是3 （）

错。三个节点连两条边，一共 4 种可能。两种链状是同构的，放射状的算另一种，向中间汇聚的不是树。因此加起来是 2 个。

1. 可逆函数一定是满射的 （）

对。可逆 = 满射+单射。

1. 在正整数集上加法和减法运算都可以保证封闭性 （）

群论不考 错。减法不满足

1. “水星上面有水”不是命题。 （）

错。简单陈述句，真假二元。是命题。

1. \(<Z, +>\) 是群，单位元是0，每个 \(i∈Z\) 的逆元是 \(-i\) （）

群论不考

1. 自然数集是可数集 （）

是。对比：NZQ都是可数的，R和C不是，参考希尔伯特对角线论证。

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

1. 半群、群及独异点的关系是（）

   A．{半群}⊂{独异点}⊂{群}

   B．{独异点}⊂{半群}⊂{群}

   C．{独异点}⊂{群}⊂{半群}

   D．{半群}⊂{群}⊂{独异点}

群论不考

1. 下述能构成集合 \(S=\{Alice,Bob,Tom,Jane\}\) 的分划的是（）

   A． \(\{\{Alice\},\{Bob,Alice,Tom\},\{Jane\}\}\)

   B． \(\{\{Alice\},\{Bob,Jane\},\{Tom\}\}\)

   C． \(\{\{Bob\},\{Jane\}\}\)

   D． \(\{\{Cindy\},\{Bob\},\{Tom\},\{Jane\}\}\)

B。分划的意思就是不重不漏做分割。

1. 设 \(A=\{a,b,c,d\}\) ，A上的关系 \(ρ=\{(a,a),(a,c),(b,b),(b,d),(c,c),(c,a),(d,a)\}\) ，则 \(ρ\) 是（）

   A．自反的

   B．对称的

   C．传递的

   D．以上均不是

D。由于不存在 (d,d) 因此不是自反的；由于存在 (b,d) 但是不存在 (d,b) 因此不是对称的；由于存在 (d,a) (a,c) 但是不存在 (d,c) 因此不是传递的。

1. 设简单无向图G所有结点的度数之和为24，则G中某一结点的度数可能为（）

   A．15

   B．14

   C．13

   D．12

D。由于握手定理可知，边数只有 12。那么这个节点度数怎么都不可能超过 12.

1. 已知 \(f:A→B\) 为一可逆函数，则下列说法可能成立的是（）

   A． \(|A|=3, |B|=2\)

   B．f不是满射

   C．A为整数集，B为偶数集

   D．f的逆函数不是单射

C。如果可逆，则 AB 至少要等势或者数量相等，A 排除。可逆=单射+满射， B 排除。C 两个集合是等势的。可逆函数的逆也是可逆的，也就是说 D 错误

1. 下列构成群的是（）

   A． \(<整数集Z, *>\)

   B． \(<有理数集Q, *>\)

   C． \(<整数集Z, +>\)

   D． \(<自然数集N, ->\)

群论不考。

1. 已知简单无向图G有n个结点，n-2条边（n>3），则下列说法错误的是（）

   A．至少存在一个结点，没有边与之相连

   B．G中一定没有回路

   C．G所有结点的度数之和为2n-4

   D．G一定不是连通的

AB

注意 n 个节点，n-1 条边的连通图是树，树的每一条边都是割边，因此 G 可以是两棵树构成的森林。当然，我们也可以考虑将森林的边相互挪动以制造更多的连通分量。但无论如何我们看看选项。

A：考虑 4 个节点，两条边连接 12 和 34，证伪 A。

B: 考虑 5 个节点，由两个孤立点和一个三元环构成，这证伪 B。

C: 对的，因为握手定理。

D：看上面的分析。

1. 下列不是可数集的是（）

   A．0到1之间的所有实数

   B．0到5之间的所有有理数

   C．所有偶数

   D．1到100之间的所有奇数

A。不解释。

1. 下列公式中为永真式的是（）

   A． \((P→Q)∧(¬P)→Q\)

   B． \((P→Q)∧(R→Q)→(P→R)\)

   C． \((P→Q)∧(Q→P)→(P∧Q)\)

   D． \((P→Q)∧(Q→R)→(P→R)\)

D

首先分析一下题目的所有式子都是类似 \(A\land B\rightarrow C\) 类型的。

A：考虑 P 是假，则前面一坨是真，这个时候真值由 Q 决定，不是重言式。

B：考虑 Q 是真，同理前面一坨是真，真值取决于 P 和 R。

C: 前面一坨就是等价，也就需要 P 和 Q 的真值相等。但是 P=Q=0 时后件为假。

D: 这个从语义层面比较明显。考虑前件为真的情况，如果 P 是 1 那么后续 Q 和 R 就得是 1；如果 P 是 0 那么后件默认是 1。

1. 已知简单无向图G是树，且G有2020个顶点，则G一定有（）

   A．2018条边

   B．2019条边

   C．2020条边

   D．2021条边

B。不解释，之前说过了。

三、填空题（共10小题，每空2分，共20分）¶

1. 写出 \(A=\{m,n\}\) ，则A的幂集 \(2^A=\) ______。

\(\{\emptyset, \{m\}, \{n\}, \{m,n\}\}\)

1. 已知 \(g,h:R→R\) ， \(g(x)=3x+1\) ， \(h(x)=x-2\) 。则复合函数 \((g∘h)(x)=\) ______。

\(3(x-2)+1 = 3x-5\)

1. 设 \(A=\{1,2,3,4\}\) 上关系 \(ρ_1=\{(1,2),(2,4),(3,3)\}\) ， \(ρ_2=\{(2,3),(2,4),(4,2)\}\) ，则复合关系 \(ρ_1∘ρ_2=\) ______。

\(\{(1,3),(1.4),(2,2)\}\)

1. 设 \(*\) 是集合S上的二元运算，若运算 \(*\) 满足结合律且存在______，则称 \(<S, *>\) 为独异点。

群论不考。

1. 每个连通分支都是树的无向图称为______。

Forest

1. 设 \(A=\{1,2,3,4\}\) ， \(R=\{(1,2),(3,4),(2,2)\}\) ，则R的自反闭包 \(r(R)=\) ______。

先把自己写出来，再往后面加自反。\(\{(1,2),(3,4),(2,2),(1,1),(3,3),(4,4)\}\)

1. 设有向图 \(G<V,E>\) ， \(V=\{v_1,v_2,v_3,v_4\}\) ，若G的邻接矩阵 \(A=\begin{bmatrix} 0&1&0&1\\ 1&0&1&0\\ 0&1&0&1\\ 1&0&1&0 \end{bmatrix}\) ，则结点 \(v_1\) 的入度=______。

2。由邻接矩阵可知。

1. 设 \(P(x)\) 表示x是小鸟， \(Q(x)\) 表示x有羽毛，将命题“有羽毛的不都是小鸟”符号化______。

换句话说，存在一只小鸟，且它没有羽毛。 \(\exists x(P(x)\land \neg Q(x))\)

1. \(A=\{x∈Z|1<x<10\}\) ， \(B=\{x|x为偶数\}\) ， \(A∩B=\) ______。

\(\{2,4,6,8\}\)

1. 设G为一27阶循环群， \(g\) 为其生成元，则满足 \(g^{3m}=e\) 的最小正数 \(m=\) ______。

群论不考。

四、计算和解答题（共5小题，每小题6分，共30分）¶

1. 二年级共有学生180人，运动会有短跑、铅球、跳高三个项目。已知有28人三个项目都参加了，有65人至少参加了两个项目。若该年级参加比赛的总人次是220人次，问有多少学生没有参加任何项目。

排斥原理的变体。一共 220 人次，那么二元交集(65-28)算了 1 次，三元交集(28)算了 2 次。

也就是 180 - (220 - 65 - 28) = 53 人。

1. 构造命题公式 \((P∧¬Q)\) 的真值表。

如下。

1. 判断函数 \(f:R→R, f(x)=(x+3)(x+2)\) 是否是可逆函数？

不是。显然对于 \(y=0\) 而言，有 \(x=3,x=2\) 两个解。

1. 一棵树T有2个度为4的结点，3个度为3的结点，5个度为2的结点，其余均是度为1的结点，问T有几个度为1的结点？

考虑有 x 个节点，然后度数之和根据握手定理是 2x-2 个，于是可以列方程：

2x-2 = 8 + 9 + 10 + x - 10 => x = 19

x - 10 = 9，有 9 个。

1. 已知图G如下：

（1）写出一条从 \(v_3\) 到 \(v_7\) 长度为3的通路；

\(v_3e_8v_6e_5v_7\)

（2）写出一条长度为5的回路。

\(v_1e_3v_3e_8v_6e_5v_7e_2v_2e_1v_1\)

五、证明题（共2小题，每题10分，共20分）¶

1. 形式证明： \(P→(Q∨R), Q→¬P, S→¬R ⇒ P→¬S\)

1. 构造下面推理的证明。 “如果小明生病了，那么小明不能参加考试；如果小明不爱锻炼身体，那么小明一定会生病；小明参加了考试，所以小明一定喜爱锻炼身体。”

首先定义：

\(P\) 是“小明生病了”，\(Q\) 是小明参加考试，\(R\) 是小明爱锻炼身体。

推理流程即：\(P\rightarrow \neg Q, \neg R \rightarrow P \Rightarrow Q\rightarrow R\)

形式证明如下：

18-19 B¶

一、判断题 (共10小题,每小题1分,共10分)¶

1. 若 \(a \in A\) ，则 \(a \in A \cap B\) ( )

错。可能位于差集。

1. 若 \(A \subseteq B\) ，则 \(A \cap B = A\) ( )

对。画 Venn 图即可。

1. 非同构的5个结点的无向树的个数是2。( )

错。正戊烷、异戊烷和新戊烷。

1. 若T是一个n个节点m条边的树，则 \(m = n - 1\) 。( )

对。显然。

1. “月球明年要撞击地球”不是命题。( )

错。显然。

1. 只有双射函数才有逆函数。( )

对。双射 = 可逆。

1. 若树T的每个分支点都恰好有r个儿子，则称T为r元正则树。( )

对。正则树的定义就是要么没有儿子要么有固定数量的儿子。

1. \(K_{3,3}\) 不是平面图， \(K_{5}\) 是平面图。( )

错。参考库拉图斯基定理。

1. 是群，单位元是0，每个 \(i \in I\) 的逆元是 \(-i\) 。( )

群论不考。

1. 个体域为整数集合Z， \(\forall x \exists y(x + y = 0)\) 为真命题。( )

对。\(y=-x\) 即可。

二、单项选择题(共10小题,每小题2分,共20分)¶

1. 令P:今天下雪了，Q:路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为( )

A. \(P \to \neg Q\)

B. \(P \vee \neg Q\)

C. \(P \wedge Q\)

D. \(P \wedge \neg Q\)

D。

简单的合取。

1. 设 \(A = \{a, b, c\}\) ，R是A上的二元关系， \(R = \{<a, a>, <a, b>, <a, c>, <c, a>\}\) ，那么R是( )

A. 反自反的

B. 反对称的

C. 可传递的

D. 不可传递的

C.

A: 由于存在 因此不是反自反的。

B: 由于存在 因此不是反对称的。

C: 验证一下就知道了

D: 同上。

1. 设集合 \(A = \{a, b, c\}\) 上的关系如下，不具有对称性的是( )

A. \(R = \{<a, c>, <c, a>, <a, b>, <b, a>\}\)

B. \(R = \{<a, c>, <b, c>, <c, a>\}\)

C. \(R = \{<a, b>, <c, c>, <b, a>\}\)

D. \(R = \{<a, a>, <b, b>\}\)

B。缺了个

1. 若T是一个(n,m)树，则( )

A. \(m = n - 1\)

B. \(n = m - 1\)

C. \(n - m + k = 2\)

D. \(m = 2n - 1\)

A. 题目大致可能是想问 n 个节点 m 条边的树。

1. 下述式子错误的是( )

A. \(\phi \in \{\phi\}\)

B. \(\phi \subseteq \{\phi\}\)

C. \(\phi \in \{\{\phi\}\}\)

D. \(\phi \subseteq \phi\)

C。“含空集作为唯一元素的集合的集合”的唯一元素是“含空集作为唯一元素的集合”。

1. 下述不能构成 \(A = \{1,2,3,4\}\) 的分划的是( )

A. \(\{\{1\}, \{2,3\}, \{4\}\}\)

B. \(\{\{1\}, \{1,2,3\}, \{4\}\}\)

C. \(\{A\}\)

D. \(\{\{1\}, \{2\}, \{3\}, \{4\}\}\)

B。出现了重复。

1. 设集合 \(A = \{1,2,3\}\) ，下列关系R中不是等价关系的是( )

A. \(R = \{<1,1>, <2,2>, <3,3>\}\)

B. \(R = \{<1,1>, <2,2>, <3,3>, <3,2>, <2,3>\}\)

C. \(R = \{<1,1>, <2,2>, <3,3>, <1,2>\}\)

D. \(R = \{<1,1>, <2,2>, <3,3>, <1,2>, <2,1>, <1,3>, <3,1>, <2,3>, <3,2>\}\)

C。比如说 <1,2> 就不满足对称性。

1. 下列函数中为双射的是( )

A. \(f: Z \to Z, f(i) = i^2\)

B. \(f: N \to N, f(j) = \begin{cases}1, j 是奇数 \\ 0, j 是偶数 \end{cases}\)

C. \(f: Z \to N, f(j) = |2j| + 1\)

D. \(f: R \to R, f(r) = 2r - 15\)

D。显然里面没有不可逆操作。

1. 下列命题公式为重言式的是( )

A. \(q \leftrightarrow (p \wedge q)\)

B. \(p \to (p \wedge q)\)

C. \((p \wedge q) \to p\)

D. \((p \vee q) \to q\)

C。前件为真时，后件一定为真。

1. 在有n个结点的连通图中，其边数( )

   A. 至少有n-1条

   B. 最多有n-1条

   C. 至少有n条

   D. 最多有n条

A。树。

三、填空题(共10小题,每空2分,共30分)¶

1. \(A = \{a, \{a\}\}\) ，则A的幂集 $P(A) = $ ________

\(\{\emptyset, \{a\}, \{\{a\}\}, \{a, \{a\}\}\}\)

1. 利用哈夫曼算法求带权为1,2,3,4,5的最优2元树T，则T的权 \(W(T) =\) ________

如下：

1
2
3
4
5
6
7
8
9

       15
      /  \
    6      9
   / \    / \
  3   3  4   5
 / \
1   2

W = 1 * 3 + 2 * 3 + 3 * 2 + 4 * 2 + 5 * 2 = 3 + 6 + 6 + 8 + 10 = 33

1. 对于如右图所示二元有序树T，后序行遍的结果为________

BDECA

1. 命题公式 \((P \wedge Q) \to \neg P\) 的成假指派为________

PQ = 11

1. 设 \(P(x)\) 表示x发光， \(Q(x)\) 表示x是金子，将命题“发光的不都是金子”符号化________

\(\exists x (P(x)\land \neg Q(x))\)

1. Z为整数集，设全集 \(U = \{i | i \in Z 且 1 \leq i < 10\}\) ， \(A = \{1,4,5,6,8\}\) ， \(B = \{4,5,9\}\) ，则 \(\sim A \cap B =\) ________， \(A - B =\) ________

\(\{9\}\), \(\{1,6,8\}\)

1. 关系 \(R = \{<1,0>, <0,1>, <2,1>, <3,0>\}\) ，则R的定义域为________，值域为________

\(\{0,1,2,3\}\), \(\{0,1\}\)

1. 设 \(A = \{1,2,3,4\}\) ， \(R \subseteq A × A\) ， \(R = \{<1,2>, <3,4>, <2,2>\}\) ，则R的自反闭包 \(r(R) =\) ________，对称闭包 \(s(R) =\) ________

\(\{<1,2>,<3,4>,<1,1>,<2,2>,<3,3>,<4,4>\}\) 和 \(\{<1,2>,<2,1>,<3,4>,<4,3>,<2,2>\}\)

1. 设 \(A = \{1,2,3,4\}\) 上关系 \(R = \{<1,2>, <2,4>, <3,3>\}\) ， \(S = \{<2,3>, <2,4>, <4,2>\}\) ，则复合关系 \(R \circ S =\) ________， \(S \circ R =\) ________

\(R \circ S =\{<1,3>, <1,4>, <2,2>\}\), \(S \circ R =\{<2,3>, <4,4>\}\)

1. 有理数集Q中的 * 运算定义如下： \(a^* b = a + b - ab\) ，则 * 运算的单位是________

群论不考。

四、计算和解答题(1-5每小题6分,6小题10分,共40分)¶

1. 集合 \(A = \{a, b, c, d\}\) ，A上的关系 \(R = \{<a, a>, <b, b>, <a, b>, <b, a>, <c, c>, <d, d>\}\) ，判断R是否为等价关系，如果是等价关系，给出对应于R的A的等价分划。

显然是，这对应了图的三个连通分量，对应的分划是：

\(\{\{a,b\},\{c\},\{d\}\}\)

1. 集合 \(A = \{1,2,3,4\}\) ，A上的关系 \(R = \{<1,2>, <2,3>, <3,4>, <3,1>, <4,3>\}\) 。画出关系R的关系图，并计算逆关系 \(R^{-1}\) 和复合关系 \(R^2\) 。

逆关系只需要颠倒次序即可。\(R^{-1} = \{<2,1>, <3,2>, <4,3>, <1,3>, <3,4>\}\)

复合关系的获取方法同前。\(R^2 = \{<1,3>, <2,4>, <2, 1>, <3,3>, <3,2>, <4,4>, <4,1>\}\)

1. 构造命题公式 \(((P \vee Q) \to (Q \wedge R)) \to (P \wedge \neg R)\) 的真值表，并给出其主析取范式。

主析取范式只需要成真赋值即可。\((P\land \neg Q \land R)\lor(\neg P\land Q \land R)\lor(\neg P\land Q \land \neg R)\lor(\neg P\land \neg Q \land R)\)

1. 无向图G如下所示。

(1) G是否是欧拉图？是否存在欧拉通路，若存在欧拉通路请给出。

只有 v3 和 v4 两个度数是奇数的节点，因此是存在欧拉通路的，但不存在欧拉回路，因此不是欧拉图。

欧拉通路：\(v_3v_1v_2v_6v_5v_2v_4v_5v_3v_4\)

(2) 给出G的最小生成树，并计算最小生成树的权。

这里简单用克鲁斯卡尔算法。计算的权为 1+2+1+4+6 = 14

1. 构造下面推理的证明。 “如果肖寒是理科生，那么他的逻辑思维能力应该不差。如果肖寒不是文科生，一定是理科生。肖寒的逻辑思维能力很差，所以肖寒一定是文科生。”

符号约定：

\(P\): 肖寒是理科生

\(Q\): 肖寒是文科生

\(R\): 肖寒的逻辑思维能力很差

推理内容即 \(P\rightarrow\neg R, \neg Q \rightarrow P, R\rightarrow Q\)

构造符号化证明：

2021A¶

一、判断题（共10小题，每小题1分，共10分）¶

1. 论述“ \(2+2=4\) 当且仅当3是奇数”是复合命题.（）

对。这是两个原子命题用等价联结词联结而成的复合命题。

1. 有向图的邻接矩阵不一定具有对称性.（）

对。考虑单向边。

1. 两个图如果满足结点数相同，边数相同且度数相同的结点数目相同，则同构.（）

错。同构没有多项式的判断条件。一个很简单的反例是 \(K_{3,3}\) 和下面的图不同构，但是满足条件：

1. 集合 \(A\) 的对称关系一定不是反对称的.（）

错。反对称的定义是如果交换关系里面元素次序还成立，可以推出两元素相等。比如说恒等关系就满足。这和对称关系不构成对立。

1. 任何树 \(T\) 都至少有两片叶子.（）

错。反例是平凡树。

1. 有向图 \(G=(V,E)\) ，其中 \(V=\{a,b,c,d\}\) ， \(E=\{\lt a,b\gt, \lt a,d\gt, \lt b,c\gt, \lt c,d\gt\}\) ，则图 \(G\) 为强连通图.（）

错。验证即可。注意是有向图。

1. 5个基本联结词的运算顺序为： \(\neg, \land, \lor, \leftrightarrow, \to\) .（）

错。注意等价的优先级最低。

1. 设 \(A、B、C\) 为任意的3个集合，则笛卡尔积： \(A \times (B \times C) = (A \times B) \times C\) .（）

错。注意这不是多元笛卡尔积。

1. 函数 \(f: N \to N,f(n) = 2n + 1\) 是单射函数.（）

对。函数值相等确实可以推出自变量相等。

1. 在谓词演算中， \(P(a)\) 是 \(\forall xP(x)\) 的有效结论，根据的是存在推广规则.（）

错。根据的是全称指定规则。从 \(P(a)\) 推导 \(\exists x P(x)\) 才是存在推广规则。

二、单项选择题（共10小题，每小题1分，共10分）¶

1. 下列句子哪一个是真命题：（）.

A. 我正在说谎

B. 如果 \(1+1=0\) ，那么雪是黑色的

C. \(9+5>18\)

D. 存在最大的素数

B

A 是悖论，不是命题；B 前件为假则默认为真；C 显然假；D 显然假。

1. 设 \(M(x):x\) 是人， \(P(x):x\) 会犯错误，则命题“没有不犯错误的人”可符号化为（）.

A. \(\forall x(M(x)\land P(x))\)

B. \(\neg(\exists x(M(x)\to \neg P(x)))\)

C. \(\neg(\exists x(M(x)\land P(x)))\)

D. \(\neg(\exists x(M(x)\land \neg P(x)))\)

D.

首先 A B 都不满足搭配规则。C 说的是不存在犯错误的人。

1. 下图描述的偏序集中，子集 \(\{b,e,f\}\) 的上界为（）.

A. \(a,c\)

B. \(a,b\)

C. \(b\)

D. \(a,b,c\)

C。根据偏序关系可以知道 \(b\ge e, b\ge f\) 因此上界是 \(b\)。

1. 设 \(A=\{\{1, 2\}, \{3\}, \{4, 5\}, \{6, 7, 8\}\}\) ，下列选项正确的是（）.

A. \(1 \in A\)

B. \(\{1,2,3\} \in A\)

C. \(\{4, 5\} \in A\)

D. \(\varnothing \in A\)

C。只需要匹配元素即可。

1. 设集合 \(A = \{1, 2, 3, 4\}\) ， \(A\) 上的关系 \(R=\{\lt1,1\gt, \lt2,2\gt, \lt1,3\gt\}\) ，则 \(R\) 具备（）.

A. 自反性

B. 传递性

C. 对称性

D. 都不对

D。原题。

1. 所有使命题公式 \(P \lor (Q \land \neg R)\) 为真的赋值为（）.

A. \(010,100,101,110,111\)

B. \(010,100,101,111\)

C. 全体赋值

D. 不存在

A。 首先测试 000 排除 C，然后测试 010 排除 D，最后测试 110 排除 B。

1. 设 \(A=\{1,2,3\}\) ， \(B=\{a,b\}\) ，下列各二元关系中是 \(A\) 到 \(B\) 的函数的是（）.

A. \(R = \{\lt1,a\gt,\lt2,a\gt,\lt3,a\gt\}\)

B. \(R = \{\lt1,a\gt,\lt2,a\gt,\lt2,b\gt,\lt3,a\gt\}\)

C. \(R = \{\lt1,a\gt,\lt2,b\gt\}\)

D. \(R = \{\lt2,a\gt,\lt2,b\gt\}\)

A。B 和 D 存在一对多，C 没有覆盖 A。

1. 设 \(R\) 为实数集，映射 \(f: R \to R\) ， \(f(x) = x^2+2x-1\) ，则 \(f\) 是（）.

A. 单射而非满射

B. 满射而非单射

C. 双射

D. 既不是单射，也不是满射

D。首先 f 有最小值，这意味着它没有射满 \(R\)，对于同一个函数值，有两个解，意味着不是单射。

1. 设个体域为整数域，下列公式真值为1的是（）.

A. \(\forall x\exists y(x + y = 0)\)

B. \(\exists y\forall x(x + y = 0)\)

C. \(\forall x\forall y(x + y = 0)\)

D. \(\neg\exists x\exists y(x + y = 0)\)

A。里面东西都是 x+y=0 那么很容易想到正确表述是对于所有整数 x 都存在一整数 y 使得 x+y = 0 这就对应 A。

1. 下图属于（）图.

A. 偶图

B. 欧拉图

C. 哈密顿图

D. 偶图、哈密顿图

D。首先看它有没有长度为奇数的回路，发现没有于是是偶图；然后哈密顿回路也很好找，绕外圈快走完的时候拐到内圈即可。图里面有 8 个度数是奇数的顶点，因此不是欧拉图。

三、填空题（共15空，每空2分，共30分）¶

1. 公式 \(\forall x(A(x) \to B(y,x))\land \exists zC(y,z) \to D(m)\) 的自由变元是______，约束变元是______.

x, z 和 y, m

1. \(n\) 个顶点的无向完全图有边数______，每个结点的度数为______.

n(n-1) / 2 和 n-1

1. 一棵树有2个2度顶点，1个3度顶点，3个4度顶点，则叶子结点有______个.

\(x + 2*2 + 1*3 + 3*4=2(x+2+1+3-1), x = 9\)

1. 设 \(A=\{\{a,b\},\{c\}\},B=\{\{a\},\{b,c\},\{c\}\}\) ，则 \(A \cup B =\) ______，幂集 \(\rho(A) =\) ______.

\(A\cup B=\{\{a,b\},\{c\},\{a\},\{b,c\}\}\), \(\rho(A) =\{\emptyset,\{\{a,b\}\},\{\{c\}\},\{\{a,b\},\{c\}\}\}\)

1. 设 \(A=\{1,2,3,4\}\) ， \(A\) 上的二元关系 \(R\) 定义为： \(R=\{\lt1,2\gt,\lt2,1\gt,\lt2,3\gt,\lt3,4\gt\}\) ，则 \(R\) 的自反闭包为______，对称闭包为______，传递闭包为______.

\(r(R)=\{\lt1,2\gt,\lt2,1\gt,\lt2,3\gt,\lt3,4\gt,<1,1>,<2,2>,<3,3>,<4,4>\}\)

\(s(R)=\{\lt1,2\gt,\lt2,1\gt,\lt2,3\gt,<3,2>,\lt3,4\gt,<4,3>\}\)

\(t(R)=\{\lt1,2\gt,\lt2,1\gt,\lt2,3\gt,<1,3>,\lt3,4\gt,<1,4>,<2,4>\}\)

1. 在具有 \(n\) 个顶点的有向图中，任何基本通路的长度都不超过______.

最长需要把每个顶点访问一次，也就是 n-1。

1. 设 \(f(x)=1+x\) ， \(g(x)=1+x^2\) ，则 \(f\circ g =\) ______.

\(2+x^2\)

1. 设无向图 \(G\) 的邻接矩阵为 \(\begin{bmatrix} 0 & 1 & 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 \end{bmatrix}\) ，则 \(G\) 的顶点数与边数分别为______.

6 和 11

1. 设 \(R\) 是集合 \(A=\{1,2,...,10\}\) 上的模7同余关系，则2的等价类 \([2]_R=\) ______， \(R\) 对应的 \(A\) 的划分的秩为______.

\(\{2,9\}\) 和 7

四、计算与解答题(共5小题，每小题6分，共30分)¶

1. (6分) 求公式 \(\neg(p\lor q)\lor r\) 的主析取范式和主合取范式。

列真值表即可。然后从成真赋值里面获得主析取范式，从成假赋值里面获得主合取范式。

主析取范式：\((\neg p \land \neg q \land \neg r)\lor(\neg p \land \neg q \land r)\lor(\neg p \land q \land r)\lor(p \land \neg q \land r)\lor(p \land q \land r)\)

主合取范式：\((\neg p \lor q \lor \neg r)\land(p \lor \neg q \lor \neg r)\land(p \lor q \lor \neg r)\)

1. (6分) 对102名学生调查表明，有35人学日语，20人学法语，45人学英语，15人既学日语又学英语，8人既学日语又学法语，10人既学法语又学英语，28人不学这3门课中的任何一门。

（1）(2分) 求三门语言都学的人数；

（2）(2分) 求至少学习两门语言的人数；

（3）(2分) 求只学英语，只学法语，只学日语的人数。

1. 设 \(A=\{a,b,c,d\}\) ， \(A\) 上的关系 \(R=\{\lt a,a\gt,\lt a,b\gt,\lt a,c\gt,\lt c,a\gt,\lt c,b\gt,\lt c,c\gt,\lt d,a\gt,\lt d,b\gt,\lt d,c\gt\}\)

（1）(2分) 画出 \(R\) 的关系图 \(G_R\) ；

（2）(2分) 判断 \(R\) 所具有的性质（自反/反自反性、对称/反对称性和传递性）；

（3）(2分) 求 \(R\) 的关系矩阵 \(M_R\) 。

1. (6分) 利用避圈法或破圈法求以下带权图的最小生成树。

1. (6分) 画一棵带权为3,4,5,6,7,8,9的最优二叉树，计算该树的权重。

五、证明题(共3小题，共20分)¶

1. (6分) 构造推理证明：“所有牛都有角，有些动物是牛，所以有些动物有角。”

2. (6分) 证明：若树中至少有一个节点的度大于等于 \(k\) ，则树中至少有 \(k\) 个度为1的结点。

1. (8分) 假设给定正整数的序偶集合 \(A\) ，在 \(A\) 上定义二元关系 \(R\) 如下： \(\lt\lt x,y\gt,\lt u,v\gt\gt \in R\) 当且仅当 \(xv=yu\) ，证明 \(R\) 为等价关系。

1
2
3
4
5
6
7

@online{Discrete_exams,
    title={《离散数学》部分期末题目题解},
    author={Yan Li},
    year={2026},
    month={Jan},
    url={\url{https://dicaeopolis.github.io/campus-sources/Discrete_exams}},
}