AI 经典逻辑推理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.代换：代换是形如t1/x1,t2/x2,tn/xn的有限集合。其中，t1,t2,tn是项，x1,x2,xn是互不相同的变元。ti/xi：用ti代换xi；不允许：ti与xi相同；xi循环地出现在另一个tj中。例：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=F1,F2,Fn，若存在一个代换使得：F1=F2=Fn，则称为公式集F的一个合一，且称F1,F2,Fn是可合一的。例：F=P(x,y,f(y),P(a,g(x),z)，证明=a/x,g(a)/y,f(g(a)/z是F的一个合一。令F1=P(x,y,f(y)，则F1=P(a,g(a),f(g(a);令F2=P(a,g(x),z)，则F2=P(a,g(a),f(g(a);可见，F1=F2，所以说为F的一个合一。,15,五、冲突消解策略,1.推理过程中匹配的三种情况：已知事实不能与知识库中的任何知识匹配；已知事实恰好与知识库中的一个知识匹配；已知事实可与知识库中的多个知识匹配，或多个已知事实与一个知识匹配，或多个已知事实与多个知识匹配。我们称3）为发生了冲突，需要进行冲突消解，所用的方法称为冲突消解策略；2.产生式系统的冲突：正向推理：多条规则前件与已知事实匹配，或多组已知事实与一条规则前件匹配，或者两者同时出现；逆向推理：多条规则后件与同一假设匹配，或多条规则后件与多个假设匹配；,16,3.冲突消解策略基本思想：冲突消解的任务是解决冲突。对正向推理来说，将决定选择哪一组已知事实来激活哪一条产生式规则，使它用于当前的推理，产生其后件指出的结论或执行相应的操作。对于逆向推理来说，它将决定用哪一个假设与哪一个产生式规则的后件进行匹配，从而推出相应的前件，作为新的假设。用对知识进行排序的思想进行冲突消解，常用的有以下几种：按针对性排序；按已知事实的新鲜性排序；按匹配度排序；根据领域问题的特点排序等。,17,5.2自然演绎推理从一组已知为真的事实出发，直接运用经典逻辑中的推理规则推出结论的过程。在这种推理中，最基本的推理规则是P规则，T规则，假言推理和拒取式推理等。P规则：在推理的任何步骤上都可以引入前提；T规则：若前面步骤中推出了公式S，则可把S引入推理过程中；假言推理：P，PQ=Q；拒取式推理：PQ，Q=P,在自然演绎推理中，需要避免两类错误：肯定后件：PQ，Q=trueP=true否定前件：PQ，P=falseQ=false,?,?,18,【例5.1】设已知如下事实：A，B，AC，BCD，DQ求证：Q为真。,证明：,A，AC=C,B，C=BC,BC，BCD=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永真？,因此要证明PQ永真，只需证明PQ不可满足。,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为互补文字。设C1和C2是子句集中的任意两个子句，如果C1中的文字L1与C2中的文字L2互补，那么从C1和C2中分别消去L1和L2，并将二个子句中余下的部分析取，构成一个新子句C12，则称这一过程为归结，称C12为C1和C2的归结式，称C1和C2为C12的亲本子句。例：设C1=PQR，C2=QS，通过归结可得：C12=PRS例：设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的逻辑结论，需证(P1P2Pn)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中的子句及一级归结式中的子句逐个