我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:2019跑狗图高清彩图 > 语义树 >

人工智能_2 ppt课件ppt

归档日期:07-27       文本归类:语义树      文章编辑:爱尚语录

  1.本站不保证该用户上传的文档完整性,不预览、不比对内容而直接下载产生的反悔问题本站不予受理。

  第二章 归结推理方法 概述 命题逻辑的归结法 子句形 Herbrand定理 归结原理 归结过程的策略控制 第二章 归结推理方法 概述 命题逻辑的归结法 子句形 Herbrand定理 归结原理 归结过程的策略控制 概述 归结原理由J.A.Robinson由1965年提出。 与演绎法完全不同,新的逻辑演算算法。 一阶逻辑中,至今为止的最有效的半可判定的算法。即,一阶逻辑中任意恒真公式,使用归结原理,总可以在有限步内给以判定。 语义网络、框架表示、产生式规则等等都是以推理方法为前提的。即,有了规则已知条件,顺藤摸瓜找到结果。 而归结方法是自动推理、自动推导证明用的。(“数学定理机器证明”) 本课程只讨论一阶谓词逻辑描述下的归结推理方法,不涉及高阶谓词逻辑问题。 第二章 归结推理方法 概述 命题逻辑的归结法 子句形 Herbrand定理 归结原理 归结过程的策略控制 第二章 归结推理方法 概述 命题逻辑的归结法 子句形 Herbrand定理 归结原理 归结过程的策略控制 命题逻辑的归结法 基本单元:简单命题(陈述句) 例: 命题: A1、A2、A3 和 B 求证: A1ΛA2ΛA3成立,则B成立, 即:A1ΛA2ΛA3 → B 反证法:证明A1ΛA2ΛA3Λ~B 是矛盾式 (永假式) 命题逻辑的归结法 建立子句集 合取范式:命题、命题和的与, 如: PΛ( P∨Q)Λ( ~P∨Q) 子句集S:合取范式形式下的子命题(元素)的集合 例:命题公式:PΛ( P∨Q)Λ( ~P∨Q) 子句集 S:S = {P, P∨Q, ~P∨Q} 命题逻辑的归结法 归结式 消除互补对,求新子句→得到归结式。 如子句:C1, C2, 归结式:R(C1, C2) = C1ΛC2 ? 注意:C1ΛC2 → R(C1, C2) , 反之不一定成立。 命题逻辑的归结法 归结过程 将命题写成合取范式 求出子句集 对子句集使用归结推理规则 归结式作为新子句参加归结 归结式为空子句□ ,S是不可满足的(矛盾),原命题成立。 ? (证明完毕) 谓词的归结:除了有量词和函数以外,其余和命题归结过程一样。 第二章 归结推理方法 概述 命题逻辑的归结法 子句形 Herbrand定理 归结原理 归结过程的策略控制 第二章 归结推理方法 概述 命题逻辑的归结法 子句形 Herbrand定理 归结原理 归结过程的策略控制 子句形 引用Herbrand定理,以说明归结原理的意义及一个原理形成的根基与背景 SKOLEM标准形 前束范式:把所有的量词都提到前面去,然后消掉所有量词。 定义:说公式A是一个前束范式,如果A中的一切量词都位于该公式的最左边(不含否定词),且这些量词的辖域都延伸到公式的末端。 子句形( Skolem 标准形) ? ? ? ? ? ? ? ? ? ? ? ? ? 量词消去原则: 消去存在量词“?”,略去全程量词“?”。 注意:左边有全程量词的存在量词,消去时该变量改写成为全程量词的函数;如没有,改写成为常量。 子句形( Skolem 标准形) ? ? ? ? ? ? ? ? ? ? ? ? ? 定理: 谓词逻辑的任意公式都可以化为与之等价的前束范式,但其前束范式不唯一。 SKOLEM标准形定义: 消去量词后的谓词公式。 注意:谓词公式G的SKOLEM标准形同G并不等值。 子句形( Skolem 标准形) ? ? ? ? ? ? ? ? ? ? ? ? ? 例: 子句形 子句与子句集 文字:不含任何连接词的谓词公式。 子句:一些文字的析取(谓词的和)。 子句集S的求取: G → SKOLEM标准形 → 消去存在变量 → 以“,”取代“Λ”,并表示为集合形式 。 子句形 G是不可满足的= S是不可满足的 G与S不等价,但在不可满足得意义下是一致的。 定理: 若G是给定的公式,而S是相应的子句集,则G是不可满足的= S是不可满足的。 注意:G真不一定S真,而S真必有G真。 即: S = G 子句形 G = G1Λ G2Λ G3Λ …Λ Gn 的子句形 G的字句集可以分解成几个单独处理。 有 SG = S1 U S2 U S3 U …U Sn 则SG 与 S1 U S2 U S3 U …U Sn在不可满足得意义上是一致的。 即SG 不可满足 = S1 U S2 U S3 U …U Sn不可满足 ? 第二章 归结推理方法 概述 命题逻辑的归结法 子句形 Herbrand定理 归结原理 归结过程的策略控制 第二章 归结推理方法 概述 命题逻辑的归结法 子句形 Herbrand定理 归结原理 归结过程的策略控制 Herbrand定理 问题: 一阶逻辑公式的永真性(永假性)的判定是否能在有限步内完成? Herbrand定理 1936年图灵(Turing)和邱吉(Church)互相独立地证明了: Herbrand定理 Herbrand的思想 定义: 公式G永真:对于G的所有解释,G都为真。 思想: 寻找一个已给的公式是真的解释。然而,如果所给定的公式的确是永假的,就没有这样的解释存在,并且算法在有限步内停止。 Herbrand定理 H域 H解释 语义树 结论:Herbrand定理 Herbrand定理 H域 H解释 语义树 结论:Herbrand定理 Herbrand定理(H域) 基本方法: 因为量词是任意的,所讨论的个体变量域D是任意的,所以解释的个数是无限、不可数的 。 简化讨论域。建立一个比较简单、特殊的域,使得只要在这个论域上,该公式是不可满足的。 此域称为H域。 ※ 例题请参考教科书P27 Herbrand定理(H域) 几个基本概念 f(tn):f为子句集S中的所有函数变量。t1, t2, …tn为S的H域的元素。通过它们来讨论永真性。 原子集A:谓词套上H域的元素组成的集合。如 A = {所有形如 P(t1, t2, …tn)的元素} 即把H中的东西填到S的谓词里去。S中的谓词是有限的,H是可数的,因此,A也时可数的。 一旦原子集内真值确定好(规定好),则S在H上的真值可确定。成为可数问题。 Herbrand定理 H域 H解释 语义树 结论:Herbrand定理 Herbrand定理 H域 H解释 语义树 结论:Herbrand定理 Herbrand定理(H解释) 解释I:取一个值得到一个结论 I映射S中到所有常量符号到它们本身。(即原子集) 令f是n元函数,I是f下的一个指派,即H中的元素到f的一个映射(函数值)。简单地说(P29),A中的各元素真假组合都是H的解释。(或真或假只取一个) 问题: 对于所有的解释,全是假才可判定。因为所有解释代表了所有的情况,如可穷举,问题便可解决 。 Herbrand定理(H解释) 如下三个定理保证了归结法的正确性: 定理1: 设I是S的论域D上的解释,存在对应于I的H解释I*,使得若有SI = T,必有 SI* = T。 定理2: 子句集S是不可满足的,当且仅当所有的S的H解释下为假。 定理3: 子句集S是不可满足的,当且仅当对每一个解释I下,至少有S的某个子句的某个基例为假。 Herbrand定理(H解释) 基例 S中某子句中所有变元符号均以S的H域中的元素代入时,所得的基子句C’称为C的一个基例。 若一个子句为假,则此解释为假。 一般来说,D是无穷不可列的,因此,子句集S也是无穷不可列的。但S确定后H是无穷可列的。不过在H上证明S的不可满足性仍然是不可能的。 解决问题的方法:语义树 Herbrand定理 H域 H解释 语义树 结论:Herbrand定理 Herbrand定理 H域 H解释 语义树 结论:Herbrand定理 Herbrand定理(语义树) 构成方法 原子集中所有元素逐层添加的一棵二叉树。将元素的是与非分别标记在两侧的分枝上(可不完全画完) 。(P34) 特点 一般情况H是可数集,S的语义树是无限树。 Herbrand定理(语义树) 意义 S ? H ? A ?语义树 可以理解语义树为H域的图形解释。 目的:把每个解释都摊开。语义树中包含原子集的全部元素,因此,语义树是完全的。每一个直到叶子节点的分支对应S的一个解释。可以通过对语义树每一个分支来计算S的真值。如果每个基例都为假,则可认为是不可满足的。 Herbrand定理(语义树) 几个概念 失败结点: 当(由上)延伸到点N时,I(N)已表明了S的某子句的某基例假。但N以前尚不能判断这事实。就称N为失败结点。 封闭语义树: 如果S的完全语义树的每个分枝上都有一个失败结点,就称它是一棵封闭语义树。 Herbrand定理 H域 H解释 语义树 结论:Herbrand定理 Herbrand定理 H域 H解释 语义树 结论:Herbrand定理 Herbrand定理(结论) Herbrand定理: 子句集S是不可满足的,当且仅当对应于S的完全语义数是棵有限封闭树。 子句集S是不可满足的,当且仅当存在不可满足的S的有限基例集。 Herbrand定理(结论) 定理的意义 Herbrand定理已将证明问题转化成了命题逻辑问题。 由此定理保证,可以放心的用机器来实现自动推理了。(归结原理) 注意 Herbrand定理给出了一阶逻辑的半可判定算法,即仅当被证明定理是成立时,使用该算法可以在有限步得证。而当被证定理并不成立时,使用该算法得不出任何结论。 但是 ? ? ? ? ? ? ? ? ? ? ? ? ? Herbrand定理(结论) 仍存在的问题: 基例集序列元素的数目随子句基的元素数目成指数地增加。 因此,Herbrand定理是30年代提出的,始终没有显著的成绩。 ??? 直至1965年Robinson提出了归结原理。 第二章 归结推理方法 概述 命题逻辑的归结法 子句形 Herbrand定理 归结原理 归结过程的策略控制 第二章 归结推理方法 概述 命题逻辑的归结法 子句形 Herbrand定理 归结原理 归结过程的策略控制 归结原理 归结原理正确性的根本在于,找到矛盾可以肯定不真。 方法: 和命题逻辑一样。 但由于有函数,所以要考虑合一和置换。 (定义与例题参考教科书P41) 归结原理 置换和合一的注意事项: 谓词的一致性,P()与Q(), 不可以 常量的一致性,P(a, …)与P(b,….), 不可以 变量,P(a, ….)与P(x, …), 可以 变量与函数,P(a, x, ….)与P(x, f(x), …),不可以;但P(a, x, …)与P(x, f(y), …),可以 是不能同时消去两个互补对,P∨Q与~P∨~Q的空,不可以 先进行内部简化(置换、合并) 归结原理 归结的过程(P48) 写出谓词关系公式 → 用反演法写出谓词表达试 → SKOLEM标准形 → 子句集S → 对S中可归结的子句做归结 → 归结式仍放入S中,反复归结过程 → 得到空子句 ?得证 归结原理 归结法的实质: 归结法是仅有一条推理规则的推理方法。 归结的过程是一个语义树倒塌的过程。 (P51) 归结法的问题 子句中有等号或不等号时,完备性不成立。 ※ Herbrand定理的不实用性引出了可实用的归结法。 第二章 归结推理方法 概述 命题逻辑的归结法 子句形 Herbrand定理 归结原理 归结过程的策略控制 第二章 归结推理方法 概述 命题逻辑的归结法 子句形 Herbrand定理 归结原理 归结过程的策略控制 归结过程的控制策略 要解决的问题: 归结方法的知识爆炸。 控制策略的目的 归结点尽量少 控制策略的原则 给出控制策略,以使仅对选择合适的子句间方可做归结。避免多余的、不必要的归结式出现。或者说,少做些归结仍能导出空子句。 归结过程的控制策略 控制策略的方法 删除 = 完备 采用支撑集 =完备 语义归结 = 完备 线性归结 =完备 单元归结 = 完备 输入归结 = 完备 第二章 归结推理方法 The End. 本课程的讨论站点正式开通(166.111.68.51) 在网络上放有pdf格式的41篇论文,分7类,供同学们阅读。 阅读讨论论文内容 1999年特邀报告 1999年获奖论文 认知模型 分布式人工智能 机器学习 自然语言处理 * * “没有一般的方法使得在有限步内判定一阶逻辑的公式是否是永真(或永假)。但是如果公式本身是永真(或永假)的,那么就能在有限步内判定它是永真(或永假)。对于非永真(或永假)的公式就不一定能在有限步内得到结论。判定的过程将可能是不停止的。” *

本文链接:http://furymagazine.com/yuyishu/207.html