人工智能基础（第2版）-高济-AI-7-本.pptVIP

人工智能基础 浙江大学计算机学院 高 济 2.4 基于规则的演绎推理 动机： 基于归结的演绎推理 简单易行——只要将问题求解的依据（事实或公式）和目标以合适公式加以形式化描述，就可交由归结反演系统和问答系统执行。 丢失隐含于合适公式的启发式知识 合适公式标准化为高度统一的子句集: P∧Q ? R ?P∨?Q∨R, 效率低下，难以适应于复杂的应用域。 不利于人们从自然思维的角度组织问题的求解和提供问题求解所需的知识——归结演绎并非人类的自然思维方式。 基于规则的演绎推理 保留蕴涵式，将其作为推理规则，用于直接推导目标公式， 符合人的自然思维方式， 通过规则（作为启发式知识）更有效地引导演绎推理过程， 比归结反演更为有效的推理技术，广泛地应用于许多问题求解任务中。 2.4 基于规则的演绎推理 总体描述 规则演绎将求解问题所需的知识分为二类： 规则——表示为蕴涵式，作为启发式知识（表示应用域中存在的规律和法则），引导演绎推理过程。 事实——表示为非蕴涵形式的合适公式，作为应用规则进行推理时参考的有关问题状态和环境的知识。 规则演绎的任务——从给定的事实（即问题的状态和环境知识）和规则，证明某个目标公式成立。 规则演绎的分类： 正向演绎——从事实出发，应用规则不断推导出中间结果作为新的事实，直至推导出目标公式。 逆向演绎——从目标公式出发，逆向应用规则不断推导出子目标，直至所有子目标就是给定的事实为止。换言之，目标公式通过逆向推理找到了支持其成立的所有依据。 主要内容： · 基于规则的正向演绎推理 · 基于规则的逆向演绎推理 · 演绎推理的应用讨论 · 逻辑语言Prolog（略） 1基于规则的正向演绎推理 1）问题求解的规范表示——分为三个部分：事实、规则集和目标 事实——表示为不含蕴涵符号的文字与或形。 例子： 作换名处理； 文字与或形更接近原始表达式 1）问题求解的规范表示 事实表达式的文字与或形可以用与或图表示： 若母式为析取式： E1∨E2∨…∨Ek 以一个K-连接指向各析取项Ei； 若母式为合取式： E1∧E2∧… ∧Ek 以k个1-连接指向各合取项Ei。 与或图例; 参见图2.29 析取（连词∨）符号与K-连接 同向，根节点在图下方。 根节点——整个事实表达式， 叶节点——对应于文字与或形 中的每一个文字。 仅借用与或图表示事实表达式，但 语义上与表示搜索过程的与或图有 本质的区别。 1）问题求解的规范表示 规则——以正向方式使用规则(称为F规则)，化简为：L ? W L为单文字——便于通过L和与或图叶节点的匹配来激活规则， W是文字与或形， 例子： L1∨L2 ? W L1 ? W, L2 ? W， L1∧L2 ? W L1 ? ?L2∨W或L2 ? ?L1∨W。 1）问题求解的规范表示 目标——化简后限定表示为文字的析取式，即子句 量词消去方法取事实表达式的对偶形式， 即将全称量词的约束变量以Sk?lem函数或常量取代； 子句隐含地受存在量词约束。 例子： 用对偶方式消去量词的直观说明——归结反演将目标公式取反， 子句中变量须作换名处理，使各文字不含同名变量。 2）正向演绎推理的实现 借助于与或图表示方式，正向演绎推理从事实表达式出发，不断用激活（左部单文字和与或图叶节点匹配）的F规则对与或图进行变换（从而扩展了与或图），直至得到一个将目标表达式（子句）包含的文字作为叶节点的一致解图。 命题逻辑的情况 基本方法——选用激活的规则对与或图进行变换。 所有公式都不含变量——易于寻找左部单文字和 与或图中叶节点匹配的规则。 例子 与或图的变换——将激活的规则加入与或图： 规则左部单文字作为节点插入与或图， 通过匹配弧和与或图相应叶节点连接； 规则右部以与或图子图的方式插入。 目标文字（目标公式中的某个文字）加入与或图： 和与或图叶节点匹配， 作为目标节点（以方框指示）插入与或图， 通过匹配弧和与或图相应叶节点连接。 演绎推理的成功结束条件——获得终止于目标节点的一个解图， 注意：要求解图的所有叶节点都是目标节点。 2）正向演绎推理的实现 谓词逻辑的情况 复杂性(因含有变量)： 规则或目标文字的激活判断——须对单文字和与或图中的相应叶节点作合一处理； 演绎推理过程可能会对同一变量进行不一致的置换，从而导致不一致解图的生成。 猎狗问题例： 参见图2.31。 解图置换——收集解图中所有变量的置换（为置换元素） 对解图置换作合一复合处理：参见书上， 例子： 参见表2.3。 回到猎狗问题例： 其解图置换的合一复合就是其自身， 得到一致解图，演绎推理成功结束， 只要将目标公式中的变