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

人工智能与专家系统人工智能与专家系统(第二版）第二版）中国水利水电出版社中国水利水电出版社 人工智能与专家系统人工智能与专家系统人工智能与专家系统人工智能与专家系统(第二版）第二版）中国水利水电出版社中国水利水电出版社 第第4章章 逻辑推理逻辑推理4.1 4.1 推理的基本概念推理的基本概念4.2 4.2 归结演绎推理归结演绎推理4.4 4.4 归结反演的改进策略归结反演的改进策略4.3 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.24.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=xi ui/yi当当yix1,x2,，xn后剩下的元素所构成的集合，记为后剩下的元素所构成的集合，记为人工智能与专家系统人工智能与专家系统(第二版）第二版）中国水利水电出版社中国水利水电出版社 定义定义4.34.3 设有公式集设有公式集F=F1,F2,Fn,若若存在一个代换存在一个代换使得使得F1=F2=Fn则称则称为公式集为公式集F的一个合一，且称的一个合一，且称F1,F2,Fn是可合一的。是可合一的。人工智能与专家系统人工智能与专家系统(第二版）第二版）中国水利水电出版社中国水利水电出版社 定义定义4.44.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/xk Fk+1=Fk tk/xk k=k+1转步骤（转步骤（2）；否则，）；否则，算法终止，算法终止，F的最一般合一不存在。的最一般合一不存在。人工智能与专家系统人工智能与专家系统(第二版）第二版）中国水利水电出版社中国水利水电出版社 例4.1 设有公式集：设有公式集：F=P(A,F=P(A,x x,f f (g g(y y),),P(P(z z,f f(z z),),f f(u 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.54.5在谓词逻辑中，把原子谓词在谓词逻辑中，把原子谓词公式及其否定统称为公式及其否定统称为文字。任何文字的析。任何文字的析取式称为取式称为子句。定义定义4.64.6 不包含任何文字的子句称为不包含任何文字的子句称为空子句。由于空子句不含有文字，它不能被任由于空子句不含有文字，它不能被任何解释满足，所以空子句是永假的，不可何解释满足，所以空子句是永假的，不可满足的。满足的。人工智能与专家系统人工智能与专家系统(第二版）第二版）中国水利水电出版社中国水利水电出版社 谓词公式化成子句集的步骤谓词公式化成子句集的步骤:（1）消去蕴涵连词）消去蕴涵连词利用下述等价关系消去谓词公式中的利用下述等价关系消去谓词公式中的蕴涵连词蕴涵连词“”：PQPQ人工智能与专家系统人工智能与专家系统(第二版）第二版）中国水利水电出版社中国水利水电出版社（2）减小否定连词的辖域）减小否定连词的辖域利用下述等价关系把利用下述等价关系把“”移到紧靠移到紧靠谓谓词的位置上：词的位置上：人工智能与专家系统人工智能与专家系统(第二版）第二版）中国水利水电出版社中国水利水电出版社（3）约束变元标准化）约束变元标准化（4）消去存在量词）消去存在量词若存在量词不在全称量词的辖域内，则若存在量词不在全称量词的辖域内，则用一个个体常量替换受该存在量词约束的变用一个个体常量替换受该存在量词约束的变元。元。若存在量词位于一个或多个全称量词的辖若存在量词位于一个或多个全称量词的辖域内，则需要用域内，则需要用Skolem函数函数f(x1,x2,，xn)替换受该存在量词约束的变元替换受该存在量词约束的变元y。人工智能与专家系统人工智能与专家系统(第二版）第二版）中国水利水电出版社中国水利水电出版社（5）组成全称量词前缀）组成全称量词前缀 （6 6）利用等价关系把母式化为）利用等价关系把母式化为SkolemSkolem标准标准形：形：（7 7）消去全称量词。）消去全称量词。（8 8）对变元更名，使不同子句中的变元不）对变元更名，使不同子句中的变元不同名。同名。（9 9）消去合取连词，得到子句集。）消去合取连词，得到子句集。人工智能与专家系统人工智能与专家系统(第二版）第二版）中国水利水电出版社中国水利水电出版社 例4.2请将下述谓词公式化为子句集：请将下述谓词公式化为子句集：人工智能与专家系统人工智能与专家系统(第二版）第二版）中国水利水电出版社中国水利水电出版社 解：人工智能与专家系统人工智能与专家系统(第二版）第二版）中国水利水电出版社中国水利水电出版社 4.2.2 归结原理归结原理子句集中的子句之间是合取关系，子句集中的子句之间是合取关系，其中只要有一个子句不可满足，子句集就其中只要有一个子句不可满足，子句集就不可满足。空子句是不可满足的。因此，不可满足。空子句是不可满足的。因此，若一个子句集中包含空子句，则这个子句若一个子句集中包含空子句，则这个子句集是不可满足的。集是不可满足的。人工智能与专家系统人工智能与专家系统(第二版）第二版）中国水利水电出版社中国水利水电出版社 1.命题逻辑中的归结原理命题逻辑中的归结原理 定义定义4.74.7若若P是原子谓词公式，则称是原子谓词公式，则称P与与P为为互补文字互补文字。定义定义4.84.8设设C1与与C2是子句集中的任意是子句集中的任意两个子句，如果两个子句，如果C1中的文字中的文字L1与与C2中的文字中的文字L2互补，那么从互补，那么从C1和和C2中分别消去中分别消去L1和和L2，并将二个子句中余下的部分析取，构成一个新并将二个子句中余下的部分析取，构成一个新子句子句C12，则称这一过程为，则称这一过程为归结归结，称，称C12为为C1和和C2的归结式，称的归结式，称C1和和C2为为C12的的亲本子句亲本子句。人工智能与专家系统人工智能与专家系统(第二版）第二版）中国水利水电出版社中国水利水电出版社 定理定理4.24.2归结式归结式C12是其亲本子句是其亲本子句C1与与C2的的逻辑结论逻辑结论。推论推论4.14.1设设C1与与C2是子句集是子句集S中的两个子句，中的两个子句，C12是它们的归结式，若用是它们的归结式，若用C12代替代替C1和和C2后得到后得到新子句集新子句集S1，则由，则由S1的不可满足性可推出原子句的不可满足性可推出原子句集集S的不可满足性，即的不可满足性，即S1的不可满足性的不可满足性S的不可满足性的不可满足性 人工智能与专家系统人工智能与专家系统(第二版）第二版）中国水利水电出版社中国水利水电出版社 推论推论4.2 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.94.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；把把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.84.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.104.10的初始子句的初始子句集进行归结。集进行归结。图图4.10线性输入策略归结树线性输入策略归结树人工智能与专家系统人工智能与专家系统(第二版）第二版）中国水利水电出版社中国水利水电出版社 3 单文字子句策略单文字子句策略3 单文字子句策略单文字子句策略如果一个子句只包含一个文字，则称如果一个子句只包含一个文字，则称它为它为单文字子句单文字子句。单文字子句策略要求参。单文字子句策略要求参加归结的两个子句中必须有一个是单文字加归结的两个子句中必须有一个是单文字子句。子句。单文字子句策略是不完备的。单文字子句策略是不完备的。人工智能与专家系统人工智能与专家系统(第二版）第二版）中国水利水电出版社中国水利水电出版社 例4.12 对例对例4.104.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祖先过滤形策略归结树祖先过滤形策略归结树