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

人工智能与专家系统(第二版）中国水利水电出版社人工智能与专家系统人工智能与专家系统(第二版）中国水利水电出版社第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,t2…tn是项；x1,x2…xn是互不相同的变元；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当yi∈{x1,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/xk}Fk+1=Fk{tk/xk}k=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=σ0{A/z}={A/z}F1=F0{A/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)/x}F2=F1{f(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)/u}F3=F2{g(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证明P→Q的永真性。应用反证法的思想可把关于永真性的证明转化为不可满足性的证明，即证明P∧﹁Q是不可满足的。人工智能与专家系统(第二版）中国水利水电出版社4.2.1谓词公式化为子句集的方法定义4.5在谓词逻辑中，把原子谓词公式及其否定统称为文字。任何文字的析取式称为子句。定义4.6不包含任何文字的子句称为空子句。由于空子句不含有文字，它不能被任何解释满足，所以空子句是永假的，不可满足的。人工智能与专家系统(第二版）中国水利水电出版社谓词公式化成子句集的步骤:（1）消去蕴涵连词利用下述等价关系消去谓词公式中的蕴涵连词“→”：P→QP∨Q人工智能与专家系统(第二版）中国水利水电出版社（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}；③把