知识的一阶谓词逻辑表示法

河南理工大学计算机学院陈峰[e-mail]人工智能中的谓词演算及应用人工智能中的谓词演算及应用1学习目标：了解一阶谓词演算的基本体系，掌握命题逻辑和谓词逻辑的归结方法，以及基于归结的提取问题回答的方法，掌握基于规则的正向演绎方法和逆向演绎方法。2学习指南：本章内容是在一阶谓词逻辑的基础上介绍有关的方法，假定读者已经学习过一阶谓词逻辑的有关内容。在学习的同时，自己尝试重新做一遍例题，将有助于你的学习。在有条件的情况下，可以尝试用程序实现本章介绍的一些主要方法，不过有一定的难度。人工智能中的谓词演算及应用3难重点：命题逻辑的归结方法，谓词逻辑的归结方法，基于归结的问题回答方法，基于规则的正向演绎方法和基于规则的逆向演绎方法。4.1一阶谓词逻辑基本理论一、命题与联结词定义4-1具有确定真值的陈述句，称为命题。命题若是简单的陈述句，不能分解成更简单的句子，我们称这样的命题为简单命题或原子命题。可以用英文字母P，Q，R，…或是带有下标的大写英文字母Pi等表示简单命题，将命题用合适的符号表示，称为命题符号化。对于简单命题来说，它的真值是确定的，因而又称为命题常项或命题常元。真值可以变化的简单陈述句称为命题变项或命题变元。2、联结词（1）“否定”联结词，当命题P为真时，则﹁P为假，反之为真。（2）∨：“析取”联结词，它表示两个命题存在“或”的关系。（3）∧：“合取”联结词，它表示两个命题之间具有“与”关系。（4）→：“蕴含”、“单条件”，P→Q表示“如果P，则Q”。其中P为前件，Q为后件。（5）：“等价”、“双条件”，PQ表示“P当且仅当Q”。4.1一阶谓词逻辑基本理论（续）4.1一阶谓词逻辑基本理论（续）二、个体词与谓词1.个体词定义4-2个体(个体词)是指所研究对象中可以独立存在的具体事物、状态或个体之间的关系。在谓词逻辑中，个体可以是常量也可以是变量(变元)。个体常量：表示具体的或特定的个体，用a,b,c,d表示；个体变量：表示抽象的或泛指的个体，用x,y,z表示；个体域(论域)：个体变量的（取值范围）值域，常用D表示。个体域可以是有限的也可以是无限的4.1一阶谓词逻辑基本理论（续）2.谓词定义4-3用于刻画个体的性质、状态或个体之间的关系，称为谓词。谓词一般也用P,Q,R等大写字母表示。3.函数符号函数符号，又称函词，是从若干个思维对象到某个思维对象的映射的符号。n元函数f(x1,x2,…,xn)规定为一个映射：f:Dn→D4.1一阶谓词逻辑基本理论（续）谓词与函数的区别：1、谓词的真值是真和假，而函数无真值可言，其值是个体域中的某个个体。2、谓词实现的是从个体域中的个体到T或F的映射，而函数实现的是同一个个体域中从一个个体到另一个个体的映射。3、在谓词逻辑中，函数本身不能单独使用，它必须嵌入到谓词中。4.1一阶谓词逻辑基本理论（续）4.谓词(谓词填式)定义4-4将表示谓词的符号和表示个体的符号组合成一个函词，就称谓词填式，简称谓词。如果没有特殊说明，以后我们提到的谓词均指谓词填式。与命题逻辑相似，谓词逻辑中也有谓词常项和谓词变项之分。含有个体变元的谓词没有真值，但当谓词中的变元都用指定的个体取代时，谓词就有了特定的值T或F。4.1一阶谓词逻辑基本理论（续）n元谓词：含有n个个体符号的谓词P(x1,x2,…,xn)，它表示一个映射：P：Dn→{T，F}或是(D1×D2×…×Dn)→{T，F}谓词的语义是由使用者根据需要人为定义的。谓词中包含的个体数目称为谓词的元数，如：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一阶谓词逻辑基本理论（续）四、谓词公式项：单独一个个体符号（包括常量和变量）是项；若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都是合式公式，则A∨B，A∧B，A→B，AB也都是合式公式；(4)若A是合式公式，x是任一个体变元，则(x)A，(x)A也都是合式公式。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上是永真的，换句话说，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的合取，即Γ=G1∧G2∧…∧Gn，若G1，G2，…，Gn皆为真，则其合取亦为真，故定义在公式G上的定义都可推广到公式集Γ，也是适用的。4.1一阶谓词逻辑基本理论（续）6谓词公式的等价性与永真蕴含性推理规则(1)P规则：在推理的任何步骤上都可以引入前提。(2)T规则：推理时，如果前面步骤中有一个或多个公式永真蕴含公式S，则可以把S引入推理过程中。(3)CP规则：如果能从R和前提集合中推出S来，则可以从前提集合推出R→S来。(4)反证法：PQ，当且仅当，P∧QF，即Q为P的逻辑结论，当且仅当P∧Q是不可满足的。定理4-1Ｑ为P1,P2,…,Pn的逻辑结论，当且仅当(P1∧P2∧P3∧…∧Pn)∧﹁Ｑ是不可满足的。4.1一阶谓词逻辑基本理论（续）定义1：谓词公式X是谓词公式A的一部分，则称X为A的子公式。若子公式为（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)关于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是等价的，记作PQ。定义4-12对于谓词公式P和Q，如果P→Q永真，则称P永真蕴含Q，且称Q为P的逻辑结论，称P为Q的前提，记作PQ。4.1一阶谓词逻辑基本理论（续）例：证明((P→Q)→R)→((R→P)→(S→P))T4.1一阶谓词逻辑基本理论（续）7谓词公式的范式（1）.前束范式定义4-13设F为一谓词公式，如果其中的所有量词均非否定地出现在公式的最前面，且它们的辖域为整个公式，则称F为前述范式。一般地，前束范式可写成(Q1x1)…(Qnxn)M(x1,…,xn)其中，Qi(i＝1,2,…,n)为前缀，它是一个由全称量词或存在量词组成的量词串，M(x1,…,xn)为母式，它是一个不含任何量词的谓词公式。4.1一阶谓词逻辑基本理论（续）(2).Skolem范式定义4-14如果前束范式中所有的存在量词都在全称量词之前，则称这种形式的谓词公式为Skolem范式。求该范式方法：把公式变换成等价的前束范式；把不含量词的母式变换成等价的合取范式；消去所有存在量词：若不受全称量词约束，用母式中没有的常量符号代换；若受全称量词约束，用母式中没有的函数来代换；4.1一阶谓词逻辑基本理论（续）3.范式的求解对任一合式公式可通过以下步骤化成前束范式：(1)消去多余的前束(量词)。这在化简过程都要随时注意到，因为可能出现母式中没有其前束中相对应的约束变元，因而这个前束是多余的，应及时消去。(2)消去蕴涵符号(“→”联结词)。反复使用具有“→”联结词的等值公式，把公式中所有的“→”都消去。(3)内移否定词“”的辖域范围。反复使用摩根定律和量词互换式，把否定词标到只作用于原子公式为止。(4)变量标准化。对变量作必要的换名，使每一量词只约束一个唯一的变量名。由于变量名可任意设定，因而该过程不影响合式公式的真值。(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}，则：P[x,f(y),b]s=P[z,f(a),b]。这里x被换成了z，y被换成了a。定义：设θ={t1/x1,t2/x2,…,tn/xn}，λ={u1/y1,u2/y2…um/ym}是两个代换。θ与λ的复合代换，记作θ·λ，是由下列集合{t1λ/x1,t2λ/x2,…,tnλ/xn,u1/y1,u2/y2…um/ym}删除所有满足tiλ=xi的元素以及所有yi出现在{x1,x2,…xn}中的元素得到的集合。例：设θ={f(y)/x,z/y},λ={a/x,b/y,y/z}复合代换一般不满足交换律。合一（Unify）：设有公式的集合{Ei}(i=1,2,...,m)，如果存在一个置换s，使得这m个公式被施以s以后，变得完全一样了，则称这m个公式是可合一的，置换s是它们的合一者。例：设有公式集{P(x,f(y),b),P(z,f(b),b)}和置换s1={a/x,b/y,a/z}，由于：P(x,f(y),b)s=P(a,f(b),b)P(z,f(b),b)s=P(a,f(b),b)所以公式集{P(x,f(y),b),P(z,f(b),b)}是可合一的，置换s1={a/x,b/y,a/z}是它们的合一者。最一般合一者（mgu）：一般来说，一个公式集的合一者不是唯一的。如s2={z/x,b/y}和s3={x/z,b/y}都是公式集{P(x,f(y),b),P