第三章 基于谓词逻辑的机器推理 ----3.2 归结
演绎推理
3.2.1子句集
定义 1 原子谓词公式及其否定称为文字；文字的析取式
称为子句； r个文字组成的子句称为 r-文字子句。 1-文
字子句也称为单元子句。不含任何文字的子句称为空
子句，记为 或 NIL。由子句构成的集合称为子句集。
任何一个谓词公式都可以化为子句集，步骤如下：
（ 1）、利用等价式 A ? B ??A ?B
和 A ? B ? (A ? B) ?(B ? A)消去联结词,?,
和, ?,。
（ 2）、缩小否定联结词的作用范围，使其仅作用于
原子公式。可利用下列等价式：
?? A ?A；
?(A?B) ?? A ?? B；
?(A ? B) ??A ??B；
??xA(x) ??x? A(x)；
??xA(x) ?? x? A(x)
（ 3）、重新命名变元名，使不同量词约束的
变元有不同的名字。
（ 4）、消去存在量词。若存在量词不在全称量
词的辖域内，则用一个常量符号替换该存在量
词辖域中的相应约束变元。这样的常量称为
Skolem常量；若该存在量词在一个或多个全称
量词的辖域内，则用这些全称量词指导变元的
一个函数替换该存在量词约束的变元。这样的
函数称为 Skolem函数。
例如 ?x1 ?x2 ? ? ???xn?yP(x1,x2,…,x n,y)中 y可用
Skolem函数 f(x1,x2,…,x n)替换为 ?x1 ?x2 ? ? ??
?xnP(x1,x2,…,x n,f(x1,x2,…,x n))。
（ 5）、把全称量词全部移到公式的左边。
（ 6）、把全称量词后面的公式利用等价关系
A?(B ?C) ? (A?B) ?(A ?C)化为子句的合取
式，得到的公式称为 Skolem标准形。 Skolem
标准形的一般形式为 ?x1 ?x2 ? ? ???xnM，其中
M是子句的合取式。
（ 7）、消去全称量词。
（ 8）、对变元更名，使子句间无同名变元。
（ 9）、消去合取词 ?,以子句为元素组成的
集合称为谓词公式的子句集。
例、把谓词公式 ?x{?yP(x,y) ?
??y[Q(x,y)?R(x,y)]}化为子句集。
定理 1 谓词公式 G 不可满足当且仅当其子句
集 S不可满足。子句集 S是不可满足的是指其
全部子句的合取式是不可满足的。
3.2.2 命题逻辑中的归结原理
要证明在前提 P下结论 Q成立，即是证明 P ? Q永真，
这只须证明 P ??Q不可满足。根据定理 1，只须证
明 P ??Q的子句集不可满足。由于子句之间是合取
关系，只要有一个子句不可满足，则整个子句集不
可满足。由于空子句是不可满足的，所以如果子句
集中包含空子句，则该子句集是不可满足的。若子
句集中不包含空子句，则可通过 Robinson提出的归
结原理对子句集进行归结，归结过程保证子句集的
不可满足性不变。一旦归结出空子句，则证明结束。
因此，归结原理把定理的证明化为子句集中归结出
空子句的过程。
定义４、设 L是一个文字，则称 L与 ?L为互补
文字。
定义５、设 C1,C2是命题逻辑中的两个子句，
C1 中有文字 L1, C２ 中有文字 L２,且 L1与 L２
互补,从 C1,C２ 中分别删除 L1, L２,再将剩
余部分析取起来，构成的新子句 C1２ 称为 C1与
C2的归结式（消解式）,C1,C2称为 C1２ 的亲
本子句。
定理２、归结式 C1２ 是其亲本子句 C1与 C2
的逻辑结论。
推论、设 C1,C2是子句集 S的两个子句，
C1２ 是它们的归结式，则
（１）若用 C1２ 代替 C1和 C2后得到新子
句集 S1，则由 S1的不可满足性可推出原
子句集 S的不可满足性。即
S1不可满足 ?S不可满足
（２）若把 C1２ 加入到 S中，得到新子句集
S２,则 S２ 与 S在不可满足意义上是等价
的。即
S2不可满足 ?S不可满足
例、用归结原理证明 R是 P,（ P ? Q）
? R,（ S?U） ? R,U的逻辑结
果。
3.2.3 替换与合一
定义６、一个替换 (Substitution)是形如 {t1 / x1,
t2 / x2,…,t n / xn }的有限集合，其中 t1,t2,…,t n
是项,x1,x2,…,x n是互不相同的个体变元。
ti / xi表示用 ti代换 xi 。 ti与 xi不同,xi也不能出
现在 tj中 (j=1,2,…,n) 。
例、｛ a/x,g(y)/y,f(g(b))/z}是一个替换，
{g(y)/x,f(x)/y}不是一个替换。
定义７、设 ?＝ {t1 / x1,t2 / x2,…,t n / xn }是一个替
换,E是一个表达式（项、原子公式、文字、
子句），把 E中出现的所有个体变元 xi都用 ti 替
换，得到的结果记为 E?,称为 E在 ?下的替换
实例。
例、若 E=P(x,y,g(z)),?＝ {a / x,f(b) /y,c /z }，则
E?= P(a,f(b),g(c))。
定义８、设 ?＝ {t1 / x1,t2 / x2,…,tn / xn },?＝
{u1 / y1,u2 / y2,…,um / ym }是两个替换，则将集合
{t1 ?/ x1,t2 ?/ x2,…,tn ?/ xn,u1 / y1,u2 / y2,…,um /
ym }中符合下列条件的两种情形删除：
１）,ti ?/ xi,当 ti ?＝ xi 。
２）,ui / yi,当 yi ?{ x1,x2,…,xn } 。
得到的集合仍是一个替换，称为 ?与 ?的复合，记为
?o?。
例、见教材 p67例 3.13。
定义９、设 S= { F1,F2,…,Fn }是一个原子谓词公式集，
若存在一个替换 ?，使得 F1 ?＝ F2 ?＝ … ＝ Fn ?，则
称 ?为 S的一个合一（ Unifier），并称 S为可合一的。
一个公式集的合一一般不唯一。
定义１０、设 ?是公式集 S的一个合一，如果对 S的任
何一个合一 ?，都存在一个替换 ?，使得 ?＝ ? o?，
则称 ?为 S的一个最一般合一（ Most General
Unifier），简称 MGU。
定义１１、设 S是一个非空的具有相同谓词名
的原子公式集，从 S中各公式的左边第一个
项开始，同时向右比较，每一组不都相同的
项的差异部分组成的集合称为 S的差异集。
例、公式集 S={P(a,x,f(g(y))),P(z,h(z,u),f(u))}的
差异集为 {a,z},{x,h(z,u)},{g(y),u}
3.2.3 替换与合一
设 S为一非空有限具有相同谓词名的原子谓词
公式集，求 S的 MGU的算法：
（ 1）、令 k=0,Sk=S,?k= ?（ ? 表示空替换）。
（ 2）、若 Sk只含有一个谓词公式，则算法停止,?k
就是要求的最一般合一。
（ 3）、求 Sk的差异集 Dk 。
（ 4）、若 Dk中存在元素 xk 和 tk,其中 xk是变元,tk
是项且 xk不在 tk中出现，则置 Sk+1 = Sk{tk /xk}, ?k+1
= ?ko{tk /xk}, k=k+1，然后转步（ 2）。
（ 5）、算法停止,S的最一般合一不存在。
定理 3（合一定理）、如果 S是一个非空有限可合一的
公式集，则合一算法总是在步（ 2）停止，且最后
的 ?k即是 S的最一般合一。
3.2.4 谓词逻辑中的归结原理
定义 12,设 C1,C2是两个没有相同变元的子句,L1，
L2分别是 C1,C2中的两个文字，如果 L1与 ?L2有最一般
合一 ?，则子句 C12=(C1?-{L1?})? (C2?-{L2?})，称作
C1和 C2的二元归结式（二元消解式）。 C1和 C2称为 C12
的亲本子句,L1,L2称为消解文字。
若在参加归结的子句内部含有可合一文字，则在进行
归结之前，应对这些文字进行合一。
定义 13、如果子句 C中，两个或两个以上的文字有一个
最一般合一 ?，则称 C?为 C的因子。
定义 14、子句 C1,C2的归结式，是下列二元归
结式之一：
1）,C1和 C2的二元归结式；
2）,C1和 C2的因子的二元归结式；
3）,C1的因子和 C2的二元归结式；
4）,C1的因子和 C2的因子的二元归结式。
定理 4、谓词逻辑中的归结式是它的亲本子句的逻辑结
果。
类似于命题逻辑中的两个推论仍成立。
归结反演：应用归结原理证明定理的过程称为归结反
演。
若 F为已知前提的公式集,Q为结论，用归结反演证明
Q为真的步骤是：
（ 1）、否定 Q，得到 ?Q；
（ 2）、把 ?Q并入到公式集 F中，得到 {F,?Q}；
（ 3）、把公式集 {F,?Q}化为子句集 S；
（ 4）、应用归结原理对子句集 S中的子句进行归结，并把每
次归结得到的归结式都并入 S中。如此反复进行，直到出现空
子句，就证明了 Q为真。
例、自然数都是大于零的数；所有整数不是偶数就是奇
数；偶数除以 2是整数。求证：所有自然数不是奇数就
是其一半为整数的数。
证明：前提,F1, ?x(N(x) ?GZ(x) ?I(x))
F2, ?x(I(x) ?E(x) ? O(x))
F3, ?x(E(x) ?I(h(x)))
结论,G,?x(N(x) ?O(x) ? I(h(x)))
F1,F2,F3 及 ?G 化为子句集：
（ 1） ?N(x)?GZ(x)
（ 2） ?N(y)?I(y)
（ 3） ?I(z)?E(z) ? O(z)
（ 4） ?E(u)?I(h(u))
（ 5） N( c)
（ 6） ?O(c)
（ 7） ?I(h( c))
归结：
（ 8） I( c) ( (2),(5),c/y )
（ 9） ?I(c) ? E( c) ( (3),(6),c/z )
（ 10） E( c) ( (8),(9) )
（ 11） I(h( c)) ( (4),(10),c/u )
（ 12） ? ( (7),(11) )
定理 5（归结原理的完备性）、如果子句集 S是不
可满足的，则必存在一个由 S推出空子句的归
结序列。
其它例见教材 p78,例 15,16。
课堂练习,p94，题 6。
归结演绎树：
?N(y)?I(y) N( c) ?I(z)?E(z) ? O(z) ?O(c)
I( c) ?I(c) ? E( c)
E(c ) ?E(u)?I(h(u))
I(h (c )) ?I(h( c))
3.3 应用归结原理求取问题答案
应用归结原理求取问题答案的步骤：
（ 1）、把已知前提用谓词公式表示出来，并化为
子句集 S。
（ 2）、把待求解问题也用谓词公式表示出来，然
后把它的否定与谓词 ANS构成析取式。 ANS的变元
应与问题的变元完全一致。
（ 3）、把此析取式化为子句集，并把该子句集并
入 S中得到子句集 S'。
（ 4）、对 S'应用归结原理进行归结。
（ 5）、若得到归结式 ANS，则答案就在 ANS中。
例、设 A,B,C三人中有人从不说真话，也有人
从不说假话，某人向这三人分别提出同一个问
题：谁是说谎者？ A答：,B和 C都是说谎者”；
B答：,A和 C都是说谎者”； C答：,A和 B中
至少有一个是说谎者”。求谁是老实人，谁是
说谎者？
解、设 T(x)表示 x说真话。如果 A说的是真话，则
有：
T(A) ?? T(B) ??T(C )
如果 A说的是假话，则有,?T(A) ?T(B)? T(C )。 同理，
对 B和 C有：
T(B) ?? T(A) ??T(C )
?T(B) ?T(A)? T(C )
T(C) ?? T(A)? ? T(B )
? T(C) ? T(A) ?T(B )
化为子句集 S：
（ 1）,? T(A)? ? T(B )
（ 2）,? T(A)? ? T(C )
（ 3）,T(A)?T(B)?T(C )
（４）,? T(B)?? T(C )
（５）,? T(A)? ? T(B ) ?? T(C )
（６）,T(C)?T(A)
（７）,T(C)?T(B)
先求谁是老实人,把 ?T(x)? ANS(x)并入 S
（８）,?T(x)? ANS(x)
（９）,T(A)? ANS( C) ( (8),(6),C/x )
（１０）,T(B)?ANS(C) ( (7),(8),C/x )
（１１）,?T(B)? ANS(C) ( (9),(1) )
（１２）,ANS(C ) ( (10),(11) )
因此 C是老实人。无论如何归结，推不出 ANS(A),ANS(B)。下证 A是
说谎者，即 ?T(A)，其否定为
（８）’ ?? T(A)即 T(A)
（９）’ ?T(B) ( (8)’,(1) )
（１０）’ T(C ) （（９）’，（７） ）
（１１）’ ?T(C ) （ （８）’,（２） ）
（１２）’ NIL （ （１０）’,（１１）’ ）
3.４ 归结策略
3.4.1 问题的提出
归结反演的一般过程。
步１ 将子句集 S置入 CLAUSES表；
步２ 若空子句 NIL在 CLAUSES中，则归结成功，
结束。
步３ 若 CLAUSES表中存在可归结的子句对，则
归结之，并将归结式并入 CLAUSES表，转步２；
步３ 归结失败，退出。
穷举算法（广度优先策略）
第一轮：将原子句集 S中的子句两两归结，产生的归
结式集合记为 S1，再将 S1并入 CLAUSES表；
第二轮：将新的 CLAUSES表即 S?S1中的子句与 S1中
的子句两两归结，产生的归结式集合记为 S2，再将
S2并入 CLAUSES；
第三轮：将新的 CLAUSES表即 S?S1 ?S2中的子句与 S2
中的子句两两归结,… 。
如此下去，直到出现空子句。
例 1 设有如下的子句集，用穷举算法归结如下：
S,（ 1） P?Q
（ 2） ? P?Q
（ 3） P?? Q
（ 4） ? P?? Q
S1,（ 5） Q [(1),(2)]
（ 6） P [(1),(3)]
（ 7） Q?? Q [(1),(4)]
（ 8） P?? P [(1),(4)]
（ 9） Q?? Q [(2),(3)]
（ 10） P?? P [(2),(3)]
（ 11） ? P [(2),(4)]
（ 12） ? Q [(3),(4)]
S2：（ 13） P? Q [(1),(7)]
（ 14） P? Q [(1),(8)]
（ 15） P? Q [(1),(9)]
（ 16） P? Q [(1),(10)]
（ 17） Q [(1),(11)]
（ 18） P [(1),(12)]
（ 19） Q [(2),(6)]
（ 20） ? P?Q [(2),(7)]
（ 21） ? P?Q [(2),(8)]
（ 22） ? P?Q [(2),(9)]
（ 23） ? P?Q [(2),(10)]
（ 24） ? P [(2),(12)]
（ 25） P [(3),(5)]
（ 26） P?? Q [(3),(7)]
（ 27） P?? Q [(3),(8)]
（ 28） P?? Q [(3),(9)]
（ 29） P?? Q [(3),(10)]
（ 30） ? Q [(3),(11)]
（ 31） ? P [(4),(5)]
（ 32） ? Q [(4),(6)]
（ 33） ? P?? Q [(4),(7)]
（ 34） ? P?? Q [(4),(8)]
（ 35） ? P?? Q [(4),(9)]
（ 36） ? P?? Q [(4),(10)]
（ 37） Q [(5),(7)]
（ 38） Q [(5),(9)]
（ 39） [(5),(12)]
3.4.2 几种常用的归结策略
1、删除策略
定义、设 C1,C2是两个子句，若存在替换 ?，使得 C1??C2,则
称子句 C1类含 C2 。
例,P(x)类含 P(a) ? Q(y)； P(x)类含 P(a)。
删除策略。在归结过程中可随时删除以下子句：
（ 1）、含有纯文字的子句；纯文字是指在子句中无补文字
的文字。
（ 2）、含有永真式的子句；
（ 3）、被子句集中别的子句类含的子句。
使用删除策略，例 1可简化为：
（ 1） P?Q （ 7） ? P [ (2),(4) ]
（ 2） ? P?Q （ 8） Q [ (3),(4) ]
（ 3） P?? Q （ 9） [(5),(8)]
（ 4） ? P?? Q
（ 5） Q [(1),(2)]
（ 6） P [(1),(3)]
删除策略的特点：
删除策略的思想是及早删除无用字句，以避
免无效归结，缩小搜索空间。
删除策略是完备的。一个归结策略是完备的，
是指对于不可满足的子句集，使用该策略进
行归结，最终必导出空子句。
2、支持集策略
支持集是指目标公式的否定的子句集。支持集策略指
每次归结时，两个亲本子句中至少要有一个是目标
公式否定的子句或其后裔。
例、见教材 P84例 4.
支持集策略的特点：
支持集策略实际是一种目标制导的反向推理。
支持集策略是完备的。
3、线性归结策略
在归结过程中，除第一次归结可都用初始子句集 S中
的子句外，其它的各次归结至少要有一个亲本子句
是前次归结的结果。
例,P85例 5
线性归结策略的特点：完备、高效、与别的策略兼容。
4、输入归结策略
每次参加归结的亲本子句，必须至少有一个是初始子
句集 S中的子句。
输入策略的特点：
输入归结策略实际是一种自底向上的推理，它有相
当高的效率。
输入归结策略不完备。例如 S={ P?Q,? P?Q,P??
Q,? P?? Q}不可满足，但用输入归结策略导不出
空子句。
可与支持集策略、线性归结策略结合。
5、单元归结策略（单文字归结策略）
每次参加归结的两个亲本子句中，必须至少有一个是
单元子句（单文字子句）。
单元归结策略的特点：
可以尽快逼近空字句；
效率高但不完备
改进型的单元归结策略：单元优先策略。
6、祖先过滤形策略
参加归结的两个子句，要么至少有一个是初始子句集
中的子句，要么一个是另一个的祖先。
例 6,P86例 6
祖先过滤形策略的特点：
是输入策略的改进。
是完备的
3.4.3 归结策略的类型
简化性策略。
限制性策略。
有序性策略。
3.5 归结反演程序举例（略）
3.6 Horn子句归结与逻辑程序
3.6.1 子句的蕴含表示形式
正文字：原子公式称为正文字。
负文字：原子公式的否定称为负文字。
把所有正、负文字分别放在一起，任意子句可写为：
? Q1?… ?? Qn ? P1?… ? Pm
可近一步化为蕴含式：
Q1 ? Q2 ?… ? Qn ?P1? P2 ?… ? Pm
如果约定前提文字之间恒为合取关系，结论文字之间
恒为析取关系，则上式可简化为：
Q1, Q2, …, Qn ?P1,P2, …, Pm
写成另一种方式：
P1,P2, …, Pm ? Q1, Q2, …, Qn
两种特殊情形：
当 m=0时，变为 ? Q1, Q2, …, Qn,相当于 ?
（ Q1 ? Q2 ?… ? Qn ）。
当 n=0时，变为 P1,P2, …, Pm ?，这相当于 P1?
P2 ?… ? Pm 。
对于子句的蕴含表示形式，归结过程变为：从其中一
个子句的,?”号左（右）侧与另一个子句 的
,?”号右（左）侧的文字中寻找可合一文字对，
然后消去它们，并把其余的左部文字合并，作为
消解式的左部；其余的右部文字合并，作为消解
式的右部。
一般地，设子句
C,P1,…, Pm ? Q1, …, Qn
和
C?, P?1,…, P ?s ? Q ?1,…, Q ?t
中有 Pi与 Q ?j （或 Qi与 P?j ）可合一,?为它们的 MGU，则
C与 C?的归结式为
P1 ?,…, Pi-1 ?, Pi+1 ?, …, Pm ?, P ?1 ?, …, P ?s
? ? Q1 ?,…, Qn?, Q ?1 ?, …, Q?j-1 ?, Q?j+1
?,…, Q?t?
或
P1 ?,…, Pm ?, P ?1 ?, …, P?j-1 ?, P ?j+1 ?, …, P
?s ? ? Q1?,…, Qi-1?, Q ?i+1 ?, …, Qn ?, Q?1
?,…, Q?t?
定义 1 至多含有一个正文字的子句称为 Horn子句。
蕴含型 Horn子句共有三种：
（ 1）,P? Q1, Q2, …, Qm 称为条件子
句,P称为头部或结论；
（ 2）,P? 称为无条件句；
（ 3）,? Q1, Q2, …, Qm 称为目标子句，
Qi称为子目标。
例 1、证明 P(a,c)是下面子句集 {（ 1），（ 2），（ 3），
（ 4） }的逻辑结论。
证, （ 1） P(x,z) ? P1(x,y),P2 (y,z)
（ 2） P1(u,v) ? P11(u,v)
（ 3） P11(a,b)?
（ 4） P2(b,c)?
（ 5） ?P(a,c)
归结（从目标子句出发，采用线性归结）
（ 6） ? P1(a,y),P2 (y,c) [(5),(1),{ a/x,c/z}]
（ 7） ? P11(a,y),P2 (y,c) [ (6),(2),{a/u,y/v} ]
（ 8） ? P2(b,c) [ (7),(3),{b/y} ]
(9) [(8),(4)]
第三章 基于谓词逻辑的机器推理 ----3.7 非归
结演绎推理
3.7.1 Bledsoe 自然演绎法
3.7.2 基于规则的演绎推理
3.7.3 王浩算法
作业：
P85,1.(3),(6); 4.(3),(4); 7