108 年 國立成功大學電腦與通信工程研究所甲組《離散數學》

核心觀念

本題屬於離散數學中**機率論（Probability Theory）**的基本範疇，核心考點包含：

1. 樣本空間（Sample Space, $S$）：隨機試驗中所有可能結果所組成的集合。本題中每名新生兒的性別為獨立試驗，且生男（$B$）與生女（$G$）的機率均等（$P(B) = P(G) = \frac{1}{2}$）。
2. 古典機率模型（Classical Probability Model）：當樣本空間 $S$ 為有限集，且每個基本事件（Outcome）發生的機率皆相等時，事件 $A$ 發生的機率定義為：
   $P(A) = \frac{|A|}{|S|}$
   其中 $|A|$ 為事件 $A$ 的元素個數，$|S|$ 為樣本空間的元素總數。
3. 事件（Event）：樣本空間的子集（Subset），根據題目條件以集合形式（Set Notation）表示。

---

解題方法

依序針對題目所求進行列舉與機率計算：

1. 建立樣本空間 $S$：
   家庭中有 3 名子女，出生順序有先後之分（第一胎、第二胎、第三胎）。依乘法法則（Rule of Product），總可能結果數為 $2^3 = 8$ 種。以三元字串表示三名子女的性別序列，列舉出所有結果。

2. 描述事件並計算機率：

   • 小題 (b.i)：尋找性別序列中「恰好包含 1 個 $G$（及 2 個 $B$）」的所有元素組成集合 $E_1$，並計算其佔樣本空間的比例 $P(E_1) = \frac{|E_1|}{|S|}$。
   • 小題 (b.ii)：尋找性別序列中「包含至少 2 個 $G$（即 2 個 $G$ 或 3 個 $G$）」的所有元素組成集合 $E_2$，並計算其佔樣本空間的比例 $P(E_2) = \frac{|E_2|}{|S|}$。

---

小題分析與推導

a. 定義樣本空間（Sample Space）

設 $B$ 表示男孩（Boy），$G$ 表示女孩（Girl）。按出生順序（第一胎、第二胎、第三胎）列舉所有可能的性別組合，樣本空間 $S$ 為：
$S = \{BBB, BBG, BGB, BGG, GBB, GBG, GGB, GGG\}$
樣本空間的大小為 $|S| = 8$。因生男與生女機率均等，此 8 種結果發生的機率皆為 $\left(\frac{1}{2}\right)^3 = \frac{1}{8}$，滿足均等機率假設。

b.i. 恰好有一名女孩的事件與機率（Exactly one child is a girl）

• 集合表示：在樣本空間 $S$ 中，恰含有 1 個字母 $G$ 的元素為第一胎為女（$GBB$）、第二胎為女（$BGB$）、第三胎為女（$BBG$）。設此事件為 $E_1$，則：

核心觀念

1. 離散隨機變數與期望值（Expected Value）：
   若離散隨機變數 $X$ 的可能取值為 $x_1, x_2, \dots, x_k$，對應機率分別為 $P(X = x_i)$，則 $X$ 的期望值定義為：
   $E[X] = \sum_{i=1}^{k} x_i \cdot P(X = x_i)$

2. 期望值的線性性質（Linearity of Expectation）：
   對於任意隨機變數 $X_1, X_2, \dots, X_n$（無論彼此是否獨立），總和的期望值等於各隨機變數期望值的總和：
   $E\left[\sum_{i=1}^{n} X_i\right] = \sum_{i=1}^{n} E[X_i]$
   當試驗為重複且同分布時，總得分期望值等於「單題期望值 $\times$ 總題數」。

---

解題方法

設考試總題數 $n = 10$。令離散隨機變數 $X_i$ 表示學生在第 $i$ 題（$i = 1, 2, \dots, 10$）所得的分數。
依據題意，單題計分規則如下：

• 答對：$X_i = +1$
• 答錯：$X_i = -1$
• 未作答：$X_i = 0$

學生試卷的總得分為隨機變數 $X = \sum_{i=1}^{10} X_i$。
由期望值的線性性質，總得分期望值可表示為：
$E[X] = E\left[ \sum_{i=1}^{10} X_i \right] = \sum_{i=1}^{10} E[X_i]$

a. 完全隨機猜測情況

• 題目條件：學生不知道答案，每題皆進行隨機猜測。
• 機率分布：是非題的選項只有「對」與「錯」兩種。隨機猜測時，答對與答錯的機率皆為 $0.5$，且每題皆作答（$P(X_i = 0) = 0$）。
  • $P(X_i = +1) = 0.5$
  • $P(X_i = -1) = 0.5$
• 單題得分期望值：
  $E[X_i] = (+1) \times 0.5 + (-1) \times 0.5 = 0.5 - 0.5 = 0$
• 總得分期望值：
  $E[X] = \sum_{i=1}^{10} E[X_i] = 10 \times 0 = 0$

b. 具 70% 信心度情況

• 題目條件：學生對每題答案有 $70\%$ 的信心度，且每題皆填寫答案。
• 機率分布：信心度 $70\%$ 表示學生答對該題的機率為 $0.7$，答錯的機率為 $1 - 0.7 = 0.3$。
  • $P(X_i = +1) = 0.7$

核心觀念

本題考查**命題邏輯（Propositional Logic）**的符號化與邏輯推論法則。解題時需運用以下定義與定理：

1. 條件句與逆否命題（Contrapositive）：
   $P \rightarrow Q \equiv \neg Q \rightarrow \neg P$
2. 否定後項律（Modus Tollens）：
   若已知 $P \rightarrow Q$ 且已知 $\neg Q$，可推導出 $\neg P$。
3. 德摩根定律（De Morgan's Laws）：
   $\neg (P \lor Q) \equiv \neg P \land \neg Q$
4. 簡化律（Simplification）：
   由 $P \land Q$ 可推導出單一命題 $P$（亦可導出 $Q$）。

---

解題方法

步驟一：命題符號化

定義下列邏輯變數：

• $A$：A 遲到（A is late）
• $B$：B 遲到（B is late）
• $C$：這堂課很無聊（The class is boring）

依據題目給定的三個已知前提（Premises）：

1. 前提一：若 A 遲到，則 B 遲到。
   $A \rightarrow B$
2. 前提二：若 A 或 B 遲到，則這堂課很無聊。
   $(A \lor B) \rightarrow C$
3. 前提三：這堂課不無聊。
   $\neg C$

步驟二：邏輯推導過程

1. 由前提二 $(A \lor B) \rightarrow C$ 與前提三 $\neg C$，套用否定後項律（Modus Tollens），可得：
   $\neg (A \lor B)$
2. 對 $\neg (A \lor B)$ 套用德摩根定律（De Morgan's Laws），可得：
   $\neg A \land \neg B$
3. 對 $\neg A \land \neg B$ 套用簡化律（Simplification），可單獨導出：
   $\neg A$
   （同理亦可導出 $\neg B$）

核心觀念

1. 奇同位 (Odd Parity) 定義：
   在數位邏輯與資料傳輸中，同位元 (Parity Bit) 用於基礎的錯誤檢測。奇同位要求包含同位位元在內的所有傳輸位元中，「1 的總個數」必須保持為奇數 (Odd)。
2. 互斥或 (XOR) 與同或 (XNOR) 運算特性：
   • 互斥或閘 (XOR, $\oplus$) 具備奇態檢測 (Odd Function) 特性。多輸入 XOR 運算結果為 $1$ 當且僅當輸入中「$1$ 的總個數為奇數」。
   • 同或閘 (XNOR, $\odot$) 為 XOR 的反相輸出（即加邏輯非 NOT）。多輸入 XNOR 運算結果為 $1$ 當且僅當輸入中「$1$ 的總個數為偶數」。
3. 同位產生器與檢查器的功能分工：
   • 四位元奇同位產生器 (Four-Bit Odd Parity Generator)：傳輸端根據 3 個資料位元 $(x, y, z)$ 產生 1 個同位位元 $P$，組合形成長度為 4 位元的奇同位碼 $(x, y, z, P)$。
   • 五位元奇同位檢查器 (Five-Bit Odd Parity Checker)：接收端接收 5 位元碼 $(A, B, C, D, E)$，檢測該 5 位元資料是否滿足奇同位規則，並輸出錯誤指示訊號。

---

解題方法

一、 四位元 $(x, y, z)$ 奇同位產生器設計

1. 邏輯函數推導：
   設 3 位元資料為 $x, y, z$，生成的同位位元為 $P$。為了保證組合碼 $(x, y, z, P)$ 中 1 的個數為奇數，四個位元的 XOR 運算結果必須為 $1$：
   $x \oplus y \oplus z \oplus P = 1$
   將等式兩邊同時與 $(x \oplus y \oplus z)$ 進行 XOR 運算，可得同位位元 $P$ 的布林表達式：
   $P = (x \oplus y \oplus z)' = x \odot y \odot z$

2. 真值表 (Truth Table)：

   $x$	$y$	$z$	$x \oplus y \oplus z$	同位位元 $P = (x \oplus y \oplus z)'$	傳輸碼 $(x, y, z, P)$ 中 1 的總個數
   0	0	0	0	1	1 (奇數)
   0	0	1	1	0	1 (奇數)
   0	1	0	1	0	1 (奇數)
   0	1	1	0	1	3 (奇數)
   1	0	0	1	0	1 (奇數)
   1	0	1	0	1	3 (奇數)
   1	1	0	0	1	3 (奇數)
   1	1	1	1	0	3 (奇數)

3. 邏輯電路實作：

   • 布林表達式：$P = ((x \oplus y) \oplus z)'$
   • 電路結構：先將輸入 $x$ 與 $y$ 接至第一個 2-input XOR 閘，其輸出再與輸入 $z$ 一起接至一個 2-input XNOR 閘（或 XOR 閘串接 NOT 閘），輸出即為同位位元 $P$。

---

二、 五位元奇同位檢查器設計

1. 邏輯函數推導：
   設接收端接收到的 5 位元資料為 $A, B, C, D, E$。
   若資料傳輸正常（無錯誤），5 位元中 1 的總個數應為奇數，即：
   $A \oplus B \oplus C \oplus D \oplus E = 1$
   定義錯誤檢測輸出旗標 $E_{err}$（$E_{err} = 1$ 表示發生傳輸錯誤；$E_{err} = 0$ 表示傳輸無誤）：

   • 當 1 的個數為偶數時，代表發生單數個位元錯誤，此時 $E_{err} = 1$。
   • 當 1 的個數為奇數時，代表資料符合規格，此時 $E_{err} = 0$。

   因此錯誤指示輸出的布林表達式為：
   $E_{err} = (A \oplus B \oplus C \oplus D \oplus E)'$
   （若定義有效旗標 $V = 1$ 表示資料正確，則 $V = A \oplus B \oplus C \oplus D \oplus E$）。

2. 電路樹狀結構 (Tree Architecture)：
   為降低閘延遲 (Gate Delay)，採用二元樹 (Binary Tree) 結構實作 5 輸入運算：

核心觀念

本題考查冪集上的包含關係所形成的偏序集合，以及 Hasse diagram 的繪製方法。

集合

$$S=\{1,2,3\}$$

的冪集為

$$P(S)=\{\varnothing,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}.$$

偏序關係為集合包含關係 $\subseteq$。在此偏序中：

• $\varnothing$ 是最小元素；
• $\{1,2,3\}$ 是最大元素；
• 集合元素個數越多，通常位於越上層。

Hasse diagram 不畫出所有包含關係，只畫「覆蓋關係」。若 $A\subset B$，且不存在集合 $C$ 使得

$$A\subset C\subset B,$$

則稱 $B$ 覆蓋 $A$，記作 $A\prec B$。

對冪集而言，覆蓋關係的判斷方式是：

$$A\prec B \quad\Longleftrightarrow\quad A\subset B,\ |B|=|A|+1.$$

也就是由下層集合增加恰好一個元素即可到達上層集合。

---

解題方法

先依照集合基數分層：

$$\begin{array}{c} \text{第 3 層：}\{1,2,3\}\\[4pt] \text{第 2 層：}\{1,2\},\{1,3\},\{2,3\}\\[4pt] \text{第 1 層：}\{1\},\{2\},\{3\}\\[4pt] \text{第 0 層：}\varnothing \end{array}$$

接著只連接相鄰層中具有包含關係的集合。

1. $\varnothing$ 覆蓋三個單元素集合：

$$\varnothing\prec\{1\},\qquad \varnothing\prec\{2\},\qquad \varnothing\prec\{3\}.$$

2. 單元素集合與雙元素集合之間的覆蓋關係為：

$$\{1\}\prec\{1,2\},\qquad \{1\}\prec\{1,3\},$$ $$\{2\}\prec\{1,2\},\qquad \{2\}\prec\{2,3\},$$ $$\{3\}\prec\{1,3\},\qquad \{3\}\prec\{2,3\}.$$

3. 三個雙元素集合皆被 $\{1,2,3\}$ 覆蓋：

核心觀念

Bubble Sort（泡沫排序法）反覆比較相鄰元素：

• 若左側元素大於右側元素，便交換兩者。
• 每完成一輪掃描，尚未排序部分的最大值會被推到最右端。
• 第 $i$ 輪完成後，最右側已有 $i$ 個元素定位完成。

標準升冪排序的核心概念是「相鄰比較與交換」。

---

解題方法

以資料

$$[5,4,2,1,3]$$

進行升冪排序。每一輪都由左至右比較相鄰元素。

第 1 輪

依序比較：

1. 比較 $5$ 與 $4$：

$$[5,4,2,1,3]\rightarrow[4,5,2,1,3]$$

2. 比較 $5$ 與 $2$：

$$[4,5,2,1,3]\rightarrow[4,2,5,1,3]$$

3. 比較 $5$ 與 $1$：

$$[4,2,5,1,3]\rightarrow[4,2,1,5,3]$$

4. 比較 $5$ 與 $3$：

$$[4,2,1,5,3]\rightarrow[4,2,1,3,5]$$

第 1 輪結束：

$$[4,2,1,3,5]$$

最大值 $5$ 已移至最右端。

第 2 輪

最右側的 $5$ 已排序，因此只需處理前四個元素：

1. $4>2$，交換：

$$[4,2,1,3,5]\rightarrow[2,4,1,3,5]$$

2. $4>1$，交換：

$$[2,4,1,3,5]\rightarrow[2,1,4,3,5]$$

3. $4>3$，交換：

$$[2,1,4,3,5]\rightarrow[2,1,3,4,5]$$

第 2 輪結束：

$$[2,1,3,4,5]$$

第 3 輪

只需處理前面三個尚未固定的元素：

1. $2>1$，交換：

$$[2,1,3,4,5]\rightarrow[1,2,3,4,5]$$

2. 比較 $2$ 與 $3$，不交換。
3. 比較 $3$ 與 $4$，不交換。

第 3 輪結束：

$$[1,2,3,4,5]$$

第 4 輪

比較剩餘的相鄰元素 $1$ 與 $2$，順序正確，不交換。

核心觀念

題目給定的 Merge() 函式，前提是兩個輸入序列已經分別排序：

$$y_1\le y_2\le\cdots\le y_l,\qquad z_1\le z_2\le\cdots\le z_m$$

Merge() 每次比較兩個序列目前最前面的元素，將較小者放入輸出序列，因此可在 $\Theta(l+m)$ 時間內合併成一個排序序列。

MergeSort() 採用分治法：

1. 將序列分成左右兩半。
2. 遞迴排序左右兩半。
3. 使用題目給定的 Merge() 合併兩個已排序序列。

解題方法

設目前要排序的範圍為 $A[left..right]$，中點為

$$mid=\left\lfloor\frac{left+right}{2}\right\rfloor$$

當範圍內只有一個元素時，序列本身已經排序完成。否則分別排序：

$$A[left..mid],\qquad A[mid+1..right]$$

再將兩個排序結果交給 Merge() 合併。

MergeSort 函式

function MergeSort(A[1..n])
    MergeSortRange(A, 1, n)
    return A


function MergeSortRange(A, left, right)
    if left >= right then
        return

    mid ← floor((left + right) / 2)

    MergeSortRange(A, left, mid)
    MergeSortRange(A, mid + 1, right)

    C ← Merge(A[left..mid], A[mid+1..right])

    for t ← 1 to right - left + 1 do
        A[left + t - 1] ← C[t]