人工智能392.pptx
《人工智能392.pptx》由会员分享，可在线阅读，更多相关《人工智能392.pptx（92页珍藏版）》请在冰点文库上搜索。
第三章确定性推理,3.1基本概念3.3自然演绎推理3.4归结演绎推理3.5基于规则的演绎推理（与/或形演绎推理）,3.1基本概念,为使计算机具有智能，仅仅使它拥有知识还不够，更重要地，还必须使它具有思维能力，即能运用知识进行推理、求解问题的能力。
知识表示（知识库）求解过程（推理）经典推理是根据经典逻辑（命题逻辑和一阶谓词逻辑）的逻辑规则进行的一种推理，又称机械-自动定理证明。
主要推理方法有：
自然演绎推理、归结演绎推理、基于规则的演绎推理（与/或形演绎推理）。
基本概念,推理推理是按某种策略由已知判断推出另一种判断的过程。
在AI系统中，推理是由程序来实现的，称为推理机。
不同的控制策略推理方式及分类：
演绎推理,由一般（全称判断）到个别（特称判断）的推理方法。
核心是三段论，通常由一个大前提、一个小前提和一个结论三部分组成的。
例：
阿凡提的故事-两头驴的故事我肩上驮的是两头驴的东西（大前提）国王和大臣的衣衫是我肩上驮的（小前提）国王和大臣的衣衫是两头驴的东西（结论）,归纳推理,从个别到一般归纳结论不具备逻辑必然性莫里斯科恩逻辑学著作包括两部分，第一部分是演绎，其功能是解释谬误；第二部分是归纳，其功能是生成谬误,我们获得关于这个实在世界的一般性事实的唯一方法！
演绎推理所得出的结论蕴含在一般性知识的前提中，演绎推理只不过是将已有事实揭示出来，因此它不能增殖新知识。
在归纳推理中，所推出的结论是没有包含在前提内容中的。
这种由个别事物或现象推出一般性知识的过程，是增殖新知识的过程。
默认推理,默认推理是在知识不完全的情况下假设某些条件已经具备所进行的推理，也称为缺省推理。
在推理过程中，如果发现原先的假设不正确，就撤消原来的假设以及由此假设所推出的所有结论，重新按新情况进行推理。
由于默认推理允许在推理过程中假设某些条件是成立的，因此解决了在一个不完备的知识集中进行推理的问题。
封闭世界假设：
如果没有足够的证据证明某命题不成立，就假定该命题成立,推理的控制策略推理过程涉及到求解方法和求解策略。
求解方法包括匹配方法、不确定性的传递方法求解策略包括推理方向、求解策略、限制策略等。
指推理是求一个解、所有解，还是最优解。
为防止无穷的推理过程，以及由此带来的时间和空间复杂性，限制策略是对推理的深度、宽度、时间、空间等进行限制。
推理方向推理方向分为正向推理、逆向推理、混合推理、双向推理四种。
无论哪一种推理，系统都具有知识库、数据库和推理机。
正向推理需要解决的问题：
1、确定匹配的方法2、确定搜索策略3、消解冲突正向推理的缺点：
盲目，效率低,逆向推理的优点：
1、目标性强2、有利于向用户提供解释逆向推理的缺点：
初始目标的选择有盲目性,逆向推理-例,有关知识规则1：
IF你丢了自行车钥匙，并且车胎没气THEN自行车不能骑规则2：
IF自行车不能骑，并且你只有走路去THEN你听课会迟到事实1：
你丢了自行车钥匙事实2：
车胎没气问题“你听课会迟到？
”,逆向推理-例,1.首先查找知识库，知该假设不是已有事实，但可由规则2导出，于是将规则2放入可用知识集，并将其两个前提条件“自行车不能骑”和“你只有走路去”都作为新的假设放入假设集。
2.从假设集中取出假设“自行车不能骑”，它不是已有事实，但可由规则1导出，于是规则1被放入可用知识集，并将其两个前提条件“你丢了自行车钥匙”和“车胎没气”也作为新的假设放入假设集。
3.从假设集中取出假设“你只有走路去”，此假设既不是已有事实，也不能被任何一条规则导出，询问用户“你只有走路去吗？
”，若用户回答“是”，则该假设成立，并被放入已有事实集。
4.假设集中还有两个假设“你丢了自行车钥匙”和“车胎没气”，它们都是已有事实，均为真。
继续推理，假设集为空，推理过程结束，“你听课会迟到”得证。
混合推理是把正向推理和逆向推理结合起来，吸取两种推理的优点。
它通常适用以下3种情况：
（1）已知事实不充分
（2）由正向推理推出的可信度不高（3）希望得到更多的结论混合推理有两种方式：
先正后逆和先逆后正,双向推理是指正向推理和逆向推理同时进行，在推理过程的某步碰头。
基本思想双向推理的难点是碰头的判定。
模式匹配,模式匹配是指对两个知识模式（如两个谓词公式、框架或语义片段等）的比较与藕合，即检查这两个知识模式是否完全一致或近似一致。
按匹配的近似程度划分，可分为确定性匹配和不确定性匹配。
确定性匹配是指两个知识模式完全一致，或经过变量代换后变得完全一致。
例如：
不确定性匹配是指两个知识模式不完全一致，但总体上它们的相似度在一定的限度内。
定义3.1置换（代换）,代换是形如的有限集合。
其中是项是互不相同的变元；表示用代换，不允许与相同，也不允许变元循环地出现在另一个中。
根据定义,是代换,不是代换,是代换,设有代换a/x,f（b）/y,u/z则对公式EP（x,y,z）有EP（a,f（b）,u）,对公式E运用代换s，记作Es。
Es称作公式E在代换s下的例（例示），它是E的逻辑结论。
设是两个代换，则此两个代换的复合也是一个代换，它是从删除以下两种元素后剩下的元素所构成的集合，记作,定义3.2代换的复合,例如：
则,解释：
就是对一个公式先运用代换，然后再运用代换.,大家验证一下！
定义3.3公式集的合一设有公式集，若存在一个代换使得则称是公式集的一个合一，且称是可合一的。
一个公式集的合一一般来说不是唯一的例如公式集有合一,定义3.4最一般合一设是公式集的一个合一，如果对任一个合一都存在一个代换，使得则称是公式集的一个最一般合一。
如前面提到的公式集是最一般合一，而则不是最一般合一。
按照最一般合一的定义，有：
因此，对于一个公式集来说，如果存在多个合一，则其中代换数最少、限制最少、产生的例最具一般性的代换称为最一般合一。
如：
一般来说，最一般合一也不是唯一的，同样是该公式集的一个最一般合一。
求最一般合一差异集：
求最一般合一算法：
（1）令。
这里，是欲求最一般合一的公式集，是空代换，它表示不做代换。
（2）若只含一个表达式，则算法停止，就是最一般合一。
（3）找出的差异集。
（4）若中存在元素和，其中是变元，是项，且不在中出现，则置：
然后转向
（2）。
（5）算法终止，的最一般合一不存在。
举例：
求的最一般合一。
消解冲突策略,在推理过程中，系统要不断地用当前已知事实与知识库中的知识进行匹配，此时可能发生以下三种情况：
（1）已知事实不能与知识库中的任何知识匹配
（2）已知事实恰好与知识库中的一条知识匹配（3）已知事实可与知识库中的多条知识匹配，或者多组已知事实可与知识库中的某一条知识匹配，或者多组已知事实可与知识库中的多条知识匹配。
处于第三种情况时，就发生冲突。
此时需要按一定的消解策略解决冲突。
冲突：
多个知识都匹配成功。
冲突消解的基本思想都是对知识进行排序。
对于产生式系统，若出现以下情况就认为发生冲突：
（1）对正向推理而言，如果有多条产生式规则的前件都和已知事实匹配，或者有多组已知事实都与同一条产生式规则的前件匹配；或者以上两种情况同时出现。
（2）对逆向推理而言，如果有多条产生式规则的后件都和同一假设匹配，或者有多条产生式规则的后件可与多个假设匹配。
常用的消解冲突策略：
1、按针对性排序设有如下两条产生式规则：
如果存在最一般合一，使得r1中的每个Ai都可以变成相应的Bi，如Ai=P（x,y），Bi=P（a,z）,则称r2比r1有更大的针对性，r1比r2有更大的通用性。
该策略选用针对性较强的产生式规则。
2、按已知事实的新鲜性排序把数据库中后生成的事实称为新鲜的事实，该策略要求具有最大新鲜性的事实总是排在前面。
设规则r1可与事实组A匹配成功，规则r2可与事实组B匹配成功，则A和B哪一组中的事实更新鲜，与它匹配的规则就先被利用。
如何衡量A和B哪一组中的事实更新鲜呢？
3、按匹配度排序4、根据领域问题的特点排序先验知识、启发式知识5、按上下文限制排序把规则按照下上文分组，并只能选取组中的规则。
6、按冗余限制排序冗余知识少的规则先推。
7、按条件个数排序条件少的规则先推。
尽量减少冲突的发生，使推理具有较高的效率,3.3自然演绎推理,自然演绎推理就是从一组已知为真的事实出发，直接运用经典逻辑的推理规则推出结论的过程。
推理规则包括：
1、假言推理2、拒取式推理3、P规则：
在推理的任何步骤都可引入前提4、T规则：
推理时，如果前面步骤有一个或多个公式永真蕴含公式S（逻辑结论），则可把公式S引入推理过程中。
例3.1已知下述事实：
A，B，AC，BCD，DQ求证：
Q为真,证明：
A，ACCP规则及假言推理B，CBC合取BC，BCDDT规则及假言推理D，DQQT规则及假言推理,思考题：
所有人都是必死的；苏格拉底是人；求证：
苏格拉底是必死的。
自然演绎推理的优点：
表达定理证明过程自然，容易理解，而且拥有丰富的推理规则，推理过程灵活，便于在它的推理规则中嵌入领域启发式知识。
自然演绎推理的缺点：
容易产生组合爆炸中间结论呈指数级增长。
3.4归结演绎推理,要证明PQ永真，需要证明它在任何个体域上所有可能的解释都是永真的，这是难以实现的。
采用反证法的思想，只要证明PQ永假（不可满足）即可。
这是因为：
PQPQ（PQ）PQ,海伯伦（Herbrand）和鲁宾逊（Robinson）在这个方向上先后作了卓越的研究工作。
首先，由海伯伦提出的H域（海伯伦域）和海伯伦定理，为自动定理证明奠定了理论基础；然后，由鲁宾逊提出的归结原理（消解原理）则使机器定理证明成为可能。
子句：
在谓词公式中，把原子谓词公式及其否定统称为文字。
例如：
P（x,y）和Q（x）都是文字。
定义任何文字的析取式称为子句。
例如：
P（x,y）Q（x）是子句；P（x,y）（Q（x）R（y）不是子句。
定义不包含任何文字的子句称为空子句，简记为NIL。
空子句是永假的，是不可满足的。
子句的集合称为子句集。
在谓词逻辑中，谓词公式可以通过等价关系及推理规则化成相应的子句集。
把谓词公式转化为子句集的步骤：
（1）消去蕴涵符号
（2）内移否定符号（3）对变元更名：
使不同量词约束的变元不同名（4）消去存在量词：
个体常量、Skolem函数代换（5）全称量词前束化（6）化为Skolem标准型：
合取范式（7）消去全称量词（8）对变元更名：
使不同子句中的变元不同名（9）消去合取词：
子句集,例如：
（x）（y）P（x,y）（y）（Q（x,y）R（x,y）（x）（y）P（x,y）（y）（Q（x,y）R（x,y）
（2）（x）（y）P（x,y）（y）（Q（x,y）R（x,y）（3）（x）（y）P（x,y）（z）（Q（x,z）R（x,z）（4）（x）（P（x,f（x）（Q（x,g（x）R（x,g（x）（5）全称量词已经前束化（6）（x）（P（x,f（x）Q（x,g（x）（P（x,f（x）R（x,g（x）（7）（P（x,f（x）Q（x,g（x）（P（x,f（x）R（x,g（x）（8）（P（x,f（x）（Q（x,g（x）（P（y,f（y）R（y,g（y）（9）P（x,f（x）Q（x,g（x）,P（y,f（y）R（y,g（y）,例1：
求谓词公式G=xyz（P（x,y）R（x,y,z）（Q（x,z）R（x,y,z）的子句集。
解：
已经是前束范式，并且不含连接词。
由于存在量词y,z都在全称量词x的辖域中，所以将y,z分别用Skolem函数f（x）、g（x）代替。
x（P（x,f（x）R（x,f（x）,g（x）（Q（x,g（x）R（x,f（x）,g（x）该谓词公式已经是合取范式了，消去全称量词、对变元更名、消去合取词，得到谓词公式G的子句集是P（x,f（x）R（x,f（x）,g（x），Q（y,g（y）R（y,f（y）,g（y）,例2：
求谓词公式的子句集:
x（yP（x,y）y（Q（x,y）R（x,y）解：
x（yP（x,y）y（Q（x,y）R（x,y）=x（yP（x,y）y（Q（x,y）R（x,y）=x（yP（x,y）y（Q（x,y）R（x,y）=x（yP（x,y）z（Q（x,z）R（x,z）=x（P（x,f（x）（Q（x,g（x）R（x,g（x）=x（P（x,f（x）Q（x,g（x）（P（x,f（x）R（x,g（x）从而该谓词公式的子句集是P（x,f（x）（Q（x,g（x），P（y,f（y）R（y,g（y）,转化要点：
1、第一步应先消去蕴涵符号，再内移否定符号等其它工作；2、先内移否定符号，再消去量词；3、先消存在量词，再消全称量词。
定理3.1设有谓词公式F，其标准形的子句集为S，则F不可满足的充要条件是S不可满足。
（注意：
F和S并不等价！
存在量词消去、变元更名）因此，要想证明F不可满足，只需证明S不可满足即可，鲁滨逊提出的归结原理就是用来解决这一问题的。
鲁宾逊归结原理为提高判定子句集不可满足的有效性，鲁宾逊于1965年提出了归结（Resolution）原理，也称为消解原理。
由谓词转化子句集的过程可以看出，在子句集中各子句之间是合取关系，其中只要有一个子句不可满足，则子句集就不可满足。
空子句是不可满足的，若一个子句集含有一个空子句（该子句集中有矛盾），子句集一定是不可满足的。
鲁宾逊归结原理的基本是：
检查子句集S是否包含空子句，若包含，则S不可满足；若不包含，就在子句集中选择合适的子句进行归结，一旦通过归结推出空子句，就说明子句集S是不可满足的。
定义3.18若P是原子谓词公式，则称P和P为互补文字。
命题逻辑中归结原理设C1和C2是子句集中任意二个子句，如果C1中的文字L1和C2中的文字L2互补，那么从C1和C2中分别消去L1和L2，并对C1和C2的剩余部分析取，构成一个新的子句C12，则称这一过程为归结，称C12为C1和C2的归结式，C1和C2是C12的亲本子句。
例：
C1=PQ，C2=QR，C3=PC12=PR，C123=R,定理3.2归结式C12是其亲本子句C1和C2的逻辑结论，即：
C1C2C12如何证明？
推论1：
设C1和C2是子句集S中的两个子句，C12是它们的归结式，若用C12代替C1和C2后得到新子句集S1，则S1的不可满足性S的不可满足性推论2：
设C1和C2是子句集S中的两个子句，C12是它们的归结式，若用C12加入S中后，得到新子句集S1，则S1的不可满足性S的不可满足性,谓词逻辑中的归结原理在谓词逻辑情况下，由于子句中含有变量，不能像命题逻辑那样直接发现和消去互补文字，往往需对潜在的互补文字先作变量代换和合一处理，才能用于归结。
例如有如下两个子句：
C1=P（x）Q（x）C2=P（a）R（y）用最一般合一=a/x对两个子句分别进行代换：
C1=P（a）Q（a）C2=P（a）R（y）可得归结式：
Q（a）R（y）若C2=P（a）R（x）又该如何？
定义3.20设C1和C2是两个没有相同变元的子句，L1和L2分别是C1和C2中的文字，若是L1和L2的最一般合一，则称C12=（C1-L1）（C2-L2）是C1和C2的二元归结式，L1和L2称为归结式上的文字。
如果在参加归结的子句内部含有可合一的文字，则在进行归结前应对这些文字先进行合一。
例如：
C1=P（x）P（f（a）Q（x）C2=P（y）R（b）C1中P（x）和P（f（a）可合一，用其最一般合一=f（a）/x进行代换，得：
C1=P（f（a）Q（f（a）C1和C2归结得C12=Q（f（a）R（b）注意：
这样多做了一次代换，相当于对C1做了更严格的限制，有可能存在归结不出结果的可能性。
一般来说：
若子句C中有两个或两个以上的文字具有最一般的合一，则称C为子句C的因子。
如果C是一个单文字，则称为单因子。
定义3.21子句C1和C2的归结式是下列二元归结式之一：
（1）C1和C2的二元归结式；
（2）C1和C2的因子C22的二元归结式；（3）C1的因子C11和C2的二元归结式；（4）C1的因子C11和C2的因子C22的二元归结式。
对于谓词逻辑，定理3.2仍然适用。
归结演绎的完备性从不可满足的意义上说，基于归结的演绎方法是完备的，即若子句集S不可满足，就必定存在一个从S到空子句的归结演绎；反之，若存在一个从S到空子句的归结演绎，则S必定是不可满足的。
关于归结演绎的完备性可用海伯伦定理进行证明，因此从这个意义上讲，归结原理是建立在海伯伦定理之上的。
不过归结原理并不能用于解决子句集不可满足性的不可判定问题，即对于永真和可满足的子句集，判定过程将无休止地进行下去，得不到任何结果。
归结反演证明Q是P1，P2Pn的逻辑结论，即：
P1P2PnQ只需证明（P1P2PnQ）是不可满足的。
因为（P1P2PnQ）（P1P2Pn）Q）（P1P2Pn）Q只需证明子句集P1，P2，Pn，Q是不可满足的。
对子句集中的子句相互归结，直到归结出空子句，这个过程就是归结反演。
设F为已知前提的公式集，Q为目标公式，用归结反演证明Q为真的步骤：
（1）否定Q，得到Q；
（2）把Q并入到公式集F中，得到F，Q；（3）把公式集F，Q化为子句集S（P126127）；（4）应用归结原理对子句集S中的子句进行归结，并把每次得到的归结式放入S中。
如此反复，若出现空子句，就停止归结，此时就证明了Q为真。
例1:
求证:
G是A1和A2的逻辑结论A1:
x（P（x）（Q（x）R（x）A2:
x（P（x）S（x）G:
x（S（x）R（x）证:
P（x）Q（x）.从A1变换P（y）R（y）.从A1变换P（a）.从A2变换S（a）.从A2变换S（z）R（z）.结论的否定R（a）.归结a/yR（a）.归结a/zNIL.归结得证.,例2:
设已知:
（1）能阅读者是识字的;
（2）海豚不识字;（3）有些海豚是聪明的;求证:
有些聪明者并不能阅读.证:
定义如下命题:
R（x）:
x能阅读;L（x）:
x识字;I（x）:
x是聪明的;D（x）:
x是海豚;把已知条件及求证结论翻译成谓词公式为x（R（x）L（x）.已知x（D（x）L（x）.已知x（D（x）I（x）.已知x（I（x）R（x）.求证结论将已知条件,求证结论的反化成子句集R（x）L（x）D（y）L（y）D（a）I（a）I（z）R（z）L（a）.2,3归结a/yR（a）.1,6归结a/xR（a）.4,5归结a/zNIL.7,8归结得证.,例3.17“快乐学生”问题假设：
任何通过计算机考试并获奖的人都是快乐的，任何肯学习或幸运的人都可以通过所有考试，张不肯学习但他是幸运的，任何幸运的人都能获奖。
求证：
张是快乐的。
解：
先定义谓词：
Pass（x,y）x可以通过y考试Win（x,prize）x能获得奖励Study（x）x肯学习Happy（x）x是快乐的Lucky（x）x是幸运的,再将问题用谓词表示如下：
“任何通过计算机考试并奖的人都是快乐的”（x）（Pass（x,computer）Win（x,prize）Happy（x）“任何肯学习或幸运的人都可以通过所有考试”（x）（y）（Study（x）Lucky（x）Pass（x,y）“张不肯学习但他是幸运的”Study（zhang）Lucky（zhang）“任何幸运的人都能获奖”（x）（Lucky（x）Win（x,prize）结论“张是快乐的”的否定Happy（zhang）,将上述谓词公式转化为子句集如下：
（1）Pass（x,computer）Win（x,prize）Happy（x）
（2）Study（y）Pass（y,z）（3）Lucky（u）Pass（u,v）（4）Study（zhang）（5）Lucky（zhang）（6）Lucky（w）Win（w,prize）（7）Happy（zhang）（结论的否定）,Pass（x,computer）Win（x,prize）Happy（x）,Lucky（w）Win（w,prize）,Pass（w,Computer）Happy（w）Lucky（w）,Happy（zhang）,Lucky（zhang）,Pass（zhang,Computer）Lucky（zhang）,Pass（zhang,Computer）,Lucky（u）Pass（u,v）,Lucky（zhang）,Lucky（zhang）,NIL,w/x,zhang/w,zhang/u,computer/v,例3.18“激动人心的生活”问题假设：
所有不贫穷并且聪明的人都是快乐的，那些看书的人是聪明的。
李明能看书且不贫穷，快乐的人过着激动人心的生活。
求证：
李明过着激动人心的生活。
解：
先定义谓词：
Poor（x）x是贫穷的Smart（x）x是聪明的Happy（x）x是快乐的Read（x）x能看书Exciting（x）x过着激动人心的生活,再将问题用谓词表示如下：
“所有不贫穷并且聪明的人都是快乐的”（x）（Poor（x）Smart（x）Happy（x）“那些看书的人是聪明的”（y）（Read（y）Smart（y）“李明能看书且不贫穷”Read（Liming）Poor（Liming）“快乐的人过着激动人心的生活”（z）（Happy（z）Exciting（z）目标“李明过着激动人心的生活”的否定Exciting（Liming）,将上述谓词公式转化为子句集如下：
（1）Poor（x）Smart（x）Happy（x）
（2）Read（y）Smart（y）（3）Read（Liming）（4）Poor（Liming）（5）Happy（z）Exciting（z）（6）Exciting（Liming）（结论的否定）,Exciting（Liming）,Happy（z）Exciting（z）,Happy（Liming）,Happy（x）Smart（x）Happy（x）,Poor（Liming）Smart（Liming）,Read（y）Smart（y）,Poor（Liming）Read（Liming）,Poor（Liming）,Read（Liming）,Read（Liming）,NIL,Liming/z,Liming/x,Liming/y,应用归结原理求问题的答案,求问题的答案与定理证明类似，其步骤为：
（1）用谓词公式表示已知前提，并化为子句集S；
（2）用谓词公式表示待求解，并将其否定与谓词ANSWER构成析取式（同一个子句）；ANSWER是一个为求解而设定的谓词，其变元必须与问题公式的变元一致；（用重言式也可）（3）把此析取式化为子句集，并把该子句集假如到子句集S中，得到子句集S；（4）对S应用归结原理进行归结；（5）若得到归结式ANSWER，则答案就在ANSWER中。
例设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（C）T（A）T（B）（4）T（B）T（C）（5）T（C）T（A）T（B）（6）T（A）T（C）（7）T（B）T（C）下面先求谁是老实人。
把T（x）Answer（x）并入S得到S1。
即多一个子句：
（8）T（x）Answer（x）应用归结原理对S1进行归结：
（9）T（A）T（C）
（1）和（7）归结（10）T（C）（6）和（9）归结（11）Answer（C）（8）和（10）归结所以C是老实人，即C从不说假话。
下面证A和B不是老实人。
设A不是老实人，则有T（A），把它否定并入S中，得到子句集S2，即S2比S多如下子句：
（8）（T（A）,即T（A）应用归结原理对S2进行归结：
（9）T（A）T（C）
（1）和（7）归结（10）T（A）
（2）和（9）归结（11）NIL（8）和（10）归结所以A不是老实人。
同理，可证明B也不是老实人。
归结时，并不
升级会员 