AI-经典逻辑推理PPT.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,0,第五章 经典逻辑推理,5.1,推理的相关概念,5.2,自然演绎推理,5.3,归结演绎推理,5.4,与或树演绎推理,1,推理与搜索,推理,搜索,观点,/,表示,逻辑,状态空间,/,问题归约,确定,确定性推理,一般图搜索,不确定,不确定性推理,模糊搜索,适用性,问题本身存在很多规则，并且规则易于获取。,规则相对较少,.,问题本身易于用状态表示,基础,谓词演算,图论,2,5.1,推理的相关概念,一、推理,1.,按照某种策略从已知事实出发去推出结论的过程,问题解决的过程（思维过程）。,推理所用的事实可分为两种情况：,与求解问题有关的,初始证据,。,推理过程中所得到的,中间结论,。,2.,推理机,智能系统中用来实现推理的那些,程序,。,例如，医疗诊断专家系统,知识库,+,事实库（综合数据库）,+,推理机,3,3.,推理方法及其分类,推理方法,主要解决在推理过程中前提与结论之间的逻辑关系，以及在非精确性推理中不确定性的传递问题。,1),按推理的逻辑基础分类,演绎推理,归纳推理,默认推理,4,演绎推理,从已知的,一般性知识,出发，去推出蕴含在这些已知知识中的适合于某种,个别情况,的结论。,它是一种由,一般到个别,的推理方法,(,即从已知的一般性知识中抽取所包含的特殊性知识,),。其核心是三段论,:,大前提：已知的一般性知识或推理过程得到的判断。,小前提：关于某种具体情况或某个具体实例的判断。,结论：由大前提推出的，并且适合于小前提的判断。,例如，有如下三个判断：,（,a,）计算机系的学生都会编程序；,（,b,）程强是计算机系的一位学生；,（,c,）程强会编程序。,5,归纳推理,从一类事物的大量,特殊事例,出发，去推出该类事物的,一般性,结论。,它是一种由,个别到一般,的推理方法。,归纳推理,按照推理所使用的方法,按照所选事例的广泛性,完全归纳推理,不完全归纳推理,枚举归纳推理,类比归纳推理,统计归纳推理,差异归纳推理,6,演绎推理与归纳推理的区别,演绎推理是在已知领域内的一般性知识的前提下，通过演绎求解一个具体问题或者证明一个结论的正确性。它所得出的结论实际上早已蕴含在一般性知识的前提中，演绎推理只不过是将已有事实揭示出来，因此,演绎推理不能增殖新知识,。,在归纳推理中，所推出的结论是没有包含在前提内容中的。这种由个别事物或现象推出一般性知识的过程，,是增殖新知识的过程,。,7,默认推理,在知识不完全的情况下假设某些条件已经具备所进行的推理，因此也称为缺省推理。,如果发现原先的假设不正确，就撤消原来的假设以及由此假设所推出的所有结论，重新按新情况进行推理。,由于默认推理允许在推理过程中假设某些条件是成立的，这就,解决了在一个不完备的知识集中进行推理的问题。,8,2).,按所用知识的确定性分类,确定性推理,推理所使用的知识和推出的结论都是可以精确表示的，其真值要么为真，要么为假，不会有第三种情况出现。,不确定性推理,推理时所用的知识不都是确定的，推出的结论也不完全是确定的，其真值会位于真与假之间。,9,3).,按推理过程的单调性,单调推理,在推理过程中，每当使用新的知识后，所得到的结论会,越来越接近于目标,，而不会出现反复情况，即不会由于新知识的加入否定了前面推出的结论，从而使推理过程又退回到先前的某一步。,非单调推理,在推理过程中，当某些新知识加入后，会否定原来推出的结论，使推理过程退回到先前的某一步。,10,4).,按推理中是否运用与问题有关的启发性知识,启发式推理,启发性知识是指与问题有关且能加快推理过程、求得问题最优解的知识。,如：设推理的目标是要在脑膜炎、肺炎、流感三种疾病中选择一个，又设有,r1,，,r2,，,r3,这三条产生式规则可供使用，分别推出脑膜炎、肺炎、流感。如果希望尽早排除脑膜炎这一危险疾病，应该先选用,r1,，若本地区目前正在流行流感，则应考虑,r3,。其中，,“,脑膜炎危险,”,及,“,目前正在流行流感,”,是与问题求解有关的启发性信息。,非启发式推理,11,5).,从方法论的角度划分,基于知识的推理,根据已掌握的知识，通过运用知识进行的推理。,统计推理,根据对某事物的数据统计进行的推理。,直觉推理,又称为常识性推理，是根据常识进行的推理。如有重物落下时，意识到危险并立即躲开。,12,当推理过程有多条知识可用时，如何从这多条可用知识中选出一条最佳知识用于推理的策略。,二、推理的控制策略及其分类,推理的控制策略：,如何使用领域知识使推理过程尽快达到目标的策略。,推理的控制策略,推理策略,推理方向：,求解策略：,限制策略：,冲突消解策略：,搜索策略,推理线路,推理效果,推理效率,正向推理、逆向推理、混合推理、双向推理,仅求一个解，还是求所有解或最优解,对推理的深度、宽度、时间、空间等进行的限制,13,三、模式匹配,1.,定义：,对两个知识模式的比较与耦合，检查这两个知识模式是否完全一致（确定性匹配）或近似一致（不确定性匹配）。,2.,代换：,代换是形如,t,1,/x,1,t,2,/x,2,t,n,/x,n,的有限集合。其中，,t,1,t,2,t,n,是项，,x,1,x,2,x,n,是互不相同的变元。,t,i,/x,i,：,用,t,i,代换,x,i,；,不允许：,t,i,与,x,i,相同；,x,i,循环地出现在另一个,t,j,中。,例：,a/x,f(b)/y,w/z,是代换。,g(y)/x,f(x)/y,不是代换。,g(a)/x,f(x)/y,是代换，等价于,g(a)/x,f(g(a)/y,。,14,四、合一,定义,：设有公式集,F=F,1,F,2,F,n,，若存在一个代换,使得：,F,1,=F,2,=,=F,n,，则称,为公式集,F,的一个合一，且称,F,1,F,2,F,n,是可合一的。,例,：,F=P(x,y,f(y),P(a,g(x),z),，证明,=a/x,g(a)/y,f(g(a)/z,是,F,的一个合一。,令,F,1,=P(x,y,f(y),，则,F,1,=P(a,g(a),f(g(a);,令,F,2,=P(a,g(x),z),，则,F,2,=P(a,g(a),f(g(a);,可见，,F,1,=F,2,，所以说,为,F,的一个合一。,15,五、冲突消解策略,1.,推理过程中匹配的三种情况：,已知事实不能与知识库中的任何知识匹配；,已知事实恰好与知识库中的一个知识匹配；,已知事实可与知识库中的多个知识匹配，或多个已知事实与一个知识匹配，或多个已知事实与多个知识匹配。,我们称,3,）为发生了冲突，需要进行冲突消解，所用的方法称为冲突消解策略；,2.,产生式系统的冲突：,正向推理：多条规则前件与已知事实匹配，或多组已知事实与一 条规则前件匹配，或者两者同时出现；,逆向推理：多条规则后件与同一假设匹配，或多条规则后件与多个假设匹配；,16,3.,冲突消解策略,基本思想：冲突消解的任务是解决冲突。,对正向推理来说，将决定选择,哪一组已知事实,来激活,哪一条产生式规则,，使它用于当前的推理，产生其后件指出的结论或执行相应的操作。,对于逆向推理来说，它将决定用,哪一个假设,与,哪一个产生式规则,的,后件,进行匹配，从而推出相应的前件，作为新的假设。,用对知识进行排序的思想进行冲突消解，常用的有以下几种：,按针对性排序；,按已知事实的新鲜性排序；,按匹配度排序；,根据领域问题的特点排序等。,17,5.2,自然演绎推理,从一组已知为真的事实出发，直接运用经典逻辑中的推理规则推出结论的过程。,在这种推理中，最基本的推理规则是,P,规则，,T,规则，假言推理和拒取式推理等。,P,规则：在推理的任何步骤上都可以引入前提；,T,规则：若前面步骤中推出了公式,S,，则可把,S,引入推理过程中；,假言推理：,P,，,P,Q,=Q,；,拒取式推理：,P,Q,，,Q,=P,在自然演绎推理中，需要避免两类错误：,肯定后件：,P Q,，,Q=true P=true,否定前件：,P Q,，,P=false Q=false,天下雨,地湿,地湿,天下雨,天不下雨,地不湿,?,?,18,【,例,5.1】,设已知如下事实：,A,，,B,，,AC,，,BC D,，,DQ,求证：,Q,为真。,证明：,A,，,AC,=,C,B,，,C,=,BC,B C,，,B CD=D,D,，,DQ=Q,P,，假言推理,引入合取词,T,，假言推理,T,，假言推理,因此，,Q,为真。,19,【,例,5.2】,设已知如下事实：,只要是需要编程序的课，王程都喜欢。,所有的程序设计语言课都是需要编程序的课。,C,是一门程序设计语言课。,求证：王程喜欢,C,这门课。,证明：,Prog(x)x,是需要编程序的课。,（,1,）定义谓词,Like(x,y)x喜欢y。,Lang(x)x是一门程序设计语言课。,（,2,）创建问题与的合式谓词公式,（,3,）推理,20,分析：,1.,优点：,定理证明过程自然，易于理解，并且有丰富的推理规则可用。,2.,缺点：,容易产生,知识爆炸,，推理过程中得到的,中间结论,一般按指数规律递增，对于复杂问题的推理不利，甚至难以实现。,21,5.3,归结演绎推理,5.3.1,子句集及其化简,5.3.2,鲁宾逊归结原理,5.3.3,归结演绎推理的归结策略,5.3.4,利用归结原理求取问题的答案,5.3.5,归结策略,22,如何证明,PQ,永真？,P,Q,永真,(P Q),不可满足,(P,Q)(P Q)P Q,因此要证明,P,Q,永真,，只需证明,P Q,不可满足。,23,5.3.1,子句集及其化简,一、定义,：,1.,在谓词逻辑中，把原子谓词公式及其否定统称为,文字,。,2.,任何文字的析取式称为,子句,。,例：,P(x)Q(x),，,P(x)Q(x,g(x),都是子句。,3.,不含任何文字的子句称为,空子句,。（永假，不可满足）,4.,由子句构成的集合称为,子句集,，,任何谓词公式都可化为子句集,。,将谓词公式化为子句集的步骤：,1,）消去谓词公式中的“”和“,”；,2,）将“”移到紧靠谓词的位置上；,3,）重新命名变元名，不同量词约束不同变元；,4,）消去存在量词：,若“”不在“”的辖域内，直接用一个新个体常量替换；,若,“,”,在若干,“,”,的辖域内，用,Skolem,函数,f,（,x,）替换,y,，,g,（,x,）替换,z,。,24,5,）把全称量词全部移到公式的左边；,6,）把公式化为,Skolem,标准形；,(x1)(x2),(xn)M,，其中,M,是子句的合取式。,7,）消去全称量词；,8,）对变元命名，使不同子句中的变元不同名；,9,）消去合取词。,例：,(x)(y)P(x,y),(y)(Q(x,y)R(x,y),),定理,：设有谓词公式,F,，其标准形的子句集为,S,，则,F,不可满足的充要条件是,S,不可满足。（即谓词公式,F,与其子句集,s,在不可满足性上是等价的）,25,归结原理,又称为消解原理，思想是通过证明子句集的不可满足性，从而实现定理证明。,由于子句集中子句之间是合取关系，只要有一个子句不可满足，则,子句集不可满足,。,证明方法：,检查子句集,S,中是否包含空子句，若包含，则,S,不可满足；若不包含，就在子句集中选择合适的子句进行,归结,，一旦通过,归结,能推出空子句，就说明子句集,S,是不可满足的。,归结：分为命题逻辑和谓词逻辑两种来探讨。,5.3.2,鲁宾逊归结原理,26,一、命题逻辑中的归结原理,定义：若,P,是原子谓词公式，则称,P,与,P,为,互补文字,。,设,C,1,和,C,2,是子句集中的任意两个子句，如果,C,1,中的文字,L,1,与,C,2,中的文字,L,2,互补，那么从,C,1,和,C2,中分别消去,L1,和,L2,，并将二个子句中余下的部分析取，构成一个新子句,C,1,2,，则称这一过程为归结，称,C1,2,为,C1,和,C2,的归结式，称,C1,和,C2,为,C1,2,的亲本子句。,例：设,C1=P,QR,，,C2=QS,，通过归结可得：,C12=,P,R S,例：设,C1=P,，,C2=P,，通过归结可得：,C12=NIL,（空子句）。,定理,：归结式,C12,是其亲本子句的,C1,与,C2,的逻辑结论。,推论,1,：设,C1,与,C2,是子句集,S,中的两个子句，,C12,是它们的归结式，若用,C12,代替,C1,和,C2,后得到新子句集,S1,，则由,S1,的不可满足性可推出原子句集,S,的不可满足性，即：,S1,的不可满足性 ,S,的不可满足性,27,推论,2,：,设,C1,与,C2,是子句集,S,中的两个子句，,C12,是它们的归结式，若把,C12,加入,S,中，得到新子句集,S2,，则,S,与,S2,在不可满足的意义上是等价的，即：,S2,的不可满足性,S,的不可满足性,二、谓词逻辑中的归结原理：,在谓词逻辑中，由于子句中含有变元，所以不像命题逻辑那样可直接消去互补文字，而需要先对变元进行代换，然后才能进行归结。例：,C1=P(x)Q(x),C2=P(a)R(y),由于,P(x),与,P(a),不同，所以,C1,与,C2,不能直接进行归结，若用,a/x,对两个子句分别进行代换：,C1a/x=P(a)Q(a),C2a/x=P(a)R(y),此时进行归结，消去,P(a),与,P(a),，得：,Q(a)R(y),28,5.3.3,归结演绎推理,欲证,Q,为,P1,P2,Pn,的逻辑结论，需证,(,P1P2,Pn,),Q,不可满足，用归结原理证明定理的过程叫,归结反演,。,步骤：设,F,为已知前提的公式集，,Q,为目标公式（结论），用归结反演证明,Q,为真的步骤如下：,否定,Q,，得到,Q,；,Q,并入,F,中，得到,F,，,Q,；,把公式集,F,，,Q,化为子句集,S,；,对,S,的子句进行归结，并将归结式并入,S,中，如此反复，出现空子句，则证明,Q,为真，停止归结。,例,1,：试证明,G,是,F,的逻辑结论。,已知：,F:,(x)(y)(A(x,y),B(y),),(y)(C(y)D(x,y),),G:(x)C(x)(x)(y)(A(x,y)B(y),29,5.3.3,归结演绎推理,例,3,：设有下列知识：,己知：规则,1,：任何人的兄弟不是女性；,规则,2,：任何人的姐妹必是女性；,事实：,Mary,是,Bill,的姐妹；,用谓词公式表示上述知识，并用归结原理证明：,Mary,不是,Tom,的兄弟。,例,2,：某公司招聘工作人员，,A,，,B,，,C,三人应试，经面试后公司表示如下想法,:,(1),三人中至少录取一人；,(2),如果录取,A,而不录取,B,，则一定录取,C,。,(3),如果录取,B,，则一定录取,C,。求证：公司一定录取。,30,5.3.4,利用归结原理求取问题的答案,步骤：,已知用谓词公式表示，化为子句集,S,；,待求解问题用谓词公式表示，将其否定与谓词,ANSWER,析取，,ANSWER,的变元必须与问题公式的变元一致。,将此析取式化为子句集，并入,S,中，得到子句集,S1,；,对,S1,应用归结原理进行归结；,若得到归结式,ANSWER,，则答案在,ANSWER,中。,例：已知小张和小李是同班同学，若,x,和,y,是同班同学，则,x,上课的教室也是,y,上课的教室。知小张在,203,上课，问小李在哪上课？,解：已知用谓词公式表示，并化为子句集：,定义谓词：,C(x,y):x,和,y,是同班同学；,At(x,u):x,在,u,处上课。,31,谓词公式：,C(Zhang,Li),(x)(y)(u)(C(x,y),At(x,u),At(y,u),At(Zhang,203),化为子句集：,C(Zhang,Li),.(1),C(x,y)At(x,u)At(y,u).(2),At(Zhang,203)(3),求解问题：,At(Li,z)ANSWER(z).(4),(1)-(4),构成了子句集,S1,，将其进行归结的过程如下：,(1),与,(2),归结，利用代换,Zhang/x,Li/y,，得：,At(Zhang,u)At(Li,u),(5),(5),与,(3),归结，利用代换,203/u,，得：,At(Li,203)(6),(6),与,(4),归结，利用代换,203/z,，得：,ANSWER(203),所以，小李在,203,上课。,32,例：,A,，,B,，,C,中有人从不说真话，有人从不说谎话，,A,说：,“,B,和,C,是说谎者,”,。,B,说：,“,A,和,C,是说谎者,”,。,C,说：,“,A,和,B,至少一人说谎,”,。问：谁说真话？谁说假话？,解：定义谓词,T,（,x,）：表示,x,说真话。,33,5.3.5,归结策略,对子句集进行归结时，关键是从子句集中找出可进行归结的一对子句。由于不知道哪两个子句可以进行归结，更不知道哪些子句的归结可以尽快得到空子句，必须,对子句逐对进行比较,，浪费了时间和空间。,因此提出归结策略，两大类：,删除策略和限制策略,。,首先，我们看归结的一般过程。,34,一、归结的一般过程,设有子句集,S=C1,C2,C3,C4,，归结的一般过程如下：,从,C1,开始，逐个与,C2,，,C3,，,C4,比较，看哪两个子句可进行归结，若能找到，则求出归结式。一轮结束，得到一级归结式。,再从,C1,开始，用,S,中的子句分别与一级归结式中的子句逐个进行比较，归结，得到二级归结式。,仍从,C1,开始，用,S,中的子句及一级归结式中的子句逐个与第二级归结式中的子句进行比较，得第三级归结式。,如此继续，直到出现空子句或不能继续归结时为止，只要子句集是不可满足的，上述的归结过程一定会归结出空子句而终止。,举例（板书）,35,二、删除策略,删除策略是要删除无用子句，缩小归结的范围，减少比较次数，从而提高归结的效率。,纯文字,删除法：某文字,L,在子句集中不存在与之互补的,L,，则删去含纯文字,L,的子句。,重言式,删除法：一个子句中同时包含互补文字时，则该子句删去。,包孕,删除法：若,C1 C2,，则称,C1,包孕于,C2,，删去,C2,。,如：,P(y),包孕于,P(x),Q(x),=x/y,则删去,P(x),Q(x),因为,P(y),的真值能够决定两个子句构成的子句集的真值。,36,三、支持集策略,思想：每一次归结时，亲本子句中,至少有一个是由目标公式的否定得到的子句,或者是,它们的后裔,。（完备策略）,例：板书,线性输入策略,思想：参加归结的子句中必须,至少有一个是初始子集中的子句,。在归结反演中，初始子句集就是由已知前提及结论的否定化来的子句集。,例：板书,单文字策略,：参加归结的两个子句中至少有一个单文字子句。,祖先过滤形策略,：满足其一：,C1,与,C2,至少一个是初始子句集中的子句；若都不是，则一个应是另一个的祖先。,37,本章作业,张某被盗，公安局派出五个侦查员去调查。研究案情时，侦查员,A,说,“,赵与钱中至少有一人作案,”,；侦查员,B,说,“,钱与孙中至少有一人作案,”,；侦查员,C,说,“,孙与李中至少有一人作案,”,；侦查员,D,说,“,赵与孙中至少有一人与此案无关,”,；侦查员,E,说,“,钱与李中至少有一人与此案无关,”,。如果这五个侦查员的话都是可信的，试用归结演绎推理求出谁是盗窃犯。,38,下课了。,追,求,