week北航系人工智能课件.ppt

第 三 章 基于逻辑的问题求解方法 认知学派的层次划分 认知区域 功能 研究学派 ------------------------------------------------------- 基于逻辑的问题求解方法 逻辑是人工智能的重要基础 一阶逻辑的基本概念回顾 基于一阶逻辑的演绎推理技术 应用逻辑系统 逻辑是人工智能的重要基础 人工智能遵循符号原理：将所有与问题有关的对象、关系以及概念等进行形式化的表示和处理。 逻辑是人工智能的重要基础 一阶逻辑对AI的贡献： 提出了陈述性知识表示方式 ； 将知识描述与知识处理相分离； 基于一阶逻辑扩展了多种应用逻辑 --- 如时序 ( p53 )、模糊、非单调等多种应用逻辑。 基于逻辑的问题求解方法 一阶逻辑的基本概念回顾 一阶谓词逻辑知识表示方法 一阶谓词逻辑的符号体系 - 字符表 常元: 变元: 函数(词)符: 谓词符: 逻辑联词: 量词: 其它: 一阶逻辑的基本概念回顾 一阶谓词逻辑的符号体系 字符表 项、谓词合式公式 等价公式 演绎推理方法 项、谓词合式公式 项： 等价公式 等价公式 演绎推理方法 解释与赋值 解释定义: 一个解释 I 由以下四部分组成。 （1）指定一个非空集合 DI，称为 I 的论域； （2）对于每个常元 a，指定 DI 中的一个元素 aI； （3）对于每个n元函数符号 f，指定DI上的一个n元运算符 fI （4）对于每个n元谓词符号 P，指定DI上的一个 n 元谓词 PI 解释与赋值 赋值定义: 设 I 是一个解释，将所有变元组成的集合映射到论域 DI 的函数称为 I 中的赋值v。 基于逻辑的问题求解方法 机器演绎推理技术 – 归结法 谓词公式的规范化 谓词公式的合取范式 合取范式的子句集形式 推理过程规范化 命题逻辑归结原理 变量置换与合一 谓词归结证明系统的相关技术 谓词公式的子句形式 文字： 子句： 空子句： 基子句： 子句的标准范式 无? 型前束合取范式: 子句的标准范式 合式谓词公式化子句集步骤 ( p43 ) 合式公式化子句集实例 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)))消? 习题：将谓词公式化为子句形式 ? (?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 命题逻辑归结原理 归结定义： 设C1,C2是任意的两个命题子句，其中， C1 = L1 ? C1’ , C2 = L2 ? C2’ ，L1, L2是互补原子命题，即 L1 = ? L2。那么，分别从 C1 和 C2 中删去 L1 和 L2，将其余部分组成的一个新的析取式 C = C1’ ? C2’ 称为 C1 和 C2 的归结式。 命题逻辑归结原理 归结定义应用例: 命题逻辑归结原理 定理：子句 C1 和 C2 的归结式 C 是 C1 和 C2 的逻辑推论，即， ? C1, C2 ? |= C 。 命题逻辑归结原理 命题归结算法： 将已知前提公式集 A 化为子句集 SA； 命题逻辑归结原理应用实例 A = ? P, (P ? Q) ? R, (S ? 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, t