目錄
這是 Stanford CS103 導讀的第 4 篇，對應 Spring 2026 官方 Lecture 2（2026-04-03）。課程團隊是 Cynthia Bailey Lee 與 Alex Aiken；公開頁面未逐堂標示講者，因此本文不猜講者。講次頁面與完整投影片公開，錄影與逐字稿只在 Canvas／Panopto，本文沒有使用。
上一講從假設直接推到結論。本講問的是：直接路線不順時，能否改證一個等價命題？要安全地改方向，必須先知道原命題究竟在什麼情況下為假。投影片因此先講蘊涵與否定，才進入逆否證明和反證法。
蘊涵只在前件成立時提出承諾
蘊涵寫成 (P\to Q)，讀作「若 (P) 為真，則 (Q) 為真」。(P) 是前件，(Q) 是後件。投影片列出「若整數 (n) 為偶數，則 (n^2) 為偶數」、「若 (m,n) 都是奇整數，則 (m+n) 為偶數」，也故意放入「若你證明 Cantor 定理錯了，就會在 CS103 拿到 A+」。第三句雖荒謬，形式上仍是蘊涵；蘊涵不保證前件會發生，也不表達因果。
彩虹例子揭示方向性：「天空有彩虹，則某處正在下雨」不等於「某處下雨，則天空必有彩虹」。沒有彩虹也不能推出沒有雨。原句唯一失敗的情況是 (P) 已成立而 (Q) 沒成立；其餘三種真假組合都未違背「一旦 (P)，就保證 (Q)」的承諾。這個失敗條件稍後會直接成為蘊涵的否定。
可以把四格逐一口述來避免誤判。當前件與後件都真，承諾確實兌現；當前件真、後件假，承諾明確破裂；當前件假時，不論後件真假，原句都沒有告訴我們該發生什麼。這不是說前件為假時後件「自動為真」，而是整條蘊涵沒有被那個案例推翻。把這個差別說清楚，才能理解為何證明蘊涵只需處理前件成立的輸入，也能理解為何反例必須同時滿足前件與否定後件。
否定是精確的真值反面
命題是具有真假值的陳述。命題 (X) 的否定 (lnot X)，必須在 (X) 為假時為真，並在 (X) 為真時為假。投影片提醒：「外面正在下雪」的否定是「外面沒有下雪」，不是「外面陽光普照」。雨天或陰天也可能沒有雪；晴天只涵蓋許多非下雪情況中的一種。
檢驗候選否定可以問兩題：它能否與原命題同時為真？兩者能否同時為假？精確否定對兩題都必須回答「不能」。數學否定翻轉的是完整真值條件，不是替換一個語感上的反義詞。
否定全稱：一個反例就足夠
全稱命題「對所有 x，P(x)」宣稱論域中每個 (x) 都滿足 (P)。它只要有一個例外便失敗，所以
[ \lnot(\forall x,P(x))\equiv\exists x,\lnot P(x). ]
投影片用「我的所有朋友都比我高」說明。只要有一位朋友不比我高，原句就是假；正確否定是「存在一位朋友不比我高」，不是「所有朋友都比我矮」。後者要求過多，也漏掉同高的情況。
逐步轉換時，先保留論域「我的朋友」，把「所有」換成「至少一位」，再否定性質「比我高」。若只否定性質而保留全稱，就會得到「每一位都不比我高」；那比否定原句強得多。
否定存在：排除每一個候選見證
存在命題 (exists x,P(x)) 只要求至少一個見證。要讓它為假，必須讓每個候選者都不滿足性質：
[ \lnot(\exists x,P(x))\equiv\forall x,\lnot P(x). ]
「存在一位朋友不比我高」的否定，是「每一位朋友都不是不比我高」，整理雙重否定後即「每一位朋友都比我高」。只找到一位較高的朋友不能否定存在句，因為另一位仍可能成為見證。
兩條規則可記成：否定穿過量詞時，全稱量詞與存在量詞互換，性質也取否定。但語意比口訣重要：全稱由一個反例擊破；存在則須排除所有候選見證。
否定蘊涵不是另一個蘊涵
投影片用 March Madness 承諾測試 (P\to Q)：如果你選出完美預測表，我就給你 A+。四種情況逐一看：完美且拿 A+ 是兌現；不完美卻拿 A+ 並未違約，因為原句沒禁止額外給分；完美卻拿 C 才是違約；不完美且拿 C 則沒有觸發承諾。
因此 (P\to Q) 的否定是 (P\land\lnot Q)，不是 (lnot P\to\lnot Q)，也不是 (P\to\lnot Q)。若外層還有全稱量詞，完整變換是
[ \lnot\bigl(\forall x(P(x)\to Q(x))\bigr) \equiv\exists x(P(x)\land\lnot Q(x)). ]
讀作：「至少有一個 (x)，前件成立，但承諾的後件不成立。」投影片特別強調「若—則」經否定後變成「而且」；反駁普遍規則必須同時交出觸發規則的輸入與規則失敗的證據。
逆否命題為何等價
(P\to Q) 的逆否命題是 (lnot Q\to\lnot P)。原命題的否定為 (P\land\lnot Q)，逆否命題的否定為 (lnot Q\land P)。合取順序不影響真假，因此兩者在完全相同的情況失敗，也就等價。
投影片用兩個例子換入口：「如果牠是小狗，我就愛牠」等價於「如果我不愛牠，牠就不是小狗」；「若貓食收在室內，浣熊就偷不到」等價於「若浣熊偷到了，我就沒把貓食收在室內」。逆否命題不是逆命題 (Q\to P)，也不是否命題 (lnot P\to\lnot Q)。必須交換前後件並同時否定兩端。
完整逆否證明：平方為偶數則原數為偶數
定理是：對任何整數 (n)，若 (n^2) 為偶數，則 (n) 為偶數。投影片改證逆否命題：「若 (n) 為奇數，則 (n^2) 為奇數。」
任取奇整數 (n)。依奇數定義，存在整數 (k) 使 (n=2k+1)。平方整理：
[ \begin{aligned} n^2&=(2k+1)^2\ &=4k^2+4k+1\ &=2(2k^2+2k)+1. \end{aligned} ]
令 (m=2k^2+2k)。整數對加法與乘法封閉，所以 (m\in\mathbb Z)，且 (n^2=2m+1)。這正符合奇數定義，故 (n^2) 為奇數；逆否命題成立，原命題也成立。
投影片反覆標出三個接口。第一，先宣布使用逆否證明，讓讀者知道方向已改。第二，寫出真正要證的逆否命題，不能只說「考慮逆否」。第三，把代數式接回「存在整數 (m)」的奇數定義；停在 (2(2k^2+2k)+1) 只是暗示，尚未交代見證與型別。
逐行檢查時，「任取」對應逆否命題中的全稱量詞，表示不能挑一個方便的奇數。接著由奇數性取得整數見證 (k)，而這個 (k) 可以依所選的 (n) 改變。展開平方只是等式變形；真正產生結論的是把括號內整體命名為整數 (m)。因此每一層量詞都有對應動作：任取 (n)、取得 (k)、構造 (m)。若把 (k) 當任意實數，或不說明 (m) 是整數，就無法套用奇數定義。
雙條件有兩個證明義務
上一講直接證明「若 (n) 為偶數，則 (n^2) 為偶數」；本講證明反方向。兩者合併成
[ n\text{ 為偶數}\iff n^2\text{ 為偶數}. ]
「若且唯若」包含兩條獨立蘊涵。證明 (P\iff Q) 必須分別證 (P\to Q) 與 (Q\to P)，而兩個方向可以採不同技法。這裡一邊直接證，另一邊用逆否證明。只完成一邊，最多得到必要條件或充分條件，不能寫成雙條件。
反證法：讓否定導向不可能
要以反證法證命題 (P)，先假設 (P) 為假，再推出不可能同時成立的結果，例如 (1=0)、元素同時屬於且不屬於同一集合，或整數同時為奇數與偶數。既然 (lnot P) 會導致矛盾，它便不能成立；在命題只有真、假兩種真值的框架中，(P) 必須成立。
投影片用兩扇門比喻：現實必在「(P) 真」或「(P) 假」其中一扇門後。排除後者，就能確定前者。這不是「找不到反例所以為真」；必須從 (lnot P) 經有效推理抵達明確矛盾。
反證例一：不存在最大的集合
定理是「不存在最大的集合」。它的否定是「存在最大的集合」，所以先假設有一個最大集合 (S)。接著考慮冪集 (wp(S))。Cantor 定理給出
[ |S|<|\wp(S)|. ]
因此 (wp(S)) 是比 (S) 更大的集合，直接違反 (S) 最大的假設。矛盾精確落在同一個 (S)：它一方面被假設不小於任何集合，另一方面又有一個基數嚴格更大的集合。故原假設錯誤，不存在最大的集合。
這也顯示反證法可以帶有構造：假設提供候選 (S)，Cantor 定理把它送到 (wp(S))，而冪集必然越過原基數。
這裡不能把結論弱化成「目前沒找到最大集合」。反證假設給的是一個具體但任意命名的最大候選 (S)，冪集運算則對任何集合都合法；因此不論候選長什麼樣，(wp(S)) 都會擊破它。也不能只說「冪集包含更多元素」：對無限集合，這種直觀描述不足，真正需要的是 Cantor 定理保證的嚴格基數不等式。
反證例二：奇偶定理的另一條路
同一條「若 (n^2) 為偶數，則 (n) 為偶數」也能反證。否定蘊涵是前件成立且後件不成立，因此假設存在整數 (n)，使 (n^2) 為偶數而 (n) 不為偶數；對整數而言，後者即 (n) 為奇數。
由奇數定義，存在整數 (k) 使 (n=2k+1)。展開得到
[ n^2=2(2k^2+2k)+1, ]
所以 (n^2) 為奇數。但假設同時說它為偶數，同一整數不能既奇又偶，故否定假設錯誤，原蘊涵成立。
CS103 要求反證明示三件事：先說使用反證法；準確寫出原命題的否定；最後指出矛盾的兩端，以及矛盾迫使哪個假設失敗。只寫「顯然矛盾」會把核心邏輯留給讀者猜。
比較兩份奇偶證明也能看出逆否與反證的差別。逆否版本只假設 (n) 奇，目標直接是 (n^2) 奇；建立奇數形式後便完成。反證版本多保留原前件「(n^2) 偶」，所以相同的代數推導不是結論，而是拿來撞上既有假設。兩者使用同一計算，邏輯終點卻不同：前者完成一條蘊涵，後者製造「同時奇且偶」的不可能情況。
三種證明蘊涵的方法
面對 (P\to Q)，本講整理出三條路：直接證明假設 (P) 並推出 (Q)；逆否證明假設 (lnot Q) 並推出 (lnot P)；反證法假設 (P\land\lnot Q) 並推出矛盾。三者是同一證明義務的不同入口。
若 (P) 的定義自然產生 (Q) 所需的見證，直接證明通常最短。若 (lnot Q) 有可操作結構，例如整數「不是偶數」可化為「奇數」，逆否較順。若結論排除存在或極值，或失敗案例會同時給出互斥性質，反證法常能集中呈現衝突。
動筆前可先寫出三個起點：(P)、(lnot Q)、(P\land\lnot Q)。哪個能立即展開定義、給出見證或連到已知定理，就先試哪條。正式稿只保留實際方法，並在開頭宣布。
常見誤判與可執行自測
常見錯誤包括：把逆命題當逆否命題；否定量詞時只改性質、不換量詞；把蘊涵的否定仍寫成蘊涵；反證只說「假設相反」卻不寫完整否定。可用四題檢查：
- 否定「每位學生都交作業」：應是「至少一位沒交」，不是「每位都沒交」。
- 否定「存在整數平方等於 2」：應是「每個整數的平方都不等於 2」。
- 否定「對每個整數 (n)，若 (n) 偶則 (n^2) 偶」：應是「存在偶整數 (n)，其平方不偶」。
- 寫「若 (ab) 奇，則 (a,b) 都奇」的逆否：否定合取結論會得到「(a) 不奇或 (b) 不奇」，不是兩者都不奇。
做完後逐題圈出量詞、前件、後件與否定範圍；反證題再寫出預期矛盾的兩端。這能在代數開始前抓出方向錯誤。
再做一次投影片式判讀：對「若我把貓食收進室內，浣熊就偷不到」，看到貓食仍在室內只能確認一個可能的後件，不能反推它先前一定收在室內；看到浣熊偷到，才可由逆否推出沒有收進室內。對「不存在最大集合」，反證開頭不能寫成「假設有些集合很大」，而要完整否定成「存在一個比所有集合都不小的集合」。兩題都要求保留原命題的方向、量詞與作用範圍。
材料缺口與閱讀界線
完整投影片足以重建蘊涵與否定規則、逆否證明、雙條件、兩個反證例題，以及課程要求的書寫步驟。公開材料沒有課堂錄影、逐字稿、投票結果或學生提問，因此本文不推測互動結果，也不把銜接文字當講師原話。末頁另提醒閱讀 office hours、LaTeX、proofwriting 資料並開始 PS1；本文不重現受限作業解答。
更新紀錄
- 2026-08-22：從官方完整投影片重建雙語正文，恢復量詞否定、逆否證明、雙條件與兩個反證例題的逐項覆蓋。
參考資料
Loading...