基于谓词逻辑的机器推理.ppt

基于谓词逻辑的机器推理 目录 5.0 机器推理概述 5.1 一阶谓词逻辑 5.2 归结演绎推理 5.3 应用归结原理求取问题答案 5.4 归结策略 5.5 归结反演程序举例* 5.6 Horn子句归结与逻辑程序 5.7 非归结演绎推理 5.0 机器推理概述（4） 本章主要解决以下几个问题： 5.1一阶谓词逻辑 5.1.1 谓词、函数、量词 5.1.2 谓词公式 5.1.3 谓词逻辑中的形式演绎推理 5.1.1谓词、函数、量词（1） 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元个体函数，简称函数。 5.1.1谓词、函数、量词（5） 5.1.1谓词、函数、量词（6） 5.1.1谓词、函数、量词（7） 5.1.1谓词、函数、量词（8） 练习：用谓词公式表示下述命题。 已知前提： （1）自然数都是大于零的整数。 （2）所有整数不是偶数就是奇数。 （3）偶数除以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))) 所有自然数不是奇数就是一半为整数的数。 G: ?x (N(x)?(I(s(x)) ?O(x))) 5.1.2谓词公式（1） 5.1.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） 全称命题： ? x P(x)等价于P (a1)?P(a2)? … ?P(an) 特称命题 ? x G(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上的一个解释。 5.1.2谓词公式（11） 例：设个体域D＝{1,2},求公式A＝ ? x ? yP（x，y）在D上的解释，并指出在每一种解释下公式A的真值。 解：公式里没有个体常量和函数，所以直接为谓词指派真值，设为 P（1，1）＝T P（1，2）＝F P（2，1）＝T P（2，2）＝F 这就是A在D上的一个解释。 在此解释下： 当x＝1时有y＝1使P（x，y）的真值为T； 当x＝2时有y