大一上離散數學

1. 命題邏輯與等價關係 (Propositional Logic)#

觀念與公式

直觀意義： 命題就像是一個開關，只能是「絕對的真 (True)」或「絕對的假 (False)」，不能模稜兩可。當我們用邏輯運算子（如 AND, OR, NOT）把多個命題串起來時，就像是在設計電路，透過真值表可以窮舉所有可能的結果。

必背公式與定律：

• 條件語句 (Conditional Statement): $p \rightarrow q \equiv \neg p \vee q$
• 雙條件語句 (Bi-conditional Statement): $p \leftrightarrow q \equiv (p \rightarrow q) \wedge (q \rightarrow p)$
• 笛摩根定律 (De Morgan’s Laws): $\neg (p \vee q) \equiv \neg p \wedge \neg q$ 以及 $\neg (p \wedge q) \equiv \neg p \vee \neg q$
• 逆反命題 (Contrapositive): $p \rightarrow q \equiv \neg q \rightarrow \neg p$

實戰演練（題型大全）

【題型一：基本真值表判斷】（常考頻率：高）

題目： 證明 $(p \wedge q) \rightarrow (p \vee q)$ 是一個恆真句 (Tautology)。

Step-by-step 解答：

1. 將條件語句轉換為 OR 形式：$\neg(p \wedge q) \vee (p \vee q)$ (透過 $p \rightarrow q \equiv \neg p \vee q$)。
2. 套用笛摩根定律：$(\neg p \vee \neg q) \vee (p \vee q)$。
3. 使用結合律與交換律重新分組：$(\neg p \vee p) \vee (\neg q \vee q)$。
4. 套用否定律：$T_0 \vee T_0 \equiv T_0$ (恆真)。

【題型二：邏輯推理謎題】（重要程度：中）

題目： 在一個島上有兩種人：一種只說真話，一種只說謊話。你遇到 A 和 B 兩人。A 說：「B 總是說真話。」B 說：「我們是不同種類的人。」請問 A 和 B 分別是哪種人？

Step-by-step 解答：

1. 假設 A 是說真話的人，那麼 B 也必須是說真話的人。
2. 如果 B 也是說真話的人，B 說的「我們是不同種類的人」就變成假話，這與前提矛盾。
3. 因此 A 必然是說謊話的人。
4. 既然 A 說謊，A 說「B 說真話」是假的，代表 B 實際上也是說謊話的人。
5. B 說「我們是不同種類的人」是謊話，符合兩人都說謊（同種類）的事實。結論：兩人皆為說謊者。

2. 述詞與量詞 (Predicate Calculus)#

觀念與公式

直觀意義： 述詞就像是一個「填空題」$P(x)$，單看述詞並不知道真假；而量詞則是規定了「範圍」。全稱量詞 ($\forall$) 代表「每一個都要滿足條件」，存在量詞 ($\exists$) 代表「只要找到一個符合的即可」。

必背公式與定律：

• 量詞的笛摩根定律: $\neg \forall x P(x) \equiv \exists x \neg P(x)$ 以及 $\neg \exists x P(x) \equiv \forall x \neg P(x)$

實戰演練（題型大全）

【題型一：量詞真偽判斷與反例】（常考頻率：高）

題目： 判斷 $\forall x (x^2 \ge x)$ 在不同論域 (Domain) 下的真偽：(a) 所有實數 (b) 所有整數。

Step-by-step 解答：

1. (a) 在實數領域中為 False。反例 (counter-example)：取 $x = 0.5$，$0.5^2 = 0.25$，並不 $\ge 0.5$。
2. (b) 在整數領域中為 True。因為 $x^2 \ge x \Leftrightarrow x(x-1) \ge 0 \Leftrightarrow x \le 0$ 或 $x \ge 1$。在整數中，不存在 $0 < x < 1$ 的數字，故永遠成立。

【題型二：日常語句翻譯成邏輯符號】（常考頻率：極高）

題目： 將「每個人都恰好有一個最要好的朋友」轉換為邏輯表示式。令 $B(x, y)$ 為「$y$ 是 $x$ 的最要好朋友」。

Step-by-step 解答：

1. 「每個人 $x$」：$\forall x$。
2. 「存在一個朋友 $y$」：$\exists y$。
3. 「恰好只有這一個 $y$」：除了 $y$ 之外的任何 $z$，如果也是好朋友，那麼 $z$ 必定等於 $y$。
4. 結合上述條件，推導邏輯表示法：$\forall x \exists y (B(x,y) \wedge \forall z (B(x,z) \rightarrow z=y))$。

3. 推理規則 (Rules of Inference)#

觀念與公式

直觀意義： 這是偵探辦案的標準流程。如果我們知道某些前提（線索）為真，就可以按照特定的套路（規則）推導出新的結論。最常用的招式是「若 A 則 B，現在 A 發生了，所以 B 一定會發生」。

必背公式與定律：

• Modus Ponens (肯定前件): $p, p \rightarrow q \vdash q$
• Modus Tollens (否定後件): $\neg q, p \rightarrow q \vdash \neg p$
• Hypothetical Syllogism (三段論): $p \rightarrow q, q \rightarrow r \vdash p \rightarrow r$
• Disjunctive Syllogism (選言三段論): $\neg p, p \vee q \vdash q$

實戰演練（題型大全）

【題型一：複合邏輯推理證明】（重要程度：高）

題目： 已知前提：(1) 如果你寄電子郵件給我，我就會寫完程式。(2) 如果你沒寄電子郵件給我，我就會早點睡覺。(3) 如果我早點睡覺，我就會神清氣爽地醒來。請證明結論：「如果我沒寫完程式，我就會神清氣爽地醒來」。

Step-by-step 解答：

1. 定義變數：$p$ = 你寄信、$q$ = 我寫完程式、$r$ = 我早睡、$s$ = 我神清氣爽。
2. 前提列式：$p \rightarrow q$, $\neg p \rightarrow r$, $r \rightarrow s$。目標結論：$\neg q \rightarrow s$。
3. 利用 $p \rightarrow q$ 的逆反命題：$\neg q \rightarrow \neg p$。
4. 利用假言三段論結合 $\neg q \rightarrow \neg p$ 與 $\neg p \rightarrow r$：得出 $\neg q \rightarrow r$。
5. 利用假言三段論結合 $\neg q \rightarrow r$ 與 $r \rightarrow s$：得出 $\neg q \rightarrow s$，證明完畢。

4. 證明方法與策略 (Methods of Proving)#

觀念與公式

直觀意義： 面對數學命題的攻擊策略。「直接證明」是正面直拳擊破；「反證法 (Contradiction)」是先假裝對手是對的，然後找出邏輯漏洞自相矛盾；「對偶證明 (Contraposition)」則是閃避正面，從背後（否定結論）攻擊。

實戰演練（題型大全）

【題型一：對偶證明法 Contraposition】（常考頻率：高）

題目： 證明：如果 $3n+2$ 是奇數，則 $n$ 是奇數。

Step-by-step 解答：

1. 假設結論的反面：$n$ 是偶數。
2. 這表示存在某個整數 $k$ 使得 $n = 2k$。
3. 代入原式：$3n+2 = 3(2k)+2 = 6k+2 = 2(3k+1)$。
4. 因為 $2(3k+1)$ 必定是偶數，代表 $3n+2$ 是偶數。因為結論的否定推導出前提的否定，故原命題成立。

【題型二：反證法 Contradiction】（常考頻率：極高）

題目： 證明 $\sqrt{2}$ 是無理數。

Step-by-step 解答：

1. 假設 $\sqrt{2}$ 是有理數，則它可以表示為兩個最簡整數比 $a/b$ ($b \neq 0$，且 $a,b$ 互質)。
2. 平方得到 $2 = a^2 / b^2$，移項得 $a^2 = 2b^2$。這代表 $a^2$ 是偶數，推導出 $a$ 也必須是偶數。
3. 令 $a = 2c$，代回得 $(2c)^2 = 2b^2 \Rightarrow 4c^2 = 2b^2 \Rightarrow b^2 = 2c^2$。
4. 這代表 $b^2$ 是偶數，推導出 $b$ 也是偶數。
5. 若 $a, b$ 皆為偶數，它們有公因數 2，與前提「最簡整數比」矛盾！故假設錯誤，$\sqrt{2}$ 必為無理數。

【題型三：無效證明與邏輯謬誤】（重要程度：高）

題目： 找出證明 $1=2$ 的謬誤。證明步驟為：$a=b \Rightarrow a^2=ab \Rightarrow a^2-b^2=ab-b^2 \Rightarrow (a-b)(a+b)=b(a-b) \Rightarrow a+b=b \Rightarrow 2b=b \Rightarrow 2=1$。

Step-by-step 解答：

1. 錯誤發生在 $(a-b)(a+b)=b(a-b)$ 轉換到 $a+b=b$ 的這一步。
2. 因為我們初始假設 $a=b$，所以 $(a-b) = 0$。
3. 在等式兩邊同除以 $(a-b)$ 等同於「除以 0」，這在數學上是不允許且無效的操作。

5. 數學歸納法 (Mathematical Induction)#

觀念與公式

直觀意義： 推骨牌效應。你要確保第一張骨牌會倒 (Basic Step, 基礎步 $P(1)$)，並且證明「只要第 $k$ 張骨牌倒下，就一定能推倒第 $k+1$ 張」(Inductive Step, 歸納步 $P(k) \rightarrow P(k+1)$)。全部成立後，所有骨牌都會倒下。

必背公式與定律：

• 標準歸納法核心： $P(1) \wedge \forall k (P(k) \rightarrow P(k+1)) \Rightarrow \forall n P(n)$
• 強歸納法核心： $\forall n ((P(1) \wedge P(2) \wedge ... \wedge P(n)) \rightarrow P(n+1))$

實戰演練（題型大全）

【題型一：數列總和證明】（常考頻率：極高）

題目： 證明前 $n$ 個正奇數的總和為 $n^2$。

Step-by-step 解答：

1. 基礎步 (Basic Step)： 當 $n=1$ 時，前 1 個正奇數為 1，其總和等於 $1^2 = 1$，成立。
2. 歸納步 (Inductive Step)： 假設 $P(k)$ 為真，即 $1+3+...+(2k-1) = k^2$。
3. 我們要證明 $P(k+1)$ 也為真。將 $P(k)$ 加上下一個奇數 $(2k+1)$：$1+3+...+(2k-1)+(2k+1) = k^2 + (2k+1)$。
4. 化簡等式右邊：$k^2 + 2k + 1 = (k+1)^2$。故得證。

【題型二：歸納法的經典錯誤】（常考頻率：中）

題目： 證明所有貓的顏色都一樣 ($P(n)$ = 任意 $n$ 隻貓顏色相同)。假設 $P(k)$ 成立，當有 $k+1$ 隻貓時，移走其中一隻 $y$，剩下的 $k$ 隻貓顏色一樣。再把 $y$ 換回來並移走另一隻貓，剩下的 $k$ 隻貓顏色也一樣，因此所有貓顏色一樣。這個證明哪裡錯了？

Step-by-step 解答：

1. 這個證明的漏洞在於歸納步從 $P(1)$ 推向 $P(2)$ 時失效。
2. 當 $k+1 = 2$ 隻貓時，移走一隻貓 $y$，剩下 1 隻貓 (顏色當然自己跟自己一樣)。
3. 但當你把 $y$ 換回來並移走另一隻時，這「兩組」剩下的貓（各只有一隻）之間，完全沒有交集 (Overlap) 的貓可以作為顏色相同的橋樑。
4. 推論中斷，歸納失敗。

6. 鴿籠原理 (Pigeonhole Principle)#

觀念與公式

直觀意義： 如果你有 10 隻鴿子，但只有 9 個籠子，晚上鴿子回籠時，絕對「至少有一個籠子會擠兩隻以上的鴿子」。

必背公式與定律：

• 廣義鴿籠原理 (Generalized Pigeonhole Principle): 若將 $N$ 個物件放入 $k$ 個箱子中，至少會有一個箱子包含 $\lceil N/k \rceil$ 個（或以上）的物件。

實戰演練（題型大全）

【題型一：同月出生問題】（常考頻率：高）

題目： 證明在 80 位以上的學生中，至少有 7 人在同一個月份出生。

Step-by-step 解答：

1. 將「學生」當作鴿子 ($N = 80$)，將「月份」當作籠子 ($k = 12$)。
2. 套用廣義鴿籠原理公式：$\lceil N/k \rceil = \lceil 80 / 12 \rceil$。
3. $80 / 12 = 6.66...$，無條件進位得到 7。
4. 因此至少有 7 人在同一個月出生，證明完畢。

【題型二：棋盤上的城堡問題】（常考頻率：中）

題目： 證明若將 33 個城堡 (Rooks) 放在標準 $8\times8$ 棋盤上，至少有 5 個城堡無法互相攻擊。

Step-by-step 解答：

1. 城堡的攻擊模式為同行或同列。我們可以在棋盤上標記數字來建立「不互攻」的集合。
2. 將棋盤劃分成對角線位移的標記區塊（例如對角線依序標上 1~8），同一數字的格子絕不會處於同行或同列。這產生了 8 個彼此獨立的箱子 ($k=8$)。
3. 共有 33 個城堡 ($N=33$)。
4. 根據鴿籠原理：$\lceil 33 / 8 \rceil = \lceil 4.125 \rceil = 5$。至少有 5 個城堡落在同一個標記區域，它們必定無法互相攻擊。

⚠️ 第一章考前避坑指南#

1. 命題邏輯的陷阱： 絕對不要把條件語句 $p \rightarrow q$ 和它的逆命題 (Converse) $q \rightarrow p$ 搞混，兩者的真值完全不相等！
2. 量詞的轄域 (Scope) 盲點： 使用全稱或存在量詞時，必須非常明確定義「論域 (Domain)」。同一個命題在整數論域為 True，在實數論域可能就是 False。
3. 歸納法的虛假安全感： 不要因為 $P(1)$ 成立，且代了 $P(2), P(3)$ 發現好像對了，就直接下結論。歸納法的靈魂在於嚴謹推導 $P(k) \rightarrow P(k+1)$，且必須注意前後集合重疊的盲點（如前述貓咪顏色的謬誤）。
4. 證明的除零謬誤： 使用直接證明法操作等式時，要相消或除以代數，務必檢查該代數是否為 0，否則會推導出 $1=2$ 的荒謬結論。

1. 加法與乘法原理 (Rule of Sum & Product)#

觀念與公式： 計數的最底層邏輯在於事件是否獨立與互斥。這如同在 AtCoder 或 Codeforces 等平台上分析演算法時，並列的迴圈時間複雜度相加，而巢狀迴圈的時間複雜度則相乘。

• 加法原理 (Rule of Sum)：處理「互斥事件」（OR 邏輯）。若事件 A 有 $m$ 種方法，事件 B 有 $n$ 種方法，兩者不能同時發生，則總方法數為 $m + n$。
• 乘法原理 (Rule of Product)：處理「連續或獨立事件」（AND 邏輯）。若事件 A 有 $m$ 種方法，接著事件 B 有 $n$ 種方法，則總方法數為 $m \times n$。

實戰演練（題型大全）：

【題型一：因數個數計算】（常考頻率：高）

題目：請問 1400 共有多少個正因數？

Step-by-step 解答：

1. 進行質因數分解：$1400 = 2^3 \times 5^2 \times 7$。
2. 每個質因數的次方數加 1 後相乘（代表取 0 次到最大次方的選擇）：$(3+1) \times (2+1) \times (1+1) = 24$ 個因數。

【題型二：多類別物件選擇】（常考頻率：中）

題目：有 5 本中文書、7 本英文書、10 本法文書，要從中挑選兩本「不同語言」的書，有幾種選法？

Step-by-step 解答：

1. 分為三種互斥情況：中英、中法、英法。
2. 應用乘法與加法原理：$5 \times 7 + 5 \times 10 + 7 \times 10 = 155$ 種。

2. 排斥原理與樹狀圖 (Inclusion-Exclusion & Tree Diagrams)#

觀念與公式：

• 排斥原理 (Principle of Inclusion-Exclusion)：當計算兩組事件的方法數時，為避免重複計算交集的部分，必須將其扣除。公式為 $|A \cup B| = |A| + |B| - |A \cap B|$。
• 樹狀圖 (Tree Diagrams)：適合用來窮舉並視覺化有條件限制的連續選擇，類似演算法中的深度優先搜尋 (DFS) 遍歷狀態樹。

實戰演練（題型大全）：

【題型一：字串條件聯集】（常考頻率：極高）

題目：長度為 8 的位元字串中，有多少個是「以 1 開頭」或「以 00 結尾」？

Step-by-step 解答：

1. 以 1 開頭的字串數：剩下的 7 個位元可任意填，共 $2^7 = 128$ 種。
2. 以 00 結尾的字串數：前面的 6 個位元可任意填，共 $2^6 = 64$ 種。
3. 同時以 1 開頭且以 00 結尾的字串數：中間 5 個位元可任意填，共 $2^5 = 32$ 種。
4. 總數 $= 128 + 64 - 32 = 160$ 種。

【題型二：反向扣除法】（常考頻率：高）

題目：350 位求職者中，220 位主修 CS，147 位主修商業，51 位雙主修 CS 與商業。請問有多少位「既沒有主修 CS 也沒有主修商業」？

Step-by-step 解答：

1. 先算出有主修其中至少一項的人數：$220 + 147 - 51 = 316$。
2. 總人數扣除上述人數：$350 - 316 = 34$ 位。

3. 排列與組合 (Permutations and Combinations)#

觀念與公式：

• 排列 (Permutation)：從 $n$ 個相異物件中選出 $r$ 個並考慮順序。公式：$P(n,r) = \frac{n!}{(n-r)!}$。
• 組合 (Combination)：從 $n$ 個相異物件中選出 $r$ 個，不考慮順序。公式：$C(n,r) = \frac{n!}{r!(n-r)!}$。
• 核心關聯：$P(n,r) = P(r,r) \times C(n,r)$。

實戰演練（題型大全）：

【題型一：不可區分物件排列（同物排列）】（常考頻率：極高）

題目：重新排列單字 “SUCCESS” 的字母，能產生多少種不同的字串？

Step-by-step 解答：

1. “SUCCESS” 共 7 個字母，若全相異則有 $7!$ 種排列。
2. 處理不可區分的物件：其中有 2 個 ‘C’ 和 3 個 ‘S’ 是不可區分的。
3. 根據公式 $\frac{n!}{n_1! n_2! ... n_k!}$，答案為 $\frac{7!}{2!3!}$ 種。

4. 重複組合與隔板法 (Combinations with Repetitions)#

觀念與公式： 當從 $n$ 種不同的物件中選出 $r$ 個，且不考慮順序、每種物件有無限供應時，此即為重複組合。

• 隔板法 (Stars and Bars)：等價於從 $(n-1+r)$ 個位置中選出 $r$ 個位置放球，即 $C(n-1+r, r)$。

實戰演練（題型大全）：

【題型一：方程式非負整數解】（常考頻率：極高）

題目：方程式 $x+y+z=11$ 中，若 $x, y, z$ 皆為非負整數，共有幾組解？

Step-by-step 解答：

1. 將 11 視為 $r=11$ 顆相同的球，變數 $x, y, z$ 視為 $n=3$ 個不同的箱子。
2. 代入隔板法公式 $C(n-1+r, r) = C(3-1+11, 11) = C(13, 11)$ 組解。

5. 經典恆等式與二項式定理 (Identities and Binomial Theorem)#

觀念與公式：

• Pascal 恆等式：$C(n,r) = C(n-1, r) + C(n-1, r-1)$。
• 二項式定理：$(x+y)^n = \sum_{r=0}^n C(n,r) x^{n-r} y^r$。
• Vandermonde 恆等式：$C(m+n, r) = \sum_{k=0}^r C(m, r-k) C(n, k)$。

實戰演練（題型大全）：

【題型一：利用 Vandermonde 簡化級數】（常考頻率：高）

題目：化簡 $\sum_{k=0}^n C(n,k)^2$。

Step-by-step 解答：

1. 將平方拆解，並利用組合對稱性：$\sum_{k=0}^n C(n,k)^2 = \sum_{k=0}^n C(n,n-k)C(n,k)$。
2. 對照 Vandermonde 恆等式，令 $m=n$、$r=n$，即可將原式化簡為 $C(2n, n)$。

⚠️ 第二章考前避坑指南#

1. 「排列」與「組合」的誤用：看見題目先問自己「順序互換是否代表不同結果？」，若不影響絕對是組合 ($C$)。
2. 同物排列忘記除掉階乘：計算密碼或字串時，若出現相同的字元，最後總排列數務必除以重複字元個數的階乘。
3. 「至少」題型未用反向扣除：題目若出現「至少包含一個」這類字眼，正面窮舉極易遺漏情況，請立刻切換為「全部情況 $-$ 完全沒有的情況」。

1. 集合論、勢與排容原理 (Sets, Cardinality & Inclusion-Exclusion)#

觀念與公式： 集合（Set）是無序的物件集合，在資訊工程中，無論是資料庫查詢還是演算法的狀態空間，皆建立在集合操作之上。

• 冪集 (Power Set)： 集合 $A$ 的所有子集所構成的集合 $2^A$。若 $|A| = n$，則 $|2^A| = 2^n$。
• 排容原理推廣： 用於精準計算聯集大小。奇數個集合的交集為正號，偶數個集合的交集為負號。

實戰演練（題型大全）：

【題型一：排容原理應用】

題目： 請問在 1 到 250 之間的整數中，有多少個數字可以被 2, 3, 5, 或 7 整除？

Step-by-step 解答：

1. 定義 $A_2, A_3, A_5, A_7$ 分別為 1 到 250 之間能被 2, 3, 5, 7 整除的集合。
2. 計算單一集合大小：$|A_2| = \lfloor 250/2 \rfloor = 125$，$|A_3| = 83$，$|A_5| = 50$，$|A_7| = 35$。
3. 計算兩兩交集（取最小公倍數）：$|A_2 \cap A_3| = \lfloor 250/6 \rfloor = 41$，依序計算出所有 $C^4_2 = 6$ 種組合。
4. 計算三個交集：$|A_2 \cap A_3 \cap A_5| = \lfloor 250/30 \rfloor = 8$，依序計算出所有 $C^4_3 = 4$ 種組合。
5. 計算四個交集：$|A_2 \cap A_3 \cap A_5 \cap A_7| = \lfloor 250/210 \rfloor = 1$。
6. 套用公式：$(125+83+50+35) - (41+25+17+16+11+7) + (8+5+3+2) - 1 = 193$。

2. 函數映射與高斯符號 (Functions, Floor & Ceiling)#

觀念與公式：

• 核心映射關係：

• Injective (單射)： $f(a) = f(b) \implies a = b$。

• Surjective (滿射)： 對應域等於值域 (Range)。

• Bijective (雙射)： 同時滿足單射與滿射。

• 高斯符號運算定律 (已知 $n$ 為整數)：

• $\lfloor -x \rfloor = -\lceil x \rceil$

• $\lfloor x+n \rfloor = \lfloor x \rfloor + n$

• $\lceil x+y \rceil \neq \lceil x \rceil + \lceil y \rceil$

實戰演練（題型大全）：

【題型一：高斯符號的代數證明】

題目： 證明 $\lfloor 2x \rfloor = \lfloor x \rfloor + \lfloor x + 0.5 \rfloor$ 對所有實數 $x$ 皆成立。

Step-by-step 解答：

1. 令小數部分 $\{x\} = x - \lfloor x \rfloor$。
2. 左式 (LHS) $= \lfloor 2\lfloor x \rfloor + 2\{x\} \rfloor = 2\lfloor x \rfloor + \lfloor 2\{x\} \rfloor$。
3. Case 1： $0 \le \{x\} < 0.5 \implies 0 \le 2\{x\} < 1$。左式 $= 2\lfloor x \rfloor + 0$。右式 $= \lfloor x \rfloor + \lfloor x + 0.5 \rfloor = \lfloor x \rfloor + \lfloor x \rfloor = 2\lfloor x \rfloor$。左式 = 右式。
4. Case 2： $0.5 \le \{x\} < 1 \implies 1 \le 2\{x\} < 2$。左式 $= 2\lfloor x \rfloor + 1$。右式 $= \lfloor x \rfloor + (\lfloor x \rfloor + 1) = 2\lfloor x \rfloor + 1$。左式 = 右式。

3. 二元關係與遞移閉包 (Binary Relations & Closures)#

觀念與公式： 二元關係直接對應到有向圖的結構。

• 四大核心性質： 反身性 (Reflexive)、對稱性 (Symmetric)、反對稱性 (Antisymmetric)、遞移性 (Transitive)。 在離散數學中，二元關係（Binary Relation）如果定義在一個集合 $A$ 上，我們可以用有向圖（Directed Graph）來完美視覺化：

• 集合中的元素就是圖上的頂點（Vertices）。

• 如果元素 $a$ 和 $b$ 有關係（即 $(a, b) \in R$），就在圖上畫一條從 $a$ 指向 $b$ 的有向邊（Edge）。

4. 等價關係、偏序集與格 (Equivalence Relations, Posets & Lattices)#

觀念與公式：

• 等價關係： 同時具備反身性、對稱性、遞移性。它會將集合切割成數個互不相交的「等價類」。
• 偏序集 (Poset)： 同時具備反身性、反對稱性、遞移性。
• Hasse Diagram (哈斯圖)： 去除自環、省略遞移邊，統一朝上簡化的圖形。
• 格 (Lattice)： 在偏序集中，若任意兩元素都有唯一的「最小上界 (LUB)」與「最大下界 (GLB)」，則該偏序集稱為格。

實戰演練（題型大全）：

【題型一：Hasse Diagram 與格的判斷】

題目： 給定偏序集 $(\{1,2,3,4,6,8,12\}, |)$，其中 $|$ 代表整除關係。請建構 Hasse Diagram 並判斷它是否為 Lattice。

Step-by-step 解答：

1. 建構哈斯圖： 最底層放置 $1$。上一層放置 $2, 3$。再上一層放置 $4, 6$。最上層放置 $8, 12$。依照整除關係連線並隱藏遞移邊。
2. 尋找極端值： 極大值 (Maximal) 為頂端沒有對外連線的節點：$8, 12$。極小值 (Minimal) 為底端：$1$。
3. Lattice 判斷： 考慮點 $8$ 與 $12$。它們的 LUB 應該是 24，但在集合 $\{1,2,3,4,6,8,12\}$ 中不存在共同的上界，因此該偏序集不是格 (Lattice)。

⚠️ 第三章考前避坑指南#

1. 空集的陷阱： $\emptyset \subseteq A$ 永遠成立，但 $\emptyset \in A$ 不一定成立。務必分清「子集」與「元素」的符號差異。
2. 反對稱 $\neq$ 不對稱： Antisymmetric 絕對不是 Symmetric 的相反詞！一個關係可以同時是對稱且反對稱的。
3. 等價類互斥定律： 任意兩個等價類要嘛完全相等，要嘛交集為空，絕對不可能出現「部分重疊」的狀況。

1. 圖的基礎定義與術語 (Graph Basics & Terminology)#

2. 握手定理 (Handshaking Theorem)#

3. 特殊簡單圖與二分圖 (Special Simple Graphs & Bipartite Graphs)#

4. 尤拉路徑與迴路 (Euler Paths & Circuits)#

5. 漢密爾頓路徑與迴路 (Hamilton Paths & Circuits)#

6. 平面圖與尤拉公式 (Planar Graphs & Euler’s Formula)#

7. 庫拉托夫斯基定理與著色問題 (Kuratowski’s Theorem & Coloring)#

⚠️ 考前避坑指南 (Exam Pitfall Guide)#

1. Self-loop 的度數計算極易錯：當你手算總分支度或判定尤拉迴路時，如果圖中有一條自我環 (Loop)，該頂點的 Degree 要 $+2$，千萬不要只加 1。

2. 握手定理適用對象：無論無向圖還是有向圖，定理等式兩側的意涵不同。證明題中極愛考「奇數度頂點數量必為偶數」，這是從 $2m = \text{Even} + \text{Odd}$ 移項得來的觀念，必考倒扣。

3. 尤拉 vs 漢密爾頓 的判定邏輯差異：

• 尤拉迴路：看「邊」(Edges)。充要條件為「全為偶數度」。條件是「若且唯若 (iff)」，看到奇數點直接判死刑。

• 漢密爾頓迴路：看「頂點」(Vertices)。Dirac 和 Ore 定理只給了「充分條件 (Sufficient)」。如果題目給的圖不滿足這兩個定理（例如每個點度數都小於 $n/2$），不代表它沒有漢密爾頓迴路！(例如一個正方形 $C_4$，不滿足充分條件，但明明就有漢密爾頓迴路) 選擇題極容易在這邊埋陷阱，反推必錯。

4. 尤拉公式中的 Region 計算：在代入 $V + F = E + 2$ 運算或是看圖數區域時，永遠記得包含最外側的無限區域 (Infinite Region)，漏算 $F$ 就會少 1 導致公式不平。

5. 平面圖的不等式誤用：$E \le 3V - 6$ (或二分圖的 $E \le 2V - 4$) 只是平面圖的「必要條件 (Necessary)」。

• 若 $E > 3V - 6$，則必定「非平面圖」。
• 若 $E \le 3V - 6$，不能保證它是平面圖！如果要證明它是，請乖乖畫出來；如果要證明不是，請找庫拉托夫斯基的子圖 $K_5$ 或 $K_{3,3}$。

1. 樹的基礎性質與節點計算 (Properties of Trees)#

2. 決策樹 (Decision Trees) 與複雜度下界#

3. 最佳前綴碼與霍夫曼樹 (Optimal Prefix Code)#

4. 生成樹與 Prüfer Code (Spanning Trees & Prüfer Codes)#

⚠️ 考前避坑指南#

1. 不要混淆 Tree 與 Binary Tree 的公式：在計算 m-ary tree 的節點數時，切記 $m$ 不一定是 2。遇到 $x = mi - i + 1$ 時，一定要先確認題目規定的 $m$ 是多少。
2. 建構 Huffman Tree 絕對不能排錯順序：每次合併完產生「新的內部節點頻率」後，必須重新將其放回候選池中參與下一次的「取最小兩個」的比較。很多學生會忘記把剛合併的數字與原本剩餘的節點重新排序，導致樹的結構完全錯誤。
3. Prüfer Code 的致命盲點：

• 產生 Code 時：每次刪除的是當前編號最小的葉節點，不是隨便挑一個葉節點。
• 還原 Tree 時：尋找配對節點的條件是「未出現在『當前剩餘』序列中」的最小可用數字。如果某個數字前面被劃掉了，但在剩餘序列中已不存在，它就有資格被選為葉節點。
• 停止條件：當節點數剩下 2 個時就必須停止，切勿將最後兩個節點也寫進 Code 裡！Code 的長度永遠死守 $n-2$。