111 專技高考高等考試 資訊技師 計算機數學 考古題詳解

核心觀念

1. 複合命題與恆真式（Tautology）之定義：

• 複合命題（Compound Proposition）：由簡單命題透過邏輯運算子（如否定 $\neg$、且 $\land$、或 $\lor$、條件式 $\to$）組合而成之命題。
• 恆真式（Tautology）：在所有可能的變數真值指派（Truth Value Assignment）下，其最終真值皆恆為「真」（True，記為 $T$ 或 $1$）的複合命題。

2. 條件式（蘊含式，Implication）之基本等價性質： $A \to B \equiv \neg A \lor B$ 條件式 $A \to B$ 僅在「前件 $A$ 為真（$T$）且後件 $B$ 為假（$F$）」時其值為假（$F$），其餘情況皆為真（$T$）。
3. 常用的邏輯等價律（Logical Equivalences）：

• 狄摩根定律（De Morgan's Laws）：$\neg(p \land q) \equiv \neg p \lor \neg q$；$\neg(p \lor q) \equiv \neg p \land \neg q$
• 結合律與交換律（Associative & Commutative Laws）：$A \lor (B \lor C) \equiv (A \lor B) \lor C$
• 排中律（Negation Law）：$p \lor \neg p \equiv T$
• 支配律（Domination Law）：$p \lor T \equiv T$
• 條件式前件為恆真：$T \to B \equiv \neg T \lor B \equiv F \lor B \equiv B$

解題方法

判定複合命題是否為恆真式，常規有兩種嚴謹證明途徑：布林代數邏輯等價化簡法與真值表法（Truth Table）。以下採用代數化簡法進行逐步推導，並輔以真值表進行驗證。

(一) 判定 $(p \land q \to p)$

運算子優先順序中，連言 $\land$ 優先於蘊含 $\to$，故題目即判定 $((p \land q) \to p)$。

【邏輯等價化簡】 利用蘊含定義式 $A \to B \equiv \neg A \lor B$ 展開：

化簡結果恆等於真值常數 $T$，因此該命題為恆真式。

【真值表驗證】

由真值表可知，在所有可能真值組合下，該式之值皆為 $T$。

(二) 判定 $(\neg q \lor (p \to q)) \to \neg p$

【邏輯等價化簡】 先化簡前件（Antecedent）式子：

核心觀念

1. 數學歸納法（Mathematical Induction）： 證明定義於非負整數（或正整數）上的命題 $P(n)$ 恆成立的標準方法，包含三個標準架構：

• 基礎步驟（Basis Step）：驗證初始值（$n = 0$ 或 $n = 1$）時命題成立。
• 歸納假設（Inductive Hypothesis, IH）：假設當 $n = k$ 時命題成立。
• 歸納步驟（Inductive Step）：利用歸納假設，推導出當 $n = k + 1$ 時命題亦成立。

2. 調和數（Harmonic Number）與群組放縮法： 調和數定義為 $H_K = \sum_{i=1}^{K} \frac{1}{i}$。本題不等式是離散數學與演算法分析中證明「調和級數發散」的經典方法（最早由 14 世紀數學家 Nicole Oresme 提出）。其切入關鍵在於將級數依 $2$ 的冪次區間進行分組： $[2^k + 1, 2^{k+1}]$ 該區間內共有 $2^k$ 個正分數，且每一項均大於等於最小項（即末項 $\frac{1}{2^{k+1}}$），藉此推得該組總和大於等於 $\frac{1}{2}$。

解題方法

證明目標：對所有整數 $n \ge 0$（或 $n \ge 1$），$H_{2^n} \ge 1 + \frac{n}{2}$ 恆成立。

步驟一：基礎步驟（Basis Step）

• 當 $n = 0$ 時： 左式 $= H_{2^0} = H_1 = 1$ 右式 $= 1 + \frac{0}{2} = 1$ 因為 $1 \ge 1$，故左式 $\ge$ 右式成立。 (註：若題目之定義域限定為正整數 $n \ge 1$，當 $n = 1$ 時：左式 $= H_{2^1} = H_2 = 1 + \frac{1}{2} = \frac{3}{2}$，右式 $= 1 + \frac{1}{2} = \frac{3}{2}$，不等式亦成立。)

步驟二：歸納假設（Inductive Hypothesis）

假設當 $n = k$（$k \ge 0$ 為整數）時，原不等式成立，即： $H_{2^k} \ge 1 + \frac{k}{2}$

步驟三：歸納步驟（Inductive Step）

考慮 $n = k + 1$ 時的左式 $H_{2^{k+1}}$： 依調和數定義拆解為前 $2^k$ 項與後續項：

核心觀念

1. 無向圖與節點連接數（Degree）： 設無向圖 $G=(V, E)$，其中頂點集合的大小為 $|V| = n$。節點 $v$ 的連接數 $\deg(v)$ 為與 $v$ 相連的邊數。題目特別強調「沒有自迴圈（no self-loop）」，表示任何節點皆不與自身相連，因此節點 $v$ 的所有相鄰點（neighbors）集合 $N(v)$ 必然滿足 $N(v) \subseteq V \setminus \{v\}$。
2. 連通圖（Connected Graph）與連通分支（Connected Component）： 若圖 $G$ 中任意兩相異節點之間均至少存在一條路徑（path），則稱 $G$ 為連通圖。若 $G$ 不是連通圖，則 $G$ 必定可以分割為至少兩個互斥、非空且彼此無邊相連的極大連通子圖，稱為連通分支。
3. 反證法（Proof by Contradiction）與排容原理（Principle of Inclusion-Exclusion）： 本題是離散數學與圖論中的經典命題（亦為狄拉克定理 Dirac's Theorem 的基礎引理）。證明連通性最嚴謹且直接的手法為「反證法」；亦可透過「排容原理」直接證明圖中任意兩點的距離至多為 $2$。

解題方法

此題在考場上有兩種標準且嚴謹的證明途徑，建議考生以結構最不易失分的「反證法」為主答，邏輯推導如下：

【方法一：反證法（利用連通分支頂點數量的極值矛盾）— 考場推薦】

1. 建立反面假設： 假設圖形 $G = (V, E)$ 不是連通圖。
2. 分割連通分支： 因為 $G$ 不連通，所以 $G$ 至少包含兩個互斥的連通分支，分別記為 $C_1 = (V_1, E_1)$ 與 $C_2 = (V_2, E_2)$。 其中 $V_1, V_2 \subseteq V$，且滿足 $V_1 \cap V_2 = \emptyset$（兩分支互斥且分支間無任何邊相連）。 因此，兩分支的頂點數總和必不大於全圖的總頂點數： $|V_1| + |V_2| \le |V|$
3. 評估單一分支內的節點數下界： 任取分支 $C_1$ 中的一個節點 $u \in V_1$。 因為 $C_1$ 為獨立的連通分支，且 $G$ 中沒有自迴圈，$u$ 的所有相鄰節點必落在 $V_1 \setminus \{u\}$ 之中。 換言之，分支 $C_1$ 內的頂點數至少包含 $u$ 本身以及與 $u$ 相鄰的所有節點： $|V_1| \ge \deg(u) + 1$ 依題目條件，每個節點的連接數至少為 $|V|/2$，即 $\deg(u) \ge \frac{|V|}{2}$，代入得： $|V_1| \ge \frac{|V|}{2} + 1$
4. 評估另一分支並導出矛盾： 同理，任取分支 $C_2$ 中的一個節點 $v \in V_2$，其分支頂點數亦滿足： $|V_2| \ge \deg(v) + 1 \ge \frac{|V|}{2} + 1$ 將兩分支的頂點數下界相加： $|V_1| + |V_2| \ge \left(\frac{|V|}{2} + 1\right) + \left(\frac{|V|}{2} + 1\right) = |V| + 2$ 此結果與步驟 2 中所得的幾何事實 $|V_1| + |V_2| \le |V|$ 產生直接矛盾（$|V| + 2 \le |V| \implies 2 \le 0$，不成立）。
5. 結論： 反面假設不成立，故圖形 $G$ 必為一連接圖。

【方法二：直接綜合法（證明任意兩點間距離 $\le 2$）】

1. 設 $|V| = n$。欲證 $G$ 為連通圖，只需證明對於任意兩相異節點 $u, v \in V$，$u$ 與 $v$ 之間皆存在一條路徑。
2. 分兩種情形討論：

• 情形一：若 $(u, v) \in E$

核心觀念

本題評量機率論中的核心推論工具，涉及以下三大觀念與定理：

1. 先驗機率（Prior Probability）與條件機率（Conditional Probability）：從樣本空間分類中求出各類別被抽中的初始機率，以及給定類別條件下特定事件發生的機率。
2. 全機率定理（Law of Total Probability）：當樣本空間被分割為互斥且聯集為全集的事件集合 $\{A, B\}$ 時，任意事件 $H$ 發生的邊際機率可展開為各分割子集的條件機率加權總和： $P(H) = P(A)P(H \mid A) + P(B)P(H \mid B)$
3. 貝氏定理（Bayes' Theorem）：在觀測到結果事件（出現正面）後，逆向反推其來自特定原因（該銅板為正面機率 $3/5$ 之銅板）的後驗機率（Posterior Probability）： $P(A \mid H) = \frac{P(A \cap H)}{P(H)} = \frac{P(A)P(H \mid A)}{P(A)P(H \mid A) + P(B)P(H \mid B)}$

解題方法

步驟一：定義事件與已知條件

• 設 $A$ 為「抽到出現正面機率為 $3/5$ 的銅板」之事件。
• 設 $B$ 為「抽到出現正面機率為 $1/3$ 的銅板」之事件。
• 設 $H$ 為「丟擲該銅板後結果出現正面」之事件。

袋中共有 12 個銅板，兩類各佔 6 個，故先驗機率分別為： $P(A) = \frac{6}{12} = \frac{1}{2}$ $P(B) = \frac{6}{12} = \frac{1}{2}$

兩類銅板出現正面的條件機率分別為： $P(H \mid A) = \frac{3}{5}$ $P(H \mid B) = \frac{1}{3}$

步驟二：利用全機率定理計算擲出正面的機率 $P(H)$

$P(H) = P(A)P(H \mid A) + P(B)P(H \mid B)$

核心觀念

本題旨在評量離散數學中**集合的遞迴定義（Recursive Definition of Sets）與形式語言（Formal Languages）**的基本概念。

一個集合 $S$ 的完整遞迴定義包含三個不可或缺的部分：

1. 基底步驟（Basis Step）：指定集合中最基礎的起始元素（通常包含空字串 $\lambda$ 或長度最短的基礎字串）。
2. 遞迴步驟（Recursive Step）：提供由已知屬於 $S$ 的元素構造出新元素的規則。
3. 排除規則／極小性條件（Exclusion Rule）：明確限制除由基底步驟與遞迴步驟經有限次應用所產生之元素外，其餘元素皆不屬於 $S$。

設二元字母集（Alphabet）為 $\Sigma = \{0, 1\}$，字串 $w \in \Sigma^*$ 中 $0$ 與 $1$ 的出現次數分別記為 $N_0(w)$ 與 $N_1(w)$。本題要求定義之集合為： $S = \{ w \in \{0, 1\}^* \mid N_0(w) = N_1(w) \}$ 該集合中的所有字串長度必為偶數（即 $|w| = 2k, k \in \mathbb{N} \cup \{0\}$）。

解題方法

要完整定義 $S$，必須確保規則具備健全性（Soundness，生成的字串必定平衡）與完備性（Completeness，所有平衡字串皆能被生成）。

1. 為什麼單純的「包夾規則」不足以涵蓋全部字串？

若僅定義「若 $w \in S$，則 $0w1 \in S$ 與 $1w0 \in S$」，則只能生成以不同符號開頭與結尾的字串。然而，許多合法字串的開頭與結尾是相同的符號（例如 $0110$ 或 $1001$），此類字串無法僅透過頭尾各加一個互補位元得到。因此，遞迴步驟必須引入字串的「串接（Concatenation）」或「分段構造」。

2. 標準解法推導（離散數學權威教材 Rosen 標準形式）

考慮任意非空且 $0$ 與 $1$ 個數相等的字串 $w \in S$（$|w| \ge 2$）：

• 假設 $w$ 以 $0$ 開頭，則 $w = 0u$。定義走步計數函數 $D(k) = N_0(w_1 \dots w_k) - N_1(w_1 \dots w_k)$。
• 在 $k=1$ 時，$D(1) = 1$；而在讀完整個字串 $k=|w|$ 時，$D(|w|) = 0$。
• 因為每次增加一個字元，$D(k)$ 的變化量只能是 $+1$ 或 $-1$，根據整數的介值性（Discrete Intermediate Value Theorem），必存在最小的正整數索引 $m \ge 2$，使得 $D(m) = 0$。
• 由於 $m$ 是首次歸零的位置，因此第 $m$ 個字元必為 $1$。
• 故字串 $w$ 可唯一分解為 $w = 0 x 1 y$，其中：
• $x$ 為第 $2$ 到第 $m-1$ 個字元，滿足 $N_0(x) = N_1(x)$，故 $x \in S$。
• $y$ 為第 $m+1$ 到結尾的字元，滿足 $N_0(y) = N_1(y)$，故 $y \in S$。
• 同理，若 $w$ 以 $1$ 開頭，則 $w$ 必可表示為 $1 x 0 y$，其中 $x, y \in S$。

核心觀念

本題評量離散數學與圖論（Graph Theory）中最小生成樹（Minimum Spanning Tree, MST）的唯一性定理。涉及的核心定義與定理如下：

1. 生成樹（Spanning Tree）： 設 $G=(V, E)$ 為一個具有 $|V|=n$ 個頂點的連通無向圖，其生成樹 $T=(V, E_T)$ 為 $G$ 的一個包含所有頂點且無迴路（acyclic）的連通子圖，滿足邊數 $|E_T| = n - 1$。
2. 最小生成樹（MST）： 在加權圖中，生成樹 $T$ 的總權重定義為所有邊權重之和： $w(T) = \sum_{e \in E_T} w(e)$ 若 $T$ 的總權重在所有可能的生成樹中最小，則稱 $T$ 為最小生成樹。
3. 環性質（Cycle Property）與替換推論（Exchange Property）： 若將一條不在樹 $T$ 中的邊 $e \notin E_T$ 加入 $T$ 中，必形成唯一的簡單環（Simple Cycle）$C$。若由該環 $C$ 中移去任意一條邊 $e' \in C$，所得的新圖依然是一棵生成樹。

解題方法

本題為申論證明題，結論為：其最小生成樹「唯一」。

採用**反證法（Proof by Contradiction）配合邊置換（Cut/Cycle Exchange Argument）**進行證明：

證明步驟

1. 提出反面假設： 假設圖 $G=(V, E)$ 的所有邊權重皆兩兩相異，但存在兩棵不同的最小生成樹 $T_1$ 與 $T_2$（即 $T_1 \neq T_2$），且兩者的總權重相同： $w(T_1) = w(T_2)$

2. 選取關鍵邊（對稱差之最小權重邊）： 因為 $T_1 \neq T_2$，兩樹的邊集合必不完全相同。考慮對稱差集合： $(E(T_1) \setminus E(T_2)) \cup (E(T_2) \setminus E(T_1)) \neq \emptyset$ 由良序性質，在此對稱差集合中必存在一條權重最小的邊，記為 $e$。 不失一般性，假設此最小邊屬於 $T_1$，即： $e \in E(T_1) \setminus E(T_2)$

3. 建構環並尋找替換邊： 將邊 $e$ 加入樹 $T_2$ 中，則 $T_2 \cup \{e\}$ 必包含唯一的簡單環 $C$。 由於 $T_1$ 本身是一棵樹（內部無環），故環 $C$ 中的邊不可能全部都屬於 $T_1$。 因此，在環 $C$ 中必定存在至少一條邊 $e'$ 滿足：

核心觀念

本題評量**抽樣分配（Sampling Distribution）與中央極限定理（Central Limit Theorem, CLT）**的應用：

1. 中央極限定理（CLT）： 若母體具有有限平均數 $\mu$ 與標準差 $\sigma$，當隨機抽樣之樣本數 $n$ 夠大（一般統計慣例 $n \ge 30$）時，樣本平均數 $\bar{X}$ 的抽樣分配會近似於常態分佈（Normal Distribution）： $\bar{X} \sim N\left(\mu, \frac{\sigma^2}{n}\right)$
2. 樣本平均數之標準誤（Standard Error, SE）： $\sigma_{\bar{X}} = \frac{\sigma}{\sqrt{n}}$ 標準誤衡量樣本平均數相對於母體平均數的離散程度，隨樣本數增加而縮小。
3. 標準化變數（Z 分數）： 將樣本平均數轉換為標準常態隨機變數 $Z \sim N(0, 1)$： $Z = \frac{\bar{X} - \mu}{\sigma_{\bar{X}}} = \frac{\bar{X} - \mu}{\frac{\sigma}{\sqrt{n}}}$

解題方法

步驟一：確認已知母體參數與抽樣條件

• 母體平均數 $\mu = 100$
• 母體標準差 $\sigma = 15$
• 隨機抽樣人數（樣本數）$n = 100$
• 欲檢驗之事件：樣本平均成績 $\bar{X} > 115$

步驟二：決定樣本平均數的分配性質

由於抽樣人數 $n = 100 \ge 30$，符合大樣本條件。依據中央極限定理，樣本平均數 $\bar{X}$ 近似服從常態分佈：

• 期望值 $E(\bar{X}) = \mu = 100$
• 標準誤 $\sigma_{\bar{X}} = \frac{\sigma}{\sqrt{n}} = \frac{15}{\sqrt{100}} = \frac{15}{10} = 1.5$

即： $\bar{X} \sim N(100, 1.5^2)$

步驟三：列出機率計算式並進行標準化

欲求樣本平均數超過 115 分的機率 $P(\bar{X} > 115)$，依題目要求列出計算式：

$P(\bar{X} > 115) = P\left(\frac{\bar{X} - \mu}{\frac{\sigma}{\sqrt{n}}} > \frac{115 - 100}{\frac{15}{\sqrt{100}}}\right) = P\left(Z > \frac{15}{1.5}\right) = P(Z > 10)$

核心觀念

本題評量**離散型二維隨機變數（Discrete Bivariate Random Variables）及其聯合機率質量函數（Joint Probability Mass Function, joint PMF）**的基本性質與事件機率計算：

1. 聯合機率質量函數之定義： 設離散隨機變數 $X, Y$ 之取值集合為 $S_X, S_Y$，對任意事件 $A \subseteq S_X \times S_Y$，該事件發生的機率為事件所包含之所有點的聯合機率總和： $P(A) = \sum_{(i,j) \in A} P(X=i, Y=j)$

2. 機率規範性檢驗（總和為 1）： 隨機變數 $X, Y \in \{1,2,3,4\}$，所有可能的取值配對共有 $4 \times 4 = 16$ 組。 總機率為： $\sum_{i=1}^4 \sum_{j=1}^4 \frac{i+j}{80} = \frac{1}{80} \left[ 4\sum_{i=1}^4 i + 4\sum_{j=1}^4 j \right] = \frac{4(10) + 4(10)}{80} = \frac{80}{80} = 1$ 確認給定之函數為合法的聯合 PMF。

解題方法

(一) 計算 $P(X=Y)$

1. 找出符合條件之點集： 事件 $\{X=Y\}$ 對應的數對集合為對角線元素： $A_1 = \{(1,1), (2,2), (3,3), (4,4)\}$

2. 代入 PMF 累加求和： $P(X=Y) = \sum_{k=1}^4 P(X=k, Y=k) = \sum_{k=1}^4 \frac{k+k}{80} = \sum_{k=1}^4 \frac{2k}{80}$ $P(X=Y) = \frac{2}{80} \times (1 + 2 + 3 + 4) = \frac{2}{80} \times 10 = \frac{20}{80} = \frac{1}{4}$

(二) 計算 $P(XY=6)$

1. 找出符合條件之點集： 由於隨機變數取值範圍為 $X, Y \in \{1,2,3,4\}$，兩數乘積等於 $6$ 之整數分解組合為： $XY = 6 \implies (X,Y) \in \{(2,3), (3,2)\}$ （註：$1 \times 6$ 與 $6 \times 1$ 因超出取值範圍 $\{1,2,3,4\}$ 而不計入）

2. 代入 PMF 累加求和： $P(XY=6) = P(X=2, Y=3) + P(X=3, Y=2)$

核心觀念

本題評量隨機變數線性組合的期望值與變異數性質，涵蓋以下核心數學定義與定理：

1. 常態分布的參數定義： 隨機變數 $Z \sim N(\mu, \sigma^2)$ 表示其期望值 $E[Z] = \mu$，變異數 $\operatorname{Var}[Z] = \sigma^2$。

• 由題意知：$E[X] = 2$、$\operatorname{Var}[X] = 5$；$E[Y] = 5$、$\operatorname{Var}[Y] = 9$。

2. 期望值的線性性質（Linearity of Expectation）： 對於任意隨機變數 $X, Y$ 及實數常數 $a, b, c$，不論兩變數是否獨立，皆滿足： $E[aX + bY + c] = aE[X] + bE[Y] + c$

3. 線性組合的變異數性質： 對於任意隨機變數 $X, Y$ 及實數常數 $a, b, c$： $\operatorname{Var}[aX + bY + c] = a^2 \operatorname{Var}[X] + b^2 \operatorname{Var}[Y] + 2ab\operatorname{Cov}(X, Y)$ 因為題目已給定 $X$ 與 $Y$ 為獨立隨機變數（Independent Random Variables），其共變異數 $\operatorname{Cov}(X, Y) = 0$，公式可簡化為： $\operatorname{Var}[aX + bY + c] = a^2 \operatorname{Var}[X] + b^2 \operatorname{Var}[Y]$

解題方法

(一) 計算 $E[W]$

給定 $W = 3X - 2Y + 1$，利用期望值的線性性質展開：

$E[W] = E[3X - 2Y + 1] = 3E[X] - 2E[Y] + 1$

將 $E[X] = 2$ 與 $E[Y] = 5$ 代入：

$E[W] = 3(2) - 2(5) + 1 = 6 - 10 + 1 = -3$

(二) 計算 $\operatorname{Var}[W]$