114 年 國立嘉義大學資訊工程學系碩士班《離散數學》

核心觀念

本題考查命題邏輯（Propositional Logic）中條件蘊涵式（Conditional/Implication） $p \rightarrow q$ 與雙條件式（Biconditional） $p \leftrightarrow q$ 的真假值定義，以及邏輯等價律（Logical Equivalences）的簡化應用。

1. 蘊涵式 $p \rightarrow q$ 的真假值定義：

   • 只有當前件 $p$ 為真（$\text{True}$）且後件 $q$ 為假（$\text{False}$）時，$p \rightarrow q$ 才為假（$\text{False}$）。
   • 當前件 $p$ 為假，或後件 $q$ 為真時，$p \rightarrow q$ 皆為真（$\text{True}$）。

2. 雙條件式 $p \leftrightarrow q$ 的真假值定義：

   • 當 $p$ 與 $q$ 的真假值相同（同為真或同為假）時，$p \leftrightarrow q$ 為真（$\text{True}$）。
   • 當 $p$ 與 $q$ 的真假值不同時，$p \leftrightarrow q$ 為假（$\text{False}$）。

3. 邏輯等價律（Logical Equivalences）：

   • 吸收律（Absorption Law）：$p \vee (p \land q) \equiv p$
   • 分配律（Distributive Law）：$p \vee (q \land r) \equiv (p \vee q) \land (p \vee r)$
   • 否定律與恆等律：$p \vee \neg p \equiv \text{True}$、$\text{True} \land r \equiv r$

解題方法

針對兩個子題之給定條件特性採用對應的切入點：

• (a) 子題切入點：條件 $p \rightarrow q \equiv \text{False}$ 具有唯一性，可唯一鎖定變數賦值 $p = \text{True}$ 且 $q = \text{False}$。將此確切真假值直接代入目標命題 $(p \vee \neg q) \rightarrow q$ 進行演算即可求得解答。
• (b) 子題切入點：條件 $p \rightarrow q \equiv \text{True}$ 包含多種可能賦值組合（共 3 種）。可透過「真值反例法」或「邏輯代數簡化法」進行分析：
  1. 真值反例法：尋找在滿足 $p \rightarrow q \equiv \text{True}$ 的前提下，能否使目標命題分別導出 $\text{True}$ 與 $\text{False}$ 兩種不同結果。若可導出兩種結果，即說明無法唯一確定。
  2. 邏輯代數簡化法：將目標命題 $p \vee (p \leftrightarrow q)$ 進行邏輯等價化簡，觀察其結構是否等價於原命題的逆命題（Converse），進而判定真假值是否受限。

選項／子題分析

(a) 子題分析與詳細推導

1. 確定真假值賦值：
   根據蘊涵式定義，當 $p \rightarrow q$ 的值為假（$\text{False}$）時，前件必須為真且後件必須為假：
   $p = \text{True}, \quad q = \text{False}$

2. 逐步計算目標命題 $(p \vee \neg q) \rightarrow q$：

   • 計算否定項：$\neg q = \neg \text{False} = \text{True}$
   • 計算前件括號項：$p \vee \neg q = \text{True} \vee \text{True} = \text{True}$
   • 代入整體蘊涵式：
     $(p \vee \neg q) \rightarrow q \equiv \text{True} \rightarrow \text{False} \equiv \text{False}$

因此，(a) 小題之真假值可完全確定為 False。

(b) 子題分析與詳細推導

1. 列出所有符合條件的賦值組合：
   當 $p \rightarrow q$ 的值為真（$\text{True}$）時，$(p, q)$ 可能為以下三種組合之一：
   • 組合一：$p = \text{True}, q = \text{True}$

核心觀念

這題考的是加權圖的單源最短路徑。每條邊的權重代表訊息傳送所需分鐘數；中心一收到消息就立即轉播，因此某中心最早收到消息的時間，等於從 $a$ 到該中心的最短路徑長度。

可用 Dijkstra 演算法逐步確定最短距離：每次選取尚未確定、暫定距離最小的頂點，再用它更新相鄰頂點的距離。

解題方法

從 $a$ 出發，初始距離為 $d(a)=0$。圖中相關邊的權重包括 $a$ 到 $b,c,d$ 分別為 $3,5,6$，以及 $b$ 到 $f$ 為 $1$、$f$ 到 $d$ 為 $1$、$f$ 到 $e$ 為 $2$、$d$ 到 $g$ 為 $2$、$g$ 到 $h$ 為 $1$。

依序更新最短距離：

1. 從 $a$ 出發：$d(b)=3,\ d(c)=5,\ d(d)=6$。
2. $b$ 在第 $3$ 分鐘收到消息。經 $b$ 更新後，$d(c)=3+1=4$、$d(f)=3+1=4$、$d(e)=3+5=8$。
3. $c$ 和 $f$ 都在第 $4$ 分鐘收到消息。經 $f$ 更新後，$d(d)=4+1=5$、$d(e)=4+2=6$、$d(g)=4+4=8$、$d(h)=4+8=12$。
4. $d$ 在第 $5$ 分鐘收到消息，更新 $d(g)=5+2=7$。

核心觀念

本題考查離散數學中的廣義鴿籠原理（Generalized Pigeonhole Principle）與資源分配容納量。

1. 廣義鴿籠原理：若將 $n$ 個物件（鴿子）放入 $k$ 個盒子（鴿籠）中，則至少有一個盒子包含至少 $\lceil n / k \rceil$ 個物件（其中 $\lceil \cdot \rceil$ 表示取頂函數 Ceiling Function）。
2. 場地排程約束：一間教室在同一個時間段（time slot）內只能排定一門課程。因此，若某時間段內有 $M$ 門課程同時進行，學校至少需要 $M$ 間教室才能保證無排課衝突。

解題方法

1. 定義變數：

   • 總課程數 $n = 698$（物件數）
   • 可用時間段數 $k = 36$（盒子數）

2. 應用廣義鴿籠原理計算尖峰時段課程數：
   將 698 門課程分配至 36 個時間段中，根據廣義鴿籠原理，必定存在至少一個時間段，其同時進行的課程數量至少為：
   $\left\lceil \frac{n}{k} \right\rceil = \left\lceil \frac{698}{36} \right\rceil$

3. 數值推導：
   進行整數除法：
   $698 = 36 \times 19 + 14$
   即：
   $\frac{698}{36} = 19 + \frac{14}{36} \approx 19.389$
   使用取頂函數向上取整：
   $\left\lceil \frac{698}{36} \right\rceil = 20$

(a) 設選到 $k$ 張黑牌，則紅牌為 $15-k$ 張。因 $15$ 為奇數，黑牌為偶數時，紅牌必為奇數。

利用奇偶二項式和：

【答案】

(b) 設紅心、方塊、黑桃、梅花張數分別為 $h,d,s,c$，則

固定各花色張數時，選法為

核心觀念

本題考查機率論中的條件機率（Conditional Probability）、全機率定理（Law of Total Probability）與貝氏定理（Bayes' Theorem），並結合醫學檢驗領域常見的「檢驗基率謬誤（Base Rate Fallacy）」。

1. 事件定義：

   • 設 $D$ 為「受測者罹患疾病（Disease）」之事件，$\overline{D}$ 為「受測者未罹患疾病」之事件。
   • 設 $T^+$ 為「檢驗結果呈陽性（Test Positive）」之事件，$T^-$ 為「檢驗結果呈陰性（Test Negative）」之事件。

2. 已知參數與統計學對應：

   • 盛行率／先驗機率（Prevalence / Prior Probability）：$P(D) = \frac{5}{1000} = 0.005$，故未患病機率 $P(\overline{D}) = 1 - P(D) = 0.995$。
   • 假陽性率（False Positive Rate）：$P(T^+ \mid \overline{D}) = 3\% = 0.03$。
   • 假陰性率（False Negative Rate）：$P(T^- \mid D) = 1\% = 0.01$。
   • 敏感度（Sensitivity / True Positive Rate）：$P(T^+ \mid D) = 1 - P(T^- \mid D) = 99\% = 0.99$。
   • 特異度（Specificity / True Negative Rate）：$P(T^- \mid \overline{D}) = 1 - P(T^+ \mid \overline{D}) = 97\% = 0.97$。

3. 目標問題：

   • (a) 求陽性預測值（Positive Predictive Value, PPV）：$P(D \mid T^+)$。
   • (b) 求陰性預測值（Negative Predictive Value, NPV）：$P(\overline{D} \mid T^-)$。

解題方法

(a) 計算陽性結果中確實患病的條件機率 $P(D \mid T^+)$

1. 運用全機率定理計算出「檢驗呈陽性」的總機率 $P(T^+)$：
   $P(T^+) = P(T^+ \mid D)P(D) + P(T^+ \mid \overline{D})P(\overline{D})$
   代入數值：
   $P(T^+) = (0.99 \times 0.005) + (0.03 \times 0.995) = 0.00495 + 0.02985 = 0.0348$

2. 運用貝氏定理求 $P(D \mid T^+)$：
   $P(D \mid T^+) = \frac{P(T^+ \mid D)P(D)}{P(T^+)}$
   代入數值：
   $P(D \mid T^+) = \frac{0.00495}{0.0348} = \frac{495}{3480} = \frac{33}{232} \approx 0.14224 \quad (14.22\%)$

(b) 計算陰性結果中確實未患病的條件機率 $P(\overline{D} \mid T^-)$

1. 運用全機率定理計算出「檢驗呈陰性」的總機率 $P(T^-)$：
   $P(T^-) = P(T^- \mid D)P(D) + P(T^- \mid \overline{D})P(\overline{D})$
   代入數值：
   $P(T^-) = (0.01 \times 0.005) + (0.97 \times 0.995) = 0.00005 + 0.96515 = 0.9652$

核心觀念

本題考查**二階常係數齊次遞迴關係（Second-order Homogeneous Linear Recurrence Relation with Constant Coefficients）**的閉合形式（Closed-form Solution）求解。

相關定理與公式如下：

1. 特徵方程式（Characteristic Equation）：對於二階齊次遞迴關係 $a_n + c_1 a_{n-1} + c_2 a_{n-2} = 0$，其對應之特徵方程式為：
   $r^2 + c_1 r + c_2 = 0$
2. 相異實根之通解公式：若特徵方程式解得兩相異實根 $r_1, r_2$（即 $r_1 \neq r_2$），則該遞迴關係的一般通解為：
   $a_n = c_1 r_1^n + c_2 r_2^n$
   其中 $c_1, c_2$ 為待定常數。
3. 邊界條件求解：代入已知項（本題為 $a_3 = 344$ 與 $a_4 = 2400$）建立二元一次方程組，即可解出常數 $c_1, c_2$。

解題方法

Step 1：建立並求解特徵方程式

已知遞迴關係為：
$a_n - 6a_{n-1} - 7a_{n-2} = 0$

寫出對應之特徵方程式：
$r^2 - 6r - 7 = 0$

對特徵方程式進行因式分解：
$(r - 7)(r + 1) = 0$

解得特徵根：
$r_1 = 7, \quad r_2 = -1$

Step 2：寫出通解形式

由於特徵根為相異實根 $7$ 與 $-1$，故遞迴關係的通解結構為：
$a_n = c_1 \cdot 7^n + c_2 \cdot (-1)^n$

Step 3：代入邊界條件聯立求解 $c_1, c_2$

題目給定 $a_3 = 344$ 與 $a_4 = 2400$：

當 $n = 3$ 時：
$a_3 = c_1 \cdot 7^3 + c_2 \cdot (-1)^3 = 343 c_1 - c_2 = 344 \quad \text{--- (1)}$