[所有分类]第5章 基于谓词逻辑的机器推理.ppt

第5章 基于谓词逻辑的机器推理 目录 5.0 机器推理概述 5.1 一阶谓词逻辑 5.2 归结演绎推理 5.3 应用归结原理求取问题答案 5.4 归结策略 5.5 归结反演程序举例* 5.6 Horn子句归结与逻辑程序 5.7 非归结演绎推理 5.1 一阶谓词逻辑 5.1.1 谓词、函数、量词 5.1.2 谓词公式 5.1.3 谓词逻辑中的形式演绎推理 5.1.1 谓词、函数、量词（1） 命题（proposition）：是具有真假意义的语句。命题代表人们进行思维时的一种判断，或者是否定，或者是肯定。 命题可以用命题符号表示，如： 用命题符号可以表示简单的逻辑关系和推理。 5.1.1 谓词、函数、量词（2） 对于复杂的知识，命题符号能力不够。 无法把所描述的客观事物的结构及逻辑特征反映出来。 无法把不同事物间的共同特征表达出来。 5.1.1谓词、函数、量词（3） 谓词(predicate)：一般形式为P(x1, x2 ,…, xn) 其中，P为谓词名，用于刻画个体的性质、状态 或个体间的关系。 x1, x2 ,…,xn是个体，表示某个独立存在的事物或者某个抽象的概念。 5.1.1 谓词、函数、量词（4） 函数：为了表达个体之间的对应关系，引入数学中函数概念和记法。用形如f(x1,x2,…,xn)来表示个体变元对应的个体y，并称之为n元个体函数，简称函数。f是函数符号。 函数增强了谓词的表达能力 逻辑联结词 5.1.1 谓词、函数、量词（5） 5.1.1 谓词、函数、量词（6） 5.1.1 谓词、函数、量词（7） 5.1.1谓词、函数、量词（8） 练习：用谓词公式表示下述命题。 已知前提： （1）自然数都是大于零的整数。 （2）所有整数不是偶数就是奇数。 （3）偶数除以2是整数。 结论：所有自然数不是奇数就是除以2为整数的数。 5.1.1 谓词、函数、量词（9） 将上述各语句翻译成谓词公式： （1）自然数都是大于零的整数。 F1: ?x(N(x)?GZ(x) ? I(x)) （2）所有整数不是偶数就是奇数。 F2: ?x(I(x)?(E(x)? O(x))) （3）偶数除以2是整数。 F3: ?x(E(x)?I(s(x))) 所有自然数不是奇数就是除以2为整数的数。 G: ?x(N(x)?(I(s(x))? O(x))) 5.1.2 谓词公式（1） 5.1.2 谓词公式（2） 定义2：原子公式 5.1.2 谓词公式（3） 5.1.2 谓词公式（4） 辖域：紧接于量词之后被量词作用（即说明）的谓词公式称为该量词的辖域。 指导变元：量词后的变元为指导变元。 约束变元：在一个量词辖域中与该量词的指导变元相同的变元称为约束变元。 自由变元：谓词公式中除了约束变元之外的变元。 5.1.2 谓词公式（5） 一个变元在一个公式中既可以约束出现，也可以自由出现，为了避免混淆，通过改名规则改名： 对需要改名的变元，应同时更改该变元在量词及其辖域中的所有出现。 新变元符号必须是量词辖域内原先没有的，最好是公式中也未出现过的。 5.1.2 谓词公式（6） 谓词公式与命题的区别与联系 谓词公式是命题函数。 一个谓词公式中所有个体变元被量化（在谓词前加上量词），谓词公式就变成了一个命题。 从谓词公式得到命题的两种方法： 给谓词中的个体变元代入个体常元； 把谓词中的个体变元全部量化。 5.1.2 谓词公式（7） 一阶谓词：仅个体变元被量化的谓词。 二阶谓词：不仅个体变元被量化，函数符号和谓词符号也被量化。如：? P ? x P（x） 以下两种命题在个体域为有限集时（n个元素），有下面的等价式 全称命题： ?xP(x)等价于P(a1)?P(a2)? … ?P(an) 特称命题 ?xG(x)等价于P(a1)?P(a2)? … ? P(an) 5.1.2 谓词公式（8） 5.1.2 谓词公式（9） 5.1.2 谓词公式（10）* 谓词公式的解释：对谓词公式中的各种变量指定特殊的常量去替代。 设D为谓词公式P的个体域，若对P中的个体常量、函数和谓词按如下规定赋值： （1）为每个个体常量指派D中的一个元素； （2）为每个n元函数指派一个从Dn到D的映射，其中 Dn＝{(x1,x2,…,xn)|x1,x2,…,xn ∈D} （3）为每个n元谓词指派一个从Dn到{F,T}的映射。 称这些指派(谓词公式的解释)为公式P在D上的一个解释。 当被解释的谓词公式在特定解释下真值为真，称这个解释满足这个谓词公式。 谓词公式的解释* 用某个解释解释一个谓词公式，就是将解释中的各个值带到谓词公式中去，要全部取到。 约束出现的变元取值关系与量词性质有关， 当指导变元的相