從含糊其詞到滴水不漏的主張
在上一篇指南裡，你把集合、關係與函數釘牢了——那些是這門學科的名詞。邏輯則提供它的動詞：一種精確說出何者為真、並把各個主張組合起來而不留任何含糊縫隙的方法。命題就只是一個非真即假、沒有中間地帶的陳述：「3 是奇數」（真）、「空字串長度為 1」（假）。從這裡開始你遇到的每一條定理，其實都是一個我們打算一刀兩斷地解決的命題；而每一個證明，都是一連串以滴水不漏的推理連起來的較小命題。
我們用四個連接詞把小命題堆成大命題。「且」要求兩部分都成立；「或」要求至少一個成立；「非」把真假對調；蘊涵「若 P 則 Q」（寫作 P -> Q）說的是 P 迫使 Q。這裡藏著兩個日常陷阱。第一，邏輯的「或」是兼容的：「P 或 Q」在任一邊為真、或兩邊都為真時都成立——不像菜單上那種「湯或沙拉」。第二，蘊涵 P -> Q 只在唯一一種情形為假，就是 P 真而 Q 假時；其餘所有情形它都為真，包括那個略帶詭異的情形——當 P 為假時，我們稱它「空泛地為真」。（「若月亮是乳酪，則 2+2=5」是個為真的蘊涵，因為它的前提從不觸發。）
對所有與存在：兩個量詞
連接詞把少數幾個有名字的命題黏在一起，但這門學科的定理一次談的是無窮多個物件——每個字串、每個狀態、每台機器。為此我們需要量詞。「對所有」（全稱量詞，寫成一個上下顛倒的 A，即符號 forall）斷言某事對某集合中的每一個物件都成立：「對 Sigma 上所有字串 w，w 的長度至少為 0」。「存在」（存在量詞，寫成一個左右翻轉的 E，即符號 exists）斷言至少有一個物件成立：「存在一個長度為 5 的字串」。被量詞掃過的那個集合——所有字串、所有自然數——是量詞的論域，把它講清楚就贏了一半。
真正的微妙之處，在於量詞交替出現時。陳述「對所有 x，存在一個 y 使得 y > x」（每個數都被一個更大的數壓過）在整數上為真——但把順序對調成「存在一個 y，使得對所有 x，y > x」（單單一個數壓過一切），它就乾脆地變成假的。順序不是裝飾：它決定了 y 是否被允許依賴於 x。由左到右讀懂這些陳述，逐一判斷每個量詞所做的選擇是否可以參考已經固定下來的變數，是一項你在每一個極限論證、每一個封閉性證明中、以及——關鍵地——在幫浦引理中都會倚重的技巧；幫浦引理的陳述正是一個四層深、交替出現的量詞巢狀結構。
Quantifier order matters: forall x. exists y. y > x -> TRUE (y may depend on x; pick y = x+1) exists y. forall x. y > x -> FALSE (one y must beat every x at once) Reading rule: a later quantifier's choice may use every variable fixed to its LEFT, never one to its right.
否定：你非做對不可的那一步
這是整套工具中最重要的一招。要反駁一個全稱主張，你不用跟它的全部較勁——你只需端出一個反例。要否認「所有天鵝都是白的」，給出一隻黑天鵝就好。用符號寫，「對所有 x，P(x)」的否定是「存在某個 x 使得非 P(x)」。而它的鏡像：「存在 x 使得 P(x)」的否定是「對所有 x，非 P(x)」。把一個「非」向內推過一個量詞時，它會把量詞翻面——「對所有」變成「存在」、「存在」變成「對所有」——而那個「非」會繼續向內行進，落到量詞原本守護的東西上。
當好幾個量詞疊在一起時，你要由外而內、一次翻一個，就像把一隻手套逐根手指地翻到反面。規則永遠不變：每個 forall 變成 exists、每個 exists 變成 forall，而最內層的命題最後才被否定。當「非」穿過連接詞時，連接詞也會翻面——根據狄摩根定律，「P 且 Q」的否定是「非 P 或非 Q」，「P 或 Q」的否定是「非 P 且非 Q」。（否定一個蘊涵 P -> Q 是最愛出的陷阱題：它變成「P 且非 Q」，也就是唯一讓它為假的那種情形。）機械化地照做，你就永遠不會迷失位置。
- 從這個陳述開始，把每個量詞與連接詞都明白寫出——不留任何縮寫藏著一個隱形的「對所有」。
- 在整句最前面放一個「非」，把它向右推過最外層的量詞，並把該量詞翻面（forall <-> exists）。
- 持續把「非」向內推，依序翻面它經過的每一個量詞，直到它抵達最內層的命題。
- 對那裡的任何「且／或」套用狄摩根定律，並把「非 (P -> Q)」改寫成「P 且非 Q」。現在把結果讀出聲——它應該恰好描述了那個讓原陳述破功的情境。
為什麼這就是偽裝過的幫浦引理
這一切會在前方第一個重要證明之一裡得到回報。幫浦引理大致是說：對每個正規語言 L，存在一個數 p（幫浦長度），使得對 L 中所有長度至少為 p 的字串 s，存在一種把 s 切成三段 x、y、z（其中 y 非空且短）的方法，使得對所有 i >= 0，幫浦後的字串 x y^i z 仍然在 L 裡。數一數量詞：forall、exists、forall、exists、forall——五層，交替出現。這個陳述是關於正規語言的；它本身並不做任何事。
要把它當武器使用，你得否定它，而這個否定恰恰就是你剛練過的翻手套。「L 不是正規語言」說得太重了；引理真正給你的是：若 L 是正規的，幫浦條件就會成立。所以你假設 L 是正規的（一個反證法），然後否定內層條件以鑿開一道裂縫。依序翻面每個量詞，證明的任務就變成：對所有 p，存在一個 L 中長度至少為 p 的壞字串 s，使得對所有切法 x、y、z，存在一個 i >= 0 使得 x y^i z 不在 L 裡。那個被否定的句子就是你的作戰計畫——而正確地讀懂它，正是這篇指南存在的全部理由。
具體地說，取經典的非正規語言 a^n b^n（先若干個 a，再同樣多個 b）。無論引理交給你的幫浦長度 p 是多少，你都挑壞字串 s = a^p b^p。任何短的前段 y 都必定整個落在那串 a 之內，所以把它幫浦成 x y^2 z 會造出比 b 還多的 a——一個落在語言之外的字串。這個單一反例，是順著被否定的量詞巢狀結構找出來的，足以證明非正規性。注意它底下的形狀：一個長字串被硬塞過一台有限的機器，於是某個狀態必定重複——那就是鴿籠原理披著量詞戲服，也就是第 4 篇指南的主題。
逆否命題，與幾句誠實的提醒
還有一個等價性能省下大量力氣。「若 P 則 Q」的逆否命題是「若非 Q 則非 P」，兩者邏輯上完全相同——永遠在完全相同的情形下為真。所以要證明一個蘊涵，你可以改去證明它的逆否命題，哪一個方向比較好論證就用哪一個。這不是逆命題（我們前面已經警告過，它可能為假）；逆否命題是貨真價實的換句話說。幫浦論證的大部分，其實就是一個更簡單事實的逆否命題：「若一台 DFA 在讀某字串時沒有任何狀態重複，則該字串的長度不超過狀態數。」
這寥寥幾招——量詞、它們的交替、乾淨的否定、逆否命題——不只是考試的小技巧；它們是從封閉性證明到不可判定性，一切事物名副其實的承重樑柱。同樣那套由外而內的否定，瞄準停機問題時，會造出一台被迫與自己唱反調的機器，那正是第 5 篇指南中對角線論證的心跳。在這裡練到流暢，前方那些艱難的定理就不再像魔法，而開始像在記帳。