《week8-北航6系人工智能课件》由会员分享，可在线阅读，更多相关《week8-北航6系人工智能课件（77页珍藏版）》请在金锄头文库上搜索。
1、第 三 章 基于逻辑的问题求解方法,第 8 周,认知区域 功能 研究学派 -,10s: 目标实现 1s: 简单操作合成 100ms:初级熟练操作 10ms: 符号存取,理性带 认知带 神经带,逻辑学派、知识工程学派 认知学派 （代表作：- SOAR） 联结学派,认知学派的层次划分,基于逻辑的问题求解方法,逻辑是人工智能的重要基础 一阶逻辑的基本概念回顾 基于一阶逻辑的演绎推理技术 应用逻辑系统,逻辑是人工智能的重要基础,人工智能遵循符号原理：将所有与问题有关的对象、关系以及概念等进行形式化的表示和处理。,一阶逻辑满足形式化表达和处理要求 ： 类自然语言的形式化的符号语言 （谓词公式描述） 强有
2、力的推理方法（公理化推理方法、归结法）； 坚实的理论证明基础（语义模型、推理的可靠性、完备性研究等）。,逻辑是人工智能的重要基础,一阶逻辑对AI的贡献： 提出了陈述性知识表示方式 ； 将知识描述与知识处理相分离； 基于一阶逻辑扩展了多种应用逻辑 - 如时序 ( p53 )、模糊、非单调等多种应用逻辑。,基于逻辑的问题求解方法,逻辑是人工智能的重要基础 一阶逻辑的基本概念回顾 演绎推理技术 应用逻辑系统,字符表,一阶逻辑的基本概念回顾,一阶谓词逻辑知识表示方法,项、合式谓词公式,演绎推理方法,解释与赋值,一阶谓词逻辑的符号体系 - 字符表,常元: 变元: 函数(词)符: 谓词符: 逻辑联词: 量
3、词: 其它:,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，A
4、B，AB, (x) A 是合式谓词公式。,例：( x) ( P(x) (y) (R(y) S(x,y) ) ),等价公式,等价公式,( 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为常元 .。,演绎推理,演绎推理方法,推理：根据一定准则，由前提判
5、断导出称为结论的思维过程。,演绎推理、归纳推理、类比推理,推理方式：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,解释与赋值,赋
6、值定义: 设 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) = ?,基于逻辑的问题求解方法,逻辑是人工智能的重要基础 一阶逻辑的基本概念回顾 机器演绎推理技术 应用逻辑系统,机器演绎推理技术 归结法,谓词公式的规范化 谓词公式的合取范式 合取范式的子句集形式 推理过程规范化 命题逻辑归结原理 变量置换与合一 谓词
7、归结证明系统的相关技术,谓词公式的子句形式,文字： 子句： 空子句： 基子句：,子句与合适公式对应关系,原子公式及其否定： 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 无 型前束合取范式,子句的标准范式,无 型前束合取范式:,（Q1x1）(Q2x2）（Qnxn）M 其中， Qi：全称量词； xi：变元 母式：M = (A11 A12 A1n ) (Am
8、1 Am2 Aml ) 是合取范式， 其中, Aij是文字。,子句集： S = A11 A12 A1n ， Am1 Am2 Aml ,合式谓词公式化子句集步骤 ( 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)
9、 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： |= A1 A2 An 语义证明方法2： A = A1 A2 An |= F,命题逻辑归结原理,支撑定理： 设 SA 是合式谓词公式 A 的标准型子句集，则 A 为永假的充
10、要条件是 SA 不可满足。,( 证明 SA不可满足）,命题逻辑归结原理,归结定义： 设C1,C2是任意的两个命题子句，其中， C1 = L1 C1 , C2 = L2 C2 ，L1, L2是互补原子命题，即 L1 = L2。那么，分别从 C1 和 C2 中删去 L1 和 L2，将其余部分组成的一个新的析取式 C = C1 C2 称为 C1 和 C2 的归结式。,命题逻辑归结原理,归结定义应用例:, P Q R, R T, P,P, P R, R, P, P Q T,命题逻辑归结原理,定理：子句 C1 和 C2 的归结式 C 是 C1 和 C2 的逻辑推论，即， C1, C2 |= C 。,推论
11、：设 C 是 C1 和 C2 的归结式，则子句集 S = C1，C2 ， Cn 与子句集 S1 = C，C1，C2 ， Cn 的不可满足性等价。,归结式性质：,C = L1 C1， L2 C2 = C1 C2,命题逻辑归结原理,命题归结算法： 将已知前提公式集 A 化为子句集 SA；,把待证命题 的否定式 化为子句集，并将其加入到前提子句集 SA 中，获子句集 S0 = SA ；,对子句集 Si（i = 0, 1, , n), 应用归结推理规则，获 Si+1 = C Si, 重复此过程，直至推出包含空子句的扩大子句集 Sn 为止。,命题逻辑归结原理应用实例,A = P, (P Q) R, (S
12、 T) Q, T |= R S0= P, P Q R, S Q , T Q, T, R |=,问题：,命题归结：,谓词归结：,需解决谓词中变量的置换与合一问题！,谓词公式的规范化表示 谓词公式的子句形式 子句的标准范式 推理过程规范化 命题逻辑归结原理 谓词公式变量的置换与合一概念 谓词归结证明系统的相关技术,机器演绎推理技术,谓词公式变量的置换与合一,置换及其实例： 设 E 为任一简单表达式，x1,x2,xn为 E 中的不同变量，t1,t2,tn 为项，则: 集合 S = t1/x1, t2/x2, tn/xn 为一置换 ES = E t1,t2,tn 为 用 ti（i=1,2,n）处处 替
13、换表达式 E 中出现的变元 xi（i=1,2,n）得到的一个实例。,x1,x2,xn,谓词公式变量的置换与合一,例：设表达式 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),谓词公式中变量的置换与合一,置换的合成： 设两个置换分别为 = t1/u1, t2/u2, tm/um, = t1/v1, t2/v2, tn/vn, 与 的合成: = t1/u1, t2/u2,tm /um，t1
14、/v1, t2/v2,tn/vn （vi ui)。置换过程如下：,首先，利用 中的置换对对变量 u1,u2,um 进行置换；如果置换后的项中出现 vi（i=1,2,n）,再用 中的置换对 vi 进行进一步的置换。,而后，用 的置换对对变量 v1,v2,vn进行置换，其中，vi uj 。,谓词公式中变量的置换与合一,置换合成的运用实例： 设 s1= g(x,y)/z , s2= A/x,B/y,C/w,D/z ,置换合成性质：,满足结合律: (s1 s2)s3 = s1(s2s3),不满足交换律: (s1 s2) (s2 s1),s1 s2 = g(A,B)/z, A/x,B/y,C/w ,变量的置换与合一,表达式的可合一性与合一者： 设有表达式集 E = Ei 和置换 S。如果 S 对 E 中所有表达式进行置换后得到的实例满足 E1S = E1S = = EnS，则称表达式
