109 年 國立高雄大學資訊工程學系碩士班《離散數學》

核心觀念

本題屬於排列組合與計數原理（Combinatorics & Counting Principles）的經典題型，主要涵蓋以下核心定義與公式：

1. 乘法原理與排列（Permutations）：位數間彼此獨立且順序相關時，若無重複限制使用 $n^k$；若元素互異且考慮順序，使用排列數 $P(n, k) = \frac{n!}{(n-k)!}$。
2. 組合（Combinations）：選取元素不考慮順序，或順序已被題目強制嚴格指定時，使用組合數 $C(n, k) = \binom{n}{k} = \frac{n!}{k!(n-k)!}$。
3. 重複組合（Combinations with Repetitions）：允許重複選擇且順序已被指定（或求解非負整數解個數）時，使用重複組合公式 $H(n, k) = C(n + k - 1, k)$。
4. 不定方程式非負整數解與排容原理（Inclusion-Exclusion Principle）：對於方程式 $x_1 + x_2 + \dots + x_n = S$ 的非負整數解，若變數設有上限限制（如數字 $0 \sim 9$），當目標總和可能使單一變數突破上限（$\ge 10$）時，需利用排容原理扣除違規解。

---

解題方法

本題密碼長度為 6 位數，設密碼序列為 $(x_1, x_2, x_3, x_4, x_5, x_6)$，每一位數字取自集合 $S = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$（共 10 種可能）。密碼允許首位為 0（例如範例中的 014679）。

各小題的分析切入點如下：

• (a) 自由排列：6 個位置各自獨立，每位置有 10 種可能，依乘法原理計算。
• (b) 互異數字排列：從 10 個數字中取出 6 個不重複數字進行直線排列，採用 $P(10, 6)$。
• (c) 嚴格遞增：條件為 $0 \le x_1 < x_2 < x_3 < x_4 < x_5 < x_6 \le 9$。從 10 個數字中任意選出 6 個相異數字後，由小到大的排列方式恰好只有 1 種，故等同於組合數 $C(10, 6)$。
• (d) 非嚴格遞增：條件為 $0 \le x_1 \le x_2 \le x_3 \le x_4 \le x_5 \le x_6 \le 9$。允許數字重複出現，從 10 種數字中選取 6 個數字的多重集合後，由小到大排序的方式恰好只有 1 種，故轉化為重複組合 $H(10, 6)$。
• (e) 數字和為 9：求 $x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 9$ 的非負整數解數量。由於總和為 9，任一數字上限必然自然滿足 $x_i \le 9$，直接套用重複組合 $H(6, 9)$。
• (f) 數字和為 20：求 $x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 20$ 的非負整數解數量，限制條件為 $0 \le x_i \le 9$。因總和達 20，需先求無上限限制的解數 $H(6, 20)$，再以排容原理扣除有變數 $\ge 10$ 的非合法解。

---

選項分析

(a) 6 個數字（0 到 9）

• 推導與計算：
  密碼長度為 6，每一位皆可獨立從 0 到 9 選取（允許重複且考慮順序）。
  $10 \times 10 \times 10 \times 10 \times 10 \times 10 = 10^6 = 1,000,000$
• 結果：$1,000,000$

(b) 6 個互異數字（0 到 9）

• 推導與計算：
  6 個位置從 10 個數字中不重複選取且考慮順序。
  $P(10, 6) = \frac{10!}{(10-6)!} = 10 \times 9 \times 8 \times 7 \times 6 \times 5 = 151,200$
• 結果：$151,200$

(c) 6 個嚴格遞增數字（0 到 9）

• 推導與計算：
  滿足 $0 \le x_1 < x_2 < x_3 < x_4 < x_5 < x_6 \le 9$。只要從 10 個數字中取出 6 個不重複數字，由小到大的排序方式只有唯一 1 種，無須另外排列。
  $C(10, 6) = \binom{10}{6} = \frac{10 \times 9 \times 8 \times 7}{4 \times 3 \times 2 \times 1} = 210$
• 結果：$210$

(d) 6 個遞增數字（0 到 9，可重複）

• 推導與計算：
  滿足 $0 \le x_1 \le x_2 \le x_3 \le x_4 \le x_5 \le x_6 \le 9$。

核心觀念

本題考查命題邏輯（Propositional Logic）中的恆真式證明（Tautology Proof）與邏輯等價律（Logical Equivalences）。

解題時主要採用的定義與邏輯定律如下：

1. 條件蘊涵消去律（Implication Law）：$A \rightarrow B \equiv \neg A \vee B$
2. 吸收律（Absorption Law）：$A \wedge (A \vee B) \equiv A$ 與 $A \vee (A \wedge B) \equiv A$
3. 排中律（Law of Excluded Middle）：$A \vee \neg A \equiv \mathbf{T}$（其中 $\mathbf{T}$ 代表 True / 恆真）
4. 支配律（Domination Law）：$A \vee \mathbf{T} \equiv \mathbf{T}$
5. 恆真式（Tautology）之定義：不論命題變數 $p$ 與 $q$ 的真假值（Truth Values）組合為何，整個複合命題之計算結果皆恆為真（$\mathbf{T}$）。

---

解題方法

本題目標為證明複合命題 $[(q \rightarrow p) \wedge p] \rightarrow (p \vee q)$ 為恆真式。以下提供兩種標準且嚴謹的證明方法：

方法一：邏輯等價律代數推導法（推薦解法）

利用邏輯等價定律對複合命題進行一步步邏輯化簡：

1. 處理內層條件式：
   利用條件蘊涵律 $q \rightarrow p \equiv \neg q \vee p$，將原式展開：
   $[(q \rightarrow p) \wedge p] \rightarrow (p \vee q) \equiv [(\neg q \vee p) \wedge p] \rightarrow (p \vee q)$

2. 套用吸收律（Absorption Law）：
   觀察前項括號內部 $(\neg q \vee p) \wedge p$，根據吸收律 $p \wedge (p \vee \neg q) \equiv p$：
   $[(\neg q \vee p) \wedge p] \equiv p$
   原式可化簡為：
   $p \rightarrow (p \vee q)$

3. 展開外層條件式：
   再次套用條件蘊涵律 $A \rightarrow B \equiv \neg A \vee B$：
   $p \rightarrow (p \vee q) \equiv \neg p \vee (p \vee q)$

4. 利用結合律與排中律：
   利用「或（$\vee$）」運算的結合律與排中律 $\neg p \vee p \equiv \mathbf{T}$：
   $\neg p \vee (p \vee q) \equiv (\neg p \vee p) \vee q \equiv \mathbf{T} \vee q$

5. 套用支配律：
   根據支配律，任何命題與恆真命題 $\mathbf{T}$ 作「或（$\vee$）」運算，結果恆為 $\mathbf{T}$：
   $\mathbf{T} \vee q \equiv \mathbf{T}$

由上述推導可知，該命題在任何情況下皆為真，證畢。

---

方法二：真值表法（Truth Table Method）

窮舉命題變數 $p, q \in \{\mathbf{T}, \mathbf{F}\}$ 的所有可能組合，計算最終命題之真值：

核心觀念

本題考查**數理邏輯（Mathematical Logic）中的一階謂詞邏輯（First-Order Predicate Logic）與論證有效性（Validity of Arguments）**判斷。

1. 論證有效性定義：一個論證（Argument）稱為有效（Valid），當且僅當在所有使前提（Premises）全為真的情況下，結論（Conclusion）亦必然為真；若能找到一種情況使得前提全為真但結論為假，則該論證稱為無效（Invalid），此種情況稱為反例（Counterexample）。
2. 全稱特化規則（Universal Instantiation, UI）：若全稱命題 $\forall x P(x)$ 為真，則對論域中的任意特定個體 $c$，$P(c)$ 亦為真。
3. 推論法則與邏輯謬誤：
   • 假言肯定律（Modus Ponens, MP）：已知條件句 $p \rightarrow q$ 為真且前項 $p$ 為真，可有效推得後項 $q$ 為真。
   • 肯定後項謬誤（Fallacy of Affirming the Consequent）：已知條件句 $p \rightarrow q$ 為真且後項 $q$ 為真，企圖推得前項 $p$ 為真（屬於無效推論）。
   • 否定前項謬誤（Fallacy of Denying the Antecedent）：已知條件句 $p \rightarrow q$ 為真且前項之否定 $\neg p$ 為真，企圖推得後項之否定 $\neg q$ 為真（屬於無效推論）。

---

解題方法

將各小題的自然語言敘述進行符號化（Symbolization）：

1. 定義適當的論域 $U$（全體人類）與謂詞（Predicates）。
2. 將全稱條件句表示為 $\forall x (P(x) \rightarrow Q(x))$。
3. 利用全稱特化（UI）將命題帶入指定個體，轉化為命題邏輯（Propositional Logic）形式。
4. 檢驗該命題邏輯形式是否符合有效推論規則（如 Modus Ponens），或屬於常見邏輯謬誤（如 Affirming the Consequent、Denying the Antecedent），並對無效論證給出合理的語義反例。

---

選項分析

a) All students go to school. / John is a student. / Therefore, John goes to school.

• 符號化定義：
  設 $S(x)$ 表示「$x$ 是學生」，$P(x)$ 表示「$x$ 上學」。

  • 前提 1：$\forall x (S(x) \rightarrow P(x))$
  • 前提 2：$S(\text{John})$
  • 結論：$P(\text{John})$

• 邏輯推導：

  1. $\forall x (S(x) \rightarrow P(x))$ （前提 1）
  2. $S(\text{John}) \rightarrow P(\text{John})$ （由 1 經全稱特化 UI 得出）
  3. $S(\text{John})$ （前提 2）
  4. $\therefore P(\text{John})$ （由 2、3 依據假言肯定律 Modus Ponens 推得）

• 分析與結論：
  推導過程完全符合假言肯定律（Modus Ponens），當前提皆為真時，結論必然為真。因此，論證 (a) 為Valid（有效）。

---

b) All citizens pay their taxes. / Tom pays his taxes. / Therefore, Tom is a citizen.

• 符號化定義：
  設 $C(x)$ 表示「$x$ 是公民」，$T(x)$ 表示「$x$ 繳稅」。

  • 前提 1：$\forall x (C(x) \rightarrow T(x))$
  • 前提 2：$T(\text{Tom})$
  • 結論：$C(\text{Tom})$

• 邏輯推導：

  1. $\forall x (C(x) \rightarrow T(x))$ （前提 1）
  2. $C(\text{Tom}) \rightarrow T(\text{Tom})$ （由 1 經全稱特化 UI 得出）

核心觀念

本題考查離散數學中的數學歸納法（Principle of Mathematical Induction, PMI）。
數學歸納法是證明與自然數或整數相關命題 $P(n)$ 對所有 $n \ge n_0$（本題起始值 $n_0 = 2$）恆成立的核心證明工具。標準證明結構包含以下三個步驟：

1. 基礎步驟（Base Step）：驗證初始值 $n = 2$ 時，命題 $P(2)$ 是否成立。
2. 歸納假設（Inductive Hypothesis）：假設當 $n = k$（$k \ge 2$ 的任意整數）時，命題 $P(k)$ 成立。
3. 歸納步驟（Inductive Step）：利用歸納假設，推導出當 $n = k + 1$ 時，命題 $P(k+1)$ 亦成立。

完成上述步驟後，根據數學歸納法原理即可宣告對所有整數 $n \ge 2$，命題 $P(n)$ 均成立。

---

解題方法

設命題 $P(n)$ 為：
$\prod_{i=2}^{n} \left(1-\frac{1}{i^2}\right) = \left(1-\frac{1}{4}\right) \times \left(1-\frac{1}{9}\right) \times \cdots \times \left(1-\frac{1}{n^2}\right) = \frac{n+1}{2n}, \quad \forall n \ge 2$

以下進行嚴嚴謹謹的數學歸納法證明：

Step 1: 基礎步驟（Base Step）

當 $n = 2$ 時：

• 左式（LHS）$= 1 - \frac{1}{2^2} = 1 - \frac{1}{4} = \frac{3}{4}$
• 右式（RHS）$= \frac{2 + 1}{2(2)} = \frac{3}{4}$

因為左式 $=$ 右式，故當 $n = 2$ 時，命題 $P(2)$ 成立。

Step 2: 歸納假設（Inductive Hypothesis）

假設當 $n = k$（$k \ge 2$ 的某個整數）時，命題 $P(k)$ 成立，即：
$\left(1-\frac{1}{4}\right) \times \left(1-\frac{1}{9}\right) \times \cdots \times \left(1-\frac{1}{k^2}\right) = \frac{k+1}{2k}$

Step 3: 歸納步驟（Inductive Step）

目標為證明當 $n = k + 1$ 時，命題 $P(k+1)$ 亦成立，即證明：
$\left(1-\frac{1}{4}\right) \times \left(1-\frac{1}{9}\right) \times \cdots \times \left(1-\frac{1}{k^2}\right) \times \left(1-\frac{1}{(k+1)^2}\right) = \frac{(k+1)+1}{2(k+1)} = \frac{k+2}{2(k+1)}$

推導過程：
當 $n = k + 1$ 時，從左式（LHS）出發：
$\text{LHS} = \left[ \left(1-\frac{1}{4}\right) \times \left(1-\frac{1}{9}\right) \times \cdots \times \left(1-\frac{1}{k^2}\right) \right] \times \left(1-\frac{1}{(k+1)^2}\right)$

將歸納假設代入中括號部分：
$\text{LHS} = \frac{k+1}{2k} \times \left(1-\frac{1}{(k+1)^2}\right)$

將右側括號內進行通分：
$\text{LHS} = \frac{k+1}{2k} \times \frac{(k+1)^2 - 1}{(k+1)^2}$

利用平方差公式 $a^2 - b^2 = (a-b)(a+b)$ 展開分子 $(k+1)^2 - 1^2$：
$(k+1)^2 - 1 = [(k+1)-1][(k+1)+1] = k(k+2)$

題目敘述的公式有誤。因群組無標籤且皆非空，將 $n$ 人分成 $n-2$ 組時，只可能有兩種情形：

1. 一組有 $3$ 人，其餘皆為單人組：共有 $\binom{n}{3}$ 種。
2. 兩組各有 $2$ 人，其餘皆為單人組：先選出 $4$ 人，再將其配成兩對；

核心觀念

本題旨在考查組合數學中的鴿籠原理（Pigeonhole Principle，又稱抽屜原理）與集合劃分（Partition of a Set）的應用：

• 鴿籠原理：若將 $n$ 個物品放入 $k$ 個盒子（鴿籠）中，且 $n > k$，則必定至少有一個盒子包含至少 $\lceil \frac{n}{k} \rceil$ 個物品。當 $n = k + 1$ 時，代表至少有一個盒子含有至少 2 個物品。
• 集合劃分：將全域集合 $S$ 分割成若干個互斥（Disjoint）的子集，使得每一個相加為目標值 10 的可能數對各自歸類為一個獨立的鴿籠。

---

解題方法

1. 建立鴿籠（構造劃分子集）：
   觀察集合 $S = \{1, 2, 3, 4, 5, 6, 7, 8, 9\}$ 中，兩數相加等於 10 的組合。將集合 $S$ 分割為以下 5 個互斥子集：
   $A_1 = \{1, 9\}$
   $A_2 = \{2, 8\}$
   $A_3 = \{3, 7\}$
   $A_4 = \{4, 6\}$
   $A_5 = \{5\}$
   這 5 個子集構成集合 $S$ 的一個完整劃分，滿足 $\bigcup_{i=1}^5 A_i = S$ 且對任意 $i \neq j$ 有 $A_i \cap A_j = \emptyset$。

2. 套用鴿籠原理：

   • 視選取的元素為「鴿子」，故鴿子數量 $n = 6$。
   • 視上述劃分出的子集 $A_1, A_2, A_3, A_4, A_5$ 為「鴿籠」，故鴿籠數量 $k = 5$。
   • 根據鴿籠原理，將 6 個元素分配至 5 個鴿籠中，必定至少有一個子集包含至少 $\lceil \frac{6}{5} \rceil = 2$ 個選取的元素。

3. 證明邏輯導出：

   • 子集 $A_5 = \{5\}$ 的大小只有 1（$|A_5| = 1$），因此不可能包含 2 個選取的元素。
   • 含有至少 2 個選取元素的子集必定屬於 $A_1, A_2, A_3, A_4$ 之一。

核心觀念

本題考查離散數學中**二元關係（Binary Relation）**的四大核心基本性質。設 $S$ 為班上所有學生的集合，$R$ 為定義在 $S$ 上的二元關係：

1. 自反性（Reflexivity）：對所有 $x \in S$，$x R x$ 恆成立。
2. 對稱性（Symmetricity）：對所有 $x, y \in S$，若 $x R y$，則 $y R x$ 恆成立。
3. 反對稱性（Antisymmetry）：對所有 $x, y \in S$，若 $x R y$ 且 $y R x$，則 $x = y$ 恆成立。
4. 遞移性（Transitivity）：對所有 $x, y, z \in S$，若 $x R y$ 且 $y R z$，則 $x R z$ 恆成立。

---

解題方法

為了嚴謹推導，我們將題目條件符號化：
設 $S$ 為班級全體學生的集合。對任意學生 $x \in S$，定義函數 $h(x)$ 代表學生 $x$ 的「家鄉」。
關係 $R$ 的定義可寫為：
$x R y \iff h(x) = h(y)$

透過將關係轉化為同一個數值／屬性的「相等關係 ($=$)」，利用相等符號的基本代數性質即可逐一判斷。

---

選項分析

• Reflexive（自反性）：具備（正確）

  • 證明：對任意學生 $x \in S$，學生 $x$ 的家鄉必定與自己相同，即 $h(x) = h(x)$ 恆成立。因此對所有 $x \in S$，皆有 $x R x$。

• Symmetric（對稱性）：具備（正確）

  • 證明：對任意學生 $x, y \in S$，若 $x R y$，表示 $h(x) = h(y)$。

核心觀念

本題考查「偏序集合」與「Hasse diagram（哈斯圖）」：

• 關係 $R$ 定義為 $xRy \iff x\mid y$，表示 $x$ 整除 $y$。
• 在偏序中，$xRy$ 可視為 $x\leq_R y$，故圖形中較小元素放在較下方。
• 若 $xRy$ 且 $x\ne y$，中間不存在元素 $z$ 使得 $xRz$ 且 $zRy$，則稱 $y$ 覆蓋 $x$，Hasse 圖只畫這些覆蓋關係。

相關定義：

• 極大元 maximal element：不存在不同於它的元素比它大。
• 極小元 minimal element：不存在不同於它的元素比它小。
• 最大元 greatest element：比集合中所有元素都大。
• 最小元 least element：比集合中所有元素都小。
• 下界 lower bound：小於等於集合中的每個元素。
• 上界 upper bound：大於等於集合中的每個元素。

本題的偏序關係是整除關係，所以：

• $x\leq_R y$ 等價於 $x\mid y$。
• 「較大」代表「被較多元素整除」。
• 「較小」代表「可以整除較多元素」。

---

解題方法

先列出 $S$ 中各元素的倍數關係：

• $1$ 整除 $2,3,4,5,6,7$。
• $2$ 整除 $4,6$。
• $3$ 整除 $6$。
• $4,5,6,7$ 在 $S$ 中沒有其他不同元素是它們的倍數。

接著刪除可由傳遞性得到的邊。例如：

• $1\mid 4$，但 $1\mid 2\mid 4$，所以 Hasse 圖不直接連接 $1$ 與 $4$。
• $1\mid 6$，但 $1\mid 2\mid 6$，且 $1\mid 3\mid 6$，所以不直接連接 $1$ 與 $6$。

保留的覆蓋關係為：

$$1\prec 2,\quad 1\prec 3,\quad 1\prec 5,\quad 1\prec 7$$ $$2\prec 4,\quad 2\prec 6,\quad 3\prec 6$$

---

(a) Hasse diagram

由下而上排列：

        4       6       5       7
        |      / \
        2     3
         \   /
           1

較精確地表示所有連線：

        4       6       5       7
        |      / \
        2     3
         \   /
           1

其中：

• $1$ 連到 $2,3,5,7$；
• $2$ 連到 $4,6$；
• $3$ 連到 $6$。

注意 $1$ 與 $4$、$1$ 與 $6$ 雖然存在整除關係，但不是覆蓋關係，因此不在 Hasse 圖中直接畫線。

---

(b) $(S,R)$ 的特殊元素

(i) 極大元 maximal elements

逐一觀察各元素在 $S$ 中是否還有不同的倍數：

• $4$ 在 $S$ 中沒有其他不同倍數；
• $5$ 在 $S$ 中沒有其他不同倍數；
• $6$ 在 $S$ 中沒有其他不同倍數；
• $7$ 在 $S$ 中沒有其他不同倍數。

所以極大元為

$$\boxed{\{4,5,6,7\}}$$

$2$ 與 $3$ 不是極大元，因為 $2\mid4$、$2\mid6$，且 $3\mid6$。$1$ 也不是極大元，因為 $1$ 整除其他多個元素。

---

(ii) 極小元 minimal elements