114 年 國立成功大學電機工程學系碩士班已組《離散數學》

核心觀念

本題考查數理邏輯（Mathematical Logic）中「命題（Proposition）」的基礎定義與判定。

1. 命題（Proposition）的定義：
   命題為一個具有明確「真值（Truth Value）」的陳述句（Declarative Sentence），其真假狀態必須是「非真即假（Either True or False, but not both）」。
2. 開放語句（Open Statement / Predicate）：
   若陳述句中包含未經量化或未給定數值的變數（Variable），導致其真值無法單獨判定，則該敘述稱為開放語句或謂詞（Predicate），不屬於命題。

---

解題方法

判定一個敘述是否為命題，切入點為檢查該敘述是否同時滿足以下兩項條件：

1. 句型必須為陳述句（排除疑問句、祈使句、感嘆句等）。
2. 真值必須客觀且唯一（無論其客觀真值為 True 或 False，只要真假狀態確定即為命題）。

若敘述中含有未綁定或未給值的自由變數（Free Variable），導致在未補充條件前無法直接給出 True 或 False，即可判定其「不是命題」。

---

選項分析

• (a) The Earth is flat.
  • 分析：此為陳述句。雖然在科學事實上為錯誤的敘述（False），但其真值是完全確定且客觀的（False）。

核心觀念

本題主要考驗**一階邏輯（First-Order Logic）中的量化命題（Quantified Statements）與質數（Prime Numbers）**的基本定義：

1. 存在量詞（Existential Quantifier, $\exists$）：命題 $\exists x \, Q(x)$ 表示在給定的定義域（Domain）中，至少存在一個元素 $x$ 使謂詞 $Q(x)$ 成立（即真值為 True）。只要能在定義域內找到一個具體符合條件的範例（Witness），該存在命題即為真。
2. 邏輯且（Conjunction, $\land$）：複合命題 $A \land B$ 唯有在 $A$ 與 $B$ 同時為 True 時，其真值才為 True。
3. 質數（Prime Number）的定義：在正整數集中，大於 $1$ 且除了 $1$ 與自身外沒有其他正因數的數。前幾個質數為 $2, 3, 5, 7, 11, 13, \dots$。
4. 雙生質數（Twin Primes）：若 $x$ 與 $x+2$ 皆為質數，則稱 $(x, x+2)$ 為一對雙生質數。

---

解題方法

本題目標為判定存在量詞命題 $\exists x (P(x) \land P(x+2))$ 的真值，其中定義域（Domain）為正整數集 $\mathbb{Z}^+ = \{1, 2, 3, 4, \dots\}$。

欲證明存在量詞命題 $\exists x (P(x) \land P(x+2))$ 為 True，僅需在定義域內找出一個特定的正整數 $k$，使得 $P(k) \land P(k+2)$ 為 True 即可：

1. 取正整數 $x = 3$：
   • 檢查 $P(3)$：$3$ 為質數，故 $P(3)$ 的真值為 True。
   • 檢查 $P(3+2) = P(5)$：$5$ 為質數，故 $P(5)$ 的真值為 True。
2. 計算合取命題 $P(3) \land P(5)$ 的真值：

解析

本題考查多項式定理（Multinomial Theorem）。

根據多項式定理，$(x_1 + x_2 + x_3)^n$ 的展開式中，一般項為：
$\frac{n!}{n_1! n_2! n_3!} x_1^{n_1} x_2^{n_2} x_3^{n_3}$
其中 $n_1 + n_2 + n_3 = n$。

將題目條件代入：

• $x_1 = x$
• $x_2 = 2y$
• $x_3 = -z$
• $n = 10$

要尋找 $x^5 y^3 z^2$ 項，對應的指數分別為 $n_1 = 5$、$n_2 = 3$、$n_3 = 2$（滿足 $5 + 3 + 2 = 10$）。

代入一般項展開：
$\frac{10!}{5! \, 3! \, 2!} \cdot (x)^5 \cdot (2y)^3 \cdot (-z)^2$

核心觀念

1. 鴿籠原理（Pigeonhole Principle）：若將 $n$ 個物品（鴿子）放入 $k$ 個盒子（鴿籠）中，且 $n > k$，則至少有一個盒子裝有至少 2 個物品。
2. 同餘與整除性（Congruence and Divisibility）：兩整數 $a, b$ 之差 $(a - b)$ 能被 $17$ 整除（即 $17 \mid (a - b)$），當且僅當 $a$ 與 $b$ 除以 $17$ 的餘數相同，即 $a \equiv b \pmod{17}$。
3. 同餘類別數量：任意整數除以 $17$ 的餘數僅有 $17$ 種可能，其餘數集合為 $\{0, 1, 2, \dots, 16\}$。

---

解題方法

本題目標為求出保證至少有兩數之差能被 $17$ 整除的「最少選取整數個數」。可以將此問題建構為鴿籠原理模型：

1. 建立鴿籠（Pigeonholes）：
   根據整數除以 $17$ 的餘數進行分類，共有 $17$ 個不同的餘數類別（鴿籠）：
   $\text{鴿籠數量 } k = 17$

2. 建立鴿子（Pigeons）：
   從 $100$ 個相異整數中選出的整數個數設為 $n$（鴿子）。

3. 推導最少選取數量：

   • 若僅選取 $17$ 個整數，最壞情況（Worst Case）為這 $17$ 個整數分別屬於 $17$ 個不同的餘數類別（即餘數恰好為 $0, 1, 2, \dots, 16$ 各一個），此時任意兩數之差皆無法被 $17$ 整除。因此選取 $17$ 個整數無法「保證」符合條件。
   • 根據鴿籠原理，當選取的整數數量 $n$ 滿足 $n \ge k + 1 = 17 + 1 = 18$ 時，必然至少有 $2$ 個整數落在同一個餘數類別中。

核心觀念

本題考查離散數學中的二元關係（Binary Relation）性質與分類。給定定義在集合 $A$ 上的二元關係 $R$，若要滿足題目要求同時具備自反性（Reflexivity）、對稱性（Symmetry）與遞移性（Transitivity），則該關係定義上稱為等價關係（Equivalence Relation）。

相關數學定義如下：

1. 自反性（Reflexive）：對於集合中的每一個元素 $x \in A$，均滿足 $x R x$。
2. 對稱性（Symmetric）：對於集合中的任意兩元素 $x, y \in A$，若 $x R y$，則必有 $y R x$。
3. 遞移性（Transitive）：對於集合中的任意三元素 $x, y, z \in A$，若 $x R y$ 且 $y R z$，則必有 $x R z$。

---

解題方法

本題屬於觀念判斷選擇題，切入點為將各選項給定的關係 $R$ 與集合 $A$ 代入上述三項基本定義，逐一檢驗其是否同時滿足自反性、對稱性與遞移性。若關係中存在任意一項不滿足的情況，則該選項即非正確答案。

---

選項分析

• (a) "<" on the set of integers ($\mathbb{Z}$)：錯誤。

  • 自反性：對任意整數 $x$，不滿足 $x < x$（例如 $1 < 1$ 不成立），故不符自反性。
  • 對稱性：若 $1 < 2$ 成立，但 $2 < 1$ 不成立，故不符對稱性。
  • 遞移性：若 $x < y$ 且 $y < z$，則必有 $x < z$，具備遞移性。
  • 小結：關係 "<" 為嚴格偏序關係（Strict Partial Order），非等價關係。

• (b) "≠" on the set of integers ($\mathbb{Z}$)：錯誤。

  • 自反性：對任意整數 $x$，不滿足 $x \neq x$（例如 $1 \neq 1$ 不成立），故不符自反性。
  • 對稱性：若 $x \neq y$，則必有 $y \neq x$，具備對稱性。
  • 遞移性：取 $x = 1, y = 2, z = 1$，此時 $1 \neq 2$ 且 $2 \neq 1$ 均成立，但 $1 \neq 1$ 不成立，故不符遞移性。
  • 小結：關係 "≠" 僅具備對稱性。

• (c) "=" on the set of integers ($\mathbb{Z}$)：正確。

  • 自反性：對任意整數 $x$，恆有 $x = x$，具備自反性。
  • 對稱性：對任意整數 $x, y$，若 $x = y$，則必有 $y = x$，具備對稱性。
  • 遞移性：對任意整數 $x, y, z$，若 $x = y$ 且 $y = z$，則必有 $x = z$，具備遞移性。

核心觀念

此題考二階常係數線性遞迴關係。對遞迴式

$$a_n=3a_{n-1}-2a_{n-2}$$

設其特徵方程為

$$r^2-3r+2=0$$

若特徵根為 $r_1,r_2$，且互異，則通解為

$$a_n=C_1r_1^n+C_2r_2^n$$

其中 $C_1,C_2$ 由初始條件決定。

解題方法

將遞迴式改寫為齊次形式：

$$a_n-3a_{n-1}+2a_{n-2}=0$$

因此特徵方程為

$$r^2-3r+2=0$$

因式分解得

$$(r-1)(r-2)=0$$

所以兩個特徵根為

$$r_1=1,\qquad r_2=2$$

通解為

$$a_n=C_1\cdot 1^n+C_2\cdot 2^n$$

即

$$a_n=C_1+C_2 2^n$$

利用初始條件 $a_0=2$：

$$C_1+C_2=2$$

利用初始條件 $a_1=7$：

$$C_1+2C_2=7$$

兩式相減：

$$C_2=5$$

代回 $C_1+C_2=2$：

$$C_1=-3$$

因此一般公式為

$$\boxed{a_n=5\cdot 2^n-3}$$

計算 $a_5$：

$$a_5=5\cdot 2^5-3$$ $$a_5=5\cdot 32-3=160-3=157$$

觀念說明

對於頂點數 $V \ge 3$ 的簡單連通平面圖（Simple, Connected Planar Graph），由於每個面（Face）的邊界至少由 3 條邊構成，即 $2E \ge 3F$。結合歐拉公式（Euler's Formula）$V - E + F = 2$，可推導出平面圖的邊數上限不等式：
$E \le 3V - 6$

---

解題步驟

1. 代入已知條件：
   題目給定頂點數 $V = 8$。

2. 計算邊數上限：
   將 $V = 8$ 代入平面圖邊數上限公式：
   $E_{max} = 3(8) - 6 = 24 - 6 = 18$

核心觀念

1. 二元搜尋樹（Binary Search Tree, BST）之建構規則：
   對於樹中任意節點 $v$，其左子樹中所有節點的值皆小於 $v$ 的值，右子樹中所有節點的值皆大於 $v$ 的值。當依序插入元素時，從根節點（Root）開始比較：若插入值小於當前節點值則往左子樹走，若大於當前節點值則往右子樹走，直到遇到空位置即建立新節點。
2. 樹的高度（Height of Tree）定義：
   在離散數學經典教材（如 Kenneth H. Rosen 所著之《Discrete Mathematics and Its Applications》）中，根節點的階層（Level）定義為 $0$。樹的高度定義為樹中所有節點的最大階層（Maximum Level），亦即從根節點到最深葉子節點（Leaf Node）之最長路徑的邊數（Number of Edges）。

---

解題方法

將給定序列 8, 3, 10, 1, 6, 14, 4, 7, 13 依序插入 BST，推導步驟如下：

1. 插入 $8$：樹為空，作為根節點（Root），位於 Level $0$。
2. 插入 $3$：$3 < 8$，放置於 $8$ 的左子節點，位於 Level $1$。
3. 插入 $10$：$10 > 8$，放置於 $8$ 的右子節點，位於 Level $1$。
4. 插入 $1$：$1 < 8 \to 1 < 3$，放置於 $3$ 的左子節點，位於 Level $2$。
5. 插入 $6$：$6 < 8 \to 6 > 3$，放置於 $3$ 的右子節點，位於 Level $2$。
6. 插入 $14$：$14 > 8 \to 14 > 10$，放置於 $10$ 的右子節點，位於 Level $2$。
7. 插入 $4$：$4 < 8 \to 4 > 3 \to 4 < 6$，放置於 $6$ 的左子節點，位於 Level $3$。
8. 插入 $7$：$7 < 8 \to 7 > 3 \to 7 > 6$，放置於 $6$ 的右子節點，位於 Level $3$。
9. 插入 $13$：$13 > 8 \to 13 > 10 \to 13 < 14$，放置於 $14$ 的左子節點，位於 Level $3$。

最終建構出之二元搜尋樹結構如下：

觀念說明

本題考查相異物與相同物之不盡相異物排列（Permutations with Repetitions）。

計算單字中所有字母構成的全排列數時，若有重複出現的字母，需扣除相同字母內部的重複排列情況。

解題步驟

1. 統計單字字母與數量：
   單字 "BOOKKEEPER" 共有 $10$ 個字母，各字母出現次數如下：

   • B: $1$ 個
   • O: $2$ 個
   • K: $2$ 個
   • E: $3$ 個
   • P: $1$ 個
   • R: $1$ 個

2. 不盡相異物排列公式：
   $n$ 個物件中，有 $n_1, n_2, \dots, n_k$ 個分別相同的物件，其全排列總數為：
   $\frac{n!}{n_1! \cdot n_2! \cdot \cdots \cdot n_k!}$

3. 代入計算：
   全排列數為：
   $\frac{10!}{1! \times 2! \times 2! \times 3! \times 1! \times 1!} = \frac{10!}{2! \cdot 2! \cdot 3!}$

4. 選項比對與簡化：
   將 $\frac{10!}{2! \cdot 2! \cdot 3!}$ 之分子分母同除以 $10$（即利用

【觀念解析】
Dijkstra 演算法用於求解「單源最短路徑問題」（Single-Source Shortest Path Problem）。在權重皆為非負值的權重圖中，維護起始節點至各節點的當前最短距離估計值 $d(v)$，每次選擇尚未確定最短路徑且 $d(v)$ 最小的節點加入確定集合，並鬆弛（Relax）其相鄰節點。

---

【詳細推導步驟】

1. 初始化：

• 起始點 $A$ 的距離 $d(A) = 0$
• 其餘節點距離設為 $\infty$：$d(B) = \infty, d(C) = \infty, d(D) = \infty, d(E) = \infty$
• 已確定最短路徑之集合 $S = \emptyset$

2. 疊代過程：

• 步驟 1：
  • 選擇目前距離最小的節點 $A$（$d(A)=0$），加入 $S = \{A\}$。
  • 鬆弛 $A$ 的鄰居 $B, C$：
    • $d(B) = \min(\infty, 0 + 4) = 4$，前趨節點為 $A$
    • $d(C) = \min(\infty, 0 + 2) = 2$，前趨節點為 $A$