西电人工智能14确定性推理part7

西安电子科技大学ArtificialIntelligence(AI)人工智能主讲：戚玉涛Email：[e-mail]第三章：确定性推理西安电子科技大学内容提要第三章：确定性推理1.推理的基本概念2.搜索策略3.自然演绎推理4.归结演绎推理5.基于规则的演绎推理西安电子科技大学归结演绎推理归结演绎推理子句集及其化简鲁滨逊归结原理归结反演推理的归结策略用归结反演求取问题的答案西安电子科技大学用归结反演求取问题的答案归结原理出了可用于定理证明外，还可用来求取问题答案，其思想与定理证明相似。其一般步骤为：(1)把问题的已知条件用谓词公式表示出来，并化为子句集；(2)把问题的目标的否定用谓词公式表示出来，并化为子句集；(3)对目标否定子句集中的每个子句，构造该子句的重言式（即把该目标否定子句和此目标否定子句的否定之间再进行析取所得到的子句），用这些重言式代替相应的目标否定子句式，并把这些重言式加入到前提子句集中，得到一个新的子句集；(4)对这个新的子句集，应用归结原理求出其证明树，这时证明树的根子句不为空，称这个证明树为修改的证明树；(5)用修改证明树的根子句作为回答语句，则答案就在此根子句中。西安电子科技大学用归结反演求取问题的答案例1：已知：“张和李是同班同学，如果x和y是同班同学，则x的教室也是y的教室，现在张在302教室上课。”问：“现在李在哪个教室上课？”解：首先定义谓词C(x,y)：x和y是同班同学At(x,u)：x在u教室上课。把已知前提用谓词公式表示如下：C(zhang,li)(∀x)(∀y)(∀u)(C(x,y)∧At(x,u)→At(y,u))At(zhang,302)西安电子科技大学用归结反演求取问题的答案把目标的否定用谓词公式表示如下：﹁(∃v)At(li,v)把上述公式化为子句集：C(zhang,li)﹁C(x,y)∨﹁At(x,u)∨At(y,u)At(zhang,302)把目标的否定化成子句式，并用下面的重言式代替：﹁At(li,v)∨At(li,v)把此重言式加入前提子句集中，得到一个新的子句集，对这个新的子句集，应用归结原理求出其证明树。西安电子科技大学用归结反演求取问题的答案求解过程如下图所示。该证明树的根子句就是所求的答案，即“李明在302教室”。﹁At(li,v)∨At(li,v)﹁C(x,y)∨﹁At(x,u)∨At(y,u)At(li,v)∨﹁C(x,li)∨﹁At(x,v)C(zhang,li)﹁At(zhang,v)∨At(li,v)At(zhang,302)At(li,302){li/y,v/u}{Zhang/x}{302/v}西安电子科技大学用归结反演求取问题的答案例2：已知：A,B,C三人中有人从不说真话，也有人从不说假话。某人向这三人分别提出同一个问题：谁是说谎者？A答：“B和C都是说谎者”；B答：“A和C都是说谎者”；C答：“A和B中至少有一个是说谎者”。问：求谁是老实人，谁是说谎者？解：首先定义谓词T(x)：表示x说真话西安电子科技大学用归结反演求取问题的答案把已知前提用谓词公式表示如下：如果A说的是真话，则有：T(C)∨T(A)∨T(B)如果A说的是假话，则有：¬T(C)∨¬T(A)∨¬T(B)对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：¬T(A)∨¬T(B)¬T(A)∨¬T(C)T(C)∨T(A)∨T(B)¬T(B)∨¬T(C)¬T(C)∨¬T(A)∨¬T(B)T(A)∨T(C)T(B)∨T(C)先求谁是老实人，结论的否定为：¬(∃x)T(x)西安电子科技大学用归结反演求取问题的答案把目标的否定化成子句式，并用下面的重言式代替：¬T(x)∨T(x)把此重言式加入前提子句集S，得到一个新子句集，对这个新的子句集，应用归结原理求出其证明树。¬T(A)∨¬T(B)T(B)∨T(C)¬T(A)∨T(C)T(A)∨T(C)T(C)¬T(x)∨T(x)T(C){C/x}C是老实人西安电子科技大学用归结反演求取问题的答案下面证明A不是老实人，结论的否定为：¬T(A)将结论的否定¬(¬T(A))加入并入前提子句集S中，应用归结原理对新的子句集进行归结：¬T(A)∨¬T(B)T(B)∨T(C)¬T(A)∨T(C)¬T(A)∨¬T(C)¬T(A)T(A)NIL得证。A不是是老实人同理可证B不是老实人西安电子科技大学归结演绎推理归结演绎推理的优点：简单，便于在计算机上实现。归结演绎推理的不足：必须把逻辑公式化成子句集。不便于阅读与理解：¬P(x)∨Q(x)没有P(x)→Q(x)直观。可能丢失控制信息，如下列逻辑公式：(¬A∧¬B)→C¬A→(B∨C)(¬A∧¬C)→B¬B→(A∨C)(¬C∧¬B)→A¬C→(B∨A)化成子句后都是:A∨B∨C西安电子科技大学内容提要第三章：确定性推理1.推理的基本概念2.搜索策略3.自然演绎推理4.归结演绎推理5.基于规则的演绎推理西安电子科技大学基于规则的演绎推理在归结演绎推理中，需要把谓词公式化为子句形，这使得原来蕴含在谓词公式中的一些重要信息却会在求取子句形的过程中被丢失。在不少情况下人们多希望使用接近于问题原始描述的形式来进行求解，而不希望把问题描述化为子句集。基于规则的演绎推理：又称为与/或形演绎推理，不再把有关知识转化为子句集，而是把领域知识及已知事实分别用蕴含式及与/或形表示出来，然后通过运用蕴含式进行演绎推理，从而证明某个目标公式。西安电子科技大学基于规则的演绎推理规则是一种比较接近于人们习惯的问题描述方式，用蕴含式（“If→Then”规则）按照这种问题描述方式进行求解的系统称为基于规则的系统，或者叫做规则演绎系统。规则演绎系统按照推理方式可分为：规则正向演绎系统规则逆向演绎系统规则双向演绎系统西安电子科技大学基于规则的演绎推理规则演绎系统规则正向演绎系统规则逆向演绎系统规则双向演绎系统西安电子科技大学规则正向演绎系统规则正向演绎系统是从已知事实出发，正向使用规则（蕴含式）直接进行演绎，直至到达目标为止。在规则正向演绎系统中，对已知事实和规则都有一定的要求，如果不是所要求的形式，需要进行变换。事实表达式的与或形变换在基于规则的正向演绎系统中，把事实表示为非蕴含形式的与或形，作为系统的总数据库把一个公式化为与或形的步骤与化为子句集类似，只是不必把公式化为子句的合取形式，也不能消去公式中的合取。西安电子科技大学规则正向演绎系统把事实表达式化为非蕴含形式的与/或形的步骤如下：(1)利用“P→Q⇔﹁P∨Q”，消去蕴含符号；(2)利用狄.摩根定律及量词转换率把“﹁”移到紧靠谓词的位置，直到否定符号的辖域最多只含一个谓词为止；(3)重新命名变元，使不同量词约束的变元有不同的名字；(4)对存在量词量化的变量用skolem函数代替；(5)消去全称量词，且使各主要合取式中的变元具有不同的变量名。西安电子科技大学规则正向演绎系统例如：有如下表达式(∃x)(∀y)(Q(y,x)∧﹁((R(y)∨P(y))∧S(x,y)))可把它转化为：Q(z,a)∧((﹁R(y)∧﹁P(y))∨﹁S(a,y))这就是与/或形表示。事实表达式的与/或形可用一棵与/或图表示出来。西安电子科技大学规则正向演绎系统Q(z,a)∧((﹁R(y)∧﹁P(y))∨﹁S(a,y))的与/或图表示如下：Q(z,a)∧((﹁R(y)∧﹁P(y))∨﹁S(a,y))Q(z,a)((﹁R(y)∧﹁P(y))∨﹁S(a,y))﹁R(y)∧﹁P(y)﹁S(a,y)﹁R(y)﹁P(y)西安电子科技大学规则正向演绎系统与/或形的与/或图表示当某表达式为k个子表达式的析取：E1∨E2∨…∨Ek，其中的每个子表达式Ei均被表示为E1∨E2∨…∨Ek的后继节点，并由一个k线连接符（即图中的半圆弧）将这些后继节点都连接到其父节点，即表示成与的关系。当某表达式为k个子表达式的合取：E1∧E2∧…∧Ek，其中的每个子表达式Ei均被表示为E1∧E2∧…∧Ek的一个单一的后继节点，无需用连接符连接，即表示成或的关系。这样，与/或图的根节点就是整个事实表达式，叶节点均为事实表达式中的一个文字。西安电子科技大学规则正向演绎系统与/或形的与/或图表示有了与/或图的表示，就可以求出其解树（结束于文字节点上的子树）集。可以发现，事实表达式的子句集与解树集之间存在着一一对应关系，即解树集中的每个解树都对应着子句集中的一个子句。解树集中每个解树的端节点上的文字的析取就是子句集中的一个子句。例如：上图所示的与/或图有3个解树，分别对应这以下3个子句：Q(z,a)﹁R(y)∨﹁S(a,y)﹁P(y)∨﹁S(a,y)西安电子科技大学规则正向演绎系统与/或形的与/或图表示可以把与/或图看作是对子句集的简洁表示。不过，表达式的与/或图表示要比子句集表示的通用性差一些，原因是与/或图中的合取元没有进一步展开，因此不能象在子句形中那样对某些变量进行改名，这就限制了与/或图表示的灵活性。例如，上面的最后一个子句“﹁P(y)∨﹁S(a,y)”：在子句集中，其变量y可全部改名为x，但却无法在与/或图中加以表示，因而失去了通用性，并且可能带来一些困难。西安电子科技大学规则正向演绎系统与/或形的与/或图表示还需要指出，这里的与/或图是作为综合数据库的一种表示，其中的变量受全称量词的约束。在第二章问题归约表示中所描述的与/或图表示方法与这里与/或形的与/或图表示有着不同的目的和含义，因此应用时应加以区分。西安电子科技大学规则正向演绎系统规则的表示为简化演绎过程，通常要求规则具有如下形式：L→W其中，L为单文字，W为与/或形公式。假定出现在蕴含式中的任何变量全都受全称量词的约束，并且这些变量已经被换名，使得他们与事实公式和其他规则中的变量不同。如果领域知识的规则表示形式与上述要求不同，则应将它转换成要求的形式。西安电子科技大学规则正向演绎系统将规则转换为要求形式的步骤：(1)暂时消去蕴含符号“→”。设有如下公式：(∀x)(((∃y)(∀z)P(x,y,z))→(∀u)Q(x,u))运用等价关系“P→Q⇔﹁P∨Q”，可将上式变为：(∀x)(﹁((∃y)(∀z)P(x,y,z))∨(∀u)Q(x,u))(2)把否定符号“﹁”移到紧靠谓词的位置上，使其作用域仅限于单个谓词。通过使用狄.摩根定律及量词转换率可把上式转换为：(∀x)((∀y)(∃z)﹁P(x,y,z))∨(∀u)Q(x,u))西安电子科技大学规则正向演绎系统将规则转换为要求形式的步骤：(3)引入Skolem函数，消去存在量词。消去存在量词后，上式可变为：(∀x)((∀y)(﹁P(x,y,f(x,y)))∨(∀u)Q(x,u))(4)把所有全称量词移至前面化成前束式，消去全部全称量词。消去全称量词后，上式变为：﹁P(x,y,f(x,y))∨Q(x,u)此公式中的变元都被视为受全称量词约束的变元。(5)恢复蕴含式表示。利用等价关系“﹁P∨Q⇔P→Q”将上式变为：P(x,y,f(x,y))→Q(x,u)西安电子科技大学规则正向演绎系统规则的表示在上述对规则的要求中，之所以限制其前件为单文字，是因为在进行正向演绎推理时要用规则作用于表示事实的与/或树，而该与/或树的叶节点都是单文字，这样就可用规则的前件与叶节点进行简单匹配。对非单文字情况，若形式为L1∨L2→W，则可将其转换成与之等价的两个规则L1→W与L2→W进行处理。目标公式的表示形式与/或树正向演绎系统要求目标公式用子句形表示。如果目标公式不是子句形，则需要化成子句形。西安电子科技大学规则正向演绎系统推理过程规则正向演绎推理过程是从已知事实出发，不断运用规则，推出欲