L03b-3 前向链接:不再列真值表,从已知事实一路往前推
从零讲为什么放弃真值表、什么是 Horn 子句、前向链接怎么用 Agenda 一步步推出目标,用 R1–R7 知识库逐帧演示 R5 → R3 → R2 → R1。
一句话版
前向链接手里有什么事实就用什么:只要某条规则的前提全部已知为真,就触发它,把结论记下来,再接着找下一条能触发的规则,直到目标出现。
它只适用于一种形状的知识库:每条规则都是「几个符号同时为真 ⇒ 一个符号」,这种规则叫 Horn 子句。上一页 L03b-2 用真值表数模型,这一页起换成按规则推。
先认识这几个词
| 词 | 全称 / 读法 | 一句人话 |
|---|---|---|
| KB | knowledge base,知识库 | 所有已知句子的合取,也就是一起成立的那堆规则和事实 |
| 推理规则 | inference rule | 从已有句子生成新句子的固定套路 |
| 可靠 | sound | 推出来的每一句都一定为真 |
| Horn 子句 | Horn clause | 一个符号,或者「若干符号的合取 ⇒ 一个符号」 |
| 前提 / 结论 | premises / conclusion | ⇒ 左边那几个 / ⇒ 右边那一个 |
| 触发 | fire | 前提都已知为真,执行这条规则,得到它的结论 |
| Agenda | 工作内存 | 到目前为止已知为真的符号清单 |
一个类比:按菜谱做菜,有料就开火
厨房里摆着几样现成的食材,墙上贴着一排菜谱。每个菜谱写的是「有了这几样,就能做出那一样」,做出来的东西又可以当别的菜谱的原料。
前向链接的做法是:扫一遍菜谱,看哪个菜谱的原料全齐了,就做那道菜,把成品放上台面。台面上多了一样东西,再扫一遍菜谱。一直做到你要的那道菜出现,或者再也没有能做的菜。
这样做不用考虑你最后想吃什么,有料就开火,所以叫数据驱动。代价是可能顺手做出一堆你根本不需要的半成品。
类比在哪里失效:
- 做菜会消耗原料,逻辑里的事实用过一次还在,可以被任意多条规则反复使用。
- 菜谱可以写「二选一的原料」,Horn 子句不行:前提只能是「全部都要」,结论只能有一个。
从零讲起
1. 为什么不再列真值表
它解决什么问题
前两页判断「KB 能不能推出 Q」,靠的是把真值表全列出来。原子少的时候这很好用,但每多一个原子,行数就翻一倍。需要一条不依赖枚举全部解释的路线。
直觉
课件把证明方法分成两条路线:
- 语义路线:枚举真值表,代价随命题符号个数指数增长。
- 语法路线:用推理规则从旧句子生成新句子,只碰和目标有关的句子。
语法路线有一个硬要求:每一步都必须可靠(sound),推出来的东西必须为真。一串这样的推理步骤,最后生成结论,就叫一个证明。本讲的三种证明方法都走语法路线:前向链接、后向链接、归结。
一步一步看
目标:看真值表行数怎样随原子个数翻倍,到 30 个原子时超过十亿行,枚举已经行不通。
看行数怎么涨:
- 1 个原子:2 行。
- 2 个原子:4 行,岛民题就是这个规模。
- 4 个原子:16 行,后面 Tom/John 那道题就是这个规模。
- 10 个原子:1024 行。
- 30 个原子:超过十亿行。
| 原子个数 | 真值表行数 |
|---|---|
| 1 | 2 |
| 2 | 4 |
| 10 | 1024 |
| 30 | 超过十亿 |
怎么判断
拿到「为什么不用真值表」这类简答题,答两句就够:真值表要枚举 2ⁿ 个解释,是指数级;推理规则只碰和目标相关的句子,不需要遍历整个解释空间。
意思是:真值表能做,只是做不动。后面三种方法都在想办法少碰句子。
常见误解
以为推理规则路线一定比真值表快
推理规则在最坏情况下也可能要碰很多句子。它的优势是通常只需要碰和目标相关的那一小部分,前向和后向链接在 Horn 子句上还能做到线性时间。
试一下
一个 KB 有 3 个命题符号,真值表有几行?再加 1 个呢?
3 个符号是 2³ = 8 行;再加 1 个是 2⁴ = 16 行,翻了一倍。每加一个符号行数都翻倍,这就是指数增长。
2. Horn 子句:链接法能处理的形状
它解决什么问题
前向和后向链接每一步只做一件简单的事:前提齐了,就得出唯一一个结论。这要求每条规则的结论只有一个。Horn 子句就是把「结论只有一个」写成形状上的规定。
从哪来(补充)
这类子句以逻辑学家 Alfred Horn 命名,他在 1951 年指出了它们的重要性。标准定义是「至多一个正文字的析取」;恰好一个正文字的叫 definite clause,对应本讲的事实和「合取 ⇒ 符号」。
直觉
课件的定义有两种形状:
- 单独一个符号 a,表示一个事实。
- (若干符号的合取) ⇒ 一个符号,例如 (a ∧ b) ⇒ c。⇒ 左边那堆叫前提。
用上一页的 implication elimination 把 ⇒ 消掉,(a ∧ b) ⇒ c 变成 ¬a ∨ ¬b ∨ c。不带 ¬ 的文字只有 c 一个。这给出一个快速判据:化成析取后,数不带 ¬ 的文字(正文字),0 个或 1 个就是 Horn 子句。
一步一步看
目标:逐个数四个子句里的正文字,看「至多一个正文字」怎样把 Horn 子句和非 Horn 子句分开。
用四个子句走一遍判定:
-
a:本身就是析取(只有一项),正文字 1 个,是 Horn 子句,也是事实。
-
(a ∧ b) ⇒ c:化成 ¬a ∨ ¬b ∨ c,正文字只有 c,是 Horn 子句。
-
¬a ∨ ¬b:正文字 0 个,按「至多一个」的标准仍是 Horn 子句。
-
a ∨ b:正文字 a、b 两个,不是 Horn 子句。
怎么判断
步骤固定:先消 ⇒(α ⇒ β 换成 ¬α ∨ β),把 ¬ 推到原子上,再数正文字。
意思是:正文字代表「可能的结论」。只有一个正文字,结论就唯一;两个正文字的 a ∨ b 说的是「a 和 b 至少一个为真,但不知道是哪个」,链接法没有办法往 Agenda 里加一个「不知道是哪个」的符号。
前向和后向链接都假设 KB 是 Horn 子句的合取:KB = H1 ∧ H2 ∧ H3 ∧ …。这是一条限制,碰上 a ∨ b 就得换方法,这正是后面引入归结法的理由。
常见误解
以为 a ⇒ (b ∧ c) 不是 Horn 子句
它可以拆成 a ⇒ b 和 a ⇒ c 两条,各自都是 Horn 子句。直接按定义看,它化开是 (¬a ∨ b) ∧ (¬a ∨ c),两个子句各有 1 个正文字。
以为「¬a ∨ ¬b 没有结论,所以不是 Horn」
Horn 的标准是正文字至多一个,0 个也算。只是它不是 definite clause,链接法里用不上它当规则。
试一下
(a ∧ b) ⇒ (c ∨ d) 是 Horn 子句吗?
化开是 ¬a ∨ ¬b ∨ c ∨ d,正文字有 c、d 两个,不是 Horn 子句。结论里出现「或」,链接法就处理不了。
3. 前向链接:有什么推什么,直到目标出现
它解决什么问题
有了一个全是 Horn 子句的 KB,想知道目标 Q 能不能推出来。前向链接给出一个机械的做法,每一步只用最简单的推理:前提全为真,结论就为真。
从哪来(补充)
「已知 P ⇒ Q,且 P 为真,推出 Q」这条推理规则叫 modus ponens,拉丁文意为「肯定的方式」。它最早由古希腊哲学家 Theophrastus 明确描述。前向链接每触发一次规则,用的都是它的多前提版本。
直觉
算法只有两步,反复交替:
- Step 1:触发任何一条前提已经全部在 Agenda 里的规则。
- Step 2:把它的结论加进 Agenda。
停下来的条件有两个:目标 Q 进了 Agenda;或者扫遍所有规则也加不出新符号。光秃秃一个符号的 Horn 子句(事实)不需要触发,一开始就直接进 Agenda。
一步一步看
目标:从事实 A、B 出发在 R1 到 R7 上一条条触发规则,看 Agenda 怎样一路长到目标 Q。
课件的知识库有七条:R1 是 P ⇒ Q,R2 是 L ∧ M ⇒ P,R3 是 B ∧ L ⇒ M,R4 是 A ∧ P ⇒ L,R5 是 A ∧ B ⇒ L,R6 是 A,R7 是 B。目标:Q 为真吗?
-
初始化:R6、R7 是事实,A 和 B 直接进 Agenda。
-
第一次触发:扫一遍,只有 R5 的前提 A、B 全在 Agenda 里。触发 R5,L 进 Agenda。
-
第二次触发:有了 L,R3 的前提 B、L 齐了。触发 R3,M 进 Agenda。
-
第三次触发:L、M 都在,触发 R2,P 进 Agenda。
-
第四次触发:P 在了,触发 R1,目标 Q 进 Agenda,停。R4 的前提 A、P 这时也都在,但它的结论 L 早就有了,触发它是无用功。
怎么算
整条推导链是 R5 → R3 → R2 → R1,Agenda 从 {A, B} 依次扩到 {A, B, L, M, P, Q}。
意思是:每一步扫规则表时只问一个问题,前提是不是全部在 Agenda 里。这个例子每一步只有一条新规则能触发,所以推导路径唯一,考场上可以照着这条链复述。
课件给了前向链接的几条性质:
- 完备:KB 里每一个可证的原子命题都能被推出来。理由是 KB 被假设为 Horn 子句的合取,最坏情况下每条规则都会被触发一次。
- 线性时间:每条规则最多触发一次。
- 数据驱动:从已知事实出发往前推,不看目标是什么。
- 缺点:同时有多条规则可触发时,选哪条是随机的,可能触发一堆和目标无关的规则。
常见误解
以为前提「已知为假」也能触发规则
课件 Step 1 原文写的是前提 known「true or false」,按字面读会误导。规则只有在前提为真时才能触发,演算过程里加进 Agenda 的全是已确定为真的符号。
以为前向链接会先去找和 Q 有关的规则
前向链接不看目标,能触发什么就触发什么。这个例子没暴露问题,是因为目标一出现就停了,而每一步恰好只有一条规则可触发。
试一下
同一个 KB,如果目标改成 M,前向链接在第几次触发后停下?
第二次。初始化 {A, B},第一次触发 R5 得 L,第二次触发 R3 得 M,目标出现即停,R2 和 R1 都不用触发。
把它们串起来
这一页换了一条路线:不再枚举所有解释,改为从已知句子一步步生成新句子。
换路线的理由是行数。真值表要列 2ⁿ 行,原子一多就做不动;推理规则只碰和目标相关的句子。代价是每一步都必须可靠,推出来的东西必须为真。
最简单的可靠推理是 modus ponens:前提为真,结论就为真。为了让这一步永远只产出一个确定的结论,知识库被限制成 Horn 子句,化成析取后正文字至多一个。
前向链接就是把 modus ponens 反复做。事实先进 Agenda,然后不断扫规则表,前提齐了就触发,结论进 Agenda,直到目标出现。R1–R7 这个例子的路径是 R5 → R3 → R2 → R1,R4 从头到尾没用上。
前向链接的毛病是不看目标,能推的都推。下一页把方向倒过来,从目标出发,只找和它有关的规则。
课件里的坑
- [原文有误导] Step 1 写前提 known「true or false」,实际只有前提为真才能触发(p.22)
- [易漏] R4 在最后一步其实可以触发,只是结论 L 早就有了;答题时写「R4 全程没被触发」(p.27)
- [限制] Horn 子句的假设是限制,a ∨ b 这种两个正文字的句子链接法做不了,后面要换归结(p.21)
- [读图] AND-OR 图里的小黑点表示进入它的几条边必须全部成立(p.22)
课后 10 分钟:考点复习
这 10 分钟怎么用:合上页面,先默写 R1–R7 七条规则;再画一张 Agenda 表,从 {A, B} 开始逐步写出每次触发哪条规则、加入哪个符号;最后用正文字判据判断几个子句是不是 Horn 子句。
必背
- 不用真值表的理由是 2ⁿ 指数爆炸;推理规则路线只碰和目标相关的句子
- Horn 子句 = 单个符号,或「合取 ⇒ 符号」;化成析取后正文字 ≤ 1 才是 Horn 子句
- 前向/后向链接都假设 KB 是 Horn 子句的合取,a ∨ b 这种两个正文字的句子装不下
- 前向链接两步:触发前提全部已知为真的规则,把结论加入 Agenda;直到推出 Q 或推不出新结论
- R1–R7 的前向推导:{A,B} → R5 → L → R3 → M → R2 → P → R1 → Q,R4 全程没被触发
- 前向链接是数据驱动、线性时间、完备的;缺点是多条规则可触发时随机选,可能推出无关结论
课件例题
例 1(课件 p.22–27):用前向链接判断 Q 是否为真
见下方完整例题。
例 2(课件 p.21):下面哪些是 Horn 子句:a、a ∨ b、(a ∧ b) ⇒ c、¬a ∨ ¬b ∨ c?
题面:用课件的定义判断,对不是的说明理由。
提示
先化成析取,再数不带 ¬ 的文字。
解答
a:正文字 1 个,是。a ∨ b:正文字 2 个,不是,它说「至少一个为真」,结论不唯一。(a ∧ b) ⇒ c:化成 ¬a ∨ ¬b ∨ c,正文字 1 个,是。¬a ∨ ¬b ∨ c:就是上一条的析取写法,是。
例 3(课件 p.20):为什么不直接用真值表判断 KB ⊨ Q?
题面:用一两句话回答,并说明推理规则路线的优势。
提示
从行数怎么随命题符号个数增长入手。
解答
真值表要枚举 2ⁿ 个解释,关于 KB 中命题符号数量是指数级。推理规则路线只碰和目标相关的句子,不需要遍历整个解释空间。
完整例题
题面(课件 p.22–27):KB 为 R1:P ⇒ Q,R2:L ∧ M ⇒ P,R3:B ∧ L ⇒ M,R4:A ∧ P ⇒ L,R5:A ∧ B ⇒ L,R6:A,R7:B。用前向链接判断 Q 是否为真。
约定:每一轮扫一遍 R1–R5,只触发前提全部在 Agenda 里、且结论还不在 Agenda 里的规则。
解法:
- 初始化。R6、R7 是事实,Agenda = {A, B}。
- 第一次触发。逐条检查:R1 缺 P,R2 缺 L、M,R3 缺 L,R4 缺 P,R5 的 A、B 都在。触发 R5,Agenda = {A, B, L}。
- 第二次触发。R3 的 B、L 齐了。触发 R3,Agenda = {A, B, L, M}。
- 第三次触发。R2 的 L、M 齐了。触发 R2,Agenda = {A, B, L, M, P}。
- 第四次触发。R1 的 P 在了。触发 R1,Agenda = {A, B, L, M, P, Q}。
- 终止。Q 进入 Agenda,Q 为真。
| 轮次 | 触发的规则 | 新加入 | Agenda |
|---|---|---|---|
| 初始化 | R6、R7(事实) | A、B | {A, B} |
| 1 | R5:A ∧ B ⇒ L | L | {A, B, L} |
| 2 | R3:B ∧ L ⇒ M | M | {A, B, L, M} |
| 3 | R2:L ∧ M ⇒ P | P | {A, B, L, M, P} |
| 4 | R1:P ⇒ Q | Q | {A, B, L, M, P, Q} |
要点:每一轮只有一条新规则能触发,路径唯一;R4 到最后才满足前提,但结论 L 早已存在,全程没被触发。
答题格式:先写初始 Agenda,再按轮次写「触发哪条规则、为什么能触发、加入什么、Agenda 变成什么」,最后一句写 Q 为真并点出触发顺序 R5 → R3 → R2 → R1。
变式题(先自己做)
(1) 改编自课件 p.22–27:把 R6(A)删掉,改成直接给定 L。前向链接还能推出 Q 吗?写出 Agenda 演变过程。 (2) 改编自课件 p.21:(¬a ∨ b) ∧ (c ⇒ (d ∨ e)) 里哪个子句不是 Horn 子句? (3) 改编自课件 p.28:在原 KB 里加一条 R8:A ⇒ Z。前向链接证 Q 时,R8 可能带来什么问题?
提示
(1) 初始 Agenda 变成 {B, L},逐条看谁的前提齐。(2) 每个子句分开数正文字。(3) 想想前向链接看不看目标。
判分点与答案(非官方评分标准)
判分点:① (1) 每一轮写出触发的规则和新 Agenda;② (1) 指出 R4、R5 因缺 A 不能触发;③ (2) 给出正文字个数;④ (3) 点出「数据驱动、可能触发无关规则」。
(1) 能。初始化 {B, L}。R3 的 B、L 齐了,触发得 M:{B, L, M}。R2 的 L、M 齐了,触发得 P:{B, L, M, P}。R1 触发得 Q:{B, L, M, P, Q}。R4、R5 都需要 A,始终不能触发。
(2) ¬a ∨ b 正文字 1 个,是 Horn 子句。c ⇒ (d ∨ e) 化成 ¬c ∨ d ∨ e,正文字 2 个,不是。
(3) R8 的前提 A 一开始就在,前向链接可能先触发它,把 Z 加进 Agenda。Z 和目标 Q 毫无关系,这就是数据驱动的缺点:可能触发和目标无关的规则。
闪卡自测
1. 证明方法的两条路线各是什么?
语义路线枚举真值表,代价可能是指数级;语法路线用推理规则,本讲三种方法都属于这条(p.20)。
2. 10 个命题符号的真值表有几行?
2¹⁰ 行,即 1024 行;30 个就超过十亿行(p.20)。
3. 怎么快速判断一个子句是不是 Horn 子句?
化成析取后数正文字,0 个或 1 个是 Horn 子句(p.21)。
4. 前向链接的两步和终止条件是什么?
触发前提全部已知为真的规则,把结论加入 Agenda;推出目标 Q 或推不出新结论时停(p.22)。
5. R1–R7 的前向推导顺序是什么?哪条规则没用上?
R5 → R3 → R2 → R1,Agenda 最终是 {A, B, L, M, P, Q};R4 全程没被触发(p.23–27)。
6. 前向链接有哪些性质?缺点是什么?
完备、线性时间、数据驱动;多条规则可触发时随机选,可能触发和目标无关的规则(p.28)。
下一讲
同一个 KB、同一个目标,下一页从 Q 倒着往回找,讲目标驱动的后向链接,以及它为什么必须记住走过的路。见 L03b-4。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。