《知识的一阶谓词逻辑表示法》由会员分享，可在线阅读，更多相关《知识的一阶谓词逻辑表示法（161页珍藏版）》请在金锄头文库上搜索。
1、河南理工大学计算机学院 陈峰 人工智能中的谓词演 算及应用人工智能中的谓词演算及应用 1 学习目标：了解一阶谓词演算的基本体系，掌握命题逻辑和谓 词逻辑的归结方法，以及基于归结的提取问题回答的方 法，掌握基于规则的正向演绎方法和逆向演绎方法。 2 学习指南：本章内容是在一阶谓词逻辑的基础上介绍有关的方 法，假定读者已经学习过一阶谓词逻辑的有关内容。在 学习的同时，自己尝试重新做一遍例题，将有助于你的 学习。在有条件的情况下，可以尝试用程序实现本章介 绍的一些主要方法，不过有一定的难度。人工智能中的谓词演算及应用 3 难重点：命题逻辑的归结方法，谓词逻辑的归结方法 ，基于归结的问题回答方法，基于
2、规则的正向演 绎方法和基于规则的逆向演绎方法。4.1一阶谓词逻辑基本理论一、命题与联结词 定义4-1 具有确定真值的陈述句，称为命题。命题若是简单的陈述句，不能分解成更简单的句子，我们称这 样的命题为简单命题或原子命题。可以用英文字母P，Q，R，或是 带有下标的大写英文字母Pi等表示简单命题，将命题用合适的符号表 示，称为命题符号化。对于简单命题来说，它的真值是确定的，因而又称为命题常项 或命题常元。真值可以变化的简单陈述句称为命题变项或命题变元。 2、联结词（1）“否定”联结词，当命题P为真时，则P为假，反之为真。 （2） ：“析取”联结词，它表示两个命题存在“或”的关系。 （3）：“合取”
3、联结词，它表示两个命题之间具有“与”关系。 （4）：“蕴含”、“单条件”，PQ表示“如果P，则Q”。其中 P为前件，Q为后件。 （5） ：“等价”、“双条件”，P Q表示“P当且仅当Q”。4.1一阶谓词逻辑基本理论（续）4.1一阶谓词逻辑基本理论（续） 二、个体词与谓词1. 个体词 定义4-2 个体 (个体词)是指所研究对象中可以独立存在的具体事 物、状态或个体之间的关系。 在谓词逻辑中，个体可以是常量也可以是变量(变元)。 个体常量：表示具体的或特定的个体，用a,b,c,d表示； 个体变量：表示抽象的或泛指的个体，用x,y,z表示； 个体域(论域)：个体变量的（取值范围）值域，常用D表示。个
4、体域 可以是有限的也可以是无限的4.1一阶谓词逻辑基本理论（续） 2. 谓词 定义4-3 用于刻画个体的性质、状态或个体之间的关系 ，称为谓词。 谓词一般也用P,Q,R等大写字母表示。 3. 函数符号 函数符号，又称函词，是从若干个思维对象到某个思维 对象的映射的符号。 n元函数f(x1,x2,xn)规定为一个映射： f: Dn D4.1一阶谓词逻辑基本理论（续） 谓词与函数的区别： 1、谓词的真值是真和假，而函数无真值可言，其 值是个体域中的某个个体。 2、谓词实现的是从个体域中的个体到T或F的映射 ，而函数实现的是同一个个体域中从一个个体到 另一个个体的映射。 3、在谓词逻辑中，函数本身不
5、能单独使用，它必 须嵌入到谓词中。4.1一阶谓词逻辑基本理论（续） 4. 谓词(谓词填式) 定义4-4 将表示谓词的符号和表示个体的符号组合成一 个函词，就称谓词填式，简称谓词。如果没有特殊说明 ，以后我们提到的谓词均指谓词填式。与命题逻辑相似 ，谓词逻辑中也有谓词常项和谓词变项之分。含有个体 变元的谓词没有真值，但当谓词中的变元都用指定的个 体取代时，谓词就有了特定的值T或F。4.1一阶谓词逻辑基本理论（续） n元谓词：含有n个个体符号的谓词P(x1,x2,xn)，它表 示一个映射： P：Dn T，F或是(D1D2Dn)T，F 谓词的语义是由使用者根据需要人为定义的。 谓词中包含的个体数目称
6、为谓词的元数，如：Q(x)是一元 谓词，P(x, a)是二元谓词，A(x1,x2,xn)是n元谓词。 若X是个体常元、变元或函数，谓词称为一阶谓词；如果 某个X本身又是一个一阶谓词，则谓词称为二阶谓词。依 次类推。 与谓词联系着的n个个体的出现顺序不是任意的。 同一谓词的个体变元取值于不同个体域时，所得命题真假 值可以不同。4.1一阶谓词逻辑基本理论（续） 三、量词 设谓词P(x)表示x是正数，F(x,y)表示x与y是好朋 友，则： (x)P(x)：表示个体域中所有个体x都是正数。 (x) (y)F(x,y)：表示在个体域中所有个体x,都 存在个体y，x与y是好朋友。 4.1一阶谓词逻辑基本理
7、论（续） 四、 谓词公式 项： 单独一个个体符号（包括常量和变量）是项； 若t1，tn是项，则f(t1,tn)是项； 所有项由上述两规则生成。 原子公式： 若t1，tn是项，P是n元谓词符号，则单 独一个谓词P(t1,tn)称为原子谓词公式； n=0时退化为原子命题公式。简称原子4.1一阶谓词逻辑基本理论（续） 定义4-5 下述规则得到谓词演算的合式公式： (1) 单个谓词是合式公式，称为原子谓词公式； (2) 若A是谓词公式，则 A也是合式公式； (3) 若A，B都是合式公式，则AB，AB，AB ，A B也都是合式公式； (4) 若A是合式公式，x是任一个体变元，则 (x)A ，(x)A也都
8、是合式公式。4.1一阶谓词逻辑基本理论（续） 2. 公式的解释 在命题逻辑中，对命题公式中各个命题变元的一次真值 指派称为命题公式的一个解释。一旦解释确定，根据各 联结词的定义就可求出命题公式中真值(T或F)。 定义4-6 解释I有四个要素： (1) 给出非空论域D； (2) 对公式G，对每个常量指派D中的一个元素； (3) 对公式G，对每个n元谓词指派一个Dn T，F的映 射； (4) 对公式G，对每个n元函数指派一个Dn D的映射。4.1一阶谓词逻辑基本理论（续） 5 谓词公式的永真性与可满足性 定义4-7 如果谓词公式P对于个体域上的任何一 个解释都取得真值，则称P在D上是永真的，换 句
9、话说，P在每一个非空个体域上均永真，则称P 永真。 定义4-8 对于谓词公式P，在个体域D中，至少 存在一个解释使得公式P在此解释下真值为T，则 公式P是可满足的或相容的。 定义4-9 如果谓词公式P对个体域D上任何一个 解释都取得真值F，则称P在D上永假的，又称为 不可满足性或不相容性的。4.1一阶谓词逻辑基本理论（续） 定义4-10 若公式G在解释I下为T，即取值为真 ，则称解释I满足公式G，或称解释I是G的一个模 型。 对于公式集，可以看成是其中的每个公式G的 合取，即 =G1G2Gn， 若G1，G2，Gn皆为真，则其合取亦为真，故 定义在公式G上的定义都可推广到公式集，也 是适用的。4
10、.1一阶谓词逻辑基本理论（续） 6 谓词公式的等价性与永真蕴含性 推理规则 (1) P规则：在推理的任何步骤上都可以引入前提。 (2) T规则：推理时，如果前面步骤中有一个或多个公式 永真蕴含公式S，则可以把S引入推理过程中。 (3) CP规则：如果能从R和前提集合中推出S来，则可以 从前提集合推出RS来。 (4) 反证法：P Q，当且仅当，P Q F ，即Q为P的逻 辑结论，当且仅当P Q是不可满足的。 定理4-1 为P1,P2,Pn的逻辑结论，当且仅当 (P1P2P3Pn) 是不可满足的。4.1一阶谓词逻辑基本理论（续） 定义1：谓词公式X是谓词公式A的一部分，则称X 为A的子公式。若子公
11、式为（ X）P(X)或（ X）P(X)，则称X为指导变元，P(X)为相应量 词的作用域或辖域。在辖域中X的所有出现称为X 在公式A中的约束出现（即X为相应量词的指导变 元所约束），A中不是约束出现的其它变元称为 自由变元。 定义2：设X是谓词合式公式A的一个个体变元，若 以y代替x后不产生变元的新的约束出现，则称A（X）关于y是自由的。4.1一阶谓词逻辑基本理论（续） 定理1：设X是谓词公式A的一个个体变元，A的论 域为D，A(x)关于y是自由的，则(x)P(x)=P(y) 特例： (x)P(x)=P(X)上述公式称为全称固化。定理2：设X是谓词公式A的一个个体变元，A的论 域为D，A(x)关
12、于y是自由的，则(x)P(x)=P(y)，其中y是个体域中某 一个可使P(y)为真的个体。 4.1一阶谓词逻辑基本理论（续） 6 谓词公式的等价性与永真蕴含性 定义4-11 设P与Q是两个谓词公式，D是它们共同 的个体域，若对于D上的任何解释，P和Q都有相 同的真值，则称P与Q在个体域D上是等价的，如 果D是任意个体域，则称P和Q是等价的，记作P Q。 定义4-12 对于谓词公式P和Q，如果PQ永真，则 称P永真蕴含Q，且称Q为P的逻辑结论，称P为Q的 前提，记作P Q。4.1一阶谓词逻辑基本理论（续） 例：证明 (PQ)R)(RP)(SP) T4.1一阶谓词逻辑基本理论（续） 7 谓词公式的
13、范式 （1）. 前束范式 定义4-13 设F为一谓词公式，如果其中的所有 量词均非否定地出现在公式的最前面，且它们的 辖域为整个公式，则称F为前述范式。一般地， 前束范式可写成 (Q1x1)(Qnxn)M(x1,xn) 其中，Qi(i1,2,n)为前缀，它是一个由全 称量词或存在量词组成的量词串，M(x1,xn) 为母式，它是一个不含任何量词的谓词公式。4.1一阶谓词逻辑基本理论（续） (2). Skolem范式 定义4-14 如果前束范式中所有的存在量词都 在全称量词之前，则称这种形式的谓词公式为 Skolem范式。求该范式方法： 把公式变换成等价的前束范式； 把不含量词的母式变换成等价的合
14、取范式； 消去所有存在量词： 若不受全称量词约束，用母式中没有的常量 符号代换； 若受全称量词约束，用母式中没有的函数来 代换；4.1一阶谓词逻辑基本理论（续） 3. 范式的求解 对任一合式公式可通过以下步骤化成前束范式： (1) 消去多余的前束(量词)。这在化简过程都要随时注 意到，因为可能出现母式中没有其前束中相对应的约束 变元，因而这个前束是多余的，应及时消去。 (2) 消去蕴涵符号(“”联结词)。反复使用具有 “”联结词的等值公式，把公式中所有的“”都消 去。 (3) 内移否定词“”的辖域范围。反复使用摩根定律和 量词互换式，把否定词标到只作用于原子公式为止。 (4) 变量标准化。对变
15、量作必要的换名，使每一量词只 约束一个唯一的变量名。由于变量名可任意设定，因而 该过程不影响合式公式的真值。 (5) 把所有量词都集中到公式左面，移动时不要改变其 相对顺序。4.1一阶谓词逻辑基本理论（续）置换（substitution）： 一个有序对的集合s=ti/vi（i=1, 2, n）称为代 换。 其中vi（i=1, 2, . n）是互不相同的变量，ti （i=1, 2, . n）是不同于vi的项，可以是常量 、函数，或者其他的变量。 当ti都是基项时，代换称为基代换。不含任何元素 的代换称为空代换。它是一个空集，记作。 置换s表示将公式（表达式）中的所有变量vi用项ti代替 。对公式E施以置换s，记作Es。 Es称作公式E的代换实例。 一个公式的任何代换实例都是原公式的逻辑结论。 例： 设有置换s=z/x, a/y， 则：Px, f(y), bs=Pz, f(a), b。 这里x被换成了z，y被换成了a。 定义：设=t1/x1,t2/x2,tn/xn， =u1/y1,u2/y2um/ym是两个代换。与的 复合代换，记作
