03 · 命题逻辑

⏱ 27 分钟 ｜ ⭐ 最小的形式化语言：只认整句话的真假，不认句子里面有什么

🎯 一句话

把一句话整个塞进一个字母，只保留它的真假，再用五个连接词把这些字母拼起来——这就是命题逻辑的全部。

它简单到近乎简陋，但它有一条别的逻辑都比不了的好处：任何公式的真假，都能在有限步内机械地算出来。

🧱 一、原子命题：能塞进一个字母的东西

命题（proposition）是一个陈述句，它必须有明确的真假。

写公式时我们用单个大写字母代替整句话，这叫缩写方案（scheme of abbreviation）：

P：苏格拉底是秃头　　Q：讲座很无聊　　T：教材读得下去

⚠️ 注意代价：P 里面的「苏格拉底」和「秃头」已经没了。命题逻辑看不见句子内部的结构， 所以它推不出「所有人都会死 + 苏格拉底是人 ⟹ 苏格拉底会死」——那要等第 6 章。

🔗 二、五个连接词

⭐ ∨ 是可兼或：P ∨ Q 在「两个都真」时也为真。上一章那个「汤或沙拉」的歧义，在这里被强行钉死成可兼或——想表达排斥或，你得自己写 (P ∨ Q) ∧ ¬(P ∧ Q)。

⚠️ 蕴含是最反直觉的那个

P → Q 只在一种情况下为假：P 真而 Q 假。也就是说：

只要 P 是假的，P → Q 就自动为真，不管 Q 是什么。

「如果我是外星人，那么我会飞」——这句话是真的，因为我不是外星人。这叫空真（vacuously true）。

⭐ 为什么要这么定义：P → Q 表达的是「承诺」——「P 成立时我保证 Q 成立」。P 根本没发生，承诺就没被违反，所以不算撒谎。⚠️ 它不表达因果关系，P → Q 里 P 和 Q 可以毫无关系。

📐 三、语法：公式是递归造出来的

哪些字符串算合法公式？用 BNF 文法一次说清：

句子     ::= 原子句 | 复合句
原子句   ::= True | False | P | Q | R | ...
复合句   ::= ( 句子 )
          | 句子 连接词 句子
          | ¬ 句子
连接词   ::= ∧ | ∨ | → | ↔

⭐ 注意它是递归的：「句子」的定义里又出现了「句子」。所以公式可以任意深地套下去， 而判断一个字符串是不是公式，是纯机械的——按规则拆，能拆干净就是。

⭐ 公式只是符号。 到这一步为止，¬A ∧ (B → C) 什么意思都没有—— 语法只管形状，意思要等下一节的语义。

🌍 四、语义：模型与真值表

模型 = 一次真值指派

模型（model）：给每个命题符号指定一个真值（真 / 假）。也叫世界（world）。

有 2 个符号 P、Q，就有 4 个模型（TT、TF、FT、FF）；有 n 个符号，就有 2ⁿ 个模型。

连接词的意思，就是这张真值表

⭐ 有了这张表，任何复杂公式的真值都能算——从最里层往外一层层填。

🖐️ 手算一张：验证一个恒真公式

算 (R ∧ S) → (¬R ∨ S)。加中间列，一列一列填：

⭐ 最后一列全是 T —— 这个公式在所有 4 个模型下都为真。

💡 手算技巧：不要试图一口气算最外层。先把每个子公式各占一列， 从最内层往外填，每一列只查一次上面那张真值表。这样 4 行 6 列的表，两分钟就填完，而且不会错。

🔀 五、⭐ 一句话，两个公式：歧义在这里被抓现行

这是本章最重要的例子。上一章说自然语言有歧义，现在我们把它抓出来量一量。

P：学生来上 COMP4418 的课　　Q：学生通过 COMP4418 考试

句子：「学生不来上课就能通过 COMP4418 考试，这是不成立的。」

这句话有两种读法，取决于「这是不成立的」罩住了哪一段：

它们是同一个公式吗？把真值表拉出来看：

⭐ 4 行里有 2 行不同（第 1、2 行） —— 两种读法是两个不同的公式。

⭐⭐ 更值得注意的是：B 为真的那一行（FF），A 也为真；反过来不成立。 也就是说 B 比 A 严格更强——⭐ 这个「谁比谁强」的关系，下一章会告诉你它就是集合的包含关系。

⭐ 这就是形式化的收益：原来两个人吵「这句话到底什么意思」，谁也说服不了谁； 现在变成两张真值表，指着第 1 行说「你的读法这里是 T、我的是 F」，争论就结束了。

🏷️ 六、三种公式：恒真、矛盾、可满足

看「最后一列」有多少个 T，公式就分成三类：

⚠️ 恒真的一定可满足，反过来不成立。三类不是并列的，是套着的。

⭐ 一条要背下来的对偶

$$\varphi \text{ 恒真} \iff \neg\varphi \text{ 不可满足}$$

理由一句话：φ 每行都 T ⟺ ¬φ 每行都 F。

⭐ 别小看这一条。第 5 章整套「反证法 + 分辨率」的合法性， 全靠它：想证一个东西恒真，就去证它的否定推不出任何一个可能世界。 计算机不擅长「检查所有情况都对」，但很擅长「把所有情况都堵死」。

💥 七、真值表能解决一切——代价是 2ⁿ

好消息：命题逻辑是可判定的。任何问题（这公式恒真吗？可满足吗？）都能靠真值表在有限步内回答。

坏消息：

⭐ 而现实里的 SAT 问题动辄几万到几百万个变量。所以真值表是「理论上行、实践上死」的方法。 第 5 章给出的分辨率法最坏情况仍是指数的，但它有一个真值表没有的性质： ⭐ 它常常在遍历完所有世界之前就结束——因为它不查世界，它推符号。

🔗 这一章连到哪里

✅ 检查点

1. 什么样的句子才能当命题？举两个不能当命题的例子。
2. 用一个字母代替一整句话，代价是什么？这个代价具体挡住了哪一类推理？
3. P ∨ Q 在「P、Q 都真」时是真还是假？要表达「二选一，不能都要」该怎么写？
4. P → Q 什么时候为假？「如果我是外星人，那么我会飞」是真是假，为什么？
5. n 个命题符号有多少个模型？手算真值表的技巧是什么？
6. 「学生不来上课就能通过考试，这是不成立的」的两种读法各是什么公式？真值表里差几行？哪个更强？
7. 恒真、可满足、不可满足怎么定义？「φ 恒真 ⟺ ¬φ 不可满足」为什么成立，它有什么用？
8. 命题逻辑是可判定的，为什么真值表法在实践中还是不够用？

🛑 可以停在这里

⚡ 走神救援

命题逻辑 = 把一整句话塞进一个字母，只留真假，再用五个连接词拼起来。代价是句子内部结构全没了（P 里的「苏格拉底」「秃头」看不见），所以它推不出三段论——要等第 6 章。五个连接词：¬ ∧ ∨ → ↔。⚠️ ∨ 是可兼或（都真时也真，排斥或要写 (P ∨ Q) ∧ ¬(P ∧ Q)）；⚠️ P → Q 只在「P 真 Q 假」一行为假，所以 P 假时它自动为真（空真）——「如果我是外星人那么我会飞」是真的；→ 表达承诺不表达因果。语法用 BNF 递归定义（「句子」的定义里又出现「句子」），判断合法与否纯机械；A + B、A ¬ B 都不是公式。⭐ 到语法为止公式什么意思都没有。语义：一个模型就是一次真值指派，n 个符号有 2ⁿ 个模型；手算真值表的技巧是⭐ 每个子公式各占一列、从最内层往外填。⭐⭐ 本章的杀手例：「学生不来上课就能通过考试，这是不成立的」有两种读法——A：¬P → ¬Q、B：¬(¬P → Q)，真值表 4 行里有 2 行不同，而且 B 只在 P、Q 全假那一行为真，A 在那行也真 → B 严格更强（这个「更强」到下一章会变成集合包含）。形式化的收益就在这：争论变成指着真值表第 1 行说「你这里是 T、我这里是 F」。三类公式：恒真（全 T，如 P ∨ ¬P、(R ∧ S) → (¬R ∨ S)）、可满足（至少一个 T）、不可满足（全 F，如 P ∧ ¬P），三者是套着的不是并列的。⭐ 要背的一条：φ 恒真 ⟺ ¬φ 不可满足——第 5 章的反证法全靠它。命题逻辑可判定，但真值表是 2ⁿ：20 个符号 100 万行、40 个 1 万亿、60 个 10 亿亿，而真实 SAT 问题有几万到几百万变量——理论上行、实践上死。

下一节 👉 04-模型集.md ⭐⭐

去那里的理由：本章你一直在填真值表的「行」。04 把这些行收成一个集合， 于是连接词全部变成集合运算，「蕴含」变成一张文氏图——这是整段逻辑最漂亮的一次视角切换。