人工智能原理教案02章 归结推理方法2归结推理方法(共94张PPT).pptx

《人工智能原理教案02章 归结推理方法2归结推理方法(共94张PPT).pptx》由会员分享，可在线阅读，更多相关《人工智能原理教案02章 归结推理方法2归结推理方法(共94张PPT).pptx（94页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二章第二章归结推理方法归结推理方法 课前指导课前指导2.1 2.1 归结原理概述归结原理概述2.2 2.2 命题逻辑的归结命题逻辑的归结2.3 2.3 谓词逻辑归结法基础谓词逻辑归结法基础2.4 2.4 归结原理归结原理2.5 2.5 归结过程控制策略归结过程控制策略2.6 Herbrand2.6 Herbrand定理定理章节小结章节小结培训专用课前指导课前指导【学习目标学习目标】本章主要讨论命题逻辑和一元谓词逻辑的归结推理方法。同学需本章主要讨论命题逻辑和一元谓词逻辑的归结推理方法。同学需要在熟练掌握一般逻辑知识的基础上，学习要在熟练掌握一般逻辑知识的基础上，学习SkolemSkolem标

2、准形和标准形和HerbrandHerbrand定理，从而对归结原理有一个比较透彻的了解。定理，从而对归结原理有一个比较透彻的了解。【学习指南学习指南】在学习新知识的同时回顾以前所学的一般逻辑知识。对所涉在学习新知识的同时回顾以前所学的一般逻辑知识。对所涉及的概念和方法不要死记硬背，对于比较抽象的概念，可以通过及的概念和方法不要死记硬背，对于比较抽象的概念，可以通过比较简单的例子来理解。比较简单的例子来理解。【难重点难重点】应该熟练掌握把逻辑公式的合取范式、应该熟练掌握把逻辑公式的合取范式、SkolemSkolem标准形的转化标准形的转化方法、归结法进行归结的过程，掌握线性归结、支撑集归结等归结

3、策方法、归结法进行归结的过程，掌握线性归结、支撑集归结等归结策略。略。培训专用【知识点知识点】归结方法的特点、与其它推理方法的比较归结方法的特点、与其它推理方法的比较 命题逻辑基础，前束范式，约束变量换名规则命题逻辑基础，前束范式，约束变量换名规则 Skolem Skolem标准形的定义，子句和子句集，定理的内容及标准形的定义，子句和子句集，定理的内容及推广推广 H H域、域、H H解释、语义树解释、语义树 合一和置换，归结过程合一和置换，归结过程 归结法的控制策略的原则及基本方法。归结法的控制策略的原则及基本方法。培训专用归结推理知识结构归结推理知识结构培训专用2.1归结原理概述归结原理概述

4、归结原理由归结原理由J.A.Robinson于于1965年提出，又称为消解原理。年提出，又称为消解原理。该原理是该原理是Robinson在在Herbrand理论基础上提出的一种基理论基础上提出的一种基于逻辑的、采用反证法的推理方法。由于其理论上的完备性，于逻辑的、采用反证法的推理方法。由于其理论上的完备性，归结原理成为机器定理证明的主要方法。归结原理成为机器定理证明的主要方法。注意注意：本课程只讨论一阶谓词逻辑描述下的归结推理方法，：本课程只讨论一阶谓词逻辑描述下的归结推理方法，不涉及高阶谓词逻辑问题不涉及高阶谓词逻辑问题本章首先介绍命题逻辑的归结，并以此为基础介绍谓词逻辑本章首先介绍命题逻辑

5、的归结，并以此为基础介绍谓词逻辑的归结过程及相关的思想、概念和定义，最后给出谓词逻辑的归结过程及相关的思想、概念和定义，最后给出谓词逻辑归结的基础归结的基础Herbrand定理的一般形式。定理的一般形式。培训专用定理证明的实质与困难定理证明的实质与困难从某种意义上讲大部分人工智能问题都可以转化为一个定理证明问从某种意义上讲大部分人工智能问题都可以转化为一个定理证明问题。题。定理证明的实质定理证明的实质：就是要对给出的（已知的）前提和结论，证明：就是要对给出的（已知的）前提和结论，证明此前提推导出该结论这一事实是永恒的真理。这是非常困难的，几此前提推导出该结论这一事实是永恒的真理。这是非常困难的

6、，几乎是不可实现的。乎是不可实现的。困难所在困难所在：要证明在一个论域上一个事件是永真的，就要证：要证明在一个论域上一个事件是永真的，就要证明在该域中的每一个点上该事实都成立。很显然，论域是不可明在该域中的每一个点上该事实都成立。很显然，论域是不可数时，该问题不可能解决。即使可数，如果该轮域是无限的，数时，该问题不可能解决。即使可数，如果该轮域是无限的，问题也无法简单地解决。问题也无法简单地解决。HerbrandHerbrand采用了采用了反证法的思想反证法的思想，将永真性的证明问题转化成为不，将永真性的证明问题转化成为不可满足性的证明问题。可满足性的证明问题。HerbrandHerbrand

7、理论为自动定理证明奠定了理论基础，理论为自动定理证明奠定了理论基础，而而RobinsonRobinson的归结原理使得自动定理证明得以实现。因此，归的归结原理使得自动定理证明得以实现。因此，归结推理方法在人工智能推理方法中有着很重要的历史地位。结推理方法在人工智能推理方法中有着很重要的历史地位。培训专用归结法的特点归结法的特点与演绎法完全不同与演绎法完全不同，归结法是一种新的，归结法是一种新的逻辑演算算法。逻辑演算算法。它是一阶逻辑中，至今为止的最有效的它是一阶逻辑中，至今为止的最有效的半可判定的算法。也是半可判定的算法。也是最适合计算机进最适合计算机进行推理行推理的逻辑演算方法。的逻辑演算方

8、法。半可判定半可判定，即，一阶逻辑中任意恒真公，即，一阶逻辑中任意恒真公式，使用归结原理，总可以在有限步内式，使用归结原理，总可以在有限步内给以判定（证明其为永真式）。给以判定（证明其为永真式）。培训专用归结法基本原理归结法基本原理归结法的基本原理：归结法的基本原理：是采用反证法或者称为反演推理方法，将待是采用反证法或者称为反演推理方法，将待证明的表达式（定理）转换成为逻辑公式（谓词公式），然后再证明的表达式（定理）转换成为逻辑公式（谓词公式），然后再进行归结，归结能够顺利完成，则证明原公式（定理）是正确性进行归结，归结能够顺利完成，则证明原公式（定理）是正确性的。的。例如：例如：由命题逻辑描

9、述的命题：由命题逻辑描述的命题：A1、A2、A3和和B，要求证明：，要求证明：如如果果A1A2A3成立，则成立，则B成立，成立，即：即：A1A2A3B是重言式（永真式）。是重言式（永真式）。归结法的思路归结法的思路：A1A2A3B是重言式等价于是重言式等价于A1A2A3B是矛盾式，也就是说永假式。是矛盾式，也就是说永假式。反证法反证法：证明：证明A1A2A3B是矛盾式是矛盾式（永假式）（永假式）归结的目的：归结的目的：建立基本规则证明该条定理（事实）成立。建立基本规则证明该条定理（事实）成立。培训专用归结法和其它推理方法的比较归结法和其它推理方法的比较 语义网络、框架表示、产生式规则等知识表示

10、方语义网络、框架表示、产生式规则等知识表示方法的推理都是以逻辑推理方法为前提的。即，有法的推理都是以逻辑推理方法为前提的。即，有了规则和已知条件，就能够依据一定的规则和公了规则和已知条件，就能够依据一定的规则和公理顺藤摸瓜找到结果。理顺藤摸瓜找到结果。而归结方法是计算机自动推理、自动推导证明用而归结方法是计算机自动推理、自动推导证明用的推理方法。（同样的内容可以在的推理方法。（同样的内容可以在“数学定理机数学定理机器证明器证明”中找到。）中找到。）培训专用2.2 2.2 命题逻辑的归结命题逻辑的归结2.2.1 2.2.1 命题逻辑基础命题逻辑基础逻辑可分为经典逻辑和非经典逻辑逻辑可分为经典逻辑

11、和非经典逻辑经典逻辑经典逻辑包括命题逻辑和谓词逻辑。包括命题逻辑和谓词逻辑。归结原理归结原理是一种主要基于谓词（逻辑）知识表示的推理方是一种主要基于谓词（逻辑）知识表示的推理方法，而命题逻辑是谓词逻辑的基础。因此，在讨论谓词逻法，而命题逻辑是谓词逻辑的基础。因此，在讨论谓词逻辑之前，先讨论命题逻辑的归结，便于内容上的理解。辑之前，先讨论命题逻辑的归结，便于内容上的理解。本节中，将主要介绍命题逻辑的归结方法，以及有关的本节中，将主要介绍命题逻辑的归结方法，以及有关的一些基础知识和重要概念，如数理逻辑基本公式变形、一些基础知识和重要概念，如数理逻辑基本公式变形、前束范式、子句集等。前束范式、子句集

12、等。培训专用命题例子命题例子命题：非真即假的简单陈述句命题：非真即假的简单陈述句。简单陈述句简单陈述句描述事实、事物的状态、关系等性质。描述事实、事物的状态、关系等性质。例如：例如：1 1、1+1=2.1+1=2.2 2、雪是黑色的。、雪是黑色的。3 3、北京是中国的首都。、北京是中国的首都。4 4、到冥王星去度假。、到冥王星去度假。判断一个句子是否是命题，首先要看它是否是陈述句，而后看它的真值是否唯判断一个句子是否是命题，首先要看它是否是陈述句，而后看它的真值是否唯一。以上的例子都是陈述句，第一。以上的例子都是陈述句，第4 4句的真值现在是假，随着人类科学的发展，句的真值现在是假，随着人类科

13、学的发展，有可能变成真。但不管怎样，真值是唯一的。因此以上例子都是命题。有可能变成真。但不管怎样，真值是唯一的。因此以上例子都是命题。而例如：而例如：1 1、快点走吧！、快点走吧！2 2、到哪去？、到哪去？3 3、X+Y10 X+Y10 等等句子，都不是命题。等等句子，都不是命题。培训专用命题表示公式（命题表示公式（1）如何将陈述句转化成命题公式？如何将陈述句转化成命题公式？例如：设例如：设“下雨下雨”为为p，“骑车上班骑车上班”为为q，1、“只要不下雨，我骑自行车上班只要不下雨，我骑自行车上班”。p是是q的充分条件，因而，可得命题公式：的充分条件，因而，可得命题公式：pq2、“只有不下雨，我

14、才骑自行车上班只有不下雨，我才骑自行车上班”。p是是q必要条件，因而，可得命题公式：必要条件，因而，可得命题公式：qp培训专用命题表示公式（命题表示公式（2）1、“如果我进城我就去看你，除非我很累。如果我进城我就去看你，除非我很累。”设：设：p，我进城；，我进城；q，去看你；，去看你；r，我很累。，我很累。则有命题公式：则有命题公式：r(pq)2、“应届高中生，得过数学或物理竞赛的一等奖，保送上北应届高中生，得过数学或物理竞赛的一等奖，保送上北京大学。京大学。”设：设：p，应届高中生；，应届高中生；p，保送上北京大学；，保送上北京大学；r，得过数，得过数学一等奖；学一等奖；t，得过物理一等奖。

15、，得过物理一等奖。则有命题公式：则有命题公式：p(r t)q培训专用数理逻辑的基本定义数理逻辑的基本定义合取式合取式：p p与与q q，记做，记做 pqpq析取式析取式：p p或或q q，记做，记做 pqpq蕴含式蕴含式：如果：如果p p则则q q，记做，记做 pqpq等价式等价式：p p当且仅当当且仅当q q，记做，记做 pqpq若若A A无成假赋值，则称无成假赋值，则称A A为为重言式重言式或或永真式永真式；若若A A无成真赋值，则称无成真赋值，则称A A为为矛盾式矛盾式或或永假式永假式；若若A A至少有一个成真赋值，则称至少有一个成真赋值，则称A A为可满足的为可满足的；析取范式析取范式

16、：仅由有限个简单合取式组成的析取式：仅由有限个简单合取式组成的析取式合取范式合取范式：仅由有限个简单析取式组成的合取式：仅由有限个简单析取式组成的合取式 培训专用数理逻辑的基本等值式（数理逻辑的基本等值式（24个）个）交换律：交换律：pqqp；pqqp结合律：结合律：(pq)rp(qr);(pq)rp(qr)分配律：分配律：p(qr)(pq)(pr)；p(qr)(pq)(pr)双重否定律：双重否定律：pp等幂律：等幂律：ppp；ppp摩根律摩根律:(pq)pq；(pq)pq吸收律吸收律:p(pq)p；p(pq)p培训专用同一律同一律:p0:p0 p p；p1 p1 p p零律：零律：p1 p1

17、 1 1p0 p0 0 0排中律：排中律：ppp p 1 1矛盾律：矛盾律：ppp p 0 0蕴含等值式：蕴含等值式：pq pq pqpq等价等值式：等价等值式：p pq q (pq)(qp)(pq)(qp)假言易位式假言易位式:pq:pq ppq q 等价否定等值式：等价否定等值式：p pq qp pq q归谬论：归谬论：(pq)(p(pq)(pq)q)p p 培训专用合取范式合取范式合取范式合取范式：单元子句、单元子句的或（：单元子句、单元子句的或（）的与（）的与（）。）。如：如：PP（PQPQ）（PQPQ）例例：求取：求取P(QR)S P(QR)S 的合取范式的合取范式 解解：P(QR)

18、SP(QR)S =（P(P(QR)QR)）SS =PP(QR)SQR)S =P(P(QQR)SR)S =P(QP(QR)SR)S =PS(QPS(QR)R)=(=(PSQ)(PSQ)(PSPSR)R)注意：首先一定要将原有的命题公式整理、转换成为各个注意：首先一定要将原有的命题公式整理、转换成为各个 或或 语句的语句的 与与，不然后续推导没有意义。转换是基于数理逻辑的基本等值，不然后续推导没有意义。转换是基于数理逻辑的基本等值公式进行的，公式进行的，或或 转换到转换到 与与 中。思路与代数学的提取公因式方法相中。思路与代数学的提取公因式方法相似。似。培训专用子句集子句集命题公式的子句集命题公式

19、的子句集S是合取范式形式下的子命题（元素）的是合取范式形式下的子命题（元素）的集合。集合。子句集子句集是合取范式中各个合取分量的集合，生成子句集的过程可是合取范式中各个合取分量的集合，生成子句集的过程可以简单地理解为将命题公式的合取范式中的与符号以简单地理解为将命题公式的合取范式中的与符号“”，置换为，置换为逗号逗号“，”。上例上例转换的合取范式：转换的合取范式：(PSQ)(PSR)其子句集为其子句集为S=PSQ,PSR又如，有命题公式：又如，有命题公式：P（PQ）（PQ）其子句集其子句集S：S=P,PQ,PQ培训专用2.2.2命题逻辑的归结命题逻辑的归结归结法推理的核心是求两个子句的归结式，

20、因此需要先讨论归归结法推理的核心是求两个子句的归结式，因此需要先讨论归结式的定义和性质。结式的定义和性质。归结式的定义归结式的定义 设设C1C1和和C2C2是子句集中的任意两个子句，如果是子句集中的任意两个子句，如果C1C1中的文字中的文字L1L1与与C2C2中的文字中的文字L2L2互补，那么可从互补，那么可从C1C1和和C2C2中分别消去中分别消去L1L1和和L2L2，并将，并将C1C1和和C2C2中余下的部分按析取关系构成一个新子句中余下的部分按析取关系构成一个新子句C12C12，则，则称这一个过程称这一个过程为归结为归结，称，称C12C12为为C1C1和和C2C2的归结式的归结式，称，称

21、C1C1和和C2C2为为C12C12的亲本子句的亲本子句。例如例如：有子句：有子句：C1C1PC1PC1，C2C2PC2PC2存在互补对存在互补对 P P和和P P，则可得归结式：则可得归结式：C12=C1C2 C12=C1C2 注意注意：C1C2 C12 C1C2 C12，反之不一定成立。反之不一定成立。培训专用归结式是原两子句的逻辑推论归结式是原两子句的逻辑推论证明归结式是原两子句的逻辑推论，或者说任一使证明归结式是原两子句的逻辑推论，或者说任一使C1C1、C2C2为真的解为真的解释释I I下必有归结式下必有归结式C12C12也为真。也为真。证明证明：设设I I是使是使C1C1，C2C2为

22、真的任一解释，若为真的任一解释，若I I下的下的P P为真，从而为真，从而P P为假，为假，必有必有I I下下C2C2为真，故为真，故C12C12为真。若不然，在为真。若不然，在I I下下P P为假，从而为假，从而I I下下C1C1为为真，故真，故I I下下C12C12为真。于是为真。于是C1C2C1C2为真。于是为真。于是C1C2R(C1,C2)C1C2R(C1,C2)成立。成立。反之不一定成立，因为存在一个使反之不一定成立，因为存在一个使C1C2C1C2为真的解释为真的解释I I，不妨设，不妨设C1C1为真，为真，C2C2为假。若为假。若P P为真，则为真，则PC2PC2就为假了。因此反之

23、不就为假了。因此反之不一定成立。由此可得归结式的性质。一定成立。由此可得归结式的性质。归结式的性质归结式的性质：归结式：归结式C12 C12 是亲本子句是亲本子句C12 C12 和和C12C12的逻辑结论。的逻辑结论。培训专用命题逻辑的归结法推理过程命题逻辑的归结法推理过程命题逻辑的归结过程也就是推理过程。命题逻辑的归结过程也就是推理过程。推理是根据一定的准则由称推理是根据一定的准则由称为前提条件的一些判断导出称为结论的另一些判断的思维过程。为前提条件的一些判断导出称为结论的另一些判断的思维过程。命题逻辑的归结方法推理过程命题逻辑的归结方法推理过程：1.1.建立待归结命题公式建立待归结命题公式

24、首先根据反证法将所求证的问题转化成为命题公式，求证其是矛首先根据反证法将所求证的问题转化成为命题公式，求证其是矛盾式（永假式）。盾式（永假式）。2.2.求取合取范式求取合取范式3.3.建立子句集建立子句集4.4.归结归结培训专用归结步骤归结步骤归结法是在子句集归结法是在子句集S的基础上通过归结推理规则得到的，归结过程的最的基础上通过归结推理规则得到的，归结过程的最基本单元是得到归结式的过程。从子句集基本单元是得到归结式的过程。从子句集S出发，对出发，对S的子句间使用的子句间使用归结推理规则，并将所得归结式仍放入到归结推理规则，并将所得归结式仍放入到S中（注意：此过程使得中（注意：此过程使得子句

25、集不断扩大，是造成计算爆炸的根本原因），进而再对新子句集使子句集不断扩大，是造成计算爆炸的根本原因），进而再对新子句集使用归结推理规则。重复使用这些规则直到得到空子句用归结推理规则。重复使用这些规则直到得到空子句。这便说明。这便说明S是是不可满足的，从而与不可满足的，从而与S所对应的定理是成立的。所对应的定理是成立的。归结步骤：归结步骤：1)对子句集中的子句使用归结规则对子句集中的子句使用归结规则2)归结式作为新子句加入子句集参加归结归结式作为新子句加入子句集参加归结3)归结式为空子句归结式为空子句为止。为止。（证明完毕）（证明完毕）得到空子句得到空子句，表示，表示S是不可满足的（矛盾），故原

26、命题成立。是不可满足的（矛盾），故原命题成立。培训专用例题例题2-1:证明公式：证明公式：(PQ)(QP)证明证明:(1)根据归结原理根据归结原理,将待证明公式转化成待归结命题公式：将待证明公式转化成待归结命题公式：(PQ)(QP)(2)分别将公式前项化为合取范式：分别将公式前项化为合取范式：PQPQ结论求后的后项化为合取范式：结论求后的后项化为合取范式：(QP)(QP)QP两项合并后化为合取范式：（两项合并后化为合取范式：（PQ）QP(3)则子句集为：则子句集为：PQ，Q，P(4)对子句集中的子句进行归结可得：对子句集中的子句进行归结可得：1.PQ2.Q 3.P4.Q （1，3归结）归结）5

27、.（2，4归结）归结）由上可得原公式成立。由上可得原公式成立。培训专用2.3 谓词逻辑归结法基础谓词逻辑归结法基础由于谓词逻辑与命题逻辑不同，有量词、变由于谓词逻辑与命题逻辑不同，有量词、变量和函数，所以在生成子句集之前要对逻辑量和函数，所以在生成子句集之前要对逻辑公式做处理，具体的说就是要将其转化为公式做处理，具体的说就是要将其转化为Skolem标准形，然后在子句集的基础上再标准形，然后在子句集的基础上再进行归结，虽然基本的归结的基本方法都相进行归结，虽然基本的归结的基本方法都相同，但是其过程较之命题公式的归结过程要同，但是其过程较之命题公式的归结过程要复杂得多。复杂得多。本节针对谓词逻辑归

28、结法介绍本节针对谓词逻辑归结法介绍Skolem标准标准形、子句集等一些必要的概念和定理。形、子句集等一些必要的概念和定理。培训专用前束范式前束范式前束范式：前束范式：A是一个前束范式，如果是一个前束范式，如果A中的一切量词都位于该公中的一切量词都位于该公式的最左边（不含否定词），且这些量词的辖域都延伸到公式的末式的最左边（不含否定词），且这些量词的辖域都延伸到公式的末端。端。前束范式前束范式A A的形式为：的形式为：(Q1x1)(Q2x2)(Qnxn)M(x1,x2,xn)即：即：把所有的量词都提到前面去。把所有的量词都提到前面去。注意：注意：由于所有的量词的辖域都延伸到公式的末端，即，最左边

29、由于所有的量词的辖域都延伸到公式的末端，即，最左边量词将约束表达式中的所有同名变量。所以将量词提到公式最前量词将约束表达式中的所有同名变量。所以将量词提到公式最前端时存在约束变量换名问题。要严守规则。端时存在约束变量换名问题。要严守规则。培训专用约束变量换名规则：约束变量换名规则：(Qx)M（x）（Qy）M（y）(Qx)M（x,z）（Qy）M（y,z）量词否定等值式：量词否定等值式：(x)M（x）（y）M（y）(x)M（x）（y）M（y）量词分配等值式：量词分配等值式：(x)(P（x）Q（x）)(x)P（x）(x)Q（x）(x)(P（x）Q（x）)(x)P（x）(x)Q（x）消去量词等值式：设

30、个体域为有穷集合（消去量词等值式：设个体域为有穷集合（a1,a2,an）(x)P（x）P（a1）P（a2）P（an）(x)P（x）P（a1）P（a2）P（an）量词辖域收缩与扩张等值式：量词辖域收缩与扩张等值式：(x)(P（x）Q)(x)P（x）Q(x)(P（x）Q)(x)P（x）Q(x)(P（x）Q)(x)P（x）Q(x)(Q P（x）)Q (x)P（x）(x)(P（x）Q)(x)P（x）Q(x)(P（x）Q)(x)P（x）Q(x)(P（x）Q)(x)P（x）Q(x)(Q P（x）)Q (x)P（x）培训专用2.3.1 Skolem 标准形标准形Skolem标准形的定义：标准形的定义：前束范

31、式中消去所有的存在量词，则称这种形前束范式中消去所有的存在量词，则称这种形式的谓词公式为式的谓词公式为Skolem标准形。标准形。注意：注意：公式公式G的的SKOLEM标准形同标准形同G并不等值。并不等值。Skolem 定理：定理：谓词逻辑的任意公式都可以化为与之等价的前束范式，谓词逻辑的任意公式都可以化为与之等价的前束范式，但其前束范式不唯一。但其前束范式不唯一。Skolem标准形的转化过程为，依据约束变量换名规则，标准形的转化过程为，依据约束变量换名规则，首先把公式变型为前束范式，然后依照量词消去原则首先把公式变型为前束范式，然后依照量词消去原则消去或者略去所有量词消去或者略去所有量词。培

32、训专用消去量词消去量词量词消去原则量词消去原则：1)消去存在量词消去存在量词“”。即，将该量词约束的变量用。即，将该量词约束的变量用任意常量（任意常量（a,b等）、或全称变量的函数等）、或全称变量的函数(f(x),g(y)等等)代替。如果存在量词左边没有任何全称量词，则只将其代替。如果存在量词左边没有任何全称量词，则只将其改写成为常量；如果是左边有全程量词的存在量词，消改写成为常量；如果是左边有全程量词的存在量词，消去时该变量改写成为全程量词的函数。去时该变量改写成为全程量词的函数。2)略去全程量词略去全程量词“”。简单地省略掉该量词。简单地省略掉该量词。培训专用例题例题2-2：将下式化为将下

33、式化为Skolem标准形：标准形：(x)(y)P(a,x,y)(x)(y)Q(y,b)R(x)解：解：第一步，消去第一步，消去号，得：号，得：(x)(y)P(a,x,y)(x)(y)Q(y,b)R(x)第二步，深入到量词内部，得：第二步，深入到量词内部，得：(x)(y)P(a,x,y)(x)(y)Q(y,b)R(x)(x)(y)P(a,x,y)(x)(y)Q(y,b)R(x)第三步，全称量词左移，（利用分配律），得第三步，全称量词左移，（利用分配律），得(x)(y)P(a,x,y)(y)(Q(y,b)R(x)第四步，变元易名，存在量词左移，直至所有的量词移到前面，得：第四步，变元易名，存在量词

34、左移，直至所有的量词移到前面，得：(x)(y)P(a,x,y)(y)(Q(y,b)R(x)(x)(y)P(a,x,y)(z)(Q(z,b)R(x)=(x)(y)(z)(P(a,x,y)Q(z,b)R(x)由此得到前述范式。由此得到前述范式。培训专用第五步，消去第五步，消去“”，略去，略去“”消去消去(y)，因为它左边只有因为它左边只有(x)，所以使用所以使用x的函数的函数f(x)代替之，这样得到：代替之，这样得到：(x)(z)(P(a,x,f(x)Q(z,b)R(x)消去消去(z)，同理使用同理使用g(x)代替之，这样得到：代替之，这样得到：(x)(P(a,x,f(x)Q(g(x),b)R(x

35、)则，略去全称变量，原式的则，略去全称变量，原式的Skolem标准形为：标准形为：P(a,x,f(x)Q(g(x),b)R(x)培训专用2.3.2子句集子句集文字：不含任何连接词的谓词公式。文字：不含任何连接词的谓词公式。子句：一些文字的析取（谓词的和）。子句：一些文字的析取（谓词的和）。子句集：所有子句的集合。子句集：所有子句的集合。对于任一个公式对于任一个公式G，都可以通过都可以通过Skolem标准形，标准标准形，标准化建立起一个子句集与之相对应。因为子句不过是一化建立起一个子句集与之相对应。因为子句不过是一些文字的析取，是一种比较简单的形式，所以对些文字的析取，是一种比较简单的形式，所以

36、对G的的讨论就用对子句集讨论就用对子句集S的讨论来代替，以便容易处理。的讨论来代替，以便容易处理。培训专用子句集子句集S的求取的求取子句集子句集S可由下面的步骤求取：可由下面的步骤求取：1.谓词公式谓词公式G转换成前束范式转换成前束范式2.消去前束范式中的存在变量，略去其中的任意变消去前束范式中的存在变量，略去其中的任意变量，生成量，生成SKOLEM标准形标准形3.将将SKOLEM标准形中的各个子句提出，表示为集标准形中的各个子句提出，表示为集合形式。合形式。教师提示：教师提示：为了简单起见，子句集生成可以理解为是用为了简单起见，子句集生成可以理解为是用“，”取代取代SKOLEM标准形中的标准

37、形中的“”，并表示为集合形并表示为集合形式式。注意：注意：SKOLEM标准形必须满足合取范式的条件。即，标准形必须满足合取范式的条件。即，在生成子句集之前逻辑表达式必须是各在生成子句集之前逻辑表达式必须是各谓词表达式谓词表达式或或谓词或表达式谓词或表达式的与。的与。培训专用定理定理：谓词表达式谓词表达式G是不可满足的，当且仅当是不可满足的，当且仅当 其子句集其子句集S是不可满足的。是不可满足的。G与与S并不等值，但它们在不可满足的意义下是一致的。并不等值，但它们在不可满足的意义下是一致的。因此如果要证明因此如果要证明 A1A2A3B，只需证明只需证明 G A1A2A3B 的子句集的子句集S S

38、是不可满足的。是不可满足的。注意：注意：G真不一定真不一定S真，而真，而S真必有真必有G真，真，即：即：S G。因为：因为：在生成在生成SKOLEM标准形时将存在量词用常量或其他变量的函数标准形时将存在量词用常量或其他变量的函数代替，使得变量讨论的论域发生了变化，即论域变小了。所以代替，使得变量讨论的论域发生了变化，即论域变小了。所以G不能不能保证保证S真。真。培训专用谓词归结子句形谓词归结子句形G=G1 G2 G3 Gn 的子句形的子句形G的子句集的求取过程可以分解成几个部分单独处理。的子句集的求取过程可以分解成几个部分单独处理。如果如果Gi的子句集为的子句集为Si，则则有有 S=S1 S2

39、 S3 Sn，虽然虽然G的子句集不的子句集不为为S，但是可以证明：但是可以证明：SG 与与S1 S2 S3 Sn在不可满足的意义上是在不可满足的意义上是一致的。一致的。即即SG 不可满足不可满足S1 S2 S3 Sn不可满足不可满足由上面的定理，我们对由上面的定理，我们对SG的讨论，可以用较为简单的的讨论，可以用较为简单的S1 S2 S3 Sn来代替。为方便起见，也称来代替。为方便起见，也称S1 S2 S3 Sn为为G的子句形，即：的子句形，即：SGS1 S2 S3 Sn。培训专用求取子句集的例子（求取子句集的例子（1）例例23：对所有的对所有的x,y,z来说，如果来说，如果y是是x的父亲，的

40、父亲，z又是又是y的父亲，则的父亲，则z是是x的祖父。又知每个人都有父亲，试问对的祖父。又知每个人都有父亲，试问对某个人来说谁是它的祖父？某个人来说谁是它的祖父？求：用一阶逻辑表示这个问题，并建立子句集。求：用一阶逻辑表示这个问题，并建立子句集。解：解：这里我们首先引入谓词：这里我们首先引入谓词：P(x,y)表示表示x是是y的父亲的父亲Q(x,y)表示表示x是是y的祖父的祖父ANS(x)表示问题的解答表示问题的解答培训专用求取子句集的例子（求取子句集的例子（2）对于第一个条件，对于第一个条件，“如果如果y是是x的父亲，的父亲，z又是又是y的父亲，则的父亲，则z是是x的的祖父祖父”，一阶逻辑表达

41、式如下：，一阶逻辑表达式如下：A1：(x)(y)(z)(P(x,y)P(y,z)Q(x,z)S A1：P(x,y)P(y,z)Q(x,z)对于第二个条件：对于第二个条件：“每个人都有父亲每个人都有父亲”，一阶逻辑表达式如下：，一阶逻辑表达式如下：A2：(y)(x)P(x,y)S A2：P(f(y),x)对于结论：某个人是它的祖父对于结论：某个人是它的祖父B：(x)(y)Q(x,y)否定后得到子句：否定后得到子句：SB：Q(x,y)ANS(x)则得到的相应的子句集为：则得到的相应的子句集为：S A1，S A2，SB 培训专用2.4归结原理归结原理本节在上节的基础上，进一步具体介绍谓词逻辑的归结方

42、法。谓词本节在上节的基础上，进一步具体介绍谓词逻辑的归结方法。谓词逻辑的归结法是以命题逻辑的归结法为基础，在逻辑的归结法是以命题逻辑的归结法为基础，在Skolem标准形的子标准形的子句集上，通过置换和合一进行归结的。句集上，通过置换和合一进行归结的。基本概念基本概念：一阶逻辑一阶逻辑：谓词中不再含有谓词的逻辑关系式。：谓词中不再含有谓词的逻辑关系式。个体词个体词：表示主语或宾语的词：表示主语或宾语的词谓词谓词：刻画个体性质或个体之间关系的词：刻画个体性质或个体之间关系的词量词量词：表示数量的词：表示数量的词个体常量个体常量：a，b，c个体变量个体变量：x，y，z谓词符号谓词符号：P，Q，R量词

43、符号量词符号：，培训专用培训专用培训专用培训专用2.4.1合一和置换合一和置换置换可以简单的理解为是在一个谓词公式中用置换项去置换变量。置换可以简单的理解为是在一个谓词公式中用置换项去置换变量。定义定义：置换置换是形如是形如 t t1 1/v/vl l,t,tn n/v/vn n 的一个有限集。其中的一个有限集。其中v vi i是变量而是变量而t ti i是不是不同于同于v vi i的项的项(常量、变量、函数常量、变量、函数),),且且 v vi ivvj j (ij),i,j=1,2,n(ij),i,j=1,2,n例如例如a/x，c/y，f(b)/z是一个置换。是一个置换。g(y)/x，f(

44、x)/y不是一个置换不是一个置换。（原因是它在原因是它在x和和y之间出现了循环置换现象。之间出现了循环置换现象。）不含任何元素的置换为不含任何元素的置换为空置换空置换,以以表示。表示。置置换换可可作作用用于于某某个个谓谓词词公公式式上上,也也可可作作用用于于某某个个项项上上。置置换换作作用用于于一一谓谓词词公公式式E,E,结结果果以以EE表示表示,并并称为称为E E的一个例。的一个例。作用于项作用于项t,t,结果以结果以tt表示。表示。培训专用定义：置换的乘法（合成）定义：置换的乘法（合成）设设=t1/xl,tn/xn，=u1/y1,um/ym，是两个置换。，是两个置换。则则与与的乘法（合成）

45、也是一个置换，记作的乘法（合成）也是一个置换，记作。它是。它是从集合从集合t1/xl,tn/xn，u1/y1,um/ym中删去以下两种元素：中删去以下两种元素：i.当当ti=xi时，从中删除时，从中删除ti/xi(i=1,2,n);ii.当当yix1,xn时，从中删除时，从中删除ui/yi(i=1,2,m)最后剩下的元素所构成的集合。最后剩下的元素所构成的集合。合成即是对合成即是对ti先做先做置换然后再做置换然后再做置换，置换置换，置换xi。培训专用置换的合成置换的合成例：例：设设：f(y)/x,z/y，a/x,b/y,y/z，求，求与与的合成。的合成。解解：先求出集合：先求出集合f(b/y)

46、/x,(y/z)/y,a/x,b/y,y/zf(b)/x,y/y,a/x,b/y,y/z其中，其中，f(b)/x中的中的f(b)是置换是置换作用于作用于f(y)的结果；的结果；y/y中的中的y是置换是置换作作用于用于z的结果。在该集合中，的结果。在该集合中，y/y满足定义中的条件满足定义中的条件i，需要删除；，需要删除；a/x，b/y满足定义中的条件满足定义中的条件ii，也需要删除。，也需要删除。最后得最后得f(b)/x，y/z培训专用合合一一合一：合一可以简单地理解为合一：合一可以简单地理解为“寻找相应变量的置换，使两个谓词寻找相应变量的置换，使两个谓词公式一致公式一致”。定义：设有公式集定

47、义：设有公式集E E E1 1,E,Ek k，若存在一个置换，若存在一个置换，可使，可使E E1 1=E=E2 2=E=Ek k，则，则称称是是E的一个合一的一个合一。同时称。同时称E E1 1,E,Ek k是是可合可合一的。一的。例：例：设有公式集设有公式集FP(x,y,f(y),P(a,g(x),z)，则则a/x,g(a)/y,f(g(a)/z是它的一个合一。是它的一个合一。注意：一般说来，一个公式集的合一不是唯一的。注意：一般说来，一个公式集的合一不是唯一的。培训专用最一般合一最一般合一定义：最一般合一定义：最一般合一设设是公式集是公式集E E1 1,E,Ek k的一个合一置换，如果对的

48、一个合一置换，如果对E E的任意一个合一的任意一个合一都都存在一个置换存在一个置换，使得，使得 ，则称则称是是E E1 1,E,Ek k的最一般合一的最一般合一（Most General UnifierMost General Unifier，简记，简记为为mgumgu）换句话来说，其他任何合一置换换句话来说，其他任何合一置换都是都是与某个置换与某个置换的合成。的合成。一个公式集的最一般合一是唯一的。若用最一般合一去置换一个公式集的最一般合一是唯一的。若用最一般合一去置换那些可合一的谓词公式，可使它们变成完全一致的谓词公式。那些可合一的谓词公式，可使它们变成完全一致的谓词公式。归结原理方法与命

49、题逻辑基本相同。但由于有变量与函数，所归结原理方法与命题逻辑基本相同。但由于有变量与函数，所以要考虑合一和置换。以要考虑合一和置换。培训专用2.4.2归结式归结式在谓词逻辑下求两个子句的归结式，和命题逻辑一样是消互补对，在谓词逻辑下求两个子句的归结式，和命题逻辑一样是消互补对，但需考虑变量的合一与置换。但需考虑变量的合一与置换。设设C1,C2是是两两个个无无公公共共变变量量的的子子句句，L1、L2分分别别是是C1、C2的的文文字字，如果如果Ll与与L2有有mgu，则则(C1-L1)(C2-L2)称作子句称作子句C1、C2的一个二元归结式的一个二元归结式，而，而L1、L2为被归结的文字。为被归结

50、的文字。子句因子子句因子：如果一个子句：如果一个子句C的几个文字有的几个文字有mgu，那么那么C的例的例C称称作子句的因子（进行作子句的因子（进行子句内部的化简子句内部的化简）。）。培训专用归结式的注意事项归结式的注意事项1、谓词的一致性，、谓词的一致性，P()与与Q()，不可以归结。不可以归结。2、常量的一致性，、常量的一致性，P(a,)与与P(b,.)，不可以归结。不可以归结。3、变量，、变量，P(a,.)与与P(x,)，可以通过置换归结。可以通过置换归结。4、变量与函数，、变量与函数，P(a,x,.)与与P(x,f(x),)，不可以归结；，不可以归结；但但P(a,x,)与与P(x,f(y