习题

单选题

1. 设 X = {1,2,3,4}，Y = {5,6,7,8,9}，给定 f = {⟨1,5⟩, ⟨2,6⟩, ⟨3,7⟩, ⟨4,8⟩}，下列选项中正确的是

A. f 是从 X 到 Y 的单射

B. f 是从 X 到 Y 的满射

C. f 是从 X 到 Y 的双射

D. f 不是从 X 到 Y 的映射（函数）

知识点：
函数：每个 x 有且只有一个 y 与之对应，允许不同的 x 对应相同的 y（y 值可以重复）
单射：要求不同的 x 对应不同的 y（y 值不能重复）
满射：要求 y 的值必须取全
双射：单射 + 满射

答案：A

f 中 1→5，2→6，3→7，4→8，每个 x 对应唯一且不同的 y，满足单射条件。但 Y 中的 9 没有被映射到，不满足满射，故 f 是单射但不是双射。

2. 在一个 6 阶简单无向图中，其结点的最大度数为

A. 2　　B. 3　　C. 4　　D. 5

知识点：
n 阶简单无向图中，最大度数为 n-1

答案：D

3. 设论域元素为 a, b，与 ∀xR(x) ∧ (∃y)S(y) 等价的是

A. (R(a) ∧ R(b)) ∧ (S(a) ∧ S(b))

B. (R(a) ∧ R(b)) ∧ (S(a) ∨ S(b))

C. (R(a) ∨ R(b)) ∧ (S(a) ∧ S(b))

D. (R(a) ∨ R(b)) ∧ (S(a) ∨ S(b))

知识点：
全称量词：∀xR(x) 在有限论域下展开为 R(a) ∧ R(b)
存在量词：∃yS(y) 在有限论域下展开为 S(a) ∨ S(b)

答案：B

两者合取即为 (R(a) ∧ R(b)) ∧ (S(a) ∨ S(b))。

4. 设论域是正整数，下列谓词公式中值为真的是

A. ∀x∃y(x² + y² = 10)

B. ∀y∃x(x² + y² = 10)

C. ∀x∀y(x² + y² = 10)

D. ∃x∃y(x² + y² = 10)

答案：D

解析：

A、B：对所有正整数 x（或 y）都要找到对应的 y（或 x）使等式成立，显然不可能，为假
C：要求所有正整数对都满足，显然为假
D：只需存在某个 x 和 y 使等式成立即可，x = 1, y = 3 时 1 + 9 = 10，为真

5. 设 A = {a, ∅}，P(A) 是 A 的幂集，下列选项中正确的是

A. {a} ∈ P(A)，{a} ⊆ P(A)

B. ∈ P(A)， ⊆ P(A)

C. {a} ∈ P(A)，{∅} ∈ P(A)

D. {a} ∈ P(A)，{∅} ⊆ P(A)

知识点： A = {a, ∅}，其幂集为 P(A) = {∅, {a}, {∅}, {a, ∅}}

答案：C

{a} ∈ P(A) ✓（{a} 是 A 的子集）
{∅} ∈ P(A) ✓（{∅} 是 A 的子集）

8. 一个 8 阶简单图的边数最大为

A. 20　　B. 25　　C. 28　　D. 30

知识点：
n 阶简单图的最大边数为n(n-1)/2

答案：C

9. R = {⟨0,1⟩, ⟨1,2⟩, ⟨2,3⟩}，S = {⟨2,1⟩, ⟨1,2⟩, ⟨3,3⟩}，下列正确的是

A. ran(R) ⊂ ran(R ∩ S)

B. ran(S) = ran(R ∪ S)

C. dom(R) = dom(S)

D. dom(R) ∪ dom(S) = ran(R) ∪ ran(S)

答案：B

解析：

dom(R) = {0,1,2}，ran(R) = {1,2,3}
dom(S) = {1,2,3}，ran(S) = {1,2,3}

逐项验证：

A：ran(R ∩ S) = ran({⟨1,2⟩}) = {2}，ran(R) = {1,2,3}，{1,2,3} ⊄ {2}，错误
B：ran(R ∪ S) = {1,2,3}，ran(S) = {1,2,3}，两者相等，正确
C：dom(R) = {0,1,2}，dom(S) = {1,2,3}，不相等，错误
D：dom(R) ∪ dom(S) = {0,1,2,3}，ran(R) ∪ ran(S) = {1,2,3}，不相等，错误

10. 设 f: R → R，f(x) = x²（x ≥ 3）或 -2（x < 3）；g: R → R，g(x) = x + 2，则 g∘f: R → R 是

A. 单射不满射

B. 满射不单射

C. 不单射不满射

D. 双射

知识点： g∘f(x) = g(f(x))：

答案：C

计算题

1.研究4阶完全图，判断其是否存在欧拉回路？是否存在哈密顿回路？如果存在，共有多少个非同构的回路？

答案：

对于4阶完全图，每个结点的度数均为3，为奇数，因而不存在欧拉回路。（2分）

中存在哈密顿回路。（2分）

而且存在3个不同构的哈密顿回路。（2分）

2.构造命题公式的真值表。

答案：（列表得2分，基本正确得4分，完整得6分）


0	0	0	1	1	0
0	0	1	1	1	1
0	1	0	0	1	0
0	1	1	0	1	1
1	0	0	1	1	0
1	0	1	1	1	1
1	1	0	0	0	0
1	1	1	0	0	0

3.给出集合上所有等价关系的个数，并列出这些关系的集合表达式。

答案：

上的等价关系共有5个。（1分）

它们分别是：（1分）

R₁ = {⟨1,2⟩, ⟨2,1⟩, ⟨1,3⟩, ⟨3,1⟩, ⟨3,2⟩, ⟨2,3⟩} ∪ Iₐ（1分）

R₂ = {⟨2,3⟩, ⟨3,2⟩} ∪ Iₐ（1分）

R₃ = {⟨1,3⟩, ⟨3,1⟩} ∪ Iₐ（1分）

R₄ = {⟨1,2⟩, ⟨2,1⟩} ∪ Iₐ

R₅ = Iₐ

4.求命题公式的主析取范式和主合取范式。

答案：

(1) 主析取范式

¬(P ∨ (Q ∧ R))

⟺ ¬P ∧ (¬Q ∨ ¬R)

⟺ (¬P ∧ ¬Q) ∨ (¬P ∧ ¬R)

⟺ (¬P ∧ ¬Q ∧ R) ∨ (¬P ∧ ¬Q ∧ ¬R) ∨ (¬P ∧ Q ∧ ¬R)

⟺ m₀₀₀ ∨ m₀₀₁ ∨ m₀₁₀

（3分）

(2) 主合取范式

由主析取范式可得，¬(P ∨ (Q ∧ R))

⟺ M₀₁₁ ∧ M₁₀₀ ∧ M₁₀₁ ∧ M₁₁₀ ∧ M₁₁₁

⟺ (P ∨ ¬Q ∨ ¬R) ∧ (¬P ∨ Q ∨ R) ∧ (¬P ∨ Q ∨ ¬R) ∧ (¬P ∨ ¬Q ∨ R) ∧ (¬P ∨ ¬Q ∨ ¬R)

（3分）

5.集合上有偏序关系。

(1) 画出偏序集的哈斯图；

(2) 找出的极大元、极小元、最大元和最小元。

答案：

(1) 哈斯图：（3分）

    e
   /|\
  b c d
   \|/
    a

(2)（3分）

极大元：
极小元：
最大元：
最小元：

6.用列真值表的方法说明下列逻辑等价式成立 P → (Q → R) ⟺ (P → Q) → (P → R).

答案：


000	1	1	1	1	1
001	1	1	1	1	1
010	0	1	1	1	1
011	1	1	1	1	1
100	1	1	0	0	1
101	1	1	0	1	1
110	0	0	1	0	0
111	1	1	1	1	1

从真值表可见，P → (Q → R) 与 (P → Q) → (P → R) 的真值完全相同，因此有

P → (Q → R) ⟺ (P → Q) → (P → R)

（真值表5分，最后结论1分）

7.求命题公式 Q ∧ (¬P → (Q ∨ ¬(Q → R))) 的主析取范式。

答案：

Q ∧ (¬P → (Q ∨ ¬(Q → R)))

⟺ Q ∧ (P ∨ (Q ∨ ¬(¬Q ∨ R)))

⟺ Q ∧ (P ∨ (Q ∨ (Q ∧ ¬R)))

⟺ (P ∧ Q) ∨ Q ∨ (Q ∧ ¬R)

⟺ (P ∧ Q ∧ R) ∨ (P ∧ Q ∧ ¬R) ∨ (¬P ∧ Q ∧ R) ∨ (¬P ∧ Q ∧ ¬R)

⟺ m₂ ∨ m₃ ∨ m₆ ∨ m₇

此即所求命题公式的主析取范式。（6分）

8.画出下列集合关于整除关系的哈斯图：，并指出它的极小元、极大元、最小元、最大元。

答案：（4分）

哈斯图：

由哈斯图可见：（2分）

极小元：1
极大元：24
最小元：1
最大元：24

9.有向图 D 如题30图所示，回答以下问题：(1) 写出 D 的邻接矩阵 A；(2) D 中长度为 1、2、3、4 的通路各有多少条？其中回路分别为多少条？

答案：

(1) 由图所示有向图 D，可得其邻接矩阵为（2分）

(2) 由上述，利用矩阵乘法可得（4分）

由此可知，D 中长度为 1 的通路有 8 条，长度为 2 的通路有 11 条，长度为 3 的通路有 14 条，长度为 4 的通路有 17 条；D 中长度为 1 的回路有 1 条，长度为 2 的回路有 3 条，长度为 3 的回路有 1 条，长度为 4 的回路有 3 条。

10. 设函数 f: N → N，其中 f = {<x, x+1> | x ∈ N}

(1) 说明函数 f 是否为单射和满射，并说明理由；

(2) 函数 f 的逆函数是否存在，如果存在，求出函数 f 的逆函数；

(3) 求 ran f。

知识点：
单射：不同的 x 对应不同的 y
满射：ran f = B
双射：单射 + 满射
N：自然数（正整数和0，即非负整数）

答案：

(1) f 是单射，不是满射。

单射：f(x) = x+1，若 f(x₁) = f(x₂)，则 x₁+1 = x₂+1，故 x₁ = x₂，满足单射。
不是满射：0 ∈ N，但不存在 x ∈ N 使 x+1 = 0（因为 x = -1 ∉ N），故 ran f ≠ N。

(2) f 不是双射（不是满射），故逆函数不存在。

(3) ran f = N - {0}

11. 设 A,B,C,D 四个旅游点之间的距离（单位为千米）如图所示，某游客现在位于 A 处，求他游完 4 个旅游点回到 A 处的最短路线和距离。

各边距离：AB=4, AD=2, BD=3, BC=5, AC=6, DC=7

知识点：
旅行商问题（货郎担问题）
最短哈密顿回路

答案：

最短路线为 A → D → B → C → A

最短距离为 2 + 3 + 5 + 6 = 16 千米

证明题

1.设无向图G有9个结点，每个节点的度数不是5就是6，证明：G中至少有5个6度结点或至少有6个5度结点。

知识点：
1.握手定理：任何图的所有顶点的度数之和等于边数的两倍。
2.任何图都有偶数个奇度顶点。

设有x个5度结点，则有9-x个6度结点。
因为奇数结点个数必须为偶数，所有可能组合为：
x=0,9-x=9
x=2,9-x=7
x=4,9-x=5
x=6,9-x=3
x=8,9-x=1
观察可知，G中至少有5个6度结点或至少有6个5度结点。

2.设A={⟨a,b⟩∣a,b 为正整数},在 A上定义二元关系 ∼如下：对任意 ⟨a,b⟩,⟨c,d⟩∈A，⟨a,b⟩∼⟨c,d⟩当且仅当a+d=b+c.要求：证明 ∼是一个等价关系。

知识点：
1.等价关系：自反性、对称性、传递性。
2.偏序关系：自反性、反对称性、传递性。

(1) 自反性
对，有，
所以。
故具有自反性。（2 分）

(2) 对称性
设，
则有，亦即，
所以。
故具有对称性。（2 分）

(3) 传递性设且，
则有
上述两式两边分别相加后消去，得所以。
故具有传递性。（1 分）

结论：
综合 (1)(2)(3)，是一个等价关系。（1 分）

3.设 Z 是整数集合，在 Z 上定义二元运算＊如下:∀x, y ∈ Z，x ＊ y = x + y - 2证明 Z 关于运算＊构成群。

知识点：
群需要满足以下四条公理：
1.封闭性：∀x, y ∈ Z，x ＊ y ∈ Z
2.结合律：∀x, y, z ∈ Z，(x ＊ y) ＊ z = x ＊ (y ＊ z)
3.单位元存在：∃e ∈ Z，使得 ∀x ∈ Z，e ＊ x = x ＊ e = x
4.逆元存在：∀x ∈ Z，∃x⁻¹ ∈ Z，使得 x ＊ x⁻¹ = x⁻¹ ＊ x = e

证明：∀x, y ∈ Z，x ＊ y = x + y - 2 ∈ Z，因而＊运算是封闭的。（2分）
显然，＊运算可结合，且单位元 e = 2。（2分）
∀a ∈ Z，由 (a ＊ a⁻¹) = a + a⁻¹ - 2 = e = 2，可得 a⁻¹ = 4 - a（2分）
即任一元素均存在逆元。
综上，Z 关于运算＊构成群。（1分）

4. R 为实数集，∀x, y ∈ R，证明 max(x,y) = ½(x+y+|x-y|)

证明：

当 x ≥ y 时，max(x,y) = x，

½(x+y+|x-y|) = ½(x+y+x-y) = ½(2x) = x

当 x < y 时，max(x,y) = y，

½(x+y+|x-y|) = ½(x+y+y-x) = ½(2y) = y

综上所述，max(x,y) = ½(x+y+|x-y|)，得证。

5. 设 A = {a + b√2 | a, b ∈ Z}，运算 + 是实数的加法，证明 <A, +> 是一个群。

证明：

设 a+b√2，c+d√2，e+f√2 ∈ A，其中 a,b,c,d,e,f ∈ Z

① 封闭性

(a+b√2) + (c+d√2) = (a+c) + (b+d)√2 ∈ A

因为 a+c, b+d ∈ Z，故封闭性成立。

② 结合律

((a+b√2) + (c+d√2)) + (e+f√2)

= a+b√2 + c+d√2 + e+f√2

= a+b√2 + (c+e+(d+f)√2)

= a+b√2 + (c+d√2 + e+f√2)

结合律成立。

③ 存在幺元

a+b√2 + 0 = a+b√2 = 0 + a+b√2

存在幺元 0 ∈ A。

④ 存在逆元

(a+b√2) + (-a+(-b)√2) = 0

存在逆元 -a+(-b)√2 ∈ A（因为 -a, -b ∈ Z）。

综上，<A, +> 是一个群。

综合应用题

1.某研究所要从3名科研人员A、B、C中挑选1～2人去进修，由于工作需要，选派时需要满足下列条件：

（1）若A去，则C同去；
（2）若B去，则C不能去；
（3）若C不去，则A或B可以去。
问：如何确定选派方案？

答案：设 p：派A去，q：派B去，r：派C去。
由已知条件可得：
(p→r) ∧ (q→¬r) ∧ (¬r→(p∨q))（2分）
经等值演算可得：
(p→r) ∧ (q→¬r) ∧ (¬r→(p∨q))
⟺ (¬p ∧ ¬q ∧ r) ∨ (¬p ∧ q ∧ ¬r) ∨ (p ∧ ¬q ∧ r)（2分）
因此，有3种选派方案：
（1）C去，A和B都不去；（1分）
（2）B去，A和C都不去；（1分）
（3）A、C同去，B不去。（1分）

2.某地区5个居民点之间现有道路距离见下列邻接矩阵（单位：千米）：

	A	B	C	D	E
A	0	5	12	14	5
B	5	0	9	11	8
C	12	9	0	6	10
D	14	11	6	0	7
E	5	8	10	7	0

现需利用现有道路铺设天然气管道。假定铺设成本完全由距离决定，试用最小生成树规划最低成本管道铺设方案，并确定该方案下总的铺设长度。

答案：

构造无向图，其中代表5个居民点，。（3分）

用 Kruskal 算法，按边权从小到大依次选取：

步骤	选取边	权值
1	a-b	5
2	a-e	5
3	c-d	6
4	d-e	7

得最小生成树如下：（3分）

b - 5 - a - 5 - e - 7 - d - 6 - c

此即最低成本管道铺设方案，该方案下总的铺设长度为千米。（1分）

习题 ​

单选题 ​

1. 设 X = {1,2,3,4}，Y = {5,6,7,8,9}，给定 f = {⟨1,5⟩, ⟨2,6⟩, ⟨3,7⟩, ⟨4,8⟩}，下列选项中正确的是 ​

2. 在一个 6 阶简单无向图中，其结点的最大度数为 ​

3. 设论域元素为 a, b，与 ∀xR(x) ∧ (∃y)S(y) 等价的是 ​

4. 设论域是正整数，下列谓词公式中值为真的是 ​

5. 设 A = {a, ∅}，P(A) 是 A 的幂集，下列选项中正确的是 ​

8. 一个 8 阶简单图的边数最大为 ​

9. R = {⟨0,1⟩, ⟨1,2⟩, ⟨2,3⟩}，S = {⟨2,1⟩, ⟨1,2⟩, ⟨3,3⟩}，下列正确的是 ​

10. 设 f: R → R，f(x) = x²（x ≥ 3）或 -2（x < 3）；g: R → R，g(x) = x + 2，则 g∘f: R → R 是 ​

计算题 ​

1.研究4阶完全图 ，判断其是否存在欧拉回路？是否存在哈密顿回路？如果存在，共有多少个非同构的回路？ ​

2.构造命题公式 的真值表。 ​

3.给出集合 上所有等价关系的个数，并列出这些关系的集合表达式。 ​

4.求命题公式 的主析取范式和主合取范式。 ​

5.集合 上有偏序关系 。 ​

6.用列真值表的方法说明下列逻辑等价式成立 P → (Q → R) ⟺ (P → Q) → (P → R). ​

7.求命题公式 Q ∧ (¬P → (Q ∨ ¬(Q → R))) 的主析取范式。 ​

8.画出下列集合关于整除关系的哈斯图：，并指出它的极小元、极大元、最小元、最大元。 ​

9.有向图 D 如题30图所示，回答以下问题：(1) 写出 D 的邻接矩阵 A；(2) D 中长度为 1、2、3、4 的通路各有多少条？其中回路分别为多少条？ ​

10. 设函数 f: N → N，其中 f = {<x, x+1> | x ∈ N} ​

11. 设 A,B,C,D 四个旅游点之间的距离（单位为千米）如图所示，某游客现在位于 A 处，求他游完 4 个旅游点回到 A 处的最短路线和距离。 ​

证明题 ​

1.设无向图G有9个结点，每个节点的度数不是5就是6，证明：G中至少有5个6度结点或至少有6个5度结点。 ​

2.设A={⟨a,b⟩∣a,b 为正整数},在 A上定义二元关系 ∼如下：对任意 ⟨a,b⟩,⟨c,d⟩∈A，⟨a,b⟩∼⟨c,d⟩当且仅当a+d=b+c.要求：证明 ∼是一个等价关系。 ​

3.设 Z 是整数集合，在 Z 上定义二元运算＊如下:∀x, y ∈ Z，x ＊ y = x + y - 2证明 Z 关于运算＊构成群。 ​

4. R 为实数集，∀x, y ∈ R，证明 max(x,y) = ½(x+y+|x-y|) ​

5. 设 A = {a + b√2 | a, b ∈ Z}，运算 + 是实数的加法，证明 <A, +> 是一个群。 ​

综合应用题 ​

1.某研究所要从3名科研人员A、B、C中挑选1～2人去进修，由于工作需要，选派时需要满足下列条件： ​

2.某地区5个居民点之间现有道路距离见下列邻接矩阵（单位：千米）： ​

习题

单选题

1. 设 X = {1,2,3,4}，Y = {5,6,7,8,9}，给定 f = {⟨1,5⟩, ⟨2,6⟩, ⟨3,7⟩, ⟨4,8⟩}，下列选项中正确的是

2. 在一个 6 阶简单无向图中，其结点的最大度数为

3. 设论域元素为 a, b，与 ∀xR(x) ∧ (∃y)S(y) 等价的是

4. 设论域是正整数，下列谓词公式中值为真的是

5. 设 A = {a, ∅}，P(A) 是 A 的幂集，下列选项中正确的是

8. 一个 8 阶简单图的边数最大为

9. R = {⟨0,1⟩, ⟨1,2⟩, ⟨2,3⟩}，S = {⟨2,1⟩, ⟨1,2⟩, ⟨3,3⟩}，下列正确的是

10. 设 f: R → R，f(x) = x²（x ≥ 3）或 -2（x < 3）；g: R → R，g(x) = x + 2，则 g∘f: R → R 是

计算题

1.研究4阶完全图，判断其是否存在欧拉回路？是否存在哈密顿回路？如果存在，共有多少个非同构的回路？

2.构造命题公式的真值表。

3.给出集合上所有等价关系的个数，并列出这些关系的集合表达式。

4.求命题公式的主析取范式和主合取范式。

5.集合上有偏序关系。

6.用列真值表的方法说明下列逻辑等价式成立 P → (Q → R) ⟺ (P → Q) → (P → R).

7.求命题公式 Q ∧ (¬P → (Q ∨ ¬(Q → R))) 的主析取范式。

8.画出下列集合关于整除关系的哈斯图：，并指出它的极小元、极大元、最小元、最大元。

9.有向图 D 如题30图所示，回答以下问题：(1) 写出 D 的邻接矩阵 A；(2) D 中长度为 1、2、3、4 的通路各有多少条？其中回路分别为多少条？

10. 设函数 f: N → N，其中 f = {<x, x+1> | x ∈ N}

11. 设 A,B,C,D 四个旅游点之间的距离（单位为千米）如图所示，某游客现在位于 A 处，求他游完 4 个旅游点回到 A 处的最短路线和距离。

证明题

1.设无向图G有9个结点，每个节点的度数不是5就是6，证明：G中至少有5个6度结点或至少有6个5度结点。

2.设A={⟨a,b⟩∣a,b 为正整数},在 A上定义二元关系 ∼如下：对任意 ⟨a,b⟩,⟨c,d⟩∈A，⟨a,b⟩∼⟨c,d⟩当且仅当a+d=b+c.要求：证明 ∼是一个等价关系。

3.设 Z 是整数集合，在 Z 上定义二元运算＊如下:∀x, y ∈ Z，x ＊ y = x + y - 2证明 Z 关于运算＊构成群。

4. R 为实数集，∀x, y ∈ R，证明 max(x,y) = ½(x+y+|x-y|)

5. 设 A = {a + b√2 | a, b ∈ Z}，运算 + 是实数的加法，证明 <A, +> 是一个群。

综合应用题

1.某研究所要从3名科研人员A、B、C中挑选1～2人去进修，由于工作需要，选派时需要满足下列条件：

2.某地区5个居民点之间现有道路距离见下列邻接矩阵（单位：千米）：