← COMP5511 全部讲次
L03b-3 · 第 3 周

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. 1 个原子:2 行。
  2. 2 个原子:4 行,岛民题就是这个规模。
  3. 4 个原子:16 行,后面 Tom/John 那道题就是这个规模。
  4. 10 个原子:1024 行。
  5. 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,对应本讲的事实和「合取 ⇒ 符号」。

出处:Wikipedia: Horn clause

直觉

课件的定义有两种形状:

  • 单独一个符号 a,表示一个事实。
  • (若干符号的合取) ⇒ 一个符号,例如 (a ∧ b) ⇒ c。⇒ 左边那堆叫前提。

用上一页的 implication elimination 把 ⇒ 消掉,(a ∧ b) ⇒ c 变成 ¬a ∨ ¬b ∨ c。不带 ¬ 的文字只有 c 一个。这给出一个快速判据:化成析取后,数不带 ¬ 的文字(正文字),0 个或 1 个就是 Horn 子句。

一步一步看

目标:逐个数四个子句里的正文字,看「至多一个正文字」怎样把 Horn 子句和非 Horn 子句分开。

用四个子句走一遍判定:

  1. a:本身就是析取(只有一项),正文字 1 个,是 Horn 子句,也是事实。

  2. (a ∧ b) ⇒ c:化成 ¬a ∨ ¬b ∨ c,正文字只有 c,是 Horn 子句。

  3. ¬a ∨ ¬b:正文字 0 个,按「至多一个」的标准仍是 Horn 子句。

  4. a ∨ b:正文字 a、b 两个,不是 Horn 子句。

    Horn 子句判定表:四个子句化成「或」的形式后数正文字,a 有 1 个、(a∧b)⇒c 化成 ¬a∨¬b∨c 有 1 个、¬a∨¬b 有 0 个,都是 Horn 子句;a∨b 有 2 个正文字,用青绿标出为不是 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 明确描述。前向链接每触发一次规则,用的都是它的多前提版本。

出处:Wikipedia: Modus ponens

直觉

算法只有两步,反复交替:

  • 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 为真吗?

  1. 初始化:R6、R7 是事实,A 和 B 直接进 Agenda。

    前向链接初始化帧:左侧 R1 到 R7 规则表,R6、R7 标为事实,右侧 Agenda 里出现 A 和 B,新加入的 A、B 用青绿标出

  2. 第一次触发:扫一遍,只有 R5 的前提 A、B 全在 Agenda 里。触发 R5,L 进 Agenda。

    前向链接第 1 次触发帧:R5 的前提 A、B 都在,触发后 L 进入 Agenda,青绿标出新加入的 L,其余规则旁注明还缺哪个前提

  3. 第二次触发:有了 L,R3 的前提 B、L 齐了。触发 R3,M 进 Agenda。

    前向链接第 2 次触发帧:R3 的前提 B、L 齐了,触发后 M 进入 Agenda 并用青绿标出,R5 标为已触发过

  4. 第三次触发:L、M 都在,触发 R2,P 进 Agenda。

    前向链接第 3 次触发帧:R2 的前提 L、M 都在,触发后 P 进入 Agenda 并用青绿标出,R3、R5 标为已触发过

  5. 第四次触发:P 在了,触发 R1,目标 Q 进 Agenda,停。R4 的前提 A、P 这时也都在,但它的结论 L 早就有了,触发它是无用功。

    前向链接第 4 次触发帧:R1 的前提 P 在了,触发后目标 Q 进入 Agenda 并用青绿标出;R4 旁注明 A、P 都在但结论 L 早就有了;Agenda 最终是 A、B、L、M、P、Q

怎么算

整条推导链是 R5 → R3 → R2 → R1,Agenda 从 {A, B} 依次扩到 {A, B, L, M, P, Q}。

意思是:每一步扫规则表时只问一个问题,前提是不是全部在 Agenda 里。这个例子每一步只有一条新规则能触发,所以推导路径唯一,考场上可以照着这条链复述。

前向链接推导链总览:已有事实 A、B 经 R5 得 L、经 R3 得 M、经 R2 得 P、经 R1 得 Q,下方是 Agenda 的五次扩展,并注明 R4 全程没被触发

课件给了前向链接的几条性质:

  • 完备: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 子句。

必背

  1. 不用真值表的理由是 2ⁿ 指数爆炸;推理规则路线只碰和目标相关的句子
  2. Horn 子句 = 单个符号,或「合取 ⇒ 符号」;化成析取后正文字 ≤ 1 才是 Horn 子句
  3. 前向/后向链接都假设 KB 是 Horn 子句的合取,a ∨ b 这种两个正文字的句子装不下
  4. 前向链接两步:触发前提全部已知为真的规则,把结论加入 Agenda;直到推出 Q 或推不出新结论
  5. R1–R7 的前向推导:{A,B} → R5 → L → R3 → M → R2 → P → R1 → Q,R4 全程没被触发
  6. 前向链接是数据驱动、线性时间、完备的;缺点是多条规则可触发时随机选,可能推出无关结论

课件例题

例 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 里的规则。

解法:

  1. 初始化。R6、R7 是事实,Agenda = {A, B}。
  2. 第一次触发。逐条检查:R1 缺 P,R2 缺 L、M,R3 缺 L,R4 缺 P,R5 的 A、B 都在。触发 R5,Agenda = {A, B, L}。
  3. 第二次触发。R3 的 B、L 齐了。触发 R3,Agenda = {A, B, L, M}。
  4. 第三次触发。R2 的 L、M 齐了。触发 R2,Agenda = {A, B, L, M, P}。
  5. 第四次触发。R1 的 P 在了。触发 R1,Agenda = {A, B, L, M, P, Q}。
  6. 终止。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。

下一讲 →
L03b-4 L03b-4 后向链接:从目标倒着找,走过的路要记住

个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。