知识表示2谓词逻辑表示产生式表示.ppt

《知识表示2谓词逻辑表示产生式表示.ppt》由会员分享，可在线阅读，更多相关《知识表示2谓词逻辑表示产生式表示.ppt（116页珍藏版）》请在三一办公上搜索。

1、2023/8/21,1,人工智能原理,第二讲知识表示 之谓词逻辑/产生式表示,主讲：王祖喜 华中科技大学图像所,2023/8/21,2,知识的表示方法,谓词逻辑法 状态空间法问题归约法语义网络法 框架表示法 面向对象表示 剧本(script)表示 过程(procedure)表示 小结,2023/8/21,3,人工智能学科体系,人工智能学科体系的层次人工智能理论基础数学基础:数理逻辑，计算的数学理论，离散数学,模糊数学思维科学理论:认知心理学,逻辑或抽象思维学,形象或直感思维学 计算机工程技术:硬件,软件技术人工智能原理知识的表达,知识的处理,知识的获取与学习,利用知识求解问题.人工智能工程系统

2、专家咨询系统,专家系统开发工具与环境,自然语言理解系统,图像理解与识别系统,智能机器人系统,2023/8/21,4,数理逻辑,数理逻辑：用数学方法来研究推理的形式结构和推理规律的数学学科与数学其它分支、计算机科学、AI、语言学有密切的联系数理逻辑的内容逻辑演算命题逻辑谓词逻辑证明论公理集合论递归论模型论,2023/8/21,5,提纲命题逻辑一阶谓词逻辑,2023/8/21,6,用形式逻辑（尤其是一阶谓词逻辑）表示知识是AI 研究中提出使用的一种普遍方法。命题逻辑和谓词逻辑是最先应用于人工智能的两种逻辑，谓词逻辑是在命题逻辑基础上发展起来的，命题逻辑可以看作是谓词逻辑的一种特殊形式。,2023/

3、8/21,7,一、命题逻辑,命题定义：能够判断真假的陈述句真值真：正确的判断;真值1,T假：错误的判断;真值0,F例子：2是素数雪是黑色的3能够被2整除地球以外的星球上也有人,2023/8/21,8,一些不是命题的句子,X+y5 X,y未知，真假不定这朵花多美呀！感叹句明天下午有会吗？疑问句请你把门关上！祈使句,2023/8/21,9,判断是否为命题的方法,陈述句真值确定真值是确定的可以不知道,2023/8/21,10,原子命题与命题符号化,原子命题（简单命题）不能够再分解的命题命题符号化使用小写的字母表示命题放在命题的前面p,q,r,pi,qi,rip:2是素数 真命题q:雪是黑的 假命题,

4、2023/8/21,11,命题常量和命题变量,命题常量：其真值是确定的简单命题命题变量（命题变元）定义：真值不确定的简单陈述句表示：也用小写字母表示：p,q,r,pi,qi,ri性质：命题变量不是命题例子：X+y5,2023/8/21,12,复合命题,定义：由简单命题用联结词联结而成的命题例子3不是偶数2是素数和偶数林芳学过英语或日语如果角A和角B是对顶角，则角A和角B相等,2023/8/21,13,否定、合取联结词,定义1：设p为任一命题，复合命题“非p”称为p的否定式，记做p。为否定联结词，p为真当且仅当p为假。p:3是偶数p:3不是偶数定义2：设p,q为二命题，复合命题“p并且q”称作p

5、和q的合取式，记做pq，为合取联结词，pq为真当且仅当p，q同时为真p:李平聪明q:李平用功pq：李平不但聪明，而且用功p q：李平聪明,但不用功,2023/8/21,14,析取联结词,定义3：设p,q为二命题，复合命题“p或q”称作p和q的析取式，记做p q，为析取联结词，pq为真当且仅当p和q中至少有一个为真p:李平聪明q:李平用功pq：李平聪明或者用功pq：李平聪明或者不用功,2023/8/21,15,蕴涵联结词,定义4：设p,q为二命题，复合命题“如果p，则q”称作p和q的蕴涵式，记做pq，为蕴涵联结词，pq为假当且仅当p为真，q为假如果pq为真，记做pq，称为定理与自然语言不一样，蕴

6、涵式的前件和后件可以没有内在联系 例如：如果224，则太阳从西边出来蕴涵式的真值表,2023/8/21,16,蕴涵联结词,将下列命题符号化只要不下雨，我就骑自行车上班只有不下雨，我才骑自行车上班p:下雨q:骑自行车上班pqqp,2023/8/21,17,等价联结词,定义5：设p,q为二命题，复合命题“p当且仅当q”称作p和q的等价式，记做p q，为等价联结词，pq为假当且仅当p与q的真值不相同与自然语言不一样，等价式的2个命题可以没有内在联系例如：224，当且仅当太阳从西边出来蕴涵式的真值表,2023/8/21,18,逻辑联结词的优先级,2023/8/21,19,命题符号化的例子,分析出简单命

7、题，将之符号化用联结词将简单命题联结起来，形成复合命题的符号化例子：1：小王是游泳冠军或是百米赛跑冠军2：如果我上街，我就去书店看看，除非我很累1：pq,其中：q:小王是游泳冠军；q:小王是百米赛跑冠军2：r(pq),其中p:我上街,q:我去书店看看,r:我很累,2023/8/21,20,命题公式及分类,复合命题：p,pq,pq,pq,pq如果p,q为命题常量，这些复合命题为命题如果p,q为命题变量，这些复合命题为命题公式命题公式：由命题常量、命题变量、逻辑联结词、括号等构成的有效字符串,2023/8/21,21,命题公式及分类,定义6：1.单个命题常项或变项p,q,r,pi,qi,ri,0,

8、1是合式公式2.如果A是合式公式，则（A）为合式公式3.如果A,B是合式公式，则（AB）,（A B）,（AB）,（A B）也是合式公式4.只有有限次地应用13组成的符号串才是合式公式命题逻辑下的合式公式：命题公式，公式例子：q qvr,2023/8/21,22,公式的层次,定义7若A为单个命题（常项或变项）p,q,r,pi,qi,ri,0,1，则称A为0层公式称A是n+1(n=0)层公式是指A符合下列情况之一：A B,B为n层公式A BC,其中B，C分别为i,j层公式，且n=max(i,j)A BC,其中B,C的层次同2A B C,其中B,C的层次同2A B C,其中B,C的层次同2,2023

9、/8/21,23,命题公式的赋值或解释,命题公式中命题常项和变项，不是命题，只有对命题公式中的所有命题变项进行赋值，公式的真值才能够确定下来，才能够变成命题定义8：设A为一个命题公式，p1,p2,pn为出现在A中的所有命题变项，给指定一组真值，称为对A的一个赋值或解释。如果指定的一组值使A的值为真，则称这组值为成真赋值，如果指定的一组值使A的值为假，则称这组值为成假赋值。,2023/8/21,24,公式的真值表,真值表：含有n个变项的公式，其赋值有2n个，将每一个赋值及公式在此赋值下的真值构成的表例子:(p(pq)q,2023/8/21,25,公式的性质,定义9设A为一个命题公式若A在它的各种

10、赋值下取值均为真，则称A为重言式或永真式（真值表最后一列全为1）若A在它的各种赋值下取值均为假，则称A为矛盾式或永假式（真值表最后一列全为0）若A至少存在一组赋值是成真赋值，则称A为可满足式（真值表最后一列有1）,2023/8/21,26,等值演算,判断公式性质的办法真值表等值演算将之演算成简单形式，判断其性质定义10设A,B为2个命题公式，若等价式A B是重言式，则称A与B是等值的，记做A B：不是逻辑联结词，一个等值的记号，不能够用（数值上的相等）代替等值本质上是指：公式A和B在任何解释下都相等,2023/8/21,27,逻辑等值式,2023/8/21,28,逻辑等值式,2023/8/21

11、,29,逻辑等值式,2023/8/21,30,等值演算,利用等值式，将一个公式变换成另外一种形式的过程例子,2023/8/21,31,等值演算,2023/8/21,32,等值演算,2023/8/21,33,简单析取式及简单合取式,简单析取式和简单合取式定义10：仅由有限个命题变项或其否定构成的析取式称为，简单析取式；仅由有限个命题变项或其否定构成的合取式称为，简单合取式例子：简单析取式：p,q,pq,pq,pqr简单合取式：p,q,pq,pq,pqr,2023/8/21,34,合取范式,定义11：仅有有限个简单析取式构成的合取式称为合取范式A=A1A2An其中A1，A2，An为简单析取式例子：

12、A=(pqr)(pq)(qq)任何公式都有与其对应的合取范式,2023/8/21,35,化成合取范式的步骤,1.消去对，来说冗余的联结词2.否定联结词的消除或内移3.利用分配率,2023/8/21,36,合取范式,原子：命题常项或变项文字：原子或原子的否定 子句：文字的析取合取范式：子句的合取子句集：合取范式的集合表示每一个合取项作为集合的元素元素之间的关系为合取,2023/8/21,37,命题逻辑的问题,命题作为命题演算的基本单位，不再分解无法研究命题内部的结构和命题之间的联系例子：苏格拉底三段论p:凡人都是要死的q:苏格拉底是人r:苏格拉底是要死的命题符号化：(pq)r 真值不定！解决问题

13、的办法将命题进一步分解成：个体词，谓词和量词等研究它们的形式结构和逻辑关系，总结出正确地推理形式和规则一阶谓词逻辑,2023/8/21,38,二、一阶谓词逻辑,简单命题的分解：个体词和谓词个体词指可以独立存在的客体可以表示具体的事物：李明，玫瑰花，自然数可以表示抽象的概念：思想谓词用于刻画个体词的性质或个体词之间的关系的词 2是有理数，是有理数 小李比小王高，比高,2023/8/21,39,个体常项、个体变项和个体域,个体常项定义：表示具体或特定的词表示：小写的英文字母a,b,c,表示个体确定下来个体变项定义：泛指的个体的词表示：小写的英文字母x,y,z,表示个体没有确定下来个体域个体变项的取

14、值范围可以是一个有限的集合a,b,c也可以是一个无限的集合：全体自然数，全体实数全总个体域：宇宙间的一切事物组成的个体域,2023/8/21,40,谓词常项、谓词变项,谓词常项定义：表示具体性质或关系的词表示：大写英文字母F,G,H,谓词变项定义：表示抽象或泛指的性质或关系的词表示：大写英文字母F,G,H,F(x):x很高，x是无理数,;L(x,y):x比y学习好,x比y大,;,2023/8/21,41,谓词的元数,谓词的元数：谓词中包含的个体词的个数n元谓词：包含有n个个体词的谓词F(x)一元谓词L(x,y)二元谓词有时n元谓词：包含有n个个体变项的谓词F(a):0元谓词L(x,a):1元谓

15、词,2023/8/21,42,谓词符号化的例子,2是素数且是偶数F(x):x是素数;G(x)：x是偶数a:2F(a)G(a)如果2大于3，则2大于4L(x,y):x大于ya:2;b:3;c:4L(a,b)L(b,c),2023/8/21,43,全称量词和存在量词,谓词符号化下面的句子所有的人都是要死的有的人活到100岁以上量词：表示数量的词全称量词对应于日常语言中的“一切”，“任意的”，“所有的”表示：xF(x）,2023/8/21,44,全称量词和存在量词,存在量词对应于日常语言中的“存在着”，“有一个”，“至少一个”等词表示：xF(x),2023/8/21,45,谓词符号化的例子,所有的人

16、都是要死的定义谓词：F(x），x是要死的个体域为全体人类时：xF(x）全总个体域(没有申明个体域)：x(M(x)F(x)特性谓词：M(x)有的人活到100岁以上定义谓词：G(x）x活到100岁以上个体域为全体人类时：xG(x）全总个体域(没有申明个体域)：x(M(x)G(x),2023/8/21,46,量词使用的注意事项,1.不同的个体域，符号化的形式可能不一样2.如果没有给出个体域，都应以全总个体域为个体域3.引入特性谓词后，使用全称量词和存在量词符号化的形式不一样4.个体词和谓词的涵义确定之后，n元谓词转化成命题至少要n个量词,2023/8/21,47,量词使用的注意事项,5.当个体域为有

17、限集时，D=a1,a2,an,由量词的意义可以看出，对于任意的谓词F(x)，都有 xF(x)F(a1)F(a2)F(an)xF(x)F(a1)F(a2)F(an)6.多个量词同时出现，不能够随意颠倒它们的次序 x yH(x,y)x yH(x,y),2023/8/21,48,一阶谓词逻辑中的命题符号化,凡是有理数都可以表示成分数不用引入特性谓词的情况 xF(x)引入特性谓词的情况 x(R(x)F(x),2023/8/21,49,一阶谓词逻辑中的命题符号化,没有不犯错误的人没有指定个体域，以全总个体域作为个体域谓词：M(x)x是人；F(x):x犯错误 x(M(x)F(x)在北京工作的人未必是北京人

18、F(x):x在北京工作；G(x):x是北京人 x(F(x)G(x),2023/8/21,50,谓词公式的字母表,定义11 字母表个体常项:a,b,c,ai,bi,ci,i=1个体变项:x,y,z,xi,yi,zi,i=1函数符号:f,g,h,fi,gi,hi,i=1谓词符号:F,G,H,Fi,Gi,Hi,i=1量词符号:,联结词符：,逗号和括号：（，），,2023/8/21,51,项的递归定义,定义121.个体常项和变项是项2.若(x1,x2,xn)是任意的n元函数，x1,x2,xn是项，则(x1,x2,xn)是项3.只有有限次地使用1，2生成的符号才是项a,b,x,y,f(x,y),f(x,

19、g(a,b,z),2023/8/21,52,合式公式（谓词公式）,原子公式定义13：设R(x1,x2,.,xn)是任意的n元谓词，t1,t2,tn为项，则R(t1,t2,tn)称为原子公式合式公式，定义14：1.原子公式是合式公式2.如果A是合式公式，则（A）为合式公式3.如果A,B是合式公式，则（AB）,（A B）,（AB）,（A B）也是合式公式4.如果A是合式公式，则 xA，xA也是合式公式5.只有有限次地应用14组成的符号串才是合式公式（谓词公式）,2023/8/21,53,指导变项、辖域,定义15：在合式公式 xA和 xA中，称x为指导变项，称A为相应量词的辖域。在辖域中，x的所有出

20、现称为约束出现（即x受相应量词指导变项的约束），A中不是约束出现的其它变项称为自由出现。通常用A(x)表示x是自由出现的任意公式例子 x(F(x)yH(x,y)xF(x)G(x,y)x y(R(x,y)L(y,z)xH(x,y),2023/8/21,54,闭式,定义16：设A为任一公式，若A中无自由出现的个体变项，则称A是封闭的合式公式，简称闭式。例子：,2023/8/21,55,换名规则和代替规则,为了避免出现某个变项既是自由出现的又是约束出现的，使用以下2种办法换名规则：将量词辖域种出现的某个约束出现的个体变项及对应的指导变项，改成另外一个辖域中未曾出现过的个体变项符号，公式其它部分不变

21、xF(x)G(x,y)zF(z)G(x,y)代替规则：对某个自由出现的个体变项用与原公式中的所有个体变项符号不同的变项符号来代替，且处处代替 xF(x)G(x,y)xF(x)G(z,y),2023/8/21,56,公式的解释,公式的解释：一阶谓词公式中含有：个体常项，个体变项（自由出现或约束出现的），函数变项，谓词变项等。对各种变项指定特殊的常项来代替，就构成公式的一个解释。解释，定义17一个解释I由下面的4个部分构成1.非空个体域D2.D上的一部分特定的元素3.D上的一些特定的函数4.D上的一些特定的谓词,2023/8/21,57,解释的例子,解释DI=2,3DI上的特定元素函数：f(2)=

22、3,f(3)=2谓词：F(2)=0;f(3)=1 G(x,y)为G(i,j)=1,i,j=2,3;L(x,y)为L(2,2)=L(3,3)=1 L(3,2)=L(2,3)=0;,2023/8/21,58,公式的解释,2023/8/21,59,公式的性质,定义18设A为一个公式(谓词公式)若A在它的任何解释下取值均为真，则称A为逻辑有效式或永真式若A在它的任何解释下取值均为假，则称A为矛盾式或永假式若A至少存在一组解释是成真赋值，则称A为可满足式,2023/8/21,60,代换实例,定义19：设A0是含命题变项p1,p2,pn的命题公式，A1,A2,An是n个谓词公式，用Ai(i=1n)处处代替

23、pi，所得到的公式称为A0的代换实例例子命题公式：pq A1 xF(x)A2 G(x,y)代换实例：(xF(x)G(x,y),2023/8/21,61,代换实例的一个结论,命题公式的重言式的代换实例在谓词逻辑中，仍然是重言式；命题公式的矛盾式的代换实例在谓词逻辑中，仍然是矛盾式；例子：,2023/8/21,62,一阶逻辑等值式,定义20：设A,B是一阶逻辑中的任意2公式，若A B是逻辑有效式，则称A与B是等值的，记做A B，称A B为等值式命题逻辑中的24条等值式的代换实例也是逻辑等值式,2023/8/21,63,谓词逻辑中的逻辑等值式1,定理1：量词否定等值式,2023/8/21,64,谓词

24、逻辑中的逻辑等值式2,定理2：量词的辖域收缩和扩张等值式,2023/8/21,65,谓词逻辑中的逻辑等值式3,定理3：量词分配等值式,2023/8/21,66,谓词逻辑中的逻辑等值式4,定理4量词的性质相同，可以交换位置量词的性质不同，不可交换位置,2023/8/21,67,前束范式,定义21：设A为一谓词公式，如果A具有如下形式：Q1x1Q2x2QkxkB 则称A是前束范式。其中每一个Qi为 或 B为不含量词的谓词公式（母式）例如：x y(F(x,y)G(x,y)前束范式 x(F(x)y(G(y)H(x)非前束范式,2023/8/21,68,前束范式例题,求下列公式的前束范式,2023/8/

25、21,69,谓词公式的合取范式和子句集,对任一公式量词辖域扩张和收缩定理，得到前束范式对于母式，等值演算得到合取范式合取项的集合，构成了该公式的子句集S前束范式母式原子：谓词文字：谓词或谓词的否定子句：文字的析取合取范式：子句的合取子句集：合取范式的集合形式，元素之间的关系为合取关系,2023/8/21,70,一阶谓词逻辑语法和语义：谓词逻辑的基本组成、谓词符号、常量符号、变量符号、函数符号、项的递归定义、原子、谓词演算语言的语义连词和量词：合适公式、连词、合取、析取、蕴含、否定、等价、命题演算、全称量词、存在量词、约束变量、自由变量、句子、一阶谓词演算,表示方法 逻辑表示法,2023/8/2

26、1,71,谓词逻辑的基本组成：谓词符号、变量符号、函数符号和常量符号，并用圆括弧、方括弧、花括弧和逗号隔开，以表示论域内的关系。谓词符号：表示个体所具有的性质，或者若干个体之间的关系的符号。习惯用大写字母P，Q，R或GREATER，LOVE表示。常量符号：用来表示论域内的物体或实体，它可以是实际的物体和人，也可以是概念或具有名字的任何事情。一般用英文字母表中前几个带下标或不带下标的小写字母表示。如a，b，.，a1，b2，c3，.。,2023/8/21,72,变量符号：不必明确涉及是哪一个实体。习惯上用带下标或不带下标的小写字母表示。如x，y，.，x1，y2，。函数符号：表示论域内的函数。习惯用

27、小写字母f，g，h表示。,2023/8/21,73,例如，要表示“机器人（ROBOT）在1号房间（ROOM1）内”，简单的原子公式如下：INROOM（ROBOT，r1）式中，INROOM为谓词符号，ROBOT和r1为常量符号。又如，要表示“李（LI）的母亲与他的父亲结婚”，原子公式如下：MARRIEDfather（LI），mother（LI）式中，函数符号mother、father分别用来表示某人与他（她的）母亲、父亲之间的映射。,2023/8/21,74,谓词演算语言的语义：对于每个谓词符号，必须规定定义域内的一个相应关系；对于每个常量符号，必须规定定义域内相应的一个实体；对于每个函数符号，

28、必须规定定义域内相应的一个函数。,2023/8/21,75,对于已定义了的某个解释的一个原子公式，只有当其对应的语句在定义域内为真时，才具有值T（真）；而当其对应的语句在定义域内为假时，该原子公式才具有值F（假）。因此，INROOM（ROBOT，r1）具有值T，而INROOM（ROBOT，r2）则具有值F。,2023/8/21,76,当一个原子公式含变量符号时，对定义域内实体的变量可能有几个设定。对某几个设定的变量，原子公式取值T；而对另外几个设定的变量，原子公式取值F。,2023/8/21,77,表示方法 逻辑表示法,一阶谓词逻辑是谓词逻辑中最直观的一种逻辑。它以谓词形式来表示动作的主题、客

29、体。客体可以多个。如：张三与李四打网球（Zhang and Li play tennis），可写为：play(Zhang,Li,tennis)这里谓词是play，动词主体是Zhang和 Li，而客体是tennis。谓词逻辑规范表达式：P(x1,x2,x3,)，这里P是谓词,xi是主体与客体。,2023/8/21,78,表示方法 逻辑表示法,谓词比命题更加细致地刻画知识：表达能力强如：北京是个城市，City(x)把城市这个概念分割出来。把“城市”与“北京”两个概念连接在一起，而且说明“北京”是“城市”的子概念。（有层）谓词可以代表变化的情况如：City(北京),真。City(煤球)，假在不同的知

30、识之间建立联系.,2023/8/21,79,表示方法 逻辑表示法,在不同的知识之间建立联系如：Human(x)Lawed(x)，人人都受法律管制，x是同一个人。Commit(x)Punished(x)，x不一定是人也可以是动物。而，Human(x)Lawed(x)commit(x)Punished(x)，意为如果由于某个x是人而受法律管制，则这个人犯了罪就一定要受到惩罚。,2023/8/21,80,表示方法 逻辑表示法,谓词逻辑法是应用最广的方法之一，其原因是：谓词逻辑与数据库，特别是关系数据库就有密切的关系。在关系数据库中，逻辑代数表达式是谓词表达式之一。因此，如果采用谓词逻辑作为系统的理论

31、背景，则可将数据库系统扩展改造成知识库。一阶谓词逻辑具有完备的逻辑推理算法。如果对逻辑的某些外延扩展后，则可把大部分的知识表达成一阶谓词逻辑的形式。（知识易表达）.,2023/8/21,81,表示方法 逻辑表示法,谓词逻辑法是应用最广的方法之一，其原因是：.谓词逻辑本身具有比较扎实的数学基础，知识的表达方式决定了系统的主要结构。因此，对知识表达方式的严密科学性要求就比较容易得到满足。这样对形式理论的扩展导致了整个系统框架的发展。逻辑推理是公理集合中演绎而得出结论的过程。由于逻辑及形式系统具有的重要性质，可以保证知识库中新旧知识在逻辑上的一致性（或通过相应的一套处理过程检验）、和所演绎出来的结论

32、的正确性。而其它的表示方法在这点上还不能与其相比。,2023/8/21,82,表示方法 逻辑表示法,为此逻辑表示法在实际人工智能系统上得到应用。存在问题：谓词表示越细，推理越慢、效率越低，但表示清楚。实际中是要折衷的。,2023/8/21,83,置换与合一,2023/8/21,84,置换,置换是形如t1/v1，.，tn/vn的一个有限集。其中vi是变量，而ti是不同于vi的项（常量、变量、函数），且vivj（ij），i，j=1，2，.，n。假元推理，就是由合适公式W1和W1W2产生合适公式W2的运算。全称化推理，是由合适公式(x)W(x)产生合适公式W(A)，其中A为任意常量符号。一个表达式的

33、置换就是在该表达式中用置换项置换变量。一般说来，置换是可结合的，但置换是不可交换的。,2023/8/21,85,置换,例1：表达式Px，f（y），B 的4 个置换为s1=z/x，w/ys2=A/ys3=q（z）/x，A/ys4=c/x，A/y将它们分别作用于表达式，得：Px，f（y），Bs1=Pz，f（w），BPx，f（y），Bs2=Px，f（A），BPx，f（y），Bs3=Pq（z），f（A），BPx，f（y），Bs4=Pc，f（A），B,2023/8/21,86,合一,寻找项对变量的置换，以使两表达式一致，叫做合一(unification)。如果一个置换s作用于表达式集Ei的每个元素，则用

34、Eis来表示置换例的集。称表达式集Ei是可合一的，如果存在一个置换s使得：E1s=E2s=E3s=那么称此s为Ei的合一者，因为s的作用是使集合Ei成为单一形式。,2023/8/21,87,合一,例2：表达式集 Px,f（y），B，Px，f（B），B的合一者为 s=A/x，B/y因为 Px，f（y），Bs=Px，f（B），Bs=PA，f（B），B如果s是的任一合一者，有存在某个s，使得Eis=Eis成立,则称为的最通用(最一般)的合一者,记为mgu.如上例s是的一个合一者，但不是最简单的合一者，其最简单的合一者为=B/y,2023/8/21,88,分歧集,设有一非空有限公式集F=F1，F2，F

35、n,从F中个公式的第一符号同时向右比较,直到发现第一个彼此不仅、不尽相同的符号为止,从F的各个公式中取出那些以第一个不一致符号开始的最大的子表达式为元素,组成一个集合D,称为F的分歧集.,2023/8/21,89,合一算法,合一算法：设F非空集合有限表达集合,则可按下列步骤求其mgu：置k=0，Fk=F，k=（空置换，不含元素的置换）若Fk只含有一个表达式，则算法停止，k=mgu。找出Fk的分歧集Dk。若Dk中存在元素ak和tk，其中ak是变元，tk是项目，且ak不在tk中出现，则置：k+1=k，Fk+1=Fktk/ak，k=k+1，转步骤（2）算法停止，F的mgu不存在。,2023/8/21

36、,90,合一算法举例,例3 求公式集 F=P(a,x,f(g(y),P(z,h(z,u),f(u)的最一般合一者,2023/8/21,91,合一算法举例（续）,K=0:F0=F,0=F0不是单一表达式，有D0=a,z,其中z是变元，且不在a中出现，则1=0a/z=a/z=a/zF1=F0a/z=P(a,x,f(g(y),P(a,h(a,u),f(u)K=1:F1不是单一表达式，有D1=x,h(a,u)2=1h(a,u)/x=a/z,h(a,u)/x F2=F1h(a,u)/x=P(a,h(a,u),f(g(y),P(a,h(a,u),f(u),2023/8/21,92,合一算法举例（续）,K=

37、2:F2不是单一表达式 D2=g(y),u 3=2g(y)/u=a/z,h(a,g(y),g(y)/u F3=F2 g(y)/u=P(a,h(a,g(y),f(g(y)K=3:F3是单一表达式，所以3=a/z,h(a,g(y),g(y)/u是F的最一般合一者,2023/8/21,93,注意：1.在合式公式中，连接词的优先级别是:,2.位于量词后面的单个谓词或用括号括起来的合式公式称为量词辖域，辖域内与量词中同名变元称为约束变元，不受约束的变元称为自由变元。如：(x)(P(x,y)Q(x,y)R(x,y)3.在谓词公式中，变元的名字是无关紧要的，可以把一个名字换成另一个名字，但必须注意：当对量词

38、辖域内的约束变元更名时，必须把同名的约束变元统一改成相同的名字，且不能与辖域内的自由变元同名；当对量词辖域内的自由变元改名时，不能改成与约束变元相同的名字。,2023/8/21,94,谓词逻辑是一种形式语言，也是到目前为止能够表达人类思维活动规律的一种最精确的语言，它与人们的自然语言比较接近，又可方便地存储到计算机中去，并被精确地处理。因此，它成为最早应用于人工智能中表示知识的一种逻辑。,知识的一阶谓词逻辑表示,2023/8/21,95,谓词逻辑适合于表示事物的状态、属性、概念等事实性的知识，也可以用来表示事物间确定的因果关系，即规则。事实通常用合式公式的“与/或”形表示（用合取符号及析取符号

39、连接起来的公式）。规则通常用蕴涵式 表示。用谓词公式（合式公式）表示知识时，需要首先定义谓词，指出每个谓词的确切含义，然后再用连接词把有关的谓词连接起来，形成一个谓词公式表达一个完整的含义。,2023/8/21,96,例1 有下列知识：刘欢比他父亲出名。高扬是计算机系的一名学生，但他不喜欢编程序。人人爱劳动。为了用谓词公式表示上述知识，首先需要定义谓词：Bigger(x,y):x 比 y 出名。Computer(x):x 是计算机系的学生。Like(x,y):x 喜欢 y。Love(x,y):x 热爱 y。Man(x):x 是人。然后用谓词公式把上述知识表示为：Bigger（Liuhong,f

40、ather(Liuhong)Computer(Gaoyang)Like(Gaoyang,programing)(x)(Man(x)Love(x,labour),2023/8/21,97,例2 设有下列知识自然数都是大于零的整数所有整数不是偶数就是奇数偶数除以2是整数首先定义谓词如下：n(x):x是自然数I(x):x是整数E(x):x是偶数O(x):x是奇数GZ(x):x大于零另外用函数S(x)表示x除以2.此时，上述知识可用谓词公式分别表示为：(x)（n(x)GZ(x)I(x)）(x)(I(x)E(x)O(x)(x)(E(x)I(s(x),2023/8/21,98,例3.设在房内c处有一机器人

41、，在a及b处各有一张桌子，a桌上有一个盒子，为了让机器人从c处出发把盒子从a处拿到b处的桌上，然后再回到c处，需要制定相应的行动规划。下面用一阶谓词逻辑描述机器人的行动过程。该例子中，不仅要用谓词表示事物的状态、位置，还要表示其行动。,设相关谓词的定义如下：table(x):x是桌子 empty(y):y手中是空的 at(y，z)：y在z的附近 holds(y,w):y拿着w on(w,x):w在x的上面 其中，x的个体域是a,b;y的个体域是robot;z的个体域是a,b,c;w的个体域是box,2023/8/21,99,问题的初始状态是：at(robot,c)empty(robot)on(

42、box,a)table(a)table(b)问题的目标状态是：at(robot,c)empty(robot)on(box,b)table(a)table(b)机器人的目标是把问题的初始状态转化为目标状态，其间它必须完成一系列的操作。,2023/8/21,100,操作一般可以分为条件和动作两部分。条件可以很容易的用谓词公式表示，动作可以通过动作前后的状态变化表示出来，即只要指出动作后应从动作前的状态中删去和增加什么谓词就描述了相应的动作。机器人为了把盒子从a处拿到b处，应执行如下三个操作：goto(x,y):从x处走到b处；pick_up(x):在x处拿起盒子；set_done(x):在x处放下

43、盒子。这三个操作分别用条件和动作表示如下：1.Goto(x,y)条件：at(robot,x)动作 删除：at(robot,x)增加：at(robot,y)2.Pick_up(x)条件：on(box,x)table(x)empty(robot)动作 删除：empty(robot)on(box,x)增加:holds(robot,box),2023/8/21,101,3.Set_down(x)条件：at(robot,x)table(x)holds(robot,box)动作 删除：holds(robot,box)增加：empty(robot)on(box,x)操作步骤：机器人在执行每一个操作前，总要先

44、检查当前状态是否可使所要求的条件得到满足。若能满足，就执行相应的操作，否则就检查下一个操作所要求的条件。所谓检查当前状态是否满足所要求的条件，其实是一个定理证明的过程，即证明当前状态是否蕴含操作所要求的条件，若蕴含表示当前所要求的条件得到了满足。机器人行动规划问题的求解过程如下：(其中，在检查条件的满足性时要进行变量的代换。),2023/8/21,102,At(robot,c)Empty(robot)状态1(初始状态)On(box,a)用c代换xTable(a)用a代换yTable(b)goto(x,y)At(robot,a)Empty(robot)状态2On(box,a)用a代换xTable

45、(a)Table(b)pick-up(x)At(robot,a)Hold(robot,box)状态3Table(a)用a代换xTable(b)用b代换y,goto(x,y)At(robot,b)Hold(robot,box)状态4Table(a)用b代换xTable(b)setdown(x)At(robot,b)empty(robot)状态5on(box,b)用b代换xTable(a)用c代换yTable(b)goto(x,y)At(robot,c)empty(robot)状态6on(box,b)(目标状态)Table(a)Table(b),2023/8/21,103,自然性：符合人类对问题的

46、直觉理解；描述性：表示与知识分离；精确性：只有“真与假”的值；严密性：谓词逻辑具有严格的形式定义以及推理规则；容易实现：用谓词逻辑表示的知识可以比较容易地转换为计算机内部形式，易于模块化，便于对知识的增加、修改、删除；不能表示不确定的知识；组合爆炸：不易表示启发式知识，当状态空间大时，当前数据库与知识库中操作的匹配以及操作层列的确定会出现时空上的膨胀。效率低。,谓词表示的特性,2023/8/21,104,产生式规则系统表示,1.Introduction产生式最早由P.Post于1943年提出，用于构造Post机计算模型；1972年A.Newell和在研究人类的认识模型中提出了 Rule-Bas

47、ed 产生式方法及规则表示模式；Rule-Based 的表示法是目前应用最为普遍的一种。产生式通常用于表示具有因果关系的知识。2.产生式规则的基本形式基本形式：P Q，或者 If P then Q其中，P是产生式的前提，用于指出该产生式是否可用的条件；Q是一组结论或操作，用于指出当前题P所指示的条件被满足时，应该得出的结论和应该执行的操作。整个产生式的含义是：如果前提P所指示的条件被满足时，则可得出结论Q或者执行Q所规定的操作。,2023/8/21,105,例如 规则1：if 该动物有羽毛 then 该动物是鸟 规则2：if 该动物是鸟 and 有长脖子 and 有长腿 and 不会飞 the

48、n 该动物是鸵鸟 注意：谓词逻辑中的蕴含式与产生式的基本形式有相同的形式，其实蕴含式只是产 生式的一种特殊情况，理由有二：(1)蕴含式只能表示精确知识，而产生式还可以表示不精确知识。例如 在疾病诊断专家系统中的一条产生式：if 本微生物的染色斑是革兰氏阴性 本微生物的形状呈杆状 病人是中间宿主 then 该微生物是绿农杆菌，置信度为0.6 它表示当前条件都被满足时，结论的可相信的程度为0.6,2023/8/21,106,(2)蕴含式只能精确匹配，而产生式可以是不精确匹配。用产生式表示的知识系统中，决定一条知识是否可用的方法是检查当前是 否有已知事实可与前提所规定的条件匹配，而且匹配可以是精确的

49、也可以 是不精确的，只要按照某种算法求出的相似度落在某个预定的范围内就认 为是可匹配的，但对谓词逻辑的蕴含式来说，其匹配总要求是精确的。由于产生式与蕴含式存在这些区别，导致它们在处理方法及应用等 方面都有较大差别。下面给出产生式的严格意义上的形式描述（BNF描述)及语义：:=:=:=:=:=操作名（变元,),2023/8/21,107,3产生式系统 把一组产生式放在一起，让他们互相配合，协同作用，一个产生式生成的结论可以供另一个产生式作为已知事实使用，以求得问题的解决，这样的系统称为产生式系统。一般说来，一个产生式系统由以下三个基本部分组成：,(1)规则库 用于描述相应领域中的知识的产生式集合

50、称为规则库。知识是否完整，一致，表达是否准确灵活，对知识的组织是否合理，不 仅将直接影响到系统的性能，而且还会影响到系统的运行效率，因此对规则库的设计和组织应给与足够的重视。,2023/8/21,108,建立规则库时，应注意以下问题：(1)有效的表达领域内的过程性知识。例:动物识别系统的规则库 这是一个用以识别虎，金钱豹，斑马，长颈鹿，企鹅，鸵鸟，信天翁等七 种动物的产生式系统。为了实现对这些动物的识别，该系统建立了如下规则库：r1:If 该动物有毛发 then 该动物是哺乳动物 r2:If 该动物有奶 then 该动物是哺乳动物 r3:If 该动物有羽毛 then 该动物是鸟 r4:If 该