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

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,Click to edit Master title style,西安电子科技大学,Artificial Intelligence(AI),人工智能,主讲：戚玉涛,Email,：,qi_,第三章：确定性推理,内容提要,第三章：确定性推理,1.,推理的基本概念,2.,搜索策略,3.,自然演绎推理,4.,归结演绎推理,5.,基于规则的演绎推理,自然演绎推理,自然演绎推理：,从一组已知为真的事实出发，直接运用经典逻辑中的推理规则推出结论的过程称为自然演绎推理。,自然演绎推理最基本的推理规则是三段论推理，它包括：,假言推理,拒取式,假言三段论,自然演绎推理,假言推理：,P,PQ Q,表示：,由,PQ,以及,P,为真，可以推出,Q,为真,例如：,由“如果,x,是金属，则,x,能导电”，以及“铜是金属”，可以推出“铜能导电”。,拒取式：,PQ,Q P,表示：,由,PQ,为真以及,Q,为假，可以推出,P,为假,例如：,由“如果下雨，则地上会湿”，以及“地上不湿”，可以推出“没有下雨”。,假言三段论：,PQ,QR PR,自然演绎推理,注意避免以下两类错误：,肯定后件的错误：,当,PQ,为真时，希望通过肯定后件,Q,为真来推出前件,P,为真，这是不允许的。,例如：,伽利略在论证哥白尼的日心说时，曾使用了如下推理：,(1),如果行星系统是以太阳为中心的，则金星会显示出位相变化；,(2),金星显示出位相变化；,(3),所有，行星系统是以太阳为中心的,这就是使用了肯定后件的推理，违反了经典逻辑的逻辑规则。,自然演绎推理,注意避免以下两类错误：,否定前件的错误：,当,PQ,为真时，希望通过否定前件,P,来推出后件,Q,为假，这也是不允许的。,例如：,(1),如果下雨，则地上会湿,(2),没有下雨,(3),所有，地上不湿,事实上，如果向地上洒水，地上也是会湿的。这就是使用了否定前件的推理，违反了经典逻辑的逻辑规则。,自然演绎推理,自然演绎推理的例子,设已知如下事实：,A,B,AC,BCD,DQ,求证：,Q,为真。,证明：,因为,A,AC C,假言推理,B,C BC,引入合取词,BC,，,BCD D,假言推理,D,DQ 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,，证明,PQ,永真。,要证明,PQ,永真，就是要证明,PQ,在任何一个非空的个体域上都是永真的。这将是非常困难的，甚至是不可实现的。,归结演绎推理,归结演绎推理：,鲁滨逊归结原理把永真性的证明转化为关于不可满足性的证明。,要证明,PQ,永真,，只需证明,PQ,不可满足,因为：,(PQ)(PQ)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,。,由子句或空子句所构成的集合称为,子句集,。,在子句集中，子句之间是,合取关系,子句集中的,变元受全称量词的约束,任何谓词公式都可通过等价关系及推理规则化为相应的子句集,子句集及其化简,把谓词公式化成子句集的步骤,Step,1,：,利用等价关系消去“”和“”,反复使用如下等价公式：,PQ PQ,PQ (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),子句集及其化简,Step,2,：,利用等价关系把,“,”,移到紧靠谓词的位置上,反复使用,双重否定率：,(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),子句集及其化简,Step,3,：,重新命名变元，使不同量词约束的变元有不同的名字,例如：,上式经重新命名变换后为,(,x)(,y)P(x,，,y)(,z,)(Q(x,，,z,)R(x,，,z,),Step 4,：,消去存在量词。消去存在量词时，需要区分以下两种情况：,1,）存在量词不出现在全称量词的辖域内，只要用一个新的个体常量替换受该存在量词约束的变元，就可消去该存在量词。,2,）存在量词位于一个或者多个全称量词的辖域内,子句集及其化简,如下面的谓词公式：,(x,1,)(x,n,)(,y,)P(x,1,，,x,2,x,n,y,),则需要用,Skolem,函数,f(x,1,，,x,2,x,n,),替换受该存在量词约束的变元,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),),子句集及其化简,Step 5,：,把全称量词全部移到公式的左边,上式中由于只有一个全称量词，而且它位于公式的最左边，所以这里不需要做任何工作。,如果在公式内部有全称量词，就需要把它们都移到公式的左边。,Step 6,：,利用等价关系,P(QR)(PQ)(PR),把公式化为,Skolem,标准形,Skolem,标准形的一般形式为,(x,1,)(x,n,)M(x,1,x,2,x,n,),其中，,M(x,1,x,2,x,n,),是,Skolem,标准形的母式，它由子句的,合取,所构成。,子句集及其化简,Skolem,标准形的一般形式为,(x,1,)(x,n,)M(x,1,x,2,x,n,),其中，,M(x,1,x,2,x,n,),是,Skolem,标准形的母式，它由子句的合取所构成。,例如：,前面的公式化为,Skolem,标准形后为,(x)(,(P(x,f(x)Q(x,g(x),(P(x,f(x)R(x,g(x),),Step 7,：,消去全称量词。由于母式中的全部变元均受全称量词的约束，并且全称量词的次序已无关紧要，因此可以省掉全称量词。,例如：,上式消去全称量词后为,(P(x,f(x)Q(x,g(x)(P(x,f(x)R(x,g(x),子句集及其化简,Step 8,：,对变元更名，,使不同子句中的变元不同名,由于每一个子句都对应着母式中的一个合取元，并且所有变元都是由全称量词量化的，因此,任意两个不同子句的变量之间实际上不存在任何关系，更换变量名不会影响公式的真值。,例如：,上式经更名后得到,(P(x,f(x)Q(x,g(x)(P(,y,f(,y,)R(,y,g(,y,),Step 9,：,消去合取词，就得到,子句集,。,例如：,消去合取词后，上式就变为下述子句集,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,）理论,为了判断子句集的不可满足性，需要对所有可能论域上的所有解释进行判定。只有当子句集对,任何非空个体域,上的,任何一个解释,都是不可满足的，才可断定该子句集不可满足。,海伯伦构造了一个特殊的论域（,海伯伦域,），并证明,只要对这个特殊域上的一切解释进行判定，就可知子句集是否不可满足,。,海伯伦定理：,子句集不可满足的,充要条件,是,存在一个有限的不可满足的基子句集,。,海伯伦从理论上给出了证明子句集不可满足性的可行性及方法，但是要在计算机上实现是很困难的。,鲁滨逊归结原理,鲁滨逊归结原理的基本思想,首先把欲证明问