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

ArtificialIntelligence(AI)人工智能,主讲：戚玉涛,Email：qi_yutao,第三章：确定性推理,内容提要,第三章：确定性推理,1.推理的基本概念,2.搜索策略,3.自然演绎推理,4.归结演绎推理,5.基于规则的演绎推理,自然演绎推理,自然演绎推理：从一组已知为真的事实出发，直接运用经典逻辑中的推理规则推出结论的过程称为自然演绎推理。自然演绎推理最基本的推理规则是三段论推理，它包括：假言推理拒取式假言三段论,自然演绎推理,假言推理：P,PQQ表示：由PQ以及P为真，可以推出Q为真例如：由“如果x是金属，则x能导电”，以及“铜是金属”，可以推出“铜能导电”。拒取式：PQ,QP表示：由PQ为真以及Q为假，可以推出P为假例如：由“如果下雨，则地上会湿”，以及“地上不湿”，可以推出“没有下雨”。假言三段论：PQ,QRPR,自然演绎推理,注意避免以下两类错误：肯定后件的错误：当PQ为真时，希望通过肯定后件Q为真来推出前件P为真，这是不允许的。例如：伽利略在论证哥白尼的日心说时，曾使用了如下推理：(1)如果行星系统是以太阳为中心的，则金星会显示出位相变化；(2)金星显示出位相变化；(3)所有，行星系统是以太阳为中心的这就是使用了肯定后件的推理，违反了经典逻辑的逻辑规则。,自然演绎推理,注意避免以下两类错误：否定前件的错误：当PQ为真时，希望通过否定前件P来推出后件Q为假，这也是不允许的。例如：(1)如果下雨，则地上会湿(2)没有下雨(3)所有，地上不湿事实上，如果向地上洒水，地上也是会湿的。这就是使用了否定前件的推理，违反了经典逻辑的逻辑规则。,自然演绎推理,自然演绎推理的例子设已知如下事实：A,B,AC,BCD,DQ求证：Q为真。证明：因为A,ACC假言推理B,CBC引入合取词BC，BCDD假言推理D,DQQ假言推理因此，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/yProg(C),Prog(x)Like(Wang,x)Like(Wang,C)假言推理C/x因此，王程喜欢C这门课。,自然演绎推理,自然演绎推理的优缺点优点：定理证明过程自然，易于理解，并且有丰富的推理规则可用。缺点：是容易产生知识爆炸，推理过程中得到的中间结论一般按指数规律递增，对于复杂问题的推理不利，甚至难以实现。,内容提要,第三章：确定性推理,1.推理的基本概念,2.搜索策略,3.自然演绎推理,4.归结演绎推理,5.基于规则的演绎推理,归结演绎推理,归结演绎推理：是一种基于鲁滨逊（Robinson）归结原理的机器推理技术。鲁滨逊归结原理亦称为消解原理，是鲁滨逊于1965年在海伯伦（Herbrand）理论的基础上提出的一种基于逻辑的“反证法”。在人工智能中，几乎所有的问题都可以转化为一个定理证明问题。定理证明的实质，就是要对前提P和结论Q，证明PQ永真。要证明PQ永真，就是要证明PQ在任何一个非空的个体域上都是永真的。这将是非常困难的，甚至是不可实现的。,归结演绎推理,归结演绎推理：鲁滨逊归结原理把永真性的证明转化为关于不可满足性的证明。要证明PQ永真，只需证明PQ不可满足因为：(PQ)(PQ)PQ海伯伦(Herbrand)定理为自动定理证明奠定了理论基础。鲁滨逊(Robinson)提出的归结原理使机器定理证明成为现实。,归结演绎推理,归结演绎推理子句集及其化简鲁滨逊归结原理归结反演推理的归结策略用归结反演求取问题的答案,归结演绎推理,归结演绎推理子句集及其化简鲁滨逊归结原理归结反演推理的归结策略用归结反演求取问题的答案,子句集及其化简,无论是海伯伦理论，还是鲁滨逊归结原理是在子句集的基础上讨论问题的。因此，讨论归结演绎推理之前，需要先讨论子句集的有关概念。子句和子句集原子谓词公式及其否定统称为文字。例如:P(x)、Q(x)、P(x)、Q(x)等都是文字。任何文字的析取式称为子句。例如，P(x)Q(x)，P(x，f(x)Q(x，g(x)都是子句。,子句集及其化简,子句和子句集不含任何文字的子句称为空子句。由于空子句不含有任何文字，也就不能被任何解释所满足，因此空子句是永假的，不可满足的。空子句一般被记为NIL。由子句或空子句所构成的集合称为子句集。在子句集中，子句之间是合取关系子句集中的变元受全称量词的约束任何谓词公式都可通过等价关系及推理规则化为相应的子句集,子句集及其化简,把谓词公式化成子句集的步骤Step1：利用等价关系消去“”和“”反复使用如下等价公式：PQPQPQ(PQ)(PQ)即可消去谓词公式中的连接词“”和“”。例如：(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摩根定律：(PQ)PQ(PQ)PQ量词转换率：(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(QR)(PQ)(PR)把公式化为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是子句集中的任意两个子句，如果C1中的文字L1与C2中的文字L2互补，那么可从C1和C2中分别消去L1和L2，并将C1和C2中余下的部分按析取关系构成一个新的子句C12，则称这一过程为归结，称C12为C1和C2的归结式，称C1和C2为C12的亲本子句。,命题逻辑的归结,例如：设C1=PQR，C2=PS，求C1和C2的归结式C12。解：这里L1=P，L2=P，通过归结可以得到C12=QRS例如：设C1=Q，C2=Q，求C1和C2的归结式C12。解：这里L1=Q，L2=Q，通过归结可以得到C12=NIL,命题逻辑的归结,例如：设设C1=PQ，C2=Q，C3=P，求C1、C2、C3的归结式C123。解：若先对C1、C2归结，可得到C12=P然后再对C12和C3归结，得到C123=NIL如果改变归结顺序，同样可以得到相同的结果，即其归结过程是不唯一的。其归结归结过程可用右图来表示，该树称为归结树。,命题逻辑的归结,定理：归结式C12是其亲本子句C1和C2的逻辑结论。证明：设C1=LC1，C2=LC2关于解释I为真，则只需证明C12=C1C2关于解释I也为真。对于解释I，L和L中必有一个为假。若L为假，则必有C1为真，不然就会使C1为假，这将与前提假设C1为真矛盾，因此只能有C1为真。同理，若L为假，则必有C2为真。因此，必有C12=C1C2关于解释I也为真。即C12是C1和C2的逻辑结论。,命题逻辑的归结,推论1：设C1和C2是子句集S中的两个子句，C12是C1和C2的归结式，若用C12代替C1和C2后得到新的子句集S1，则由S1的不可满足性可以推出原子句集S的不可满足性。即：S1的不可满足性S的不可满足性推论2：设C1和C2是子句集S中的两个子句，C12是C1和C2的归结式，若把C12加入S中得到新的子句集S2，则S与S2的不可满足性是等价的。即：S2的不可满足性S的不可满足性,命题逻辑的归结,上述两个推论说明，为证明子句集S的不可满足性，只要对其中可进行归结得子句进行归结，并把归结式加入到子句集S中，或者用归结式代替他的亲本子句，然后对新的子句集证明其不可满足性就可以了。如果经归结能得到空子句，根据空子句的不可满足性，即可得到原子句集S是不可满足的结论。在命题逻辑中，对不可满足的子句集S，其归结原理是完备的。即：子句集S是不可满足的，当且仅当存在一个从S到空子句的归结过程。,命题逻辑的归结,命题逻辑的归结反演归结原理：假设F为已知前提，G为欲证明的结论，归结原理把证明G为F的逻辑结论转化为证明FG为不可满足。再根据上述定理，在不可满足的意义上，公式集FG与其子句集是等价的，即把公式集上的不可满足转化为子句集上的不可满足。应用归结原理证明定理的过程称为归结