《人工智能与专家系统(第二版)》第4章 逻辑推理.pptx

《人工智能与专家系统(第二版)》第4章 逻辑推理.pptx

《《人工智能与专家系统(第二版)》第4章 逻辑推理.pptx》由会员分享，可在线阅读，更多相关《《人工智能与专家系统(第二版)》第4章 逻辑推理.pptx（73页珍藏版）》请在冰点文库上搜索。

,人工智能与专家系统,第4章逻辑推理,4.1推理的基本概念,4.2归结演绎推理,4.4归结反演的改进策略,4.3基于归结反演的问题求解,4.1推理的基本概念,4.1.1推理方式及其分类4.1.2推理的控制策略4.1.3模式匹配及其变量代换,4.1.1推理方式及其分类,1演绎推理、归纳推理、默认推理演绎推理:

是从全称判断推导出特称判断的过程，即由一般性知识推理适合于某一具体情况的结论，是一种从一般到个别的推理。

归纳推理:

是从足够多的事例中归纳出一般性结论的推理过程，是一种从个别到一般的推理。

默认推理:

是在知识不完全的情况下假设某些条件已经具备所进行的推理,2确定性推理、不确定性推理确定性推理:

是指推理时所用的知识都是精确的，推出的结论也是确定的，其真值或者为真，或者为假。

不确定性推理:

是指推理时所用的知识不都是精确的，推出的结论也不完全是肯定的，其真值位于真与假之间。

3单调推理、非单调推理单调推理:

随着推理过程向前推进及新知识的进入，推出的结论呈单调增加的趋势。

非单调推理:

由于新知识的加入，不仅没有加强已推出的结论，反而要使得推理退回到前面的某一步，重新开始。

4启发式推理、非启发式推理启发式推理:

运用与问题有关的启发性知识，且能加快推理进程的推理。

5基于知识的推理、直觉推理基于知识的推理:

根据已掌握的事实，通过运用知识进行推理。

直觉推理:

根据常识进行的推理。

4.1.2推理的控制策略,1推理方向

（1）正向推理

（2）逆向推理（3）混合推理,2求解策略推理的求解策略:

推理是只求一个解，还是求所有解以及最优解等。

3限制策略推理的限制策略:

在控制策略中指定推理的限制条件，以对推理的深度、宽度、时间、空间等进行限制。

4冲突消解策略在推理过程中，可能发生已知事实可与知识库中的多个知识匹配成功；或者有多个已知事实可与知识库中的多个知识匹配成功。

称这种情况为发生了冲突。

冲突消解:

需要按一定策略解决冲突，以便从中挑选一个知识用于当前的推理，称这一解决冲突的过程为冲突消解。

解决冲突所用的方法称为冲突消解策略。

4.1.3模式匹配及其变量代换,模式匹配:

两个知识模式（如两个谓词公式、两个框架片断等）比较，检查这两个知识模式是否完全一致或近似一致。

如果两者完全一致，或者虽不完全一致但其相似程度落在指定的限度内，就称它们是可匹配的，否则为不可匹配。

确定性匹配:

两个知识模式完全一致，或者经过变量代换后变得完全一致。

例:

设有如下两个知识模式：

P1：

Father（李四，李小四）andMan（李小四）P2：

Father（x,y）andMan（y）若用常量“李四”代换变量x，用常量“李小四”代换变量y，则P1与P2就变得完全一致。

定义4.1代换是形如t1/x1,t2/x2,，tn/xn的有限集合。

其中t1,t2tn是项；x1,x2xn是互不相同的变元；ti/xi表示用ti代换xi,不允许ti与xi相同，也不允许变元xi循环地出现在另一个tj中。

定义4.2设=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=xiui/yi当yix1,x2,，xn后剩下的元素所构成的集合，记为,定义4.3设有公式集F=F1,F2,Fn,若存在一个代换使得F1=F2=Fn则称为公式集F的一个合一，且称F1,F2,Fn是可合一的。

定义4.4设是公式集F的一个合一，如果对任一个合一都存在一个代换，使得=。

则称是公式集F的最一般合一（mgu）。

差异集：

设有如下两个谓词公式：

F1：

P（x,y,z）F2：

P（x,f（A）,h（B）分别从F1与F2的第一个符号开始比较，得到第一个差异集：

D1=y,f（A）当继续比较，又发现F1中的z与F2中的h（B）不同，则得到第二个差异集：

D2=z,h（B）,求最一般合一算法:

（1）初始化，令k=0,Fk=F,k=。

其中，是代换空集。

（2）若Fk只含一个表达式，则算法停止，k就是最一般合一；否则转步骤（3）。

（3）找出Fk的差异集Dk。

（4）若Dk中存在变元xk和项tk，且xk不在tk中出现，则：

k+1=k。

tk/xkFk+1=Fktk/xkk=k+1转步骤

（2）；否则，算法终止，F的最一般合一不存在。

例4.1设有公式集：

F=P（A,x,f（g（y）,P（z,f（z）,f（u），求其最一般合一。

解：

初始化，令k=0，0=，F0=F=P（A,x,f（g（y）,P（z,f（z）,f（u）Loop1：

F0含有2个表达式，故0不是最一般合一，F0的差异集D0=A，z，可有代换A/z，1=0A/z=A/zF1=F0A/z=P（A,x,f（g（y）,P（A,f（A）,f（u）,Loop2：

F1含有2个表达式，故1不是最一般合一，F1的差异集D1=x，f（A），可有代换f（A）/x，2=1。

f（A）/x=A/z。

f（A）/x=A/z,f（A）/xF2=F1f（A）/x=P（A,f（A）,f（g（y）,P（A,f（A）,f（u）,Loop3：

F2的差异集D2=g（y），u，可有代换g（y）/u，3=2。

g（y）/u=A/z,f（A）/x。

g（y）/u=A/z,f（A）/x,g（y）/uF3=F2g（y）/u=P（A,f（A）,f（g（y）,P（A,f（A）,f（g（y）=P（A,f（A）,f（g（y）Loop4：

F3中只含有一个表达式，故算法成功终止。

公式集F的最一般合一为3=A/z,f（A）/x,g（y）/u,4.2归结演绎推理,4.2.1谓词公式化为子句集的方法4.2.2归结原理4.2.3归结反演,定理证明的实质是对已知前提P和待证结论Q证明PQ的永真性。

应用反证法的思想可把关于永真性的证明转化为不可满足性的证明，即证明PQ是不可满足的。

4.2.1谓词公式化为子句集的方法,定义4.5在谓词逻辑中，把原子谓词公式及其否定统称为文字。

任何文字的析取式称为子句。

定义4.6不包含任何文字的子句称为空子句。

由于空子句不含有文字，它不能被任何解释满足，所以空子句是永假的，不可满足的。

谓词公式化成子句集的步骤:

（1）消去蕴涵连词利用下述等价关系消去谓词公式中的蕴涵连词“”：

PQPQ,

（2）减小否定连词的辖域利用下述等价关系把“”移到紧靠谓词的位置上：

（3）约束变元标准化（4）消去存在量词若存在量词不在全称量词的辖域内，则用一个个体常量替换受该存在量词约束的变元。

若存在量词位于一个或多个全称量词的辖域内，则需要用Skolem函数f（x1,x2,，xn）替换受该存在量词约束的变元y。

（5）组成全称量词前缀（6）利用等价关系把母式化为Skolem标准形：

（7）消去全称量词。

（8）对变元更名，使不同子句中的变元不同名。

（9）消去合取连词，得到子句集。

例4.2请将下述谓词公式化为子句集：

解：

4.2.2归结原理,子句集中的子句之间是合取关系，其中只要有一个子句不可满足，子句集就不可满足。

空子句是不可满足的。

因此，若一个子句集中包含空子句，则这个子句集是不可满足的。

1.命题逻辑中的归结原理定义4.7若P是原子谓词公式，则称P与P为互补文字。

定义4.8设C1与C2是子句集中的任意两个子句，如果C1中的文字L1与C2中的文字L2互补，那么从C1和C2中分别消去L1和L2，并将二个子句中余下的部分析取，构成一个新子句C12，则称这一过程为归结，称C12为C1和C2的归结式，称C1和C2为C12的亲本子句。

定理4.2归结式C12是其亲本子句C1与C2的逻辑结论。

推论4.1设C1与C2是子句集S中的两个子句，C12是它们的归结式，若用C12代替C1和C2后得到新子句集S1，则由S1的不可满足性可推出原子句集S的不可满足性，即S1的不可满足性S的不可满足性,推论4.2设C1与C2是子句集S中的两个子句，C12是它们的归结式，若把C12加入S中，得到新子句集S2，则S与S2在不可满足的意义上是等价的，即S2的不可满足性S的不可满足性,2.谓词逻辑中的归结原理在谓词逻辑中，由于子句中含有变元，所以不可直接消去互补文字，先对变元代换，才能进行归结。

例如：

用最一般合一：

=A/x对两个子句分别进行代换：

C1=P（A）Q（A）C2=P（A）R（y）得到归结式：

Q（A）R（y）,定义4.9设C1与C2是两个没有相同变元的子句，L1和L2分别是C1和C2中的文字，若是L1和L2的最一般合一，则称C12=（C1-L1）（C2-L2）为C1和C2的二元归结式，L1和L2称为归结式的文字。

例4.3设C1=P（A）Q（x）R（x），C2=P（y）Q（B），给出C1和C2的归结式。

上述归结过程可以用归结树表示如图4.1所示。

图4.1例4.3的一种归结树,若选L1=Q（x）,L2=Q（B）,=B/x,则可得：

C12=（P（A）,Q（B）,R（B）-Q（B）（P（y）,Q（B）-Q（B）=（P（A）,R（B）（P（y）=P（A）,R（B）,P（y）=P（A）R（B）P（y）,上述归结过程的归结树如图4.2所示。

图4.2例4.3的另一种归结树,4.2.3归结反演,应用归结原理证明结论为真的过程称为归结反演。

设F为已知前提的公式集，Q为目标公式（结论），用归结反演证明Q为真的步骤：

否定Q，得到Q；把Q并入到公式集F中，得到F，Q；把公式集F，Q化为子句集S；应用归结原理对子句集S中的子句进行归结，并把每次归结得到的归结式都并入S中。

如此反复进行，若出现了空子句，则停止归结，此时就证明了Q为真。

例4.6已知求证：

G是F的逻辑结论。

证：

首先把F和G化为子句集,图4.4例4.6的归结树,例4.7在第2章例2.4中曾经得到如下公式：

自然数都是大于零的整数。

所有整数不是偶数就是奇数。

偶数除以是整数。

求证：

所有自然数不是奇数就是其一半为整数的数。

证：

首先把求证的问题用谓词公式表示出来：

把F1，F2，F3及G化成子句集：

（1）N（x）GZ（x）

（2）N（u）I（u）（3）I（y）E（y）O（y）（4）E（z）I（s（z）（5）N（t）（6）O（t）（7）I（s（t）,图4.5例4.7的归结树,4.3基于归结反演的问题求解,问题求解的步骤：

把已知前提用谓词公式表示，并且化为相应的子句集S。

把待求解的问题也用谓词公式表示，把它的否定式与谓词ANSWER构成一个析取式，ANSWER的变元数量和变元名必须与问题公式的变元一致。

把此析取式化为子句集，并且把该子句集加入到子句集S中，得到子句集S。

对S应用归结原理进行归结。

若在归结树的根节点中仅得到归结式ANSWER，则答案就在ANSWER中。

例4.8已知F1：

王（Wang）先生是小李（Li）的老师。

F2：

小李与小张（Zhang）是同班同学。

F3：

如果x与y是同班同学，则x的老师也是y的老师。

求：

小张的老师是谁？

解：

1定义谓词T（x,y）x是y的老师。

C（x,y）x与y是同班同学。

2谓词公式表示目标公式G的否定式与ANSWER的析取式为：

3化为子句集

（1）T（Wang,Li）

（2）C（Li,Zhang）（3）C（x,y）T（z,x）T（x,y）（4）T（u,Zhang）ANSWER（u）,图4.6例4.8的归结树,例4.9设A，B，C三人中有人从不说真话，也有人从不说假话，某人向这三人分别提出同一个问题：

谁是说谎者？

A答：

“B和C都是说谎者”；B答：

“A和C都是说谎者”；C答：

“A和B中至少有一个是说谎者”。

求谁是老实人，谁是说谎者？

解：

1定义谓词：

T（x）表示x说真话。

2谓词公式表示如果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）,3化成子句集S

（1）T（A）T（B）

（2）T（A）T（C）（3）T（A）T（B）T（C）（4）T（B）T（C）（5）T（C）T（A）T（B）（6）T（C）T（A）（7）T（C）T（B）求谁是老实人的目标公式：

（x）T（x）（8）T（x）ANSWER（x）,图4.7求谁是老实人的归结树,证明A和B不是老实人：

设A不是老实人，则有T（A），把它的否定式T（A）加入到S中，得到子句集S2。

对S2归结，从而证明了A不是老实人。

同理，可证明B也不是老实人。

图4.8例4.9证明A不是老实人的归结树,4.4归结反演的改进策略,4.4.1删除策略4.4.2限制策略,4.4.1删除策略,1纯文字删除如果某文字L在子句集中不存在可与之互补的文字L，则称该文字为纯文字。

在归结时纯文字不可能被消去，因而用包含它的子句进行归结时不可能得到空子句。

例如，设有子句集：

S=PQR,QR，Q,R其中，P是纯文字，因此可将子句PQR从S中删去。

2重言式删除如果一个子句中同时包含互补文字时，则称该子句为重言式。

例如P（x）P（x）,P（x）Q（x）P（x）都是重言式。

重言式是真值为真的子句。

对于一个子句集来说，增加或者删去一个真值为真的子句都不会影响它的不可满足性，因而可从子句集中删去重言式。

3包孕删除设有子句C1和C2，如果存在一个代换，使得则称C1包孕于C2。

例如：

P（x）包孕于P（y）Q（z）=y/x或称P（x）被P（y）Q（z）包孕把子句集中被包孕的子句删去后，不会影响子句集的不可满足性，可从子句集中删去被其它子句包孕的子句。

4.4.2限制策略,1支持集策略支持集策略对参加归结的子句提出了如下限制：

每一次归结时，亲本子句中至少应有一个是由目标公式的否定所得到的子句，或者是它们的后裔。

支持集策略是完备的。

例4.10设有初始子句集：

S=I（x）R（x）,I（A）,R（y）L（y）,L（A）其中I（x）R（x）是目标公式否定得到的子句。

图4.9支持集策略归结树,2线性输入策略线性输入策略对参加归结的子句提出了如下限制：

参加归结的两个子句中必须至少有一个是初始子句集中的子句。

线性输入策略是不完备的。

例4.11应用线性输入策略对例4.10的初始子句集进行归结。

图4.10线性输入策略归结树,3单文字子句策略,3单文字子句策略如果一个子句只包含一个文字，则称它为单文字子句。

单文字子句策略要求参加归结的两个子句中必须有一个是单文字子句。

单文字子句策略是不完备的。

例4.12对例4.10给出的初始子句集按单文字子句策略进行归结。

图4.11单文字子句策略的归结树,5祖先过滤形策略祖先过滤形策略要求两个子句C1和C2满足下述两个条件中的任意一个条件：

C1与C2中至少有一个是初始子句集中的子句。

如果两个子句都不是初始子句集中的子句，则一个应是另一个的祖先。

祖先过滤形策略是完备的。

例4.13有子句集S=P（x）Q（x）,P（y）Q（y）,P（u）Q（u）,P（t）Q（t）,用祖先过滤形策略进行归结。

图4.12祖先过滤形策略归结树,