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

核心觀念

1. 反證法（Proof by Contradiction）：
   欲證明條件命題 $P \implies Q$ 成立，我們先假設前提 $P$ 為真且結論 $Q$ 為假（即假設 $\neg Q$ 成立），由此出發經過正確的邏輯推導，導出與已知條件或公理定理相矛盾的結果（例如 $R \land \neg R$）。從而證明反證假設不成立，即原命題 $P \implies Q$ 必定為真。
2. 德摩根定律（De Morgan's Laws）：
   對於包含複合邏輯語句的否定，滿足 $\neg(A \lor B) \equiv \neg A \land \neg B$。因此，結論「$a \nmid b$ 或 $a \nmid (b+1)$」的邏輯否定為「$a \mid b$ 且 $a \mid (b+1)$」。
3. 整除之定義與性質（Divisibility）：
   • 定義：對任意整數 $a, b \in \mathbb{Z}$ 且 $a \neq 0$，若存在一整數 $k \in \mathbb{Z}$ 使得 $b = a \cdot k$，則稱 $a$ 整除 $b$，記作 $a \mid b$。
   • 線性組合性質：若 $a \mid b$ 且 $a \mid c$，則對任意整數 $x, y \in \mathbb{Z}$，均有 $a \mid (x \cdot b + y \cdot c)$。特別地，取 $x = -1, y = 1$ 時，可得 $a \mid ((b+1) - b)$，即 $a \mid 1$。

---

解題方法

本題指定採用**反證法（Proof by Contradiction）**進行證明，完整步驟與推導如下：

步驟一：建立反證假設

假設已知條件成立（$a, b \in \mathbb{Z}$ 且 $a \geq 2$），但原命題之結論為假。
即假設否定敘述 $\neg (a \nmid b \lor a \nmid (b+1))$ 成立。
根據德摩根定律，反證假設等價於：
$a \mid b \quad \text{且} \quad a \mid (b+1)$

步驟二：套用整除定義展開

由 $a \mid b$，根據整除定義，存在整數 $k_1 \in \mathbb{Z}$ 使得：
$b = a \cdot k_1 \quad \text{--- (式 1)}$

同理，由 $a \mid (b+1)$，存在整數 $k_2 \in \mathbb{Z}$ 使得：
$b + 1 = a \cdot k_2 \quad \text{--- (式 2)}$

步驟三：消去變數並導出矛盾

將 (式 2) 減去 (式 1)，可得：
$(b + 1) - b = a \cdot k_2 - a \cdot k_1$
$1 = a \cdot (k_2 - k_1)$

核心觀念

• 遞迴關係式的疊代法 (Method of Iteration / Backward Substitution)：將遞迴關係式中的 $h_k$ 逐次向前展開，表示為 $h_{k-1}, h_{k-2}, \dots, h_0$ 的組合，從中歸納出求和規律（一般為等比級數）。
• 等比級數求和公式 (Sum of Geometric Series)：
  首項為 $a$、公比為 $r \neq 1$ 的前 $n+1$ 項有限等比級數求和公式為：
  $\sum_{i=0}^{n} a \cdot r^i = a \cdot \frac{1 - r^{n+1}}{1 - r}$

---

解題方法

步驟一：使用疊代法（Iteration）展開遞迴式
已知遞迴關係式為：
$h_k = 2^k - h_{k-1} \quad (k \geq 1)$
初始條件為 $h_0 = 1$。

將遞迴式連續向前代入展開：

$$\begin{aligned} h_k &= 2^k - h_{k-1} \\ &= 2^k - (2^{k-1} - h_{k-2}) = 2^k - 2^{k-1} + h_{k-2} \\ &= 2^k - 2^{k-1} + (2^{k-2} - h_{k-3}) = 2^k - 2^{k-1} + 2^{k-2} - h_{k-3} \\ &= 2^k - 2^{k-1} + 2^{k-2} - 2^{k-3} + \dots + (-1)^{k-1} 2^1 + (-1)^k h_0 \end{aligned}$$

步驟二：將初始條件 $h_0 = 1$ 代入並改寫為總和符號
因為 $h_0 = 1 = 2^0$，故可將展開式寫為：
$h_k = \sum_{i=0}^{k} (-1)^{k-i} 2^i$

提出與求和變數 $i$ 無關的因子 $(-1)^k$：
$h_k = (-1)^k \sum_{i=0}^{k} (-1)^{-i} 2^i = (-1)^k \sum_{i=0}^{k} (-2)^i$

步驟三：計算等比級數並最簡化
利用公比 $r = -2$ 的等比級數求和公式：
$\sum_{i=0}^{k} (-2)^i = \frac{1 - (-2)^{k+1}}{1 - (-2)} = \frac{1 - (-2)^{k+1}}{3}$

將級數結果代回 $h_k$ 關係式中：

核心觀念

1. 數字與位數同構映射（Mapping Integers to Fixed-Length Digit Vectors）
   介於 $1$ 到 $99,999$ 的任意整數，皆可唯一表示為補足前導零的 5 位數 $(x_1, x_2, x_3, x_4, x_5)$，其中各個位數滿足 $0 \le x_i \le 9$ ($i = 1, 2, 3, 4, 5$)。
2. 重複組合（Combinations with Repetition）
   求非負整數方程式 $x_1 + x_2 + \cdots + x_n = k$ 的解個數，公式為：
   $H_n^k = C(n+k-1, k) = C(n+k-1, n-1)$
3. 排容原理（Inclusion-Exclusion Principle）
   由於十進位單一位數上限為 $9$（即限制 $x_i \le 9$），當方程式之和 $k \ge 10$ 時，需使用排容原理扣除有位數 $x_i \ge 10$ 的不合法解。

---

解題方法

步驟一：模型建立
將問題轉化為求解線性方程式之非負整數解個數：
求滿足下列條件的五元組 $(x_1, x_2, x_3, x_4, x_5)$ 個數：
$x_1 + x_2 + x_3 + x_4 + x_5 = 10, \quad \text{其中 } 0 \le x_i \le 9, \, \forall i \in \{1, 2, 3, 4, 5\}$

由於位數和為 $10 \neq 0$，解集合不包含全零組 $(0,0,0,0,0)$（對應數字 $0$），因此所有解皆唯一對應到 $1$ 至 $99,999$ 範圍內的一個整數。

步驟二：計算無上限限制下的非負整數解
若暫不考慮位數上限 $x_i \le 9$ 的限制，僅考慮非負整數解 $x_i \ge 0$：
方程式 $x_1 + x_2 + x_3 + x_4 + x_5 = 10$ 的非負整數解個數為重複組合 $H_5^{10}$：
$H_5^{10} = C(5 + 10 - 1, 10) = C(14, 10) = C(14, 4)$
計算組合數：
$C(14, 4) = \frac{14 \times 13 \times 12 \times 11}{4 \times 3 \times 2 \times 1} = 1001$

步驟三：使用排容原理扣除不合法的解
十進位的單一位數上限為 $9$，若存在某位數 $x_i \ge 10$，該解即為無效解。
在 $x_1 + x_2 + x_3 + x_4 + x_5 = 10$ 且 $x_i \ge 0$ 的前提下，若有位數 $x_i \ge 10$，唯一的可能性為該位數 $x_i = 10$，其餘四個位數皆為 $0$。
此種情況共有 5 種：
$(10, 0, 0, 0, 0), (0, 10, 0, 0, 0), (0, 0, 10, 0, 0), (0, 0, 0, 10, 0), (0, 0, 0, 0, 10)$

核心觀念

本題考查常係數線性齊次遞迴關係式（Linear Homogeneous Recurrence Relation with Constant Coefficients）中，特徵方程式根與通解（General Solution）結構的對應關係。

根據離散數學定理：若一個 $k$ 階常係數線性齊次遞迴關係式的特徵方程式具有相異特徵根 $\lambda_1, \lambda_2, \dots, \lambda_t$，且其對應的重數（Multiplicity）分別為 $m_1, m_2, \dots, m_t$（滿足 $\sum_{i=1}^t m_i = k$），則對應特徵根 $\lambda_i$ 的齊次通解成分為：
$(C_{i, 0} + C_{i, 1} n + C_{i, 2} n^2 + \dots + C_{i, m_i - 1} n^{m_i - 1}) \lambda_i^n$
其中 $C_{i, j}$ 為任意實數常數。

將所有特徵根產生的通解成分疊加（相加），即可得到該遞迴關係式的完整通解 $a_n$。

---

解題方法

步驟 1：統計各特徵根及其重數（Multiplicity）
題目給定特徵方程式的根共有 $10$ 個（代表此遞迴關係式為 $10$ 階），整理各相異根與重數如下：

• 特徵根 $\lambda_1 = 1$，出現 $4$ 次 $\implies$ 重數 $m_1 = 4$
• 特徵根 $\lambda_2 = -2$，出現 $3$ 次 $\implies$ 重數 $m_2 = 3$
• 特徵根 $\lambda_3 = 3$，出現 $2$ 次 $\implies$ 重數 $m_3 = 2$
• 特徵根 $\lambda_4 = -4$，出現 $1$ 次 $\implies$ 重數 $m_4 = 1$

步驟 2：寫出各特徵根對應的通解分量

• 針對 $\lambda_1 = 1$（重數 $m_1 = 4$）：
  最高次項為 $n^{4-1} = n^3$，故對應的多項式包含 $4$ 個未定常數：
  $a_n^{(1)} = (C_1 + C_2 n + C_3 n^2 + C_4 n^3) \cdot 1^n = C_1 + C_2 n + C_3 n^2 + C_4 n^3$
• 針對 $\lambda_2 = -2$（重數 $m_2 = 3$）：
  最高次項為 $n^{3-1} = n^2$，對應 $3$ 個未定常數：
  $a_n^{(2)} = (C_5 + C_6 n + C_7 n^2) \cdot (-2)^n$
• 針對 $\lambda_3 = 3$（重數 $m_3 = 2$）：
  最高次項為 $n^{2-1} = n^1$，對應 $2$ 個未定常數：
  $a_n^{(3)} = (C_8 + C_9 n) \cdot 3^n$
• 針對 $\lambda_4 = -4$（重數 $m_4 = 1$）：
  單根對應 $0$ 次多項式（即單一常數）：

核心觀念

本題考查數論（Number Theory）中的中國剩餘定理（Chinese Remainder Theorem, CRT）與同餘方程組（System of Linear Congruences）的求解。

1. 中國剩餘定理（CRT）：
   設 $m_1, m_2, \dots, m_k$ 為兩兩互質（pairwise coprime）的正整數，即當 $i \neq j$ 時，$\gcd(m_i, m_j) = 1$。
   對任意整數 $a_1, a_2, \dots, a_k$，聯立同餘方程組： $$\begin{cases} n \equiv a_1 \pmod{m_1} \\ n \equiv a_2 \pmod{m_2} \\ \quad \vdots \\ n \equiv a_k \pmod{m_k} \end{cases}$$ 在模 $M = \prod_{i=1}^k m_i$ 下有唯一解。
2. 構造解公式：
   • 令 $M = m_1 \times m_2 \times \dots \times m_k$。
   • 對每個 $i = 1, 2, \dots, k$，計算 $M_i = \frac{M}{m_i}$。
   • 求解乘法反元素 $y_i$，滿足 $M_i y_i \equiv 1 \pmod{m_i}$。
   • 方程組的通解為 $n \equiv \sum_{i=1}^k a_i M_i y_i \pmod M$。

---

解題方法

已知同餘方程組為：

$$\begin{cases} n \equiv 1 \pmod 7 \\ n \equiv 3 \pmod 8 \\ n \equiv 2 \pmod 9 \end{cases}$$

步驟一：驗證條件與計算總模數 $M$
模數分別為 $m_1 = 7$, $m_2 = 8$, $m_3 = 9$。
檢查兩兩互質條件：
$\gcd(7, 8) = 1$、$\gcd(7, 9) = 1$、$\gcd(8, 9) = 1$，確定可直接使用中國剩餘定理。
計算總模數 $M$：
$M = 7 \times 8 \times 9 = 504$

步驟二：計算各項的 $M_i$

• $M_1 = \frac{504}{7} = 72$
• $M_2 = \frac{504}{8} = 63$
• $M_3 = \frac{504}{9} = 56$

步驟三：求解模反元素 $y_i$（滿足 $M_i y_i \equiv 1 \pmod{m_i}$）

1. 求解 $y_1$：
   $72 y_1 \equiv 1 \pmod 7$
   因 $72 \equiv 2 \pmod 7$，簡化為 $2 y_1 \equiv 1 \pmod 7$。
   兩邊同乘以 $4$ 得 $8 y_1 \equiv 4 \pmod 7 \implies y_1 \equiv 4 \pmod 7$。

猜想（Conjecture）：
所有大於等於 20 美分的郵資 $n$（即 $n \ge 20, n \in \mathbb{Z}^+$），皆可僅使用 5 美分與 6 美分的郵票組合而成。

---

證明（Proof）：使用數學歸納法（Mathematical Induction）

1. 基礎步驟（Base Cases）：

證明當 $n = 20, 21, 22, 23, 24$ 時命題成立：

• $20 = 5 \times 4 + 6 \times 0$
• $21 = 5 \times 3 + 6 \times 1$
• $22 = 5 \times 2 + 6 \times 2$
• $23 = 5 \times 1 + 6 \times 3$
• $24 = 5 \times 0 + 6 \times 4$

核心觀念

本題考查量詞否定、德摩根定律，以及蘊涵命題的否定：

$$\neg(\forall x\, P(x))\equiv \exists x\,\neg P(x)$$ $$\neg(\exists x\, P(x))\equiv \forall x\,\neg P(x)$$ $$\neg(A\land B)\equiv \neg A\lor\neg B$$ $$\neg(A\lor B)\equiv \neg A\land\neg B$$

此外，蘊涵命題的否定為：

$$\neg(A\rightarrow B)\equiv A\land\neg B$$

解題時由最外層開始逐步否定，並將每個否定符號推入，直到否定符號只出現在謂詞前。

---

解題方法與推導

(a) $\forall x \exists y \forall z\, T(x,y,z)$

原命題否定為：

$$\neg\left(\forall x\exists y\forall z\,T(x,y,z)\right)$$

依序否定量詞：

$$\equiv \exists x\neg\left(\exists y\forall z\,T(x,y,z)\right)$$ $$\equiv \exists x\forall y\neg\left(\forall z\,T(x,y,z)\right)$$ $$\equiv \exists x\forall y\exists z\,\neg T(x,y,z)$$

因此：

$$\boxed{\exists x\forall y\exists z\,\neg T(x,y,z)}$$

語意上表示：存在某個 $x$，使得對所有 $y$，都存在某個 $z$，讓 $T(x,y,z)$ 不成立。

---

(b) $\forall x \exists y\,P(x,y)\lor\forall x \exists y\,Q(x,y)$

為避免兩個分句中的束縛變數混淆，先改寫為：

$$\left(\forall x\exists y\,P(x,y)\right) \lor \left(\forall u\exists v\,Q(u,v)\right)$$

原命題否定為：

$$\neg\left[ \left(\forall x\exists y\,P(x,y)\right) \lor \left(\forall u\exists v\,Q(u,v)\right) \right]$$

使用德摩根定律：

$$\equiv \neg\left(\forall x\exists y\,P(x,y)\right) \land \neg\left(\forall u\exists v\,Q(u,v)\right)$$

分別否定兩個量詞結構：

$$\equiv \left(\exists x\forall y\,\neg P(x,y)\right) \land \left(\exists u\forall v\,\neg Q(u,v)\right)$$

因此：

$$\boxed{ \left(\exists x\forall y\,\neg P(x,y)\right) \land \left(\exists u\forall v\,\neg Q(u,v)\right) }$$

將變數名稱統一後，也可寫成：

$$\boxed{ \left(\exists x\forall y\,\neg P(x,y)\right) \land \left(\exists x\forall y\,\neg Q(x,y)\right) }$$

兩個分句中的 $x,y$ 各自受其所在量詞束縛，因此不會造成變數衝突。

---

(c) $\forall x \exists y\left(P(x,y)\land\exists z\,R(x,y,z)\right)$

原命題否定為：

$$\neg\left[ \forall x\exists y \left(P(x,y)\land\exists z\,R(x,y,z)\right) \right]$$

先否定最外層量詞：