命题的连接词
Propositions from Propositions数学家拿 NOT、AND、OR、IMPLIES、IFF 这些词做了精确到无歧义的规定——规定的方式就是真值表（truth table）：枚举变量真假的所有组合，写出公式在每种组合下的真值。P、Q 这样的命题变量（propositional variables）只取 T（真）/ F（假）两个值，又称布尔变量，致敬十九世纪的 George Boole。
大多数字你都能猜对意思，但有两个暗坑："OR" 允许两者皆真（数学家说"蛋糕或冰淇淋"时，你真两样都拿他也不算你错——想表达"二选一"得用 XOR）；以及 IFF（当且仅当）断言两边真值相同。IMPLIES 则最反直觉，先卖个关子——你亲手把五张真值表填出来，它的脾气自然现形：
3.1.3IMPLIES 的两场实验
有了真值表，可以裁决两个古怪句子。"若哥德巴赫猜想为真，则 x² ≥ 0 对所有实数成立。"——哥德巴赫真假未知，但 x² ≥ 0 恒真（then 部分真），落在真值表 (tt) 或 (ft) 行，整句为真。"若猪会飞，则你的账户不会被黑。"——猪不会飞（if 部分假），落在 (ft)/(ff) 行，也是真的！数学蕴含无视因果关系：只要 if 部分是假的，蕴含就自动真。这不是 bug：12 条"若传感器 i 为真则执行动作 i"的系统规格，正是靠"假前提自动真"才能合并成一条逻辑公式。
计算机程序里的命题逻辑
Propositional Logic in Computer Programs看一段 C/Java 风格的代码：if ( x > 0 || (x <= 0 && y > 100) )。令 A ::= "x > 0"，B ::= "y > 100"，条件即 A OR (NOT(A) AND B)。逐列填完真值表你会发现它能化简——这就是编译器与电路综合器每天都在做的事：
3.2.2暗号对照表
NOT(P) = ¬P = P̄；AND = ∧（电路设计者叫"乘"）；OR = ∨（"加"）；IMPLIES = ⇒；IFF = ⟷；XOR = ⊕。本书坚持用英文单词，免得跟算术运算打架——只在公式太长要跑出页面时才用符号。
等价与有效性
Equivalence and Validity"我饿 ⇒ 我暴躁"和"我不暴躁 ⇒ 我不饿"说的是同一件事吗？把两句话都译成命题逻辑（P ::= 我饿，Q ::= 我暴躁），真值表给出裁决：P ⇒ Q 与 ¬Q ⇒ ¬P 的结果列完全相同——它们等价。¬Q ⇒ ¬P 叫做 逆否命题（contrapositive）。而逆命题（converse）"我暴躁 ⇒ 我饿"的真值列在两处不同——蕴含一般不等价于它的逆。第一章 Non-Rule 的坑，这里终于有了正式户口。
三个新身份名词：
有效（valid）：无论变量取什么值恒真。最简单：P OR NOT(P)。
可满足（satisfiable）：存在某组真值使它为真。
不可满足：永远为假（如 P AND NOT(P)）。
两者互相成就：P 有效 ⟺ NOT(P) 不可满足；两公式等价 ⟺ "P IFF Q" 有效。
命题代数
The Algebra of Propositions真值表有个致命伤：n 个变量就要 2ⁿ 行——30 个变量就是十亿多行。另一条路是代数变形：用一组等价公理（AND 的交换/结合/单位元/零元/分配律、OR over AND 的分配律、幂等、双否、De Morgan……）像整形代数那样推等价。每条公理都可以用小真值表秒验。
析取范式 DNF（积之和）：从真值表的每个 T 行读出一个"变量或其否定的 AND"，再 OR 起来。
合取范式 CNF（和之积）：对每个 F 行读出 OR-项再 AND 起来。
定理 3.4.1：任何命题公式都等价于一个 DNF 和一个 CNF。定理 3.4.3（完备性）：两条公式可证等价 ⟺ 它们真的等价。
练一手"从真值表读 DNF"，再玩一把 De Morgan 链式变形：
SAT 问题
The SAT Problem给定一个命题公式，问：存不存在一组真值赋值让它为真？这就是 SAT 问题。直觉上"暴力枚举 2ⁿ 种组合"总能解决，但 n 一大就爆炸。有没有跑得多项式时间（如 n²、n¹⁴）而非指数时间（2ⁿ）的算法？没人知道。这就是理论计算机科学头号未解之谜 P vs. NP——千禧年七大数学难题之一，克雷研究所悬赏 100 万美元。高效 SAT 算法将瞬间攻克调度、资源分配、电路验证等一大片问题，也会让现有密码学与"网上乱说话" simultaneously 玩完。
原书在正文里随手丢了一个 SAT 实例——四条子句的 AND。别看答案，先当猎手：
谓词公式
Predicate Formulas命题变量只有真假，表达力有限。谓词公式引入两个量词：∀（全称量化，"对所有"）与 ∃（存在量化，"至少有一个"）。∀x∈ℝ. x²≥0 恒真；∃x∈ℝ. 5x²−7=0 为真（x=±√(7/5)）；∀x∈ℝ. 5x²−7=0 为假。"每次真"与"有时真"在数学写作里有上百种说法，但公式只有这两个量词。
3.6.3量词顺序：换一个，差一个世界
"每个美国人都有一个梦想"——∀a∃d H(a,d)（人人有各自的美梦）和 ∃d∀a H(a,d)（全民共享同一个梦）完全两回事。把哥德巴赫猜想的量词调个顺序，就更妙了：
∃p∈Primes ∃q∈Primes ∀n∈Evens. n = p+q ✗ 换序版：所有偶数共享同一对素数
终局自测
Final Check六题，覆盖全章。
彩蛋与课后挑战
Easter Eggs & Problems数学家的 if-then 和妈妈的 if-then 不是一回事（原书习题 3.3）
数学家说："若函数不连续，则不可微。"（¬C ⇒ ¬D，即 D ⇒ C）——严格的蕴含。
妈妈说："你不写作业，就别想看电视。"（¬H ⇒ ¬T）——如果你按数学翻译，这句只禁止"没写作业还看电视"，没说写完作业就能看！但妈妈的意图显然是 H ⟺ T：写完作业才能看电视。
同样的句型，两种翻译都对——数学家的 if-then 是逻辑承诺，妈妈的 if-then 是因果契约。逻辑无视因果，生活处处因果。
从命题逻辑到芯片：半加器（原书习题 3.6 / 3.7）
2 位半加器把 k + b 做成二进制加法，全部由逻辑公式描述：c₀ ::= b，s₀ ::= a₀ XOR c₀，c₁ ::= a₀ AND c₀，s₁ ::= a₁ XOR c₁，c ::= c₂ ::= a₁ AND c₁。每个公式就是一个逻辑门——命题逻辑的化简 = 芯片门数的化简。串联（ripple-carry）结构简单但延迟随位数线性涨；并行（carry look-ahead）设计把延迟压到对数级。你算一算 n 位各自的门数与延迟，就摸到了"公式化简的现实回报"。
Sloppy Sam 的循环证明（原书习题 3.5）
Sam 证出了 P⇒Q、Q⇒R、R⇒P 三条蕴含，然后宣布"P、Q、R 全真"。反例：P=Q=R=F——三条蕴含全部为真（假⇒假仍是真），但 P∧Q∧R 为假！循环蕴含锁不死任何真值：环上只要有一处为假，假就沿环传染一圈，"全假"与"全真"同样自洽。这个反例赋值值得亲手在真值表里验一遍。
SAT 进阶（原书习题 3.8 / 3.10）
3.8：(P̄∨Q) ∧ (Q̄∨R) ∧ (R̄∨S) ∧ (S̄∨P) ∧ M ∧ N̄ 恰有两个满足赋值——别列 2⁶=64 行真值表，按 P 的真假分类讨论（原书就是想教你这招）。
3.10：给一批公式标"有效 V / 可满足非有效 S / 不可满足 N"——互动 ③ 的加强版，做完可以直接当 6.042 助教。