離散數學 · Y. C. Chan · Fall 2026
| p | q | p → q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
1.1 · 投影片 p2–15
學完你能：不漏列地建出真值表，並說出 → 何時為 F。
小考：真值表五年每年都考，10–20 分，是整章最穩的分數。
命題＝有明確真假的陳述句，假的也算。
例子
「Toronto 是加拿大首都」是命題（假）。「現在幾點？」不是。下列哪一句是命題？
p2邏輯不管「數學家有沒有穿涼鞋」，只保證：前提為真，結論必為真。所以第一步先把句子變成只有真或假的命題。
含變數的句子，到 1.4 節用量詞（∀ 唸「對所有」、∃ 唸「存在」）包起來才會變命題。
共六個：¬ 吃一個命題，其他五個吃兩個。
| 符號 | 唸法 | 白話 |
|---|---|---|
| ¬ | 非（not） | 否定，只吃 1 個命題 |
| ∧ | 且（and） | p 和 q 都要 |
| ∨ | 或（or） | 至少一個 |
| ⊕ | 恰有一個（xor） | 剛好一個為真 |
| → | 若…則（implies） | 條件句 |
| ↔ | 若且唯若（iff） | 雙條件句 |
例子
p＝今天下雨、q＝我帶傘。¬p＝今天沒下雨；p ∧ q＝下雨且我帶傘。坑
「手機至少有 32GB」的否定是？
¬ 的真值表：p 為 T 則 ¬p 為 F，反之亦然。投影片有時把 ¬p 寫成 p 上面一條橫線。
∧ 全真才真；∨ 全假才假；⊕ 兩個不同才真。
| p | q | p ∧ q | p ∨ q | p ⊕ q |
|---|---|---|---|---|
| T | T | T | T | F |
| T | F | F | T | T |
| F | T | F | T | T |
| F | F | F | F | F |
例子
菜單「附湯或沙拉」通常是 ⊕（只能選一個）；「修過 A 或 B」是 ∨（兩個都修也行）。p＝T、q＝T 時，p ∨ q 與 p ⊕ q 依序是？
p14位元運算：1 當 T、0 當 F，每個位置各算各的（這部分五年沒考過）。x ＝ 01 1011 0110，y ＝ 11 0001 1101：
p → q 只有「p 真 q 假」才是 F，其他三列全是 T。
flowchart TD
P["承諾 p → q 我當選就降稅"] --> C{"當選了嗎"}
C -->|"當選了"| D1{"有降稅嗎"}
C -->|"沒當選"| D2{"有降稅嗎"}
D1 -->|"有"| R1["T 說到做到"]
D1 -->|"沒有"| R2["F 食言 這是唯一的 F"]
D2 -->|"有"| R3["T 承諾沒啟動"]
D2 -->|"沒有"| R4["T 承諾沒啟動"]
| p | q | p → q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
例子
候選人說「我當選就降稅」。當選了卻沒降稅才是騙人（F）；沒當選，降不降稅都沒人能告他（T）。坑
p＝F、q＝F 時，p → q 是？
「如果 1 + 1 = 3，則我是總統」是真還是假？
小明題（投影片 p9）：小明只會全說真話或全說謊話。他說「我愛小華」和「若我愛小華，則我愛小強」。小明愛小華嗎？
假設全說謊：l＝F，但這時 l → k 因前件為假而是 T，說謊者不能說真話，矛盾。所以他說實話，l＝T（k 也是 T）。已用 python 列舉 8 種組合，只有 (說真話, l, k)＝(T, T, T) 成立。
p ↔ q 真假相同才真，和 p ⊕ q 永遠相反。
| p | q | p → q | q → p | p ↔ q | p ⊕ q |
|---|---|---|---|---|---|
| T | T | T | T | T | F |
| T | F | F | T | F | T |
| F | T | T | F | F | T |
| F | F | T | T | T | F |
p＝F、q＝T 時，p → q 與 p ↔ q 依序是？
if 接前件，only if 接後件。
例子
「只有滿 18 歲才能考駕照」：d＝能考、a＝滿 18。翻成 d → a（能考，就一定滿 18）。坑
p＝拿到 A、q＝期中及格。「只有期中及格，才可能拿 A」？
其他都是 p → q 的說法：if p, q ／ when p, q ／ p implies q ／ q follows from p ／ q is necessary for p ／ p is sufficient for q。注意 whenever、when 後面接的也是前件。
只有逆否命題 ¬q → ¬p 和原句等價。
flowchart TD
A["原命題 p → q"] ---|"永遠等價"| D["逆否 ¬q → ¬p"]
B["逆命題 q → p"] ---|"永遠等價"| C["反命題 ¬p → ¬q"]
A -->|"前後對調"| B
A -->|"各加 ¬"| C
A -->|"對調又加 ¬"| D
例子
原句「下雨 → 地濕」。逆否「地不濕 → 沒下雨」一定對；逆命題「地濕 → 下雨」不一定（可能是灑水車）。| p | q | p → q | q → p | ¬p → ¬q | ¬q → ¬p |
|---|---|---|---|---|---|
| T | T | T | T | T | T |
| T | F | F | T | T | F |
| F | T | T | F | F | T |
| F | F | T | T | T | T |
前後兩欄一樣（≡ 唸「邏輯等價於」），中間兩欄一樣，但前後和中間不同。
下列哪一個與 p → q 永遠同真假？
先 ¬、再 ∧、∨、→、↔；不確定就加括號。
| 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|
| ¬ | ∧ | ∨ | → | ↔ |
例子
p ∨ q ∧ r 是 p ∨ (q ∧ r)。p＝T、q＝F、r＝F 時，它是 T，而 (p ∨ q) ∧ r 是 F。p＝T、q＝T 時，¬p ∨ q 是？（¬ 只管緊跟的 p）
n 個變數列 2ⁿ 列，固定順序排，由內往外加欄。
3 變數的列順序
TTT, TTF, TFT, TFF, FTT, FTF, FFT, FFFflowchart TD
A["數變數 n"] --> B["列 2 的 n 次方 列"]
B --> C["變數欄 TTT 排到 FFF"]
C --> D["由內往外加輔助欄"]
D --> E["最後一欄是答案"]
E --> F["逐列檢查 T 對 F 的 →"]自己試（直接貼 ¬ ∧ ∨ ⊕ → ↔，變數用單一小寫字母）：
4 個變數的真值表要列幾列？
投影片例子（Table 7）：(p ∨ ¬q) → (p ∧ q)。
| p | q | ¬q | p ∨ ¬q | p ∧ q | (p ∨ ¬q) → (p ∧ q) |
|---|---|---|---|---|---|
| T | T | F | T | T | T |
| T | F | T | T | F | F |
| F | T | F | F | F | T |
| F | F | T | T | F | F |
歷屆有人多畫無關的欄（沒扣分）、或用非標準列順序但八列齊全（滿分）。只要列齊、每欄都對就拿分。
練功 1 109-1(a)・107-1 原題
Construct the truth table for p → (¬q ∨ r).
| p | q | r | ¬q | ¬q ∨ r | p → (¬q ∨ r) |
|---|---|---|---|---|---|
| T | T | T | F | T | T |
| T | T | F | F | F | F |
| T | F | T | T | T | T |
| T | F | F | T | T | T |
| F | T | T | F | T | T |
| F | T | F | F | F | T |
| F | F | T | T | T | T |
| F | F | F | T | T | T |
結果欄 T F T T T T T T。p＝F 的四列前件為假，自動 T；只有 p＝T 而 ¬q ∨ r＝F（q＝T、r＝F）那列是 F。
練功 2 110-1(b)・109-1(b) 原題
Construct the truth table for (p ↔ q) ⊕ (p ↔ ¬q).
| p | q | ¬q | p ↔ q | p ↔ ¬q | (p ↔ q) ⊕ (p ↔ ¬q) |
|---|---|---|---|---|---|
| T | T | F | T | F | T |
| T | F | T | F | T | T |
| F | T | F | F | T | T |
| F | F | T | T | F | T |
p ↔ q 與 p ↔ ¬q 永遠一真一假，⊕ 遇到一真一假就是 T，所以結果欄全是 T（恆真式，1.3 節會講）。
練功 3 110-1(a)・108-1 原題
Construct the truth table for ¬p → (q → r).
| p | q | r | ¬p | q → r | ¬p → (q → r) |
|---|---|---|---|---|---|
| T | T | T | F | T | T |
| T | T | F | F | F | T |
| T | F | T | F | T | T |
| T | F | F | F | T | T |
| F | T | T | T | T | T |
| F | T | F | T | F | F |
| F | F | T | T | T | T |
| F | F | F | T | T | T |
結果欄 T T T T T F T T。只有 p＝F、q＝T、r＝F 那一列是 F。
練功 4 112-4 題型
Construct the truth table for (q ⊕ r) → (¬p ↔ q).
| p | q | r | q ⊕ r | ¬p | ¬p ↔ q | (q ⊕ r) → (¬p ↔ q) |
|---|---|---|---|---|---|---|
| T | T | T | F | F | F | T |
| T | T | F | T | F | F | F |
| T | F | T | T | F | T | T |
| T | F | F | F | F | T | T |
| F | T | T | F | T | T | T |
| F | T | F | T | T | T | T |
| F | F | T | T | T | F | F |
| F | F | F | F | T | F | T |
結果欄 T F T T T T F T。F 的兩列是 (T,T,F) 與 (F,F,T)。
1.2 · 投影片 p16–19
學完你能：用 x ↔ S 解武士與無賴謎題，認出三個歷屆套路。
小考：謎題五年每年一題（10–15 分）；翻譯、規格、電路五年沒考過。
先切原子命題再選連接詞；A unless B ＝ 若非 B 則 A。
例子
「我去爬山，除非下雨」：h＝我去爬山、r＝下雨。翻成 ¬r → h，等價 h ∨ r。坑
e＝你能進場、m＝你是會員。「除非你是會員，否則你不能進場」翻成？
p16課本 Example 2：「You cannot ride the roller coaster if you are under 4 feet tall unless you are older than 16 years old.」q＝能搭、r＝未滿 4 英尺、s＝超過 16 歲。意思是：矮、且不是超過 16 歲，就不能搭。翻成 (r ∧ ¬s) → ¬q。等價的寫法都算對。
一致＝存在一組真值，讓所有規格同時為真。
例子
p＝存在緩衝區、q＝被重傳。規格：p ∨ q、¬p、p → q。¬p 要 p＝F，p ∨ q 要 q＝T，這時 p → q 自動 T：(F, T) 就是解，所以一致。| p | q | p ∨ q | ¬p | p → q | 三條都真 |
|---|---|---|---|---|---|
| T | T | T | F | T | F |
| T | F | T | F | F | F |
| F | T | T | T | T | T |
| F | F | F | T | T | F |
再加一條 (4)「沒有被重傳」即 ¬q，四條還一致嗎？
邏輯電路（p18，五年沒考過）：反相器是 ¬、OR 閘是 ∨、AND 閘是 ∧，公式由最內層往外接線。課本 Example 10 輸出 (p ∨ ¬r) ∧ (¬p ∨ (q ∨ ¬r))，用 3 個反相器、3 個 OR、1 個 AND。各線的值：
| p | q | r | ¬r | p ∨ ¬r | ¬p ∨ (q ∨ ¬r) | 輸出 |
|---|---|---|---|---|---|---|
| T | T | T | F | T | T | T |
| T | T | F | T | T | T | T |
| T | F | T | F | T | F | F |
| T | F | F | T | T | T | T |
| F | T | T | F | F | T | F |
| F | T | F | T | T | T | T |
| F | F | T | F | F | T | F |
| F | F | F | T | T | T | T |
輸出欄 T T F T F T F T，和 ¬r ∨ (p ∧ q) 完全一樣（python 驗算過），所以可以用更少的閘做出來；這是 1.3 節化簡的用處。
X 說了一句話 S，就寫 x ↔ S。
例子
A 說「我是無賴」：S＝¬a，條件 a ↔ ¬a 永遠為假。沒有人說得出這句話。有人說「我是無賴」，這可能嗎？
窮舉身分或假設推矛盾，最後數有幾組解。
flowchart TD
R["A 說 B 是無賴 B 說 A 和 B 都是武士"] --> H1["假設 A 是武士"]
R --> H2["假設 A 是無賴"]
H1 --> H1a["A 的話為真 所以 B 是無賴"]
H1a --> H1b["B 說的話為假 無賴本來就說假話"]
H1b --> H1c["沒有矛盾 這組成立"]
H2 --> H2a["A 說謊 所以 B 是武士"]
H2a --> H2b["B 的話必須為真 即 A 和 B 都是武士"]
H2b --> H2c["但 A 是無賴 矛盾 剪掉"]
flowchart TD
A["X 說了 S"] --> B["寫 x ↔ S"]
B --> C{"人數少嗎"}
C -->|"是"| D["窮舉 2 的 n 次方 種身分"]
C -->|"否"| E["假設某人是武士 推矛盾"]
D --> F["數有幾組解"]
E --> F例子
A：「B 是無賴。」B：「A 和 B 都是武士。」四種組合只有 (a, b)＝(T, F) 過關：A 是武士，B 是無賴。A 說：「B 是武士。」B 說：「A 和我是不同種類。」A、B 各是？
A 的例題完整表：
| a | b | a ↔ ¬b | b ↔ (a ∧ b) | 兩人都符合 |
|---|---|---|---|---|
| T | T | F | T | F |
| T | F | T | T | T |
| F | T | T | F | F |
| F | F | F | T | F |
假設推矛盾：假設 B 是武士，則「A、B 都是武士」為真，A 也是武士，但 A 說「B 是無賴」就成了假話，矛盾。所以 B 是無賴，A 的話為真，A 是武士。
自己練：A 說「我是無賴，或 B 是武士」，B 說「A 和我是同一種人」。假設 A 是無賴，則 ¬a 為真，A 的話為真，無賴說真話，矛盾；所以 A 是武士，要讓 ¬a ∨ b 為真，b＝T。答案：兩人都是武士（python 列舉四組，只有 (T,T)）。
找出不管武士或無賴都會說的話，它是確定的事實。
flowchart TD
J["甲被問 武士還是道士"] --> J1["兩種人都答 我是武士"]
J1 --> Y["乙說 甲說他是道士 一定是假話"]
Y --> Y1["乙是道士"]
Y1 --> B["丙說 乙在騙人 是真話"]
B --> B1["丙是武士"]
J1 --> J2["甲的答案分不出身分 無法確定"]
例子
武當山：甲被問「你是武士還是道士」，兩種人都答「武士」。乙說「甲說他是道士」＝假話，乙是道士；丙說乙在騙人＝真話，丙是武士；甲無法確定。坑
你問一個居民「Are you a knight?」，他最可能怎麼答？
分辨身分要答案不同，問事實要答案相同。
例子
岔路問「右邊通廢墟嗎？」：說謊者會反著答。多包一層「你會回答 yes 嗎？」，說謊者反兩次又變回事實，答 yes 就走右邊。想知道「岔路哪條通到目的地」，不管對方是誰，該設計成？
誠實的人說「不知道」，就洩漏了他自己那份。
flowchart TD
P1["第 1 位說 不知道"] --> W1["他自己要 w1 為 T"]
W1 --> P2["第 2 位說 不知道"]
P2 --> W2["w1 已是 T 所以他也要 w2 為 T"]
W2 --> P3["第 3 位說 不是"]
P3 --> W3["大家都要 就等於 w3 所以 w3 為 F"]
例子
三位教授被問「大家都要咖啡嗎？」答：不知道、不知道、不是。第 1、2 位說不知道＝他們要；第 3 位答不是＝他不要。誠實的第 1 位教授說「我不知道大家是否都要咖啡」，代表？
練功 1 投影片 p19
Translate: You cannot edit a protected Wikipedia entry unless you are an administrator.（e＝能編輯、a＝是管理員）
答案 e → a（或 ¬a → ¬e）。常見錯誤寫成 a → e，方向反了。python 驗算過 ¬a → ¬e 與 e → a 等價。
練功 2 110-2・107-2 原題
武當山住著專說真話的武士和專說假話的道士。張無忌問路人甲：「你是武士還是道士？」風太大沒聽到。路人乙說：「甲說他自己是道士。」路人丙說：「不要相信乙，他是騙你的。」請問甲、乙、丙各是哪一種？（說明理由）
結論：甲無法確定，乙是道士，丙是武士。python 列舉 8 種身分，剩 (武士,道士,武士) 與 (道士,道士,武士)，只差在甲。
練功 3 投影片 p11 練習
島上有兩個部落，一個都說實話，一個都說謊話。問土著「島上有金礦嗎？」他答：「島上有金礦若且為若我說實話。」他來自哪個部落？島上有沒有金礦？
兩種部落 g 都是 T：島上有金礦；部落無法確定。python 列舉 (g, t)，剩 (T,T)、(T,F) 兩組。
練功 4 108-2 原題
An explorer is captured by cannibals who either always tell the truth or always lie. He may ask exactly one question to tell which type a cannibal is. (a) Why does 「Are you a liar?」 not work? (b) Find a question that works.
(a) 說真話者答 No；說謊者真相是 Yes，說謊後也答 No。兩種人都答 No，分不出來。（yes 的條件 t ↔ ¬t 永遠為假。）
(b) 問「Is 1 + 1 = 2?」說真話者答 Yes，說謊者答 No，一聽就知道。（yes 的條件是 t ↔ T，即 t。）
練功 5 109-2 原題
A villager always tells the truth or always lies, answering only “Yes” or “No”. At a fork, one branch leads to the ruins. Explain why asking “If I were to ask you whether the right branch leads to the ruins, would you say ‘yes’?” tells you which branch to take.
t ↔ (t ↔ R) 化簡後等於 R（兩個 t 抵消）。
| R | 村民 | 直接問會答 | 複合問句的回答 |
|---|---|---|---|
| 真 | 說真話 | yes | yes |
| 真 | 說謊 | no | yes |
| 假 | 說真話 | no | no |
| 假 | 說謊 | yes | no |
結論：回答 yes 就走右邊，no 就走左邊，不用管他是誰。注意：109 年有人寫「可以分辨誰說真話」，得 0 分；這題做不到也不需要。
練功 6 112-2 原題
Three professors are asked: “Does everyone want coffee?” The first says “I do not know.” The second says “I do not know.” The third says “No, not everyone wants coffee.” How did the hostess figure out who wanted coffee?
結論：第 1、2 位要咖啡，第 3 位不要。python 窮舉 8 種，照「只知道自己偏好和先前回答」模擬，只有 (T,T,F) 產生「不知道、不知道、不是」。
1.3 · 投影片 p20–30
學完你能：判斷兩個式子等不等價，並一步一步用定律化簡。
小考：109-3、107-3、108-3 各 10 分，連三題都是「用等價律證明兩式等價」，這節是送分題。
寫法不同、真假永遠一樣的兩個式子，叫邏輯等價，記作 ≡。
例子
「下雨就帶傘」p → q 和「沒下雨或有帶傘」¬p ∨ q，四種天氣下真假完全一樣，所以等價。 p20–21p ∧ q 與 q ∧ p 等價嗎？
兩個式子用同樣的原子命題 p₁, …, pₙ 組成，對每一種真值指派真值都相同才算等價。三種說法是同一件事：P ≡ Q ⇔ P ↔ Q 恆真 ⇔ 真值表兩欄逐列相同（⇔ 唸「若且唯若」）。
坑
真值表結果欄全 T 是恆真句，全 F 是矛盾句，其餘是適真句。
例子
「下雨或不下雨」一定對，是恆真；「下雨而且不下雨」一定錯，是矛盾。 p20(p ∧ q) → p 屬於哪一類？
存在某一種真值指派使它為 T，就叫可滿足（satisfiable）；沒有任何指派能讓它為 T 叫不可滿足，也就是矛盾句。所以恆真句和適真句都可滿足。這個概念歷屆小考沒考過。
課本例：A = (p ∨ ¬q) ∧ (q ∨ ¬r) ∧ (r ∨ ¬p) 在 p、q、r 全相同時為 T；B = (p ∨ q ∨ r) ∧ (¬p ∨ ¬q ∨ ¬r) 在三者不全相同時為 T；C = A ∧ B 兩個要求互相矛盾，不可滿足。
列出所有組合，算出兩個式子，兩個結果欄逐列相同就等價。
| p | q | p → q | ¬p | ¬p ∨ q |
|---|---|---|---|---|
| T | T | T | F | T |
| T | F | F | F | F |
| F | T | T | T | T |
| F | F | T | T | T |
兩個標記欄都是 T, F, T, T，所以 p → q ≡ ¬p ∨ q。自己輸入式子試試：
p → q 與 q → p（逆命題）等價嗎？
| p | q | p ∨ q | ¬(p ∨ q) | ¬p | ¬q | ¬p ∧ ¬q |
|---|---|---|---|---|---|---|
| T | T | T | F | F | F | F |
| T | F | T | F | F | T | F |
| F | T | T | F | T | F | F |
| F | F | F | T | T | T | T |
結果欄都是 F, F, F, T，所以 ¬(p ∨ q) ≡ ¬p ∧ ¬q。三個變數就有 8 列，分配律 p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) 的兩欄都是 T, T, T, T, T, F, F, F。
否定進括號，且與或互換。
例子
「不是（下雨而且颳風）」＝「沒下雨或沒颳風」。只要有一個沒發生，原句就不成立。坑
哪一個與 ¬(p ∨ ¬q) 等價？
大多數定律成對出現，兩式互為對偶（∧∨ 互換、T F 互換）；雙重否定律只有一式。
| 定律 | 式子 | 白話 |
|---|---|---|
| 同一律 Identity | p ∧ T ≡ p p ∨ F ≡ p | 和恆真做且、和恆假做或，沒變 |
| 支配律 Domination | p ∧ F ≡ F p ∨ T ≡ T | 有 F 的且是 F，有 T 的或是 T |
| 冪等律 Idempotent | p ∧ p ≡ p p ∨ p ≡ p | 重複寫沒差 |
| 雙重否定律 Double negation | ¬(¬p) ≡ p | 否定兩次回原狀 |
| 交換律 Commutative | p ∨ q ≡ q ∨ p p ∧ q ≡ q ∧ p | 順序可對調 |
| 結合律 Associative | (p ∨ q) ∨ r ≡ p ∨ (q ∨ r) (p ∧ q) ∧ r ≡ p ∧ (q ∧ r) | 同種運算括號位置不影響 |
| 分配律 Distributive | p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) | 兩個方向都能分配 |
| De Morgan | ¬(p ∧ q) ≡ ¬p ∨ ¬q ¬(p ∨ q) ≡ ¬p ∧ ¬q | 否定進括號，且或互換 |
| 吸收律 Absorption | p ∨ (p ∧ q) ≡ p p ∧ (p ∨ q) ≡ p | 多出來的部分被吃掉 |
| 否定律 Negation | p ∨ ¬p ≡ T p ∧ ¬p ≡ F | p 或非 p 必真，p 且非 p 必假 |
p ∨ (p ∧ q) 化簡後是？
投影片與考卷用「第一式、第二式」指同一格裡的上下兩條。例如 first De Morgan 是 ¬(p ∧ q) ≡ ¬p ∨ ¬q，second De Morgan 是 ¬(p ∨ q) ≡ ¬p ∧ ¬q。這張表是課本 Table 6（p25）。
最常用 p → q ≡ ¬p ∨ q；它的否定是 p ∧ ¬q。
例子
「下雨就帶傘」被打破，只有一種情況：下雨了而且沒帶傘。 p27坑
¬(p → q) 與哪一個等價？
| 編號 | 條件句等價式（Table 7） | 備註 |
|---|---|---|
| 1 | p → q ≡ ¬p ∨ q | 最常用 |
| 2 | p → q ≡ ¬q → ¬p | 逆否 |
| 3 | p ∨ q ≡ ¬p → q | |
| 4 | p ∧ q ≡ ¬(p → ¬q) | |
| 5 | ¬(p → q) ≡ p ∧ ¬q | 否定條件句 |
| 6 | (p → q) ∧ (p → r) ≡ p → (q ∧ r) | |
| 7 | (p → r) ∧ (q → r) ≡ (p ∨ q) → r | 109-3、107-3 |
| 8 | (p → q) ∨ (p → r) ≡ p → (q ∨ r) | |
| 9 | (p → r) ∨ (q → r) ≡ (p ∧ q) → r | 108-3 |
| 編號 | 雙條件句等價式（Table 8） | 備註 |
|---|---|---|
| 1 | p ↔ q ≡ (p → q) ∧ (q → p) | 雙向都成立 |
| 2 | p ↔ q ≡ ¬p ↔ ¬q | |
| 3 | p ↔ q ≡ (p ∧ q) ∨ (¬p ∧ ¬q) | 最常用：同真或同假 |
| 4 | ¬(p ↔ q) ≡ p ↔ ¬q |
記不下就先記 Table 7 第 1、2、5 列和 Table 8 第 3 列。考試引用時要寫明是哪一條。
p22 的餐廳招牌：「好的食物不便宜」是 g → ¬c，「便宜的食物不好」是 c → ¬g，兩者互為逆否，都等價於 ¬(g ∧ c)。
看到 → 就先改成 ¬… ∨ …，後面才有定律可用。
flowchart TD
A["拿到要證明的等價式"] --> B{"式子裡有 → 嗎？"}
B -->|有| C["先把 → 改成 ¬… ∨ …"]
B -->|沒有| D{"¬ 在括號前面嗎？"}
C --> D
D -->|是| E["用 De Morgan"]
D -->|否| F["括號套括號就用分配律"]
E --> G["每步只套一條定律並寫名稱"]
F --> G
要證 (p → r) ∧ (q → r) ≡ (p ∨ q) → r，第一步做什麼？
109-3、107-3（兩年同一題）與 108-3 都是投影片 p30 的 Exercise，也就是 Table 7 的第 7、9 列。歷屆寫法都是 5 行左右：改條件句、整理（分配、結合或冪等）、De Morgan、再還原成 →。
108-3 有人把第二步標成「分配律」，實際用的是結合律、交換律加冪等律。標錯定律名稱可能被扣分。109-3 的卷面沒寫名稱仍拿滿分，但題目明說要 develop a series of logical equivalences，寫名稱最安全。
一行換一個地方，右邊寫下用的定律名稱。
例子
¬p ∧ (p ∨ ¬q) ≡ (¬p ∧ p) ∨ (¬p ∧ ¬q) 用的是哪條定律？
證明 ¬(p ∨ (¬p ∧ q)) ≡ ¬p ∧ ¬q：
證恆真句：(p ∧ q) → (p ∨ q) 的第一步改條件句，再 De Morgan，最後配成 T ∨ T ≡ T。見練功 4。
練功 1 109-3 原題 107-3 原題
Show that (p → r) ∧ (q → r) and (p ∨ q) → r are logically equivalent by developing a series of logical equivalences. (10%)
第 3 步是關鍵。分配律寫成 r ∨ (¬p ∧ ¬q) ≡ (r ∨ ¬p) ∧ (r ∨ ¬q)，兩邊用交換律換位置，就是我們用的方向。
也可以用真值表，8 列，最後兩欄逐列相同（T, F, T, F, T, F, T, T）：
| p | q | r | p → r | q → r | (p → r) ∧ (q → r) | p ∨ q | (p ∨ q) → r |
|---|---|---|---|---|---|---|---|
| T | T | T | T | T | T | T | T |
| T | T | F | F | F | F | T | F |
| T | F | T | T | T | T | T | T |
| T | F | F | F | T | F | T | F |
| F | T | T | T | T | T | T | T |
| F | T | F | T | F | F | T | F |
| F | F | T | T | T | T | F | T |
| F | F | F | T | T | T | F | T |
練功 2 108-3 原題
Show that (p → r) ∨ (q → r) and (p ∧ q) → r are logically equivalent by developing a series of logical equivalences. (10%)
第 3 步其實用了結合律和交換律兩條。考試寫成兩行更保險，這裡為版面合併。
練功 3
用一連串等價式證明 p → (q → r) ≡ (p ∧ q) → r，每一步標定律名稱。
白話：「先 p 再 q 就推出 r」和「p 與 q 都成立就推出 r」是同一件事。
練功 4
用等價律證明 (p ∧ q) → (p ∨ q) 是恆真句，每一步標定律名稱。
1.4 · 投影片 p31–56
學完你能：把英文句子翻成量詞式，並判斷、否定含量詞的敘述。
小考：109-4、107-4 各 20 分，前半是英文翻量詞式（後半推論在 1.6 教）。
P(x) 是帶變數的敘述，x 沒有值時沒有真假，代入具體值才變命題。
例子
P(x) 是「x > 3」：P(4) 為 T，P(2) 為 F。 p32–34Q(x, y) 是「x = y + 3」。Q(0, 3) 的真值是？
命題邏輯把整句話當不可分的積木，寫不出「所有人都會死，蘇格拉底是人，所以蘇格拉底會死」這種推論。謂詞邏輯補上變數和量詞。「x > 3」「x = y + 3」在變數沒值時不是命題。
n 個變數的 P(x₁, …, xₙ) 叫 n 元謂詞，n 個變數全部給值後才變成命題。例：R(x, y, z) 是「x + y = z」，R(1, 2, 3) 為 T，R(0, 0, 1) 為 F。
∀x P(x) 表示論域裡每個 x 都成立，只要一個反例就是 F。
例子
P(x) 是「x² < 10」，論域 {1, 2, 3, 4}。16 < 10 不成立，x = 4 是反例，所以 ∀x P(x) 為 F。 p35–40∀x (x² ≥ x)，論域是整數，真假？
∃x P(x) 表示至少有一個 x 成立，找到一個例子就是 T。
例子
P(x) 是「x² > 10」，論域 {1, 2, 3, 4}。16 > 10，所以 ∃x P(x) 為 T。 p42–46坑
∃x (x² = 2)，論域是整數，真假？
| 敘述 | 什麼時候為 T | 什麼時候為 F |
|---|---|---|
| ∀x P(x) | 每個 x 都使 P(x) 為 T | 有某個 x 使 P(x) 為 F |
| ∃x P(x) | 有某個 x 使 P(x) 為 T | 每個 x 都使 P(x) 為 F |
注意「至少一個」不是「恰好一個」。
零個自由變數才是命題；量詞只管緊跟在後面的那一塊。
例子
∀x P(x) ∨ Q(x) 讀成 (∀x P(x)) ∨ Q(x)，後面的 x 沒人管，整句沒有真假。 p48–49∀x P(x) ∨ Q(x) 是命題嗎？
否定穿過量詞時，∀ 與 ∃ 互換，¬ 推進述詞裡面。
例子
「每位學生都修過微積分」的否定，是「至少有一位沒修過」，不是「所有人都沒修過」。 p50–54坑
¬∀x (x² > x) 等價於？
這和 1.3 的 De Morgan 是同一個精神，因為 ∀ 是一長串 ∧，∃ 是一長串 ∨。其他例子：¬∃x (x² = 2) ≡ ∀x (x² ≠ 2)。
英文 "All politicians are not honest" 有歧義，可能是「全都不誠實」也可能是「不是全都誠實」，寫否定時改用 "Some politician is not honest"。
「所有 A 都是 B」寫成 ∀x (A(x) → B(x))，∀ 配 →。
例子
論域是學校的人。Amy（學生、修過）、Bob（老師）。「所有學生都修過」是真的。∀x (S(x) → C(x))：Bob 的前件 F，條件句為 T，整句 T。∀x (S(x) ∧ C(x))：Bob 不是學生，整句 F，翻錯了。坑
S(x) 是「x 是學生」，C(x) 是「x 修過微積分」。「所有學生都修過微積分」是？
如果論域已經限定是 A（例如「論域是班上的學生」），A(x) 就不用寫，直接 ∀x B(x)。真的要說每個人都是朋友又完美時，∀ 配 ∧ 才對：∀x (F(x) ∧ P(x))。
「有 A 是 B」寫成 ∃x (A(x) ∧ B(x))，∃ 配 ∧。
例子
Amy 是學生但沒修過，Bob 是老師。「有學生修過」是假的。∃x (S(x) → C(x))：Bob 前件 F，條件句 T，整句 T，翻錯了。∃x (S(x) ∧ C(x)) 為 F，正確。坑
「有學生修過微積分」的正確翻譯是？
∀ 配 →，∃ 配 ∧；「沒有」就是 ∀ 配 → ¬，或 ¬∃ 配 ∧。
| 中文／英文 | 量詞式 | 備註 |
|---|---|---|
| 所有 A 都是 B All A are B | ∀x (A(x) → B(x)) | ∀ 配 → |
| 沒有 A 是 B No A is B | ∀x (A(x) → ¬B(x)) ¬∃x (A(x) ∧ B(x)) | 兩個寫法等價 |
| 有些 A 是 B Some A is B | ∃x (A(x) ∧ B(x)) | ∃ 配 ∧ |
| 有些 A 不是 B Some A is not B | ∃x (A(x) ∧ ¬B(x)) ¬∀x (A(x) → B(x)) | 兩個寫法等價 |
flowchart TD
A["讀句子，先定出 A(x) 和 B(x)"] --> B{"句子開頭是哪個字？"}
B -->|All 所有| C["用 ∀x，A(x) → B(x)"]
B -->|Some 有些| D["用 ∃x，A(x) ∧ B(x)"]
B -->|No 沒有| E["用 ∀x，A(x) → ¬B(x)"]
C --> F["檢查括號有包住整個式子"]
D --> F
E --> F
「沒有學生作弊」，S(x) 是學生，H(x) 是作弊。正確翻譯是？
P(x) 是「x 會說俄語」，Q(x) 是「x 會 C++」，論域是學校的所有學生：
Lewis Carroll 例（p55）：論域是鳥，P 是蜂鳥、Q 是大、R 靠蜂蜜維生、S 色彩鮮豔。「所有蜂鳥都色彩鮮豔」是 ∀x (P(x) → S(x))；「沒有大鳥靠蜂蜜維生」是 ¬∃x (Q(x) ∧ R(x))；「不靠蜂蜜的鳥都色彩單調」是 ∀x (¬R(x) → ¬S(x))；結論「蜂鳥是小鳥」是 ∀x (P(x) → ¬Q(x))。能不能推出結論，1.6 才教。
∀ 能對 ∧ 分配，∃ 能對 ∨ 分配，反過來不行。
| 式子 | 是否等價 |
|---|---|
| ∀x (P(x) ∧ Q(x)) 與 ∀x P(x) ∧ ∀x Q(x) | 等價 |
| ∃x (P(x) ∨ Q(x)) 與 ∃x P(x) ∨ ∃x Q(x) | 等價 |
| ∀x (P(x) ∨ Q(x)) 與 ∀x P(x) ∨ ∀x Q(x) | 不等價 |
| ∃x (P(x) ∧ Q(x)) 與 ∃x P(x) ∧ ∃x Q(x) | 不等價 |
例子
論域 {1, 2}，P 是偶數，Q 是奇數。每個數不是偶數就是奇數，所以 ∀x (P(x) ∨ Q(x)) 為 T，但 ∀x P(x) ∨ ∀x Q(x) 為 F。論域 {1, 2}，P 是偶數，Q 是奇數。∃x (P(x) ∧ Q(x)) 的真值？
另有 ∀x (A(x) → ¬B(x)) ≡ ¬∃x (A(x) ∧ B(x))，是量詞 De Morgan 加上 1.3 的 ¬(p → q) 組合出來的。多個量詞套在一起（∀x ∃y …）是 1.5 的內容。
練功 1 109-4 原題
P(x)、S(x) 分別是 “x is a duck,” “x is willing to waltz.” 用量詞表達 (a) No ducks are willing to waltz。另外說明為什麼 (a) 不能寫成 ¬∃x (P(x) → S(x))。
練功 2 109-4 原題
Q(x)、R(x)、P(x)、S(x) 分別是 “x is one of my poultry,” “x is an officer,” “x is a duck,” “x is willing to waltz.” 用量詞表達：(b) No officers ever decline to waltz. (c) All my poultry are ducks. (d) My poultry are not officers.
（原題 (e) 問 (d) 是否由 (a)(b)(c) 推出，屬於 1.6。）
練功 3 107-4 原題
P(x)、Q(x)、R(x) 分別是 “x is a clear explanation,” “x is satisfactory,” “x is an excuse.” 論域是所有英文文字。用量詞、聯結詞表達：(a) All clear explanations are satisfactory. (b) Some excuses are unsatisfactory. (c) Some excuses are not clear explanations.
（原題 (d) 要問 (c) 能否由 (a)(b) 推出並證明，是 1.6 的內容。）
陷阱：(b)(c) 寫成 ∃x (R(x) → ¬Q(x)) 就錯了，只要有一段文字不是藉口，整句就成立。後半的證明別只寫 yes，107-4 就有人因此被扣 5 分。
練功 4
P(x) 是「x 是偶數」，Q(x) 是「x² < 30」，論域是 {1, 2, 3, 4, 5}。判斷真假：∀x P(x)、∃x P(x)、∀x Q(x)、∃x ¬Q(x)、∀x (P(x) → Q(x))。
1.5 · 投影片 p57–69
學完你能：讀懂兩層量詞、判斷順序換了會不會變、把否定一層層推進去。
小考：107–112 五年都沒單獨考。但 1.6 的量詞推論要靠這節的讀式能力。
兩個量詞疊在一起叫巢狀量詞，從左到右一層一層讀就好。
例子 p57–58
∀x ∃y (x + y = 0)：每個實數 x，都找得到某個 y 讓 x + y = 0。（y 就是 −x）∀x ∃y L(x, y)，L 是「x 愛 y」。怎麼讀？
∀ 是「找反例」的迴圈，∃ 是「找見證」的迴圈。
flowchart TD
A["讀第一個量詞"] --> B{"∀ 還是 ∃"}
B -->|"∀"| C["對每個 x 檢查內層"]
B -->|"∃"| D["挑一個 x 讓內層成立"]
C --> E["內層同樣處理：∀ 找反例，∃ 找見證"]
D --> E
論域 {1, 2, 3}，∀x ∃y (y > x) 的真假？
∀ 和 ∃ 混用時不能換順序，換了真假可能不同。
例子 p62
實數、x + y = 0：∀x ∃y 真（取 y = −x）；∃y ∀x 假（固定 y 之後只有 x = −y 能成立）。坑
論域 {1, 2, 3}，「x ≠ y」。哪一句為真？
全是 ∀、或全是 ∃ 時，順序可以換（p61）：∀x∀y P ≡ ∀y∀x P。只要 ∀、∃ 混用就不能換。
| 式子 | 何時為真 | 何時為假 |
|---|---|---|
| ∀x∀y P | 每一組 (x, y) 都真 | 有一組為假 |
| ∀x∃y P | 每個 x 都有某個 y 使 P 為真 | 有一個 x，對每個 y 都假 |
| ∃x∀y P | 有一個 x，對每個 y 都真 | 每個 x 都有某個 y 使 P 為假 |
| ∃x∃y P | 有一組為真 | 每一組都假 |
「一個 y 通吃」比「每個 x 各有各的 y」強。
例子
「有一個人被所有人愛」為真，「每個人都有愛的人」一定為真：大家都愛同一個人嘛。反過來，各愛各的就不是同一個人。已知 ∃y ∀x P(x, y) 為真，∀x ∃y P(x, y) 呢？
¬ 每越過一個量詞，∀ 與 ∃ 對調；最內層否定述詞本身。
例子 p67
坑
flowchart LR
A["¬∀x ∃y (xy = 1)"] -->|"越過 ∀ 變 ∃"| B["∃x ¬∃y (xy = 1)"]
B -->|"越過 ∃ 變 ∀"| C["∃x ∀y ¬(xy = 1)"]
C -->|"否定述詞"| D["∃x ∀y (xy ≠ 1)"]
¬∀x ∃y P(x, y) 等價於？
「有一個女人搭過每家航空公司的班機」∃w ∀a ∃f (P(w, f) ∧ Q(f, a)) 的否定：
∀ 對 ∧、∃ 對 ∨ 才能分配；限制論域時 ∀ 配 →、∃ 配 ∧。
坑
「每個學生都有朋友」，論域含非學生。哪個翻譯對？
p64–66論域是 a, b, c… 時，∀x P(x) 就是 P(a) ∧ P(b) ∧ …，∃x P(x) 就是 P(a) ∨ P(b) ∨ …。這就是為什麼量詞有 De Morgan。同樣道理，∃ 對 ∧ 也不能分配：(∃x P) ∧ (∃x Q) 真，∃x (P ∧ Q) 假（上面的論域）。
p69「每個正整數都是四個整數的平方和」：∀n (n > 0 → ∃a ∃b ∃c ∃d (n = a² + b² + c² + d²))。a, b, c, d 的論域要含 0，因為 1 = 1² + 0² + 0² + 0²。
練功 1
論域是實數，判斷真假並用一句話說理由：
(a) ∀x ∃y (xy = 1) (b) ∃x ∀y (xy = 0) (c) ∀x ∃y (y² = x) (d) ∀x ∃y (x < y) (e) ∃y ∀x (x < y)
練功 2
寫出 ∀x ∃y ∀z (P(x, y, z) → Q(x, z)) 的否定，使 ¬ 不出現在任何量詞前面，也不出現在 → 的外面。
1.6 · 投影片 p70–88
學完你能：判斷論證有不有效，並寫出每步標規則與行號的量詞推導。
小考：量詞推論 107–112 每年都考，單題 10–15 分，是第 1 章配分最高的題型；命題論證也考過三次。
前提全真時，結論一定真，就叫有效。只看形式。
例子 p70–72
有有效密碼就能登入；你有有效密碼；所以你能登入。形式 p → q，p ∴ q（p → q 唸「若 p 則 q」）。p ∨ q，p ∴ ¬q 有效嗎？
有效只保證：前提全真時結論不會假。前提是假的就沒保證。
例子 p77
「若 √2 > 3/2 則 2 > 9/4；√2 > 3/2；所以 2 > 9/4」。形式有效，但 √2 ≈ 1.414，前提是假的，結論也假。flowchart LR
A["假前提：√2 ＞ 3/2"] --> B["形式有效：p → q，p ∴ q"]
B --> C["結論 2 ＞ 9/4 也是假的"]
D["真前提"] --> B
B --> E["結論一定為真"]
有效的論證，結論卻是假的。那前提呢？
只看「前提全是 T」的列；那幾列結論有 F，就是反例，論證無效。
| p | q | 前提 p → q | 前提 p | 結論 q |
|---|---|---|---|---|
| T | T | T | T | T |
| T | F | F | T | F |
| F | T | T | F | T |
| F | F | T | F | F |
檢查 p → q，¬p ∴ ¬q，反例是哪組真值？
上面的表是 modus ponens：前提同時為 T 的只有第一列，結論是 T，所以有效。第二列結論雖然是 F，但前提 p → q 已經是 F，不算數。
八條規則各對應一個恆真式；先符號化，再對形式。
| 規則 | 形式（前提 ∴ 結論） | 白話 |
|---|---|---|
| Modus ponens 肯定前件 | p，p → q ∴ q | p 成立，所以 q 成立 |
| Modus tollens 否定後件 | ¬q，p → q ∴ ¬p | q 沒發生，所以 p 沒發生 |
| Hypothetical syllogism 假言三段論 | p → q，q → r ∴ p → r | 條件句接龍，q 消掉 |
| Disjunctive syllogism 選言三段論 | p ∨ q，¬p ∴ q | 二選一，排除一個就剩另一個 |
| Addition 添加律 | p ∴ p ∨ q | p 真，則「p 或任何事」真 |
| Simplification 簡化律 | p ∧ q ∴ p | 連言拆開取一項 |
| Conjunction 連言律 | p，q ∴ p ∧ q | 兩個都成立就併起來 |
| Resolution 預解律 | p ∨ q，¬p ∨ r ∴ q ∨ r | p 與 ¬p 消掉，剩下併起來 |
口訣 p74
ponens 肯定前件，從 p 推 q；tollens 否定後件，從 ¬q 推 ¬p。flowchart LR
A["p → q 與 p"] -->|"Modus ponens"| B["q"]
C["p → q 與 ¬q"] -->|"Modus tollens"| D["¬p"]
E["p → q 與 q → r"] -->|"假言三段論"| F["p → r"]
「若 n > 3 則 n² > 9。n² 不大於 9。所以 n 不大於 3。」用哪條規則？
每一行都要有理由：前提，或「規則名稱＋用到第幾行」。
例子 p78 游泳與獨木舟
前提：不晴而且冷；只有晴才游泳；不游泳就划獨木舟；划獨木舟就早回家。結論：早回家。
flowchart TD
A["前提 1：¬sunny ∧ cold"] -->|"簡化律"| B["¬sunny"]
B -->|"Modus tollens，配前提 2"| C["¬swim"]
C -->|"Modus ponens，配前提 3"| D["canoe"]
D -->|"Modus ponens，配前提 4"| E["early：結論"]
「只有天晴我們才游泳」，符號化是？
由 (p ∧ q) ∨ r 與 r → s 推 p ∨ s：
肯定後件、否定前件看起來像規則，其實都無效。
| 謬誤 | 形式 | 像哪條有效規則 |
|---|---|---|
| 肯定後件 | p → q，q ∴ p | Modus ponens |
| 否定前件 | p → q，¬p ∴ ¬q | Modus tollens |
例子 p82
「做完每題就會學會離散；你學會了；所以做完每題。」你可能沒做完，靠別的方法學會（p = F、q = T）。坑
「若下雨，地會濕。地是濕的。所以下過雨。」
UI 和 EG 隨時能用；EI 的 c 要是新名字；UG 的 c 要是任意元素。
| 規則 | 形式 | 限制 |
|---|---|---|
| UI 全稱個例化 | ∀x P(x) ∴ P(c) | 隨時可用，c 是論域中任何元素 |
| EG 存在通則化 | P(c) ∴ ∃x P(x) | 隨時可用 |
| EI 存在個例化 | ∃x P(x) ∴ P(c) | c 必須是新名字，代表「某個我不知道是誰的元素」 |
| UG 全稱通則化 | P(c) ∴ ∀x P(x) | c 必須是任意元素，不能是 EI 來的 |
flowchart LR
A["∀x P(x)"] -->|"UI：隨時可用"| B["P(c)"]
B -->|"EG：隨時可用"| C["∃x P(x)"]
C -->|"EI：c 要是新名字"| B
B -->|"UG：c 要是任意元素"| A
「Marla 修過資工的課。所以有人修過資工的課。」用哪條？
先 EI 取新名字 c，再 UI 代同一個 c，接命題規則，最後 EG 或 UG。
flowchart TD
A["有 ∃ 的前提：先 EI，取新名字 c"] --> B["有 ∀ 的前提：UI，代同一個 c"]
B --> C["用命題規則推理：簡化、肯定前件、否定後件、選言三段論、連言"]
C --> D{"結論是 ∃ 還是 ∀"}
D -->|"∃"| E["EG：存在通則化"]
D -->|"∀"| F["UG：c 必須是任意元素"]
前提 ∀x (P(x) → Q(x)) 與 ∃x (R(x) ∧ ¬Q(x))，第一步做什麼？
p85UI ＋ modus ponens：每個班上的人都修過資工，Marla 在班上，所以 Marla 修過資工。
p86EI → UI → 命題規則 → EG：班上有人沒讀過書，班上每個人都通過考試，所以有人通過考試但沒讀過書。
EI 的 c 不能重複用、不能亂 UG、不能亂簡化條件句。
坑
1. ∃x P(x) 前提 2. P(c) EI，用 1 3. ∀x P(x) UG，用 2。錯在哪？
簡化律只適用於 A ∧ B。P → (Q ∧ S) 是條件句，要先有 P，用 modus ponens 得到 Q ∧ S，再簡化。
練功 1 112-5 原題（＝p88）
Use rules of inference to show that if ∀x (P(x) → (Q(x) ∧ S(x))) and ∀x (P(x) ∧ R(x)) are true, then ∀x (R(x) ∧ S(x)) is true.（15 分）
流程：UI（同一個 c）→ 命題規則 → UG。
第 6 到 8 行要先 modus ponens 再簡化，不要把條件句直接「簡化」成 P(c) → S(c)。
練功 2 110-4 原題＝109-5
Use rules of inference to show that if ∀x (P(x) ∨ Q(x)), ∀x (¬Q(x) ∨ S(x)), ∀x (R(x) → ¬S(x)) and ∃x ¬P(x) are true, then ∃x ¬R(x) is true.（10 分）
第 8 行（選言三段論）把 Q(c) 當成 ¬Q(c) 的否定；第 11 行（modus tollens）把 S(c) 當成 ¬S(c) 的否定。這兩步都悄悄用了雙重否定。也可以用預解律走（109 學生就是這樣）。
練功 3 108-4 原題（107-4(d) 同一推論）
(108-4) Use rules of inference to show that if ∀x (P(x) → Q(x)) and ∃x (R(x) ∧ ¬Q(x)) are true, then ∃x (R(x) ∧ ¬P(x)) is true.（10 分）
(107-4) P(x)：清楚的解釋，Q(x)：令人滿意，R(x)：藉口。(a) 所有清楚的解釋都令人滿意。(b) 有些藉口不令人滿意。(c) 有些藉口不是清楚的解釋。把 (a)(b)(c) 寫成量詞式，並回答 (c) 是否由 (a)(b) 推得；是的話請證明。（20 分）
107-4 翻譯：(a) ∀x (P(x) → Q(x))；(b) ∃x (R(x) ∧ ¬Q(x))；(c) ∃x (R(x) ∧ ¬P(x))。「所有 A 都 B」配 →；「有些 A 不是 B」配 ∧。答案是是，(c) 可由 (a)(b) 推得；只寫 yes 會被扣 5 分。
白話：有個藉口不令人滿意；清楚的解釋都令人滿意，所以這個藉口不是清楚的解釋。
練功 4 112-7 ≈ 108-8
Show that the argument is valid or not.（10 至 15 分）
p → q
¬p → r
r → s
∴ ¬q → s
（112-7 文字版：寄信我就寫完程式；不寄信就早睡；早睡就神清氣爽；結論：沒寫完程式，起床就神清氣爽。p 寄信、q 寫完程式、r 早睡、s 神清氣爽。）
有效。
另一種走法（預解律）：子句 ¬p ∨ q、p ∨ r、¬r ∨ s。前兩個消掉 p 得 q ∨ r；再和 ¬r ∨ s 消掉 r 得 q ∨ s，而 q ∨ s ≡ ¬q → s。
1.7 · 投影片 p89–104
學完你能：看到定理，知道開頭寫什麼、寫到哪算完。
小考：逆否＋矛盾 110–107 每年一題（兩小題），n³+5 原題考過三次。
開頭假設什麼、中間憑什麼、結尾推出什麼。
例子
證「n 奇 → n² 奇」：開頭寫「設 n = 2k+1」，中間展開，結尾寫「所以 n² 是奇數」。
flowchart LR
A["開頭：假設什麼"] --> B["中間：憑什麼推"] --> C["結尾：回到定義，寫所以成立"]
證明寫到哪裡才算完？
| 英文 | 中文 | 意思 |
|---|---|---|
| theorem | 定理 | 可以被證明為真的敘述 |
| axiom | 公理 | 直接假定為真、不需證明 |
| lemma | 引理 | 用來幫忙證明別的結果的次要定理 |
| corollary | 推論 | 由已證明的定理直接推得 |
| conjecture | 猜想 | 真假還沒被證明（就算大家都相信） |
證明第一步：把文字換成式子。
公理
每個整數不是奇數就是偶數，不會兩者都是。所以「n 不是奇數」可以改寫成「n 是偶數」。
「n 不是奇數」，第一步該寫成什麼？
偶數：存在整數 k 使 n = 2k。奇數：存在整數 k 使 n = 2k+1。有理數：存在整數 p、q，q ≠ 0，使 r = p/q。不是有理數的實數叫無理數（irrational number）。
先看 p 好不好用；不好用就看 ¬q 好不好算。
flowchart TD
A["要證 若 p 則 q"] --> B{"前提 p 好用嗎"}
B -->|"好用"| C["直接證明：假設 p 推出 q"]
B -->|"不好用"| D{"否定結論好算嗎"}
D -->|"好算"| E["逆否證明：假設 非q 推出 非p"]
D -->|"都卡住"| F["矛盾證明：假設 p 且 非q 推出矛盾"]
例子
「若 3n+2 為奇，則 n 為奇」：p 不好用；¬q 是 n 為偶，寫成 2k 很好算，走逆否。
「若 n² 為偶，則 n 為偶」，¬q 是「n 為奇」可寫成 2k+1。該走哪種？
假設 p 成立，一路算到 q。
證明骨架：直接證明
例子：n 奇 → n² 奇
flowchart LR
A["假設 p"] --> B["依定義寫成式子"] --> C["代數推導"] --> D["整理成 q 的形式"] --> E["所以 q"]
n = 2k+1，n² 整理成奇數的形式是？
設 r = p/q、s = t/u（q、u ≠ 0）。r + s = (pu + qt)/(qu)。pu+qt 與 qu 都是整數，且 qu ≠ 0，所以 r + s 是有理數。
直接證卡住時，改假設 ¬q，去證 ¬p。
證明骨架：逆否證明
例子：3n+2 奇 → n 奇
假設 ¬q：n 是偶數，n = 2k。3n+2 = 6k+2 = 2(3k+1)，是偶數，即 ¬p。得證。
坑
flowchart LR
A["假設 非q"] --> B["依定義寫成式子"] --> C["代數推導"] --> D["得到 非p"] --> E["逆否成立，故 p 推 q 成立"]
逆否證「若 n² 為偶，則 n 為偶」，開頭假設？
假設 p 成立且 q 不成立，推出某句話又真又假。
證明骨架：矛盾證明
例子：22 天中有 4 天同星期幾
假設不成立：每個星期幾至多 3 次。7 × 3 = 21 天，但選了 22 天，矛盾。
坑
flowchart LR
A["假設 p 且 非q"] --> B["代數推導"] --> C["撞牆：某句話又真又假"] --> D["假設不成立，故 p 推 q 成立"]
矛盾證「若 n² 為偶，則 n 為偶」，開頭假設？
p ↔ q 要兩個方向各證一次。
證明骨架：等價證明
例子：n 奇 ↔ n² 奇
(⇒) 直接證明（前面做過）。(⇐) 逆否：n 偶，n = 2k，n² = 2(2k²) 偶。
要證「p 若且唯若 q」，至少要證？
空泛看前提恆假，平庸看結論恆真。
例子
「若 n 是兩個質數的和，則 n 是奇數或偶數」：結論對每個整數都真，平庸證明。
「若 n 既奇又偶，則 n² = n + n」是哪種證明？
一個反例推翻「對所有」；舉再多例子也證不了。
例子
「每個正整數都是兩個整數的平方和」是假的，反例 3：平方數只有 0、1、4…，兩個相加湊不出 3。
坑
哪個寫法能證「n 偶 → n²+n 偶」？
練功 1 110-5 ＝ 108-6 ＝ 107-6 原題 (a)
練功 2 110-5 ＝ 108-6 ＝ 107-6 原題 (b)
與逆否的差別：逆否起點只有 ¬q，矛盾起點是 p ∧ ¬q 兩個。
練功 3 109-6 原題
(a) 逆否
(b) 矛盾：假設 3n+2 是偶數且 n 是奇數。
練功 4 110-6 ＝ 109-7 原題
1.8 · 投影片 p105–116
學完你能：看出定理的形狀，寫出 √2 那種存在證明。
小考：非構造式存在證明 112-8、108-7、107-7 各 10 分，其餘沒單獨考。
先看定理長什麼樣，再選方法。
flowchart TD
A["看定理長什麼樣"] --> B["案例很少"] --> B2["窮舉證明"]
A --> C["前提能分類"] --> C2["分案證明"]
A --> D["有某個東西"] --> D2["存在證明"]
A --> E["恰好一個"] --> E2["唯一性證明"]
定理說「恰好有一個實數 r 使 3r + b = 0」，用哪種？
| 定理的形狀 | 方法 |
|---|---|
| 只需檢查很少的幾個情形 | 窮舉證明 exhaustive proof |
| 前提可以分成幾類 | 分案證明 proof by cases |
| ∃xP(x)（唸「存在 x 使 P(x) 成立」） | 存在證明（構造式或非構造式） |
| 斷言「恰好有一個」 | 唯一性證明（存在＋唯一） |
案例少到能一個一個代，就全部算一遍。
例子：n ≤ 4 時 (n+1)³ ≥ 3ⁿ
n = 1, 2, 3, 4 時，(n+1)³ = 8, 27, 64, 125，3ⁿ = 3, 9, 27, 81，四個都成立，得證。
上面那題，若改成 n ≤ 5，還成立嗎？
投影片印的是 (n+1)² ≥ 3ⁿ，疑似把三次方打成平方。照平方版，n = 3 時 16 < 27，命題為假。學習以三次方版本為準；考卷若真是平方版，窮舉到 n = 3 就回答「命題為假」。
前提能分成幾類，每類各證一次，但要涵蓋全部。
證明骨架：分案證明
例子：|x| ≥ x
案例 x ≥ 0：|x| = x，成立。案例 x < 0：|x| = −x > 0 > x，成立。兩案涵蓋所有實數。
flowchart TD
A["任意實數 x"] --> B["案例 1：x 大於等於 0"]
A --> C["案例 2：x 小於 0"]
B --> D["各案都證完，且涵蓋全部，故成立"]
C --> D
證一個關於所有實數 x 的敘述，哪種分案有漏洞？
|xy| = |x||y|：x、y 各有「≥ 0」「< 0」兩種，共四案。(i) 都 ≥ 0：|xy| = xy。(ii) x ≥ 0、y < 0：|xy| = −xy = x(−y)。(iii) 與 (ii) 對稱。(iv) 都 < 0：xy = (−x)(−y)。四案都等於 |x||y|。
完全平方的個位數：n = 10a + b，n² 的個位數等於 b² 的個位數。b 與 10−b 的平方個位數相同，只要分六案，結果只會是 0、1、4、5、6、9。（投影片最後一行多印了 2，是筆誤。）
直接拿出一個具體的例子，並驗算。
例子：存在 n 有兩種立方和寫法
取 n = 1729：9³ + 10³ = 729 + 1000 = 1729，1³ + 12³ = 1 + 1728 = 1729。給出具體的數並驗算，證畢。
要證「存在 r 使 ar + b = 0」（a ≠ 0），取 r = −b/a 代入驗證，是哪種？
1729 這個數出自拉馬努金的故事，投影片 p111 的例題。
不知道 (√2)^(√2) 有理還無理，兩種情形各給一組。
證明骨架：非構造式存在
flowchart TD
A["z = (√2)^(√2) 是有理或無理"] --> B["情形 1：z 有理"]
A --> C["情形 2：z 無理"]
B --> D["取 x = √2 且 y = √2，x^y = z 有理"]
C --> E["取 x = z 且 y = √2，x^y = 2 有理"]
D --> F["兩情形涵蓋全部，所以存在"]
E --> F
例子：x、y 無理，x^y 有理
情形 2 算式：((√2)^(√2))^(√2) = (√2)^(√2·√2) = (√2)² = 2，是有理數。
哪個證明屬於非構造式存在證明？
定理：存在無理數 x、y 使 x^y 是有理數。已知 √2 是無理數（1.7 證過）。令 z = (√2)^(√2)。情形 1：z 有理，取 x = y = √2。情形 2：z 無理，取 x = z、y = √2，x^y = 2。z 不是有理就是無理，兩情形涵蓋全部。
兩情形必有一種為真，各自都推得結論。
坑
flowchart TD
A["z 不是有理就是無理，必有一種為真"] --> B["有理：結論成立"]
A --> C["無理：結論成立"]
B --> D["不必知道是哪一種，結論都成立"]
C --> D
為什麼不用判斷 z 到底是有理還是無理？
用比較深的定理可證 z 其實是無理數，所以真正符合的是情形 2。但本課不需要這個事實，證明也不依賴它。
「恰好一個」要證兩段：存在，加上唯一。
證明骨架：唯一性證明
例子：3r + b = 0 恰有一解
存在：r = −b/3。唯一：設 3s + b = 0，則 3s = 3r，s = r。
flowchart LR
A["要證恰好一個"] --> B["第一步 存在：構造 r 並驗算"] --> C["第二步 唯一：設 s 也滿足，證 s = r"] --> D["存在且唯一，故恰有一個"]
只證出「r = −b/a 是一個解」，夠證「恰好一個」嗎？
往前推、往回推，或找反例。
例子：(x+y)/2 ≥ √(xy)
倒推：等價於 (x+y)² ≥ 4xy，等價於 (x−y)² ≥ 0，明顯成立。正式證明要從 (x−y)² ≥ 0 往前寫。
往回推找到路之後，正式證明該怎麼寫？
證 ∀xP(x) ∨ ∀xQ(x) 與 ∀x(P(x) ∨ Q(x)) 不等價。論域取正整數，P：x 是奇數，Q：x 是偶數。後者為真（非奇即偶）；前者中 ∀xP(x) 因 2 不是奇數而假，∀xQ(x) 因 1 不是偶數而假，所以前者為假。一真一假，不等價。
練功 1 112-8 原題
這是非構造式證明：沒決定 z 屬於哪一種，所以沒指出是哪一組。
練功 2 108-7 原題
原意版：令 z = (√2)^(√2)。z 有理取 (√2, √2)；z 無理取 (z, √2)，x^y = 2。
字面版：取 x = √2、y = log₂3。
考試建議兩個版本都寫：先照字面證，再註明「若題意為 rational」，寫 (√2)^(√2) 的分案證明。
為什麼不取 x = y = √2：要知道 (√2)^(√2) 無理，需要 Gelfond–Schneider 定理，超出本課。
練功 3 107-7 原題
套路：選一個不知有理無理的 z，一個情形直接用 z，另一個情形把 z 配另一個數湊出結果。
練功 4 課本 p115
2.1 · 投影片 p3–18
學完你能：看一串集合式子，判斷 ∈、⊆、冪集合、笛卡兒積的真假。
小考：五年都考，累計 66 分（集合 T/F 46 分、冪集合 20 分）；112-1 與 109-8 是同一題。
集合是一袋東西：只看袋子裡有什麼，不看順序，也不看重複。
例子
V = {a, e, i, o, u}：a ∈ V 為真，b ∈ V 為假。|S|（唸「S 的基數」）是不同元素的個數：|{1,2,2,3}| = 3，|{{1,2,3},{4,5}}| = 2。 p3–5p7p12|{a, a, b, a, b}| 是多少？
兩種寫法：列舉 V = {a, e, i, o, u}，或條件式（集合建構符號）O = {x | x 是正奇數}，「|」唸「滿足」。第三種是 Venn 圖（p5–6，U 是宇集）。
常見的無限集合（p8）：N = {1, 2, …}、Z = {…, −2, −1, 0, 1, 2, …}、R 是實數。p17 的真值集合：{x ∈ Z | |x| = 1} = {−1, 1}；x² = 2 在整數裡沒有解，所以是 ∅；|x| = x 的解是全部非負整數。
投影片小瑕疵：p8 的 N 不含 0，但 p12 說「|S| ∈ N 就是有限集」，例子又有 |∅| = 0。意思是「有限」，別糾結 N 含不含 0。p3 提到集合論由 Boole 和 Cantor（康托爾）在十九世紀後期發展。
X ⊆ Y（唸「X 是 Y 的子集」）：X 的每一項都在 Y 裡，兩邊一樣也算。
例子
{1,2} ⊆ {1,2,3} 真；{1,2} ⊆ {1,2} 真；{1,2} ⊂ {1,2} 假（兩邊一樣，不是真子集）。 p9坑
{3} ⊆ {3} 為真還是假？
定理（p10）：對任何集合 S，∅ ⊆ S 且 S ⊆ S。所以非空集合至少有兩個子集：∅ 和它自己。
∅ ＝ { }，沒有任何元素，而且是每一個集合的子集。
例子
∅ ⊆ {1} 真（子集）；∅ ⊂ {1} 真（真子集）；∅ ∈ {1} 假，因為 {1} 的唯一一項是 1。 p9–10坑
下列哪一個為真？
為什麼 ∅ ⊆ S？「∅ 的每一項都在 S 裡」沒有任何一項能違反這句話，所以成立。這和 1.1 的「前件為假的條件句為真」是同一個道理（空泛成立）。
∅ 是空袋子；{∅} 是裝著一個空袋子的袋子，有 1 項。
| 式子 | 真假 | 理由 |
|---|---|---|
| ∅ ∈ {∅} | 真 | 唯一一項就是 ∅ |
| {∅} ∈ {∅} | 假 | 唯一一項是 ∅，不是 {∅} |
| ∅ ⊆ {∅} | 真 | ∅ 是任何集合的子集 |
| {∅} ⊆ {∅} | 真 | 左邊的 ∅ 在右邊裡（⊆ 允許相等） |
例子
空紙袋裡面 0 個東西；一個裝著空紙袋的紙袋，裡面 1 個東西。 p13flowchart LR
E["∅ 大小 0"] --> E0["（裡面沒有東西）"]
S["{∅} 大小 1"] --> S1["∅"] --> S0["（裡面沒有東西）"]
上排是空袋子；下排是袋子裡多裝了一個空袋子。
|{∅}| 是多少？
這幾列就是 107-5 (a)(b) 與 112-1 (j) 的考法：先把最外層大括號拆開，看裡面裝了什麼，再比較。
元素也可以是集合；1、{1}、{{1}} 是三個不同的東西。
例子
S = {1, {1}, {{1}}} 有 3 項。{1} ∈ {{1}} 真；1 ∈ {{1}} 假，因為 {{1}} 裡面沒有裸的 1。 p11坑
flowchart LR
A["{{1}}"] -->|"唯一一項"| B["{1}"] -->|"唯一一項"| C["1"]
每個箭頭是一次 ∈：{1} ∈ {{1}}、1 ∈ {1}；但 1 ∈ {{1}} 要跳兩層，所以假。
下列哪一個為真？
p11 的例子：S = {x | x ⊆ {1,2,3}} 的每一項本身都是集合：∅、{1}、{2}、{3}、{1,2}、{1,3}、{2,3}、{1,2,3}，共 8 項。這就是下面的冪集合。
∈ 只問最外層的「整塊」；⊆ 要把左邊拆開，每一項都檢查。
flowchart TD
A["看到 左邊 ? 右邊"] --> B{"符號是哪一個？"}
B -->|屬於 ∈| C["拆開右邊最外層，列出每一項"]
C --> D["左邊整塊有在裡面嗎？"]
B -->|子集 ⊆| E["拆開左邊最外層，列出每一項"]
E --> F["每一項都在右邊的項裡嗎？"]
| 式子 | 真假 | 怎麼想 |
|---|---|---|
| {x} ∈ {{x}} | 真 | {{x}} 的唯一一項就是 {x} |
| {x} ∈ {x} | 假 | {x} 的唯一一項是 x |
| {x} ⊆ {x} | 真 | 左邊拆開只有 x，在右邊裡 |
| {x} ⊆ {{x}} | 假 | 左邊拆開是 x，右邊的項是 {x}，沒有 x |
{∅} ⊆ {{∅}} 為真還是假？
捷徑：{x} ⊆ Y 等於 x ∈ Y，把左邊的大括號拿掉再問「屬於嗎」。注意這招只對單項集合好用，多項時要每一項都檢查。
P(S) ＝ S 的所有子集排成的集合；S 有 n 項，P(S) 就有 2ⁿ 項。
例子
P({a,b}) = {∅, {a}, {b}, {a,b}}，4 項 ＝ 2²。|P({1,2,3})| = 8。 p13flowchart BT
E["∅ 0 項"] --> A["{a} 1 項"]
E --> B["{b} 1 項"]
A --> AB["{a,b} 2 項"]
B --> AB
P({a,b}) 的子集一層一層往上加元素：共 4 = 2² 個。
|P({1,2,3,4})| 是多少？
照「項數」分組列：0 項（∅）、1 項、2 項、…、全部（S 自己）。例：P({1,2,3}) ＝ ∅；{1}、{2}、{3}；{1,2}、{1,3}、{2,3}；{1,2,3}，共 1+3+3+1 = 8。列完要數一次是不是 2ⁿ 個。
P(∅) ＝ {∅}（1 項）；再套一層 P({∅}) ＝ {∅, {∅}}（2 項）。
考試寫法
112-3 (b)、108-5 (b) 都問 P(∅)，題目的寫法有兩種讀法。108 級有人只寫 {∅, {∅}} 被扣 5 分，112 級同樣答案卻被打勾。兩層都寫：P(∅) = {∅}，所以 P(P(∅)) = {∅, {∅}}。P(∅) 等於什麼？
連續套下去：|P(∅)| = 1、|P(P(∅))| = 2、|P(P(P(∅)))| = 4（每套一層，大小變成 2 的上一個大小次方）。考卷若寫「Find the power set of P(∅)」，被冪的集合就是 P(∅) 本身，答案是 {∅, {∅}}。
小括號 (a, b) 有順序；大括號 {a, b} 沒有順序。
例子
電影院座位「第 3 排第 5 號」寫成 (3, 5)，(5, 3) 是另一個位子。 p14下列哪一個為真？
兩個有序對相等，代表每一格都相同：(a,b) = (c,d) ⇔ a = c 且 b = d。
A × B（唸「A 叉 B」）＝ 所有 (a, b)，a 取自 A、b 取自 B。
例子
{a,b} × {1,2} = {(a,1), (a,2), (b,1), (b,2)}；{1,2} × {a,b,c} 有 2×3 = 6 項：(1,a) (1,b) (1,c) (2,a) (2,b) (2,c)。 p15–16坑
|A| = 3、|B| = 4，則 |A × B| 是多少？
p16 的學生×課程例子：A 是全校學生、B 是全校課程，A × B 的每一項 (a, b) 代表「學生 a 修課 b」這種可能性。
p15、p18：A × B × C 的項是三格的 (a, b, c)；(A × B) × C 的項是 ((a, b), c)，第一格是一個有序對，所以兩者不同。若有 A × ∅，沒有任何配對，結果是 ∅。
練功 1 112-1 原題 109-8 原題
Determine whether each of these statements is true or false. (10%)
(a) 0 ∈ ∅ (b) ∅ ∈ {0} (c) {0} ⊂ ∅ (d) ∅ ⊂ {0} (e) x ∈ {x}
(f) {x} ⊆ {x} (g) {x} ∈ {x} (h) {x} ∈ {{x}} (i) 0 ⊆ {x} (j) {{∅}} ⊂ {{∅},{∅}}
答案：(a) F (b) F (c) F (d) T (e) T (f) T (g) F (h) T (i) F (j) F
| 小題 | 答案 | 理由 |
|---|---|---|
| (a) | F | ∅ 沒有任何元素 |
| (b) | F | {0} 的唯一一項是數字 0，不是 ∅（∅ ⊆ {0} 才成立） |
| (c) | F | 非空集合不可能是 ∅ 的子集 |
| (d) | T | ∅ 是任何集合的子集，而且 ∅ ≠ {0}，所以是真子集 |
| (e) | T | x 就是 {x} 的那一項 |
| (f) | T | ⊆ 允許相等（112 級有人答 F，被扣分） |
| (g) | F | {x} 的唯一一項是 x，不是 {x} |
| (h) | T | {{x}} 的唯一一項正是 {x} |
| (i) | F | 0 是數字，不是集合；若題目是 ∅ ⊆ {x} 才為 T |
| (j) | F | {{∅},{∅}} 重複只算一個，等於 {{∅}}，兩邊相同，不是真子集 |
投影片 p18 的同型練習（答案已驗算）：(a) F (b) F (c) F (d) T (e) {0} ∈ {0} F (f) {0} ⊂ {0} F (g) {∅} ⊆ {∅} T；大小依序是 1、1、2、3。
練功 2 112-3 原題 108-5 原題
Find the power set of the following sets, where a and b are distinct elements. (10%)
(a) {a, b, {a, b}} (b) P(∅)
(a) 有 3 項，共 2³ = 8 個子集：
(b) P(∅) = {∅}（∅ 只有一個子集，2⁰ = 1 項）。P(P(∅)) = P({∅}) = {∅, {∅}}（2¹ = 2 項）。考試兩層都寫，並標明哪一個是 P(∅)、哪一個是 P(P(∅))。
陷阱：108 級有人寫「2¹ = 2，{∅,{∅}}」（也就是 P(P(∅))）被扣 5 分，但 112 級同樣的答案被打勾。題目的「P(∅)」兩種讀法都說得通，所以兩層都寫最保險。
練功 3 110-7 原題
Suppose A = {a, b, c}. Mark the following statements TRUE or FALSE. (16%)
(a) {b,c} ∈ P(A) (b) {{a}} ⊆ P(A) (c) ∅ ⊆ A (d) {∅} ⊆ P(A)
(e) ∅ ⊆ A × A (f) {a,c} ∈ A (g) {a,b} ∈ A × A (h) (c,c) ∈ A × A
答案：(a) T (b) T (c) T (d) T (e) T (f) F (g) F (h) T（已用程式列出 P(A)、A × A 逐項驗算：|P(A)| = 8、|A × A| = 9）
| 小題 | 答案 | 理由 |
|---|---|---|
| (a) | T | {b,c} 是 A 的子集，所以是 P(A) 的一項 |
| (b) | T | {{a}} 的唯一一項是 {a}，而 {a} ⊆ A，所以 {a} ∈ P(A) |
| (c) | T | ∅ 是任何集合的子集 |
| (d) | T | {∅} 的唯一一項是 ∅，而 ∅ ⊆ A，所以 ∅ ∈ P(A) |
| (e) | T | ∅ 是任何集合的子集 |
| (f) | F | {a,c} 是 A 的子集，不是 A 的一項（A 的項只有 a、b、c） |
| (g) | F | A × A 的項是有序對 (a,b)，不是集合 {a,b} |
| (h) | T | c ∈ A 且 c ∈ A，所以 (c,c) ∈ A × A |
2.2 · 投影片 p19–35
學完你能：算集合運算，並證明一條集合恆等式，或找出反例推翻它。
小考：112-6（20 分）、110-3（10 分）考集合恆等式的證明與證偽，累計 30 分；112 級集合題共 40 分。
A ∪ B（唸「A 聯集 B」）＝ 在 A「或」在 B 的所有元素，重複的只算一次。
例子
{2,3,5} ∪ {3,5,7} = {2,3,5,7}，3 和 5 只算一次。{a,b,c} ∪ {2,3} = {a,b,c,2,3}。 p19{1,2} ∪ {2,3} 等於什麼？
聯集有交換律和結合律，所以連續寫 A₁ ∪ A₂ ∪ … ∪ Aₙ 不用括號，簡寫成大 U 加上下標：⋃i=1n Ai；無限多個寫成 ⋃i=1∞ Ai（p32）。
A ∩ B（唸「A 交集 B」）＝ 同時在 A「且」在 B 的元素。
例子
{2,4,6} ∩ {3,4,5} = {4}；{a,b,c} ∩ {2,3} = ∅；偶數集和奇數集不相交。 p20–21|A| = 5、|B| = 4、|A ∩ B| = 2，則 |A ∪ B| 是多少？
交集也有交換律和結合律，連續交集寫成大 ∩ 加上下標：⋂i=1n Ai，無限多個寫成 ⋂i=1∞ Ai（p33）。排容原理（排容 ＝ 排除重複、容納全部）在 p21。
A − B ＝ 在 A 裡、但不在 B 裡的元素；先改寫成 A ∩ Bc 最好用。
例子
{1,2,3,4,5,6} − {2,3,5,7,9,11} = {1,4,6}。7、9、11 本來就不在 A 裡，不用管。 p22坑
{1,2,3} − {3,4,5} 等於什麼？
投影片還寫成 A − B = {x | ¬(x ∈ A → x ∈ B)}：「x ∈ A 但 x ∉ B」正好就是「x ∈ A → x ∈ B 為假」（1.1 的 → 只有前真後假才是 F）。
Ac（唸「A 補集」）＝ 宇集 U 裡不在 A 的元素，也就是 U − A。
例子
U ＝ 26 個英文字母，A = {a,e,i,o,u}，則 Ac 是 21 個子音。U ＝ 正整數、A ＝ 大於 10 的數，則 Ac = {1,2,…,10}。 p23–24U = {1,…,6}、A = {2,4,6}，則 Ac 是什麼？
p34：宇集 U = {1,…,10}，每個元素一個位元，在集合裡是 1，不在是 0。奇數集合 {1,3,5,7,9} ＝ 1010101010。補集 ＝ 每個位元翻面；∪ ＝ 逐位元 OR；∩ ＝ 逐位元 AND；A − B ＝ A AND（NOT B）。
例：A ＝ 奇數 1010101010，B ＝ {1,2,3,4,5} ＝ 1111100000，則 A ∪ B ＝ 1111101010，A ∩ B ＝ 1010100000，A − B ＝ 0000001010，Ac ＝ 0101010101。
A ⊕ B ＝ 只在其中一邊的元素，兩邊都有的拿掉。
例子
{1,2,3} ⊕ {3,4,5} = {1,2,3,4,5} − {3} = {1,2,4,5}。 p25{1,2} ⊕ {2,3} 等於什麼？
If A ⊕ B = C, then A ⊕ C = B and B ⊕ C = A：為真。因為 ⊕ 有結合律，而且 A ⊕ A = ∅、∅ ⊕ B = B：A ⊕ C = A ⊕ (A ⊕ B) = (A ⊕ A) ⊕ B = ∅ ⊕ B = B，另一式同理（已用程式對 {1,2,3,4} 的所有子集驗算）。
集合律和 1.3 的等價律是同一套：∪ 對 ∨、∩ 對 ∧、補集對 ¬。
| 名稱 | 第一式 | 第二式 |
|---|---|---|
| 同一律 | A ∪ ∅ = A | A ∩ U = A |
| 支配律 | A ∪ U = U | A ∩ ∅ = ∅ |
| 冪等律 | A ∪ A = A | A ∩ A = A |
| 補集律（雙重補集） | (Ac)c = A | （只有一條） |
| 交換律 | A ∪ B = B ∪ A | A ∩ B = B ∩ A |
| 結合律 | A ∪ (B ∪ C) = (A ∪ B) ∪ C | A ∩ (B ∩ C) = (A ∩ B) ∩ C |
| 分配律 | A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) | A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) |
| 笛摩根定律 | (A ∪ B)c = Ac ∩ Bc | (A ∩ B)c = Ac ∪ Bc |
| 吸收律 | A ∪ (A ∩ B) = A | A ∩ (A ∪ B) = A |
| 補律 | A ∪ Ac = U | A ∩ Ac = ∅ |
(A ∪ B)c 等於什麼？
這張表是投影片 p26（課本 Table 1）。所有恆等式都用程式對 {1,2,3,4} 的全部子集組合驗算過。為什麼和等價律一樣？因為 x ∈ A ∪ B 就是 x ∈ A ∨ x ∈ B，集合恆等式只是把邏輯等價律換了一層寫法。
證 E₁ = E₂ 有三招；說「不成立」只要一個反例。
flowchart TD
A["題目：E₁ = E₂ 對嗎？"] --> B{"覺得成立還是不成立？"}
B -->|成立| C["選一招來證"]
C --> D["招 1：互為子集"]
C --> E["招 2：建構式加等價律"]
C --> F["招 3：成員表，最機械不會漏"]
B -->|不成立| G["找一個反例就夠"]
G --> H["看成員表兩欄不同的那一列"]
考試
110-3 的卷面附註：只畫 Venn 圖很難拿滿分，因為三個集合的位置關係不只一種，除非把所有情形都畫出來。 p27要證「對所有集合 A、B、C 恆等式都成立」，哪一個夠？
三招可以混用：成員表最不會出錯、但畫起來要時間；推導（招 2）最短，但要先把 − 改成 ∩c；互為子集（招 1）適合帶「若…則」的題目，例如 112-6 (d)。
E₁ ⊆ E₂ 和 E₂ ⊆ E₁ 各證一次，每次都從「任取一個 x」開始。
例子（p28）
證 A ∩ (B ∪ C) ⊆ (A ∩ B) ∪ (A ∩ C)：設 x 在左邊。則 x ∈ A，且 x ∈ B 或 x ∈ C。案 1：x ∈ B，所以 x ∈ A ∩ B。案 2：x ∈ C，所以 x ∈ A ∩ C。兩案都得 x ∈ (A ∩ B) ∪ (A ∩ C)。 p28坑
證 E₁ ⊆ E₂ 的第一步是什麼？
證 (A ∩ B) ∪ (A ∩ C) ⊆ A ∩ (B ∪ C)：設 x 在左邊。案 1：x ∈ A ∩ B，則 x ∈ A 且 x ∈ B，因為 B ⊆ B ∪ C，所以 x ∈ B ∪ C，得 x ∈ A ∩ (B ∪ C)。案 2：x ∈ A ∩ C，同理。兩個方向都完成，所以兩邊相等。
把「x 屬於左邊」一步步改寫成「x 屬於右邊」，每步用定義或一條等價律。
例子（p29）：(A ∩ B)c = Ac ∪ Bc
x ∈ A − B 要改寫成什麼？
為什麼這招可行：每一個 ⇔ 都是「集合的定義」或「1.3 的邏輯等價」，鏈子頭到尾都成立，所以 x 屬於左邊 ⇔ x 屬於右邊，兩個集合就相等。
像真值表：1 ＝ 元素在這個集合，0 ＝ 不在；3 個集合畫 8 列。
| 運算 | 這一欄何時是 1 |
|---|---|
| A ∪ B | A、B 至少一個是 1 |
| A ∩ B | A、B 都是 1 |
| A − B | A 是 1 而且 B 是 0 |
| Ac | A 是 0（把 0 和 1 對調） |
| A ⊕ B | A、B 不同 |
例子（p31）：(A ∪ B) − C = (A − C) ∪ (B − C)
| A | B | C | A∪B | (A∪B)−C | A−C | B−C | (A−C)∪(B−C) |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
標色的兩欄逐列相同（0, 0, 1, 0, 1, 0, 1, 0），所以恆等式成立。
坑
成員表的一列 (A, B, C) = (1, 0, 1) 代表什麼情形？
證 (A ∪ B) − B = A − B，4 列，標色兩欄相同：
| A | B | A∪B | (A∪B)−B | A−B |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 0 |
| 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 |
說「不成立」只要一組具體集合；成員表兩欄不同的那列就是線索。
例子：(A ∪ B) − A = B ?
| A | B | A∪B | (A∪B)−A | B |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 0 |
| 1 | 1 | 1 | 0 | 1 |
(1, 1) 那列兩欄不同：元素在 A 也在 B。取 A = B = {1}：左邊 ({1} ∪ {1}) − {1} = ∅，右邊 B = {1}，不相等，所以不成立。
要推翻「A ∪ C = B ∪ C 則 A = B」，哪組是反例？
找不到反例不等於成立：成員表要把 8 列都檢查完，沒有任何一列不同才算證完。112-6 (d)「若 A ∩ B = A ∪ B 則 A = B」就是找不到反例的那種，要用招 1 證。
練功 1 112-6 原題（題幹整理過）
Let A, B, and C be sets. Mark each statement TRUE or FALSE and explain your answer. (20%)（橫線＝補集，這裡寫成 c）
(a) A − (B − C) = (A − B) − C (b) (A ∪ Bc)c ∪ Ac = Ac
(c) (A − C) − (B − C) = A − B (d) 若 A ∩ B = A ∪ B，則 A = B (e) 若 A ∪ C = B ∪ C，則 A = B
答案：(a) F (b) T (c) F (d) T (e) F（已用程式對 {1,2,3} 的全部子集組合驗算）
| 小題 | 答案 | 說明 |
|---|---|---|
| (a) | FALSE | 成員表 (A,B,C) = (1,0,1) 與 (1,1,1) 兩列不同。反例：A = C = {1}、B = ∅。左邊 {1} − (∅ − {1}) = {1}，右邊 ({1} − ∅) − {1} = ∅ |
| (b) | TRUE | (A ∪ Bc)c = Ac ∩ B（笛摩根加雙重補集），所以左邊 (Ac ∩ B) ∪ Ac = Ac（吸收律） |
| (c) | FALSE | 成員表 (1,0,1) 那列不同。反例：A = C = {1}、B = ∅。左邊 ({1} − {1}) − (∅ − {1}) = ∅，右邊 A − B = {1} |
| (d) | TRUE | 設 A ∩ B = A ∪ B。A ⊆ A ∪ B = A ∩ B ⊆ B，且 B ⊆ A ∪ B = A ∩ B ⊆ A，所以 A = B |
| (e) | FALSE | 聯集沒有消去律。反例：A = {1}、B = ∅、C = {1}，兩邊聯集都是 {1}，但 A ≠ B |
(a) 的成員表中 A − (B − C) 與 (A − B) − C 在 (1,0,1)、(1,1,1) 兩列不同；(b) 題卷面的橫線很容易看錯位置，先確認哪一段被整個蓋住。
練功 2 110-3 原題
Prove or disprove: A − (B ∩ C) = (A − B) ∪ (A − C). (10%)
答案：TRUE（成員表 8 列兩欄逐列相同，已用程式對所有子集組合驗算）。方法一：推導。
方法二：成員表（標色兩欄逐列相同）：
| A | B | C | B∩C | A−(B∩C) | A−B | A−C | (A−B)∪(A−C) |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
方法三（建構式）：x ∈ A − (B ∩ C) ⇔ x ∈ A ∧ ¬(x ∈ B ∧ x ∈ C) ⇔ x ∈ A ∧ (x ∉ B ∨ x ∉ C) ⇔ (x ∈ A ∧ x ∉ B) ∨ (x ∈ A ∧ x ∉ C) ⇔ x ∈ (A − B) ∪ (A − C)。
提醒：卷面附註，只畫 Venn 圖很難拿滿分，把上面任一種寫出來。
2.3 · 投影片 p36–56
學完你能：判斷一個對應是不是函數，並分辨一對一、映成、一一對應。
小考：不在小考 1 範圍，但後面章節（數列、基數）一直會用到。
函數＝每個輸入剛好配一個輸出。
例子
老師把成績配給每位學生：每人剛好拿到一個等第。這就是函數。
坑
A＝{小明, 小華}，B＝{A, B}。哪個是 A→B 的函數？
p37函數可以畫成：像文氏圖的箭頭、雙邊點線圖（bipartite graph）、或 x–y 座標圖。p54也可以寫成有序對集合 {(a, b) | f(a) = b}，例如 f(n)=2n+1 在整數上的圖是一堆點 (n, 2n+1)。
定義域＝輸入的集合，對應域＝你宣告輸出可以去哪。
例子
外送 App：定義域＝所有訂單，對應域＝{外送員 1, 2, 3}。每張訂單剛好配一位外送員。
f：訂單→外送員。「外送員 2」對 f 來說是什麼？
值域（range）是真的被打到的輸出，可以比對應域小。
例子（p39）
宣告「f 把全班配到等第 {A,B,C,D,E}」：對應域＝{A,B,C,D,E}。結果全班只拿 A 和 B，值域＝{A,B}，對應域仍是 {A,B,C,D,E}。
生活版：餐廳菜單有 10 道菜（對應域），今天只賣出 3 道（值域）。
坑
f：Z→Z，f(x)=x²。值域是？
p41程式語言的函式宣告就是在指定定義域與對應域，例如 int floor(float x)：定義域是實數，對應域是整數。p40ISBN 檢查碼 0-8065-0959-7：1·0+2·8+3·0+4·6+5·5+6·0+7·9+8·5+9·9 = 249，249 mod 11 = 7，這是一個「書號→0..10」的函數。
一對一＝不同輸入一定得到不同輸出。
口訣
反例只要找到「兩個不同輸入、同一個輸出」就破功。
例子
學號→學生：一個學號對一個人，一對一。
學生→生日月份：兩人同月，不是一對一。
| 箭頭長相 | 1-1？ |
|---|---|
| 每個輸出最多被一條箭頭打到 | 是 |
| 某個輸出被兩條箭頭打到 | 否 |
f：Z→Z，f(x)=x²，是一對一嗎？
p44範例 {a,b,c,d}→{1,2,3,4,5}，f(a)=4、f(b)=5、f(c)=1、f(d)=3：四個輸出互不相同，是一對一（5 個目標點只用了 4 個）。p46在實數上，嚴格遞增或嚴格遞減的函數一定一對一。p45若同一個輸入配到兩個輸出，連函數都不是。
映成＝對應域每個點都被打到，值域＝對應域。
口訣
找一個輸出「沒人要」就破功。
例子
f：{1,2,3,4}→{x,y}，1→x、2→x、3→y、4→y。x 和 y 都被打到，映成；但 1、2 撞在 x，不是一對一。
f：{1,2,3}→{a,b,c,d}，1→a、2→b、3→c。f 映成嗎？
投影片 p47 的四張圖：映成但非 1-1、非映成（有點沒被打到）、兩者皆是、1-1 但非映成（對應域多一個沒人要的點）。
一一對應＝一對一且映成，剛好兩邊一人配一人。
| 類型 | 一對一？ | 映成？ | 例子 |
|---|---|---|---|
| 只一對一 | 是 | 否 | {1,2,3}→{a,b,c,d} |
| 只映成 | 否 | 是 | {1,2,3,4}→{x,y} |
| 一一對應 | 是 | 是 | {a,b,c,d}→{1,2,3,4}，a→4、b→2、c→1、d→3 |
| 都不是 | 否 | 否 | {1,2}→{x,y,z}，全送到 x |
口訣
1-1 看「撞不撞」，onto 看「漏不漏」。
f：{a,b,c,d}→{1,2,3,4}，f(a)=4、f(b)=2、f(c)=1、f(d)=3。是一一對應嗎？
只有一一對應的函數才有反函數：把箭頭倒過來。
例子（p50）
f(a)=2、f(b)=3、f(c)=1，是一一對應。反函數：f⁻¹(1)=c、f⁻¹(2)=a、f⁻¹(3)=b。
坑
f：R→R，f(x)=2x+1。f⁻¹(5) 是多少？
p53函數與它的反函數合成（任何順序）會得到恆等函數：(f⁻¹∘f)(a)=a，(f∘f⁻¹)(b)=b。
f∘g＝先做 g，再做 f，由右往左。
例子
f(x)=x+1（加 1），g(x)=2x（乘 2）。f∘g(3)＝f(6)＝7；g∘f(3)＝g(4)＝8。順序一換，答案就不同。
坑
f(x)=x+1，g(x)=2x。(g∘f)(3) 是多少？
p52g：{a,b,c}→{a,b,c}，g(a)=b、g(b)=c、g(c)=a；f：{a,b,c}→{1,2,3}，f(a)=3、f(b)=2、f(c)=1。則 f∘g(a)=f(b)=2、f∘g(b)=f(c)=1、f∘g(c)=f(a)=3。g∘f 沒有定義，因為 f 的輸出 1,2,3 不在 g 的定義域 {a,b,c} 裡。
floor 往下取整，ceiling 往上取整；負數最容易錯。
| x | ⌊x⌋ | ⌈x⌉ |
|---|---|---|
| 0.5 | 0 | 1 |
| −0.5 | −1 | 0 |
| 3.1 | 3 | 4 |
| 7 | 7 | 7 |
坑
⌈−2.5⌉ 是多少？
p55階乘函數 f(n)=n! = 1·2·…·n，f：N→Z⁺，0!=1，6!=720。p42兩個 R 的函數可以相加相乘：(f₁+f₂)(x)=f₁(x)+f₂(x)，(f₁f₂)(x)=f₁(x)f₂(x)。例：f₁=x²、f₂=x−x² 則和＝x，積＝x³−x⁴。p43集合的映像 f(S)＝{f(s) | s∈S}：f(a)=2、f(b)=1、f(c)=4、f(d)=1、f(e)=1，S={b,c,d} 則 f(S)={1,4}。
練功 1 p56 練習
f：Z×Z→Z，哪些是映成（onto）？
a) f(m,n)=m+n b) f(m,n)=m²+n² c) f(m,n)=m d) f(m,n)=|n| e) f(m,n)=m−n
（d 的 |n| 是絕對值，投影片的直線符號。）
答案：a、c、e 映成；b、d 不映成。（python 在 −30..30 的輸入範圍驗算，−8..8 的輸出全被打到者只有 a、c、e。）
練功 2 p56 練習
下列 R→R 的函數，哪些是一一對應？
a) 2x+1 b) x²+1 c) x³ d) (x²+1)/(x²+2)
答案：a、c。
（投影片 p56 另有一題：f(x)=ax+b、g(x)=cx+d，求何時 f∘g=g∘f。f(g(x))=acx+ad+b，g(f(x))=acx+cb+d，所以條件是 ad+b = cb+d。已用 python 驗算。）
2.4 · 投影片 p57–74
學完你能：算出數列的項、解簡單遞迴、看懂 Σ 並算出常見的和。
小考：不在小考 1 範圍。目標是看得懂、會算基本題。
數列就是「排好順序的一串數」，第 n 項記成 an。
例子
an = 1/n（n ≥ 1），數列就是 1, 1/2, 1/3, 1/4, …。像是 Spotify 播放清單，第 3 首就是 a3。an = 1/n，那 a4 是多少？
投影片的正式說法：數列由一個「生成函數」f : S → A 決定，S 通常是 N 或 N−{0}。a1, a2, …, an 這種有限數列在資訊領域常被叫做字串（string）。數列有限的叫有限數列，一直列下去的叫無窮數列。
等比是一直「乘」同一個數，等差是一直「加」同一個數。
| 等比（幾何） | 等差（算術） | |
|---|---|---|
| 長相 | a, ar, ar², ar³, … | a, a+d, a+2d, a+3d, … |
| 首項、固定量 | 首項 a、公比 r | 首項 a、公差 d |
| 第 n 項（從 n=0 起） | cn = a·rⁿ | sn = a + n·d |
例子 p59p60
cn = 2·5ⁿ 得 2, 10, 50, 250, 1250, …（每次 ×5）。sn = −1+4n 得 −1, 3, 7, 11, 15, …（每次 +4）。3, 6, 12, 24, … 是哪一種？
遞迴關係＝「這一項怎麼從前面的項算出來」的公式。
例子（p61）
an = an−1 + 3，a0 = 2。an = 2·an−1，a0 = 1，則 a3 = ？
把遞迴一層層展開，直到看出 an 的直接公式。
例子：an = an−1 + 3，a0 = 2
用上面的公式，a10 = ？
投影片 p62 的起點寫成 a1 = 2，結果是 an = 2 + 3(n−1)；p61 的起點則是 a0 = 2。兩頁的起點編號不一致，所以公式差一格。本卡照 p61 的 a0 = 2 計算（即 an = 2+3n）。做題時看清楚是從 0 還是從 1 開始。
每年本金 ×1.11，所以 Pn = 1.11ⁿ × 10000。
例子
30 年後：P30 = 1.11³⁰ × 10000 ≈ 228,922.97 元。（P1 = 11,100、P2 = 12,321）本金 100、年利率 10% 複利，2 年後是多少？
給前幾項要猜規則：先看「加」、再看「乘」、再看「組合」。
例子（p64）
1, 2, 3, 4 → 5。1, 3, 5, 7, 9 → 11。2, 3, 5, 7, 11 → 13（質數）。1, 1, 2, 3, 5, 8, ? 下一項是？
p66 的 Table 1：n²：1, 4, 9, 16, 25…；n³：1, 8, 27, 64…；2ⁿ：2, 4, 8, 16…（從 n=1）；3ⁿ：3, 9, 27, 81…；n!：1, 2, 6, 24, 120…。Fibonacci 若從 f0 = 0、f1 = 1 起算，同樣得到 f2 = 1、f3 = 2。
p67 練習：5, 11, 17, …, 59 → an = 6n−1（n 從 1）。1, 7, 25, 79, 241, … → an = 3ⁿ−2（n 從 1），也可寫成 an = 3an−1+4。第三題 4, 9, 20, 35 的相鄰差是 5, 11, 15，沒有簡單規則，投影片也沒給答案，應是題目不完整，不用練。
Σ 是「把一串東西全部加起來」，上下標告訴你從哪加到哪。
例子（p69）
Σj=15 j² = 1 + 4 + 9 + 16 + 25 = 55。Σk=14 2k 的值是？
雙重 Σ 由內往外算：先把裡面那層算成一個數。
例子（p70）
Σi=14 Σj=13 ijΣi=12 Σj=13 1 的值是？
常見的和都有「一行公式」，直接代，不用一項項加。
| 和 | 結果 |
|---|---|
| Σk=0n ark | (arn+1 − a)/(r − 1)，r ≠ 1；r = 1 時是 (n+1)a |
| Σk=1n k | n(n+1)/2 |
| Σk=1n k² | n(n+1)(2n+1)/6 |
| Σk=1n k³ | n²(n+1)²/4 |
例子 p71p72
Σk=1100 k = 100·101/2 = 5050。Σk=04 3·2k = 3(2⁵−1)/(2−1) = 93。1 + 2 + 4 + 8 + 16 = ？
p72 還有無窮級數：Σk=0∞ xk = 1/(1−x)（|x| < 1）；Σk=1∞ kxk−1 = 1/(1−x)²（|x| < 1）。
p71 證明的想法：令 S = Σarj，則 rS = S + (arn+1 − a)，移項得 S(r−1) = arn+1 − a。
練功 1 p73 例題
（與投影片 p73 的答案相同。）
練功 2 p74 練習
以上已用程式驗算。投影片沒有給答案。
2.5 · 投影片 p75–81
學完你能：判斷一個無窮集合能不能排成一列，並說出對角線論證在幹嘛。
小考：不在小考 1 範圍。重點是看懂「可數」的意思。
基數＝集合的元素個數；無窮集合用「一一對應」比大小。
例子
全班的人和全班的座位：每人剛好坐一個位子、沒有空位，就知道人數＝座位數，連數都不用數。要說 |A| = |B|，需要什麼？
能排成一列、一個個編號下去的集合，叫可數。
例子
整數 0, 1, −1, 2, −2, 3, −3, … 正負交替就能排成一列，所以整數可數。「可數」最直白的意思是？
f(n) = 2n − 1 把每個正整數配到一個正奇數，剛好配完。
例子
正整數 1 2 3 4 5 …f(n) = 2n − 1，f(5) 配到哪個正奇數？
1-1 證明：若 f(n) = f(m)，則 2n−1 = 2m−1，所以 n = m。onto 證明：任何正奇數 t 比某個偶數 2k 小 1，即 t = 2k−1 = f(k)，k 是正整數。f 是一一對應，所以正奇數可數。
按 p+q = 2, 3, 4, … 一層一層列出 p/q，就排成一列了。
例子
排出來：1, 1/2, 2, 1/3, 3, 1/4, 2/3, 3/2, 4, 1/5, 5, …p+q = 4 這一層會跳過哪個？
要證實數不可數，先假設 0 到 1 的實數排得成一列。
想像一張無限大的表（舉例的數字）
| 第1位 | 第2位 | 第3位 | 第4位 | 第5位 | |
|---|---|---|---|---|---|
| r1 | 3 | 1 | 4 | 1 | 5 |
| r2 | 9 | 4 | 2 | 6 | 5 |
| r3 | 1 | 8 | 7 | 2 | 8 |
| r4 | 2 | 7 | 1 | 4 | 1 |
| r5 | 0 | 2 | 8 | 3 | 9 |
這個論證一開始「假設」的是什麼？
沿對角線，每一位都故意跟那個數「不一樣」，造出新數 r。
| 第1位 | 第2位 | 第3位 | 第4位 | 第5位 | |
|---|---|---|---|---|---|
| 對角線 | 3 | 4 | 7 | 4 | 9 |
| 新數 r | 4 | 5 | 4 | 5 | 4 |
接上一張的表
對角線是 3, 4, 7, 4, 9。對角線數字是 4, 4, 6，造出的 r 前三位是？
為什麼只用 4 和 5？因為 0.4999… = 0.5000… 這種「一個數兩種寫法」會讓「位數不同就是不同數」這句話不成立。只用 4 和 5 就不會遇到 0 或 9 結尾的問題。
新數 r 跟表裡每一列都至少有一位不同，所以 r 不在表裡。
flowchart LR A["假設實數排得成一列"] --> B["沿對角線造新數 r"] B --> C["r 和每一列都有一位不同"] C --> D["r 不在表裡，矛盾"] D --> E["所以實數不可數"]
例子
上表裡 r = 0.45454… 與 r1 = 0.31415… 第 1 位 4 ≠ 3；與 r5 第 5 位 4 ≠ 9。每一列都被「打槍」。為什麼 r 一定不等於 r7？
練功 1 p81 練習
投影片沒有給答案。
練功 2 p81 練習
投影片沒有給答案。
2.6 · 投影片 p82–98
學完你能：算矩陣的加、乘、轉置，並做 0-1 矩陣的 ∨、∧、布林積。
小考：不在小考 1 範圍；0-1 矩陣與布林積後面講關係與圖時會用到。
m×n 矩陣＝m 列（橫）、n 行（直），先講列再講行。
| 例：A（3×2） | |
|---|---|
| 2 | 3 |
| 5 | -1 |
| 7 | 0 |
例子
A 的 a21 ＝ 5（第 2 列第 1 行），a32 ＝ 0。上面的 A 中，a12 是多少？
p83兩個矩陣相等：列數相同、行數相同、每一格都相同。投影片的例子：2×2 的 [3 2; −1 6] 和 2×3 的 [3 2 0; −1 6 0] 不相等，因為大小不同。
p84列從上到下編 1 到 m，行從左到右編 1 到 n，寫成 A＝[aij]。
大小一樣才能加，對應的格子各加各的。
| A（2×2） | |
|---|---|
| 2 | 6 |
| 0 | -8 |
| B（2×2） | |
|---|---|
| 9 | 3 |
| -11 | 3 |
| A＋B（2×2） | |
|---|---|
| 11 | 9 |
| -11 | -5 |
2×3 矩陣能和 3×2 矩陣相加嗎？
算法例：2＋9＝11，6＋3＝9，0＋(−11)＝−11，−8＋3＝−5，與投影片 p85 相符。
A 的第 i 列 × B 的第 j 行，乘完加起來，得到 C 的 (i,j) 格。
| A（2×3） | ||
|---|---|---|
| 1 | 2 | 3 |
| 4 | 5 | 6 |
| B（3×2） | |
|---|---|
| 1 | 0 |
| 0 | 1 |
| 1 | 1 |
| AB（2×2） | |
|---|---|
| 4 | 5 |
| 10 | 11 |
例子
左上角：1·1＋2·0＋3·1 ＝ 4；右下角：4·0＋5·1＋6·1 ＝ 11。3×2 矩陣乘 2×4 矩陣，結果幾乘幾？
公式：cij ＝ Σℓ=1..k aiℓ bℓj（Σ 唸「sigma」，連加）。p87投影片完整例子放在練功 1。
矩陣乘法不能交換，順序換了答案就不同。
| A（2×2） | |
|---|---|
| 1 | 2 |
| 0 | 1 |
| B（2×2） | |
|---|---|
| 0 | 1 |
| 1 | 0 |
| AB（2×2） | |
|---|---|
| 2 | 1 |
| 1 | 0 |
| BA（2×2） | |
|---|---|
| 0 | 1 |
| 1 | 2 |
A 是 2×3、B 是 3×2，則 AB 和 BA 的大小？
上例 AB 的第 1 列是 [2 1]，BA 的第 1 列是 [0 1]，第一格就不同。
I 乘誰都不變；A⁻¹ 是讓 A⁻¹A＝I 的那個矩陣。
| I3（3×3） | ||
|---|---|---|
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 0 | 0 | 1 |
例子
數字世界的 1：乘誰都不變。反矩陣像「÷」：把 A 乘回 I。哪個矩陣一定沒有反矩陣？
2×2 反矩陣公式（投影片沒寫，後面練功用）：[a b; c d]⁻¹ ＝ 1/(ad−bc) · [d −b; −c a]，ad−bc≠0 才有。例：[2 3; 1 4]，ad−bc＝8−3＝5，反矩陣是 [4/5 −3/5; −1/5 2/5]，已驗算兩邊乘起來都是 I。[1 1; 1 1] 的 ad−bc＝0，沒有反矩陣。
轉置＝沿對角線翻過去，列變行；A＝Aᵗ 就是對稱。
| A（2×3） | ||
|---|---|---|
| 2 | 1 | 3 |
| 0 | -1 | -2 |
| Aᵗ（3×2） | |
|---|---|
| 2 | 0 |
| 1 | -1 |
| 3 | -2 |
下列哪個是對稱矩陣？
p92投影片「Which is symmetric?」三個矩陣：第 1 個 3×2（非方陣，不對稱）、第 2 個對稱、第 3 個不對稱。已用 python 驗算。
每格只有 0（F）或 1（T）；∨ 取 join，∧ 取 meet，各格各算。
| A（2×3） | ||
|---|---|---|
| 1 | 0 | 1 |
| 0 | 1 | 0 |
| B（2×3） | ||
|---|---|---|
| 0 | 1 | 0 |
| 1 | 1 | 0 |
| A∨B（2×3） | ||
|---|---|---|
| 1 | 1 | 1 |
| 1 | 1 | 0 |
| A∧B（2×3） | ||
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
1∨0、1∧0 依序是？
p94這就是投影片的例題。∨ 與 ∧ 的規則和 1.1 節的「或」「且」相同，1＝T、0＝F。meet 是「交」、join 是「聯」，跟集合的 ∩、∪ 概念類似。
走法跟矩陣乘法一樣，只是「乘」換成 ∧、「加」換成 ∨。
| A（3×2） | |
|---|---|
| 1 | 0 |
| 0 | 1 |
| 1 | 0 |
| B（2×3） | ||
|---|---|---|
| 1 | 1 | 0 |
| 0 | 1 | 1 |
| A⊙B（3×3） | ||
|---|---|---|
| 1 | 1 | 0 |
| 0 | 1 | 1 |
| 1 | 1 | 0 |
例子
左上角：(1∧1)∨(0∧0) ＝ 1∨0 ＝ 1；右上角：(1∧0)∨(0∧1) ＝ 0。列 [1 0 1] 與行 [0 1 1]（直的）的布林積那一格是？
p96投影片答案 [1 1 0; 0 1 1; 1 1 0]，已驗算，與投影片相符。
A 要是方陣才能連乘；A⁰＝I；布林冪次用 ⊙ 連乘，記成 A[k]。
| A（2×2） | |
|---|---|
| 2 | 1 |
| -1 | 0 |
| A²（2×2） | |
|---|---|
| 3 | 2 |
| -2 | -1 |
| A³（2×2） | |
|---|---|
| 4 | 3 |
| -3 | -2 |
例子
先算 A² 再乘 A（投影片 p90）：A³ ＝ [4 3; −3 −2]。D＝[1 1; 0 1]，布林冪次 D[2] 是？
布林冪次再一例：C＝[0 1 0; 0 0 1; 1 0 0]，C[2]＝[0 0 1; 1 0 0; 0 1 0]，C[3]＝I3。已用 python 驗算。後面講圖時，這種冪次可算「走 k 步到得了哪裡」。
練功 1 p87
| 答案（2×4） | |||
|---|---|---|---|
| 1 | 0 | -5 | -1 |
| 3 | -2 | 11 | 3 |
投影片 p87 的答案相同，已驗算。
練功 2 p98
注意要從左邊乘：因為 AB≠BA，M⁻¹ 放右邊是錯的。
練功 3 p98
| (a) A∨B（3×3） | ||
|---|---|---|
| 1 | 1 | 1 |
| 1 | 1 | 1 |
| 1 | 0 | 1 |
| (b) A∧B（3×3） | ||
|---|---|---|
| 0 | 0 | 1 |
| 1 | 0 | 0 |
| 0 | 0 | 1 |
| (c) A⊙B（3×3） | ||
|---|---|---|
| 1 | 1 | 1 |
| 1 | 1 | 1 |
| 1 | 0 | 1 |
(c) 若用一般乘法會得到 [1 1 2; 1 1 2; 1 0 1]，把 2 壓成 1 就是布林積。