西电人工智能12确定性推理part5

西安电子科技大学ArtificialIntelligence(AI)人工智能主讲：戚玉涛Email：[e-mail]第三章：确定性推理西安电子科技大学内容提要第三章：确定性推理1.推理的基本概念2.搜索策略3.自然演绎推理4.归结演绎推理5.基于规则的演绎推理西安电子科技大学自然演绎推理自然演绎推理：从一组已知为真的事实出发，直接运用经典逻辑中的推理规则推出结论的过程称为自然演绎推理。自然演绎推理最基本的推理规则是三段论推理，它包括：假言推理拒取式假言三段论西安电子科技大学自然演绎推理假言推理：P,P→Q⇒Q表示：由P→Q以及P为真，可以推出Q为真例如：由“如果x是金属，则x能导电”，以及“铜是金属”，可以推出“铜能导电”。拒取式：P→Q,﹁Q⇒﹁P表示：由P→Q为真以及Q为假，可以推出P为假例如：由“如果下雨，则地上会湿”，以及“地上不湿”，可以推出“没有下雨”。假言三段论：P→Q,Q→R⇒P→R西安电子科技大学自然演绎推理注意避免以下两类错误：肯定后件的错误：当P→Q为真时，希望通过肯定后件Q为真来推出前件P为真，这是不允许的。例如：伽利略在论证哥白尼的日心说时，曾使用了如下推理：(1)如果行星系统是以太阳为中心的，则金星会显示出位相变化；(2)金星显示出位相变化；(3)所有，行星系统是以太阳为中心的这就是使用了肯定后件的推理，违反了经典逻辑的逻辑规则。西安电子科技大学自然演绎推理注意避免以下两类错误：否定前件的错误：当P→Q为真时，希望通过否定前件P来推出后件Q为假，这也是不允许的。例如：(1)如果下雨，则地上会湿(2)没有下雨(3)所有，地上不湿事实上，如果向地上洒水，地上也是会湿的。这就是使用了否定前件的推理，违反了经典逻辑的逻辑规则。西安电子科技大学自然演绎推理自然演绎推理的例子设已知如下事实：A,B,A→C,B∧C→D,D→Q求证：Q为真。证明：因为A,A→C⇒C假言推理B,C⇒B∧C引入合取词B∧C，B∧C→D⇒D假言推理D,D→Q⇒Q假言推理因此，Q为真西安电子科技大学自然演绎推理自然演绎推理的例子设已知如下事实：•(1)只要是需要编程序的课，王程都喜欢。•(2)所有的程序设计语言课都是需要编程序的课。•(3)C是一门程序设计语言课。求证：王程喜欢C这门课。证明：首先定义谓词•Prog(x)：x是需要编程序的课。•Like(x,y):x喜欢y。•Lang(x):x是一门程序设计语言课西安电子科技大学自然演绎推理自然演绎推理的例子把已知事实及待求解问题用谓词公式表示如下：•Prog(x)→Like(Wang,x)•(∀x)(Lang(x)→Prog(x))•Lang(C)应用推理规则进行推理：•Lang(y)→Prog(y)全称固化•Lang(C)，Lang(y)→Prog(y)⇒Prog(C)假言推理{C/y}•Prog(C),Prog(x)→Like(Wang,x)⇒Like(Wang,C)假言推理{C/x}因此，王程喜欢C这门课。西安电子科技大学自然演绎推理自然演绎推理的优缺点优点：定理证明过程自然，易于理解，并且有丰富的推理规则可用。缺点：是容易产生知识爆炸，推理过程中得到的中间结论一般按指数规律递增，对于复杂问题的推理不利，甚至难以实现。西安电子科技大学内容提要第三章：确定性推理1.推理的基本概念2.搜索策略3.自然演绎推理4.归结演绎推理5.基于规则的演绎推理西安电子科技大学归结演绎推理归结演绎推理：是一种基于鲁滨逊（Robinson）归结原理的机器推理技术。鲁滨逊归结原理亦称为消解原理，是鲁滨逊于1965年在海伯伦（Herbrand）理论的基础上提出的一种基于逻辑的“反证法”。在人工智能中，几乎所有的问题都可以转化为一个定理证明问题。定理证明的实质，就是要对前提P和结论Q，证明P→Q永真。要证明P→Q永真，就是要证明P→Q在任何一个非空的个体域上都是永真的。这将是非常困难的，甚至是不可实现的。西安电子科技大学归结演绎推理归结演绎推理：鲁滨逊归结原理把永真性的证明转化为关于不可满足性的证明。要证明P→Q永真，只需证明P∧﹁Q不可满足因为：﹁(P→Q)⇔﹁(﹁P∨Q)⇔P∧﹁Q海伯伦(Herbrand)定理为自动定理证明奠定了理论基础。鲁滨逊(Robinson)提出的归结原理使机器定理证明成为现实。西安电子科技大学归结演绎推理归结演绎推理子句集及其化简鲁滨逊归结原理归结反演推理的归结策略用归结反演求取问题的答案西安电子科技大学归结演绎推理归结演绎推理子句集及其化简鲁滨逊归结原理归结反演推理的归结策略用归结反演求取问题的答案西安电子科技大学子句集及其化简无论是海伯伦理论，还是鲁滨逊归结原理是在子句集的基础上讨论问题的。因此，讨论归结演绎推理之前，需要先讨论子句集的有关概念。子句和子句集原子谓词公式及其否定统称为文字。例如:P(x)、Q(x)、﹁P(x)、﹁Q(x)等都是文字。任何文字的析取式称为子句。例如，P(x)∨Q(x)，P(x，f(x))∨Q(x，g(x))都是子句。西安电子科技大学子句集及其化简子句和子句集不含任何文字的子句称为空子句。由于空子句不含有任何文字，也就不能被任何解释所满足，因此空子句是永假的，不可满足的。空子句一般被记为NIL。由子句或空子句所构成的集合称为子句集。在子句集中，子句之间是合取关系子句集中的变元受全称量词的约束任何谓词公式都可通过等价关系及推理规则化为相应的子句集西安电子科技大学子句集及其化简把谓词公式化成子句集的步骤Step1：利用等价关系消去“→”和“↔”反复使用如下等价公式：–P→Q⇔﹁P∨Q–P↔Q⇔(P∧Q)∨(﹁P∧﹁Q)即可消去谓词公式中的连接词“→”和“↔”。例如：(∀x)((∀y)P(x,y)→﹁(∀y)(Q(x,y)→R(x,y)))经等价变化后为：(∀x)(﹁(∀y)P(x,y)∨﹁(∀y)(﹁Q(x,y)∨R(x,y)))西安电子科技大学子句集及其化简Step2：利用等价关系把“¬”移到紧靠谓词的位置上反复使用–双重否定率：﹁(﹁P)⇔P–摩根定律：﹁(P∧Q)⇔﹁P∨﹁Q﹁(P∨Q)⇔﹁P∧﹁Q–量词转换率：﹁(∀x)P(x)⇔(∃x)﹁P(x)﹁(∃x)P(x)⇔(∀x)﹁P(x)使得每个否定符号最多只作用于一个谓词上。例如：上式经等价变换后为(∀x)((∃y)﹁P(x，y)∨(∃y)(Q(x，y)∧﹁R(x，y))西安电子科技大学子句集及其化简Step3：重新命名变元，使不同量词约束的变元有不同的名字例如：上式经重新命名变换后为(∀x)((∃y)﹁P(x，y)∨(∃z)(Q(x，z)∧﹁R(x，z)))Step4：消去存在量词。消去存在量词时，需要区分以下两种情况：1）存在量词不出现在全称量词的辖域内，只要用一个新的个体常量替换受该存在量词约束的变元，就可消去该存在量词。2）存在量词位于一个或者多个全称量词的辖域内西安电子科技大学子句集及其化简如下面的谓词公式：(∀x1)…(∀xn)(∃y)P(x1，x2,…,xn,y)则需要用Skolem函数f(x1，x2,…,xn)替换受该存在量词约束的变元y，然后再消去该存在量词。例如：继续上面的例子(∀x)((∃y)﹁P(x，y)∨(∃z)(Q(x，z)∧﹁R(x，z)))式子中存在量词(y)及(z)都位于(x)的辖域内，所以需要用Skolem函数替换，设替换y和z的Skolem函数分别是f(x)和g(x)，则替换后得到：(∀x)(﹁P(x,f(x))∨(Q(x,g(x))∧﹁R(x,g(x))))西安电子科技大学子句集及其化简Step5：把全称量词全部移到公式的左边上式中由于只有一个全称量词，而且它位于公式的最左边，所以这里不需要做任何工作。如果在公式内部有全称量词，就需要把它们都移到公式的左边。Step6：利用等价关系P∨(Q∧R)⇔(P∨Q)∧(P∨R)把公式化为Skolem标准形Skolem标准形的一般形式为(∀x1)…(∀xn)M(x1,x2,……,xn)其中，M(x1,x2,……,xn)是Skolem标准形的母式，它由子句的合取所构成。西安电子科技大学子句集及其化简Skolem标准形的一般形式为(∀x1)…(∀xn)M(x1,x2,……,xn)其中，M(x1,x2,……,xn)是Skolem标准形的母式，它由子句的合取所构成。例如：前面的公式化为Skolem标准形后为(∀x)((﹁P(x,f(x))∨Q(x,g(x)))∧(﹁P(x,f(x))﹁R(x,g(x))))Step7：消去全称量词。由于母式中的全部变元均受全称量词的约束，并且全称量词的次序已无关紧要，因此可以省掉全称量词。例如：上式消去全称量词后为(﹁P(x,f(x))∨Q(x,g(x))∧(﹁P(x,f(x))∨﹁R(x,g(x)))西安电子科技大学子句集及其化简Step8：对变元更名，使不同子句中的变元不同名由于每一个子句都对应着母式中的一个合取元，并且所有变元都是由全称量词量化的，因此任意两个不同子句的变量之间实际上不存在任何关系，更换变量名不会影响公式的真值。例如：上式经更名后得到(﹁P(x,f(x))∨Q(x,g(x))∧(﹁P(y,f(y))∨﹁R(y,g(y)))Step9：消去合取词，就得到子句集。例如：消去合取词后，上式就变为下述子句集﹁P(x,f(x))∨Q(x,g(x))﹁P(y,f(y))∨﹁R(y,g(y))西安电子科技大学子句集及其化简子句集的意义在上述化简过程中，由于在消去存在量词时所用的Skolem函数可以不同，因此化简后的标准子句集是不唯一的。因此，当原谓词公式为非永假时，它与其标准子句集并不等价。但当原谓词公式为永假（或不可满足）时，其标准子句集则一定是永假的，即Skolem化并不影响原谓词公式的永假性。子句集S的不可满足性：对于任意论域中的任意一个解释，S中的子句不能同时取得真值T。西安电子科技大学子句集及其化简定理：设有谓词公式F，其子句集为S，则F不可满足的充要条件是S不可满足。由此定理可知，要证明一个谓词公式是不可满足的，只要证明其相应的标准子句集是不可满足的就可以了。由于子句集中的子句之间是合取关系，子句集中只要有一个子句为不可满足，则整个子句集就是不可满足的。空子句是不可满足的。因此，一个子句集中如果包含有空子句，则此子句集就一定是不可满足的。这个结论是鲁滨逊归结原理的主要依据。西安电子科技大学归结演绎推理归结演绎推理子句集及其化简鲁滨逊归结原理归结反演推理的归结策略用归结反演求取问题的答案西安电子科技大学鲁滨逊归结原理海伯伦（Herbrand）理论为了判断子句集的不可满足性，需要对所有可能论域上的所有解释进行判定。只有当子句集对任何非空个体域上的任何一个解释都是不可满足的，才可断定该子句集不可满足。海伯伦构造了一个特殊的论域（海伯伦域），并证明只要对这个特殊域上的一切解释进行判定，就可知子句集是否不可满足。海伯伦定理：子句集不可满足的充要条件是存在一个有限的不可满足的基子句集。海伯伦从理论上给出了证明子句集不可满足性的可行性及方法，但是要在计算机上实现是很困难的。西安电子科技大学鲁滨逊归结原理鲁滨逊归结原理的基本思想首先把欲证明问题的结论否定，并加入子句集，得到一个扩充的子句集S'；然后设法检验子句集S'是否含有空子句，若含有空子句，则表明S'是不可满足的；若不含有空子句，则继续使用归结法，在子句集中选择合适的子句进行归结，直至导出空子句或不能继续归结为止。鲁滨逊归结原理包括命题逻辑消解原理谓词逻辑消解原理西安电子科技大学命题逻辑的归结归结推理的核心是求两个子句的归结式归结式的定义及性质若P是原子谓词公式，则称P与﹁P为互补文字设C1和C2是子句集中的任意两个子句，