人工智能 谓词逻辑与归结原理

谓词逻辑与归结原理消解原理基本知识合取范式：仅由有限个简单析取式构成的合取式，即合取项是单元子句或单元子句的析取形如：P∧（P∨Q）∧（~P∨~Q）求合取范式的基本原则：利用“∨”对“∧”的分配求合取范式的基本步骤：削去对于{→，∨，∧}来说冗余的联结词内移或削去否定号利用分配律消解原理基本知识求取p∧(q→r)→s的合取范式=~(p∧(~q∨r))∨s=~p∨~(~q∨r)∨s=~p∨(~~q∧~r)∨s=~p∨(q∧~r)∨s=~p∨s∨(q∧~r)=（~p∨s∨q）∧（~p∨s∨~r)p∧(q→r)→s命题逻辑的推理方法：我们说如果有条件F1，F2，F3…..Fn同时成立，则有结论B成立。F1∧F2∧F3∧……∧Fn∧~B（永假）~(~(F1∧F2∧F3∧……∧Fn)∨B)不成立~(F1∧F2∧F3∧……∧Fn)∨B成立（永真）可以表示说：F1∧F2∧F3∧……∧Fn→B成立（永真）基础知识谓词公式、某些推理规则以及置换合一等概念。子句，由文字的析取组成的公式；一个原子公式和原子公式的否定都叫做文字。消解当消解可使用时，消解过程被应用于母体子句对，以便产生一个导出子句。例如，如果存在某个公理E1∨E2和另一公理～E2∨E3，那么E1∨E3在逻辑上成立。这就是消解，而称E1∨E3为E1∨E2和～E2∨E3的消解式（resolvent）。任一谓词演算公式可以化成一个子句集子句集的求取消解原理子句集的求取由下列九个步骤组成：(1)消去蕴涵符号只应用∨和～符号，以～A∨B替换A=B。(2)减少否定符号的辖域每个否定符号～最多只用到一个谓词符号上，并反复应用狄·摩根定律。例如：以～A∨～B代替～(A∧B)以～A∧～B代替～(A∨B)以(x){～A}代替～(x)A以(x){～A}代替～(x)A以A代替～(～A)(3)对变量标准化子句集的求取由下列九个步骤组成：在任一量词辖域内，受该量词约束的变量为一哑元(虚构变量)，它可以在该辖域内处处统一地被另一个没有出现过的任意变量所代替，而不改变公式的真值。合适公式中变量的标准化，意味着对哑元改名以保证每个量词有其自己唯一的哑元。例如，把标准化而得到:(4)消去存在量词对于一个受存在量词约束的变量，如果它不受全称量词约束，则该变量用一个常量来代替，如果它受全称量词约束，则该变量用一个含有全称量词对应变量的函数（Skolem函数）来代替。Skolem函数所使用的函数符号必须是新的，即不允许是公式中已经出现过的函数符号。替代的常量符号必须是个新的常量符号，它未曾在公式中其它地方使用过。子句集的求取由下列九个步骤组成：例如：(5)化为前束形到这一步，已不留下任何存在量词，而且每个全称量词都有自己的变量。把所有全称量词移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整个部分。所得公式称为前束形。前束形公式由前缀和母式组成，前缀由全称量词串组成，母式由没有量词的公式组成，即前束形=(前缀)(母式)全称量词串无量词公式子句集的求取由下列九个步骤组成：(6)把母式化为合取范式任何母式都可写成由一些谓词公式和(或)谓词公式的否定的析取的有限集组成的合取。这种母式叫做合取范式。我们可以反复应用分配律。把任一母式化成合取范式。例如，我们把(7)消去全称量词到了这一步，所有余下的量词均被全称量词量化了。同时，全称量词的次序也不重要了。因此，我们可以消去前缀，即消去明显出现的全称量词。(8)消去连词符号∧用{(A∨B),(A∨C)}代替(A∨B)∧(A∨C)，以消去明显的符号∧。反复代替的结果，最后得到一个有限集，其中每个公式是文字的析取。任一个只由文字的析取构成的合适公式叫做一个子句。子句集的求取由下列九个步骤组成：(9)更换变量名称可以更换变量符号的名称，使一个变量符号不出现在一个以上的子句中。例如，对于子集{～P(x)∨～P(y)∨P[f(x,y)],～P(x)∨Q[x,g(x)],～P(x)∨～P[g(x)]}，在更改变量名后，可以得到子句集：{～P(x1)∨～P(y)∨P[f(x1,y)],～P(x2)∨Q[x2,g(x2)],～P(x3)∨～P[g(x3)]}子句集的求取例：①(x){~P(x)∨{(y)[~P(y)∨P(f(x,y))]∧~(y)[~Q(x,y)∨P(y)]}}②(x){~P(x)∨{(y)[~P(y)∨P(f(x,y))]∧(y){~[~Q(x,y)∨P(y)]}}(x){~P(x)∨{(y)[~P(y)∨P(f(x,y))]∧(y)[Q(x,y)∧~P(y)]}}③(x){~P(x)∨{(y)[~P(y)∨P(f(x,y))]∧(w)[Q(x,w)∧~P(w)]}}④(x){~P(x)∨{(y)[~P(y)∨P(f(x,y))]∧[Q(x,g(x)∧~P(g(x)]}}⑤(x)(y){~P(x)∨{[~P(y)∨P(f(x,y))]∧[Q(x,g(x)∧~P(g(x)]}}子句集的求取⑥(x)(y){[~P(x)∨~P(y)∨P(f(x,y))]∧[~P(x)∨Q(x,g(x)]∧[~P(x)∨~P(g(x)]}}⑦[~P(x)∨~P(y)∨P(f(x,y))]∧[~P(x)∨Q(x,g(x)]∧[~P(x)∨~P(g(x)]}}⑧~P(x)∨~P(y)∨P(f(x,y))~P(x)∨Q(x,g(x)~P(x)∨~P(g(x)⑨~P(x1)∨~P(y)∨P(f(x1,y))~P(x2)∨Q(x2,g(x2)~P(x3)∨~P(g(x3)消解推理规则令L1为任一原子公式，L2为另一原子公式；L1和L2具有相同的谓词符号，但一般具有不同的变量。已知两子句L1∨α和～L2∨β如果L1和L2具有最一般合一者σ，那么通过消解可以从这两个父辈子句推导出一个新子句(α∨β)σ。这个新子句叫做消解式。它是由取这两个子句的析取，然后消去互补对而得到的。从父辈子句求消解式的例子(a)假言推理(b)合并(c)重言式(d)链式(三段论)(e)空子句(矛盾)消解可以合并几个运算为一简单的推理规则含有变量的子句使用消解的例子例1例2例3消解推理常用规则消解反演求解过程基本思想把要解决的问题作为一个要证明的命题，其目标公式被否定并化成子句形，然后添加到命题公式集中去,把消解反演系统应用于联合集，并推导出一个空子句(NIL)，产生一个矛盾，这说明目标公式的否定式不成立，即有目标公式成立，定理得证，问题得到解决。这与数学中反证法的思想十分相似。消解反演求解过程消解反演反演求解的步骤给出一个公式集S和目标公式L，通过反证或反演来求证目标公式L，其证明步骤如下：(1)否定L，得～L；(2)把～L添加到S中去；(3)把新产生的集合｛～L，S｝化成子句集；(4)应用消解原理，力图推导出一个表示矛盾的空子句NIL。消解反演求解过程消解反演反演求解的正确性设公式L在逻辑上遵循公式集S，那么按照定义满足S的每个解释也满足L。决不会有满足S的解释能够满足～L的，所以不存在能够满足并集S∪｛～L｝的解释。如果一个公式集不能被任一解释所满足，那么这个公式是不可满足的。因此，如果L在逻辑上遵循S，那么S∪｛～L｝是不可满足的。可以证明，如果消解反演反复应用到不可满足的子句集，那么最终将要产生空子句NIL。因此，如果L在逻辑上遵循S，那么由并集S∪｛～L｝消解得到的子句，最后将产生空子句；反之，可以证明，如果从S∪｛～L｝的子句消解得到空子句，那么L在逻辑上遵循S。反演求解的举例例:假设任何通过计算机考试并获奖的人是快乐的,任何肯学习或幸运的人都可以通过所有的考试,张不肯学习但他是幸运的,任何幸运的人都能获奖.求证:张是快乐的.示例的谓词表示1.(x)((pass(x,computer)∧win(x,prize))happy(x))2.(x)(y)(study(x)∨lucky(x)pass(x,y))3.~study(zhang)∧lucky(zhang)4.(x)(Lucky(x)win(x,prize))5.~happy(zhang)化成子句集①~pass(x,computer)∨~win(x,prize)∨happy(x)②~study(y)∨pass(y,z)③~lucky(u)∨pass(u,v)④~study(zhang)⑤lucky(zhang)⑥~lucky(w)∨win(w,prize)⑦~happy(zhang)反演求解过程反演求解过程从反演树求取答案步骤把由目标公式的否定产生的每个子句添加到目标公式否定之否定(肯定\永真式)的子句中去。按照反演树，执行和以前相同的消解，直至在根部得到某个子句止。用根部的子句作为一个回答语句。实质把一棵根部有NIL的反演树变换为根部带有回答语句的一棵证明树。反演求解的举例IfFidogoeswhereverJohngoesandifJohnisatschool，whereisFido?先把问题用谓词逻辑公式表示：前提公式集：(∀x)（AT（John，x）→AT（Fido，x））AT（John，School）目标公式：(∃x)AT（Fido，x）反演求解的举例菲多在哪里例题的反演树从消解求取答案例题的反演树修改证明树修改证明树菲多在哪里例题的修改证明树反演求解的举例已知：①会朗读的人是识字的；②海豚都不识字；③有些海豚是很机灵的。证明：有些很机灵的东西不会朗读。把问题用谓词逻辑描述如下：已知：①（x）（R（x）→L（x））②（x）（D（x）→~L（x））③（x）（D（x）∧I（x））求证：（x）（I（x）∧~R（x））反演求解的举例例：寒冷户外戴帽子。cold∧outdoor→wearing应届高中生，得过数学或物理竞赛的一等奖，保送上北京大学。p∧(r∨t)→q规则演绎系统定义基于规则的问题求解系统运用If→Then规则来建立，每个if可能与某断言(assertion)集中的一个或多个断言匹配。有时把该断言集称为工作内存，then部分用于规定放入工作内存的新断言。这种基于规则的系统叫做规则演绎系统。在这种系统中，通常称每个if部分为前项，称每个then部分为后项。规则正向演绎系统定义正向规则演绎系统是从事实到目标进行操作的，即从状况条件到动作进行推理的，也就是从if到then的方向进行推理的求解过程事实表达式的与或形变换在基于规则的正向演绎系统中，我们把事实表示为非蕴涵形式的与或形，作为系统的总数据库。事实表达式的与或图表示事实表达式的与或图表示与或图的F规则变换我们把允许用作规则的公式类型限制为下列形式：L⇒W式中：L是单文字；W为与或形的唯一公式。单文字前项的任何蕴涵式，不管其量化情况如何都可以化为某种量化辖域为整个蕴涵式的形式。不含变量的与或图应用一条⇒规则得到的与或图P∨Q∨S,R∨S,P∨Q∨T∨U,R∨T∨U(1)X∨Z∨P∨Q,Y∨Z∨P∨Q,(2)R∨X∨Z,R∨Y∨Z规则S⇒[(X∧Y)∨Z]作为终止条件的目标公式规则逆向演绎系统定义逆向规则演绎系统是从then向if进行推理的，即从目标或动作向事实或状况条件进行推理的。求解过程目标表达式的与或形式与或图的B规则变换作为终止条件的事实节点的一致解图规则双向演绎系统概念正向和逆向组合系统是建立在两个系统相结合的基础上的。此组合系统的总数据库由表示目标和表示事实的两个与或图结构组成。这些与或图结构分别用正向系统的F规则和逆向系统的B规则来修正。