谓词演算中的归结.ppt

《谓词演算中的归结.ppt》由会员分享，可在线阅读，更多相关《谓词演算中的归结.ppt（31页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、谓词演算中的归结现在学习的是第1页，共31页合一合一 合合式式公公式式(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、能如果两个子句的文字相匹配但是互补，我们能归结归结它们它们就像在命题演算中一样。如果一个子句中有一个文字就像在命题演算中一样。如果一个子句中有一个文字()()(是一个变量是一个变量)，而另一个子句中有一个互补文字，而另一个子句中有一个互补文字()()，是是不包含不包含的某个项的某个项，我们能把第一个子句中的所有，我们能把第一个子句中的所有用用代替；代替；然后对互补文字进行命题归结以产生那两个子句的归结式。然后对互补文字进行命题归结以产生那两个子句的归结式。现在学习的是第2页，共31页合一合一 举例举例：考虑两个子句：考虑两个子句:P(f(y)P(f(y)，A)Q(B A)Q(B，C)C)P(x

3、P(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)，C)S(A C)S(A，B)Q(B B)Q(B，C)C)。用一个被称为用一个被称为合一合一的方法计算适当的置换。合一在的方法计算适当的置换。合一在AIAI中是一中

4、是一个极其重要的方法。个极其重要的方法。现在学习的是第3页，共31页合一合一 为了描述合一，必须先讨论一下置换为了描述合一，必须先讨论一下置换:一一个个表表达达式式项项可可能能是是变变量量符符号号、对对象象常常量量或或者者函函数数表表达达式式，后后者者包包含含函函数数常常量量和和表表达达式式项项。一一个个表表达达式式的的置置换换实实例例通通过过置置换换那那个个表表达达式式中中的的变变量量项项而而得得到到。因因此此，P Pxx，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

5、)，B B PC PC，f(A)f(A)，B B 上面第一个实例称为原始文字的上面第一个实例称为原始文字的字母变种字母变种(alphabetic variant)alphabetic variant)，因为我们因为我们仅仅用另外的变量代替了仅仅用另外的变量代替了PxPx，f(y)f(y)，B B中出现的变量。第中出现的变量。第4 4个叫个叫基例基例(ground ground instance)instance)，因为文字中没有一项包含变量因为文字中没有一项包含变量(一个基项是一个不包含任何变量的项一个基项是一个不包含任何变量的项)。现在学习的是第4页，共31页合一合一 我我们们能能通通过过一

6、一组组有有序序对对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/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来指称一个使用置换来指称一个使用置

7、换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现在学习的是第5页，共31页合一合一 两个置换两个置换s1s1和和s2s2的组合用的组合用s1s2s1s2指称，它指的是这个置换通过指称，它指的是这个置换通过先把先把s2s2应用到应用到s1s1各项，再加上不含出现在各项，再加上不含出现在s1s1中变量的所有中变量的所有s2s2对而得对而得到

8、到，因此；，因此；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连续地应用到连续地应用到表达式和把表达式和把s1s2s1s2应用到应用到是是相同的，即：相同的，即：(s1)s2 s1)s2(sls2)(sls2)。也能看出，置换组合是符也能看出，置换组合是符合结合律的。即：合结合律的。即：(

9、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(A)x x，A Ayy P(f(A)P(f(A)，A)A)现在学习的是第6页，共31页合一合一 一一般般地地讲讲，置置换换不不符符合合交交换换律律，即即s1s2s1s2s2s1s2s1是是不不成成立立的的。因因此，改变应用置换顺序会产生差异。此，改变应用置换

10、顺序会产生差异。例如：例如：是是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)现在学习的是第7页，共31页合一合一 当一个置换当一个置换s s被应用到一个表达式集合被应用到一个表达式集合 i i 的每一个成员的每一个成员时，用时，用i iss表示置换实例集合。如果存在一个置换表示置换实例集合。如果存在一个置换s s，它使它使1 1s=s=2 2s=s=3 3s s，我们说

11、表达式集合我们说表达式集合i i 是可以是可以合一的合一的(unifiable)unifiable)。在这种情况下，在这种情况下，s s被称为被称为i i 的一个的一个合一式合一式(unifier)unifier)，因为它的使用把集合压缩成为一个单元素集合。因为它的使用把集合压缩成为一个单元素集合。例如：例如：s s A Ax x，B Byy把集合把集合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

12、s是产生是产生i iss的的i i 的任意合一式，那么存在一个置换的任意合一式，那么存在一个置换ss以使以使i iss i igs gs 。而且，经一个最一般的合一而且，经一个最一般的合一式产生的通用实例除了字母变化外是惟一的。式产生的通用实例除了字母变化外是惟一的。现在学习的是第8页，共31页合一合一 有很多算法可以用来找到一个可以合一的表达式的有限集合的有很多算法可以用来找到一个可以合一的表达式的有限集合的mgumgu，并且当那个并且当那个集合不能被合一时能返回失败。这里给出的算法集合不能被合一时能返回失败。这里给出的算法UNIFYUNIFY工作在一个列表结构的表工作在一个列表结构的表达式

13、集合上，在这些表达式中，每个文字和项作为一个列表项。例如：达式集合上，在这些表达式中，每个文字和项作为一个列表项。例如：P(xP(x，f(A f(A，y)y)写为写为(P x (f A y)P x (f A y)列表结构形式，表达式列表结构形式，表达式P P是列表中是列表中的第一个顶级表达式，的第一个顶级表达式，(f A y)f A y)是第三个顶级表达式。是第三个顶级表达式。UNIFY UNIFY的基础是的基础是分歧集分歧集(disagreement set)disagreement set)的思想。一个非空的表达式集合的思想。一个非空的表达式集合W W的分歧集由下面的方法得到：的分歧集由下

14、面的方法得到：首先定位第一个符号首先定位第一个符号(从左边计数从左边计数)，如果在这个位置不是，如果在这个位置不是W W中的所有表达式有中的所有表达式有完全相同的符号，那么从完全相同的符号，那么从W W的每个表达式中提取从占据那个位置的符号开始的子表的每个表达式中提取从占据那个位置的符号开始的子表达式，各个子表达式集合构成达式，各个子表达式集合构成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产生协调。产生协调。现在学

15、习的是第9页，共31页合一合一 UNIFY()(UNIFY()(是一个列表表达式集合是一个列表表达式集合)1)1)k0k0，k k，k k(初始化步骤；初始化步骤；是空的置换是空的置换)。2)2)如果如果k k是一个单元素集合，用是一个单元素集合，用的的mgu mgu k k退出；否则继续。退出；否则继续。3)3)D Dk kk k的分歧集。的分歧集。4)4)如如果果在在 D Dk k中中存存在在元元素素 v vk k和和t tk k，v vk k 是是一一个个不不会会出出现现在在t tk k 中中的的变变量量，则则继继续；否则，失败退出，续；否则，失败退出，是不可以合一的。是不可以合一的。5

16、)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步。步。现在学习的是第10页，共31页合一合一 例：例：设设 F=P(a，x，f(g(y)，P(z，f(z)，f(u)，求其合一。求其合一。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

17、 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=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现在学习的是第11页，共31页合一合一 8

18、)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就是最一般合一，就是最一般合一，即即 a/z,f(a)/x,g(y)/ua/z,f(a)/x,g(y)/u是最一般合一。是最一般合一。现在学习的是第12页，共31页谓词演算归结谓词演算归结 假假如如1 1和和2 2是是两两个个子子句句(表表示示为为文文字字集集合合)。如如果果1 1中中有有一一个个原原子子，2 2中中有有一一个个文文字字，并并使使和和有有一一个个最最一一般般合合一一式式(mgu)mgu)，

19、那那么么这这两两个个子子句句有有一一个个归归结结式式，它它通通过过把把置置换换与与1 1和和2 2减减去去互互补补其其文文字字的的并并集而得到。集而得到。即：即：=（1 1-）（2 2-）现在学习的是第13页，共31页谓词演算归结谓词演算归结 在在两两个个子子句句被被归归结结前前，为为了了避避免免变变量量混混淆淆，我我们们对对每每个个子子句句中中的的变变量量重重命命名名以以使使一一个个子子句句中中的的变变量量不不会会出出现现在在另另一一个个中中。例例如如：假假如如我我们们正正在在归归结结P(x)P(x)Q(f(x)Q(f(x)与与R(g(x)R(g(x)Q(f(A)Q(f(A)，首首先先重重写

20、写第第二二个个子子句句，比比如如说说为为R(g(y)R(g(y)Q(f(A)Q(f(A)，然然后后执执行行归归结结获获得得P(A)P(A)R(g(y)R(g(y)。变变量量重重命命名名被被称称为为对对变变量量进进行行标准化标准化(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

21、(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)R(B)，P(AP(A，z)z)。现在学习的是第14页，共31页谓词演算归结谓词演算归结 有有时时需需要要对对谓谓词词演演算算归归结结有有一一个个稍稍强强的的定定义义。例例如如，考考虑虑两两个个子子句句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

22、 Ax x，A Ay y获获得得)。从从这这些些基基例例中中，能能推推断断出出空空子子句句，因因此此我我们们应应该该能能从从初初始始子子句句推推断断它它，但但是是刚刚刚刚给给定定的的归归结结规规则则不不能能做做到到这这些些。更更强强的的规则规则如下如下:假假定定1 1和和2 2是是两两个个子子句句(再再次次表表示示为为文文字字集集合合)。如如果果有有1 1的的一一个个子子集集1 1和和2 2的的一一个个子子集集2 2，使使得得1 1的的文文字字能能与与2 2的的文文字字的的否否定定式式用用最最一一般般合合一一式式合合一一，那那么么这这两两个个子子句句有有一一个个归归结结式式，它它通通过过把把置

23、置换换与与1 1和和2 2减减去去其其互互补补子子集集的的并并集集而而得到。即：得到。即：=(=(1 1-1 1)()(2 2-2 2)用这个归结定义，归结子句用这个归结定义，归结子句P(u),P(v)P(u),P(v)和和P P（x x），），P(y)P(y)产生产生空子句。空子句。现在学习的是第15页，共31页完备性和合理性完备性和合理性 谓词演算的归结是合理的。也就是说，如果谓词演算的归结是合理的。也就是说，如果是是两个子句两个子句和和归结式，那么归结式，那么，。这个事实的这个事实的证明不比命题归结的合理性证明难证明不比命题归结的合理性证明难。现在学习的是第16页，共31页把任意的合式公

24、式转化为子句形式把任意的合式公式转化为子句形式 就就像像在在命命题题演演算算中中一一样样，任任何何合合式式公公式式能能被被转转化化为为子子句句形形式。步骤如下：式。步骤如下：1)1)消除蕴含符号消除蕴含符号(如在命题演算中一样如在命题演算中一样)。2)2)减少否定符号的范围减少否定符号的范围(如在命题演算中一样如在命题演算中一样)。3)3)变变量量标标准准化化，由由于于量量词词范范围围内内的的变变量量像像“哑哑元元”，因此它们能被更名，以使每个量词有它自己的变量符号。因此它们能被更名，以使每个量词有它自己的变量符号。举例：举例：可以改写为可以改写为:现在学习的是第17页，共31页把任意的合式公

25、式转化为子句形式把任意的合式公式转化为子句形式 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值值。这样的一个函数叫做。这样的一个函数叫做 Skol

26、em Skolem 函数函数。如果我们把如果我们把 Skolem Skolem 函数用在函数用在y y存在的位置，就能取消存在量存在的位置，就能取消存在量词，并写为词，并写为 现在学习的是第18页，共31页把任意的合式公式转化为子句形式把任意的合式公式转化为子句形式 从从一一个个合合式式公公式式中中消消除除一一个个存存在在量量词词的的一一般般规规则则是是用用一一个个Skolem Skolem 函函数数代代替替存存在在量量词词作作用用范范围围内内变变量量的的每每一一次次出出现现，Skolem Skolem 函函数数的的参参数数是是那那些些被被全全称称量量词词约约束束的的变变量量，全全称称量量词词

27、的的范范围围包包括括要要被被消消除除的的存存在在量量词词的的范范围围。用用在在Skolem Skolem 函函数数中中的的函函数数符符号号必必须须是是“新新的的”，不不能能是是已已经经出出现现在在任任何何合合式式公公式式中中被被用在归结反驳中的符号。用在归结反驳中的符号。因此，我们能从因此，我们能从 经消除经消除(z z)，产生产生现在学习的是第19页，共31页把任意的合式公式转化为子句形式把任意的合式公式转化为子句形式 我们能从我们能从 经消除经消除(w w)，产生产生 其中其中g(Xg(X，y)y)和和h(x)h(x)都是都是Skolem Skolem 函数。函数。如果要被消除的存在量词不

28、在任何全称量词的范围内，那如果要被消除的存在量词不在任何全称量词的范围内，那么我们使用一个么我们使用一个没有参数的没有参数的Skolem Skolem 函数函数，它只是，它只是y y一个常量。因一个常量。因此，此，(x)P(x)x)P(x)成为成为P(Sk)P(Sk)，常量符号常量符号 Sk(Sk(用来指向我们知道存用来指向我们知道存在的那个项。另外，在的那个项。另外，Sk Sk 是一个新的符号常量且没有用在其他函是一个新的符号常量且没有用在其他函数中，这是必要的。数中，这是必要的。现在学习的是第20页，共31页把任意的合式公式转化为子句形式把任意的合式公式转化为子句形式 为为了了从从一一个个

29、合合式式公公式式中中消消除除所所有有的的存存在在量量化化变变量量，依依次次对对每每个个子子公公式式使使用用前前述述的的过过程程。从从一一组组合合式式公公式式中中消消除除存存在在量词产生公式集合的量词产生公式集合的Skolem Skolem 范式。范式。注意，一个合式公式的注意，一个合式公式的Skolem Skolem 范式并不等价于原始的合式公式！范式并不等价于原始的合式公式！公式公式(x)P(x)x)P(x)被它的被它的Skolem Skolem 范式范式P(Sk)P(Sk)逻辑涵蕴，但反过来就逻辑涵蕴，但反过来就不行。不行。作为另一个例子，注意作为另一个例子，注意 P(A)P(B)P(A)

30、P(B)(x)P(x)x)P(x)，但是但是 P(A)P(B)P(A)P(B)P(Sk)P(Sk)。公式集合公式集合是可以满足的，当且仅当是可以满足的，当且仅当的的Skolem Skolem 范式是可以满足的。或者，对归结反驳更有用的是，范式是可以满足的。或者，对归结反驳更有用的是，是不可满足的，当且仅当是不可满足的，当且仅当的的Skolem Skolem 范式是不可满足。范式是不可满足。现在学习的是第21页，共31页把任意的合式公式转化为子句形式把任意的合式公式转化为子句形式 5)5)转化为前束范式转化为前束范式。在这个阶段，没有任何残留的存在量。在这个阶段，没有任何残留的存在量词，每个全称

31、量词有它自己的变量符号。现在，我们可以把所词，每个全称量词有它自己的变量符号。现在，我们可以把所有的全称量词移到合式公式的前面，并且让每个量词的范围包有的全称量词移到合式公式的前面，并且让每个量词的范围包括跟随它的合式公式的全部。这样的合式公式被称为是在前束括跟随它的合式公式的全部。这样的合式公式被称为是在前束范式中。前束范式的一个合式公式包括一个称为前束范式的量范式中。前束范式的一个合式公式包括一个称为前束范式的量词，它后面跟随一个称为词，它后面跟随一个称为矩阵矩阵(matrix)matrix)的没有量词的公式。的没有量词的公式。合式公式：合式公式：的前束范式是：的前束范式是：现在学习的是第

32、22页，共31页 6 6)将将矩矩阵阵写写成成一一个个合合取取范范式式。像像命命题题演演算算一一样样，我我们们可可以以通过重复使用分配律，用通过重复使用分配律，用 代替，代替，把任何矩阵改写成合取范式。把任何矩阵改写成合取范式。将前述合式公式例子的矩阵改写成合取范式，它变为将前述合式公式例子的矩阵改写成合取范式，它变为 7)7)消除全称量词消除全称量词。由于用在合式公式中的所有变量必须是。由于用在合式公式中的所有变量必须是在一个量词范围内，保证在这一步保留的所有变量都被全称在一个量词范围内，保证在这一步保留的所有变量都被全称量化。而且，全称量化的顺序并不重要，因此可以删去明确量化。而且，全称量

33、化的顺序并不重要，因此可以删去明确出现的全称量词，并且根据约定可以保证矩阵中的所有变量出现的全称量词，并且根据约定可以保证矩阵中的所有变量都被全称量化。现在，只留下了一个合取范式的矩阵。都被全称量化。现在，只留下了一个合取范式的矩阵。把任意的合式公式转化为子句形式把任意的合式公式转化为子句形式 现在学习的是第23页，共31页把任意的合式公式转化为子句形式把任意的合式公式转化为子句形式 8)8)消消除除符符号号。可可以以用用合合式式公公式式集集合合1 1，2 2 代代替替表表达达式式(1 12 2)，删删除除显显式式出出现现的的符符号号。重重复复代代替替的的结结果果是是获获得得一一个个有有限限的

34、的合合式式公公式式集集合合，合合式式公公式式中中的的每每一一项项是是一一个个文文字字析析取取项项。只只包包含含文文字字析析取取项项的的任任何何合合式式公公式式被被称称为为一一个个子子句句，我们的合式公式例子被转化为下面的子句集合：我们的合式公式例子被转化为下面的子句集合：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)现在学习的是第24页，共31页把任意的合式公式转化为子句形式把任意的合式公式转化为子句形式 9)9)变变量量更更名名。变变量量符符号号可可以以被被更更名名，以以使使没没有有任任何何变变量量

35、符符号号出出现现在在多多于于一一个个的的子子句句中中。注注意意到到(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)一个子句的文字可以包含变量，但这些变量总是被理解一个子句的文字可以包含变量，但这些变量总是被理解为是全称量化的。为是全称量化的。现在学习的是第25页，共31页用归结证明定理用归结证明定理 当归结用作一个定理证明系统的推论规则时，可以将要

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

37、1)(1)(x x，y)y)Package(x)Package(y)Inroom(xPackage(x)Package(y)Inroom(x，27)Inroom27)Inroom(y(y，28)28)Smaller(x Smaller(x，y)y)现在学习的是第26页，共31页缩写谓词符号使公式紧凑。转换为子句形式，产生：缩写谓词符号使公式紧凑。转换为子句形式，产生：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)假假定定机机器器人人知知道道箱箱子子A A在在2727号号或或2828号号房房间间中中(但但不不知知道道是是哪哪一一

38、个个)。它知道箱子它知道箱子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号房间中。号房间中。用归结证明定理用归结证明定理 现在学习的是第27页，共31页用归结证明定理用归结证明定理 下图是一棵证明树。待证明的合式公式的否定被标在左上角；下图是一棵证明树。待证明的合式公式的否定被标在左上角；和机器人明确知道的相对应的合式公式被标在

39、图中沿右手方和机器人明确知道的相对应的合式公式被标在图中沿右手方向。归结期间的置换在图中也已表示出来。向。归结期间的置换在图中也已表示出来。现在学习的是第28页，共31页回答提取回答提取 为了用归结回答由谓词演算合式公式表示一个领域知识的为了用归结回答由谓词演算合式公式表示一个领域知识的问题，通常要做的不只是证明一个定理。问题，通常要做的不只是证明一个定理。例如，假定必须证明形如例如，假定必须证明形如()()()的一个定理。我们的一个定理。我们可能也想得到已经证明存在的可能也想得到已经证明存在的。为了做到这些，必须跟踪在为了做到这些，必须跟踪在反驳过程中所做的置换，可以用一个回答文字策略跟踪那

40、个置反驳过程中所做的置换，可以用一个回答文字策略跟踪那个置换。将文字换。将文字Ans(Ans(1 1，2 2，)加到要证明的定理的否定子加到要证明的定理的否定子句，执行归结直到只剩下一个回答文字。在句，执行归结直到只剩下一个回答文字。在Ans Ans 文字中的文字中的变量是出现在待证明定理的否定子句形式中的所有变量。变量是出现在待证明定理的否定子句形式中的所有变量。在证明期间代替在证明期间代替Ans Ans 文字中变量的项，将成为被证明文字中变量的项，将成为被证明合式公式中存在量化变量的实例。合式公式中存在量化变量的实例。现在学习的是第29页，共31页回答提取回答提取 在下图中，给出了如何使用

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

42、一一致，只要知识库适当地约束实际的关系。致，只要知识库适当地约束实际的关系。然而，有一些重要且经常出现的关系，我们可能想让所有的然而，有一些重要且经常出现的关系，我们可能想让所有的知识库描述它们。例如等式关系，我们可以使用前缀形式知识库描述它们。例如等式关系，我们可以使用前缀形式EqualsEquals(A(A，B)B)或者中缀形式或者中缀形式A AB B来表示一个关系常量。仅仅因为在来表示一个关系常量。仅仅因为在知识库中包括了公式知识库中包括了公式Equals(AEquals(A，B)B)，并不意味着能够从并不意味着能够从P(A)P(A)中推中推出出P(B)P(B)，正如我们也不能归结正如我们也不能归结Q(BQ(B，A)A)和和Q(AQ(A，B)B)一样。没有一样。没有附加的公式，知识库无法知道附加的公式，知识库无法知道EqualsEquals是什么。是什么。现在学习的是第31页，共31页