4.5-小结与习题.pdf

第第4章章 确定性推理确定性推理 4 1 推理的基本概念推理的基本概念 4 2 推理的逻辑基础推理的逻辑基础 4 3 自然演绎推理自然演绎推理 4 4 归结演绎推理归结演绎推理 4 5 小结与习题小结与习题 4 5 1 小结小结 知识结构知识结构 确确 定定 性性 推推 理理 推理的基本概念推理的基本概念 推理的基本概念推理的基本概念 推理的方式及其分类推理的方式及其分类 推理的控制策略推理的控制策略 自然演绎推理自然演绎推理 推理规则推理规则 自然演绎推理的基本概念自然演绎推理的基本概念 归结演绎推理归结演绎推理 子句型子句型 归结原理归结原理 归结反演与答案的提取归结反演与答案的提取 推理的逻辑基础推理的逻辑基础 谓词与个体谓词与个体 谓词的永真与可满足性谓词的永真与可满足性 置换与合一置换与合一 推理的基本问题 1 什么是推理 2 推理如何分类 3 推理的控制策略 4 5 1 小结小结 知识点知识点 什么是推理什么是推理 推理 推理 从一个或几个已知的判断 前提 逻从一个或几个已知的判断 前提 逻 辑地推论出一个新的判断 结论 思维形式辑地推论出一个新的判断 结论 思维形式 称为推理 这是事物的客观联系在意识中的称为推理 这是事物的客观联系在意识中的 反映 反映 已知判断 包括已掌握的与求解问题有关的知识 及关于问题的已知事实 推理的结论 由已知判断推出新判断 实现 实现 推理由程序实现 称为推理由程序实现 称为推理机 推理机 推理方式及其分类 1 演绎推理 归纳推理 默认推理 演绎推理 归纳推理 默认推理 按判断推出的途径来划分 可分为演绎 推理 归结推理及默认推理 2 2 单调推理 非单调推理 单调推理 非单调推理 按推理过程中推出的结论是否单调地增 加 或推出的结论是否越来越接近目标 可 分为单调推理和非单调推理 推理方式及其分类 3 3 确定性推理 不确定性推理 确定性推理 不确定性推理 在客观世界中存在大量不确定性问题 不确定 性来自人类的主观认识与客观实际之间存在差异 事物发生的随机性 人类知识的不完全 不可靠 不精确和不一致 自然语言中存在的模糊性和歧 义性都反映了这种差异 都会带来不确定性 按推理时所用知识的确定性来划分 推理可 分为确定性推理 不确定性推理 推理的控制策略 推理的控制策略推理的控制策略 主要包括推理方向 搜索策略 冲 突消解策略 求解策略及限制策略等 自然演绎推理问题 1 什么是自然演绎推理 2 自然演绎推理有哪些推理规则 3 避免产生两类错误 小结小结 知识点知识点 自然演绎推理自然演绎推理 基本概念 推理规则基本概念 推理规则 定义 定义 自然演绎推理是指从一组已知的事实出发 自然演绎推理是指从一组已知的事实出发 直接运用命题逻辑或谓词逻辑中的推理规则推出直接运用命题逻辑或谓词逻辑中的推理规则推出 结论的过程 结论的过程 推理规则 推理规则 P规则 规则 在推理的任何步骤上都可引入前提 继 续进行推理 T规则 规则 推理时 如果前面步骤中有一个或多个 公式永真蕴涵公式S 则可把S引入推理过程中 自然演绎推理自然演绎推理 基本概念 推理规则基本概念 推理规则 假言推理 假言推理 假言推理的一般形式是 假言推理的一般形式是 P P Q Q 它表示 由它表示 由P Q及及P为真 可推出为真 可推出Q为真 为真 拒取式推理 拒取式推理 拒取式推理的一般形是 拒取式推理的一般形是 P Q Q P 它表示 由它表示 由P Q为真及为真及Q为假 可推出为假 可推出P为假 为假 自然演绎推理 两类错误 肯定后件肯定后件 Q Q 的错误 当的错误 当P QP Q为真时为真时 希望通过希望通过 肯定后件肯定后件Q Q推出前件推出前件P P为真为真 这是不允许的这是不允许的 否定前件否定前件 P P 的错误 当的错误 当P QP Q为真时为真时 希望通过希望通过 否定前件否定前件P P推出后件推出后件Q Q为假为假 这也是不允许的这也是不允许的 避免产生两类错误 避免产生两类错误 归结演绎推理问题 1 子句型 2 命题逻辑归结原理 3 谓词逻辑归结原理 4 如何归结反演 5 如何问题求解 小结小结 知识点知识点 SkolemSkolem标准化过程标准化过程 1 11 n nnQxQx Mxx Step1 化成前束范式化成前束范式 Step2 使用下述方法可以消去前缀中存在的所有量词 使用下述方法可以消去前缀中存在的所有量词 令令 是是 中出现的存在量词中出现的存在量词 rQ1 1 n nQxQx 1 r n Case1 若在若在 之前不出现全称量词 则选择一个与之前不出现全称量词 则选择一个与M 中出现的所有常量都不相同的新常量中出现的所有常量都不相同的新常量c 用 用c代替代替M中出中出 现的所有现的所有xr 并且由前缀中删去 并且由前缀中删去 Qrxr rQ Case2 若在若在 之前出现全称量词之前出现全称量词 则选择一 则选择一 个与个与M中出现的任一函数符号都不相同的新中出现的任一函数符号都不相同的新m元函数符元函数符 号号f 用 用 代替代替M中的所有中的所有xr 并且由前缀中删 并且由前缀中删 去去 Qrxr rQ1 ssmQQ 1 ssmf xx 按上述方法删去前缀中的所有存在量词之后得出的公式称为合式按上述方法删去前缀中的所有存在量词之后得出的公式称为合式 公式的公式的Skolem标准型标准型 替代存在量化变量的常量 替代存在量化变量的常量c 视为视为0元函数元函数 和函数和函数f称为称为Skolem函数 函数 子句型子句型 定义定义4 4 1 1 文字文字 literal literal 是原子或原子之非是原子或原子之非 定义定义4 1 子句 子句 任何文字的析取式称为任何文字的析取式称为子句 子句 例如例如 P QP Q P x F x y Q y R f x P x F x y Q y R f x 都是子句 都是子句 定义定义4 3 空子句 空子句 不包含任何文字的子句称为不包含任何文字的子句称为空子句空子句 空子句中不包含任何文字 不能被任何解释满足 空子句中不包含任何文字 不能被任何解释满足 所以空子句是永假的 不可满足的 所以空子句是永假的 不可满足的 定理 定理 在谓词逻辑中 任何一个谓词公式都可以化成在谓词逻辑中 任何一个谓词公式都可以化成 一个子句集 一个子句集 谓词逻辑的二元归结式谓词逻辑的二元归结式 定义定义4 4 MGU 若由子句若由子句C中的两个或多个中的两个或多个 文字构成的集合存在文字构成的集合存在最一般合一置换最一般合一置换 则则 称称 为为C的因子的因子 factor 若若 是单位子句是单位子句 则称它为则称它为C的单位因子的单位因子 Unit factor C C 定义定义4 5 令令 和和 为两个无公共变量的子句为两个无公共变量的子句 令令 和和 分别为分别为 和和 中的两个文字中的两个文字 若集合若集合 存在最一般合一置换存在最一般合一置换 则子句则子句 称为称为 和和 的的二元归结式二元归结式 Binary resolvent 文文 字字 和和 称为被归结的文字 称为被归结的文字 1C 2C 1L 2L1C 2C 1L2 L 1122 CLCL 1C2C 1L 2L 谓词逻辑的二元归结式谓词逻辑的二元归结式 设要被证明的定理可用谓词公式表示为如下的形设要被证明的定理可用谓词公式表示为如下的形 式式 1 首先否定结论首先否定结论B 并将否定后的公式并将否定后的公式 B与前提与前提 公式集组成如下形式的谓词公式公式集组成如下形式的谓词公式 2 求谓词公式求谓词公式G的子句集的子句集S 3 应用归结原理应用归结原理 证明子句集证明子句集S的不可满足性的不可满足性 从而证明谓词公式从而证明谓词公式G的不可满足性的不可满足性 这就说明对结这就说明对结 论论B的否定是错误的的否定是错误的 推断出定理的成立推断出定理的成立 12nA AAB 12 nG A AAB 归结反演归结反演 用归结反演求取问题的答案用归结反演求取问题的答案 归结原理出了可用于定理证明外 还可用来求取归结原理出了可用于定理证明外 还可用来求取 问题答案 其思想与定理证明相似 其一般步骤问题答案 其思想与定理证明相似 其一般步骤 为 为 1 把问题的已知条件用谓词公式表示出来 并化为相应把问题的已知条件用谓词公式表示出来 并化为相应 的子句集 的子句集 2 把问题的目标的否定用谓词公式表示出来 并化为子把问题的目标的否定用谓词公式表示出来 并化为子 句集 句集 用归结反演求取问题的答案用归结反演求取问题的答案 3 对目标否定子句集中的每个子句 构造该子句对目标否定子句集中的每个子句 构造该子句的重言式的重言式 即把该目标否定子句和此目标否定子句的否定之间再进行 即把该目标否定子句和此目标否定子句的否定之间再进行 析取所得到的子句 析取所得到的子句 用这些重言式代替相应的目标否定子用这些重言式代替相应的目标否定子 句式 并把这些重言式加入到前提子句集中 得到一个新的句式 并把这些重言式加入到前提子句集中 得到一个新的 子句集 子句集 4 对这个新的子句集 应用归结原理求出其证明树 这对这个新的子句集 应用归结原理求出其证明树 这 时证明树的根子句不为空 称这个证明树为时证明树的根子句不为空 称这个证明树为修改的证明树修改的证明树 5 用修改的证明树的根子句作为回答语句 则答案就在用修改的证明树的根子句作为回答语句 则答案就在 此根子句中 此根子句中 4 5 2 4 5 2 例题分析例题分析 例题分析 例题分析 已知 张和李是同班同学 如果已知 张和李是同班同学 如果x x和和y y是同是同 班同学 则班同学 则x x的教室也是的教室也是y y的教室 现在张在的教室 现在张在 J1 J1 3 3上课 问李在哪里上课 上课 问李在哪里上课 4 5 2 4 5 2 例题分析例题分析 uyAtuxAtyxCuyx 解解 首先定义谓词 C x y x 和y是同学 At x u x在u教室上课 则已知前提可表示为 C Zhang Li At Zhang J1 3 目标公式的否定为 vAt Li v 目标采用重言式方式 得到子句集合S为 4 5 2 4 5 2 例题分析例题分析 uyAtuxAtyxCLiZh