《人工智能》第三章知识演绎课件.ppt

* 谓词演绎的归结方法 命题逻辑中的归结推理方法 若命题逻辑描述的命题A1,A2,...An和B,要证明在A1∧A2∧...∧An成立的条件下有B成立，或说A1∧A2∧...∧An→B。很显然A1∧A2∧...∧An→B等价于证明A1∧A2∧...∧An∧?B是矛盾(永假)式。归结推理的方法就是从A1∧A2∧...∧An∧ ?B出发使用归结推理规则来寻找矛盾，从而证明A1∧A2∧...∧An→B的成立。这种方法称为反演推理方法。 * 谓词演绎的归结方法 命题逻辑的归结推理过程 利用逻辑蕴含式和逻辑等价式将命题公式化成合取范式(子句的合取) 子句集：将若干个子句的合取式中的合取词∧换成逗号，形成的集合称为子句集。 从子句集S出发，仅只对S的子句间使用归结推理规则（即求归结式），并将所得归结式仍放入S中，进而再对新子句集使用归结推理规则，重复这些步骤直到得到空子句□（说明有矛盾）。也就是说S是不可满足的，从而与子句集S对应的定理是成立的。 * 谓词演绎的归结方法 谓词公式的子句形 合取范式和析取范式 合取范式：若谓词公式A有如下形式B1∧B2∧...∧Bn,其中Bi(i=1,2,...n)形如L1∨L2∨...∨Ln，并且L1,L2,...Ln都是文字。析取范式：若谓词公式A有如下形式B1∨B2∨...∨Bn,其中Bi(i=1,2,...n)形如L1∧L2∧...∧Ln，并且L1,L2,...Ln都是文字。前束范式：将所有的量词都放在谓词公式的前面。前束范式可分成前束合取范式和前束析取范式。 * 谓词演绎的归结方法 化成前束合取范式的步骤 Step1：消去∧，∨，?以外的连接词? A?B............. ? A∨B A?B............(? A∨B)∧(? B∨A) step2：将连接词?内移，移到原子公式之前?  ?(? A) ?A  ?(A∧B) ? ? A∨ ? B  ?(A∨B) ? ? A∧ ? B  ??xA(x) ? ?x ? A(x)  ? ?xA(x) ? ? x ? A(x) * 谓词演绎的归结方法 化成前束合取范式的步骤 Step3：将量词尽可能向左推，推到前缀所在的位置，用下列公式：? ?xA(x)∨B............ ?x（A(x)∨B），其中B中不含约束变元 B∨?xA(x)............ ?x（B∨A(x)），其中B中不含约束变元 ?xA(x)∨B............ ?x（A(x)∨B），其中B中不含约束变元 B∨?xA(x)............ ?x（B∨A(x)），其中B中不含约束变元 同样对上面式子中的∨改为∧可得到另一组关于的∧的替换式。 * 谓词演绎的归结方法 化成前束合取范式的步骤 step4：用下式进行替换： ?xA(x)∧?xB(x).................. ?x（A(x)∧B(x)） ?xA(x)∨?xB(x).................. ?x?y（A(x)∨B(y)）,采用更名规则 ?xA(x)∨?xB(x).................. ?x（A(x)∨B(x)） ?xA(x)∧?xB(x).................. ?x?y（A(x)∧B(y)）,采用更名规则 Step5：使用∧，∨的分配律化成合取范式。 * 谓词演绎的归结方法 将谓词公式化成子句集的步骤 按上述步骤化成前束合取范式； 化成Skolem标准型，消去存在量词；消取存在量词时，还要进行变元替换。变元替换分两种情况： ⑴若该存在量词在某些全称量词的辖域内，则用这些全称量词指导变元的一个函数代替该存在量词辖域中的相应约束变元，这样的函数称为Skolem函数；  ⑵ 若该存在量词不在任何全称量词的辖域内，则用一个常量符号代替该存在量词辖域中相应约束变元，这样的常量符号称为Skolem常量。 * 谓词演绎的归结方法 将谓词公式化成子句集的步骤 消去所有全称量词? 消去合取词∧，用逗号代替，以子句为元素组成一个集合S，即是谓词公式的子句集。 * 谓词演绎的归结方法 引入控制策略 从谓词逻辑的归结方法中我们可以看出，当使用归结法时，若从子句集 S 出发做所有可能的归结，并将 归结式加入 S 中，再做第二层这样的归结，…直到产生空子 句。 这种盲目的归结，会产生组合爆炸问题。 这种无控制的归结导致大量的不必要的归结式的产生。 如何给出控制策略，以使系统仅 选择合式的子句对其做归结来避免多余不必要的归结式的 出现，或者说少做些归结但仍然导出空子句来，这已经成为 一个重要的问题。 《人工智能》第三章 知识演绎 实验课教学的主要目标是使我们了解