108 年 國立臺灣大學電機工程研究所丙組《離散數學（B）》

注意：題目中 $C(n, k)$ 即為組合數 $\binom{n}{k}$，亦即求：
$S = \sum_{k=0}^{n} \binom{n}{k}^2 (k^3 - 1) = \sum_{k=0}^{n} k^3 \binom{n}{k}^2 - \sum_{k=0}^{n} \binom{n}{k}^2$

利用 Vandermonde's Identity 可得：
$\sum_{k=0}^{n} \binom{n}{k}^2 = \binom{2n}{n}$

針對第一項 $\sum_{k=0}^{n} k^3 \binom{n}{k}^2$，利用恆等式 $k \binom{n}{k} = n \binom{n-1}{k-1}$ 展開 $k^3 = k(k-1)(k-2) + 3k(k-1) + k$：

1. 一階項：
   $\sum_{k=0}^{n} k \binom{n}{k}^2 = n \binom{2n-1}{n-1} = \frac{n}{2} \binom{2n}{n}$

2. 二階項：

將原遞迴關係式兩邊同乘以 $n$：
$(n-1)a_n = 3a_{n-1} + n, \quad \text{for } n \ge 2$

對 $n \ge 2$，兩邊同除以 $3^n$：
$\frac{(n-1)a_n}{3^n} = \frac{a_{n-1}}{3^{n-1}} + \frac{n}{3^n}$

令變數變換 $b_n = \frac{(n-1)a_n}{3^n}$，則對 $n \ge 2$：
$b_n = b_{n-1} + \frac{n}{3^n}$

計算初始條件 $b_1$：
$b_1 = \frac{(1-1)a_1}{3^1} = 0$

經由累加法（Telescoping sum）：
$b_n = b_1 + \sum_{k=2}^{n} \frac{k}{3^k} = \sum_{k=2}^{n} \frac{k}{3^k}$

考慮無窮級數/有限和公式：令 $S_n = \sum_{k=1}^{n} k x^k$，當 $x = \frac{1}{3}$ 時，

題目解析與推導

步驟一：簡化同餘條件 $\pmod{25}$

已知 $n^5 + (n + 1)^5 \equiv 0 \pmod{25}$。
將 $(n+1)^5$ 依二項式定理展開：
$(n + 1)^5 = n^5 + 5n^4 + 10n^3 + 10n^2 + 5n + 1$
將其代入原式：
$n^5 + (n + 1)^5 = 2n^5 + 5n^4 + 10n^3 + 10n^2 + 5n + 1 \equiv 0 \pmod{25}$

考慮 $\pmod 5$ 的情況：
因為 $25 \mid (n^5 + (n+1)^5)$，故必有 $5 \mid (n^5 + (n+1)^5)$。
由費馬小定理，對任意整數 $k$，皆有 $k^5 \equiv k \pmod 5$。因此：
$n^5 + (n + 1)^5 \equiv n + (n + 1) = 2n + 1 \equiv 0 \pmod 5$
解得：
$2n \equiv -1 \equiv 4 \pmod 5 \implies n \equiv 2 \pmod 5$

步驟二：確定 $n \pmod{25}$ 的可能性

設 $n = 5k + 2$（其中 $k \in \mathbb{Z}$），將其代入原式 $\pmod{25}$ 進行檢驗。
由於 $n \equiv 2 \pmod 5$，我們計算 $n^5 \pmod{25}$：
由二項式定理 $n^5 = (5k + 2)^5 = 2^5 + 5 \cdot 2^4 \cdot (5k) + \mathcal{O}(25) \equiv 32 + 400k \equiv 7 \pmod{25}$。
同理，$(n+1)^5 = (5k + 3)^5 = 3^5 + 5 \cdot 3^4 \cdot (5k) + \mathcal{O}(25) \equiv 243 + 2025k \equiv 18 \pmod{25}$。

核心觀念

1. 數理邏輯（Mathematical Logic）：

   • 一階邏輯量詞（Quantifiers）：量詞作用域展開與恆真式（Tautology）推導。
   • 功能完備集（Functionally Complete Set）：命題邏輯運算子的表達能力，若一個運算子集合能表達出已知的功能完備集（如 $\{\neg, \lor\}$ 或 $\{\neg, \land\}$），則該集合亦為功能完備集。
   • 命題邏輯等價與鴿籠原理（Pigeonhole Principle）：$n$ 個命題變數共有 $2^{(2^n)}$ 種不相等的真值表輸出組合。

2. 集合論與基數（Sets & Cardinality）：

   • 單射（Injection / One-to-One Function）：包含映射（Inclusion Map）的定義與性質。
   • 不可數集基數比較（Uncountable Sets）：基數的大小關係與康托爾定理（Cantor's Theorem，$|\mathcal{P}(S)| > |S|$）。

3. 關係與偏序（Relations & Partial Orders）：

   • 對稱關係（Symmetric Relation）：合成運算（Composition）與逆關係/轉置關係的反轉律定理 $(R \circ S)^{-1} = S^{-1} \circ R^{-1}$。
   • 有限偏序集（Finite Poset）與極大元（Maximal Element）：偏序集極值元存在性定理與空集合邊界條件。

---

解題方法

本題為是非題（True / False），評分機制包含倒扣（答對 $+5$ 分，答錯 $-6$ 分），答題時需極度嚴謹：

1. 邏輯式：利用邏輯蘊涵等價律 $A \implies B \equiv \neg A \lor B$ 與 De Morgan 定律進行式子簡化，並依變數真假值進行分情況討論（Proof by Cases）。
2. 功能完備集：構造出 $\lor$ 或 $\land$ 的等價表示式。
3. 語句等價性：算出單一變數 $p$ 能夠構成的相異真值表總數，再套用鴿籠原理。
4. 集合映射與基數：使用子集的包含映射構造單射；使用冪集（Power Set）構造不可數集的基數反例。
5. 關係運算：使用關係矩陣轉置或逆關係代數式驗證對稱性 $(R^3)^{-1} = R^3$。
6. 偏序集極值：檢驗極大元定義並檢查論域是否包含空集合（$\emptyset$）等邊界條件。

---

選項分析

(a) $\exists x ( \forall y (P(y) \wedge Q(y)) \implies P(x) )$

• 分析：正確（True）。

• 推導：
  在標準一階邏輯中，討論論域（Domain）$D$ 預設為非空集合（Non-empty set）。
  令前件命題 $A \equiv \forall y (P(y) \wedge Q(y))$。
  原式可表示為 $\exists x ( A \implies P(x) )$。
  利用邏輯蘊涵等價律 $A \implies B \equiv \neg A \vee B$，原式等價於：
  $\exists x ( \neg (\forall y (P(y) \wedge Q(y))) \vee P(x) )$
  因為前件 $\neg (\forall y (P(y) \wedge Q(y)))$ 不含有變數 $x$，可將存在量詞 $\exists x$ 作用於後件，得：
  $\neg (\forall y (P(y) \wedge Q(y))) \vee (\exists x P(x))$
  利用 De Morgan 定律展開左式：
  $(\exists y (\neg P(y) \vee \neg Q(y))) \vee (\exists x P(x))$
  進行分情況討論：

  • 情況一：若 $\exists x P(x)$ 為真，則右式為真，整體命題必為真。
  • 情況二：若 $\exists x P(x)$ 為假，代表對論域中任意元素 $x$，$P(x)$ 皆為假。因論域非空，任取一元素 $y \in D$，其 $P(y)$ 必為假，故 $\neg P(y)$ 為真，使得左式 $\exists y (\neg P(y) \vee \neg Q(y))$ 為真，整體命題亦為真。

  綜合上述，無論命題函數 $P, Q$ 如何定義，該式在任何非空論域下皆為恆真式（Tautology）。

(b) In propositional logic, $\{ \neg, \implies \}$ is a functionally complete set.

• 分析：正確（True）。
• 推導：
  已知經典集合 $\{\neg, \lor\}$ 為功能完備集。若能利用 $\{\neg, \implies\}$ 表示出邏輯或（OR, $\lor$），則 $\{\neg, \implies\}$ 亦為功能完備集。
  由蘊涵定義 $p \implies q \equiv \neg p \lor q$，若將 $p$ 替換為 $\neg p$，可得：
  $(\neg p) \implies q \equiv \neg(\neg p) \lor q \equiv p \lor q$
  因此 $p \lor q \equiv (\neg p) \implies q$。同理，邏輯與（AND, $\land$）可表示為 $p \land q \equiv \neg(p \implies \neg q)$。
  故僅需反相器（NOT）與蘊涵門（IMPLY），即可組合出所有布林函數，證得 $\{\neg, \implies\}$ 為功能完備集。

(c) Given five propositional logic statements using a single variable $p$, there exist two of them which are equivalent to each other.

• 分析：正確（True）。
• 推導：
  由單一命題變數 $p$ 構成的命題，其真值表只有 $2^1 = 2$ 列（即 $p=T$ 與 $p=F$）。
  一個真值表輸出的可能組合數為：
  $2^{(2^1)} = 2^2 = 4 \text{ 種}$
  這 4 種邏輯不等價的命題類別分別對應：矛盾式（Contradiction, $F$）、變數本身（$p$）、否定式（$\neg p$）與恆真式（Tautology, $T$）。

核心觀念

1. 平面圖歐拉公式（Euler's Formula for Planar Graphs）：
   對於任何包含 $k$ 個連通分量（connected components）的簡單平面圖 $G = (V, E)$，設其平面嵌入的區域（面）集合為 $F$，則恆滿足歐拉公式不等式：
   $|V| - |E| + |F| = 1 + k \ge 2$
   （若 $G$ 為連通圖，則 $k = 1$，等式成立為 $|V| - |E| + |F| = 2$）。

2. 圖的圍長（Girth）與面度（Face Degree）的關係：
   圖 $G$ 的圍長 $g(G)$ 為圖中最短簡單環（simple cycle）的長度。若簡單平面圖中包含環，且圍長 $g(G) \ge 5$，則該圖嵌入平面後，每個面 $f \in F$ 的邊界至少由 5 條邊組成，即面的度數 $\text{deg}(f) \ge 5$。

3. 面的握手定理（Handshaking Lemma for Faces）：
   在平面圖中，所有面的度數總和等於總邊數的兩倍：
   $\sum_{f \in F} \text{deg}(f) = 2|E|$

---

解題方法

結論：是的，該敘述永遠成立（It is always true）。

正式證明：

分兩種情況討論圖 $G$ 是否包含簡單環：

情況一：圖 $G$ 包含至少一個簡單環（Cycle）

1. 根據題意，圖 $G$ 中所有簡單環的長度皆至少為 $5$，即圍長 $g(G) \ge 5$。
2. 由於每一個面 $f \in F$ 的邊界均由簡單環或幾何邊界所構成，故每個面的度數滿足 $\text{deg}(f) \ge 5$。
3. 由面的握手定理可得：
   $2|E| = \sum_{f \in F} \text{deg}(f) \ge 5|F| \implies |F| \le \frac{2}{5}|E|$
4. 將 $|F| \le \frac{2}{5}|E|$ 代入平面圖歐拉公式不等式 $|V| - |E| + |F| \ge 2$：
   $|V| - |E| + \frac{2}{5}|E| \ge |V| - |E| + |F| \ge 2$
   $|V| - \frac{3}{5}|E| \ge 2$
5. 兩邊同乘以 $5$ 並移項整理：
   $5|V| - 3|E| \ge 10 \implies 3|E| \le 5|V| - 10$

情況二：圖 $G$ 不包含任何簡單環（無環圖／森林 Forest）

1. 若 $G$ 無環，則 $G$ 為森林。

考點：極小非平面圖（Minimal Non-planar Graph / Edge-critical Non-planar Graph）與 Kuratowski 定理

詳解

根據題意，$G$ 為擁有 15 個頂點的連通無向圖（$|V| = 15$）。$G$ 本身非平面圖（Non-planar），但移除任意邊後皆變成平面圖，故 $G$ 為極小非平面圖（Minimal non-planar graph）。

依據 Kuratowski 定理與極小非平面圖的結構特性，最簡的極小非平面圖僅由以下兩種基本結構之一加上孤立頂點或細分結構組成：

1. 完全圖 $K_5$（邊數為 10）
2. 完全二分圖 $K_{3,3}$（邊數為 9）

由於 $G$ 為連通圖且 $|V| = 15$，可分為以下情況討論：

情況一：$G$ 由基本極小非平面核心與剩餘頂點構成樹狀/路徑連接

• 若核心為 $K_5$：頂點數佔 5 個，剩餘 $15 - 5 = 10$ 個頂點必須與 $K_5$ 連通且不形成額外的環（否則移除該邊後仍包含 $K_5$，失去極小性）。