《4 北航6系人工智能课件》由会员分享，可在线阅读，更多相关《4 北航6系人工智能课件（77页珍藏版）》请在金锄头文库上搜索。
1、北京航空航天大学软件开发环境国家重点实验室 Slide 1 第 三 章 基于逻辑的问题求解方法 第 8 周 北京航空航天大学软件开发环境国家重点实验室 Slide 2 认知区域 功能 研究学派 - - 10s: 目标实现 1s: 简单操作合成 100ms:初级熟练操作 10ms: 符号存取 理性带 认知带 神经带 逻辑学派、知 识工程学派 认知学派 （代表作：- SOAR） 联结学派 认知学派的层次划分 北京航空航天大学软件开发环境国家重点实验室 Slide 3 基于逻辑的问题求解方法 n逻辑是人工智能的重要基础 n一阶逻辑的基本概念回顾 n基于一阶逻辑的演绎推理技术 n应用逻辑系统 北京航空
2、航天大学软件开发环境国家重点实验室 Slide 4 逻辑是人工智能的重要基础 n人工智能遵循符号原理：将所有与问题有关的对象、 关系以及概念等进行形式化的表示和处理。 n 一阶逻辑满足形式化表达和处理要求 ： w 类自然语言的形式化的符号语言 （谓词公式描述） w 强有力的推理方法（公理化推理方法、归结法）； w 坚实的理论证明基础（语义模型、推理的可靠性、 完备性研究等）。 北京航空航天大学软件开发环境国家重点实验室 Slide 5 逻辑是人工智能的重要基础 n 一阶逻辑对AI的贡献： w 提出了陈述性知识表示方式 ； w 将知识描述与知识处理相分离； w 基于一阶逻辑扩展了多种应用逻辑 -
3、 如时序 ( p53 )、模糊、非单调等多种应用逻辑。 北京航空航天大学软件开发环境国家重点实验室 Slide 6 基于逻辑的问题求解方法 n逻辑是人工智能的重要基础 n一阶逻辑的基本概念回顾 n演绎推理技术 n应用逻辑系统 北京航空航天大学软件开发环境国家重点实验室 Slide 7 u 字符表 一阶逻辑的基本概念回顾 一阶谓词逻辑知识表示方法 w 项、合式谓词公式 w 演绎推理方法 w 解释与赋值 北京航空航天大学软件开发环境国家重点实验室 Slide 8 一阶谓词逻辑的符号体系 - 字符表 n常元: n变元: n函数(词)符 : n谓词符: n逻辑联词: n量词: n其它: a, b, c
4、,.; A, B, C,.; x, y, z,.; Fn, gm, .; e.g., f1(x): x的父亲。 Pn, Qm, R, .; e.g., brother2(x, y)。 , , , , 。 , 。 (, ), ，。 北京航空航天大学软件开发环境国家重点实验室 Slide 9 一阶逻辑的基本概念回顾 n一阶谓词逻辑的符号体系 w 字符表 w 项、谓词合式公式 w 等价公式 w 演绎推理方法 北京航空航天大学软件开发环境国家重点实验室 Slide 10 项、谓词合式公式 n 项： 常元: a,b,; 变元: x,y,.; 函词: fn(x1,x2,xn) ，其中， xi是项。 n 合
5、适谓词公式 原子公式 Pn(x1,x2,xn)是合式谓词公式 ，其中， xi 是项。 设: A,B是合式谓词公式，则 A，AB，AB，AB, (x) A 是合式谓词公式。 例：( x) ( P(x) (y) (R(y) S(x,y) ) ) 北京航空航天大学软件开发环境国家重点实验室 Slide 11 等价公式 n等价公式 ( 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) (
6、x)P(x) ( x) P(x) 全称量词消去规则： （x)P(x) P(y) 存在量词消去规则：（ x)P(x) P(c) c为常元 .。 北京航空航天大学软件开发环境国家重点实验室 Slide 12 演绎推理 演绎推理方法 推理：根据一定准则，由前提判断导出称为结论的思维过程。 演绎推理、归纳推理、类比推理 推理方式：A1,A2,An |= B, iff （ x）（ P(x) Q(x) ） P(a) - Q(a) ， 推理规则： 推理过程：反复运用等价公式、推理规则对已 知的谓词公式进行变换，得到所需的逻辑结论的 过程。 归 原 理 结 北京航空航天大学软件开发环境国家重点实验室 Slid
7、e 13 解释与赋值 n解释定义: 一个解释 I 由以下四部分组成。 w（1）指定一个非空集合 DI，称为 I 的论域； w（2）对于每个常元 a，指定 DI 中的一个元素 aI； w（3）对于每个n元函数符号 f，指定DI上的一个n元运算符 fI w（4）对于每个n元谓词符号 P，指定DI上的一个 n 元谓词 PI 北京航空航天大学软件开发环境国家重点实验室 Slide 14 解释与赋值 n 赋值定义: w设 I 是一个解释，将所有变元组成的集合映射到 论域 DI 的函数称为 I 中的赋值v。 n 解释和赋值共同规定了项和公式的意义。 n 例：设 DI 为自然数集合，fI 是自然数乘法，gI
8、 是自然 数加法，aI = 2，I中赋值 v 使 v(x) = 1。 项 f(g(a,x),a)在 I 和 v 下的意义： I（f(g(a,x),a)）(v) = ? 北京航空航天大学软件开发环境国家重点实验室 Slide 15 基于逻辑的问题求解方法 n逻辑是人工智能的重要基础 n一阶逻辑的基本概念回顾 n 机器演绎推理技术 n 应用逻辑系统 北京航空航天大学软件开发环境国家重点实验室 Slide 16 机器演绎推理技术 归结法 n 谓词公式的规范化 w 谓词公式的合取范式 w 合取范式的子句集形式 n 推理过程规范化 w 命题逻辑归结原理 w 变量置换与合一 w谓词归结证明系统的相关技术
9、北京航空航天大学软件开发环境国家重点实验室 Slide 17 谓词公式的子句形式 n文字： n子句： n空子句： n基子句： 子句与合适 公式对应关系 原子公式及其否定： 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 无 型前束合取范式 北京航空航天大学软件开发环境国家重点实验室 Slide 18 子句的标准范式 n无 型前束合取范
10、式: （Q1x1）(Q2x2）（Qnxn）M 其中， Qi：全称量词； xi：变元 母式：M = (A11 A12 A1n ) (Am1 Am2 Aml ) 是合取范式， 其中, Aij是文字。 子句集： S = A11 A12 A1n ， Am1 Am2 Aml 北京航空航天大学软件开发环境国家重点实验室 Slide 19 n合式谓词公式化子句集步骤 ( p43 ) 子句的标准范式 合式公式 A 变换成子句集 SA 实例： A=( x) ( P(x) (y) (R(y) S(x,y) ) ) 北京航空航天大学软件开发环境国家重点实验室 Slide 20 合式公式化子句集实例 nA (x)(P
11、(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) 母 式 北京航空航天大学软件开发环境国家重点实验室 Slide 21 习题：将谓词公式化为子句形式 n (x)P(x) (x ) P(x) n (x)(P(x) ( (y)(P(y) P(f(x,y) (y)(Q(x,y) P(y) 北京航空航天大学软件开发环境国家重点实验室 Slide
12、 22 机器演绎推理技术 归结法 n 谓词公式的规范化表示 w 谓词公式的合取范式 w 合取范式的子句集形式 n 推理过程规范化 w 命题逻辑归结原理 w 变量的置换与合一概念 w 谓词归结证明系统的相关技术 北京航空航天大学软件开发环境国家重点实验室 Slide 23 n 核心思想： w要证 B = A1，A2 ， An |= w语义证明方法1： |= A1 A2 An w语义证明方法2： A = A1 A2 An |= F 命题逻辑归结原理 n 支撑定理： 设 SA 是合式谓词公式 A 的标准型子句集，则 A 为永 假的充要条件是 SA 不可满足。 ( 证明 SA不可满足）即：SA = S
13、B |= 北京航空航天大学软件开发环境国家重点实验室 Slide 24 命题逻辑归结原理 n归结定义： 设C1,C2是任意的两个命题子句，其中， C1 = L1 C1 , C2 = L2 C2 ，L1, L2是互补原 子命题，即 L1 = L2。那么，分别从 C1 和 C2 中删去 L1 和 L2，将其余部分组成的一个新的析 取式 C = C1 C2 称为 C1 和 C2 的归结式。 北京航空航天大学软件开发环境国家重点实验室 Slide 25 命题逻辑归结原理 n归结定义应用例: P Q R R T PP P R R P P Q T 不可归结 P R P Q 北京航空航天大学软件开发环境国家
14、重点实验室 Slide 26 命题逻辑归结原理 v 定理：子句 C1 和 C2 的归结式 C 是 C1 和 C2 的逻辑推论，即， C1, C2 |= C 。 v 推论：设 C 是 C1 和 C2 的归结式，则子句集 S = C1，C2 ， Cn 与子句集 S1 = C，C1， C2 ， Cn 的不可满足性等价。 归结式性质： C = L1 C1， L2 C2 = C1 C2 北京航空航天大学软件开发环境国家重点实验室 Slide 27 命题逻辑归结原理 n命题归结算法： w 将已知前提公式集 A 化为子句集 SA； w 把待证命题 的否定式 化为子句集，并将其 加入到前提子句集 SA 中，获子句集 S0 = SA ； w 对子句集 Si（i = 0, 1, , n), 应用归结推理
