离散数学作为计算机科学与技术的重要基础课程之一，其理论知识和应用能力对于学生未来的学习与发展具有深远影响。本篇文章将围绕离散数学期末考试的相关内容展开，旨在帮助大家更好地理解知识点并提升解题技巧。

一、选择题

1. 下列哪个选项是命题逻辑中的永真式？

A. \( p \rightarrow q \)

B. \( \neg p \lor q \)

C. \( p \land q \rightarrow r \)

D. \( (p \lor q) \land (\neg p \lor \neg q) \)

解析：根据命题逻辑的性质，\( (p \lor q) \land (\neg p \lor \neg q) \) 是一个永真式，因为它等价于 \( p \leftrightarrow q \)，即无论 \( p \) 和 \( q \) 的真假值如何，该表达式的值始终为真。

2. 在图论中，以下哪种图一定是连通的？

A. 完全图

B. 二分图

C. 树

D. 轮图

解析：完全图是指任意两个顶点之间都有一条边相连，因此它一定是连通的。而二分图、树和轮图并不一定满足连通性条件。

二、填空题

1. 设集合 \( A = \{1, 2, 3\} \)，则 \( A \) 上的所有关系共有 _______ 种。

答案：\( 2^9 \)（因为 \( |A|^2 = 9 \)，每个元素对都可以有“属于”或“不属于”的关系）。

2. 若函数 \( f: X \to Y \) 是满射，则当且仅当 \( |X| \geq |Y| \)。

解析：满射意味着 \( Y \) 中的每个元素至少有一个原像，因此 \( X \) 的元素数量必须大于等于 \( Y \) 的元素数量。

三、解答题

1. 设 \( G \) 是一个无向简单图，若 \( G \) 的顶点数为 \( n \)，边数为 \( m \)，且 \( m > \frac{n(n-1)}{4} \)，证明 \( G \) 必定包含一个三角形。

证明：假设 \( G \) 不含任何三角形，则 \( G \) 的最大度数不超过 \( \lfloor \sqrt{m} \rfloor \)。此时，边数 \( m \leq \frac{n}{2} \cdot \lfloor \sqrt{m} \rfloor \)，通过计算可得矛盾，从而证明 \( G \) 必定包含一个三角形。

2. 求解递推关系 \( T(n) = T(n-1) + T(n-2) \)，其中 \( T(0) = 0 \)，\( T(1) = 1 \)。

解答：此递推关系实际上就是著名的斐波那契数列，其通项公式为：

\[ T(n) = \frac{\phi^n - \psi^n}{\sqrt{5}} \]

其中 \( \phi = \frac{1+\sqrt{5}}{2} \)，\( \psi = \frac{1-\sqrt{5}}{2} \)。

四、综合题

设 \( R \) 是集合 \( A = \{1, 2, 3, 4\} \) 上的关系，定义为 \( R = \{(1,2), (2,3), (3,4), (4,1)\} \)。请回答以下问题：

1. 判断 \( R \) 是否为自反关系。

2. 判断 \( R \) 是否为对称关系。

3. 求出 \( R \) 的传递闭包。

解析：

1. \( R \) 不是自反关系，因为对角线上的元素 \( (1,1), (2,2), (3,3), (4,4) \) 均不在 \( R \) 中。

2. \( R \) 不是对称关系，因为存在 \( (1,2) \in R \)，但 \( (2,1) \notin R \)。

3. \( R \) 的传递闭包为 \( R^ = \{(1,2), (2,3), (3,4), (4,1), (1,3), (2,4), (3,1), (4,2)\} \)。

以上便是本次离散数学期末考试的部分试题及其参考答案。希望这些题目能够帮助同学们巩固所学知识，并在考试中取得优异的成绩！