第三讲经典逻辑推理..ppt

目标公式的与/或形变换 在与/或形逆向演绎推理中，要求目标公式采用与/或形表示，其化简采用与正向系统中对事实表达式处理的对偶形式。 转化步骤 要用存在量词约束变元的Skolem函数来替换由全称量词约束的相应变元，消去全称量词。（隐含着变量受存在量词的约束 ） 再消去存在量词，并进行变元换名，使主析取元之间具有不同的变元名。 目标公式的与/或形变换 例如，有如下目标公式： (?y) (?x)(P(x)→(Q(x)∧?(R(x)∧S(y)))) Skolem化后为 ?P(f(y))∨(Q(f(y), y)∧(?R(f(y))∨?S(y))) 变元换名后为 ?P(f(z))∨(Q(f(y), y)∧(?R(f(y))∨?S(y))) 目标公式的与/或树表示 目标公式的与/或形也可用与/或树表示出来，其表示方法与正向演绎推理中事实的与或树表示略有不同： 子表达式之间的析取关系用单一连接符连接，表示为或的关系； 子表达式之间的合取关系则用k线连接符连接，表示为与的关系。 例如：对上述目标公式的与/或形，可用如下的与/或树表示。 目标公式的与/或树表示 ?P(f(z))∨Q(f(y), y)∧(?R(f(y))∨?S(y)) ?P(f(z)) Q(f(y), y)∧(?R(f(y))∨?S(y)) Q(f(y), y) ?R(f(y))∨?S(y) ?R(f(y)) ?S(y) 若把叶节点用它们之间的合取及析取关系连接起来，就可得到原目标公式的三个子目标： ?P(f(z))； Q(f(y), y)∧? R(f(y))； Q(f(y), y)∧? S(y) B规则的表示形式 B规则的表示形示形式 W→L 其中，前项W为任一与/或形公式，后项 L为一单文字。 这里要求B规则的右边为文字，是因为推理时要用它与目标与或树中的叶节点进行匹配（合一），而目标与或树中的叶节点是文字。 如果已知的B规则不是要求的形式，可用与转化F规则类似的方法把它转化为规定的形式。 特别地，当B规则为W→L1∧L2时，则可化件为两条规则W→L1和W→L2进行处理。 已知事实的表示形式 已知事实的表示形式 反向演绎系统的事实表达式限制为文字合取形式，如： F1∧F2∧ …∧Fn 其中，每个Fi（i=1,2,…,n）都为单文字，且都可单独起作用，因此可表示为如下集合形式 { F1，F2， … ，Fn } 规则逆向演绎推理过程 规则逆向演绎推理 从目标公式的与/或树出发，通过运用B规则最终得到了某个终止在事实节点上的一致解图，推理就可成功结束 推理过程 1）首先用与/或树把目标公式表示出来； 2）用B规则的右部和与/或树的叶节点进行匹配，并将匹配成功的B规则加入到与/或树中； 3）重复进行步骤2，直到产生某个终止在事实节点上的一致解图为止。这里的“一致解图”是指在推理过程中所用到的代换应该是一致的。 规则逆向演绎推理过程 例：设有如下事实及规则 事实： f1: DOG(Fido) Fido是一只狗 f 2: ? BARKS(Fido) Fido是不叫的 f 3: WAGS-TAIL(Fido) Fido摇尾巴 f 4: MEOWS(Myrtle) Myrtle喵喵叫 规则逆向演绎推理过程 规则： r1: (WAGS-TAIL(x1)∧DOG(x1))→ FRIENDLY(x1) 摇尾巴的狗是温顺的狗 r2: (FRIENDLY(x2)∧ ? BARKS(x2))→ ? AFRAID(y2, x2) 温顺又不叫的东西是不值得害怕的 r3: DOG(x3)→ANIMAL(x3) ：狗为动物 r4: CAT(x4)→ANIMAL(x4)：猫为动物 r5: MEOWS(x5)→CAT(x5)：喵喵叫的动物是猫 规则逆向演绎推理过程 问题： 是否存在这样的一只猫和一条狗，使得这只猫不害怕这只狗？ 该问题的目标公式为： (?x) (?y) (CAT(x)∧DOG(y)∧?AFRAID(x, y)) 改目标公式经变换后得到 CAT(x)∧DOG(y)∧ ? AFRAID(x, y) 用逆向推理求解该问题的演绎过程如下图所示： CAT(x)∧DOG(y)∧ ? AFRAID(x,y)