跳到主要内容

逻辑智能体 — 知识库、wumpus 世界与命题推理

这一章讲三件事: 「知识」变成计算机里的东西之后长什么样; 一个只能闻到臭味和微风的 agent,怎么推出看不见的陷阱在哪; 以及判断「KB 是否蕴含 α」的三条算法路线各要多少计算。 读完你会拿到一条贯穿第 7–9 章的暗线:表示的表达力,决定推断的代价。

1. 这一章讲什么​

第 1 章的基于模型的 agent 会维护内部状态,但它不知道任何一般事实—— 寻路 agent 不知道「路的长度不可能是负数」。本章的 agent 升级为 基于知识的智能体:对知识的内部表示进行推理,来确定动作1。

核心部件是知识库(KB):一组用知识表示语言写成的语句。 直接写进去的叫公理;从旧语句推出新语句的动作叫推断; 推断的铁律只有一条:向 KB 询问(Ask)时,答案必须遵循已告知(Tell) 的内容——不能捏造2。

「知识层面」与「实现层面」的区分是这个框架的卖点: 出租车要过金门大桥,因为「它知道这是唯一通路」——这个分析 与它用链表还是神经网络存地理毫无关系3。

2. 顶层全景​

  agent 循环:Tell(KB, 感知) → Ask(KB, 该做什么) → Tell(KB, 已做动作)
                                │
      KB ⊨ α? (蕴含:在 KB 为真的每个模型中 α 也为真)
                                │
     ┌──────────────────────────┼──────────────────────┐
     ▼                          ▼                      ▼
  模型检验                  定理证明                局部搜索
  枚举所有模型              推断规则+搜索证明        WalkSAT 翻符号
  TT-Entails? O(2^n)        归结(CNF+空子句)        可靠但可能不终止
  余 NP 完全                前向/反向链接(霍恩:线性)  「想不出反例」≠证明
     │                          │                      │
     └──── SAT 视角:KB ⊨ α ⟺ KB ∧ ¬α 不可满足(DPLL/WalkSAT)

图说:三种路线共享同一个 SAT 视角;差别只在「什么时候能算完」。

3. 核心原理​

3.1 主走查(一):wumpus 世界的两级推理​

主走查的世界:4×4 洞穴,一只吃人的 wumpus、若干无底洞(每格 0.2 概率)、 一块金子。agent 只有一支箭;性能度量:金子 +1000、死亡 −1000、 每个动作 −1、空放一箭 −10。传感器只有五件套: 臭味(与 wumpus 直邻)、微风(与坑直邻)、闪光、碰撞、惨叫4。

第一步推理(逻辑版):agent 在 [1,1] 什么也没感觉到, 立刻断定 [1,2] 和 [2,1] 没有 wumpus 也没有坑(不直邻就没有信号)。 前进到 [2,1],闻到微风——某个邻格有坑;[1,1] 已排除, 所以坑在 [2,2] 或 [3,1] (标「P?」)。谨慎的 agent 掉头走 [1,2]5。

第二步推理(结合时间与地点):在 [1,2] 闻到臭味却没有微风。 两条规则各推一步:臭味 ⟹ wumpus 在 [1,3]([1,1] 排除;若在 [2,2], 刚才在 [2,1] 就该闻到——用了不同时刻的感知);无微风 + 「坑在 [2,2] 或 [3,1]」⟹ 坑在 [3,1]。书里特意点出:这是一次「相当复杂的推断, 它结合了在不同时间、不同地点获取的信息,并在缺乏感知的情况下 迈出了关键的一步」6。

概率版将在第 9 章回来:逻辑只能告诉你在 [2,2] 没有确定结论, 概率能告诉你 [2,2] 有坑的可能性是 86%——该不该避开,只有概率能答7。

3.2 命题逻辑:先定写法,再定真假​

语法就是「合法语句怎么写」。

语义就是「语句何时算真」。语法五件套:¬ ∧ ∨ ⇒ ⇔ 加括号;原子语句是一个命题符号(如 W1,3)8。

语义用「模型」定义:模型 = 给每个符号指定真/假。真值表里四行中唯一 可能惹麻烦的是 P⇒Q——只要 P 为假,整个蕴涵式为真,哪怕 Q 荒谬。 书里的例子:「5 是奇数蕴涵东京是日本的首都」是真语句; 「5 是偶数蕴涵 Sam 很聪明」也为真。理解它只需换个读法: 「P⇒Q」=「如果 P 真,我可以断言 Q;否则我什么也没说」9。 正是这个「前提假即真」的性质,让 ∀ 和 ⇒ 天然搭配(下一章)。

蕴含(KB ⊨ α):在 KB 为真的每个模型中 α 也为真10。 书里给了一个可数的走查:只看 [1,2]、[2,2]、[3,1] 三个格子的坑, 共 2³=8 个模型;已知 [1,1] 无微风、[2,1] 有微风,KB 为真的模型只剩 3 个; 「[1,2] 无坑」在这 3 个里全真,所以被蕴含;「[2,2] 无坑」在其中 2 真 1 假, KB 对它不表态11。这是「逻辑知道什么、不知道什么」的精确说法。

3.3 模型检验:最老实也最贵的算法​

TT-Entails? 直接枚举所有真值组合:7 个符号 128 个模型,KB 真的 3 个, 逐个查 α12。它可靠(直接照定义办事)、完备(对所有 KB 和 α 都适用), 但时间 O(2^n)——而且这不是实现偷懒:命题蕴含本身是余 NP 完全的, 所有已知推断算法最坏都是指数13。

3.4 定理证明:不数模型,数证明​

换一条路:直接对 KB 应用推断规则,把证明「长」出来。 书里先立了两条基础规则——肯定前件(α 与 α⇒β 在手,得 β) 和合取消去——它们可靠性的验证只需真值表四行14。

主走查(二):五步证明 [1,2] 没有坑。 从 KB 的规则 R1–R5 出发 (R2:一个格子有微风,当且仅当邻格有坑;R4:[1,1] 无微风)15:

  (1) 对 R2 用「等价消去」(A⇔B 拆成两条 ⇒)
  (2) 对所得 R6 用「合取消去」,取出方向 [1,1]→邻格有坑的那条
  (3) 用「假言易位」(α⇒β ≡ ¬β⇒¬α):邻格无坑 ⇒ [1,1] 无微风 反过来用
  (4) 与感知 R4(¬B1,1)一起用「肯定前件」→ [1,2] 和 [2,1] 都没有坑
  (5) 用「德摩根律」整理成 ¬P1,2 ∧ ¬P2,1

16

证明即搜索:初始状态=KB,动作=应用推断规则,目标=出现待证语句17。 定理证明的威力在于聚焦:上面五步根本没碰 B2,1、P3,1 这些符号; 哪怕 KB 再加一百万条语句,这个证明一个字都不用改——而真值表 会被指数爆炸直接压死18。

归结是把这件事推到完备的单一规则:两个子句里有互补文字 (如 ¬P2,2 与 P2,2),合并时把这对删掉。单文字归结、因子提取都是它的变体19。 它适用于一切命题语句的诀窍是先转成 CNF(合取范式): 消 ⇔ → 消 ⇒ → 把 ¬ 内移(德摩根)→ 用分配律摊平 ∧/∨20。 然后反证法上场:要证 KB⊨α,就证 KB∧¬α 推得出空子句—— 空析取式恒为假,导出它即矛盾21。

3.5 霍恩子句:约束表达力,换来线性时间​

确定子句 = 至多一个正文字的子句(¬A∨¬B∨C 就是 A∧B⇒C)。 只用确定子句写 KB,三个好处22:可读(蕴涵式,体/头)、 可高效推断(前向/反向链接,线性时间)、是逻辑编程的基础。

  • 前向链接(数据驱动):从已知事实出发,数着每条规则还差几个前提 (count 表),凑齐就点火,把结论加入队列。看到刹车灯就刹车、 但不知道为什么的,就是它23。
  • 反向链接(目标导向):从查询倒着找「谁能推出它」,递归验证前提。 回答「我的钥匙在哪」这种具体问题,代价远小于线性24。

3.6 SAT 求解与它的边界​

蕴含 ⟺ 不可满足性检验(KB∧¬α 无模型),于是 SAT 求解器接管一切25。 DPLL:在 TT-Entails 的穷举上加三个剪枝——提前终止(一个文字真, 整个子句真)、纯符号启发式(全库只以一种极性出现的符号直接定值)、 「只剩一个文字还可能为真」的子句启发式:直接定值并连锁反应(这一步称为单元传播:一个连锁的定值反应)26。 WalkSAT:随机翻转符号,一半时间选「最能减少冲突子句」的翻转, 一半时间纯随机;p≈0.5。它可靠但不完备:返回失败有两种可能—— 真的无解,或者时间不够。书里的判词很准:agent 可以说 「我想了一小时,想不出这个格子不安全的可能世界」,但这不是证明27。

随机 3-CNF 上有一条著名经验曲线:子句/符号比低于 4.3 几乎全可解, 高于它几乎全不可解,而最难的问题恰好聚在 4.3 的峭壁上28。

3.7 命题逻辑 agent 与它的天花板​

把感知带上时间戳(Stench⁴ 而非 Stench,避免与上一时刻的 ¬Stench³ 矛盾), 把世界随时间变化的部分写成流(fluent),再加后继状态公理—— agent 就能维护「世界现在什么样」的逻辑估计29。更进一步,SATPlan 把「找一个到达目标的规划」整个变成 SAT:翻译成 CNF,交给求解器, 从模型里读出动作序列30。

但这里撞上了表达力的墙。SATPlan 第一次跑就把 [Shoot⁰] 也当成了 到达 [2,1] 的合法规划——因为 KB 没说过「agent 不能同时在两个位置」; 要修,得补上唯一位置公理、前提公理、动作排除公理31。 更根本的:100×100 的场地、1000 个时间步,KB 里的语句要以亿计—— 「对于每个时刻 t」「对于每个方格 [x,y]」这种模式,命题逻辑只能靠展开硬扛。 书里的结论是一阶逻辑的预告:同样大小的 wumpus 世界, 一阶逻辑用大约 10 条语句就能描述32。

4. 作者的判断与证据​

  • (书内定理) 归结 + CNF 构成完备推断过程(基本归结定理); 命题蕴含余 NP 完全——上界与下界都写死了1333。
  • (书内观察) 前向链接的不动点本身构成 KB 的一个模型—— 完备性的证明思路比定理本身更值得带走34。
  • (书内经验规律) 随机 3-SAT 的 4.3 峭壁;最难实例聚集在阈值(临界比值)处。 书里如实注明:可满足性阈值猜想「即便对 k=3 也仍未被证明」35。
  • (作者的立场) 「连接主义与逻辑之争」在书里被处理成表示选择问题: 布尔电路与神经电路都能实现条件-动作规则(第 2 章注脚), 而 SATPlan 的失败暴露的是语言表达力,不是「逻辑不行」36。
  • (书内坦白) 落地问题:KB 在真实世界里是否为真,取决于传感器与 学习过程;学习可能出错——「wumpus 有臭味,但闰年 2 月 29 日除外, 因为这一天它要洗澡」37。

5. 边界与局限​

  • 命题逻辑没有对象与变量:每个方格×每个时刻都要单独一个符号。 这是下一章的全部动机。
  • WalkSAT 式的「找不反例」推断在安全攸关场景(证明格子安全)不可用。
  • 真值表与 DPLL 最坏指数;这是问题本身的复杂度,不是工程缺陷。
  • wumpus 世界对真实世界的映射是修辞:感知无噪声、规则全知—— 正因为这些假设,概率(第 9 章)才显得必要。

6. 可带走的​

  1. 「不能捏造」是把逻辑 agent 与普通程序区分开的一条线: Ask 的每个答案都必须遵循 Tell 过的内容。
  2. 蕴含的读法是集合包含:M(KB) ⊆ M(α)。KB 越强,留下的模型越少,断言越多。
  3. ⇒ 的真值表(前件假即真)不是反直觉的 bug,是让一般规则可写的 feature。
  4. 「KB ⊨ α ⟺ KB∧¬α 不可满足」一句打通三条算法路线:模型检验、归结、SAT。
  5. 约束表达力能换线性时间:能写成确定子句就别用一般子句。
  6. 归谬法是定理证明的主引擎;找证明 = 搜索,规则就是算子。
  7. 一个知识库的第一批 bug 往往是「没说出口的常识」(不能同时在两地)—— SATPlan 是极好的 KB 调试器。

7. 原文地图​

主题原书章原文位置
KB/Tell/Ask/不捏造7.1text/10-fm.txt:7039(搜「知识库」) · text/10-fm.txt:954(搜「遵循」)
知识层面 vs 实现层面7.1text/10-fm.txt:7076(搜「知识层面」)
wumpus PEAS7.2text/10-fm.txt:7105(搜「+1000」) · text/10-fm.txt:7121(搜「5 个传感器」)
两级推理走查7.2text/10-fm.txt:7153(搜「[1, 2]」) · text/10-fm.txt:7166(搜「wumpus 在 [1, 3]」) · text/10-fm.txt:7168(搜「相当复杂的推断」)
概率版预告7.2 注text/10-fm.txt:7254(搜「概率」)
语法/联结词7.4.1text/10-fm.txt:7279(搜「原子语句」) · text/10-fm.txt:7285(搜「联结词」)
⇒ 真值表反直觉7.4.2text/10-fm.txt:7363(搜「奇数蕴涵东京」)
蕴含定义7.3text/10-fm.txt:7195(搜「蕴含」) · text/10-fm.txt:7198(搜「每个模型」)
8 模型走查7.3text/10-fm.txt:7208(搜「8 个可能的模型」) · text/10-fm.txt:7221(搜「α 1」)
干草堆与针7.3text/10-fm.txt:7232(搜「草堆」)
可靠/完备7.3text/10-fm.txt:7237(搜「可靠」)
落地与学习出错7.3text/10-fm.txt:7267(搜「洗澡」)
TT-Entails 128 模型7.4.4text/10-fm.txt:7406(搜「27=128 个可能的模型」)
余 NP 完全7.4.4text/10-fm.txt:7455(搜「NP 完全」)
肯定前件7.5.1text/10-fm.txt:7514(搜「Modus Ponens」)
五步证明7.5.1text/10-fm.txt:7530(搜「等价消去」) · text/10-fm.txt:7538(搜「德摩根律」)
证明=搜索7.5.1text/10-fm.txt:7541(搜「搜索算法」)
证明的聚焦性7.5.1text/10-fm.txt:7556(搜「一百万条」)
单调性7.5.1text/10-fm.txt:7558(搜「单调性」)
归结规则7.5.2text/10-fm.txt:7585(搜「归结」) · text/10-fm.txt:7592(搜「单元归结」)
CNF 四步7.5.2text/10-fm.txt:7622(搜「消去 ⇔」)
空子句=蕴含7.5.2text/10-fm.txt:3329(搜「反证法」) · text/10-fm.txt:7676(搜「空子句」)
基本归结定理7.5.2text/10-fm.txt:7694(搜「归结闭包」)
确定子句/霍恩7.5.3text/10-fm.txt:7723(搜「确定子句」) · text/10-fm.txt:7731(搜「3 个」)
前向链接7.5.4text/10-fm.txt:7744(搜「前向链接」) · text/10-fm.txt:7791(搜「数据驱动」)
反向链接7.5.4text/10-fm.txt:7798(搜「反向链接」) · text/10-fm.txt:7803(搜「目标导向」)
DPLL 三改进7.6.1text/10-fm.txt:7827(搜「提前终止」) · text/10-fm.txt:7834(搜「纯符号」) · text/10-fm.txt:7841(搜「单元子句」)
WalkSAT7.6.2text/10-fm.txt:7906(搜「WalkSAT」) · text/10-fm.txt:7933(搜「思考了一小时」)
4.3 峭壁7.6.3text/10-fm.txt:7958(搜「4.3」) · text/10-fm.txt:7962(搜「猜想」)
流 fluent7.7.1text/10-fm.txt:8003(搜「Stench」) · text/10-fm.txt:8007(搜「流」)
SATPlan 的 Shoot⁰7.7.4text/10-fm.txt:8219(搜「Shoot」) · text/10-fm.txt:8225(搜「调试工具」)
前提/动作排除公理7.7.4text/10-fm.txt:8234(搜「前提公理」) · text/10-fm.txt:8243(搜「动作排除公理」)
10 条语句的预告7.7.4text/10-fm.txt:8254(搜「上亿」) · text/10-fm.txt:8259(搜「10 条」)

Footnotes​

  1. 出处:「逻辑智能体」第 7012 段(text/10-fm.txt:7012,搜「基于知识的智能体」)。 ↩

  2. 出处:「逻辑智能体」第 7039 段(text/10-fm.txt:7039,搜「知识库」)与 第 7050 段(text/10-fm.txt:7050,搜「不能进行捏造」)。 「推断过程中不能进行捏造」在 7050 段。 ↩

  3. 出处:「逻辑智能体」第 7076 段(text/10-fm.txt:7076,搜「知识层面」)。 金门大桥例子在 7078–7082 段。 ↩

  4. 出处:「逻辑智能体」第 7105 段(text/10-fm.txt:7105,搜「+1000」)与 第 7121 段(text/10-fm.txt:7121,搜「5 个传感器」)。 每格 0.2 概率的坑在 7109 段。 ↩

  5. 出处:「逻辑智能体」第 7153 段(text/10-fm.txt:7153,搜「[1, 2]」)与 第 7160 段(text/10-fm.txt:7160,搜「微风」)。 「P?」标记在 7162 段。 ↩

  6. 出处:「逻辑智能体」第 7168 段(text/10-fm.txt:7168,搜「相当复杂的推断」)。 wumpus 在 [1,3] 的推断在 7166 段。 ↩

  7. 出处:「逻辑智能体」第 7254 段(text/10-fm.txt:7254,搜「概率」)。 ↩

  8. 出处:「逻辑智能体」第 7279 段(text/10-fm.txt:7279,搜「原子语句」)。 ↩

  9. 出处:「逻辑智能体」第 7363 段(text/10-fm.txt:7363,搜「奇数蕴涵东京」)。 「否则我无法断言」的读法在 7365–7366 段。 ↩

  10. 出处:「逻辑智能体」第 7195 段(text/10-fm.txt:7195,搜「蕴含」)。 ↩

  11. 出处:「逻辑智能体」第 7208 段(text/10-fm.txt:7208,搜「8 个可能的模型」)与 第 7226 段(text/10-fm.txt:7226,搜「无法断定」)。 ↩

  12. 出处:「逻辑智能体」第 7406 段(text/10-fm.txt:7406,搜「27=128 个可能的模型」)。 ↩

  13. 出处:「逻辑智能体」第 7455 段(text/10-fm.txt:7455,搜「NP 完全」)。 ↩ ↩2

  14. 出处:「逻辑智能体」第 7514 段(text/10-fm.txt:7514,搜「Modus Ponens」)。 可靠性验证在 7522 段。 ↩

  15. 出处:「逻辑智能体」第 7389 段(text/10-fm.txt:7389,搜「R1 : ¬P1,1」)。 R2 的双向蕴含式在 7391 段;R4 在 7398 段。 ↩

  16. 出处:「逻辑智能体」第 7530 段(text/10-fm.txt:7530,搜「等价消去」)至 第 7540 段(text/10-fm.txt:7540,搜「都没有无底洞」)。 ↩

  17. 出处:「逻辑智能体」第 7541 段(text/10-fm.txt:7541,搜「搜索算法」)。 ↩

  18. 出处:「逻辑智能体」第 7556 段(text/10-fm.txt:7556,搜「一百万条」)。 ↩

  19. 出处:「逻辑智能体」第 7585 段(text/10-fm.txt:7585,搜「归结」)与 第 7592 段(text/10-fm.txt:7592,搜「单元归结」)。 ↩

  20. 出处:「逻辑智能体」第 7622 段(text/10-fm.txt:7622,搜「消去 ⇔」)。 四个步骤编号在 7622–7638 段。 ↩

  21. 出处:「逻辑智能体」第 3329 段(text/10-fm.txt:3329,搜「反证法」)与 第 7676 段(text/10-fm.txt:7676,搜「空子句」)。 ↩

  22. 出处:「逻辑智能体」第 7723 段(text/10-fm.txt:7723,搜「确定子句」)与 第 7731 段(text/10-fm.txt:7731,搜「3 个」)。 ↩

  23. 出处:「逻辑智能体」第 7744 段(text/10-fm.txt:7744,搜「前向链接」)与 第 7791 段(text/10-fm.txt:7791,搜「数据驱动」)。 ↩

  24. 出处:「逻辑智能体」第 7798 段(text/10-fm.txt:7798,搜「反向链接」)与 第 7803 段(text/10-fm.txt:7803,搜「目标导向」)。 ↩

  25. 出处:「逻辑智能体」第 7812 段(text/10-fm.txt:7812,搜「可满足性检验」)。 ↩

  26. 出处:「逻辑智能体」第 7827 段(text/10-fm.txt:7827,搜「提前终止」)、 第 7834 段(text/10-fm.txt:7834,搜「纯符号」)与 第 7841 段(text/10-fm.txt:7841,搜「单元子句」)。 「级联」即单元传播在 7849 段。 ↩

  27. 出处:「逻辑智能体」第 7906 段(text/10-fm.txt:7906,搜「WalkSAT」)与 第 7933 段(text/10-fm.txt:7933,搜「思考了一小时」)。 ↩

  28. 出处:「逻辑智能体」第 7958 段(text/10-fm.txt:7958,搜「4.3」)。 ↩

  29. 出处:「逻辑智能体」第 8003 段(text/10-fm.txt:8003,搜「Stench」)与 第 8007 段(text/10-fm.txt:8007,搜「流」)。 ↩

  30. 出处:「逻辑智能体」图 7-22 说明,第 8208 段(text/10-fm.txt:8208,搜「SATPlan」)。 ↩

  31. 出处:「逻辑智能体」第 8219 段(text/10-fm.txt:8219,搜「Shoot」)、 第 8225 段(text/10-fm.txt:8225,搜「调试工具」)、 第 8234 段(text/10-fm.txt:8234,搜「前提公理」)、 第 8243 段(text/10-fm.txt:8243,搜「动作排除公理」)。 ↩

  32. 出处:「逻辑智能体」第 8254 段(text/10-fm.txt:8254,搜「上亿」)与 第 8259 段(text/10-fm.txt:8259,搜「10 条」)。 ↩

  33. 出处:「逻辑智能体」第 7694 段(text/10-fm.txt:7694,搜「归结闭包」)。 ↩

  34. 出处:「逻辑智能体」第 7787 段(text/10-fm.txt:7787,搜「不动点」)。 ↩

  35. 出处:「逻辑智能体」第 7960 段(text/10-fm.txt:7960,搜「猜想」)。 ↩

  36. 出处:「逻辑智能体」第 8255 段(text/10-fm.txt:8255,搜「深层次的问题」)。 ↩

  37. 出处:「逻辑智能体」第 7267 段(text/10-fm.txt:7267,搜「洗澡」)。 ↩