AI(确定性推理)专用课件.pptVIP

* 4.5 基于规则的演绎推理 上一节讨论了归结演绎推理，它需要把谓词公式化为子句形，尽管这种转化在逻辑上是等价的，但是原来蕴含在谓词公式中的一些重要信息却会在求取子句形的过程中被丢失。例如，下面的几个蕴含式 ﹁A∧﹁B→C, ﹁A∧﹁C→B, ﹁A→B∨C, ﹁B→A∨C, 都与子句 A∨B∨C 等价。但在A∨B∨C中，是根本得不到原逻辑公式中所蕴含的哪些超逻辑的含义的。况且，在不少情况下人们多希望使用那种接近于问题原始描述的形式来进行求解，而不希望把问题描述化为子句集。 规则是一种比较接近于人们习惯的问题描述方式，按照这种问题描述方式进行求解的系统称为基于规则的系统，或者叫做基于规则的演绎系统。 规则演绎系统的推理可分为正向演绎推理、逆向演绎推理和双向演绎推理三种形式。 * 4.5.1 规则正向演绎推理 规则正向演绎和前面所讨论过的正向推理相对应。 它是从已知事实出发，正向使用规则，直接进行演绎，直至到达目标为止的一种证明方法。一个直接演绎系统不一定比反演系统更有效，但其演绎过程容易被人们所理解。 * 4.5.1 规则正向演绎推理1. 事实表达式的与/或形变换（1/2） 在一个基于规则的正向演绎系统中，其前提条件中的事实表达式是作为系统的初始综合数据库来描述的。对事实的化简，只须转换成不含蕴含符号“→”的与/或形表示即可，而不必化成子句集。把事实表达式化为非蕴含形式的与/或形的主要步骤如下： (1) 利用连接词化规律“P→Q?﹁P∨Q”，消去蕴含符号。事实上，在事实表达式中很少有含蕴含符号“→”出现，因为可把蕴含式表示成规则。 (2) 利用狄.摩根定律及量词转换率把“﹁”移到紧靠谓词的位置，直到每个否定符号的辖域最多只含一个谓词为止。 (3) 对所得到的表达式进行前束化。 (4) 对全称量词辖域内的变量进行改名和标准化，对存在量词量化的变量用skolem函数代替，使不同量词约束的变元有不同的名字。 (5) 消去全称量词，而余下的变量都被认为是全程量词量化的变量。 (6) 对变量进行换名，使主合取元具有不同的变量名。 * 4.5.1 规则正向演绎推理1. 事实表达式的与/或形变换（2/2） 例如，有如下表达式 (?x) (?y)(Q(y, x)∧﹁((R(y)∨P(y))∧S(x, y))) 可把它转化为： Q(z, a)∧((﹁R(y)∧﹁P(y))∨﹁S(a, y)) 这就是与/或形表示。 * 4.5.1 规则正向演绎推理2. 事实表达式的与/或树表示（1/3） 事实表达式的与/或形可用一棵与/或树表示出来。例如，对上例所给出的与/或式，可用如下与/或树来表示。 Q(z, a)∧((﹁R(y)∧﹁P(y))∨﹁S(a, y)) Q(z, a) ((﹁R(y)∧﹁P(y))∨﹁S(a, y)) ﹁R(y)∧﹁P(y) ﹁S(a, y) ﹁R(y) ﹁P(y) * 4.5.1 规则正向演绎推理2. 事实表达式的与/或树表示（2/3） 在该图中，每个节点表示该事实表达式的一个子表达式，子表达式之间的与、或关系规定如下： 当某个表达式为k个子表达式的析取时，例如E1∨E2∨…∨Ek，其中的每个子表达式Ei均被表示为E1∨E2∨…∨Ek的后继节点，并由一个k线连接符将这些后继节点都连接到其父节点，即表示成与的关系。 当某个表达式为k个子表达式的合取时，例如E1∧E2∧…∧Ek，其中的每个子表达式Ei均被表示成E1∧E2∧…∧Ek的一个单一的后继节点，并由一个单一连接符连接到其父节点，即表示成或的关系。 这样，与/或树的根节点就是整个事实表达式，端节点均为事实表达式中的一个文字。有了与/或树的表示，就可以求出其解树（结束于文字节点上的子树）集。并且可以发现，事实表达式的子句集与解树集之间存在着一一对应关系，即解树集中的每个解树都对应着子句集中的一个子句。其对应方式为：解树集中每个解树的端节点上的文字的析取就是子句集中的一个子句。 例如，上图所示的与/或树有3个解树，分别对应这以下3个子句： Q(z, a) ﹁R(y)∨ ﹁ S(a, y) ﹁P(y)∨ ﹁ S(a, y) * 3.5.1 规则正向演绎推理2. 事实表达式的与/或树表示（3/3） 与/或树的这个性质很重要，它可以把与/或树看作是对子句集的简洁表示。不过，表达式的与/或树表示要比子句集表示的通用性差一些，原因是与/或树中的合取元没有进一步展开