week8北航6系人工智能课件.ppt

第三章基于逻辑的问题求解方法,第8周,认知区域功能研究学派-,10s:目标实现1s:简单操作合成100ms:初级熟练操作10ms:符号存取,理性带认知带神经带,逻辑学派、知识工程学派认知学派（代表作：-SOAR）联结学派,认知学派的层次划分,基于逻辑的问题求解方法,逻辑是人工智能的重要基础一阶逻辑的基本概念回顾基于一阶逻辑的演绎推理技术应用逻辑系统,逻辑是人工智能的重要基础,人工智能遵循符号原理：将所有与问题有关的对象、关系以及概念等进行形式化的表示和处理。,一阶逻辑满足形式化表达和处理要求：类自然语言的形式化的符号语言（谓词公式描述）强有力的推理方法（公理化推理方法、归结法）；坚实的理论证明基础（语义模型、推理的可靠性、完备性研究等）。,逻辑是人工智能的重要基础,一阶逻辑对AI的贡献：提出了陈述性知识表示方式；将知识描述与知识处理相分离；基于一阶逻辑扩展了多种应用逻辑-如时序(p53)、模糊、非单调等多种应用逻辑。,基于逻辑的问题求解方法,逻辑是人工智能的重要基础一阶逻辑的基本概念回顾演绎推理技术应用逻辑系统,字符表,一阶逻辑的基本概念回顾,一阶谓词逻辑知识表示方法,项、合式谓词公式,演绎推理方法,解释与赋值,一阶谓词逻辑的符号体系-字符表,常元:变元:函数(词)符:谓词符:逻辑联词:量词:其它:,a,b,c,.;A,B,C,.;,x,y,z,.;,Fn,gm,.;e.g.,f1(x):x的父亲。,Pn,Qm,R,.;e.g.,brother2(x,y)。,。,。,(,),，。,一阶逻辑的基本概念回顾,一阶谓词逻辑的符号体系字符表项、谓词合式公式等价公式演绎推理方法,项、谓词合式公式,项：,常元:a,b,;变元:x,y,.;函词:fn(x1,x2,xn)，其中，xi是项。,合适谓词公式,原子公式Pn(x1,x2,xn)是合式谓词公式，其中，xi是项。,设:A,B是合式谓词公式，则A，AB，AB，AB,(x)A是合式谓词公式。,例：(x)(P(x)(y)(R(y)S(x,y),等价公式,等价公式,(p41-42),得摩根定律：(PQ)PQ(PQ)PQ分配律：R(PQ)（RP）(RQ)R(PQ)（RP）(RQ)蕴含等价式：PQPQ.；量词转换律:(x)P(x)(x)P(x)(x)P(x)(x)P(x)全称量词消去规则：（x)P(x)P(y)存在量词消去规则：（x)P(x)P(c)c为常元.。,演绎推理,演绎推理方法,推理：根据一定准则，由前提判断导出称为结论的思维过程。,演绎推理、归纳推理、类比推理,推理方式：A1,A2,An|=B,iff,（x）（P(x)Q(x)）P(a)-Q(a)，,推理规则：,推理过程：反复运用等价公式、推理规则对已知的谓词公式进行变换，得到所需的逻辑结论的过程。,归原理结,解释与赋值,解释定义:一个解释I由以下四部分组成。（1）指定一个非空集合DI，称为I的论域；（2）对于每个常元a，指定DI中的一个元素aI；（3）对于每个n元函数符号f，指定DI上的一个n元运算符fI（4）对于每个n元谓词符号P，指定DI上的一个n元谓词PI,解释与赋值,赋值定义:设I是一个解释，将所有变元组成的集合映射到论域DI的函数称为I中的赋值v。,解释和赋值共同规定了项和公式的意义。,例：设DI为自然数集合，fI是自然数乘法，gI是自然数加法，aI=2，I中赋值v使v(x)=1。项f(g(a,x),a)在I和v下的意义：I（f(g(a,x),a)）(v)=?,基于逻辑的问题求解方法,逻辑是人工智能的重要基础一阶逻辑的基本概念回顾机器演绎推理技术应用逻辑系统,机器演绎推理技术归结法,谓词公式的规范化谓词公式的合取范式合取范式的子句集形式推理过程规范化命题逻辑归结原理变量置换与合一谓词归结证明系统的相关技术,谓词公式的子句形式,文字：子句：空子句：基子句：,子句与合适公式对应关系,原子公式及其否定：P(x1,x2,xn)，Q(x1,x2,xm),文字的有穷集合：P(x1,x2,xn)，Q(x1,x2,xm）,不含任何变元的子句：P(A),R(b,f(b),空子句永假公式F非空子句L1,L2,Ln析取式L1L2Ln子句集SA=A1,A2,An无型前束合取范式,子句的标准范式,无型前束合取范式:,（Q1x1）(Q2x2）（Qnxn）M其中，Qi：全称量词；xi：变元母式：M=(A11A12A1n)(Am1Am2Aml)是合取范式，其中,Aij是文字。,子句集：S=A11A12A1n，Am1Am2Aml,合式谓词公式化子句集步骤(p43),子句的标准范式,合式公式A变换成子句集SA实例：A=(x)(P(x)(y)(R(y)S(x,y),合式公式化子句集实例,A(x)(P(x)(y)(R(y)S(x,y)(x)(P(x)(y)(R(y)S(x,y)消(x)(y)(P(x)(R(y)S(x,y)前束(x)(P(x)(R(f(x)S(x,f(x)消,子句集:SA=P(x),R(f(x)S(x,f(x),习题：将谓词公式化为子句形式,(x)P(x)(x)P(x)(x)(P(x)(y)(P(y)P(f(x,y)(y)(Q(x,y)P(y),机器演绎推理技术归结法,谓词公式的规范化表示谓词公式的合取范式合取范式的子句集形式推理过程规范化命题逻辑归结原理变量的置换与合一概念谓词归结证明系统的相关技术,核心思想：要证B=A1，A2，An|=语义证明方法1：|=A1A2An语义证明方法2：A=A1A2An|=F,命题逻辑归结原理,支撑定理：设SA是合式谓词公式A的标准型子句集，则A为永假的充要条件是SA不可满足。,(证明SA不可满足）,命题逻辑归结原理,归结定义：设C1,C2是任意的两个命题子句，其中，C1=L1C1,C2=L2C2，L1,L2是互补原子命题，即L1=L2。那么，分别从C1和C2中删去L1和L2，将其余部分组成的一个新的析取式C=C1C2称为C1和C2的归结式。,命题逻辑归结原理,归结定义应用例:,PQR,RT,P,P,PR,R,P,PQT,命题逻辑归结原理,定理：子句C1和C2的归结式C是C1和C2的逻辑推论，即，C1,C2|=C。,推论：设C是C1和C2的归结式，则子句集S=C1，C2，Cn与子句集S1=C，C1，C2，Cn的不可满足性等价。,归结式性质：,C=L1C1，L2C2=C1C2,命题逻辑归结原理,命题归结算法：将已知前提公式集A化为子句集SA；,把待证命题的否定式化为子句集，并将其加入到前提子句集SA中，获子句集S0=SA；,对子句集Si（i=0,1,n),应用归结推理规则，获Si+1=CSi,重复此过程，直至推出包含空子句的扩大子句集Sn为止。,命题逻辑归结原理应用实例,A=P,(PQ)R,(ST)Q,T|=RS0=P,PQR,SQ,TQ,T,R|=,问题：,命题归结：,谓词归结：,需解决谓词中变量的置换与合一问题！,谓词公式的规范化表示谓词公式的子句形式子句的标准范式推理过程规范化命题逻辑归结原理谓词公式变量的置换与合一概念谓词归结证明系统的相关技术,机器演绎推理技术,谓词公式变量的置换与合一,置换及其实例：设E为任一简单表达式，x1,x2,xn为E中的不同变量，t1,t2,tn为项，则:集合S=t1/x1,t2/x2,tn/xn为一置换ES=Et1,t2,tn为用ti（i=1,2,n）处处替换表达式E中出现的变元xi（i=1,2,n）得到的一个实例。,x1,x2,xn,谓词公式变量的置换与合一,例：设表达式E=P(x,f(y),B)置换实例-,S1=z/x,w/yS2=g(z)/x,A/yS3=C/x,A/y,ES1=P(z,f(w),B),ES2=P(g(z),f(A),B),ES3=P(C,f(A),B),谓词公式中变量的置换与合一,置换的合成：设两个置换分别为=t1/u1,t2/u2,tm/um,=t1/v1,t2/v2,tn/vn,与的合成:=t1/u1,t2/u2,tm/um，t1/v1,t2/v2,tn/vn（viui)。置换过程如下：,首先，利用中的置换对对变量u1,u2,um进行置换；如果置换后的项中出现vi（i=1,2,n）,再用中的置换对vi进行进一步的置换。,而后，用的置换对对变量v1,v2,vn进行置换，其中，viuj。,谓词公式中变量的置换与合一,置换合成的运用实例：设s1=g(x,y)/z,s2=A/x,B/y,C/w,D/z,置换合成性质：,满足结合律:(s1s2)s3=s1(s2s3),不满足交换律:(s1s2)(s2s1),s1s2=g(A,B)/z,A/x,B/y,C/w,变量的置换与合一,表达式的可合一性与合一者：设有表达式集E=Ei和置换S。如果S对E中所有表达式进行置换后得到的实例满足E1S=E1S=.=EnS，则称表达式集Ei是可合一的，S为Ei的合一者,例：设表达式集Ei=P(x,f(y),B)，P(x,f(B),B)置换1：s1=A/x,B/y,置换后有：E1s1=E2s1=P(A,f(B),B),置换2：s2=B/y置换后有：E1s2=E2s2=P(x,f(B),B),变量的置换与合一,最一般合一者（mguMostGeneralUnifier）是表达式Ei的最一般的合一者，如果它满足以下关系：对于表达式集Ei的任一合一者S，都存在另一个置换S，使得S=S，或者ES=(E)S成立。,例：设s=A/x,B/y=B/y，S=A/x,有：S=S。,演绎推理技术,谓词公式的规范化表示谓词公式的子句形式子句的标准范式推理过程规范化命题逻辑归结原理谓词公式变量的置换与合一概念谓词归结证明系统的相关技术,谓词归结证明系统的相关技术,合一匹配算法一阶谓词归结原理归结证明系统的基本推理算法归结证明系统的推理策略,合一匹配算法：,用形式化的方法，寻找两个子句的最一般合一者，构成该子句对的互补文字。,合一匹配算法：,分歧集定义：设Ei是简单表达式的非空集合，将Ei的所有元素从左自右扫描，如果找到对应符号串中第一个不相同的符号，则称以此符号位置为起点的子表达式构成的集合为Ei的一个分歧集。,例：设Ei=P(f(x),h(y),a),P(f(x),z,a),P(f(x),h(y),b),Ei的分歧集：,h(y),z；a,b,合一匹配算法：,例1:设Ei=P(f(a),g(x),P(y,y)置换0=;分歧集D0=f(a),y置换合成1=f(a)/y实例Ei1=P(f(a),g(x),P(f(a),f(a)分歧集D1=g(x),f(a)打印“Ei不可合一”。,合一匹配算法应用实例：,合一匹配算法应用习题：,2、设Ei=P(a,x,h(g(z),P(z,h(y),h(y)对Ei实施合一匹配算法。,1、判断下列文字能否合一，若不能，请说明理由，若能，请求出其mgu。Ei=P(f(x,g(z),h(A),P(f(x,y),z),谓词归结证明系统的相关技术,合一匹配算法一阶谓词归结原理归结证明系统的基本推理算法归结证明系统的推理策略,一阶谓词归结原理,归结定义：设C1,C2是任意的两个谓词子句，其中，C1=L1C1,C2=L2C2，L1,L2是可化为互补文字的两个原子谓词公式,（即二者间存在最一般合一者mgu）。那么，C1和C2的归结式C可由下式求得：C=C1-L1C2-L2=C1C2,一阶谓词归结原理演算实例,P(x),P(x)Q(x),Q(x),P(x,f(y)Q(x)R(f(a),y),P(f(f(a),z)R(z,w),Q(f(f(a)R(f(a),y)R(f(y),w),谓词归结证明系统的相关技术,合一匹配算法一阶谓词归结原理归结证明系统的基本算法归结证明系统的推理策略,设公式集S和待证目标公式W，将公式集S,W化成子句集S0；CLAUSES=S0；UntilCLAUSES,do:begin从CLAUSES中选择两个不同的可归结子句C1和C2；对C1和C2中互反文字进行归结，获归结式C，且CLAUSES=CLAUSESC；end,一阶谓词归结证明系统的基本算法,一阶谓词归结证明系统应用实例（1）,已知：会朗读的人是识字的人，海豚都不识字，有些海豚很机灵。求证:有些很机灵的东西不会朗读,一阶谓词描述：(x)(R(x)L(x)(x)(D(x)L(x)(x)(D(x)I(x)求证：w=(x)(I(x)R(x),设原子谓词公式：R(x)：x会朗读；L(x)：x识字D(x)：x是海豚；I(x)：x机灵,W=(x)(I(x)R(x)=(x)(I(x)R(x)=(x)I(z)R(z),一阶谓词归结证明系统应用实例（2）,子句集：S0=R(x)L(x),D(y)L(y),D(A),I(A),I(z)R(z),一阶谓词归结证明系统应用实例（3）,S0=R(x)L(x),D(y)L(y),D(A),I(A),I(z)R(z),谓词归结证明系统的相关技术,合一匹配算法一阶谓词归结原理归结反演系统的基本算法归结证明系统的推理策略,归结证明系统的推理策略,搜索策略的完备性如果给定问题的子句集存在矛盾，便可以通过运用某种归结搜索策略,最终构造出一棵以结尾的归结反演树，称此归结搜索策略是完备的。,策略的搜索效率需要兼顾策略的完备性和高效性。,常用归结搜索策略,推理策略实例（1）,已知：会朗读的人是识字的人，海豚都不识字，有些海豚很机灵。,设原子谓词公式：R(x)：x会朗读；L(x)：x识字D(x)：x是海豚；I(x)：x机灵。,求证:有些很机灵的东西不会朗读。,一阶谓词描述：(x)(R(x)L(x)；(x)(D(x)L(x)(x)(D(x)I(x)求证：(x)(I(x)R(x),推理策略实例（2）,子句集：S0=R(x)L(x),D(y)L(y),D(A),I(A),I(z)R(z),推理策略实例-宽度优先策略（1）,s0,s1,s2,s3,推理策略实例-宽度优先策略（2）,归结策略运用过程：第一级：原始子句集S0中所有可能归结的子句对进行归结，产生全部归结式，将其加到S0中获新的归结子句集S1=S01级归结式。第i级：Si-1中所有可能归结的子句对进行归结，产生全部归结式，将其加到归结子句集Si-1中获新的归结子句集Si=Si-1第i级归结式。,归结策略特点：策略完备，搜索效率低。,推理策略分析改进（1）,策略分析：由于前提公式集中并无矛盾，推理反驳是由待证结论的否定式加入引起的。因此，有支持集策略。,支持集策略特点：每次归结的选用的母子句对中至少有一个母子句是与目标公式否定式有关的子句，即它或是目标公式否定式本身或是否定式的后裔。,推理策略实例-支持集策略（1）,s0,s1,s2,s3,推理策略实例-支持集策略（2）,归结策略运用过程：第一级：原始子句集S0中所有能与目标公式否定式归结的子句对进行归结，产生全部可能的归结式，将其加到S0中获新的归结子句集S1=S01级归结式。第i级：Si-1中所有能与目标公式否定式及其后裔归结的子句对进行归结，产生全部可能的归结式，将其加到Si1中获新的归结子句集Si=Si-1第i级归结式,归结策略特点：,策略完备，搜索效率相对高。,推理策略分析改进（2）,策略分析：由于归结的过程最终要产生长度为零的空子句。为了加快归结进度，因此，有单元归结策略。,单元归结策略特点：每次归结时，优先选取单元子句（只含有一个文字的子句）作为母子句进行归结。,推理策略实例-单元归结策略（1）,P,归结策略特点：此策略可缩短归结过程，能大大提高搜索效率。策略不完备，S中无单子句时，无法进行归结。,归结实例：S=R,PR,QR,PQ,Q,推理策略分析改进（3）,策略分析：综合多种归结搜索策略特征，有利于提高搜索的有效性和完备性。因此，有线性归结策略。,线性归结策略特点：与诸如“支持集策略”、“单元集策略”等搜索策略特征相容，可视为多种策略的组合。,线性归结策略（1）,设子句集S,顶子句C0和B0S，从S到Cn推理序列中产生线性归结式Ci（0in)的任意归结母式Ci-1和Bi-1均应满足以下条件：,Ci-1是Ci直接上一级的线性归结式；Bi-1或者属于子句集S，或是某个已知的线性归结式Cj(ji)；分别称Ci-1和Bi-1为中心子句和边子句。,线性归结策略（2）,线性归结例：设S=AB,AB,AB,AB,B,AB,A,AB,B,B,归结策略特点：当C0或B0之一等于时，线性归结为支持集策略；与单元归结策略类似，优先选择较短的母子句进行归结。,策略完备，结构简单。,利用线性归结策略求证下列公式永真:(x)(P(x)(Q(A)Q(B)(x)(P(x)Q(x),习题：,基于逻辑的应用系统,基于规则的演绎推理系统,基于规则的演绎推理系统,问题提出：,因此，有：基于规则的演绎推理系统：直接根据问题领域的事实和规则，证明某目标公式是否成立，而不是先将公式化成子句形式，用归结反演方法证明。此种证明方法称为直接证明法。,基于归结的推理可能丢失蕴含式中的有用的控制信息：子句:ABC|=|ABC；ACB；BCA；(AB)C；(B(AC)；C(AB),一阶谓词的蕴含式常用于表示问题领域的各种知识：P(x,y)P(y,z)G(x,z)；,基于规则的演绎推理-PROLOG,定义:称最多含一个正文字的子句为Horn子句。例：A1A2AnB等价式：A1A2AnB,PROLOG:基于Horn子句的逻辑程序描述语言；优点：1、表达能力强：凡能用一阶逻辑描述的问题均可用Horn子句表达2、表达直观、推理简单,若有：WL1L2，可化为：WL1，WL2,基于规则的演绎推理-PROLOG,描述：待证目标库：G规则集：BCG,DB,事实库：C，D,推理策