从事实推导后果
规则系统可以存储事实和连接事实的规则。前向链推理从事实开始;当某条规则的所有前提已知,就加入其结论。使用前必须先说明语言。
定义 20.1.1
(有限 Horn 规则库)
原子是有限个命题符号,每条规则形如
前提和结论都是原子。我们把前提视为集合,同一原子重复出现不构成第二个要求。没有前提的规则()就是事实。本节没有变量、函数符号、否定结论或表达矛盾的规则。
定义 20.1.2
(赋值、模型与蕴涵)
一个赋值指定哪些原子为真。若至少一个前提为假,或者结论为真,该赋值就满足规则;因此规则不触发也可以被满足。若赋值满足所有事实和规则,它就是知识库的模型。知识库蕴涵原子 ,意思是每个模型都令 为真;这关乎所有模型,而非某次执行处理规则的顺序。
定义 20.1.3
(前向链闭包)
若每条前提全在集合 内的规则,其结论也在 内,就称 是封闭的。闭包 这样得到:从空集合开始,反复加入某条规则的结论,条件是该规则的前提全在目前集合内而结论尚未在内,直至再没有这样的规则。事实没有前提,所以最先加入。过程停下时的集合 称为固定点。
追踪一个小系统
例题 20.1.4
(雨天系统的前向链推理)
令 分别表示下雨、地面潮湿、地面易滑倒及洒水器开启。这些名称只供理解:下面的蕴涵是明确给定的形式规则,不是声称现实中每次下雨都会令地面潮湿。
| 类型 | 规则或事实 |
|---|---|
| 事实 | |
| 规则 | |
| 规则 | |
| 规则 | |
| 规则 |
从 开始。第一条规则加入 ,得到 。此时 的两个前提都成立,故加入 ,得 。 虽可使用,但 已在集合内。没有规则加入 ;只知道 不能令 反向触发。于是到达固定点 。
反例模式
结论不能证明前提
由 和 推出 是错误的: 也可由 得到。在这个形式系统中,令恰好 为真的赋值满足所有规则,却令 为假。它是“知识库蕴涵 ”的具体反模型。
但这不表示知识库蕴涵 :令四个原子全部为真也是模型。所以 和 都不被蕴涵;原子没有出现在推导集合中,不等于一般地断言它为假。
为什么固定点能回答正原子查询?
定理 20.1.5
(闭包是最小模型)
设 是有限原子集合上的有限 Horn 规则库。无论按什么次序使用可用规则,前向链推理都会终止,而其闭包 满足:
- 中每个原子在 的每个模型中都为真;
- 恰好令 内原子为真的赋值本身是 的模型。
因此 按包含关系是 的最小模型,任何终止的处理次序都得到同一个 ,而且对原子 ,知识库蕴涵 当且仅当 。
证明
(先证可靠性,再证闭包是模型)
原子集合有限,每一步有效加入都增加一个尚未出现的原子,所以过程终止。处理次序可以不同,但必须继续至没有规则能加入新原子。
首先, 中每个原子在每个模型都为真。初始事实如此。若某规则的所有前提都有此性质,每个模型都满足这些前提,也因此必须满足结论。归纳可知每次加入都可靠。
其次,考虑恰好令 内原子为真的赋值。所有事实都在 。若某规则的所有前提都在 ,其结论也必在 ;否则仍可加入新原子。若有前提不在 ,则该蕴涵在此赋值下为真。因此 本身是模型。
可靠性说明 包含于每个模型,而上一步说明它本身是模型,故 按集合包含关系是最小模型。正原子 若在 ,便在每个模型为真;若不在 ,模型 令它为假,因而证明它不被蕴涵。特别地,任何运行至固定点的规则处理顺序都得到同一闭包。
证明透视
有限性、Horn 形式与两个包含关系用在哪里
有限性只用一次,就是保证终止:每个有效步骤都在有限的原子集合内扩大 。没有有限性,过程可以不停。
Horn 形式,即结论只是一个正原子,是第二部分能成立的原因。每当所有前提都在 内,结论便可加入,所以 对所有规则封闭。若有一条无前提、结论为析取 的规则,则 与 都是模型,但它们的交集 不是模型,因此没有最小模型,也没有单一集合可追。
关键一步是两个包含关系的夹逼。可靠性给出对每个模型 都有 ;规则下的封闭性给出 本身就是其中一个模型。包含于每个模型而且自身是模型的集合,必定是最小的。论证的收尾是把“不在 ”变成证据:若 ,赋值 就是令 为假的模型,即具体反模型。这里并没有断言 在每个模型都为假,所以得不到 。
此反模型回答的是“这个正原子是否在所有模型中必真”,并没有采用“没有记载的原子在现实中都为假”的封闭世界假设。上述结果也不声称能完整处理任意否定公式或不受限制的谓词逻辑。
概念视角结构
闭包就是全部模型的交集
Horn 规则库的模型集合对交集封闭:若 与 都满足某条规则,而其全部前提都落在 内,则结论同时属于两者,因而属于交集。所以全部模型的交集本身也是模型,并且是最小的一个,即 。对雨的系统,模型只有 与 ,两者的交集是 ,正是前向链推理得到的闭包。被蕴涵的原子,就是落在这个交集内的原子。
下面的互动图对这些规则重放前向链推理,并独立检查每个赋值,因此缺少的结论要由真正的反模型确认,而不是擅自当作假。
缺少结论时,要找反模型,不能擅自当成否定
重放有限正 Horn 规则,检查合取计数并建立推导见证,再独立检查每个赋值,把最终闭包与逻辑蕴含连起来。
断言为真的初始事实
移除事实只是撤回事实断言,不是断言其否定。r,w,t,s 是示例标签;这些是明确给定的形式蕴涵,不是现实天气的普遍定律。
已在完成检查点。
工作队列检查点 3/3: 此检查点已处理的原子: t.
当前已知: {r,w,t}
当前已处理: {r,w,t}
队列存储顺序
空
每个检查点一次完整处理一个移除原子及它索引到的全部规则前提出现。新头部成为已知,且只入队一次。FIFO 从显示左端取出;LIFO 从右端取出。表格是完成检查点,不是只更新一半的计数。
启用规则须满足全部前提。蕴涵不可倒推。第五条 w∧t→s 是教材的可选扩展;切换它会改变知识库。
| 规则 | 启用 | 前提 → 头部 | 尚未已知的前提 | 尚未处理的前提数 | 头部当前已知 | 规则在当前已知集赋值下成立 | 此检查点的计数变更 | 新头部入队 |
|---|---|---|---|---|---|---|---|---|
| R1 | r → w | ∅ | 0 | 是 | 是 | 无 | 不适用 | |
| R2 | r∧w → t | ∅ | 0 | 是 | 是 | 无 | 不适用 | |
| R3 | s → w | {s} | 1 | 是 | 是 | 无 | 不适用 | |
| R4 | t → r | ∅ | 0 | 是 | 是 | 1 → 0 | 否 | |
| R5 | w∧t → s | ∅ | 不适用 | 否 | 不适用 | 无 | 不适用 |
计数记录不同且尚未处理的前提,不是尚未知的前提。已知而仍在队中的原子,仍可计入。到零时全部前提已处理,头部已知或只新增一次。有假前提的规则在该赋值下已成立,即使不能触发。
当前可取得的推导见证: s
每条规则见证依赖全部列出前提。保留的首次推导是其中一个证明,不声称唯一。其前提较早已知,所以即使规则图有循环,记录证明仍无环。队列顺序可改证明,但不改最终闭包。
完成闭包没有此查询,且是令查询为假的模型,因此证明正查询不被蕴含。全真模型则令查询为真,所以其否定也不被蕴含。
独立检查完成实验的语义
此面板检查完整当前知识库的全部模型,不受重放游标影响。完成闭包 C 是最小模型,每个模型都包含它。中途已知集赋值可能违反一条结论尚待推导的规则。
最终闭包 C: {r,w,t}; 知识库模型数: 2; 令查询为真的模型: 1; 令查询为假的模型: 1.
这个确定正规则片段中,全真赋值始终是模型,所以反驳蕴含 ¬q。q 若不在 C,C 也反驳蕴含 q:q 与 ¬q 都不被蕴含。这没有施加封闭世界假设。
独立赋值检查器: 7
这些真值按钮检查赋值,不是初始事实,绝不改变知识库或重放。反模型须满足全部已断言事实与启用规则;只把查询设成假并不足够。
满足整个知识库: 是; 违反的初始事实: ∅; 违反的启用规则: 无; s=假. 正查询蕴含的反模型: 是; 否定查询蕴含的反模型: 否.
全部有限赋值
| 赋值编号 | r | w | t | s | 满足整个知识库 | 违反的初始事实 | 违反的启用规则 |
|---|---|---|---|---|---|---|---|
| 假 | 假 | 假 | 假 | 否 | {r} | 无 | |
| 真 | 假 | 假 | 假 | 否 | ∅ | R1 | |
| 假 | 真 | 假 | 假 | 否 | {r} | 无 | |
| 真 | 真 | 假 | 假 | 否 | ∅ | R2 | |
| 假 | 假 | 真 | 假 | 否 | {r} | R4 | |
| 真 | 假 | 真 | 假 | 否 | ∅ | R1 | |
| 假 | 真 | 真 | 假 | 否 | {r} | R4 | |
| 真 | 真 | 真 | 假 | 是 | ∅ | 无 | |
| 假 | 假 | 假 | 真 | 否 | {r} | R3 | |
| 真 | 假 | 假 | 真 | 否 | ∅ | R1, R3 | |
| 假 | 真 | 假 | 真 | 否 | {r} | 无 | |
| 真 | 真 | 假 | 真 | 否 | ∅ | R2 | |
| 假 | 假 | 真 | 真 | 否 | {r} | R3, R4 | |
| 真 | 假 | 真 | 真 | 否 | ∅ | R1, R3 | |
| 假 | 真 | 真 | 真 | 否 | {r} | R4 | |
| 真 | 真 | 真 | 真 | 是 | ∅ | 无 |
- 查询在此检查点已知
- 否
- 当前已知集是知识库模型
- 是
- 知识库蕴含正查询
- 否
- 知识库蕴含查询的否定
- 否
- 知识库模型数
- 2
- 已处理原子数
- 3
- 已处理的前提出现数
- 4
- 不同前提出现总数 B
- 5
FIFO:移除最早入队者, 工作队列检查点 3/3; 当前已知: {r,w,t}; 当前已处理: {r,w,t}; 队列存储顺序: []. q=s; 查询在此检查点已知: 否; 当前已知集是知识库模型: 是; 最终闭包 C: {r,w,t}; 知识库蕴含正查询: 否; 知识库蕴含查询的否定: 否. 赋值编号: 7; 满足整个知识库: 是; q=假.
为何闭包等于最小模型
正规则 p₁∧…∧pₖ→q 需要全部前提,不是其中一个。重复前提不会增加条件;没有前提就是事实。前向链推理具可靠性:初始事实在每个模型成立,若规则全部前提在每个模型成立,头部也必须成立。归纳涵盖每个新推导原子。
完成时恰把 C 解释为真。每个事实在 C;若全部前提在 C,规则头部也在 C,否则仍可新增。若某前提缺席,蕴涵不必触发便已成立。因此 C 本身是模型。可靠性又使 C 包含于每个模型,所以它是包含关系下的最小模型。
q∈C 时每个模型令 q 真;q∉C 时模型 C 令 q 假,反驳蕴含。全真仍是本片段的另一模型,因此缺席不蕴含 ¬q。教材中 C={r,w,t}:不能从 s→w 与地湿倒推洒水器 s。C 与 {r,w,t,s} 都满足规则。
没有事实时,循环不会自启。还原事实 r 推得 w,再得 t;t→r 遇到已知头部,不会把 r 再入队。加入 w∧t→s 后可得 s。r、s 同为初始事实时,FIFO 先由 r→w 推 w,LIFO 可先由 s→w 推 w。证明改变,两种完整终止顺序仍到达同一最小模型。
按不同前提建立规则索引,每条规则初始化一个计数,每个已知原子最多入队一次。处理原子只访问其前提出现一次。抽象邻接表模型的初始化与工作为 O(|A|+|R|+B) 时空。快照复制、证明显示与枚举 2^|A| 赋值是额外教学成本,不包含在前向链推理界限内。此有限教学实现另有规范化、排序、扫描原子/规则组合建索引与数组队列操作,并不声称实际程序达到该抽象界。
当前已知集总能证明缺少查询不被蕴含吗?
只有它满足整个知识库才行。教材初始检查点 {r} 违反 r→w,不能当作稍后会推出的 t 的反模型。完成闭包 {r,w,t} 才是真模型,并反驳蕴含 s。
四个固定示例原子与五条可选正规则。内核支持最多六原子、八条不同编号规则,包括无前提规则与重复前提去重。不含负事实/头部、完整性约束、变量或函数符号。事实/规则/顺序编辑会重建记录、选最后检查点,并把赋值检查器设为新最小模型。查询编辑及重放保留独立赋值。模型枚举只对此有限命题实验完整。
含有推不出前提的规则库
例题 20.1.6
(没有规则能推出的前提)
取事实 及规则 、、。前向链推理先加入 ,再加入 。原子 既不是事实,也不是任何规则的结论,所以永不加入, 和 也永远推不出。闭包是 。
令恰好 为真的赋值满足该事实和三条规则,因为后两条规则的前提 为假。所以 都不被蕴涵。五个原子全为真的赋值也是模型,所以 同样都不被蕴涵。事实 是没有前提的规则,所以它的前提计数在任何步骤之前已是零。
用工作队列实现
为有效处理,对每个不同前提建立索引,列出包含它的规则。每条规则维持一个计数器,记录尚未处理的不同前提数。每个已知事实只入队一次。取出一个原子时,访问以它为前提的规则并递减计数器;计数器到零时,若结论尚未知,就加入并入队一次。零前提规则的结论在初始化时加入。
例题 20.1.7
(雨天系统的计数器)
计数器起始值: 为 , 为 , 为 , 为 ;队列中有 。
取出 :规则 降至 ,所以 加入并入队;规则 由二降至一。取出 :规则 降至 ,所以 加入并入队。取出 :规则 降至 ,但 已知,因此不入队,循环终止。此时队列已空。 的计数器从未改变,因为 从未被处理,所以 只经由 推出。
若使用适当的邻接索引且每个原子最多入队一次,初始化及处理的时间与空间均为 ;其中 是有限原子集合, 是规则集合, 是各规则不同前提出现次数的总和。此界包括初始化计数器和结论,并不适用于不受限制的一阶推理引擎。
常见错误
常见错误
(只按规则顺序扫描一遍就停)
设规则按 在前、 在后排列,事实为 。按排列顺序扫描一遍,第一条规则因 尚未知而不适用;第二条规则加入 ,然后这一遍结束,没有得到 。但 其实被蕴涵。应该继续扫描,直至整一遍都没有加入新原子;或改用工作队列,它恰在某条规则的前提变成已知时才重新检视该规则。
常见错误
(按前提出现次数而非不同前提计数)
前提构成集合,所以 只有一个不同前提。若因为 写了两次而把计数器初始化为二,但规则只在 之下索引一次,那么处理 只会把它减至一,该规则永不触发, 便丢失,虽然事实 蕴涵 。每个计数器应初始化为不同前提的个数。
练习与解答
快速检查
(移除事实 且没有其他事实时,雨天系统的闭包是什么?)
想想哪一条规则可以最先触发。
解答 · 答案
空集合。循环或前提未满足的规则都不能自行启动。
快速检查
(保留原事实,再加入规则 ;现在蕴涵 吗?)
先追踪 和 的推导。
解答 · 答案
是。先得 ,再得 ,最后由新规则得 ;可靠性保证它在每个模型为真。
快速检查
(单一规则 能蕴涵 吗?)
找一个满足该规则而令 为假的赋值。
解答 · 答案
不能。令 均为假,蕴涵仍成立,此赋值是 的反模型。
快速检查
(处理 时,为什么工作队列不可再次加入 ?)
留意此时 已在闭包内。
解答 · 答案
已知;只让新原子入队可以避免循环造成无限重复工作,同时保留所有结论。
前向链把证明和程序连起来:推导出的原子有来自事实的证明,而完整闭包为每个未出现的正原子提供反模型。