L03b Knowledge Representation：岛民说「我是骗子」，这句话在逻辑上不可能被说出来

一句话版

把知识写成符号，再用三种机械规则从已知推出未知：前向链接、后向链接、归结。

一个类比：一间审讯室，证词全都只能是真或假

你面前坐着几个人，每个人要么句句实话、要么句句谎话，没有中间态。你手上还有一叠既有的案卷规则：“如果某人是父亲，那他有孩子”这一类。你的任务是从这堆东西里推出一个确定的结论。

语法管的是笔录该怎么写才算格式合规——哪些符号能接在一起、“P ∧ ¬Q ∨ R”这样的串是不是合法句子。语义管的是把具体真假代进去之后整句成不成立。判据很干脆：只看形状的归语法，需要代值的归语义（p.8）。

有了这两层，审讯就能做了。你把某人说的话翻成符号，再把”要么全真要么全假”这条规则也翻成符号，两边一合取，剩下的工作是穷举所有可能的真假组合看哪几行成立——这就是真值表（p.15）。

案卷厚起来之后穷举就撑不住了。n 个命题符号有 2ⁿ 种组合，12 个符号就是 4096 行（p.20）。于是换成按规则推：前向链接是从手上已有的事实出发，能推什么推什么，一路往前直到目标出现；后向链接是从要证的那个结论倒着找，问”要它成立需要什么”，只碰跟目标有关的规则（p.28、p.34）。

最后一种最像审讯的套路。归结用的是反证：先假设结论不成立，把这条假设塞进案卷里一起推，推到自相矛盾为止——矛盾一出，原结论就被证明了（p.39）。

类比在哪里失效：真实证人可以半真半假，命题逻辑只有 True 和 False 两个值，没有第三种（p.13）。⇒ 在这里跟因果无关，它只声明”不出现前真后假这种组合”，所以”如果我是校长就给全校放假”这句话在我不是校长时是真的，这叫空真（p.14）。课件在开头用 closely approximate 形容符号化这件事：翻译过程一定有损，推出来的结论只在形式化本身正确的前提下才对（p.2）。还有一条——归结法只能回答”矛盾还是不矛盾”，给不出”有多大可能”，那是本周另一份课件的事。

概念卡

1. 三分法与运算符优先级（Syntax / Semantics / Deduction rules）

人话定义：语法管什么样的符号串算合法句子，语义管句子在某个解释下的真假，推理规则管怎么从已知推出未知。后面全部内容都挂在这个三分法上。

例子：优先级从高到低是 ¬ > ∧ > ∨ > ⇒ > ⇔，恰好是连接词在符号表里出现的顺序（p.12）。课件那道加括号题：P ∧ ¬Q ∨ R ⇒ S ⇔ ¬W 等于 (((P ∧ (¬Q)) ∨ R) ⇒ S) ⇔ (¬W)。因为 ⇔ 优先级最低，它总在最外层，看到它先把整句从那里劈成两半。

常见误解

把”P ∧ ¬Q ∨ R 在 P=T,Q=F,R=F 下为真”当成语法问题 → 那是语义。语法只判断它是不是合法句子。给你一个说法问属于哪一层，判据就是要不要代真值（p.8）。

2. 蕴含的空真与 S1 ⇒ S2 ≡ ¬S1 ∨ S2

人话定义：S1 ⇒ S2 为真当且仅当 S1 为假或 S2 为真。前件为假时整个蕴含就为真，这叫空真（vacuous truth）。

例子：把真值表里 ⇒ 那一列和 ¬S1 ∨ S2 那一列并排看，四行完全相同（p.14）。这条等价在课件的等价律表里叫 implication elimination，也是转 CNF 第二步的依据（p.18、p.37）。

常见误解

拿日常的”因为…所以…”理解 ⇒ → 它不表达因果，只表达「不出现前真后假这种组合」。与之相关的另一个高频陷阱是逆否：α ⇒ β 只等价于 ¬β ⇒ ¬α，逆命题 β ⇒ α 和否命题 ¬α ⇒ ¬β 都不等价（p.14、p.18）。

3. 可满足、不可满足与有效（Satisfiable / Unsatisfiable / Valid）

人话定义：按模型数量分类——至少一个模型是 satisfiable，零个是 unsatisfiable，全部 2ⁿ 个解释都为真是 valid。文氏图上 Valid 是 Satisfiable 里面的一个小圈，Unsatisfiable 在外面。

例子：岛民问题那三句话正好是三个实例（p.16、p.17）。“At least one of us is a liar” 形式化成 (AL ⇒ ¬(AL∨BL)) ∧ (¬AL ⇒ (AL∨BL))，四行真值表里只有 AL=F、BL=T 那行成立，1 个模型，结论是 A 说真话、B 是骗子。“None of us is a liar” 有 3 个模型，结论弱到只能说 AL ∨ ¬BL。“I am a liar” 化成 (AL ⇒ ¬AL) ∧ (¬AL ⇒ AL)，0 个模型，不可满足。

三个词的关系是套圈：

常见误解

把”I am a liar”理解成”无法判断” → 它在这个形式化下是逻辑上不可能。真实含义是岛上的人说不出这句话，如果你真听到了，说明”每人要么全真要么全假”这条前提本身有问题（p.16）。

4. Horn 子句与两种链接（Horn Clause / Forward & Backward Chaining）

人话定义：本讲用的 definite clause 要么是单个正命题符号，要么形如「若干符号的合取 ⇒ 符号」；它是 Horn 子句的子类。快速判据是化成析取形式后数没带否定号的文字，0 个或 1 个才是 Horn。

例子：课件那个 KB 有七条——R1: P ⇒ Q，R2: L ∧ M ⇒ P，R3: B ∧ L ⇒ M，R4: A ∧ P ⇒ L，R5: A ∧ B ⇒ L，R6: A，R7: B（p.22）。前向链接从 Agenda = {A, B} 出发，触发顺序是 R5 → R3 → R2 → R1，Agenda 依次变成 {A,B,L}、{A,B,L,M}、{A,B,L,M,P}、{A,B,L,M,P,Q}，R4 全程没被用上。后向链接把同一条链倒过来走：Q 需要 P（R1），P 需要 L 和 M（R2），M 需要 B 和 L（R3），L 选 R5 得到 A 和 B，触底返回（p.23–33）。

这条链画出来更好背：

常见误解

以为后向链接在 p.32 那步可以随便挑规则 → 证 L 时有 R4 和 R5 两条可选，课件明确标注 R4 不能选，因为 P 已经在当前递归路径上，选它就会陷入”证 L 要先证 P、证 P 又要先证 L”的循环。后向链接必须记录已访问目标，前向链接只往前加事实、天然单调，没有这个问题（p.32）。

5. 归结、CNF 与反证法（Resolution）

人话定义：两个析取子句若含一对互补文字（一个有 X、另一个有 ¬X），就能把这一对消掉、其余全部或起来组成新子句。一次只能消一对。

例子：A1 ∨ A2 与 ¬A1 ∨ A3 归结出 A2 ∨ A3（p.35）。归结只对析取子句定义，所以所有句子要先转成 CNF，四步顺序不能乱：消 ⇔ → 消 ⇒ → 把 ¬ 内推（de Morgan 加双重否定）→ 用分配律展平（p.37）。课件那道练习把 α ⇔ (β ∨ γ) 转成 (¬α ∨ β ∨ γ) ∧ (¬β ∨ α) ∧ (¬γ ∨ α)，三个子句（p.38）。

常见误解

以为归结能直接证出蕴含 → 本讲用它做不可满足性反驳。证 KB ⊨ Q 的做法是把 ¬Q 加进集合 S，证 KB ∧ ¬Q 不可满足，依据是”α 有效等价于 ¬α 不可满足”。漏掉 ¬Q 是这类题最常见的失分点（p.39、p.41）。

把它们串起来

整讲的推进只有一个动力：上一种方法的代价太大，所以换下一种。

起点是那张表示层与世界层的对照图：符号之间的 entail 要对应现实之间的 follow，逻辑推理的全部有效性都来自这条对应关系（p.2）。有了这个承诺，就需要一套精确的符号语言，于是有了语法（哪些串合法）和语义（怎么定真假）（p.8–14）。

语义直接给出了第一种证明方法——枚举真值表。岛民问题两个原子只要算四行，很舒服（p.15）。但 n 个符号要 2ⁿ 行，10 个就 1024 行，30 个超过十亿，课件在 p.20 明确写了这是指数级。于是转到语法路线：用推理规则，只碰跟目标相关的句子。

前向链接和后向链接是这条路线的头两个成品，一个数据驱动一个目标驱动，在线性复杂度的课件结论下，要采用相应查重、缓存实现，且这里的 KB 是命题 definite clauses（p.28、p.34）。“Tom 和 John 之间至少有一个是父亲”翻出来是 p ∨ q，两个正文字，Horn 装不下（p.40）。这就是归结存在的理由：它只有一条规则，代价是所有句子先转 CNF，而分配律那一步会让子句数量成倍增长，最坏是指数级的长度（p.37）。每一步都在拿一种成本换另一种。

课件里的坑

• [课件有误] p.22 前向链接 Step 1 原文写的是前提 “true or false” → 按字面读会误导，规则只有在前提为真时才能触发；整个演算过程里进 Agenda 的全是已确定为真的命题（p.22）
• [课件有误] p.34 原文写的是「much less linear in the size of KB」，漏了一个 than → 应读作 much less than linear，意思是后向链接的实际开销取决于与目标相关的那一小片子图，而非整个 KB（p.34）

课后 10 分钟：考点复习

这 10 分钟怎么用：合上页面，先默写三条——语法 + 语义 + 推理三件套、Horn 子句与前向后向链接的驱动方向、归结的反证骨架 KB ∪ {¬Q}；再把下面的「变式题」做一遍；最后回查两个最容易错的地方——忘了 S1 为假时蕴含为真（空真）、归结推出中间子句就收笔。三步做完再往下看答案。

必背

1. 一个逻辑系统 = 语法（结构）+ 语义（含义）+ 推理规则；只看符号形状的是语法，要代入真值判断的是语义。
2. 连接词优先级 ¬ > ∧ > ∨ > ⇒ > ⇔，恰好是它们在课件符号表里出现的顺序。
3. S1 ⇒ S2 在 S1 为假时为真（空真），且 S1 ⇒ S2 ≡ ¬S1 ∨ S2——这条等价是转 CNF 的关键。
4. 解释 = 给每个原子赋真值，n 个原子有 2ⁿ 个解释；模型 = 让句子为真的解释。
5. satisfiable ≥ 1 个模型，unsatisfiable 0 个，valid 全部 2ⁿ 个；Valid ⊂ Satisfiable，且 α 有效等价于 ¬α 不可满足。
6. Horn 子句的正文字不超过 1 个；本讲链接法用恰有 1 个正文字的 definite clause（事实或「合取 ⇒ 符号」）。
7. 前向链接是数据驱动、后向链接是目标驱动；命题 definite-clause KB 配合查重、缓存等实现可线性求解，朴素回溯不自动享有此界。
8. 归结用反证法：S = KB ∪ {¬Q} 全转 CNF 反复归结，推出空子句则 Q 成立；推不出新子句只说明 KB ⊭ Q，不代表 Q 为假。

完整例题

课件 p.40–43 那道 Tom/John 题是这一讲计算量最大的题型，完整走一遍。

题面：Tom 和 John 之间至少有一个是父亲；如果 John 是父亲，那他有一个儿子；如果 Tom 是父亲，那他有一个女儿；Tom 没有女儿。求证：John 有一个儿子。

1. 定符号。p = John is a dad，q = Tom is a dad，r = Tom has a daughter，s = John has a son（p.41）。
2. 写 KB。“至少有一个是父亲” = p ∨ q；“John 是父亲则有儿子” = p ⇒ s；“Tom 是父亲则有女儿” = q ⇒ r；“Tom 没有女儿” = ¬r。注意第一条有两个正文字，不是 Horn 子句，所以不能直接套本讲 definite-clause 链接法，可用归结或真值表（p.40）。
3. 否定目标并入集合。目标是 s，把 ¬s 加进去，集合 S 一共 5 条。
4. 转 CNF。只需用 implication elimination 消掉两个 ⇒：p ∨ q 不变、p ⇒ s 变成 ¬p ∨ s、q ⇒ r 变成 ¬q ∨ r、¬r 不变、¬s 不变（p.42）。
5. 第一轮归结，把所有含互补文字的配对都做一遍：p∨q 与 ¬p∨s 消去 p 得 q ∨ s；p∨q 与 ¬q∨r 消去 q 得 p ∨ r；¬p∨s 与 ¬s 消去 s 得 ¬p；¬q∨r 与 ¬r 消去 r 得 ¬q（p.42）。
6. 第二轮归结。第一轮的 q ∨ s 与 ¬q 消去 q，得到单文字子句 s（p.43）。
7. 最后一步必须写出来：集合里本来就有 ¬s，s 与 ¬s 归结，两个文字全被消掉，什么都不剩，得到空子句 □。课件在这里标注 Null Clause! Contradiction!，但没把这条箭头画出来，答题时不能省。
8. 结论：S = KB ∧ ¬s 不可满足，所以 KB ⊨ s，John 有一个儿子，得证。

整棵归结树长这样：

考场检查用的两行语义验算：Tom 没有女儿（¬r）加上”Tom 是父亲则有女儿”（q ⇒ r），推出 Tom 不是父亲（¬q）；再由”至少一人是父亲”（p ∨ q）推出 John 是父亲（p）；再由 p ⇒ s 推出 John 有儿子（s）。这条链正是归结树上的 ¬q → p → s。

变式题（先自己做）

符号全部沿用上面那题，只把第 4 条前提换成 John 没有儿子（¬s），要证的结论换成 Tom 有一个女儿（r）。用归结法走一遍。

提示

前三条前提的 CNF 一个字都不用改，先把它们抄下来。然后想清楚：要证 r，加进子句集的那一条该写成什么。

参考答案与自检（非官方评分标准）

自检要点：① 加进子句集的必须是结论的否定 ¬r，写成 r 就不是在反驳目标的否定；② 必须一路推到空子句 □，推出 q 还没有完成反驳；③ 能补一句语义验算最稳。

1. 子句集：p∨q、¬p∨s、¬q∨r、¬s，再加上结论的否定 ¬r。
2. ¬p∨s 和 ¬s 归结 → ¬p。
3. p∨q 和 ¬p 归结 → q。
4. ¬q∨r 和 ¬r 归结 → ¬q。
5. q 和 ¬q 归结 → □（空子句），矛盾，故 r 成立。
6. 语义验算：John 没儿子 → 由第 2 条反推 John 不是父亲（¬p）→ 由第 1 条得 Tom 是父亲（q）→ 由第 3 条得 Tom 有女儿（r）。推理链和归结的顺序正好对上。

闪卡自测

1. 「PL 是 FOL 的特例」具体差在哪？

PL 的原子只有整句话的真假，没有对象、谓词和量词。「所有人都会死」在 PL 里只能写成一个不可再分的符号，FOL 里才能写成带 ∀ 的形式。课件从 PL 讲起是因为它的推理算法简单且可判定（p.3）。

2. 逻辑推理的有效性来自哪里？

来自符号层与现实层之间的对应：如果表示是忠实的，符号之间的 entail 就对应现实之间的 follow。课件用 closely approximate 提醒这个翻译过程有损（p.2）。

3. 给 P ∧ ¬Q ∨ R ⇒ S ⇔ ¬W 加上全部括号。

(((P ∧ (¬Q)) ∨ R) ⇒ S) ⇔ (¬W)。顺序是先 ¬ 结合最近的原子，再 ∧，再 ∨，再 ⇒，最后 ⇔ 把整句劈成两半（p.12）。

4. 解释和模型的区别是什么？n 个原子有几个解释？

解释是给每个符号各指定一个真值的一次赋值，n 个原子有 2ⁿ 个解释；模型是其中让句子为真的那些解释。课件说岛民问题第一句「只有一个模型」用的就是这个词（p.13）。

5. 岛民说「At least one of us is a liar」，写出形式化式子和结论。

设 AL = A 是骗子、BL = B 是骗子，A 的话是 AL ∨ BL。要写双向蕴含：(AL ⇒ ¬(AL ∨ BL)) ∧ (¬AL ⇒ (AL ∨ BL))。四行真值表只有 AL=F、BL=T 成立，结论 ¬AL ∧ BL——A 说真话，B 是骗子（p.11、p.15）。

6. 岛民三句话各有几个模型？分别对应哪个术语？

第一句 1 个模型（satisfiable，结论唯一），第二句「None of us is a liar」3 个模型（satisfiable，但结论弱到只能说 AL ∨ ¬BL），第三句「I’m a liar」0 个模型（unsatisfiable，说谎者悖论）（p.16、p.17）。

7. 为什么不用真值表枚举做证明？

行数是 2ⁿ。10 个命题符号要 1024 行，30 个超过十亿。推理规则的优势是只碰跟目标有关的那些句子，不用遍历整个解释空间（p.20）。

8. 判断哪些是 Horn 子句：a、a ∨ b、(a ∧ b) ⇒ c、¬a ∨ ¬b ∨ c。

化成析取后数正文字，0 个或 1 个才是 Horn。a 是（1 个）；a ∨ b 不是（2 个正文字）；(a ∧ b) ⇒ c 化开是 ¬a ∨ ¬b ∨ c，正文字只有 c，是；最后一条与上一条相同，是（p.21）。

9. 写出 R1–R7 那个 KB 的完整前向推导过程。

Agenda 初始 = {A, B}（来自 R6、R7）。触发 R5（A ∧ B ⇒ L）得 L，触发 R3（B ∧ L ⇒ M）得 M，触发 R2（L ∧ M ⇒ P）得 P，触发 R1（P ⇒ Q）得 Q，停止。最终 Agenda = {A,B,L,M,P,Q}，R4 全程没被触发（p.23–p.27）。

10. 前向链接和后向链接各有什么优缺点？

前向是数据驱动，从已知事实往前推，不看目标，缺点是同时可触发多条规则时选哪条是随机的，可能推出一堆无关结论。后向是目标驱动，递归加回溯，只碰相关规则，实际开销可能小于遍历整个 KB，代价是必须记录已访问目标以防循环。本讲命题 definite-clause KB 可用线性算法求解，但朴素后向回溯可能重复子目标，需要查重和缓存（p.28、p.34）。

11. 转 CNF 的四步是什么？为什么顺序不能乱？

消 ⇔（biconditional elimination）→ 消 ⇒（implication elimination）→ 把 ¬ 内推（de Morgan 加双重否定）→ 用分配律展平。不先消两种箭头，de Morgan 无处可用；不先把 ¬ 推到原子上，分配律展出来的仍然不是子句。第四步会让子句数量成倍增长，是归结法的主要代价（p.37）。

12. 命题归结穷尽所有新子句仍未得到空子句，能得出什么结论？

只能说 KB 推不出 Q（KB ⊭ Q），即 KB 为真时 Q 也可能为假。这和「Q 一定为假」是两回事。归结法是反驳完备的：只要 KB ∧ ¬Q 真的不可满足，它一定能推出空子句（p.39）。

下一讲

下一讲离开符号推理，转向让机器自己从数据里学出规则的那条路线。