第16章谓词演算中的归结

1、第第1616章章 谓词演算中的归结谓词演算中的归结 第三部分第三部分 知识的表示和推理知识的表示和推理合一合一 合式公式合式公式( ( 1 1，2 2，n n)( )( 1 12 2k k) )，可缩写为可缩写为1 12 2k k，其中其中11，22，k k是可能是可能包含变量包含变量1 1，2 2，n n的文字。也就是说，仅仅去掉的文字。也就是说，仅仅去掉了全称量词，并假定了全称量词，并假定i i中任何变量全称量化。这种缩写形中任何变量全称量化。这种缩写形式的合式公式叫做式的合式公式叫做子句子句。有时，用集合符号。有时，用集合符号( (1 1，2 2，k k) )表达一个子句，并假定集合中的

2、元素是析取的。表达一个子句，并假定集合中的元素是析取的。 如果两个子句的文字相匹配但是互补，我们能如果两个子句的文字相匹配但是互补，我们能归结归结它它们们就像在命题演算中一样。如果一个子句中有一个文就像在命题演算中一样。如果一个子句中有一个文字字()( ()( 是一个变量是一个变量) )，而另一个子句中有一个互补文，而另一个子句中有一个互补文字字()()，是不包含是不包含的某个项的某个项，我们能把第一个子，我们能把第一个子句中的所有句中的所有用用代替；然后对互补文字进行命题归结以代替；然后对互补文字进行命题归结以产生那两个子句的归结式。产生那两个子句的归结式。 合一合一 举例举例：考虑两个子句

3、：考虑两个子句 : : P(f(y)P(f(y)， A) Q(B A) Q(B， C) C) P(xP(x， A) R(x A) R(x， C) S(A C) S(A， B) B)。 用用f(y)f(y)代替第二个子句中的代替第二个子句中的x x产生产生: : P( f(y)P( f(y)，A) R( f(y)A) R( f(y)，C) S(AC) S(A， B) B)。 现在，两个子句中的第一个文字刚好互补，因此我们现在，两个子句中的第一个文字刚好互补，因此我们能对文字能对文字( (f(y)f(y)，A)A)执行一次归结，产生归结式执行一次归结，产生归结式: : R(f(y) R(f(y)，

4、 C) S(A C) S(A， B) Q(B B) Q(B， C) C)。 用一个被称为用一个被称为合一合一的方法计算适当的置换。合一在的方法计算适当的置换。合一在AIAI中是一个极其重要的方法。中是一个极其重要的方法。 合一合一 为了描述合一，必须先讨论一下置换为了描述合一，必须先讨论一下置换: : 一个表达式项可能是变量符号、对象常量或者函数表达式，后者包一个表达式项可能是变量符号、对象常量或者函数表达式，后者包含函数常量和表达式项。一个表达式的置换实例通过置换那个表达式中含函数常量和表达式项。一个表达式的置换实例通过置换那个表达式中的变量项而得到。因此，的变量项而得到。因此， PxPx，

5、f(y)f(y)， B B的四个置换实例是：的四个置换实例是： PzPz，f(w)f(w)， B B Px Px，f(A)f(A)， B B Pg(z) Pg(z)，f(A)f(A)， B B PC PC，f(A)f(A)， B B 上面第一个实例称为原始文字的上面第一个实例称为原始文字的字母变种字母变种( ( alphabetic variant)alphabetic variant)，因为我们仅仅用另外的变量代替了因为我们仅仅用另外的变量代替了PxPx， f(y) f(y)， B B中出现的变量。第中出现的变量。第4 4个叫个叫基例基例( (ground instance)ground i

6、nstance)，因为文字中没有一项包含变量因为文字中没有一项包含变量( (一个基项一个基项是一个不包含任何变量的项是一个不包含任何变量的项) )。 合一合一 我们能通过一组有序对我们能通过一组有序对s=s=1 1/1 1，2 2/2 2，n n/n n 来表达任何置换。来表达任何置换。i i/i i对意思是说对意思是说i i项替换在项替换在整个置换范围内的整个置换范围内的i i的每次出现的每次出现。而且，变量不能被一个。而且，变量不能被一个包含相同变量的项代替。使用前面包含相同变量的项代替。使用前面PxPx， f(y) f(y)， B B的四个的四个实例的置换是：实例的置换是： s1s1z/

7、xz/x， w/y w/y s2 s2A/yA/y s3 s3g(z)/xg(z)/x， A/y A/y s4 s4C/xC/x， A/y A/y 上面是用上面是用ss来指称一个使用置换来指称一个使用置换s s的表达式的表达式的一个置的一个置换实例。因此，换实例。因此，PzPz， f(w) f(w)， B= Px B= Px，f(y)f(y)，Bs1Bs1。 Pz Pz，f(w)f(w)， B B Px Px，f(A)f(A)， B B Pg(z) Pg(z)，f(A)f(A)， B B PC PC，f(A)f(A)， B B合一合一 两个置换两个置换s1s1和和s2s2的组合用的组合用s1s

8、2s1s2指称，它指的是这个置指称，它指的是这个置换通过先把换通过先把s2s2应用到应用到s1s1各项，再加上不含出现在各项，再加上不含出现在s1s1中变量中变量的所有的所有s2s2对而得到对而得到，因此；，因此； g(xg(x，y)/z y)/z A/x A/x，B/yB/y， C/w C/w， D/z D/z g(A g(A，B)/zB)/z，A/xA/x， B/y B/y， C/w C/w f(y)/x,z/y f(y)/x,z/y a/x,b/y,y/z= a/x,b/y,y/z= f(b)/x ,y/z f(b)/x ,y/z可以看出，可以看出，把把s1s1和和s2s2连续地应用到连

9、续地应用到表达式和把表达式和把s1s2s1s2应用应用到到是相同的，即：是相同的，即：( ( s1) s2 s1) s2(sls2)(sls2)。也能看出，也能看出，置换组合是符合结合律的。即：置换组合是符合结合律的。即：( (s1s2) s3s1s2) s3s1(s2s3)s1(s2s3)。 举例举例: :是是P(xP(x，y)y)， s1 s1是是 f(y)f(y)xx， s2 s2是是 A Ayy。那么那么 ( (s1)s2s1)s2p(f(y)p(f(y)，y) y) A Ayy P(f(A) P(f(A)，A)A)和和 (s1s2) (s1s2)P(xP(x，y) y) f(A) f

10、(A)x x，A Ayy P(f(A) P(f(A)，A) A) 合一合一 一般地讲，置换不符合交换律，即一般地讲，置换不符合交换律，即s1s2s1s2s2s1s2s1是不成是不成立的。因此，改变应用置换顺序会产生差异。立的。因此，改变应用置换顺序会产生差异。 例如：例如：是是P(xP(x，y)y)， s1 s1是是 f(y)f(y)xx， s2 s2是是A Ayy。那么那么 (s1s2) (s1s2)P(f(A)P(f(A)， A) A) (s2s1) (s2s1)P(xP(x， y) y) A Ay y，f(y)f(y)xx P(f(y) P(f(y)， A) A) 合一合一 当一个置换当

11、一个置换s s被应用到一个表达式集合被应用到一个表达式集合 i i 的每一个的每一个成员时，用成员时，用i iss表示置换实例集合。如果存在一个置换表示置换实例集合。如果存在一个置换s s，它使它使1 1s=s=2 2s=s=3 3s s，我们说表达式集合我们说表达式集合i i 是是可以可以合一的合一的( (unifiable)unifiable)。在这种情况下，在这种情况下，s s被称为被称为i i 的一个的一个合一式合一式( (unifier)unifier)，因为它的使用把集合压缩成为因为它的使用把集合压缩成为一个单元素集合。一个单元素集合。例如：例如： s s A Ax x，B Byy

12、把集合把集合pxpx，f(y)f(y)，BB， Px Px，f(B)f(B)，BB合一产生合一产生 pApA，f(B)f(B)，BB。 最一般最一般( (或最简单或最简单) )的合一式的合一式( (mgu)mgu)i i 的的g g有下面的有下面的特性：如果特性：如果s s是产生是产生i iss的的i i 的任意合一式，那么存的任意合一式，那么存在一个置换在一个置换ss以使以使i iss i igs gs 。而且，经一个而且，经一个最一般的合一式产生的通用实例除了字母变化外是惟一的。最一般的合一式产生的通用实例除了字母变化外是惟一的。 合一合一 有很多算法可以用来找到一个可以合一的表达式的有限

13、集合的有很多算法可以用来找到一个可以合一的表达式的有限集合的mgumgu，并且当那个集合不能被合一时能返回失败。这里给出的算法并且当那个集合不能被合一时能返回失败。这里给出的算法UNIFYUNIFY工作在一个列表结构的表达式集合上，在这些表达式中，每个工作在一个列表结构的表达式集合上，在这些表达式中，每个文字和项作为一个列表项。例如：文字和项作为一个列表项。例如：P(xP(x， f(A f(A， y) y)写为写为( (P x P x (f A y)(f A y)列表结构形式，表达式列表结构形式，表达式P P是列表中的第一个顶级表达式，是列表中的第一个顶级表达式，( (f A y)f A y)

14、是第三个顶级表达式。是第三个顶级表达式。 UNIFY UNIFY的基础是的基础是分歧集分歧集( (disagreement set)disagreement set)的思想。一个非空的的思想。一个非空的表达式集合表达式集合W W的分歧集由下面的方法得到：的分歧集由下面的方法得到： 首先定位第一个符号首先定位第一个符号( (从左边计数从左边计数) )，如果在这个位置不是，如果在这个位置不是W W中的中的所有表达式有完全相同的符号，那么从所有表达式有完全相同的符号，那么从W W的每个表达式中提取从占据的每个表达式中提取从占据那个位置的符号开始的子表达式，各个子表达式集合构成那个位置的符号开始的子表

15、达式，各个子表达式集合构成W W的分歧集。的分歧集。 例如，两个列表例如，两个列表(P x (f A y)P x (f A y)，( (P x (f z B)P x (f z B)集合的分集合的分歧集是歧集是 A A，zz。分歧集能用置换分歧集能用置换A Az z产生协调。产生协调。 合一合一 UNIFY()( UNIFY()( 是一个列表表达式集合是一个列表表达式集合) ) 1) 1)k0k0， k k，k k(初始化步骤；初始化步骤； 是空的置换是空的置换) )。 2) 2)如果如果k k是一个单元素集合，用是一个单元素集合，用的的mgu mgu k k退出；否则继续。退出；否则继续。 3

16、) 3)D Dk kk k的分歧集。的分歧集。 4) 4)如果在如果在 D Dk k中存在元素中存在元素 v vk k和和t tk k，v vk k 是一个不会出现在是一个不会出现在t tk k 中的变中的变量，则继续；否则，失败退出，量，则继续；否则，失败退出，是不可以合一的。是不可以合一的。 5) 5) k+1k+1k kttk k/v/vk k ，k+1k+1ttk kv vk k ( (注意注意k+1k+1=k kk+1k+1) )。 6)kk+1 6)kk+1 7) 7)转到第转到第2 2步。步。 合一合一 例：例： 设设 F= P(a，x，f(g(y)，P(z，f(z)，f(u)，

17、求其合一。求其合一。 1）令令0 0= = ,F,F0 0=F,=F,因因F F0 0中含有两个表达式，所以中含有两个表达式，所以0 0不是最不是最一般合一。一般合一。 2 2）分歧集）分歧集D D0 0= = a a，z.z. 3) 3) 1 1= = 0 0 a/z = a/z = a/za/z F F1 1= = P(aP(a，x x，f(g(y)f(g(y)，P(aP(a，f(a)f(a)，f(u)f(u) 4) D1= 4) D1= x,f(a)x,f(a) 5) 5) 2 2= = 1 1 f(a)/x= f(a)/x= a/z,f(a)/xa/z,f(a)/x F F2 2=F=

18、F1 1 f(a)/x= f(a)/x= P(a,f(a),f(g(y),P(a,f(a),f(u)P(a,f(a),f(g(y),P(a,f(a),f(u) 6) D 6) D2 2= = g(y),ug(y),u 7) 7) 3 3 = = 2 2 g(y)/u= g(y)/u= a/z,f(a)/x,g(y)/ua/z,f(a)/x,g(y)/u合一合一 8) F 8) F3 3=F=F2 2 g(y)/u= g(y)/u= P(a,f(a),f(g(y).P(a,f(a),f(g(y). 因为因为F F3 3只含一个表达式，所以只含一个表达式，所以0 0就是最一般合一，就是最一般合一，

19、即即 a/z,f(a)/x,g(y)/ua/z,f(a)/x,g(y)/u是最一般合一。是最一般合一。谓词演算归结谓词演算归结 假如假如1 1和和2 2是两个子句是两个子句( (表示为文字集合表示为文字集合) )。如果如果1 1中有一个原子中有一个原子， 2 2中有一个文字中有一个文字，并使并使和和有一个最一般合一式有一个最一般合一式( (mgu)mgu)，那么这两那么这两个子句有一个归结式个子句有一个归结式，它通过把置换它通过把置换与与1 1和和2 2减去互补其文字的并集而得到。减去互补其文字的并集而得到。 即：即：=（ 1 1 - - ）（ 2 2 - - ） 谓词演算归结谓词演算归结 在

20、两个子句被归结前，为了避免变量混淆，我们对在两个子句被归结前，为了避免变量混淆，我们对每个子句中的变量重命名以使一个子句中的变量不会出每个子句中的变量重命名以使一个子句中的变量不会出现在另一个中。例如：假如我们正在归结现在另一个中。例如：假如我们正在归结P(x) Q(f(x)P(x) Q(f(x)与与R(g(x) R(g(x) Q(f(A)Q(f(A)，首先重写第二个子句，比如说首先重写第二个子句，比如说为为R(g(y) R(g(y) Q(f(A)Q(f(A)，然后执行归结获得然后执行归结获得P(A) P(A) R(g(y)R(g(y)。变量重命名被称为变量重命名被称为对变量进行标准化对变量进

21、行标准化( (standardizing the variables apart)standardizing the variables apart)。 下面是一些例子下面是一些例子: : P(x)P(x)，Q(xQ(x，y)y)和和P(A)P(A)，R(BR(B，z)z)归结产生归结产生: : Q(AQ(A，y)y)，R(BR(B，z)z)。 P(xP(x，x)x)，Q(x)Q(x)，R(x)R(x)和和P(AP(A，z)z)，Q(B)Q(B)可用两可用两种不同的方式归结，分别产生种不同的方式归结，分别产生Q(A)Q(A)，R(A)R(A)，Q(B)Q(B)和和P(BP(B，B)B)，R(B

22、)R(B)，P(AP(A，z)z)。 谓词演算归结谓词演算归结 有时需要对谓词演算归结有一个稍强的定义。例如，有时需要对谓词演算归结有一个稍强的定义。例如，考虑两个子句考虑两个子句P(u)P(u)，P(v)P(v)和和P(x)P(x)，P(y)P(y)。这两个子这两个子句各自有基例句各自有基例P(A)P(A)和和P(A)(P(A)(由置换由置换A Au u， A Av v， A Ax x， A Ay y获得获得) )。从这些基例中，能推断出空子句，因此我们。从这些基例中，能推断出空子句，因此我们应该能从初始子句推断它，但是刚刚给定的归结规则不能应该能从初始子句推断它，但是刚刚给定的归结规则不能

23、做到这些。做到这些。更强的规则更强的规则如下如下: : 假定假定1 1和和2 2是两个子句是两个子句( (再次表示为文字集合再次表示为文字集合) )。如。如果有果有1 1的一个子集的一个子集1 1和和2 2的一个子集的一个子集2 2，使得使得1 1的文字能与的文字能与2 2的文字的否定式用最一般合一式的文字的否定式用最一般合一式合一，合一，那么这两个子句有一个归结式那么这两个子句有一个归结式，它通过把置换它通过把置换与与1 1和和2 2减去其互补子集的并集而得到。即：减去其互补子集的并集而得到。即：=(=(1 1- -1 1)( )( 2 2- -2 2) ) 用这个归结定义，归结子句用这个归

24、结定义，归结子句P(u),P(v)P(u),P(v)和和P P（x x），），P(y)P(y)产生空子句。产生空子句。 完备性和合理性完备性和合理性 谓词演算的归结是合理的。也就是说，如果谓词演算的归结是合理的。也就是说，如果是两个子句是两个子句和和归结式，那么归结式，那么， 。这个事实的证明不比命题归结的合理性证明难这个事实的证明不比命题归结的合理性证明难。 把任意的合式公式转化为子句形式把任意的合式公式转化为子句形式 就像在命题演算中一样，任何合式公式能被转化就像在命题演算中一样，任何合式公式能被转化为子句形式。步骤如下：为子句形式。步骤如下： 1)1)消除蕴含符号消除蕴含符号( (如在命

25、题演算中一样如在命题演算中一样) )。 2)2)减少否定符号的范围减少否定符号的范围( (如在命题演算中一样如在命题演算中一样) )。 3)3)变量标准化变量标准化，由于量词范围内的变量像，由于量词范围内的变量像“哑哑元元”，因此它们能被更名，以使每个量词有它自己，因此它们能被更名，以使每个量词有它自己的变量符号。的变量符号。 举例：举例：可以改写为可以改写为: : x x) )Q Q( (x x) ) ( (P P( (x x) )x x) ) ( ( y y) )Q Q( (y y) ) ( (P P( (x x) )x x) ) ( ( 把任意的合式公式转化为子句形式把任意的合式公式转化

26、为子句形式 4) 4)取消存在量词取消存在量词。 举例：在举例：在 中，存在量词中，存在量词( ( y)y)在一个全称量词在一个全称量词( ( x)x)范围内，因此，范围内，因此，y y的的“存在存在”可能依可能依赖赖x x的值。例如，如果的意思是的值。例如，如果的意思是“每个人每个人x x有身高有身高y”y”，那那么很明显身高与人有关。用么很明显身高与人有关。用某个未知的函数某个未知的函数h(x)h(x)显式定显式定义这个依赖关系，义这个依赖关系，h(x)h(x)把把x x的每个值映射为存在的的每个值映射为存在的y y值值。这样的一个函数叫做这样的一个函数叫做 Skolem Skolem 函

27、数函数。如果我们把。如果我们把 Skolem Skolem 函数用在函数用在y y存在的位置，就能取消存在量词，并写为存在的位置，就能取消存在量词，并写为 h h( (x x) ) , ,x x) )H He ei ig gh ht t x x( (y y) ) , ,y y) )H He ei ig gh ht t( (x xx x) ) ( ( (把任意的合式公式转化为子句形式把任意的合式公式转化为子句形式 从一个合式公式中消除一个存在量词的一般规则是用从一个合式公式中消除一个存在量词的一般规则是用一个一个Skolem Skolem 函数代替函数代替存在量词作用范围内变量的每一次存在量词作

28、用范围内变量的每一次出现出现， Skolem Skolem 函数的参数是那些函数的参数是那些被全称量词约束被全称量词约束的变量，的变量，全称量词的范围包括要被消除的存在量词的范围。用在全称量词的范围包括要被消除的存在量词的范围。用在Skolem Skolem 函数中的函数符号必须是函数中的函数符号必须是“新的新的”，不能是已经，不能是已经出现在任何合式公式中被用在归结反驳中的符号。出现在任何合式公式中被用在归结反驳中的符号。因此，我们能从因此，我们能从 经消除经消除( ( z z) )，产生产生z z) ) u u, ,y y, ,u u) )R R( (x x, ,( (z z) )y y,

29、 ,z z) ) P P( (x x, ,y y) ) ( (x x) ) ( ( (w w) )Q Q( (w w) ) ( ( y y) ) ) g g( (x x, ,u u, ,y y, ,u u) )R R( (x x, ,( (y y) ) )g g( (x x, ,y y, ,y y) ) P P( (x x, ,x x) ) ( ( (w w) )Q Q( (w w) ) ( ( 把任意的合式公式转化为子句形式把任意的合式公式转化为子句形式 我们能从我们能从 经消除经消除( ( w w) )，产生产生 其中其中g(Xg(X，y)y)和和h(x)h(x)都是都是Skolem Sk

30、olem 函数。函数。 如果要被消除的存在量词不在任何全称量词的范围内，如果要被消除的存在量词不在任何全称量词的范围内，那么我们使用一个那么我们使用一个没有参数的没有参数的Skolem Skolem 函数函数，它只是，它只是y y一个一个常量。因此，常量。因此，( ( x) P(x)x) P(x)成为成为P(Sk)P(Sk)，常量符号常量符号 Sk (Sk (用来指用来指向我们知道存在的那个项。另外，向我们知道存在的那个项。另外，Sk Sk 是一个新的符号常量是一个新的符号常量且没有用在其他函数中，这是必要的。且没有用在其他函数中，这是必要的。 P(w)P(w)w)w)w)Q(x,w)Q(x,

31、( (y)y)P(f(x,P(f(x,P(y)P(y)x)x)(P(x)P(x)x)x)( ( P P( (h h( (x x) ) ) h h( (x x) ) ) Q Q( (x x, ,y y) ) ) P P( (f f( (x x, ,P P( (y y) )y y P P( (x x) )x x) ) ( ( 把任意的合式公式转化为子句形式把任意的合式公式转化为子句形式 为了从一个合式公式中消除所有的存在量化变量，依为了从一个合式公式中消除所有的存在量化变量，依次对每个子公式使用前述的过程。从一组合式公式中消除次对每个子公式使用前述的过程。从一组合式公式中消除存在量词产生公式集合的

32、存在量词产生公式集合的Skolem Skolem 范式。范式。 注意，一个合式公式的注意，一个合式公式的Skolem Skolem 范式并不等价于原始范式并不等价于原始的合式公式！公式的合式公式！公式( ( x) P(x)x) P(x)被它的被它的Skolem Skolem 范式范式P(Sk)P(Sk)逻逻辑涵蕴，但反过来就不行。辑涵蕴，但反过来就不行。 作为另一个例子，注意作为另一个例子，注意 P(A)P(B) P(A)P(B) ( ( x)P(x) x)P(x)，但是但是 P(A) P(B) P(A) P(B) P(Sk)P(Sk)。公式集合公式集合是可以满足的，是可以满足的，当且仅当当且

33、仅当的的Skolem Skolem 范式是可以满足的。或者，对归结范式是可以满足的。或者，对归结反驳更有用的是，反驳更有用的是， 是不可满足的，当且仅当是不可满足的，当且仅当的的Skolem Skolem 范式是不可满足。范式是不可满足。 把任意的合式公式转化为子句形式把任意的合式公式转化为子句形式 5)5)转化为前束范式转化为前束范式。在这个阶段，没有任何残留的。在这个阶段，没有任何残留的存在量词，每个全称量词有它自己的变量符号。现在，存在量词，每个全称量词有它自己的变量符号。现在，我们可以把所有的全称量词移到合式公式的前面，并且我们可以把所有的全称量词移到合式公式的前面，并且让每个量词的范

34、围包括跟随它的合式公式的全部。这样让每个量词的范围包括跟随它的合式公式的全部。这样的合式公式被称为是在前束范式中。前束范式的一个合的合式公式被称为是在前束范式中。前束范式的一个合式公式包括一个称为前束范式的量词，它后面跟随一个式公式包括一个称为前束范式的量词，它后面跟随一个称为称为矩阵矩阵( (matrix)matrix)的没有量词的公式。的没有量词的公式。 合式公式：合式公式：的前束范式是：的前束范式是： P P( (h h( (x x) ) ) h h( (x x) ) ) Q Q( (x x, ,y y) ) ) P P( (f f( (x x, ,P P( (y y) ) P P( (

35、x x) )y y) ) x x) )( ( (P P( (h h( (x x) ) ) h h( (x x) ) ) Q Q( (x x, ,y y) ) ) P P( (f f( (x x, ,P P( (y y) )y y P P( (x x) )x x) ) ( ( 6 6) )将矩阵写成一个合取范式将矩阵写成一个合取范式。像命题演算一样，我。像命题演算一样，我们可以通过重复使用分配律，用们可以通过重复使用分配律，用 代替，代替， 把任何矩阵改写成合取范式。把任何矩阵改写成合取范式。 将前述合式公式例子的矩阵改写成合取范式，它变将前述合式公式例子的矩阵改写成合取范式，它变为为 y y)

36、 ) ) P P( (f f( (x x, ,P P( (y y) )P P( (x x) )y y) ) x x) )( ( () )( () )( (3 31 12 21 1 ) )( (3 32 21 1 7)7)消除全称量词消除全称量词。由于用在合式公式中的所有变量。由于用在合式公式中的所有变量必须是在一个量词范围内，保证在这一步保留的所有变必须是在一个量词范围内，保证在这一步保留的所有变量都被全称量化。而且，全称量化的顺序并不重要，因量都被全称量化。而且，全称量化的顺序并不重要，因此可以删去明确出现的全称量词，并且根据约定可以保此可以删去明确出现的全称量词，并且根据约定可以保证矩阵中

37、的所有变量都被全称量化。现在，只留下了一证矩阵中的所有变量都被全称量化。现在，只留下了一个合取范式的矩阵。个合取范式的矩阵。 把任意的合式公式转化为子句形式把任意的合式公式转化为子句形式 P P( (h h( (x x) ) ) P P( (x x) ) h h( (x x) ) ) Q Q( (x x, ,P P( (x x) ) 把任意的合式公式转化为子句形式把任意的合式公式转化为子句形式 8)8)消除消除符号符号。可以用合式公式集合。可以用合式公式集合1 1， 2 2 代代替表达式替表达式( (1 12 2) )，删除显式出现的删除显式出现的符号。重复代符号。重复代替的结果是获得一个有限

38、的合式公式集合，合式公式替的结果是获得一个有限的合式公式集合，合式公式中的每一项是一个文字析取项。只包含文字析取项的中的每一项是一个文字析取项。只包含文字析取项的任何合式公式被称为一个子句，我们的合式公式例子任何合式公式被称为一个子句，我们的合式公式例子被转化为下面的子句集合：被转化为下面的子句集合： P(x)P(x)P(y)Pf(x,y)P(y)Pf(x,y) P(x)Qx,h(x)P(x)Qx,h(x) P(x)P(x)Ph(x) Ph(x) 把任意的合式公式转化为子句形式把任意的合式公式转化为子句形式 9)9)变量更名变量更名。变量符号可以被更名，以使没有任何。变量符号可以被更名，以使没

39、有任何变 量 符 号 出 现 在 多 于 一 个 的 子 句 中 。 注 意 到变 量 符 号 出 现 在 多 于 一 个 的 子 句 中 。 注 意 到 ( ( x)P(x)Q(x)x)P(x)Q(x)等价于等价于( x)P(x) (x)P(x) ( y)Q(y)y)Q(y)。现在子句是：现在子句是： P(x1)P(x1)P(y) Pf(xlP(y) Pf(xl，y)y) P(x2)Qx2P(x2)Qx2，h(x2)h(x2) P(x3)Ph(x3)P(x3)Ph(x3) 一个子句的文字可以包含变量，但这些变量总是被一个子句的文字可以包含变量，但这些变量总是被理解为是全称量化的。理解为是全称

40、量化的。 用归结证明定理用归结证明定理 当归结用作一个定理证明系统的推论规则时，可以当归结用作一个定理证明系统的推论规则时，可以将要从中证明一个定理的合式公式集合首先转化成子句。将要从中证明一个定理的合式公式集合首先转化成子句。可以证明如果合式公式可以证明如果合式公式从一个合式公式集合从一个合式公式集合中逻辑中逻辑地产生，那么同样也从地产生，那么同样也从中的合式公式转换成的子句集中的合式公式转换成的子句集合中逻辑地产生。反之亦然合中逻辑地产生。反之亦然。因此，子句是一个表达谓因此，子句是一个表达谓词演算合式公式的完备的通用形式。词演算合式公式的完备的通用形式。 假如机器人知道假如机器人知道27

41、27号房间中的所有箱子都比号房间中的所有箱子都比2828号房间中号房间中的小。即：的小。即： 1)( 1)( x x，y)y)Package(x)Package(y)Inroom(xPackage(x)Package(y)Inroom(x，27)Inroom(y27)Inroom(y，28) 28) Smaller(x Smaller(x，y )y ) 缩写谓词符号使公式紧凑。转换为子句形式，产生：缩写谓词符号使公式紧凑。转换为子句形式，产生： 2) 2)P(x) P(x) P(y) P(y)I(xI(x，27)27)I(yI(y，28)S(x28)S(x，y)y) 假定机器人知道箱子假定机器

42、人知道箱子A A在在2727号或号或2828号房间中号房间中( (但不知道是但不知道是哪一个哪一个) )。它知道箱子。它知道箱子B B在房间在房间2727中且中且B B不比不比A A小。小。 3) 3) P (A) P (A) 4) 4) P( B)P( B) 5) I( A 5) I( A，27) I(A27) I(A，28)28) 6) I( B 6) I( B，27)27) 7) 7) S( B S( B，A)A)用归结反驳，机器人能证明箱子用归结反驳，机器人能证明箱子A A在在2727号房间中。号房间中。 用归结证明定理用归结证明定理 用归结证明定理用归结证明定理 下图是一棵证明树。待

43、证明的合式公式的否定被标在左上下图是一棵证明树。待证明的合式公式的否定被标在左上角；和机器人明确知道的相对应的合式公式被标在图中沿角；和机器人明确知道的相对应的合式公式被标在图中沿右手方向。归结期间的置换在图中也已表示出来。右手方向。归结期间的置换在图中也已表示出来。 回答提取回答提取 为了用归结回答由谓词演算合式公式表示一个领域为了用归结回答由谓词演算合式公式表示一个领域知识的问题，通常要做的不只是证明一个定理。知识的问题，通常要做的不只是证明一个定理。 例如，假定必须证明形如例如，假定必须证明形如( ( ) () ()的一个定的一个定理。我们可能也想得到已经证明存在的理。我们可能也想得到已

44、经证明存在的。为了做到这为了做到这些，必须跟踪在反驳过程中所做的置换，可以用一个回些，必须跟踪在反驳过程中所做的置换，可以用一个回答文字策略跟踪那个置换。将文字答文字策略跟踪那个置换。将文字Ans (Ans (1 1，2 2，)加到要证明的定理的否定子句，执行归结直到只剩下一加到要证明的定理的否定子句，执行归结直到只剩下一个回答文字。在个回答文字。在Ans Ans 文字中的变量是出现在待证明定理文字中的变量是出现在待证明定理的否定子句形式中的所有变量。的否定子句形式中的所有变量。 在证明期间代替在证明期间代替Ans Ans 文字中变量的项，将成为被证文字中变量的项，将成为被证明合式公式中存在量

45、化变量的实例。明合式公式中存在量化变量的实例。 回答提取回答提取 在下图中，给出了如何使用在下图中，给出了如何使用Ans Ans 文字的一个例子，现在要文字的一个例子，现在要证明合式公式证明合式公式( u)I(A， u)，它可以看作是机器人问它自它可以看作是机器人问它自己：己：“A A究竟在哪个房间究竟在哪个房间?”?”。 等式谓词等式谓词 用在一个知识库公式中的关系常量常常有用在一个知识库公式中的关系常量常常有意向含意意向含意( (即关系即关系) )，但是这些关系仅仅被知识库的模型集合所约束，但是这些关系仅仅被知识库的模型集合所约束，根本不会被用在关系常量中的特殊符号所约束。归结反驳根本不会被用在