《人工智能与专家系统(第二版)》第4章 逻辑推理484

单击此处编辑母版标题样式,单击此处编辑母版文本样式,人工智能与专家系统(第二版）,中国水利水电出版社,人工智能与专家系统,第4章 逻辑推理,4.1 推理的基本概念,4.2 归结演绎推理,4.4 归结反演的改进策略,4.3 基于归结反演的问题求解,4.1 推理的基本概念,4.1.1 推理方式及其分类,4.1.2 推理的控制策略,4.1.3 模式匹配及其变量代换,4.1.1 推理方式及其分类,1 演绎推理、归纳推理、默认推理,演绎推理:,是从全称判断推导出特称判断的,过程，即由一般性知识推理适合于某一具体情况,的结论，是一种从一般到个别的推理。,归纳推理:,是从足够多的事例中归纳出一般,性结论的推理过程，是一种从个别到一般的推理。,默认推理:,是在知识不完全的情况下假设某,些条件已经具备所进行的推理,2 确定性推理、不确定性推理,确定性推理:,是指推理时所用的知识,都是精确的，推出的结论也是确定的，其,真值或者为真，或者为假。,不确定性推理:,是指推理时所用的知识,不都是精确的，推出的结论也不完全是肯,定的，其真值位于真与假之间。,3 单调推理、非单调推理,单调推理:,随着推理过程向前推进及新,知识的进入，推出的结论呈单调增加的,趋势。,非单调推理:,由于新知识的加入，不仅,没有加强已推出的结论，反而要使得推理,退回到前面的某一步，重新开始。,4 启发式推理、非启发式推理,启发式推理:,运用与问题有关的启,发性知识，且能加快推理进程的推理。,5 基于知识的推理、直觉推理,基于知识的推理:,根据已掌握的事,实，通过运用知识进行推理。,直觉推理:,根据常识进行的推理。,4.1.2 推理的控制策略,1 推理方向,（1）正向推理,（2）逆向推理,（3）混合推理,2 求解策略,推理的求解策略:,推理是只求一个,解，还是求所有解以及最优解等。,3 限制策略,推理的限制策略:,在控制策略中指定推,理的限制条件，以对推理的深度、宽度、,时间、空间等进行限制。,4 冲突消解策略,在推理过程中，可能发生已知事实可,与知识库中的多个知识匹配成功；或者有,多个已知事实可与知识库中的多个知识匹,配成功。称这种情况为发生了,冲突,。,冲突消解:,需要按一定策略解决冲突，,以便从中挑选一个知识用于当前的推理，称,这一解决冲突的过程为,冲突消解,。,解决冲突所用的方法称为,冲突消解策略,。,4.1.3 模式匹配及其变量代换,模式匹配:,两个知识模式（如两个谓词,公式、两个框架片断等）比较，检查这两个知,识模式是否完全一致或近似一致。如果两者完全,一致，或者虽不完全一致但其相似程度落在指定,的限度内，就称它们是,可匹配,的，否则为,不可匹,配。,确定性匹配:,两个知识模式完全一致，或者经过变量代换后变得完全一致。,例:设有如下两个知识模式：,P,1,：Father（李四，李小四）and Man (李小四),P,2,：Father(,x,y,) and Man (,y,),若用常量“李四”代换变量,x,，用常量,“李小四”代换变量,y,，则P,1,与P,2,就变得完全,一致。,定义4.1,代换,是形如,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,中。,定义4.2,设,=,t,1,/,x,1,t,2,/,x,2, ，,t,n,/,x,n,=u,1,/,y,1, u,2,/,y,2, ，u,m,/,y,m,是两个代换，则此两个代换的复合也是一个代换，,它是从,t,1,/,x,1,t,2,/,x,2, ,t,n,/,x,n,u,1,/,y,1,u,2,/,y,2, ，,u,m,/,y,m,中删去如下两种元素：,t,i,/,x,i,当,t,i,=,x,i,u,i,/,y,i,当,y,i,x,1,x,2, ，,x,n,后剩下的元素所构成的集合，记为,定义4.3,设有公式集F=F,1, F,2, , F,n,若,存在一个代换,使得,F,1,=F,2,= =F,n,则称,为公式集F的一个合一，且称F,1, F,2, ,F,n,是可合一的。,定义4.4,设,是公式集F的一个合一，,如果对任一个合一,都存在一个代换,，,使得,=,。,则称,是公式集F的最一般合一(mgu)。,差异集：,设有如下两个谓词公式：,F,1,：P（,x,y,z,）,F,2,：P (,x,f,(A),h,(B) ),分别从F,1,与F,2,的第一个符号开始比较，得到第一个差异,集：,D,1,=,y,f,(A),当继续比较，又发现F,1,中的,z,与F,2,中的,h,(B)不同，则得到,第二个差异集：,D,2,=,z,h,(B),求最一般合一算法:,（1）初始化，令,k,=0, F,k,=F,k,=。其中，是代换空,集。,（2）若F,k,只含一个表达式，则算法停止，,k,就是最一,般合一；否则转步骤（3）。,（3）找出F,k,的差异集D,k,。,（4）若D,k,中存在变元,x,k,和项,t,k,，且,x,k,不在,t,k,中出现，则：,k,+1,=,k,。,t,k,/,x,k,F,k,+1,=F,k,t,k,/,x,k,k,=,k,+1,转步骤（2）；否则， 算法终止，F的最一般合一不存在。,例4.1,设有公式集：F=P(A,x,f,(,g,(,y,), P(,z,f,(,z,),f,(,u,) ，求其最一般合一。,解：,初始化，令,k,=0，,0,=,，,F,0,=F= P (A,x, f,(,g,(,y,), P(,z, f,(,z,),f,(,u,) ,Loop 1：,F,0,含有2个表达式，故,0,不是最一般合一，,F,0,的差异集D,0,=A，,z,， 可有代换A/,z,，,1,=,0,A/,z,=A/,z,F,1,=F,0,A/,z,= P(A,x,f,(,g,(,y,), P(A,f,(A),f,(,u,) ,Loop 2：,F,1,含有2个表达式，故,1,不是最一般合一，,F,1,的差异集D,1,=,x,，,f,(A)，可有代换,f (,A)/,x,，,2,=,1,。,f,(A)/,x,=A/,z, 。,f,(A)/,x,=A/,z,f,(A)/,x,F,2,=F,1,f,(A)/,x,= P(A,f,(A),f,(,g,(,y,), P(A,f,(A),f,(,u,),Loop 3：,F,2,的差异集D,2,=,g,(,y,)，,u,，可有代换,g,(,y,)/,u,，,3,=,2,。,g,(,y,)/,u,= A/,z,f,(A)/,x, 。,g,(,y,)/,u,=A/,z,f,(A)/,x,g,(,y,)/,u,F,3,=F,2,g,(,y,)/,u,= P(A,f,(A),f,(,g,(,y,), P(A,f,(A),f,(,g,(,y,) ,= P(A,f,(A),f,(,g,(,y,) ,Loop 4：,F,3,中只含有一个表达式，故算法成功终止。公式集,F的最一般合一为,3,=A/,z,f,(A)/,x,g,(,y,)/,u,4.2 归结演绎推理,4.2.1 谓词公式化为子句集的方法,4.2.2 归结原理,4.2.3 归结反演,定理证明的实质是对已知前提P和待证,结论Q证明PQ的永真性。,应用反证法的思想可把关于永真性的,证明转化为不可满足性的证明，即证明,PQ是不可满足的。,4.2.1 谓词公式化为子句集的方法,定义4.5,在谓词逻辑中，把原子谓词,公式及其否定统称为,文字,。任何文字的析,取式称为,子句,。,定义4.6,不包含任何文字的子句称为,空子句,。,由于空子句不含有文字，它不能被任,何解释满足，所以空子句是永假的，不可,满足的。,谓词公式化成子句集的步骤:,（1）消去蕴涵连词,利用下述等价关系消去谓词公式中的,蕴涵连词“”：,PQ PQ,（2）减小否定连词的辖域,利用下述等价关系把“,”移到紧靠谓,词的位置上：,（3）约束变元标准化,（4）消去存在量词,若存在量词不在全称量词的辖域内，则,用一个个体常量替换受该存在量词约束的变,元。,若存在量词位于一个或多个全称量词的辖,域内，则需要用,Skolem,函数,f,(,x,1,x,2, ，,x,n,),替换受该存在量词约束的变元,y,。,（5）组成全称量词前缀,（6）利用等价关系把母式化为Skolem标准,形：,（7）消去全称量词。,（8）对变元更名，使不同子句中的变元不,同名。,（9）消去合取连词，得到子句集。,例4.2,请将下述谓词公式化为子句集：,解,：,4.2.2 归结原理,子句集中的子句之间是合取关系，,其中只要有一个子句不可满足，子句集就,不可满足。空子句是不可满足的。因此，,若一个子句集中包含空子句，则这个子句,集是不可满足的。,1. 命题逻辑中的归结原理,定义4.7,若P是原子谓词公式，则称P,与P为,互补文字,。,定义4.8,设C,1,与C,2,是子句集中的任意,两个子句，如果C,1,中的文字L,1,与C,2,中的文字,L,2,互补，那么从C,1,和C,2,中分别消去L,1,和L,2,，,并将二个子句中余下的部分析取，构成一个新,子句C,12,，则称这一过程为,归结,，称C,12,为C,1,和,C,2,的归结式，称C,1,和C,2,为C,12,的,亲本子句,。,定理4.2,归结式C,12,是其亲本子句C,1,与C,2,的,逻辑结论。,推论4.1,设C,1,与C,2,是子句集S中的两个子句，,C,12,是它们的归结式，若用C,12,代替C,1,和C,2,后得到,新子句集S,1,，则由S,1,的不可满足性可推出原子句,集S的不可满足性，即,S,1,的不可满足性 S的不可满足性,推论4.2,设C,1,与C,2,是子句集S中的两,个子句，C,12,是它们的归结式，若把C,12,加,入S中，得到新子句集S,2,，则S与S,2,在不可,满足的意义上是等价的，即,S,2,的不可满足性 S的不可满足性,2. 谓词逻辑中的归结原理,在谓词逻辑中，由于子句中含有变元，所,以不可直接消去互补文字，先对变元代换，才能,进行归结。例如：,用最一般合一：,=A /,x,对两个子句分别进行代换：,C,1,=P(A)Q(A) C,2,=P(A)R(,y,),得到归结式：Q(A) R(,y,),定义4.9,设C,1,与C,2,是两个没有相同变元,的子句，L,1,和L,2,分别是C,1,和C,2,中的文字，若,是L,1,和L,2,的最一般合一，则称,C,12,=(C,1,-L,1,)(C,2,-L,2,),为C,1,和C,2,的,二元归结式,，L,1,和L,2,称为,归结式,的文字。,例4.3,设C,1,=P(A)Q(,x,)R(,x,)，C,2,=P(,y,)Q(B)，给出C,1,和C,2,的归结式。,上述归结过程可以用归结树表示如图4.1所示。,图4.1 例4.3的一种归结树,若选L,1,= Q(,x,), L,2,=Q(B),=B/,x, 则可得：,C,12,= (P(A), Q(B), R(B)- Q(B)( P(,y,), Q(B)-Q(B),=(P(A), R(B)(P(,y,),=P(A), R(B), P(,y,),=P(A)R(B)P(,y,),上述归结过程的归结树如图4.2所示。,图4.2 例4.3的另一种归结树,4.2.3 归结反演,应用归结原理证明结论为真的过程称为,归结反演,。,设F为已知前提的公式集，Q为目标公式（结论），,用,归结反演证明Q为真的步骤,：,否定Q，得到 Q；,把 Q并入到公式集F中，得到F， Q；,把公式集F， Q化为子句集S；,应用归结原理对子句集S中的子句进行归结，并把,每次归结得到的归结式都并入S中。如此反复进行，若出,现了空子句，则停止归结，此时就证明了Q为真。,例4.6,已知,求证：,G,是F的逻辑结论。,证,：,首先把F和,G,化为子句集,图4.4 例4.6的归结树,例4.7,在第2章例2.4中曾经得到如下公式：,自然数都是大于零的整数。,所有整数不是偶数就是奇数。,偶数除以是整数。,求证：所有自然数不是奇数就是其一半为整数的数。,证,：,首先把求证的问题用谓词公式表示出来：,把F,1,，F,2,，F,3,及,G,化成子句集：,(1),N(,x,) GZ(,x,),(2),N(,u,) I(,u,),(3),I(,y,)E(,y,)O(,y,),(4),E(,z,)I(s(,z,),(5)N(,t,),(6),O(,t,),(7),I(s(,t,),图4.5 例4.7的归结树,4.3 基于归结反演的问题求解,问题求解的步骤,：,把已知前提用谓词公式表示，并且,化为相应的子句集S。,把待求解的问题也用谓词公式表,示，把它的否定式与谓词ANSWER构成一,个析取式，ANSWER的变元数量和变元名,必须与问题公式的变元一致。,把此析取式化为子句集，并且把该,子句集加入到子句集S中，得到子句集S,。,对S,应用归结原理进行归结。,若在归结树的根节点中仅得到归结,式ANSWER，则答案就在ANSWER中。,例4.8,已知,F,1,：王（Wan,g,）先生是小李（Li）的老师。,F,2,：小李与小张（Zhan,g,）是同班同学。,F,3,：如果,x,与,y,是同班同学，则,x,的老师也是,y,的老师。,求：小张的老师是谁？,解,：,1,定义谓词,T(,x,y,),x,是,y,的老师。,C(,x,y,),x,与,y,是同班同学。,2 谓词公式表示,目标公式G的否定式与ANSWER的析取式为：,3 化为子句集,(1)T(Wan,g, Li),(2) C (Li, Zhang,),(3) C(,x,y,) T(,z,x,)T(,x,y,),(4) T(,u, Zhang,)ANSWER(,u,),图4.6 例4.8的归结树,例4.9,设A，B，C三人中有人从不说,真话，也有人从不说假话，某人向这三人,分别提出同一个问题：谁是说谎者？A答：,“B和C都是说谎者”；B答：“A和C都是说,谎者”；C答：“A和B中至少有一个是说谎,者”。求谁是老实人，谁是说谎者？,解,：1,定义谓词：,T(,x,) 表示,x,说真话,。,2 谓词公式表示,如果A说的是真话，则有：,T(A) T(B)T(C),如果A说的是假话，则有：, T(A) T(B)T(C),对B和C说的话作相同的处理，可得：,T(B) T(A),T(C),T(B) T(A)T(C),T(C ) T(A),T(B),T(C ) T(A)T(B),3 化成子句集S,(1) T(A) T(B),(2) T(A) T(C),(3)T(A)T(B)T(C),(4) T(B) T(C),(5) T(C ) T(A) T(B),(6)T(C )T(A),(7)T(C )T(B),求谁是老实人的目标公式：(,x,)T(,x,),(8) T(,x,)ANSWER(,x,),图4.7 求谁是老实人的归结树,证明A和B不是老实人：,设A不是老实人，则有,T(A)，把它的否定,式T(A) 加入到S中，得到子句集S,2。,对S,2,归结，从而证明了A不是老实人。,同理，可证明B也不是老实人。,图4.8 例4.9证明A不是老实人的归结树,4.4 归结反演的改进策略,4.4.1 删除策略,4.4.2 限制策略,4.4.1 删除策略,1 纯文字删除,如果某文字L在子句集中不存在可与之互补,的文字L，则称该文字为,纯文字,。,在归结时纯文字不可能被消去，因而用包含,它的子句进行归结时不可能得到空子句。例如，,设有子句集：,S= PQR, QR，Q, R ,其中，P是纯文字，因此可将子句 PQR从S,中删去。,2 重言式删除,如果一个子句中同时包含互补文字时，则称,该子句为,重言式,。,例如,P(,x,) P(,x,),P(,x,)Q(,x,) P(,x,),都是重言式。,重言式是真值为真的子句。对于一个子句集来说，,增加或者删去一个真值为真的子句都不会影响它的不可,满足性，因而可从子句集中删去重言式。,3 包孕删除,设有子句C,1,和C,2,，如果存在一个代换,，使得 则称C,1,包孕于C,2,。,例如：,P(,x,) 包孕于 P(,y,)Q(,z,),=,y,/,x,或称,P(,x,) 被 P(,y,)Q(,z,) 包孕,把子句集中被包孕的子句删去后，不会影响,子句集的不可满足性，可从子句集中删去被其它,子句包孕的子句。,4.4.2 限制策略,1 支持集策略,支持集策略,对参加归结的子句提出了,如下限制：每一次归结时，亲本子句中至,少应有一个是由目标公式的否定所得到的,子句，或者是它们的后裔。,支持集策略是完备的。,例4.10,设有初始子句集：,S=I(,x,) R(,x,),I(A),R(,y,)L(,y,),L(A),其中 I(,x,)R(,x,)是目标公式否定得到的,子句。,图4.9 支持集策略归结树,2 线性输入策略,线性输入策略,对参加归结的子句提出,了如下限制：参加归结的两个子句中必须,至少有一个是初始子句集中的子句。,线性输入策略是不完备的。,例4.11,应用线性输入策略对例4.10的初始子句集进行归结。,图4.10 线性输入策略归结树,3 单文字子句策略,3 单文字子句策略,如果一个子句只包含一个文字，则称,它为,单文字子句,。单文字子句策略要求参,加归结的两个子句中必须有一个是单文字,子句。,单文字子句策略是不完备的。,例4.12,对例4.10给出的初始子句集按单文字子句策略进行归结。,图4.11 单文字子句策略的归结树,5 祖先过滤形策略,祖先过滤形策略,要求两个子句C,1,和C,2,满足下述两个条件中的任意一个条件：, C,1,与C,2,中至少有一个是初始子句集,中的子句。, 如果两个子句都不是初始子句集中,的子句，则一个应是另一个的祖先。,祖先过滤形策略是完备的。,例,4.13,有子句集,S=,P(,x,)Q(,x,), P(,y,)Q(,y,),P(,u,)Q(,u,),P(,t,),Q(,t,),用祖先过滤形策略进行归结。,图4.12 祖先过滤形策略归结树,演讲完毕，谢谢观看！,