我要投搞

标签云

收藏小站

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

当前位置:管家婆六肖中特 > 非单调推理 >

人工智能5第五章 确定性推理

归档日期:05-05       文本归类:非单调推理      文章编辑:爱尚语录

  人工智能5第五章 确定性推理_物理_自然科学_专业资料。第四章 确定性推理 2013-6-6 1 第四章 确定性推理 4.1概述 4.1 确定性推理概述 2013-6-6 2 第四章 确定性推理 4.1概述 推 理 ? 推理是指按照

  第四章 确定性推理 2013-6-6 1 第四章 确定性推理 4.1概述 4.1 确定性推理概述 2013-6-6 2 第四章 确定性推理 4.1概述 推 理 ? 推理是指按照某种策略从巳知事实出发去推出结论 的过程 ? 智能系统的推理过程实际上就是一种思维过程。 ? 智能系统的推理过程是通过推理机来完成的。 ? 推理机就是智能系统中用来实现推理的程序。 ? 按照推理过程所用知识的确定性,推理可分为确定 性推理和不确定性推理。 2013-6-6 3 第四章 确定性推理 4.1概述 事 实 ?事实是推理过程中按知识表示方 式表示的已知的知识 ?推理所用的事实可分为两种情况: ?与求解问题有关的初始证据. ?推理过程中所得到的中间结论。 2013-6-6 4 第四章 确定性推理 4.1概述 推理的基本问题 ?智能系统的推理包括两个基本问题: ?一个是推理的方法 ?一个是推理的控制策略 ? 推理方法主要解决: ?在推理过程中前提与结论之间的逻辑关系 ?在非精确性推理中不确定性的传递问题 2013-6-6 5 第四章 确定性推理 4.1概述 推理方法的分类 ? 推理可以有多种不同的分类方法 ? 按照推理的逻辑基础分类: ?演绎推理 ?归纳推理 ?默认推理 ? 按照所用知识的确定性分类: ?确定性推理 ?不确定性推理 ? 按照推理过程的单调性分类(推理过程所得到的 结论是否越来越接近目标): ?单调推理 ?非单调推理 2013-6-6 6 第四章 确定性推理 4.1概述 演绎推理 ? 从已知的一般性知识出发,去推出蕴含在 这些已知知识中的适合于某种个别情况的 结论。 ?它是一种由一般到个别的推理方法。 ?核心是三段论 2013-6-6 7 第四章 确定性推理 4.1概述 归纳推理 ? 从一类事物的大量特殊事例出发,去推出该类 事物的一般性结论。 ? 它是一种由个别到一般的推理方法。 ? 基本思想: ?先从已知事实中猜测出一个结论,然后对这个结论的 正确性加以证明确认 ? 数学归纳法就是归纳推理的一种典型例子。 ? 按照所选事例的广泛性,归纳推理可分为: ?完全归纳推理和不完全归纳推理; ? 按照推理所使用的方法可分为: ?枚举归纳推理、类比归纳推理、统计归纳推理和差异 归纳推理等。 2013-6-6 8 第四章 确定性推理 4.1概述 默认推理 ? 在知识不完全的倩况下,假设某些条件已经具备所 进行的推理,因此也称为缺省推理。 ? 在推理过程中.如果发现原先的假设不正确,就撤 销原来的假设以及由此假设所推出的所有结论。 ? 重新按新情况进行推理。 ? 解决了在一个不完备的知识集中进行推理的问题。 2013-6-6 9 第四章 确定性推理 4.1概述 推理过程的单调性 ? 按照推理过程所得到的结论是否越来越接近日标, 推理可分为单调推理与非单调推理。 ? 单调推理: ?在推理过程中,每当使用新的知识后,所得到的结论会越 来越接近于目标 ?不会出现反复情况,即不会由于新知识的加入否定了前面 推出的结论。 ? 非单调推理: ?在推理过程中,当某些新知识加入后,会否定原来推出的 结论。 ? 非单调推理往往是在知识不完全的情况下发生的。 2013-6-6 10 第四章 确定性推理 4.1概述 推理控制策略 ?推理的控制策略是在推理过程中 采用的、解决如何使用领域知识 使推理过程尽快达到目标的策略。 2013-6-6 11 第四章 确定性推理 4.1概述 推理控制策略分类 ?智能系统的推理过程一般表现为一种搜索 过程,因此,推理的控制策略又可分为推 理策略和搜索策略。 ?推理策略主要解决推理方向、冲突消解等 问题。 ?搜索策略主要解决推理线路、推理效果、 推理效率等问题。 2013-6-6 12 第四章 确定性推理 4.1概述 推理方向 ?推理方向确定推理过程是从初始证据开始 到目标,还是从目标开始到初始证据。按 照对推理方向的控制,推理可分为正向推 理、逆向推理、混合推理及双向推理四种 情况。 2013-6-6 13 第四章 确定性推理 4.1概述 正向推理 ? 正向推理是一种从已知事实出发、正向使用推理规 则的推理方式,亦称为数据驱动推理。 ? 基本思想是: ?用户需要事先提供一组初始证据,并将其放入综合数据库。 ?推理机根据综合数据库中的已有事实,到知识库中寻找当前 可用知识,形成一个当前可用知识集。 ?按照冲突消解策略,从该知识集中选择一条知识进行推理, 并将新推出的事实加入综合数据库,作为后面继续推理时可 用的巳知事实, ?重复这一过程,直到求出所需要的解或者知识库中再无可用 知识为止 2013-6-6 14 第四章 确定性推理 4.1概述 逆向推理 ? 逆向推理是一种从以某个假设目标作为出发点的推 理方法,亦称为目标驱动推理 ? 基本思想是: ?将要求证的目标(称为假设)构成一个假设集。 ?取一个假设对其进行验证, ?若在综合数据库里,则假设成立 ?若能被用户认定为事实,则假设成立,并放入综合数据库 ?若可由知识库中的一个或多个知识导出,则这些知识构成可 用知识集。按照冲突消解策略,从该知识集中选择一条知识, 将其前提中的所有子条件作为新的假设加入假设集。 ?重复这一过程,直到假设集为空或假设集非空但可用知识集 空为止 2013-6-6 15 第四章 确定性推理 4.1概述 混合推理 ? 正向推理和逆向推理都有各自的优缺点。当 问题较复杂时,单独使用其中哪一种,都会 影响到推理效率。 ?为了取长补短.可将它们结合起来使用。 ?这种把正向推理和逆向推理结合起来所进行 的推理称为混合推理。 2013-6-6 16 第四章 确定性推理 4.1概述 混合推理的实现方法 ?混合推理可有多种具体的实现方法 ?先正向推理,后逆向推理的方法 ?先逆向推理,后正向推理的方法 ?采用随机选择正向和逆向推理的方法 (双向混合推理) 2013-6-6 17 第四章 确定性推理 4.1概述 混合推理的适用场合 ?已知事实不够充分。 ?由正向推理推出的结论可信度不高 ?希望得出更多的结论 ?希望从正反两个方向同时进行推理 2013-6-6 18 第四章 确定性推理 4.1概述 冲突消解策略 ? 冲突消解策略是指当推理过程有多条知识可用时,如 何从这多条可用知识中选出一条最佳知识用于推理的 策略。 ? 冲突消解的基本思想是对可用知识进行排序。 ? 常用的冲突消解策略有: ?特殊知识优先 ?新鲜知识优先 ?差异性大的知识优先 ?领域特点知识优先 ?上下文关系知识优先 ?前提条件少的知识优先 2013-6-6 19 第四章 确定性推理 4.2自然演绎推理 自然演绎推理 ? 从一组己知为真的事实出发,直接运用经典逻辑中 的推理规则推出结论的过程称为自然演绎推理。 ? 在自然演绎推理中,需要避免两类错误: ?肯定后件的错误和否定前件的错误。 ? 优点: ?定理证明过程自然,易于理解,有丰富的推理规则 ? 主要缺点: ?容易产生知识爆炸,推理过程中得到的中间结论一般按指 数规律递增,对于复杂问题的推理不利,甚至难以实现。 ? 因此,提出了归结演绎推理 2013-6-6 20 第四章 确定性推理 4.3归结演绎推理 归结演绎推理 ? 归结演绎推理是一种基于归结原理的推理方法。 ? 归结原理亦称消解原理,是鲁宾逊1965年提出的 ? 归结演绎推理实际上是一种“反正法”,基本思想: ? 推理就是要对前提P和结论Q,证明P ? Q永真。 ?这就要证明P ? Q在任何一个非空的个体域上都是 永真的。这将是非常困难的,甚至是不可实现的。 ?而用反证法,只要能够证明~(P ? Q)是不可满足 的。 2013-6-6 21 第四章 确定性推理 4.3归结演绎推理 子句和子句集 ?原子谓词公式及其否定都称为文字 ?文字的析取构成的公式称为子句 ?不包含任何文字的子句称为空了句 ?空子句不包含任何文字,因此,不能被任何 指派所满足 ?所以空子句是不可满足的 ?子句集中的子句之间是合取关系 ?含空子句的子句集也就一定是不可满足的。 2013-6-6 22 第四章 确定性推理 4.3归结演绎推理 谓词公式转化为子句集 ? ? ? ? ? ? ? ? ? 消去蕴涵符号: ~ P∨Q取代P→Q 减少否定符号的管辖域 对变量标准化 消去存在量词 化为前束形 化为合取范式: 如:PΛ(P∨Q)Λ(~P∨Q) 消去全称量词 获得子句集 更换变量名 2013-6-6 23 第四章 确定性推理 4.3归结演绎推理 化子句集例 例:(?z) (?x)(?y){[(P(x) ?Q(x)) ?R(y)] ?U(z)} 1, 消蕴涵符 理论根据:a ?b = ~a ?b (?z) (?x)(?y){[~(P(x) ?Q(x)) ? R(y)] ?U(z)} 2, 移动否定符 理论根据:~(a ?b) = ~a ?~b ~(a ?b) = ~a ?~b ~(?x)P(x)=(?x)~P(x) ~(?x)P(x)=(?x)~P(x) (?z) (?x)(?y){[(~P(x) ?~Q(x)) ? R(y)] ?U(z)} 2013-6-6 24 第四章 确定性推理 4.3归结演绎推理 化子句集例(续1) 3, 变量标准化 即:对于不同的约束,对应于不同的变量 (?x)A(x) ? (?x)B(x) = (?x)A(x) ? (?y)B(y) 4, 量词左移 (?x)A(x) ? (?y)B(y) = (?x) (?y) {A(x) ? B(y)} 5, 消存在量词 (skolem化) 原则:对于一个受存在量词约束的变量,如果他 不受全程量词约束,则该变量用一个常量代替, 如果他受全程量词约束,则该变量用一个函数代 替。 (?z) (?x)(?y){[(~P(x) ?~Q(x)) ? R(y)] ?U(z)} = (?x) {[(~P(x) ?~Q(x)) ? R(f(x))] ?U(a)} 2013-6-6 25 第四章 确定性推理 4.3归结演绎推理 化子句集例(续2) 6, 化为合取范式 即(a?b) ? (c?d) ? (e?f)的形式 (?x){[(~P(x) ?~Q(x)) ? R(f(x))]?U(a)} = (?x){(~P(x) ?~Q(x)) ? R(f(x))?U(a)} = (?x){[~P(x) ? R(f(x))?U(a)] ? [~Q(x))? R(f(x))?U(a)]} 7, 隐去全程量词 {[~P(x) ? R(f(x))?U(a)] ?[~Q(x))? R(f(x))?U(a)]} 2013-6-6 26 第四章 确定性推理 4.3归结演绎推理 化子句集例(续3) 8, 表示为子句集 {~P(x) ? R(f(x))?U(a), ~Q(x))? R(f(x))?U(a)} 9, 变量标准化(变量换名) {~P(x1) ? R(f(x1))?U(a), ~Q(x2))? R(f(x2))?U(a)} 2013-6-6 27 第四章 确定性推理 4.3归结演绎推理 归结(消解)原理基本思想 ?首先把欲证明问题的结论否定,并加入子 句集,得到一个扩充的子句集S’。 ?检验子句集S’是否含有空子句 ?若不含空子句,则继续使用归结法,在子 句集中选择合适的子句进行归结 ?直至导出空子句或不能继续归结为止。 2013-6-6 28 第四章 确定性推理 4.3归结演绎推理 归结原理分类 ? 鲁宾逊归结原理可分为: ?命题逻辑归结原理 ?谓词逻辑归结原理 2013-6-6 29 第四章 确定性推理 4.3归结演绎推理 归结式 ? 归结推理的核心是求两个子句的归结式 ? 若P是原子谓词公式,则称P与~P为互补文字 ? 设C1和C2是子句集中的任意两个子句 ? 如果C1中的文字L1与C2中的文字L2互补 ? 那么可从C1和C2中分别消去L1和L2 ? 并将C1和C2中余下的部分按析取关系构成一个新 的子句C12, ? 则称这一过程为归结, ? 称C12为C1和C2的归结式,C1和C2为C12的亲本 子句。 2013-6-6 30 第四章 确定性推理 4.2归结演绎推理 消解过程举例 ? ? E2 ∨ E1 (前提) ~ E2 ∨ E3 (前提) ? (消解式) E1 ∨ E3 (结论) 2013-6-6 31 第四章 确定性推理 4.2归结演绎推理 命题逻辑的消解推理举例 假言推理:P ~P∨Q (P→Q) 合并:P∨Q ~P∨Q 消解式:Q 重言式:P ∨Q ~P∨~Q 消解式:Q∨Q = Q 空子句:P ~P 消解式:P∨~P 或 Q∨~Q 消解式:NIL 三段论: ~P∨Q (P→Q) ~Q∨R (P→Q) (Q→R) 消解式:~P∨R 2013-6-6 32 第四章 确定性推理 4.2归结演绎推理 谓词逻辑的消解推理举例 B(x) ~B(x)∨C(x) P(x)∨Q(x) 消解式:P[f(y)] ~Q[f(y)] 臵换:f(y)/x 消解式:C(x) P[x,f(y)]∨Q(x)∨R[f(a),y] ~P[f(f(a)),z]∨R(z,w) 臵换:f(f(a))/x, f(y)/z 消解式:Q[f(f(a))]∨R[f(a),y]∨R[f(y),w] 2013-6-6 33 第四章 确定性推理 4.2归结演绎推理 消解反演 ?消解反演是利用消解原理进行推理的过程。 ?消解反演的推理过程: ?给定公式集S和目标公式L ?证明公式L的步骤如下: ?否定L ,得~L ?把~L 添加到S中去 ?把新产生的集合{~L ,S}化成子句集 ?应用消解原理力图推导出一个表示矛盾的空子 句 2013-6-6 34 第四章 确定性推理 4.2归结演绎推理 命题逻辑消解反演的例子 设公理集: P, (P?Q) ?R, (S?T) ?Q, T 求证:R 子句集: (1) P (2) ~P?~Q?R (3) ~S?Q (4) ~T?Q (5) T (6) ~R(目标求反) 2013-6-6 化子句集: (P?Q) ?R = ~(P?Q)?R = ~P?~Q?R (S?T) ?Q = ~ (S?T)?Q = (~S?~T)?Q = (~S?Q) ?(~T?Q) = {~S?Q, ~T?Q} 35 第四章 确定性推理 4.2归结演绎推理 命题逻辑消解反演的例子(续) 子句集: (1) P (2) ~P?~Q?R (3) ~S?Q (4) ~T?Q (5) T (6) ~R(目标求反) 归结: (7) ~P?~Q (8) ~Q (9) ~T (10) nil (2, 6) (1, 7) (4, 8) (5, 9) 2013-6-6 36 第四章 确定性推理 4.2归结演绎推理 谓词逻辑消解反演的例子 ?例:已知:If Fido goes wherever John goes and if John is at school, where is Fido ? (?x)[AT(John, x) ? AT(Fido, x)] AT(John, School) 求证:(?x)AT(Fido, x) 子句集: ~AT(John, y) ? AT(Fido, y) AT(John, School) ~AT(Fido, x) ( ~(?x)AT(Fido, x) = (? x) ~AT(Fido, x) ) 2013-6-6 37 第四章 确定性推理 4.2归结演绎推理 谓词逻辑消解反演的例子(续) 子句集: ~AT(John, y) ? AT(Fido, y) AT(John, School) ~AT(Fido, x) ~AT(John, y) ?AT(Fido, y) {x/y} AT(John, School) ~AT(John, x) {School/x} 2013-6-6 ~AT(Fido, x) nil AT(Fido, School) 38 第四章 确定性推理 4.2归结演绎推理 基于消解原理的问答系统 ?消解原理主要用来解决证明的问题,但有 时我们希望得到如x=?时,W(x)为真的回答 ?消解原理是将结论的否定作为前提进行归 结,而为了回答问题,用由结论的否定构 成的重言式作为前提进行归结,得到的结 论是问题的回答而不是空语句。这个过程 称为修改证明过程(或修改归结过程)。 ?下面以猴子摘香蕉问题为例来说明 2013-6-6 39 第四章 确定性推理 4.2归结演绎推理 用消解原理解猴子摘香蕉问题 ? 为了把状态空间的算符描述与谓词演算结合起来, 将状态添到谓词上; ? 将算符看成是把一种状态映射成另一种状态的函数; ? 问题简化成没有goto()规则; c 2013-6-6 40 第四章 确定性推理 4.2归结演绎推理 猴子摘香蕉问题的表示 问题可以描述如下: 1, ~ONBOX(s0) 2, (?x)(?s)(~ONBOX(s) ? AT(box, x, push(x, s))) 3, (?s)(ONBOX(climbbox(s))) 4, (?s)((ONBOX(s) ? AT(box, c, s)) ? HB(grasp(s))) 5, (?x)(?s)(AT(box, x, s) ? AT(box, x, climb(s))) 求解:(?s)HB(s) 2013-6-6 41 第四章 确定性推理 4.2归结演绎推理 猴子摘香蕉问题的子句集 1, ~ON(s0) 2, ON(s1) ? AT(box, x1, push(x1, s1)) 3, ON(climb(s2)) 4, ~ON(s3) ? ~AT(box, c, s3) ? HB(grasp(s3)) 5, ~AT(box, x4, s4) ?AT(box, x4, climb(s4)) 6, ~HB(s5) 2013-6-6 42 第四章 确定性推理 HB(s5) ? ~HB(s5) 4.2归结演绎推理 ~ON(s3) ? ~AT(box, c, s3) ? HB(grasp(s3)) {grasp(s3)/s5} 猴 子 摘 香 蕉 问 题 的 ( 修 正 ) 消 解 树 HB(grasp(s3)) ? ~ON(s3) ? ~AT(box, c, s3) ON(climb(s2)) {climb(s2)/s3} ~AT(box, c, climb(s2)) ~ON(s0) ? HB(grasp(climb(s2))) ON(s1) ? AT(box, x1, push(x1, s1)) {s0/s1} AT(box, x1, push(x1, s0)) {x4/x1,push(x4,s0)/s4} ~AT(box, x4, s4) ?AT(box, x4, climb(s4)) AT(box, x4, climb(push(x4,s0))) {c/x4,push(c,s0)/s2} 43 2013-6-6 NIL HB(grasp(climb(push(c,s0)))) 第四章 确定性推理 4.2归结演绎推理 归结反演的搜索策略 ? 归结反演过程是“运用归结规则直到产生空子句 为止” ? 在对子句集进行归结时,一个关键问题是如何选 择子句进行归结。 ? 如果对任意一对可以归结的子句都做归结,这样 不仅消耗很多的时间,还会产生许多无用的归结 式,占用很多空间 ? 因此,需要研究有效的归结控制(搜索)策略。 ? 归结搜索策略一般包括:排序策略和限制策略 2013-6-6 44 第四章 确定性推理 4.2归结演绎推理 排序策略 ? 归结顺序与状态空间的扩展顺序类似。 ? 状态空间的搜索问题有多种搜索策略。 ? 把原始子句看成0层归结式。 ? (i+1)层的归结式是一个i层归结式和一个j(j≤i)层 归结式进行归结所得到的归结式。 ? 宽度优先: ?先生成第1层的所有归结式.然后是第2层所有的归结式, 依次类推,直到产生空子句或不能再进行归结为止。 ? 深度优先: ?产生一个第1层的归结式,然后用第1层的归结式和第0层的 归结式进行归结,得到第2层的归结式,直到产生空子句结 束,或者不能归结,则回溯到其他的上层子句继续归结 ? 单元优先: 2013-6-6 ?在归结过程中优先考虑仅由一个文字构成的子句,这样的 45 子句称为单元子句。 第四章 确定性推理 4.2归结演绎推理 限制策略 ?限制策略不涉及被归结子句的排序.只允 许某些归结发生。其中几种限制归结策略: ?删除策略 ?支持集策略。 ?线性输入策略。 ?祖先过滤策略。 2013-6-6 46 第四章 确定性推理 4.2归结演绎推理 删除策略 ?如果在归结时能把子句集中的无用子句删 除掉,这样就会缩小寻找范围,减少比较 次数。从而提高归结的效率。 ?删除策略有几种删除方法: ? ? ? (1)纯文字删除法。 (2)重言式删除法。 (3)包孕删除法 2013-6-6 47 第四章 确定性推理 4.2归结演绎推理 纯文字删除法 ? 如果某文字L在子句集中不存在可与之互补的文字 ~L,则称该文字为纯文字。 ? 在归结时纯文字不可能被消去,因而用包含它的子 句进行归结时不可能得到空子句。 ? 因此,这样的子句对归结是无意义的,把它从子句 集中删去,不会影响子句集的不可满足性。 ? 例如,子句集:S={PV Q VR, ~Q VR,Q,~R} ? 可以看出,P是纯文字,因此可将子句PV Q VR从S 中删去。 2013-6-6 48 第四章 确定性推理 4.2归结演绎推理 重言式删除法 ?如果一个子句中同时包含互补文字对, 则称该子句为重言式。 ?例如,P(x)VQ(x)V ~P(x)是重言式。 ?重言式是真值为真的子句。 ?对于一个子句集,增加或删去一个重言 式子句都不会影响它的不可满足性, ?因而可从子句集中删去重言式。 2013-6-6 49 第四章 确定性推理 4.2归结演绎推理 包孕删除法 ?设C1,C2是两个子句,若存在臵换σ,使得 C1σ?C2,则称子句C2包孕C1 ?例如,P(a)VQ(y)包孕P(x) (σ={a/x}) ? P(a)VQ(y)包孕Q(y) ?对于一个子句集,删去一个被别的子句包孕 的子句,不会影响它的不可满足性。 ?因而可从子句集中删去被包孕的子句。 2013-6-6 50 第四章 确定性推理 4.2归结演绎推理 支持集策略 ? 支持集策略:每次归结时.参与归结的子句中 至少应有一个是由目标公式的否定所得到的子 句,或者是它们的后裔 ? 后裔的定义:设α1是子句 ?α1 与另外某子句的归结式是α1 的后裔 ?α1 的后裔与其他子句的归结式是α1 的后裔。 ? 支持集策略是完备的。即对一个不可满足的子 句集运用支持集策略进行归结,最终总会导出 空子句。 2013-6-6 51 第四章 确定性推理 4.2归结演绎推理 线性输入策略 ? 线性输入策略:参加归结的两个子句中 至少有一个是初始子句集中的子句。 ?线性输入策略是不完备的。对于某些不可 满足的子句集,无法用线性输入归结得到 结果。 2013-6-6 52 第四章 确定性推理 4.2归结演绎推理 祖先过滤策略 ?祖先过滤策略:参与归结的两个子句中 至少有一个是初始子句集中的子句,或 者一个子句是另一个子句的祖先。 ?祖先过滤策略是线性输入策略的改进策 略,它是完备的。 2013-6-6 53 第四章 确定性推理 4.2归结演绎推理 消解方法小结 ?求子句集,进行归结,方法简单 ?通过修改证明树的方法,提取回答 ?方法通用 ?求解效率低,不宜引入启发信息 ?不宜理解推理过程 2013-6-6 54 第四章 确定性推理 4.3基于规则的演绎推理 基于规则的演绎推理(一) ? 归结反演系统解决问题的效率低下 ? 归结演绎并非人类的自然思维方式,不利于人们从 自然思维的角度组织问题的求解和提供问题求解所 需的知识 ? 基于规则的演绎推理,运用推理规则,直接推导目 标公式 ? 这符合人的自然思维方式,也能通过规则(作为启 发式知识)更有效地引导演绎推理过程。 ? 基于规则的演绎推理成为比归结反演更有效的技术, 广泛地应用于许多问题求解中 2013-6-6 55 第四章 确定性推理 4.3基于规则的演绎推理 基于规则的演绎推理(二) ? 它把知识分为两类:规则和事实 ?规则表示为if then 形式 ?事实表示为与或形 ? 规则作为启发式知识,引导演绎推理过程。 ? 事实是有关问题状态和环境的知识, ? 规则演绎的任务就是从给定的事实证明某个目 标公式成立。 ? 采用直接法而不是反演系统证明目标公式,强 调用规则进行演绎,故称基于规则的演绎推理. ? 分为两类:正向演绎和逆向演绎 2013-6-6 56 第四章 确定性推理 4.3基于规则的演绎推理——正向演绎 基于规则的正向演绎推理 ? 将非蕴涵式部分的事实表示成与或形,可用 与或图表示 ? 将蕴涵式部分的事实表示成规则 ?规则表示成形式:L ? W 其中,L是单文字,W是与或形,变量受全称量词约束 ? 将目标公式表示成子句集 ? 正向演绎推理的过程,就是将规则运用于事实 与或图,对与或图进行扩展变换的过程 ? 当与或图的叶节点包含目标公式的子句集时, 推理成功 57 2013-6-6 第四章 确定性推理 4.3基于规则的演绎推理——正向演绎 化目标公式为子句集 ? 大部分步骤与归结原理中化子句集步骤相同 ? 消存在量词 (skolem化)过程不同。对于一个受存 在量词约束的变量,消去原则: ? 如果他不受全程量词约束,则该变量用一个常量代替 ? 如果他受全程量词约束,则该变量用一个函数代替,且 全称量词变为存在量词。 (?z) (?x)(?y){[(~P(x) ?~Q(x)) ? R(y)] ?U(z)} = (? x) {[(~P(x) ?~Q(x)) ? R(f(x))] ?U(a)} ? 消存在量词 [(~P(x) ?~Q(x)) ? R(f(x))] ?U(a) ? 隐含目标公式的变量都受存在量词的约束 2013-6-6 58 第四章 确定性推理 4.3基于规则的演绎推理——正向演绎 事实表达式的与或图表示 ?用K连线表示析取,无连线表示合取 例: Q(w, A)?((~R(v) ? ~P(v)) ? ~S(A, v)) Q(w, A)?((~R(v) ? ~P(v)) ? ~S(A, v)) Q(w, A) (~R(v) ? ~P(v)) ? ~S(A, v) ~S(A, v) ~P(v) 59 ~R(v) ? ~P(v) ~R(v) 2013-6-6 第四章 确定性推理 4.3基于规则的演绎推理——正向演绎 将规则变换为限定形式 ? 如果规则不是形式:L ? W 其中,L是单文字,W是与或形,变量受全称量词约束 ?则首先变换为这种形式 ? 例:(?x)(((?y)(?z)P(x, y, z)) ? (?u)Q(x, u)) = (?x)(~((?y)(?z)P(x, y, z)) ? (?u)Q(x, u)) = (?x)((?y)(?z)~P(x, y, z) ? (?u)Q(x, u)) = (?x)(?y)(?z) (?u)(~P(x, y, z) ? Q(x, u)) = ~P(x, y, f(x, y)) ? Q(x, u) (Skolem化) = P(x, y, f(x, y)) ? Q(x, u) (恢复蕴涵式) ? 例:(L1 ? L2) ? W = L1 ? W 和 L2 ? W 2013-6-6 60 第四章 确定性推理 4.3基于规则的演绎推理——正向演绎 对与或图作变换例 ?例: 事实:((P ? Q) ? R) ? (S ? (T ? U)) 规则:S ? (X ? Y) ? Z ? 事实的与或图与规则对其进行的变换过程如 下图: 2013-6-6 61 第四章 确定性推理 4.3基于规则的演绎推理——正向演绎 P? Q? S P? Q? T? U Z S T U S? R R? T? U P? Q? X? Z P? Q? Y? Z R? X? Z R? Y? Z X X?Y P Q Y P?Q R S (P ? Q) ? R T?U 规则的子句: S ? (X ? Y) ? Z = ~S?(X ? Y) ? Z = ~S ? X ? Z ~S ? Y ? Z S ? (T ? U) ((P ? Q) ? R) ? (S ? (T ? U)) 结论:加入规则后得到的解图,是事实与规则对应子句的归结式 2013-6-6 62 第四章 确定性推理 4.3基于规则的演绎推理——正向演绎 目标公式作为终止条件 ?应用规则进行推理的目的是为了证明某 个目标公式 ?在正向推理系统中,这种目标表达式只 限于可证明的表达式,尤其是可证明的 文字析取形的目标公式表达式 ?在与或图的产生过程中,目标文字或规 则与图中文字节点匹配时,产生新后裔 节点,标记为匹配的目标文字。当产生 的图包含有终止在目标节点上的一个解 图时,系统便成功地结束。 2013-6-6 63 第四章 确定性推理 4.3基于规则的演绎推理——正向演绎 目标公式作为终止条件例一 例: 事实:A ? B 规则集: A?C?D B?E?G 目标公式: C? G 目标 C D A 匹配弧 2013-6-6 G E B B C G A A? B 64 第四章 确定性推理 4.3基于规则的演绎推理——正向演绎 目标公式作为终止条件例二 例:事实:P(x, y) ? (Q(x, A) ? R(B, y)) 规则集: P(A, B) ? (S(A) ? X(B)) Q(B, A) ? U(A) R(B, B) ? V(B) 目标:S(A) ? X(B) ?(U(A) ? V(B)) 事实的与或图与规则对其进行的变换过程如下 图: 2013-6-6 65 第四章 确定性推理 4.3基于规则的演绎推理——正向演绎 例二的与或图 U(A) V(B) R(B, B) S(A) X(B) Q(B, A) {B/x} P(A, B) {A/x,B/y} P(x, y) Q(x, A) ? R(B, y) Q(x, A) R(B, y) {B/y} P(x, y) ? (Q(x, A) ? R(B, y)) 2013-6-6 66 第四章 确定性推理 4.3基于规则的演绎推理——逆向演绎 基于规则的逆向演绎推理 ? 将目标表达式表示成与或形 ? 将规则限制为下列形式: W?L 其中,L是单文字,W是与或形,变量受全称量词约束 如规则形为: W? L1 ?L2,则变换为: W? L1 和 W? L2 ? 事实表达式均限制为文字合取形,形如: ? F1 ?F2 ? … ? Fn Fi(i=1,2…n)为单文 字.且都可单独起作用 ? 推理过程:从目标公式的与/或树出发,不断 用规则的后件和与/或树的叶节点进行匹配,并 将匹配成功的规则用匹配弧加入与/或树中,直 到产生某个终止在事实节点上的解图为止。 2013-6-6 67 第四章 确定性推理 4.3基于规则的演绎推理——逆向演绎 化目标表达式为与或形 ? ? ? ? ? 消去蕴涵符号: ~ P∨Q取代P→Q 减少否定符号的管辖域 对变量标准化 消去全称量词 :引入Skolem函数 消去存在量词 2013-6-6 68 第四章 确定性推理 4.3基于规则的演绎推理——逆向演绎 目标表达式化为与或形举例 例:(?z) (?x)(?y){[(P(x) ?Q(x)) ?R(y)] ?U(z)} 前三步:1, 消蕴涵符 2, 移动否定符 3, 变量标准化 等3步与正向推理中化事实的表达式方法相同 4, 消全称量词 (skolem化(对偶形) ) 原则:对于一个受全称量词约束的变量,如果他 受存在量词约束,则该变量用一个函数代替。 (?z) (?x)(?y){[(~P(x) ?~Q(x)) ? R(y)] ?U(z)} = (?z) ) (?y){[(~P(f(z)) ?~Q(f(z))) ? R(y)] ?U(z)} 5, 消存在量词 [(~ P(f(z))?~Q(f(z))) ? R(y)] ?U(z) 2013-6-6 69 第四章 确定性推理 4.3基于规则的演绎推理——逆向演绎 目标表达式的与或图表示 ? 用K连线表示合取,无连线表示析取 例: Q(w, A) ? ((~R(v) ?~P(v)) ? ~S(A, v)) Q(w, A) ?((~R(v) ? ~P(v)) ? ~S(A, v)) Q(w, A) (~R(v) ? ~P(v)) ? ~S(A, v) ~S(A, v) ~P(v) ~R(v) ? ~P(v) ~R(v) 读叶节点的与 或关系,得子 句: Q(w, A) ~R(v)?~S(A,v) ~P(v)?~S(A,v) 2013-6-6 70 第四章 确定性推理 4.3基于规则的演绎推理——逆向演绎 C(x) ? D(y) ? ~A(x, y) C(x) {x/x5} 逆向演绎例: 事实: D(F) ~B(F) W(F) M(N) 规则: R1: (W(x1) ? D(x1)) ? F(x1) R2: (F(x2) ? ~B(x2)) ? ~A(y2, x2) R3: D(X3) ? A(x3) R4: C(x4) ? A(x4) R5: M(x5) ? C(x5) 目标: C(x) ? D(y) ? ~A(x, y) 2013-6-6 D(y) {F/y} ~A(x, y) {x/y2,y/x2} C(x5) R5 D(F) F(y) ~A(y2, x2) R2 M(x) {N/x} ~B(y) {F/y} {y/x1} M(N) W(y) F(x1) R1 ~B(F) D(y) {F/y} {F/y} W(F) D(F) 71 第四章 确定性推理 4.3基于规则的演绎推理 正、逆向系统对比 ? ? ? ? ? ? ? ? 事实表达式任意形 规则形式: 单文字 ? W 目标公式为文字析取 对事实、规则消存在量词, Skolem化 消目标的全称量词, Skolem化(对偶形) 事实表达式与或树,“?” 对“与”,“?”对应“或” 从事实出发,正向应用规则 以目标为结束的一致解图 ? ? ? ? ? ? ? ? 事实表达式是合取形 规则形式: L ? 单文字 目标公式任意形 对事实、规则消存在量词, Skolem化 消目标的全称量词, Skolem化(对偶形) 目标公式的与或树,“?” 对“与”,“?”对应“或” 从目标出发,逆向应用规则 以事实为结束的一致解图 2013-6-6 72 第四章 确定性推理 The End 2013-6-6 73

本文链接:http://meghanmbiro.com/feidandiaotuili/332.html