第三章 推理技术.ppt

第三章推理技术 4 1消解原理 4 1消解原理 3 1消解原理 3 2规则演绎系统 3 3不确定性推理 3 4非单调推理 3 1消解原理消解原理的基础知识 1 谓词公式 某些推理规则以及置换合一等概念 2 文字 一个原子公式和原子公式的否定都叫做文字 3 子句 由文字的析取组成的公式 4 子句集 子句通过合取符号联接起来形成子句集 任一谓词演算公式可以化成一个子句集 3 1 1子句集的求取 1 步骤 1 消去蕴涵符号以 A B替换A B 例 A B B C 在消去蕴涵符号后得到公式 A A B B CB A B B C 5 消解 如果存在某个公理E1 E2和另一公理 E2 E3 那么E1 E3在逻辑上成立 这就是消解 而称E1 E3为E1 E2和 E2 E3的消解式 resolvent 2 减少否定符号的辖域每个否定符号 最多只用到一个谓词符号上 并反复应用狄 摩根定律 3 对变量标准化在任一量词辖域内 受该量词约束的变量为一哑元 虚构变量 它可以在该辖域内处处统一地被另一个没有出现过的任意变量所代替 而不改变公式的真值 合适公式中变量的标准化意味着对哑元改名以保证每个量词有其自己唯一的哑元 4 消去存在量词 Skolem函数 在公式 y Skolem函数 在公式 y x P x y 中 存在量词是在全称量词的辖域内 我们允许所存在的x可能依赖于y值 令这种依赖关系明显地由函数g y 所定义 它把每个y值映射到存在的那个x 这种函数叫做Skolem函数 如果用Skolem函数代替存在的x 我们就可以消去全部存在量词 并写成 y P g y y 如果要消去的存在量词不在任何一个全称量词的辖域内 那么我们就用不含变量的Skolem函数即常量 例如 x P x 化为P A 5 化为前束形把所有全称量词移到公式的左边 并使每个量词的辖域包括这个量词后面公式的整个部分 所得公式称为前束形 前束形公式由前缀和母式组成 前缀由全称量词串组成 母式由没有量词的公式组成 即前束形 前缀 母式 全称量词串无量词公式 6 把母式化为合取范式任何母式都可写成由一些谓词公式和 或 谓词公式的否定的析取的有限集组成的合取 这种母式叫做合取范式 例如 A B C 化为 A B A C 7 消去全称量词可以消去明显出现的全称量词 8 消去连词符号 用用 A B A C 代替 A B A C 以消去明显的符号 反复代替的结果 最后得到一个有限集 其中每个公式是文字的析取 任一个只由文字的析取构成的合适公式叫做一个子句 9 更换变量名称可以更换变量符号的名称 使一个变量符号不出现在一个以上的子句中 例如 对于子集 P x P y P f x y P x Q x g x P x P g x 在更改变量名后 可以得到子句集 将下列谓词演算公式化为一个子句集 x P x y P y P f x y y Q x y P y 3 1 2消解推理规则1 消解式已知两子句L1 和 L2 如果L1和L2具有最一般合一者 那么通过消解可以从这两个父辈子句推导出一个新子句 这个新子句叫做消解式 它是由取这两个子句的析取 然后消去互补对而得到的 2 消解式求法 1 假言推理父辈子句P P Q 即P Q 消解式Q 2 合并 3 重言式 4 空子句 矛盾 5 链式 三段论 3 1 3含有变量的消解式为了对含有变量的子句使用消解规则 我们必须找到一个置换 作用于父辈子句使其含有互补文字 例1 例2 表3 1消解推理常用规则 3 1 4消解反演求解过程1基本思想把要解决的问题作为一个要证明的命题 其目标公式被否定并化成子句形 然后添加到命题公式集中去 把消解反演系统应用于联合集 并推导出一个空子句 NIL 产生一个矛盾 这说明目标公式的否定式不成立 即有目标公式成立 定理得证 问题得到解决 这与数学中反证法的思想十分相似 2消解反演 1 反演求解的步骤给出一个公式集S和目标公式L 通过反证或反演来求证目标公式L 其证明步骤如下 1 否定L 得 L 2 把 L添加到S中去 3 把新产生的集合 L S 化成子句集 4 应用消解原理 力图推导出一个表示矛盾的空子句NIL 2 反演求解的正确性设公式L在逻辑上遵循公式集S 那么按照定义满足S的每个解释也满足L 决不会有满足S的解释能够满足 L的 所以不存在能够满足并集S L 的解释 因此 如果L在逻辑上遵循S 那么由并集S L 消解得到的子句 最后将产生空子句 反之 可以证明 如果从S L 的子句消解得到空子句 那么L在逻辑上遵循S 3 反演求解举例例1某公司招聘工作人员 有A B C三人面试 公司表达想法 1 三人中至少取一人 2 如果录取A而不录取B 则一定录取C 3 如果录取B 则一定录取C 求证 公司一定录取C 例2 有些患者喜欢任一医生 没有任一患者喜欢任一庸医 所以没有庸医的医生 消解反演可以表示为一棵反演树 其根节点为NIL 3问题求解 把已知前提用谓词公式表示出来 并且化为子句集 把待求解的问题也用谓词公式表示出来 并且与谓词ANSWER一起构成析取式 变元要一致 也化为子句集 并将其并入 构成新子句集 对新子句集消解反演 若得到归结式ANSWER 则答案就在ANSWER中 下面举例说明问题求解过程 例 已知 王先生是小李的老师 小李与小张是同班同学 如果 与 是同班同学 则 的老师也是的 老师 求 小张的老师是谁 例 说 和 说假话 说 和 中至少有一人说假话 说 和 说假话 求谁说真话 3 2规则演绎系统 本节将研究采用易于叙述的if then 如果 那么 规则来求解问题 基于规则的问题求解系统运用下述规则 其中 If部分可能由几个if组成 而Then部分可能由一个或一个以上的then组成 这种基于规则的系统叫做规则演绎系统 rulebaseddeductionsystem 在这种系统中 通常称每个if部分为前项 称每个then部分为后项 有时 then部分用于规定动作 这时 称这种基于规则的系统为反应式系统 reactionsystem 或产生式系统 productionsystem 3 2 1规则正向演绎系统基于规则的演绎系统和产生式系统 均有两种推理方式 正向推理和逆向推理 正向推理 从if部分向then部分推理的过程 它是从事实或状况向目标或动作进行操作的 逆向推理 从then部分向if部分推理的过程 它是从目标或动作向事实或状况进行操作的 1 事实表达式的与或形变换在基于规则的正向演绎系统中 把事实表示为谓词演算公式 并把这些公式变换为叫做与或形的非蕴涵形式 与或形表达式是由符号 和 连接的一些文字的子表达式组成的 要把一个公式化为与或形 可采用下列步骤 1 利用 W1 W2 和 W1 W2 的等价关系 消去符号 如果存在该符号的话 实际上 在事实中间很少有符号 出现 因为可把蕴涵式表示为规则 2 用狄 摩根 DeMorgan 定律把否定符号移进括号内 直到每个否定符号的辖域最多只含有一个谓词为止 3 对所得到的表达式进行Skolem化和前束化 4 对全称量词辖域内的变量进行改名和变量标准化 而存在量词量化变量用Skolem函数代替 5 删去全称量词 而任何余下的变量都被认为具有全称量化作用 例如 有事实表达式 u v Q v u R v P v S u v 把它化为 Q v A R v P v S A v Q w A R v P v S A v 对变量更名标准化 使得同一变量不出现在事实表达式的不同主要合取式中 更名后得与或形表达式 2 事实表达式的与或图表示与或形的事实表达式可用与或图来表示 如图的与或树表示出上述例子的与或形事实表达 3与或图的F规则变换F规则 L W式中 L是单文字 W为与或形的唯一公式 把形式为L W的规则应用到任一个具有叶节点n并由文字L标记的与或图上 可以得到一个新的与或图 在新的图上 节点n由一个单线连接符接到后继节点 也由L标记 它是表示为W的一个与或图结构的根节点 例如 把规则S X Y Z应用到下图所示的与或图中标有S的叶节点上 图中标记S的两个节点由一条叫做匹配弧的弧线连接起来 我们希望在应用规则之后得到的图 既能表示原始事实 又能表示从原始事实和该规则推出的事实表达式 事实表达式 Q w A R v P v S A v 与规则S X Y Z的消解式 X Z P Q Y Z P Q R X Z R Y Z全部包含在解图所表示的子句之中 4 作为终止条件的目标公式应用F规则的目的在于从某个事实公式和某个规则集出发来证明某个目标公式 目标文字和规则可用来对与或图添加后继节点 当一个目标文字与该图中文字节点n上的一个文字相匹配时 我们就对该图添加这个节点n的新后裔 并标记为匹配的目标文字 这个后裔叫做目标节点 举例 用消解反演来证明目标公式 结论 当正向演绎系统产生一个含有以目标节点作为终止的解图时 此系统就成功地终止 3 2 2规则逆向演绎系统基于规则的逆向演绎系统 其操作过程与正向演绎系统相反 即为从目标到事实的操作过程 从then到if的推理过程 1 目标表达式的与或形式逆向演绎系统能够处理任意形式的目标表达式 首先 采用与变换事实表达式同样的过程 把目标公式化成与或形 即消去蕴涵符号 把否定符号移进括号内 对全称量词Skolem化并删去存在量词 举例如下 目标表达式被化成与或形 P f y Q f y y P f y S y 式中 f y 为一Skolem函数 对目标的主要析取式中的变量分离标准化可得 P f z Q f y y P f y S y 应注意不能对析取的子表达式内的变量y改名而使每个析取式具有不同的变量 与或形的目标公式也可以表示为与或图 不过 与事实表达式的与或图不同的是 对于目标表达式 与或图中的k线连接符用来分开合取关系的子表达式 上例所用的目标公式的与或图如下所示 这个目标公式的子句形表示中的子句集可从终止在叶节点上的解图集读出 P f z Q f y y R f y Q f y y S y 可见目标子句是文字的合取 而这些子句的析取是目标公式的子句形 2 与或图的B规则变换B规则 即逆向推理规则 B规则是建立在确定的蕴涵式基础上的 我们把B规则限制为 W L其中 W为任一与或形公式 L为文字 把B规则限制为这种形式的蕴涵式还可以简化匹配 可以把像W L1 L2 这样的蕴涵式化为两个规则W L1和W L2 3 作为终止条件的事实节点的一致解图逆向系统中的事实表达式均限制为文字合取形 它可以表示为一个文字集 当一个事实文字和标在该图文字节点上的文字相匹配时 就可把相应的后裔事实节点添加到该与或图中去 这个事实节点通过标有mgu的匹配弧与匹配的子目标文字节点连接起来 逆向系统成功的终止条件是与或图包含有某个终止在事实节点上的一致解图 下面以一个简单的例子 分析基于规则的逆向演绎系统的工作过程 这个例子的事实 应用规则和问题分别表示于下 事实 F1 DOG FIDO 狗的名字叫FidoF2 BARKS FIDO Fido是不叫的F3 WAGSTAIL FIDO Fido摇尾巴F4 MEOWS MYRTLE 猫咪的名字叫Myrtle规则 R1 WAGSTAIL x1 DOG x1 FRIENDLY x1 摇尾巴的狗是温顺的狗R2 FRIENDLY x2 BARKS x2 AFRAID y2 x2 温顺而又不叫的东西是不值得害怕的R3 DOG x3 ANIMAL x3 狗为动物R4 CAT x4 ANIMAL x4 猫为动物R5 MEOWS x5 CAT x5 猫咪是猫问题 是否存在这样的一只猫和一条狗 使得这只猫不怕这条狗 用目标表达式表示此问题为 x y CAT x DOG y AFRAID x y 下图表示出这个问题的一致解图 图中 用双线框表示事实节点 用规则编号R1 R2和R5等来标记所应用的规则 此解图中有八条匹配弧 每条匹配弧上都有一个置换 终止在事实节点前的置换为 MYRTLE x 和 FIDO y 把它应用到目标表达式 我们就得到该问题的回答语句如下 CAT MYRTLE DOG FIDO AFRAID MYRTLE FIDO 3 3不确定性推理 推理 从已知事实出发 通过运用相关的知识逐步推出某个结论的过程 不确定性推理 就是从不确定性初始证据出发 通过运用不确定性的知识 最终推出具有一定程度的不确定性但却有合理或者近乎合理的结论的思维过程 不确定性是智能问题的本质特征 智能离不开对不确定性知识的处理 智能主要反映在求解不确定性问题的能力上 3 3 1概率推理基于概率论的不确定性推理有很多种 在这里仅讨论比较成熟的一种推理方法 主观Bayes方法 1 Bayes公式及主观Bayes方法主观Bayes方法是最早用于处理不确定性推理的方法之一 已在地矿勘探专家系统PROSPECTOR中得到了成功的应用 Bayes公式 若有诸事件A1 A2 An 彼此独立 B为任何事件 且P Ai 0 i 1 2 n P B 0 那么Bayes公式可表示为 为先验概率 为后验概率 Bayes公式就是从先验概率推导出后验概率的公式 为阐明主观Bayes方法 先引入几个概念 1 几率函数几率函数定义为 它表示x的出现概率与不出现概率之比 显然随P x 的加大o x 也加大 而且当P x 0时 有o x 0当P x 1时 有o x 于是 取值于 0 1 的P x 被放大为取值于 0 的o x 2 充分性度量充分性度量定义为 它表示E对H的支持程度 取值于 0 由专家给出 3 必要性度量 必要性度量定义为 它表示 E对 的支持程度 即E对H为真的必要性程度 取值范围为 0 也是由专家凭经验给出 2 证据的不确定性描述在主观Bayes方法中 证据的不确定性也是用概率表示的 在PROSPECTOR中 由于根据观察S直接求出P E S 非常困难 所以它采用了一种变通的方法 即引进了可信度C E S 的概念 用户可根据实际情况在 5 5 中选取一个整数作为初始证据的可信度 可信度C E S 与