4 北航6系人工智能课件

北京航空航天大学软件开发环境国家重点实验室Slide1第三章基于逻辑的问题求解方法第8周北京航空航天大学软件开发环境国家重点实验室Slide2认知区域功能研究学派-------------------------------------------------------10s:目标实现1s:简单操作合成100ms:初级熟练操作10ms:符号存取理性带认知带神经带逻辑学派、知识工程学派认知学派（代表作：---SOAR）联结学派认知学派的层次划分北京航空航天大学软件开发环境国家重点实验室Slide3基于逻辑的问题求解方法逻辑是人工智能的重要基础一阶逻辑的基本概念回顾基于一阶逻辑的演绎推理技术应用逻辑系统北京航空航天大学软件开发环境国家重点实验室Slide4逻辑是人工智能的重要基础人工智能遵循符号原理：将所有与问题有关的对象、关系以及概念等进行形式化的表示和处理。一阶逻辑满足形式化表达和处理要求：类自然语言的形式化的符号语言（谓词公式描述）强有力的推理方法（公理化推理方法、归结法）；坚实的理论证明基础（语义模型、推理的可靠性、完备性研究等）。北京航空航天大学软件开发环境国家重点实验室Slide5逻辑是人工智能的重要基础一阶逻辑对AI的贡献：提出了陈述性知识表示方式；将知识描述与知识处理相分离；基于一阶逻辑扩展了多种应用逻辑---如时序(p53)、模糊、非单调等多种应用逻辑。北京航空航天大学软件开发环境国家重点实验室Slide6基于逻辑的问题求解方法逻辑是人工智能的重要基础一阶逻辑的基本概念回顾演绎推理技术应用逻辑系统北京航空航天大学软件开发环境国家重点实验室Slide7字符表一阶逻辑的基本概念回顾一阶谓词逻辑知识表示方法项、合式谓词公式演绎推理方法解释与赋值北京航空航天大学软件开发环境国家重点实验室Slide8一阶谓词逻辑的符号体系-字符表常元:变元:函数(词)符:谓词符:逻辑联词:量词:其它:a,b,c,….;A,B,C,…..;x,y,z,…..;Fn,gm,…..;e.g.,f1(x):x的父亲。Pn,Qm,R,…..;e.g.,brother2(x,y)。,,,,。,。(,),，。北京航空航天大学软件开发环境国家重点实验室Slide9一阶逻辑的基本概念回顾一阶谓词逻辑的符号体系字符表项、谓词合式公式等价公式演绎推理方法北京航空航天大学软件开发环境国家重点实验室Slide10项、谓词合式公式项：常元:a,b,…;变元:x,y,….;函词:fn(x1,x2,…xn)，其中，xi是项。合适谓词公式原子公式Pn(x1,x2,…xn)是合式谓词公式，其中，xi是项。设:A,B是合式谓词公式，则A，AB，AB，AB,(x)A是合式谓词公式。例：(x)(P(x)(y)(R(y)S(x,y)))北京航空航天大学软件开发环境国家重点实验室Slide11等价公式等价公式(p41-42)得摩根定律：(PQ)PQ(PQ)PQ分配律：R(PQ)（RP）(RQ)R(PQ)（RP）(RQ)蕴含等价式：PQPQ…….；量词转换律:(x)P(x)(x)P(x)(x)P(x)(x)P(x)全称量词消去规则：（x)P(x)P(y)存在量词消去规则：（x)P(x)P(c)c为常元…….。北京航空航天大学软件开发环境国家重点实验室Slide12演绎推理演绎推理方法推理：根据一定准则，由前提判断导出称为结论的思维过程。演绎推理、归纳推理、类比推理推理方式：{A1,A2,…,An}|=B,iff（x）（P(x)Q(x)）P(a)--------------------------------------Q(a)，推理规则：推理过程：反复运用等价公式、推理规则对已知的谓词公式进行变换，得到所需的逻辑结论的过程。归原理结北京航空航天大学软件开发环境国家重点实验室Slide13解释与赋值解释定义:一个解释I由以下四部分组成。（1）指定一个非空集合DI，称为I的论域；（2）对于每个常元a，指定DI中的一个元素aI；（3）对于每个n元函数符号f，指定DI上的一个n元运算符fI（4）对于每个n元谓词符号P，指定DI上的一个n元谓词PI北京航空航天大学软件开发环境国家重点实验室Slide14解释与赋值赋值定义:设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)=?北京航空航天大学软件开发环境国家重点实验室Slide15基于逻辑的问题求解方法逻辑是人工智能的重要基础一阶逻辑的基本概念回顾机器演绎推理技术应用逻辑系统北京航空航天大学软件开发环境国家重点实验室Slide16机器演绎推理技术–归结法谓词公式的规范化谓词公式的合取范式合取范式的子句集形式推理过程规范化命题逻辑归结原理变量置换与合一谓词归结证明系统的相关技术北京航空航天大学软件开发环境国家重点实验室Slide17谓词公式的子句形式文字：子句：空子句：基子句：子句与合适公式对应关系原子公式及其否定：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}析取式L1L2…Ln子句集SA={A1,A2,…,An}无型前束合取范式北京航空航天大学软件开发环境国家重点实验室Slide18子句的标准范式无型前束合取范式:（Q1x1）(Q2x2）…（Qnxn）M其中，Qi：全称量词；xi：变元母式：M=(A11A12…A1n)…(Am1Am2…Aml)是合取范式，其中,Aij是文字。子句集：S=A11A12…A1n，…，Am1Am2…Aml北京航空航天大学软件开发环境国家重点实验室Slide19合式谓词公式化子句集步骤(p43)子句的标准范式合式公式A变换成子句集SA实例：A=(x)(P(x)(y)(R(y)S(x,y)))北京航空航天大学软件开发环境国家重点实验室Slide20合式公式化子句集实例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))前束(子句1,子句2)母式北京航空航天大学软件开发环境国家重点实验室Slide21习题：将谓词公式化为子句形式(x)P(x)(x)P(x)(x)(P(x)((y)(P(y)P(f(x,y)))(y)(Q(x,y)P(y))))北京航空航天大学软件开发环境国家重点实验室Slide22机器演绎推理技术–归结法谓词公式的规范化表示谓词公式的合取范式合取范式的子句集形式推理过程规范化命题逻辑归结原理变量的置换与合一概念谓词归结证明系统的相关技术北京航空航天大学软件开发环境国家重点实验室Slide23核心思想：要证B=A1，A2，…An|=语义证明方法1：|=A1A2…An语义证明方法2：A=A1A2…An|=F命题逻辑归结原理支撑定理：设SA是合式谓词公式A的标准型子句集，则A为永假的充要条件是SA不可满足。(证明SA不可满足）即：SA=SB|=北京航空航天大学软件开发环境国家重点实验室Slide24命题逻辑归结原理归结定义：设C1,C2是任意的两个命题子句，其中，C1=L1C1’,C2=L2C2’，L1,L2是互补原子命题，即L1=L2。那么，分别从C1和C2中删去L1和L2，将其余部分组成的一个新的析取式C=C1’C2’称为C1和C2的归结式。北京航空航天大学软件开发环境国家重点实验室Slide25命题逻辑归结原理归结定义应用例:PQRRTPPPRRPPQT不可归结PRPQ北京航空航天大学软件开发环境国家重点实验室Slide26命题逻辑归结原理定理：子句C1和C2的归结式C是C1和C2的逻辑推论，即，C1,C2|=C。推论：设C是C1和C2的归结式，则子句集S=C1，C2，…Cn与子句集S1=C，C1，C2，…Cn的不可满足性等价。归结式性质：C={L1C1，L2C2}=C1C2北京航空航天大学软件开发环境国家重点实验室Slide27命题逻辑归结原理命题归结算法：将已知前提公式集A化为子句集SA；把待证命题的否定式化为子句集，并将其加入到前提子句集SA中，获子句集S0=SA；对子句集Si（i=0,1,…,n),应用归结推理规则，获Si+1=CSi,重复此过程，直至推出包含空子句的扩大子句集Sn为止。北京航空航天大学软件开发环境国家重点实验室Slide28命题逻辑归结原理应用实例A=P,(PQ)R,(ST)Q,T|=RS0=P,PQR,SQ,TQ,T,R|=PQRR②⑥PQP⑦①QTQ⑧④TT⑨⑤北京航空航天大学软件开发环境国家重点实验室Slide29问题：命题归结：C1=PC2=P谓词归结：C1=P(f(a))C2=P(x)?需解决谓词中变量的置换与合一问题！！北京航空航天大学软件开发环境国家重点实验室Slide30谓词公式的规范化表示谓词公式的子句形式子句的标准范式推理过程规范化命题逻辑归结原理谓词公式变量的置换与合一概念谓词归结证明系统的相关技术机器演绎推理技术北京航空航天大学软件开发环境国家重点实验室Slide31谓词公式变量的置换与合一置换及其实例：设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北京航空航天大学软件开发环境国家重点实验室Slide32谓词公式变量的置换与合一例：设表达式E=P(x,f(y),B)置换实例----------------------------------------------------S1={z/x,w/y}S2={g(z)/x,A/y}S3={C/x,A/y}ES1=P(z,f(w),B)ES2=P(g(z),f(A),B)ES3=P(C,f(A),B)北京航空航天大学软件开发环境国家重点实验室Slide33谓词公式中变量的置换与合一置换的合成：设两个置换分别为=t1/u1,t2/u2,…,tm/um,=t’1/v1,t’2/v2,…,t’n/vn,与的合成:=t1/u1,t2/u2,…,tm/um，t’1/v1,t’2/v2,…,t’n/vn（viui)。置换过程如下：首先，利用中的置换对对变量u1,u2,…,um进行置换；如果置换后的项中出现vi（i=1,2,…n）,再用中的置换对vi进行进一步的置换。而后，用的置换对对变量v1,v2,…,vn进行置换，其中，viuj。北京航空航天大学软件开发环境国家重点实验室Slide34谓词公式中变量的置换与合一置换合成的运用实例：设s1={g(x,