经典逻辑推理.ppt

第四章经典逻辑推理 4 1基本概念4 2自然演绎推理4 3归结演绎推理4 4与 或形演绎推理 4 1基本概念 为使计算机具有智能 仅仅使它拥有知识还不够 更重要地 还必须使它具有思维能力 即能运用知识进行推理 求解问题的能力知识表示 知识库 求解过程 推理 经典推理是根据经典逻辑 命题逻辑和一阶谓词逻辑 的逻辑规则进行的一种推理 又称机械 自动定理证明 主要推理方法有 自然演绎推理 归结演绎推理 与 或形演绎推理 基本概念 推理推理是按某种策略由已知判断推出另一种判断的过程 在AI系统中 推理是由程序来实现的 称为推理机 不同的控制策略推理方式及分类 演绎推理 由一般 全称判断 到个别 特称判断 的推理方法 核心是三段论 通常由一个大前提 一个小前提和一个结论三部分组成的 例 阿凡提的故事 两头驴的故事 我肩上驮的是两头驴的东西 大前提 国王和大臣的衣衫是我肩上驮的 小前提 国王和大臣的衣衫是两头驴的东西 结论 归纳推理 从个别到一般归纳结论不具备逻辑必然性莫里斯 科恩逻辑学著作包括两部分 第一部分是演绎 其功能是解释谬误 第二部分是归纳 其功能是生成谬误 我们获得关于这个实在世界的一般性事实的唯一方法 演绎推理所得出的结论蕴含在一般性知识的前提中 演绎推理只不过是将已有事实揭示出来 因此它不能增殖新知识 在归纳推理中 所推出的结论是没有包含在前提内容中的 这种由个别事物或现象推出一般性知识的过程 是增殖新知识的过程 默认推理 默认推理是在知识不完全的情况下假设某些条件已经具备所进行的推理 也称为缺省推理 在推理过程中 如果发现原先的假设不正确 就撤消原来的假设以及由此假设所推出的所有结论 重新按新情况进行推理 由于默认推理允许在推理过程中假设某些条件是成立的 因此解决了在一个不完备的知识集中进行推理的问题 封闭世界假设 如果没有足够的证据证明某命题不成立 就假定该命题成立 推理的控制策略推理过程涉及到求解方法和求解策略 求解方法包括匹配方法 不确定性的传递方法求解策略包括推理方向 求解策略 限制策略等 指推理是求一个解 所有解 还是最优解 为防止无穷的推理过程 以及由此带来的时间和空间复杂性 限制策略是对推理的深度 宽度 时间 空间等进行限制 推理方向推理方向分为正向推理 逆向推理 混合推理 双向推理四种 无论哪一种推理 系统都具有知识库 数据库和推理机 正向推理需要解决的问题 1 确定匹配的方法2 确定搜索策略3 消解冲突正向推理的缺点 盲目 效率低 逆向推理的优点 1 目标性强2 有利于向用户提供解释逆向推理的缺点 初始目标的选择有盲目性 逆向推理 例 有关知识规则1 IF你丢了自行车钥匙 并且车胎没气THEN自行车不能骑规则2 IF自行车不能骑 并且你只有走路去THEN你听课会迟到事实1 你丢了自行车钥匙事实2 车胎没气问题 你听课会迟到 逆向推理 例 1 首先查找知识库 知该假设不是已有事实 但可由规则2导出 于是将规则2放入可用知识集 并将其两个前提条件 自行车不能骑 和 你只有走路去 都作为新的假设放入假设集 2 从假设集中取出假设 自行车不能骑 它不是已有事实 但可由规则1导出 于是规则1被放入可用知识集 并将其两个前提条件 你丢了自行车钥匙 和 车胎没气 也作为新的假设放入假设集 3 从假设集中取出假设 你只有走路去 此假设既不是已有事实 也不能被任何一条规则导出 询问用户 你只有走路去吗 若用户回答 是 则该假设成立 并被放入已有事实集 4 假设集中还有两个假设 你丢了自行车钥匙 和 车胎没气 它们都是已有事实 均为真 继续推理 假设集为空 推理过程结束 你听课会迟到 得证 混合推理是把正向推理和逆向推理结合起来 吸取两种推理的优点 它通常适用以下3种情况 1 已知事实不充分 2 由正向推理推出的可信度不高 3 希望得到更多的结论混合推理有两种方式 先正后逆和先逆后正 双向推理是指正向推理和逆向推理同时进行 在推理过程的某步碰头 基本思想双向推理的难点是碰头的判定 模式匹配 模式匹配是指对两个知识模式 如两个谓词公式 框架或语义片段等 的比较与藕合 即检查这两个知识模式是否完全一致或近似一致 按匹配的近似程度划分 可分为确定性匹配和不确定性匹配 确定性匹配是指两个知识模式完全一致 或经过变量代换后变得完全一致 例如 不确定性匹配是指两个知识模式不完全一致 但总体上它们的相似度在一定的限度内 定义4 1代换 代换是形如的有限集合 其中是项 是互不相同的变元 表示用代换 不允许与相同 也不允许变元循环的出现在另一个中 根据定义是代换不是代换 g a x f x y 是代换 设是两个代换 则此两个代换的复合也是一个代换 它是从删除以下两种元素后剩下的元素所构成的集合 记作就是对一个公式先运用 代换 然后再运用 代换 定义4 2代换的复合 例如 则 解释 定义4 3公式集的合一设有公式集 若存在一个代换使得则称是公式集的一个合一 且称是可合一的 一个公式集的合一一般来说不是唯一的例如公式集有合一 定义4 4最一般的合一设是公式集的一个合一 如果对任一个合一都存在一个代换 使得则称是一个最一般的合一 求最一般的合一 差异集 求最一般合一算法 1 令 这里 是欲求最一般合一的公式集 是空代换 它表示不做代换 2 若只含一个表达式 则算法停止 就是最一般合一 3 找出的差异集 4 若中存在元素和 其中是变元 是项 且不在中出现 则置 然后转向 2 5 算法终止 的最一般合一不存在 举例 求最一般合一 消解冲突策略 在推理过程中 系统要不断地用当前已知事实与知识库中的知识进行匹配 此时可能发生以下三种情况 1 已知事实不能与知识库中的任何知识匹配 2 已知事实恰好与知识库中的一条知识匹配 3 已知事实可与知识库中的多条知识匹配 或者多个已知事实可与知识库中的某一条知识匹配 或者多个已知事实可与知识库中的多条知识匹配 处于第三种情况时 就发生冲突 此时需要按一定的消解策略解决冲突 冲突 多个知识都匹配成功 冲突消解的基本思想都是对知识进行排序 对于产生式系统 若出现以下情况就认为发生冲突 1 对正向推理而言 如果有多条产生式规则的前件都和已知事实匹配 或者有多组已知事实都与同一条产生式规则的前件匹配 或者以上两种情况同时出现 2 对逆向推理而言 如果有多条产生式规则的后件都和同一假设匹配 或者有多条产生式规则的后件可与多个假设匹配 常用的消解冲突策略 1 按针对性排序设有如下两条产生式规则 如果存在最一般合一 使得r1中的每个Ai都可以变成相应的Bi 则称r2比r1有更大的针对性 r1比r2有更大的通用性 该策略选用针对性较强的产生式规则 2 按已知事实的新鲜性排序把数据库中后生成的事实称为新鲜的事实 该策略要求具有最大新鲜性的事实总是排在前面 设规则r1可与事实组A匹配成功 规则r2可与事实组B匹配成功 则A和B哪一组中的事实新鲜 与它匹配的规则就先被利用 如何衡量A和B哪一组中的事实更新鲜呢 1 3 P123 3 按匹配度排序4 根据领域问题的特点排序5 按上下文限制排序6 按冗余限制排序7 按条件个数排序 尽量减少冲突的发生 使推理具有较高的效率 4 2自然演绎推理 自然演绎推理就是从一组已知为真的事实出发 直接运用经典逻辑的推理规则推出结论的过程 推理规则包括 1 假言推理2 拒取式推理3 P规则 在推理的任何步骤中都可引入前提4 T规则 推理时 如果前面步骤中有一个或多个公式永真蕴含公式S 则可把公式S引入推理过程中 例4 1已知下述事实 A B A C B C D D Q求证 Q为真 证明 A A CCP规则及假言推理B CB C合取B C B C DDT规则及假言推理D D QQT规则及假言推理 作业题 所有人都是必死的 苏格拉底是人 求证 苏格拉底是必死的 自然演绎推理的优点 表达定理证明过程自然 容易理解 而且拥有丰富的推理规则 推理过程灵活 便于在它的推理规则中嵌入领域启发式知识 自然演绎推理的缺点 容易产生组合爆炸 中间结论呈指数级增长 4 3归结演绎推理 要证明P Q为真 只要证明P Q永假 即不可满足性 这是因为 P Q P Q P Q P Q 海伯伦 Herbrand 和鲁宾逊 Robinson 在这个方向上先后作了卓越的研究工作 首先 由海伯伦提出的H域 海伯伦域 和海伯伦定理 为自动定理证明奠定了理论基础 然后 由鲁宾逊提出的归结原理则使机器定理证明成为可能 子句 在谓词公式中 把原子谓词公式及其否定统称为文字 定义4 5任何文字的析取式称为子句 定义4 6不包含任何文字的子句称为空子句 简记为NIL 空子句是永假的 是不可满足的 子句的集合称为子句集 在谓词逻辑中 谓词公式可以通过等价关系及推理规则化成相应的子句集 把谓词公式转化为子句集的步骤 1 消去蕴涵符号 2 内移否定符号 3 对变元更名 使不同量词约束的变元不同名 4 消去存在量词 个体常量 Skolem函数代换 5 全称量词前束化 6 化为Skolem标准型 合取范式 7 消去全称量词 8 对变元更名 使不同子句中的变元不同名 9 消去合取词 子句集 例如 x y P x y y Q x y R x y x y P x y y Q x y R x y 2 x y P x y y Q x y R x y 3 x y P x y z Q x z R x z 4 x P x f x Q x g x R x g x 5 6 x P x f x Q x g x P x f x R x g x 7 P x f x Q x g x P x f x R x g x 8 P x f x Q x g x P y f y R y g y 9 P x f x Q x g x P y f y R y g y 例1 求谓词公式G xyz P x y R x y z Q x z R x y z 的子句集 解 已经是前束范式 并且不含连接词 由于存在量词y z都在全称量词x的辖域中 所以将y z分别用Skolem函数f x g x 代替 x P x f x R x f x g x Q x g x R x f x g x 该谓词公式已经是合取范式了 消去全称量词 对变元更名 消去合取词 得到谓词公式G的子句集是 P x f x R x f x g x Q y g y R y f y g y 例2 求谓词公式的子句集 x yP x y y Q x y R x y 解 x yP x y y Q x y R x y x yP x y y Q x y R x y x y P x y y Q x y R x y x y P x y z Q x z R x z x P x f x Q x g x R x g x x P x f x Q x g x P x f x R x g x 从而该谓词公式的子句集是 P x f x Q x g x P y f y R y g y 定理4 1设有谓词公式F 其标准形的子句集为S 则F不可满足的充要条件是S不可满足 鲁宾逊归结原理为提高判定子句集不可满足的有效性 鲁宾逊于1965年提出了归结 Resolution 原理 也称为消解原理 由谓词转化子句集的过程可以看出 在子句集之间是合取关系 其中只要有一个子句不可满足 则子句集就不可满足 空子句是不可满足的 若一个子句集含有一个空子句 该子句集中有矛盾 子句集一定是不可满足的 鲁宾逊归结原理的基本是 检查子句集S是否包含空子句 若包含 则S不可满足 若不包含 就在子句集中选择合适的子句进行归结 一旦通过归结推出空子句 就说明子句集S是不可满足的 定义4 9若P是原子谓词公式 则称P和 P为互补文字 命题逻辑中归结原理定义4 10设C1和C2是子句集中任意二个子句 如果C1中的文字L1和C2中的文字L2互补 那么从C1和C2中分别消去L1和L2 并对C1和C2的剩余部分析取 构成一个新的子句C12 则称这一过程为归结 称C12为C1和C2的归结式 C1和C2是C12的亲本子句 例 C1 P Q C2 Q R C3 PC12 P R C123 R 定理4 4归结式C12是其亲本子句的C1和C2的逻辑结论 即 C1 C2C12推论1 设C1和C2是子句集S中的两个子句 C12是它们的归结式 若用C12代替C1和C2后得到新子句集S1 则S1的不可满足性S的不可满足性推论2 设C1和C2是子句集S中的两个子句 C12是它们的归结式 若用C12加入S中后 得到新子句集S1 则S1的不可满足性 S的不可满足性 谓词逻辑中的归结原理在谓词逻辑情况下 由于子句中含有变量 不能像命题逻辑那样直接发现和消去互补文字 往往需对潜在的互补文字先作变量置换和合一处理 才能用于归结 例如有如下两个子句 C1 P x Q x C1 P a R y 用最一般合一 a x 对两个子句分别进行代换 C1 P a Q a C1 P a R y 可得归结式 Q a R y 定义4 10设C1和C2是两个没有相同变元的子句 L1和L2分别是C1和C2中的文字 若 是L1和 L2的最一般合一 则称C12 C1 L1 C2 L2 是C1和C2的二元归结式 L1和L2称为归结式上的文字 参见P132例4 10 4 11 如果在参加归结的子句内部含有可合一的文字 则在进行归结前应对这些文字先进行合一 例如 C1 P x P f a Q x C2 P y R b C1中P x 和P f a 可合一 用其最一般合一 f a x 进行代换 得 C1 P f a Q f a C1 和C2归结得C12 Q f a R b 一般来说 若子句C中有两个或两个以上的文字具有最一般的合一 则称C 为子句C的因子 如果C 是一个单文字 则称为单因子 定义4 12子句C1和C2的归结式是下列二元归结式之一 1 C1和C2的二元归结式 2 C1和C2的因子C2 2的二元归结式 3 C1的因子C1 1和C2的二元归结式 4 C1的因子C1 1和C2的因子C2 2的二元归结式 对于谓词逻辑 定理4 4仍然适用 归结演绎的完备性从不可满足的意义上说 基于归结的演绎方法是完备的 即若子句集S不可满足 就必定存在一个从S到空子句的归结演绎 反之 若存在一个从S到空子句的归结演绎 则S必定是不可满足的 关于归结演绎的完备性可用海伯伦定理进行证明 因此从这个意义上讲 归结原理是建立在海伯伦定理之上的 不过归结原理并不能用于解决子句集不可满足性的不可判问题 即对于永真和可满足的子句集 判定过程将无休止地进行下去 得不到任何结果 归结反演证明Q是P1 P2 Pn的逻辑结论 即 P1 P2 Pn Q只需证明 P1 P2 Pn Q 是不可满足的 因为 P1 P2 Pn Q P1 P2 Pn Q P1 P2 Pn Q只需证明子句集 P1 P2 Pn Q 是不可满足的 对子句集中的子句相互归结 直到归结出空子句 这个过程就是归结反演 设F为已知前提的公式集 Q为目标公式 用归结反演证明Q为真的步骤 1 否定Q 得到 Q 2 把 Q并入到公式集F中 得到 F Q 3 把公式集 F Q 化为子句集S P126 127 4 应用归结原理对子句集S中的子句进行归结 并把每次得到的归结式放入S中 如此反复 若出现空子句 就停止归结 此时就证明了Q为真 参见P134 135例4 12 4 14 例1 求证 G是A1和A2的逻辑结果A1 x P x Q x R x A2 x P x S x G x S x R x 证 P x Q x 从A1变换 P y R y 从A1变换 P a 从A2变换 S a 从A2变换 S z R z 结论的否定 R a 归结 a y R a 归结 a z 归结得证 例2 设已知 1 能阅读者是识字的 2 海豚不识字 3 有些海豚是聪明的 求证 有些聪明者并不能阅读 证 定义如下命题 R x x能阅读 L x x识字 I x x是聪明的 D x x是海豚 把已知条件及求证结论翻译成谓词公式为x R x L x 已知x D x L x 已知x D x I x 已知x I x R x 求证结论将已知条件 求证结论的反化成子句集 R x L x D y L y D a I a I z R z L a 2 3归结 a y R a 1 6归结 a x R a 4 5归结 a z 7 8归结得证 应用归结原理求问题的答案 求问题的答案与定理证明类似 其步骤为 1 用谓词公式表示已知前提 并化为子句集S 2 用谓词公式表示待求解 并将其否定与谓词ANSWER构成析取式 同一个子句 ANSWER是一个为求解而设定的谓词 其变元必须与问题公式的变元一致 用重言式也可 3 把此析取式化为子句集 并把该子句集假如到子句集S中 得到子句集S 4 对S 应用归结原理进行归结 5 若得到归结式ANSWER 则答案就在ANSWER中 参见P136 137例4 15 4 16 归结策略 1 计算机进行归结的一般过程设子句集S C1 C2 C3 C4 计算机对此子句集进行归结的一般过程是 1 从子句C1开始 逐个与C2 C3 C4进行比较 若能归结 就求出归结式 然后用C2与C3 C4进行归结 最后C3和C4进行归结 经过这一轮的比较和归结后 就得到一组归结式 称为第一级归结式 2 再从C1开始 用S中的子句分别与第一级归结式中的子句逐个地比较 归结 这样又会得到一组归结式 称为第二级归结式 3 仍然从C1开始 用S中的子句及第一级归结式中的子句分别与第二级归结式中的子句逐个地比较 归结 得到第三级归结式 如此继续 直到出现空子句或者不能再继续归结为止 例4 17设有子句集 S P R P Q Q R 归结过程 S 1 P 2 R 3 P Q 4 Q RS1 5 Q 6 Q 7 P R S2 8 R 9 P 10 P 11 RS3 12 NIL 2 删除策略 删除策略是指在归结过程中把子句集的无用的子句删除掉这样就会缩小寻找范围 减少比较次数 删除策略具有以下几种删除方法 1 纯文字删除法 如果某文字L在子句集中不存在可与之互补的文字 L 则称该文字是纯文字 例如 S P Q R Q R Q R 中 是纯文字 2 重言式删除法 如果一个子句中同时包含互补文字对 则称该子句为重言式 重言式是永真式 例如 P x P x P x x P x 包孕删除法 设子句C1和C2 如果存在一个代换 使得C1 C2 则称C1包含于C2 例如 P x 包含于P y Q z y x 支持集策略 每一次归结时 亲本子句中至少有一个是由目标公式的否定所得到的子句 或者是他们的后裔 可以证明 支持集策略是完备的 例4 18设有子句集 S I x R x I a R y L y L a 其中 I x R x 是目标公式否定后得到的子句 4 线性输入策略 参加归结的两个子句中必须至少有一个是初始子句集的子句 线性输入策略是不完备的 例如S P x Q x P x Q x P u Q u P t Q t 是不可满足的 但用线性输入策略却归结不出空子句 5 单文字子句策略如果一个子句只包含一个文字 就称它为单文字子句 该策略要求参加归结的子句至少有一个是单文字子句 该策略也是不完备的 6 祖先过滤形策略 当两个子句C1和C2进行归结时 只要它们满足下述两个条件中的任一个就可以归结 1 C1和C2中至少有一个是初始子句集的子句 2 如果两个子句都不是初始子句集的子句 则一个应是另一个的祖先 祖先过滤形策略是完备的 归结演绎推理具有证明简单 在计算机上容易实现等优点 但同时具有以下缺点 1 必须把逻辑公式化成子句集 2 不自然 不便于阅读与理解 如 P x Q x 没有P x Q x 直观 3 有可能丢失一些重要的控制信息 针对以上缺点 与 或形演绎推理可以克服 通常很多应用知识是用蕴含式直接表达的 因此都带有超逻辑的或启发式的控制信息 在归结反演证明系统中 要把这些表达式化成子句形表示 这就可能丢掉隐含在蕴含式中 对推理有用的控制信息 例如下面的几个蕴含式 A B C A C B B C A A B C B A C C A B其中任意一个式子在逻辑上都与子句 A B C 等价 而每种形式表达的蕴含式都有其内在含有的各不相同的超逻辑的控制信息 子句形表示只给出了谓词间的逻辑关系 因此有时候会希望系统能按近于原始给定的描述形式来使用这些公式 不把它们都化成子句集 这就是基于规则的演绎系统 强调直接使用规则进行演绎 本书称为与 或形演绎推理 的基本思想 与 或形演绎推理 1 与 或形正向演绎推理它是从已知事实出发 正向使用蕴涵式 F规则 进行演绎推理 直到得到某个目标公式的一个终止条件 在这种推理中 对已知事实 F规则及目标公式的表示形式都有一定的要求 如果不是所要求的形式 就需要进行变换 事实为支持演绎推理 事实表达式不必化简为子句集 只需规范地表示为不含蕴涵符号的文字与或形 具体步骤如下 1 利用P Q P Q消去公式中的 2 把 移到紧靠谓词的位置上 3 重新命名变元名 使不同量词约束的变元有不同的名字 4 引入Skolem函数消去存在量词 5 消去全称量词 使主合取式中的变元不同名 例如 x y Q y x R y P y S x y x y Q y x R y P y S x y y Q y a R y P y S a y Q z a R y P y S a y 子句集 解图 Q z a R y S a y P y S a y F规则在与 或形正向演绎推理中 通常要求F规则具有如下形式 L W其中 L为单文字 W为与 或形 为了得到这种可应用的形式 对原始蕴含式必须作必要的化简 设原始公式为 x y z P x y z u Q x u 则化简步骤如下 1 x y z P x y z u Q x u 2 x y z P x y z u Q x u 3 x y P x y f x y u Q x u 4 P x y f x y Q x u 5 P x y f x y Q x u 对规则作单文字前项的限制将大大简化了应用时的匹配过程 对非单文字前项的情况 若形式为 L1 L2 W 则可化成与其等价的两个规则L1 W与L2 W进行处理 目标公式的表示形式目标公式用子句 析取式 表示 推理过程 1 首先用与 或树表示已知事实 2 用F规则的左部与与 或树的叶节点匹配 并把匹配成功的F规则加入到与 或树中 3 重复 2 直到产生一个含有以目标节点作为终止节点的一致解图为止 例4 22设已知事实为 A BF规则为 r1 A C Dr2 B E G欲证明的目标公式为 C G解图 归结式 归结演绎推理该如何做 例设已知事实为 P Q R S T U 规则为S X Y Z解图 归结式 例事实与或形表示为P A y Q x A R B y 规则为P z B S z X B 施以规则后的与或图如右图所示 解图 归结式 一个解图是否是一致的 需要看该解图所涉及的若干个置换组成的置换集是否存在矛盾 当置换集没有矛盾存在时 称该置换集是一致的 也就是没有矛盾的 否则就是不一致的 只有当解图所涉及的置换集是一致的时 解图才是一致的 有些时候演绎过程会多次调用同一条规则 这时要注意每次应用都要使用改名的变量 以免匹配过程产生一些不必要的约束 2 与 或形逆向演绎推理 与 或形逆向演绎推理从目标公式出发 逆向应用蕴含式 B规则 对相应于目标公式的原始与 或树进行变换 直至得到一个所有叶节点都是事实节点