目錄
這是 Stanford CS103 導讀的第 5 篇，對應 Spring 2026 官方 Lecture 3（2026-04-06）。課程團隊是 Cynthia Bailey Lee 與 Alex Aiken；公開頁面沒有逐堂講者欄，因此本文不猜講者。講次頁面與完整投影片公開，錄影與逐字稿只在 Canvas／Panopto，本文沒有使用。
本講回答「如何形式化證明裡使用的定義與推理」。命題邏輯先把每個完整陳述壓縮成一個真假值，只研究它們如何由連接詞組合；下一階段的一階邏輯才會打開陳述，處理物件及其性質。這個限制既是命題邏輯的力量，也是它不能表達所有數學內容的邊界。
從英文命題到布林代數
命題是必定為真或為假的陳述。英文敘述句可能是命題，問題與命令則不是，因為「請關門」或「現在幾點？」沒有可直接指定的真值。命題邏輯用命題變數代表完整命題，通常寫成小寫 $p,q,r,s$；每個變數只能取真或假。
投影片把這次抽象比作從算術升級到代數。算術可確認特定數字的等式，代數則用變數抽出可重複使用的結構規則。同樣地，把「整數 $x$ 是奇數」或「你在 CS103 拿到 A+」替換成 $p$，我們便能忽略句子的題材，專注於論證形狀。例如「證明逆否命題就證明原命題」是一條與小狗、奇偶數或貓食內容無關的結構規則。
三個基本連接詞：非、且、或
投影片先介紹否定 $¬p$、合取 $p∧q$ 與析取 $p∨q$。$¬p$ 在 $p$ 假時真；$p∧q$ 只有兩者都真才真；$p∨q$ 只要至少一者真就真。這裡的「或」是包含式或：$p,q$ 同時為真時，$p∨q$ 仍為真，與 C、C++、Java 的 || 或 Python 的 or 相近。
若要互斥或，也不必新增原始連接詞。投影片要求用現有符號組出「恰有一者為真」，例如 $(p∨q)∧¬(p∧q)$；另一個等價寫法是 $(p∧¬q)∨(¬p∧q)$。自測時列四種輸入：假假與真真輸出假，假真與真假輸出真。只寫 $p∨q$ 會錯在真真那列。
三個基本表也值得逐列說清楚。否定只有一個輸入，所以 $p$ 真時 $¬p$ 假，$p$ 假時 $¬p$ 真。合取的真列只有「真、真」一列；析取的假列只有「假、假」一列。這種「記住唯一例外」的方式與上一講的蘊涵相呼應，但不要混在一起：合取問兩件事是否同時成立，析取問至少一件是否成立，蘊涵則問承諾是否被某個案例打破。
真值表是公式的完整規格
真值表列出公式對每種輸入配置的輸出。含兩個變數時有四列；含 $n$ 個獨立變數時有 $2^n$ 列，因為每個變數各有真假兩種選擇。計算複合公式時，不應靠語感一次猜終值，而應為子公式加欄位。
例如檢查 $(p∨q)∧¬(p∧q)$，依序算 $p∨q$、$p∧q$、$¬(p∧q)$，最後才做合取。真值表不只用來「算答案」，也是兩公式等價的判準：若它們在所有輸入列輸出相同，就具有相同真值函數。
列舉也要有固定順序，才不會漏列或重列。兩個變數可按「假假、假真、真假、真真」排列；三個變數則讓最右欄每列翻轉、中間欄每兩列翻轉、最左欄每四列翻轉。每加一個變數，列數加倍。完成後先檢查輸入列是否齊全，再逐欄依公式語法樹計算。若某欄是 $p∧q$，就只讀 $p,q$ 兩欄，不能讓最終預期答案反過來影響中間值。
以 $p→q$ 為例，先圈出唯一的假列「真、假」，剩下三列填真；以 $p↔q$ 為例，直接比較兩欄是否相同。這些捷徑都是由定義濃縮而來，仍可隨時展開成逐列判斷。考試或除錯時若捷徑與語意衝突，應回到完整四列，而不是憑直覺硬改答案。
蘊涵的四列與空真
蘊涵 $p→q$ 只有 $p$ 真且 $q$ 假時為假；四列依序是：假假為真、假真為真、真假為假、真真為真。投影片再次用「若預測出完美 March Madness bracket，就給 A+」逐列判斷。沒有完美預測時，無論最後成績為何都沒違反承諾；完美預測卻沒拿 A+ 才違約。
前件為假時，蘊涵稱為 vacuously true（空真）。這不表示後件本身被證成真，而是這個輸入沒有推翻條件承諾。投影片要求記住整張表，因為之後數週會反覆使用。另一個重要觀察是：$p→q$ 為真，恰好等價於它的唯一失敗情況 $p∧¬q$ 為假。
若不確定假假那列為何是真，可以回到承諾，而不要套日常因果。前件為假的案例沒有提供違約證據，因此在二值邏輯中整式歸為真。這個定義也不是隨意選擇：它讓 $p→q$ 與 $¬p∨q$、以及 $¬(p∧¬q)$ 完全對齊，讓否定蘊涵與反例的結構一致。修改其中一列，後面這些等價式與證明方法就會一起斷裂。
雙條件、真與假常數
雙條件 $p↔q$ 讀作「$p$ 若且唯若 $q$」，等價於 $(p→q)∧(q→p)$。它在兩邊真值相同時為真：假假與真真為真，假真與真假為假。可以把它視為布林值的相等判斷，但證明雙條件時仍要記得其中包含兩個方向。
投影片再加入常數 $⊤$ 與 $⊥$：前者永遠為真，後者永遠為假。上一講的反證法因此能寫成 $(¬p→⊥)→p$：如果假設 $p$ 為假會推出必假的命題，便可得到 $p$。
運算優先序與括號
投影片給出的優先序由高到低是 $¬$、$∧$、$∨$、$→$；複雜式則建議直接加括號。否定只綁定緊接在後的項目，且 $∧,∨$ 比 $→$ 更緊。因此 $p∧q→r$ 通常解析為 $(p∧q)→r$，不是 $p∧(q→r)$。
面對投影片的 $¬x→y∨z→x∨y∧z$，不能憑閱讀節奏自選分組。先標出 $¬x$ 與 $y∧z$，再處理析取，最後才判斷蘊涵結構；若箭頭串接仍可能歧義，正式書寫就加括號。優先序的目的不是鼓勵省括號，而是讓常見短式有一致讀法。
投影片用多張逐步頁面讓讀者一次只處理一層。可沿用相同程序：先在每個否定符號後框出直接操作數；再把所有合取成組；接著處理析取；最後處理箭頭。若同一優先級連續出現而課程沒有在當頁明定結合方向，就不要猜，直接補括號。翻譯自然語言時反過來做：先畫出句子的主連接詞，再遞迴翻譯左右子句，能避免把局部的「且」誤當全句骨架。
七種符號的角色與程式語言對照
本講的「大表」包含七項：$¬$（否定）、$∧$（合取）、$∨$（析取）、$→$（蘊涵）、$↔$（雙條件）、$⊤$（真）、$⊥$（假）。前面三者在常見程式語言約對應 !、&&、||，常數對應 true、false；投影片沒有把蘊涵與雙條件草率等同某個單一運算子，而把相關程式練習留給 PS2。
程式語言對照只能幫助記憶真值，不能偷渡執行語意。短路求值涉及是否執行右側函式，命題邏輯則只把左右視為已具有真值的命題。後面 De Morgan 的程式例子說兩種寫法連短路行為也一致，但那是特定改寫的額外好處。
把英文翻成符號：先固定原子命題
投影片定義 $a$ 為「我會在日全食路徑上」，$b$ 為「我會看到日全食」。句子「如果我不在全食帶上，我就看不到日全食」翻成 $¬a→¬b$。翻譯時先圈出完整原子句，再判斷連接詞；否定應落在變數上，不要擅自更換因果方向。
特別容易錯的是英文 “p if q”。它表示「若 q，則 p」，所以是 $q→p$，不是 $p→q$。可以把 if 後面的子句當前件。相對地，“p only if q” 才把 $q$ 放在必要條件的位置，形成 $p→q$。本講投影片明示前一個陷阱，目的就是阻止讀者依英文出現順序照抄箭頭。
日食例題還可用真值語意回查方向。句子承諾：一旦「不在全食帶」成立，「看不到日全食」也成立；因此唯一違反它的世界是人不在全食帶卻仍看到日全食。這正是 $¬a$ 真而 $¬b$ 假的一列。若誤寫成 $¬b→¬a$，承諾會變成「只要沒看到，就一定不在全食帶」，但雲層或其他原因也可能使全食帶內的人看不到，兩句顯然不同。
but 在命題邏輯裡仍是合取
加入 $c$：「今天有日全食」。投影片句子「如果我會在全食帶上，但今天沒有日食，我就看不到日全食」翻成 $(a∧¬c)→¬b$。英文 but 帶有語氣上的反差，在命題邏輯的真假條件中仍只是 and，所以前件是 $a∧¬c$。
這個例子同時檢查三層作用範圍：but 把兩個條件合取；沒有 只否定 $c$；整個合取才是蘊涵前件。若漏掉括號寫成 $a∧¬c→¬b$，依既定優先序仍可得到相同解析，但在翻譯題中加括號更能顯示理解。
等價不是語句相似，而是每列相同
命題等價表示兩個公式對所有變數配置都有相同真值。投影片用杯子下是否有巧克力來問：要證明 $p∧q$ 為假，只需掀開一個杯子看到空；要證明 $p∨q$ 為假，則兩個杯子都必須是空的。這個差別正好導出合取與析取的否定規則。
單一案例相同不能證明等價，因為其他真值列可能分岔。可靠方法是建立共同輸入列，分別計算兩個公式，逐列比較輸出欄。找到一列不同即可否證等價；要證明等價則要覆蓋所有列，或使用已證明的等價律逐步改寫。
De Morgan 定律逐列理解
兩條 De Morgan 定律是
[ ¬(p∧q)≡¬p∨¬q, \qquad ¬(p∨q)≡¬p∧¬q. ]
第一條說「不是兩者都真」等於「至少一者不真」；第二條說「兩者並非至少一個真」等於「兩者都不真」。否定穿過括號時，$∧$ 與 $∨$ 互換，且每個操作數都取否定。只在外面加否定、不換連接詞，或只否定其中一邊，都會在真值表某列失敗。
杯子例題提供一個不靠符號的檢查。若 $p$ 表示一號杯下有巧克力、$q$ 表示二號杯下有巧克力，要推翻 $p∧q$，掀開任何一杯看到空就夠，對應 $¬p∨¬q$；要推翻 $p∨q$，則必須兩杯都空，對應 $¬p∧¬q$。如果自己的符號改寫要求掀錯數量的杯子，就代表連接詞沒有隨否定交換。
投影片的程式建議把 !(p() && q()) 改成 !p() || !q()；兩者真值等價，並能保持相應的短路行為。數學推導的核心仍是等價式，不是程式碼風格偏好。
蘊涵的兩個重要等價式
由蘊涵唯一失敗於 $p∧¬q$，可得
[ p→q≡¬(p∧¬q). ]
因此否定蘊涵便是 $¬(p→q)≡p∧¬q$，與上一講找反例的格式完全一致。再套用 De Morgan：
[ ¬(p∧¬q)≡¬p∨¬¬q≡¬p∨q, ]
所以 $p→q≡¬p∨q$。若 $p$ 假，$¬p$ 讓析取為真；若 $p$ 真，整式真值就由 $q$ 決定，恰好重現蘊涵真值表。這條等價式之後可用來消去箭頭，但每一步都必須維持括號與否定範圍。
可以把推導分成可稽核的三步：先以唯一反例把箭頭改成外層否定；再用 De Morgan 把否定分配進合取；最後消去 $¬¬q$。每一步只使用一條已知等價律，左右公式的自由變數仍是同一組 $p,q$。若直接從 $p→q$ 跳到 $¬p∨q$，結果雖對，讀者卻無法判斷是套用了已證等價式，還是把箭頭當成日常語句猜測。
常見翻譯錯誤與可執行自測
常見錯誤有四類：把包含式或當互斥或；把 “p if q” 依字面順序寫成 $p→q$；把 but 當新連接詞；以及在多層否定中漏換 $∧,∨$。另一個錯誤是因前件為假就說後件為真；空真描述的是整個蘊涵，不是後件。
可實作一張四列小表檢查：先算 $p↔q$ 與 $(p→q)∧(q→p)$；再算互斥或兩種寫法；接著驗證 $p→q$ 與 $¬p∨q$；最後找出 $¬(p∧q)$ 和 $¬p∧¬q$ 不同的輸入列。每題都先完整列出子公式欄，若只看自然語言猜答案，就失去真值表提供的機械檢查。
最後再做一題作用範圍檢查：把「若 $p$ 且 $q$，則不是 $r$ 或 $s$」先畫成前件與後件，再寫成 $(p∧q)→(¬r∨s)$。接著依優先序拿掉不必要括號並重新解析，確認仍得到相同語法樹。若把它誤讀為 $p∧(q→¬(r∨s))$，真值表會在多列不同；列出其中一個反例，就能具體定位究竟是主連接詞、否定範圍或合取分組出了錯。
材料缺口與閱讀界線
公開完整投影片足以覆蓋命題變數、七種符號、各真值表、優先序、日食翻譯例題、杯子例題、De Morgan 定律與蘊涵等價式。本講有課堂投票與鄰座討論提示，但公開材料沒有結果、錄影或逐字稿，因此本文只重建題目與可由投影片確認的答案，不推測學生反應。PS2 只作為投影片指向的後續練習，不重現受限解答。
更新紀錄
- 2026-08-22：依官方完整投影片重建雙語正文，恢復真值表、翻譯例題、優先序與命題等價式的逐項覆蓋。
參考資料
Loading...