【离散数学期末考试试题与答案】随着学期的临近，离散数学课程的期末考试也逐渐进入备考阶段。为了帮助同学们更好地复习和掌握知识点，以下是一份模拟的离散数学期末考试试题与参考答案，内容涵盖集合论、逻辑学、图论、关系与函数等核心章节。
一、选择题（每题2分，共10分）
1. 下列哪个命题是真命题？
A. 若 a > b，则 a² > b²
B. 若 a + b = 0，则 a = -b
C. 所有整数都是自然数
D. 集合 {1, 2, 3} 的子集个数为 6
答案：B
2. 设集合 A = {1, 2}, B = {2, 3}，则 A ∪ B 是：
A. {1}
B. {1, 2, 3}
C. {2}
D. {1, 3}
答案：B
3. 命题“如果今天下雨，那么我不出门”的逆否命题是：
A. 如果我不出门，那么今天下雨
B. 如果今天不下雨，那么我出门
C. 如果我出门，那么今天没下雨
D. 如果今天没下雨，那么我不出门
答案：C
4. 在一个无向图中，所有顶点的度数之和一定是：
A. 奇数
B. 偶数
C. 负数
D. 零
答案：B
5. 函数 f: R → R 定义为 f(x) = x²，该函数是：
A. 单射
B. 满射
C. 双射
D. 非单射非满射
答案：D
二、填空题（每空2分，共10分）
1. 集合 {a, b, c} 的幂集元素个数为 ______。
答案：8
2. 命题 “p ∧ (q ∨ r)” 的对偶式是 ______。
答案：p ∨ (q ∧ r)
3. 在一个简单无向图中，若顶点数为 n，边数最多为 ______。
答案：n(n-1)/2
4. 设 f: A → B 是一个函数，若对于任意 x₁, x₂ ∈ A，当 x₁ ≠ x₂ 时，f(x₁) ≠ f(x₂)，则称 f 为 ______ 函数。
答案：单射
5. 设 R 是集合 A 上的一个关系，若对于所有 a ∈ A，都有 (a, a) ∈ R，则 R 具有 ______ 性质。
答案：自反
三、简答题（每题5分，共15分）
1. 什么是逻辑蕴含？请举例说明。
答：逻辑蕴含是指在命题逻辑中，若 p → q 为真，则称 p 蕴含 q。例如：如果今天下雨（p），那么地会湿（q）。即 p → q 成立。
2. 简述图的欧拉回路与哈密尔顿回路的区别。
答：欧拉回路是指经过图中每条边一次且仅一次的回路；哈密尔顿回路是指经过图中每个顶点一次且仅一次的回路。
3. 什么是等价关系？请写出其三个性质。
答：等价关系是满足自反性、对称性和传递性的关系。例如：集合上的相等关系就是一个典型的等价关系。
四、解答题（每题10分，共20分）
1. 设集合 A = {1, 2, 3, 4}，定义关系 R ⊆ A × A 如下：
R = { (1,1), (2,2), (3,3), (4,4), (1,2), (2,1), (3,4), (4,3) }
请判断 R 是否为等价关系，并说明理由。
解：
- 自反性：(1,1), (2,2), (3,3), (4,4) 存在，满足自反性。
- 对称性：(1,2) 和 (2,1) 同时存在；(3,4) 和 (4,3) 同时存在，满足对称性。
- 传递性：检查是否所有 (a,b) 和 (b,c) 都有 (a,c)。
例如：(1,2) 和 (2,1) 存在，但 (1,1) 已存在；(3,4) 和 (4,3) 存在，(3,3) 也存在。
但 (1,2) 和 (2,1) 并不推出 (1,1) 以外的其他关系，因此传递性成立。
结论：R 是等价关系。
2. 给定命题公式 P → (Q → R)，请将其化为只含 ¬ 和 ∧ 的形式，并写出其真值表。
解：
- 根据逻辑等价关系，P → Q 等价于 ¬P ∨ Q。
- 因此，P → (Q → R) 等价于 ¬P ∨ (¬Q ∨ R)。
- 再根据分配律，可写为 (¬P ∨ ¬Q) ∨ R，进一步整理为 ¬P ∨ ¬Q ∨ R。
- 或者写成 ¬P ∧ ¬Q ∧ R 的否定形式？不对，应保持原结构。
- 最终表达式为：¬P ∨ ¬Q ∨ R。
真值表如下：
| P | Q | R | P→(Q→R) |
|---|---|---|---------|
| 0 | 0 | 0 |1|
| 0 | 0 | 1 |1|
| 0 | 1 | 0 |1|
| 0 | 1 | 1 |1|
| 1 | 0 | 0 |1|
| 1 | 0 | 1 |1|
| 1 | 1 | 0 |0|
| 1 | 1 | 1 |1|
五、应用题（15分）
设某学校有 5 个班级，每个班级有 30 名学生。现需从这些学生中选出若干名代表组成校级委员会。要求：
1. 每个班级至少选 1 名代表；
2. 总人数不超过 10 人。
问：有多少种不同的选法？
解：
这是一个典型的组合问题，属于“限制条件下的组合计数”。
设每个班级选出的学生数分别为 x₁, x₂, x₃, x₄, x₅，其中 x_i ≥ 1 且 x₁ + x₂ + x₃ + x₄ + x₅ ≤ 10。
令 y_i = x_i - 1 ≥ 0，代入得：y₁ + y₂ + y₃ + y₄ + y₅ ≤ 5。
求非负整数解的个数，相当于求 y₁ + y₂ + y₃ + y₄ + y₅ + y₆ = 5（引入虚拟变量 y₆ 表示剩余名额）。
使用“隔板法”计算：C(5 + 6 - 1, 6 - 1) = C(10, 5) = 252。
答案：252 种不同的选法。
结语：
离散数学作为计算机科学与数学的重要基础学科，理解其基本概念与逻辑推理方法至关重要。希望本套试题能帮助大家巩固知识，顺利通过期末考试。祝大家考出好成绩！
