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

核心觀念

本題考驗數理邏輯中的**功能完備集（Functionally Complete Set / Universal Operator）**概念，以及基本邏輯等價律的靈活運用。

關鍵定義與定律如下：

1. NOR 運算子定義：
   $P \text{ nor } Q \equiv \neg (P \lor Q)$
2. 冪等律（Idempotent Law）：
   $P \lor P \equiv P$
3. 德摩根定律（De Morgan's Laws）：
   $P \land Q \equiv \neg (\neg P \lor \neg Q)$
4. 雙重否定律（Double Negation Law）：
   $\neg (\neg P) \equiv P$

---

解題方法

目標為僅使用 nor、變數 $P$、$Q$ 與括號 $(, )$ 來表示邏輯與語句 $P \land Q$。

推導步驟如下：

第一步：將單一變數的反相（NOT 閘）用 NOR 運算子表示
利用冪等律 $P \lor P \equiv P$，對變數 $P$ 進行 self-NOR 運算：
$P \text{ nor } P \equiv \neg (P \lor P) \equiv \neg P$
同理可得：
$Q \text{ nor } Q \equiv \neg Q$

第二步：利用德摩根定律轉換邏輯「與」（AND）運算
將 $P \land Q$ 透過德摩根定律轉換為以「非」（NOT）與「或」（OR）構成的形式：
$P \land Q \equiv \neg (\neg P \lor \neg Q)$

第三步：將外層結構轉換為 NOR 形式
觀察上式外層的 $\neg (\dots \lor \dots)$ 結構，此即為 NOR 運算子的定義：
$\neg (\neg P \lor \neg Q) \equiv (\neg P) \text{ nor } (\neg Q)$

第四步：代入第一步的表達式
將 $\neg P \equiv (P \text{ nor } P)$ 與 $\neg Q \equiv (Q \text{ nor } Q)$ 代入：
$P \land Q \equiv (P \text{ nor } P) \text{ nor } (Q \text{ nor } Q)$

---

選項分析

本題為非選擇題（計算與證明題）。以下針對解答式子中各子結構與整體運算子進行邏輯功能拆解分析：

• 子結構 1：$(P \text{ nor } P)$
  • 功能：實現邏輯反相器（NOT $P$）。
  • 分析：由定義 $(P \text{ nor } P) = \neg (P \lor P) = \neg P$。此項成功將輸入變數 $P$ 反相。

核心觀念

本題考查離散數學中**強數學歸納法（Strong Mathematical Induction）與同餘（Modular Arithmetic）**的綜合應用。

1. 強數學歸納法：當遞迴關係式 $a_n$ 依賴於前 $k$ 項（本題依賴前 $4$ 項：$a_{n-1}, a_{n-2}, a_{n-3}, a_{n-4}$）時，基礎步驟（Base Cases）必須連續驗證 $k$ 個初始值。
2. 同餘加法性質：若 $x \equiv a \pmod m$ 且 $y \equiv b \pmod m$，則 $x + y \equiv a + b \pmod m$。

---

解題方法

採用強數學歸納法進行證明：

第一步：基礎步驟（Base Cases）
當 $n = 0, 1, 2, 3$ 時，由題目定義可知：

• $a_0 = 1 \equiv 1 \pmod 3$
• $a_1 = 1 \equiv 1 \pmod 3$
• $a_2 = 1 \equiv 1 \pmod 3$
• $a_3 = 1 \equiv 1 \pmod 3$

故當 $0 \le n \le 3$ 時，$a_n \equiv 1 \pmod 3$ 均成立。

第二步：歸納假設（Inductive Hypothesis）
假設對任意整數 $k \ge 3$，當 $0 \le m \le k$ 時，$a_m \equiv 1 \pmod 3$ 恆成立。
（特別地，包含 $a_k \equiv 1 \pmod 3$、$a_{k-1} \equiv 1 \pmod 3$、$a_{k-2} \equiv 1 \pmod 3$、$a_{k-3} \equiv 1 \pmod 3$）

第三步：歸納步驟（Inductive Step）
考慮 $n = k + 1$ 的情況（此時 $k + 1 \ge 4$）：
根據遞迴關係式定義：
$a_{k+1} = a_k + a_{k-1} + a_{k-2} + a_{k-3}$

核心觀念

1. 外平面圖（Outerplanar Graph）定義：無向圖 $G = (V, E)$ 若能將其所有頂點放置於同一個圓周上，且在圓內部繪製直條邊時任意兩邊皆不相交，則稱為外平面圖。外平面圖的任意子圖（Subgraph）必然亦為外平面圖。
2. 圖著色與著色數（Graph Coloring & Chromatic Number）：為圖 $G$ 的每個頂點塗上顏色，使得任意一條邊所連接的兩個相鄰頂點顏色皆不相同。若只需用 $k$ 種（或更少）顏色即可完成合法的頂點著色，則稱該圖為 $k$-可著色（$k$-colorable）。
3. 頂點最小度數性質（Minimum Degree Property）：題幹給定可直接使用之事實：任意外平面圖必然存在度數最多為 2 的頂點（即最小度數 $\delta(G) \le 2$）。
4. 數學歸納法（Mathematical Induction）：對圖的頂點數 $n = |V|$ 進行結構歸納法，為圖論中證明著色數上限的標準方法。

---

解題方法

採用**對頂點數量 $n = |V|$ 進行數學歸納法（Mathematical Induction）**證明：

基底步驟（Base Step）：

當頂點數 $n \le 3$ 時：

• 若 $n = 1$，僅需 1 種顏色。
• 若 $n = 2$，最多僅需 2 種顏色。
• 若 $n = 3$，完全圖 $K_3$ 需 3 種顏色；若非完全圖則需少於 3 種顏色。
  因此，當 $n \le 3$ 時，任意外平面圖皆顯然為 3-可著色（3-colorable）。基底步驟成立。

歸納假設（Inductive Hypothesis）：

假設對於所有頂點數為 $k$（其中 $k \ge 1$）的任意外平面圖，皆為 3-可著色。

歸納步驟（Inductive Step）：

考慮任意一個頂點數量為 $n = k + 1$ 的外平面圖 $G = (V, E)$：

1. 尋求低度數頂點：根據題幹給定之事實，外平面圖 $G$ 中必存在至少一個頂點 $v \in V$，其度數滿足 $\deg(v) \le 2$。
2. 建構子圖：將頂點 $v$ 及其相連的邊自 $G$ 中移除，得到子圖 $G' = G \setminus \{v\}$。
3. 驗證子圖性質：由於移除頂點與邊不會破壞剩餘頂點於圓周上的佈局與邊不相交性，故 $G'$ 必然仍為外平面圖。
4. 套用歸納假設：子圖 $G'$ 的頂點數為 $k$。由歸納假設可知，$G'$ 存在合法的 3-著色方案。設所使用的顏色集合為 $C = \{1, 2, 3\}$。
5. 塗色回填：將頂點 $v$ 重新加回 $G'$ 中：

核心觀念

1. 集合勢（Cardinality）與雙重變數計數：求滿足給定不等式的格點（Integer Lattice Points）數量。
2. 總和符號與多項式求和公式：
   • 常數求和：$\sum_{i=0}^{m} c = c(m + 1)$
   • 自然數平方和公式：$\sum_{i=1}^{m} i^2 = \frac{m(m+1)(2m+1)}{6}$

---

解題方法

Step 1：確定變數 $i$ 的取值範圍

題目已知 $n = m^2$（$m \in \mathbb{Z}^+$），要求非負整數對 $(i, j)$ 滿足：
$i \ge 0, \quad j \ge 0, \quad i^2 + j \le n$

將 $j \ge 0$ 代入不等式 $i^2 + j \le n$，可得 $i^2 \le n = m^2$。
由於 $i$ 為非負整數，故 $i$ 的可能取值範圍為：
$0 \le i \le m \quad (i \in \{0, 1, 2, \dots, m\})$

Step 2：計算固定 $i$ 時，$j$ 的合法選擇個數

對於任意固定的 $i$（$0 \le i \le m$），整數 $j$ 必須滿足：
$0 \le j \le n - i^2 = m^2 - i^2$

因此，合法的非負整數 $j$ 個數為：
$(m^2 - i^2) - 0 + 1 = m^2 - i^2 + 1$

Step 3：建立求和式並計算 $h(n) = |S_n|$

將所有可能的 $i$ 值（從 $i = 0$ 到 $i = m$）之 $j$ 個數累加：
$h(n) = \sum_{i=0}^{m} (m^2 - i^2 + 1)$

拆解求和式：
$h(n) = \sum_{i=0}^{m} (m^2 + 1) - \sum_{i=0}^{m} i^2$

計算各項總和：

• 第一項：常數 $(m^2 + 1)$ 累加 $m + 1$ 次（因 $i$ 從 $0$ 到 $m$ 共有 $m+1$ 項）：
  $\sum_{i=0}^{m} (m^2 + 1) = (m + 1)(m^2 + 1)$
• 第二項：平方和（$i = 0$ 時 $i^2 = 0$，故可自 $i=1$ 開始求和）：
  $\sum_{i=0}^{m} i^2 = \sum_{i=1}^{m} i^2 = \frac{m(m+1)(2m+1)}{6}$

Step 4：代入並化簡結果

$h(n) = (m + 1)(m^2 + 1) - \frac{m(m+1)(2m+1)}{6}$

核心觀念

本題為研究所離散數學中「組合數學與級數求和（Combinatorics and Series Summation）」的經典考題，包含兩大主題：

1. (a) 題：正負交錯線性級數求和與數學歸納法 (Alternating Linear Sum & Mathematical Induction)

   • 天花板函數 (Ceiling Function)：對任意實數 $x$，$\lceil x \rceil$ 表示大於等於 $x$ 的最小整數。
   • 數學歸納法 (Mathematical Induction)：用於證明對所有非負整數成立的命題，需經過「基礎步驟（Base Step）」與「歸納步驟（Inductive Step）」。
   • 整數分割與偶奇討論 (Parity Split)：利用偶數 $n = 2m$ 與奇數 $n = 2m+1$ 的規律進行分項對消與求和。

2. (b) 題：二項式定理與偶次方萃取技巧 (Binomial Theorem & Multi-section / Filtering)

   • 二項式定理 (Binomial Theorem)：
     $(1+x)^n = \sum_{j=0}^n \binom{n}{j} x^j$
   • 偶數項組合數求和：利用 $(1+x)^n$ 與 $(1-x)^n$ 正負項相減或相加對消的經典技巧，過濾出僅含偶數項 $j = 2k$ 的組合級數：
     $\sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n}{2k} x^{2k} = \frac{(1+x)^n + (1-x)^n}{2}$

---

解題方法

(a) 題推導與證明

【方法一】數學歸納法（最嚴密的標準證明）

要證明對所有非負整數 $n \ge 0$，命題 $P(n): f(n) = (-1)^n \lceil \frac{n}{2} \rceil$ 皆成立。

1. 基礎步驟 (Base Step)：
   當 $n = 0$ 時：
   $f(0) = \sum_{k=0}^0 (-1)^k k = (-1)^0 \cdot 0 = 0$
   右式為 $(-1)^0 \lceil \frac{0}{2} \rceil = 1 \cdot 0 = 0$。
   兩式相等，$P(0)$ 成立。

2. 歸納假設 (Inductive Hypothesis)：
   假設當 $n = k$ （$k \ge 0$）時，命題 $P(k)$ 成立，即：
   $f(k) = \sum_{j=0}^k (-1)^j j = (-1)^k \left\lceil \frac{k}{2} \right\rceil$

3. 歸納步驟 (Inductive Step)：
   考慮 $n = k + 1$ 的情況：
   $f(k+1) = \sum_{j=0}^{k+1} (-1)^j j = f(k) + (-1)^{k+1}(k+1)$
   代入歸納假設：
   $f(k+1) = (-1)^k \left\lceil \frac{k}{2} \right\rceil + (-1)^{k+1}(k+1)$
   提出共通項 $(-1)^{k+1}$：
   $f(k+1) = (-1)^{k+1} \left[ (k+1) - \left\lceil \frac{k}{2} \right\rceil \right]$

   根據天花板函數與地板函數之恆等式，對任意整數 $k$：
   $(k+1) - \left\lceil \frac{k}{2} \right\rceil = \left\lfloor \frac{k}{2} \right\rfloor + 1 = \left\lceil \frac{k+1}{2} \right\rceil$
   （註：若 $k=2m$ 為偶數，$(2m+1) - m = m+1 = \lceil \frac{2m+1}{2} \rceil$；若 $k=2m+1$ 為奇數，$(2m+2) - (m+1) = m+1 = \lceil \frac{2m+2}{2} \rceil$）

   將此恆等式代回，可得：
   $f(k+1) = (-1)^{k+1} \left\lceil \frac{k+1}{2} \right\rceil$
   即 $P(k+1)$ 亦成立。

由數學歸納法得證，對所有非負整數 $n \ge 0$，$f(n) = (-1)^n \lceil \frac{n}{2} \rceil$ 均成立。

---

【方法二】奇偶分類討論法（兩兩分組對消）

直接計算級數 $\sum_{k=0}^n (-1)^k k = 0 - 1 + 2 - 3 + 4 - 5 + \dots + (-1)^n n$：

• 情況一：$n$ 為偶數 ($n = 2m, m \ge 0$)
  $f(2m) = (0) + (-1 + 2) + (-3 + 4) + \dots + (-(2m-1) + 2m)$
  將項兩兩配對，共有 $m$ 個小括弧，每個括弧值皆為 $1$：
  $f(2m) = \underbrace{1 + 1 + \dots + 1}_{m \text{ 個}} = m$
  而 $(-1)^{2m} \lceil \frac{2m}{2} \rceil = 1 \cdot m = m$，公式吻合。

核心觀念

本題屬於離散數學與機率論中「機率集中不等式」（Concentration Inequalities）的經典題型，核心考點包含：

1. 獨立隨機變數和的期望值線性（Linearity of Expectation）：
   $T = \sum_{i=1}^{100} T_i$ 的期望值為 $\mu = E[T] = \sum_{i=1}^{100} E[T_i] = 100 \times 0.3 = 30$。
2. 柴諾夫界限（Chernoff Bound）與動差生成函數（Moment Generating Function, MGF）：
   當隨機變數 $T_i$ 相互獨立且限制在區間 $[0, 1]$ 時，利用馬爾可夫不等式（Markov's Inequality）作用於動差生成函數 $e^{tT}$ （其中 $t > 0$），可以推導出指數級尾端機率上界（Exponential Tail Bound）。
3. 凸函數性質與指數不等式：
   對任意 $x \in [0, 1]$ 及 $t > 0$，利用 $e^{tx}$ 的凸性（Convexity）可得 $e^{tx} \le 1 + x(e^t - 1)$，再配合 $1 + y \le e^y$ 建立 MGF 之上界。

---

解題方法

步驟一：計算總期望值 $\mu$
由於 $T_1, T_2, \dots, T_{100}$ 相互獨立，且對於所有 $i$ 皆有 $E[T_i] = 0.3$，根據期望值的線性性質：
$\mu = E[T] = E\left[ \sum_{i=1}^{100} T_i \right] = \sum_{i=1}^{100} E[T_i] = 100 \times 0.3 = 30$

步驟二：利用馬爾可夫不等式建立 Chernoff Bound 架構
對任意參數 $t > 0$，由於事件 $T > 30e$ 等價於 $e^{tT} > e^{30et}$，根據馬爾可夫不等式（Markov's Inequality）：
$\Pr\{T > 30e\} = \Pr\{e^{tT} > e^{30et}\} \le \frac{E[e^{tT}]}{e^{30et}}$

步驟三：推導動差生成函數 $E[e^{tT}]$ 的上界
由 $T_i$ 之相互獨立性，動差生成函數可拆解為各變數 MGF 之乘積：
$E[e^{tT}] = E\left[ e^{t \sum_{i=1}^{100} T_i} \right] = E\left[ \prod_{i=1}^{100} e^{tT_i} \right] = \prod_{i=1}^{100} E[e^{tT_i}]$

因為已知 $0 \le T_i \le 1$，根據 $f(x) = e^{tx}$ 在 $x \in [0, 1]$ 上的凸性，區間內任意點的值不大於端點割線值：
$e^{tT_i} \le (1 - T_i) e^{t \cdot 0} + T_i e^{t \cdot 1} = 1 + T_i (e^t - 1)$

對兩邊取期望值：
$E[e^{tT_i}] \le 1 + E[T_i](e^t - 1)$

利用實數基本不等式 $1 + y \le e^y$（令 $y = E[T_i](e^t - 1)$）：
$E[e^{tT_i}] \le e^{E[T_i](e^t - 1)}$

將各變數的上界相乘：
$E[e^{tT}] \le \prod_{i=1}^{100} e^{E[T_i](e^t - 1)} = e^{\sum_{i=1}^{100} E[T_i](e^t - 1)} = e^{\mu (e^t - 1)} = e^{30(e^t - 1)}$

步驟四：代回上界並求解最佳參數 $t$
將 $E[e^{tT}]$ 的上界代回機率不等式：
$\Pr\{T > 30e\} \le \frac{e^{30(e^t - 1)}}{e^{30et}} = e^{30(e^t - 1 - et)}$

為了得到最緊密（最佳）的上界，需尋找使指數 $g(t) = e^t - 1 - et$ 達到極小值的 $t > 0$。對 $t$ 微分並令其為零：
$g'(t) = e^t - e = 0 \implies e^t = e \implies t = 1$

將 $t = 1 > 0$ 代回指數式：
$g(1) = e^1 - 1 - e(1) = -1$