确定性推理方法修改版.ppt

第四章 确定性推理方法 推理：求解问题的一种重要方法。从已知事实出发，通过运用已掌握的知识，找出其中蕴含的事实，或归纳出新的事实，这一过程通常称为推理。 确定性推理：知识和证据是确定的，结论也是确定的。 不确定推理： 单调推理、非单调推理 按照推理过程中推出的结论是否越来越接近最终目标来划分，推理又分为单调推理和非单调推理。 单调推理是在推理过程中随着推理向前推进及新知识的加入，推出的结论越来越接近最终目标。 非单调推理是在推理过程中有新知识的加入，不仅没有加强已推出的结论，反而要否定它，使推理退回到前面的一步，然后重新开始。（知识不完全情况下发生。）X是鸟，会飞，X是企鹅，不会飞。 命题逻辑 命题：能判断真假的陈述句为命题。 命题公式：单个常量或变量的命题称作合式公式。合式公式有限次组合所构成的字符串称为命题公式。 命题逻辑的基本联接词有： ~， ?， ?， ?， 等价，当且仅当，双条件 命题公式的解释： 设A为一个命题公式，P1 P2 P3 ,…,Pn 是出现在A中的全部命题变量，给P1 P2 P3 ,…,Pn各指定一个真值（0或1），称为对A的一个赋值或解释。 公式的分类 永真式：若A无成假赋值，则称A为重言式。或永真式。 永假式 可满足式：若A至少有一个成真赋值，则称A为可满足式。 非重言式的可满足式：若A至少有一个成真赋值，又至少有一个成假赋值，则称A为非重言式的可满足式。 范式（公式的标准型式） 简单合取式：仅由有限个命题变量或其否定构成的合取式成为简单合取式。 简单析取式：仅由有限个命题变量或其否定构成的析取式称为简单析取式。 合取范式：仅由有限个简单析取式构成的合取式称为合取范式。P ?(P?Q) ?(~P ?Q) 析取范式：仅由有限个简单合取式构成的析取式称为析取范式。P?(P?Q)?(~P?Q) 析取范式是矛盾式，每个简单合取式都是矛盾式。 合取范式是重言式，每个简单析取式都是重言式。 谓词逻辑 是一种形式语言，具有严密的理论体系 是一种常用的知识表示方法 例： City（北京） City（上海） Age（张三，23） (?x)(? y)(? z)(F(x, y)?F(y, z)?GF(x, z) 谓词逻辑 原子谓词公式：是一个不能再分解的命题。 原子谓词公式及其否定，统称为文字。P与~P为互补文字。 任何文字的析取称为子句。 由子句构成的集合成为子句集。 不包含任何文字的子句称为空子句，表示为NIL。 由于空子句不包含任何文字，不能被任何解释满足，所以，空子句是永假的，不可满足的。 4.1 归结原理 归结原理是一种定理证明方法，1965年由Robinson提出，从理论上解决了定理证明问题。 子句集 无量词约束 元素只是文字的析取 否定符只作用于单个文字 元素间默认为和取 例：{~I(z)?R(z), I(A), ~R(x) ?L(x), ~D(y)} 谓词公式化子句集的方法 例：(?z) (?x)(?y){[(P(x) ?Q(x)) ?R(y)] ?U(z)} 1, 消蕴涵符 理论根据：a ?b = ~a ?b p ?Q= (P ? Q) ?(~ P ? ~ Q) (?z) (?x)(?y){[~(P(x) ?Q(x)) ? R(y)] ?U(z)} 2, 移动否定符（把否定符移动到紧靠谓词的位置上） 理论根据：~(a ?b) = ~a ?~b ~(a ?b) = ~a ?~b ~(?x)P(x)=(?x)~P(x) ~(?x)P(x)=(?x)~P(x) (?z) (?x)(?y){[(~P(x) ?~Q(x)) ? R(y)] ?U(z)} 化子句集的方法（续1） 3, 变量标准化 即：对于不同的约束，对应于不同的变量 (?x)A(x) ? (?x)B(x) = (?x)A(x) ? (?y)B(y) 4, 量词左移 (?x)A(x) ? (?y)B(y) = (?x) (?y) {A(x) ? B(y)} 5, 消存在量词 (skolem化） 原则：对于一个受存在量词约束的变量，如果他不受全程量词约束，则该变量用一个常量代替，如果他受全程量词约束，则该变量用一个函数代替。 (?z) (?x)(?y){[(~P(x) ?~Q(x)) ? R(y)] ?U(z)} = (?x) {[(~P(x) ?~Q(x)) ? R(f(x))] ?U(a)} 化子句集的方法（续2） 6, 化为合取范式 即(a?b) ? (c?d) ? (e?f)的形式 (?x){[(~P(x) ?~Q(x)) ? R(f(x))]?U(a)} = (?x){(~P(x) ?