河南大学计算机与信息工程学院 2013～2014 学年第一学期期末考试#
《 离散数学 》试卷（A 卷）#
考试方式： 闭卷
考试时间： 120 分钟
卷面总分： 100 分
适用专业： 计算机科学与技术 / 软件工程 / 网络工程 / 人工智能
一、 单项选择题（本题共 15 小题，每小题 2 分，共 30 分）#
1. 用 P 表示命题“派小王参加下周的会议”，用 Q 表示命题“派小李参加下周 of 的会议”，则命题“小王和小李两个人中必须派一人且只能派一人参加下周的会议”可以表示为______。 [ ]
- A. P∧¬Q
- B. P→¬Q
- C. (¬P∧Q)∨(P∧¬Q)
- D. (P→¬Q)∨(Q→¬P)
2. 设命题公式 G 为：¬P→(Q∧R)，则下列选项中（依次为 P,Q,R 的真值）哪个是公式 G 的成假解释______。 [ ]
- A. T, F, T
- B. T, T, T
- C. F, F, F
- D. F, T, T
3. 下列公式中正确的等价式是______。 [ ]
- A. ¬(∃x)A(x)⇔(∃x)¬A(x)
- B. ¬(∀x)A(x)⇔(∃x)¬A(x)
- C. (∀x)(∀y)A(x,y)⇔(∃y)(∀x)A(x,y)
- D. (∀x)(A(x)∨B(x))⇔(∀x)A(x)∨(∀x)B(x)
4. 设 X,Y,Z 为任意集合，且 X⊕Y={1,2,3}，X⊕Z={2,3,4}，若 2∈Y，则一定有______。 [ ]
- A. 1∈Z
- B. 2∈Z
- C. 3∈Z
- D. 4∈Z
5. 下列函数是双射的是______。 [ ]
- A. f:R→R,f(x)=2x+1
- B. f:Z+→R,f(x)=lnx （其中 Z+ 为正整数集）
- C. f:R→Z,f(x)=⌊x⌋
- D. f:R→R,f(x)=−x2+2x−1
6. 下列选项哪一项构成集合 {a,b,c,d,e,f,g} 的划分______。 [ ]
- A. {{a,b,c},{d,e},{f,g,h}}
- B. {{a,b},{c,d,e},{e,f,g}}
- C. {{a},{b,c,d},{f,g}}
- D. {{a,b,c,d},{e},{f,g}}
7. 设 S={1,2,3}，其上二元关系 R 的关系图如图 1 所示，则 R 具有______性质。 [ ]
图1
- A. 自反性、对称性、传递性
- B. 自反性、反对称性
- C. 自反性、反对称性、传递性
- D. 自反性
8. 设 S={0,1}，∗ 为普通乘法，则 ⟨S,∗⟩ 是______。 [ ]
- A. 半群，但不是独异点
- B. 只是独异点，但不是群
- C. 群
- D. 环，但不是群
9. 在______中，补元是唯一的。 [ ]
- A. 有界格
- B. 有补格
- C. 分配格
- D. 有补分配格
10. 下面偏序集中的图______能构成格。 [ ]
图2
- A. 图 A
- B. 图 B
- C. 图 C
- D. 图 D
11. 设 + 和 ∘ 为普通加法和普通乘法，则下列集合 S 与 +, ∘ 可以构成域的是______。 [ ]
- A. S={x∣x=2n∧n∈Z}
- B. S={x∣x=2n+1∧n∈Z}
- C. S={x∣x∈Z∧x≥0}=N
- D. S={x∣x=a+b3,a,b∈Q}
12. 设 G 是 5 个顶点的完全图，则从 G 中删去______条边可以得到树。 [ ]
13. 在一棵树中有 7 片树叶，3 个 3 度结点，其余都是 4 度结点，则该树有______个 4 度结点。 [ ]
14. 下图中，______是欧拉图。 [ ]
图3
- A. 图 A
- B. 图 B
- C. 图 C
- D. 图 D
15. 下图所示的二叉树中，后序遍历的结果是______。 [ ]
图4
- A. abcde
- B. edcba
- C. bdeca
- D. badce
二、 填空题（本题共 10 空，每空 2 分，共 20 分）#
1. 设集合 A={x∣x=n2∧x∈N}，N 为自然数集，则 A 的基数为______。
2. 设集合 A={{1,2},1}，则幂集 P(A)=______。
3. 设集合 A={1,2,3,4}，A 上的二元关系 R={⟨1,1⟩,⟨1,2⟩,⟨2,3⟩}，S={⟨1,3⟩,⟨2,3⟩,⟨3,2⟩}，则 R∘S=______。
4. 设关系 R={⟨1,1⟩,⟨1,2⟩,⟨2,3⟩}，则 R 的对称闭包是______。
5. 设 G=⟨a⟩ 是 15 阶循环群，则 G 的所有生成元个数有______个。
6. 设 Z 为整数集，∀a,b∈Z，a∘b=a+b−1，则任意 a∈Z 的逆元 a−1=______。
7. 设 G=⟨a⟩ 为 12 阶循环群，则 G 的 4 阶子群是______。
8. 设连通平面图有 n 个结点，m 条边，r 个面，则它们的关系是______。
9. 所有非同构的 5 阶根树有______棵。
10. 高为 h 的正则 2 叉树至少有______片树叶。
三、 计算题（本题共 4 小题，每小题 10 分，共 40 分）#
1. 求公式 (P→(R∨P))∧(Q↔P) 的主合取范式及主析取范式。
2. 设集合 A={1,2,3,4,6,8,12}，R 为 A 上的整除关系。
(1) 画出偏序集 ⟨A,R⟩ 的哈斯图；
(2) 写出 A 的子集 B={4,6} 的上确界，下确界；
(3) 写出 A 的最大元，最小元，极大元，极小元。
3. 设 ⟨Z6,+6⟩ 是一个群，这里 +6 是模 6 加法，Z6={0,1,2,3,4,5}，试求出 ⟨Z6,+6⟩ 的所有子群及其相应左陪集。
4. 一公司在五个城市 C1,C2,…,C5 中都有分公司，从 Ci 到 Cj 的班机费如下图所示，对上述五个城市中计算 C1 到其它城市费用最低的路线。（要求写出求解过程）
图5
四、 证明题（本题共 1 小题，共 10 分）#
1. 在自然推理系统中，构造下面推理的证明：
前提：实数不是有理数就是无理数，无理数都不是分数
结论：若有分数，则必有有理数（个体域为实数集合）
