-高求解技术.docVIP

2006-2007年度第1学期信息与计算科学专业2003级5班《人工智能》教案----详案 第四章 高级求解技术 4-1 规则演绎系统 4-1-1 基本概念 工作内存：断言集合。 规则：由IF…THEN…构成。其中，IF中的断言（Assertion）部分称为前项（Antecedent），THEN部分称为后项（Consequent），用于规定放入工作内存的新断言。这种基于规则的系统称为规则演绎系统（Rule based deduction system）。如果THEN部分用于规定某种动作，则称为反应式系统（Reaction system）或产生式系统（Production system）。 正向推理（Forward chaining）：从IF向THEN方向进行的推理（从事实出发）。 逆向推理（Backward chaining）：从THEN部分向IF的推理（从结论出发）。 4-1-2 规则正向演绎系统 1. 事实表达式的“与或形”变换：将事实表示为非蕴涵形的“与或形”，作为系统的总数据库。即将事实表示为谓词演算公式，而不是化为子句。 步骤如下： 用和的关系，消去蕴涵式。 用De Morgan定律将否定符号移入括号内，直到每个否定符号的辖域只有一个谓词符号为止。 对表达式进行Skolem替换及变成“前束范式”。 对全称量词改名、量词进行标准化、消去存在量词。 删除全称量词（则所有余下的量词都是全称量化的）。 事实表达式的“与或图”表示（实际上是对子句集的简洁表示） 图2-3-1 事实表达式的“与或图/树”表示图示 例如：将进行“与或形”变换后成为如下形式：。“与或图”表示如图2-3-1。其中，根表示整个事实表达式，叶节点表示基本事实表达式。 “与或图”的F规则变换（Forward或正向规则变换） 目的：应用1条规则到“与或图”时，用规则的后项代替“与或图”中所有与该规则的前项相同的叶子节点（即基本事实节点），可以由新图的叶子节点，很容易地得到全部消解式。从而证明某个目标公式。 假设：中，是单文字，是“与或”形的唯一公式。且出现在该蕴涵式中的所有变量都是全称化变量。那么，单文字前项的任何蕴涵式，都可以化为辖域为整个表达式蕴涵形式。 例如： 消去蕴涵 否定移入 进行Skolem化 消去全称量词 恢复蕴涵式 图2-3-2 (a) 不含变量的“与或图” 图2-3-2 (b) 应用一条规则得到的??与或图” 应用实例：将规则运用至图2-3-2(a)的叶节点上成为图2-3-2(b)所示，其中连接两个的弧线叫“匹配弧”。 图2-3-2中，规则的子句形式为：和。原来的事实表达式子句图解集为（如图2-3-2(a)）：{，，，}。运用规则的两个子句对事实表达式子句集合中的进行消解，从图上很容易获得其消解式的完备集合：{，，，}。 目标公式（终止条件） 运用F规则的目的：从事实公式及规则集出发，证明某一个目标公式。 方法：①假设用文字集表示目标公式，且该集合各元素都用析取表示。②用目标文字和规则对“与或图”增加后继节点。当目标节点与图中文字节点n上的一个文字相匹配时，则对节点n添加新后继，标记为匹配的目标文字（即成为新的目标节点），并用匹配弧线连接到其父辈节点上去。③当产生式系统产生一个“与或图”，并且包含一个图解时，系统结束。 终止条件：当正向演绎系统产生了一个包含有以目标节点作为终止的解图时，系统就成功地终止。 目标节点 规则： 匹配弧线 图2-3-4 用消解反演求证目标公式的图解 图2-3-3 满足终止条件的“与或图” 例如： 事实： 规则：， 目标： 规则的子句析取形式集：{，，，} 图2-3-3终止条件的“与或图”形成过程： 事实节点及其或分支文字节点和； 和分别和两个规则都有相匹配的文字，所以，在和之后分别添加以规则为基础的后继节点和。 其中的，分别和目标匹配。系统结束。 目标的否定： 从目标?事实的操作过程，从THEN到IF的推理过程。 图2-3-4目标公式的反演求证过程： 4-1-3 规则逆向演绎系统 目标表达式的“与或”形式 将目标公式化为“与或”形或“与或图”（消去蕴涵，否定移入，量词处理等） 如：化成： ，然后，作变量分离标准化： 图2-3-5 目标公式的“与或图”表示实例 注1：逆向推理中的“与或图”之 K线连接符的目的是用来表达合取关系的。 注2：根节点的任一后裔叫做子目标节点，相应的表达式称做子目标。 注3：目标公式的子句集合可从“与或图”中得到，即叶节点上文字的合取。如上图的结果如下： “与或图”B规则变换（Backward或逆向规则变换） 与F规则变换相比，变成形式。同时，对，将其化为两条规则，即和。 事实节点的一致解图（终止条件） 假设：事实表达式均为文字的合取形；当一个文字与“与或图”的文字