06 · 一阶逻辑

⏱ 38 分钟 ｜ ⭐⭐ 把句子拆开：对象、性质、关系，以及「所有」和「有些」

🎯 一句话

命题逻辑把一整句话塞进一个字母，于是「所有人都会死」和「苏格拉底是人」之间没有任何可用的联系；一阶逻辑把字母拆成「对象 + 谓词 + 量词」，那条联系就回来了。

🧱 一、命题逻辑撑不住的地方

「所有人都会死」P、「苏格拉底是人」Q、「苏格拉底会死」R —— ⚠️ P ∧ Q ⊨ R 不成立：三个字母之间没有结构，P 里的「所有」和「苏格拉底」全看不见。

缺两样：① 对象和谓词（小明会编程 该拆成「小明 / 会 / 编程」）② 变量和量词（「所有学生」要能一次说完）。一阶逻辑写成：

$$\forall x\,(Student(x) \to Knows(x, Programming))$$

🔩 二、新的零件

⭐ 函数和谓词最容易混：函数返回对象，谓词返回真假。 cityOf(Alice) 是一个城市，不能问它真不真；VisitedCity(Alice, Melbourne) 是一句话，只有真假。

于是语法上有两类东西：项（解释成对象）和公式（解释成真假）。BNF 文法：

公式     ::= 原子公式 | 公式 连接词 公式 | 量词 变量 公式 | ¬ 公式 | ( 公式 )
原子公式 ::= P(T1, ..., Tn)              P 是 n 元谓词，Ti 是项
项       ::= c | v | F(T1, ..., Tn)      常量 | 变量 | n 元函数套项
连接词   ::= → | ∧ | ∨ | ↔        量词 ::= ∀ | ∃

💡 命题逻辑是一阶逻辑的特例：没有量词、变量、函数，谓词全是 0 元的—— 0 元谓词不带参数、只有真假，那正是一个命题。

✍️ 三、翻译：⭐ ∀ 配 → ，∃ 配 ∧

⭐⭐ 规律：∀ 后面几乎总跟 →，∃ 后面几乎总跟 ∧。配错意思会彻底变：

⭐ 为什么是这个搭配：∀ 遍历所有对象，必须先用 → 把范围缩到你关心的那些；∃ 只要找到一个，就用 ∧ 钉住全部条件。

🎯 四、作用域、自由与约束

作用域 = 量词管到的那段子公式。约束变量 = 落在某量词作用域里的；自由变量 = 没被罩住的。 闭公式（句子） = 没有自由变量的公式 —— ⭐ 只有闭公式才有确定的真假。

P(x) 里 x 自由、不是闭公式；∀x P(x) 里 x 被约束、是闭公式；∃y Q(y,z) 里 y 约束而 z 自由，不是闭公式。

⚠️ 括号决定一切：∀z P(z) → ¬Q(z) 里 ∀z 只管 P(z)，后面那个 z 是自由的。要罩住整句必须写 ∀z (P(z) → ¬Q(z))。

🔀 五、⭐ 量词顺序：经典考点

日常版：「每个人都有妈妈」（∀x∃y）对 「有一个人是所有人的妈妈」（∃y∀x）——第二句显然强得多。

🖐️ 手算：三个人，一张关系表

论域 D = {小明, 小红, 小刚}，关系 欣赏 = {(小明,小红), (小红,小刚), (小刚,小明)}。

• ∀x∃y 欣赏(x,y)：三人各有欣赏对象 → ⭐ 真
• ∃y∀x 欣赏(x,y)：小红只被小明欣赏、小刚只被小红欣赏、小明只被小刚欣赏，没人被三个人都欣赏 → ⭐ 假

把关系换成 {(小明,小红), (小红,小红), (小刚,小红)}（三人都欣赏小红），则两个都真（取 y = 小红）。

⭐⭐ 结论：∃y∀x φ ⊨ ∀x∃y φ，反过来不成立。 这正是第 2 章「每个学生都读了一本书」那两种读法的准确形式——换个量词顺序，是两个不同强度的断言。

🌍 六、语义：模型是一个二元组

模型 M = ⟨D, I⟩：D 是论域（非空的对象集合，我们在谈论谁）；I 是解释函数—— 常量 → D 里一个对象；n 元函数 → 一个 Dⁿ→D 的函数；⭐ n 元谓词 → Dⁿ 的一个子集（哪些元组让它为真）。

🖐️ 手算：验证公式在模型里成不成立

公式 ∀x∀y (Enrolled(x,y) → Student(x))（「选了课的都是学生」）。模型： D = {ALICE, BOB, C4418, C9020}，I(Student) = {ALICE, BOB}，I(Enrolled) = {(ALICE, C4418), (BOB, C9020)}。

x、y 各 4 种取值 → 共 16 对要查：

⭐ 16 对全过 → M ⊨ ∀x∀y (Enrolled(x,y) → Student(x))。⭐ 那 14 对靠空真白送——「∀ 配 →」的绝大多数情况都这样通过，真正被检查的只有前件为真的那几个。

⚠️ 换个模型就可能为假：往 I(Enrolled) 里加一条 (C4418, C9020)，前件真而 Student(C4418) 假，公式立刻挂。⭐ 意思全在 I 里——这就是第 2 章那句「一个句子本身什么都不意味着」。

⚙️ 七、推理：流程照搬，多两个零件

流程和第 5 章完全一样：否定结论 → 转 CNF → 反复分辨 → 推出 □。

CNF 七步：① 消 →、↔　② 把 ¬ 推到底（新增 ¬∀x φ ≡ ∃x ¬φ、¬∃x φ ≡ ∀x ¬φ）　③ 变量改名　④ ⭐ Skolem 化，消掉所有 ∃　⑤ 丢掉所有 ∀　⑥ 分配律　⑦ 展平清理。

⭐ 零件一：Skolem 化 —— 给「存在的那个东西」起名字

⭐ 直觉：「每个人都爱着某个人」→ 把 x 爱的那个人叫做 f(x)，于是变成「每个人 x 都爱 f(x)」。 ⚠️ 它不是等价变换（f 是凭空造的），只保证原式可满足 ⟺ 新式可满足——对反证法正好够用。

走一遍 ∀x (Person(x) → ∃y Loves(x,y))：消 → ；Skolem 化；丢 ∀ ⟹ 子句 ¬Person(x) ∨ Loves(x, f(x)) ✅

⭐ 零件二：合一（MGU）

命题逻辑里 P 和 ¬P 一眼对消；一阶逻辑里 Loves(John, z) 和 ¬Loves(x, y) 长得不一样，得先找一个变量替换让它们变成同一个。

⭐ 为什么要「最一般」的那个（MGU）：P(x,y) 与 P(a,z) 用 {x/a, y/z} 就够；{x/a, y/b, z/b} 也能合上，但它白白把 y、z 钉死成 b，会漏掉本来能成的推导——完备性就是这么丢的。

🖐️ 手算：一阶分辨率

KB：① ∀x (Human(x) → Mortal(x))　② Human(Socrates)。求证 Mortal(Socrates)。

⭐ 本章开头那个「命题逻辑做不到」的推理，三步做完。 一阶分辨率同样是可靠 + 反驳完备。

🧩 八、回收：第 2 章那个积木谜题

第 2 章的题：a 在 b 上、b 在 c 上、a 绿、c 非绿，问有没有绿块直接压在非绿块上。现在能写下来了：

$$S = \{On(a,b),\; On(b,c),\; Green(a),\; \neg Green(c)\}$$ $$\alpha = \exists x \exists y\,[\,Green(x) \wedge \neg Green(y) \wedge On(x,y)\,]$$

证明：设 I 是任何让 S 全真的解释，对 Green(b) 分两种情况：

两种情况都得 I ⊨ α，所以 S ⊨ α。∎

⭐⭐ 最值得体会的地方：∃x∃y 只承诺存在，不承诺你能指出是谁——两个分支的见证者完全不同（(b,c) 与 (a,b)），结论却一样成立。这就是第 2 章说的「4 条显式事实逼出一条谁都没写过的结论」。

⚖️ 九、代价：一阶逻辑不可判定

表达力是要付钱的。命题逻辑可判定（真值表必停机，代价 2ⁿ）；⭐ 一阶逻辑不可判定（丘奇 1936），只是半可判定：

结论真成立时，证明器一定能在有限时间内找到证明；不成立时，它可能永远跑下去。

⚠️ 后果比听起来严重：证明器跑了两小时没结果，你分不清是「命题不成立」还是「再等十分钟就出来了」。 ⭐ 所以工业界大量使用被故意削弱的片段——Datalog、描述逻辑（知识图谱的 OWL）、SMT 的可判定理论——拿表达力换回「一定会停」。

（另有二阶、模态、时序（LTL/CTL，用于程序验证）、概率、模糊逻辑等分支，本教程不展开。）

🚪 十、交接：从「什么是真的」到「什么是好的」

⭐ 最大的断裂在最后两行：逻辑里没有「立场」，命题的真假不取决于谁在问；而从第 7 章起，每个结论都挂在「谁的偏好」上——同一个结果，你觉得好、我觉得糟，两边都没错。

⭐ 所以「真」在下一章退场，换成「偏好」：第 7 章要做的第一件事， 就是把「我更喜欢 A 而不是 B」这句大白话，变成一个能排序、能比较、能拿来算期望的数——效用。

🔗 这一章连到哪里

✅ 检查点

1. 命题逻辑缺哪两样东西？函数和谓词怎么区分？什么是闭公式？
2. 为什么 ∀ 配 → 而 ∃ 配 ∧？写反了各会变成什么意思？
3. ∀x∃y 和 ∃y∀x 差在哪？用「三个人互相欣赏」那个例子说明，哪个能推出哪个？
4. 模型由哪两部分组成？谓词被解释成什么？选课那个例子要检查几对，大部分怎么通过的？
5. Skolem 化在干什么？∀x∃y P(x,y) 为什么要用 f(x) 而不是常量？它是等价变换吗？MGU 为什么必须「最一般」？
6. 用一阶分辨率证明 Mortal(Socrates)，写出每一步和合一子。
7. 第 2 章那个积木谜题怎么形式化、怎么证？这个证明能指出是哪一对积木吗？
8. 一阶逻辑的可判定性如何？「半可判定」在实践中意味着什么，工业界怎么应对？

🛑 可以停在这里

⚡ 走神救援

一阶逻辑加进常量、变量、函数、谓词、量词，⭐ 函数返回对象、谓词返回真假；⭐ 命题逻辑就是「谓词全 0 元、无量词无变量」的一阶逻辑。⭐⭐ 翻译铁律：∀ 配 →、∃ 配 ∧——∀ 遍历一切，必须先用 → 缩范围；∃ 只找一个，要用 ∧ 钉住条件；写反了，∀x(Student(x) ∧ …) 变成「一切都是学生」，∃x(Student(x) → …) 只要存在一个非学生就空真。⭐ 只有闭公式才有确定真假。⭐⭐ 量词顺序是经典考点：三人例子（小明→小红、小红→小刚、小刚→小明）里 ∀x∃y 真而 ∃y∀x 假——∃y∀x ⊨ ∀x∃y，反向不成立。模型 M = ⟨D, I⟩，⭐ n 元谓词被解释成 Dⁿ 的子集；选课例子查 16 对，只 2 对前件为真，其余 14 对靠空真白送——意思全在 I 里。推理流程照搬第 5 章，只多两个零件：⭐ Skolem 化（∀x∃y 必须用函数 f(x)；⚠️ 不等价，只保可满足性）和 ⭐ 合一 / MGU（要最一般，多余限制会丢掉完备性）。Socrates 那题三步推到 □，合一子 {x/Socrates}。⭐⭐ 积木谜题解开了：对 Green(b) 分情况——b 绿则见证者 (b,c)，b 非绿则 (a,b)；⭐ 两分支见证者不同，所以「存在」成立却指不出是哪一对。⚠️ 一阶逻辑不可判定（丘奇 1936），只半可判定——成立时一定证得出，不成立时可能永远跑；工业界因此用 Datalog / 描述逻辑（OWL）/ SMT，拿表达力换「一定会停」。⭐ 交接：逻辑问什么是真的，第 7 章起问什么是好的（偏好、效用、目标可能冲突的多个主体）。

下一节 👉 07-偏好与效用.md ⭐⭐

去那里的理由：本章最后那张对照表说明了断裂在哪——逻辑里没有立场，博弈论里全是立场。 07 先把「我更喜欢 A」变成一个能排序、能算期望的数（效用）， 后面所有的均衡、匹配、分配、投票都建在它上面。