week8 北航6系人工智能ppt课件.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 ),得摩根定律： (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为常元.。,演绎推理,演绎推理方法,推理：根据一定准则，由前提判断导出称为结论的思维过程。,演绎推理、归纳推理、类比推理,推理方式：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 析取式 L1 L2 Ln子句集SA=A1, A2, An 无 型前束合取范式,子句的标准范式,无 型前束合取范式:,（Q1x1）(Q2x2）（Qnxn）M 其中， Qi：全称量词； xi：变元母式：M = (A11 A12 A1n ) (Am1 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) 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 为永假的充要条件是 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 。,推论：设 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 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）处处替换表达式 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 （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，则称表达式集 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 ),变量的置换与合一,最一般合一者（mgu Most General Unifier） 是表达式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 实例Ei 1 = 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 = L1 C1 , C2 = L2 C2 ，L1, L2是可化为互补文字的两个原子谓词公式,（即二者间存在最一般合一者mgu ）。那么，C1 和 C2 的归结式 C 可由下式求得：C= C1-L1 C2-L2 = C1 C2,一阶谓词归结原理演算实例,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 ； Until CLAUSES, do: begin 从 CLAUSES中选择两个不同的可归结子句 C1和 C2； 对 C1 和 C2 中互反文字进行归结，获归结式 C，且 CLAUSES = CLAUSES C ； 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 = S0 1级归结式 。 第i级：Si -1中所有可能归结的子句对进行归结，产生全部归结式，将其加到归结子句集 Si -1中获新的归结子句集 Si = Si -1 第 i 级归结式 。,归结策略特点： 策略完备，搜索效率低。,推理策略分析改进（1）,策略分析： 由于前提公式集中并无矛盾，推理反驳是由待证结论的否定式加入引起的。因此，有支持集策略。,支持集策略特点： 每次归结的选用的母子句对中至少有一个母子句是与目标公式否定式 有关的子句，即它或是目标公式否定式 本身或是否定式的后裔。,推理策略实例 - 支持集策略（1）,s0,s1,s2,s3,推理策略实例-支持集策略（2）,归结策略运用过程： 第一级：原始子句集 S0 中所有能与目标公式否定式 归结的子句对进行归结，产生全部可能的归结式，将其加到 S0 中获新的归结子句集 S1 = S0 1级归结式 。 第i级：Si -1 中所有能与目标公式否定式 及其后裔归结的子句对进行归结，产生全部可能的归结式，将其加到 Si 1 中获新的归结子句集 Si = Si -1 第i级归结式,归结策略特点：,策略完备，搜索效率相对高。,推理策略分析改进（2）,策略分析： 由于归结的过程最终要产生长度为零的空子句。为了加快归结进度，因此，有单元归结策略。,单元归结策略特点： 每次归结时，优先选取单元子句（只含有一个文字的子句）作为母子句进行归结。,推理策略实例- 单元归结策略（1）,P ,归结策略特点： 此策略可缩短归结过程，能大大提高搜索效率。 策略不完备，S 中无单子句时，无法进行归结。,归结实例： S = R, PR, QR, P Q,Q,推理策略分析改进（3）,策略分析： 综合多种归结搜索策略特征，有利于提高搜索的有效性和完备性。因此，有线性归结策略。,线性归结策略特点： 与诸如“支持集策略”、“单元集策略”等搜索策略特征相容，可视为多种策略的组合。,线性归结策略（1）,设子句集 S,顶子句 C0 和 B0 S，从 S到 Cn 推理序列中产生线性归结式 Ci（0in)的任意归结母式 Ci-1和 Bi-1 均应满足以下条件：,Ci-1是 Ci 直接上一级的线性归结式； Bi-1或者属于子句集S，或是某个已知的线性归结式 Cj(ji)； 分别称 Ci-1 和 Bi-1 为中心子句和边子句。,线性归结策略（2）,线性归结例：设 S=A B, A B, A B, A B ,B,A B,A, A B, 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子句。例： A1 A2 An B 等价式： A1 A2 An B,PROLOG: 基于Horn子句的逻辑程序描述语言； 优点：1、表达能力强：凡能用一阶逻辑描述的问题均可用Horn子句表达2、表达直观、推理简单,若有：W L1 L2，可化为：W L1，W L2,基于规则的演绎推理 - PROLOG,描述： 待证目标库： G 规则集： B C G, D B, 事实库： C， D ,推理策略： 线性归结策略。,已知事实库:F1: Dog(sid); F2: Barks(sid); F3: Tail(sid);F4: Meows(mik).,蕴涵规则库: R1: Dog(x) Tail(x) Kind(x); R2: Kind(s) Barks(s) Afraid(x,s); R3: Dog(u) Animal(u); R4: Cat(v) Animal(v); R5: Meows(w) Cat(w).,目标: ( x) ( y)(Cat(x) Dog(y) Afraid(x,y),PROLOG 演绎推理实例,基于规则的逆向演绎系统实例,Cat (x1) Dog (y1) Afraid (x1, y1),Cat (w),Scat (x1),Scat (mik),Dog (sid),Afraid (z, s),Kind(x),Dog (sid),Tail(Sid), Bark(sid),基于规则的演绎系统小结,基于目标驱动的初始表达式形式 推理过程中规则的变换过程 合一匹配与一致解图的求解过程,无矛盾、无残缺、经合一匹配的与或解图。,基于蕴涵规则的推理,AI中的应用逻辑,各种应用逻辑 时态逻辑 模态逻辑 模糊逻辑 ,对一阶逻辑的改进 语法结构方面的改进 推理方法方面的改进,习题1：将谓词公式化为子句形式, (x)P(x) (x ) P(x) (x)(P(x) ( (y)(P(y) P(f(x,y) (y)(Q(x,y) P(y),利用线性归结策略求证下列公式永真: (x)(P(x) (Q(A) Q(B) ( x)(P(x) Q(x),习题2：,等价求证:(x) (P (x) (Q(A) Q(B) |= ( x) (P (x) Q (x)(x) (P (x) (Q(A) Q(B), ( x) (P (x) Q (x) |=,习题3：合一匹配算法应用,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),