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

《知识表示2谓词逻辑表示产生式表示》由会员分享，可在线阅读，更多相关《知识表示2谓词逻辑表示产生式表示（116页珍藏版）》请在金锄头文库上搜索。

1、2024/8/271人工智能原理第二讲第二讲知识表示知识表示 之之谓词逻辑谓词逻辑/ /产生式表示产生式表示主讲：王祖喜主讲：王祖喜 华中科技大学图像所华中科技大学图像所2024/8/272知识的表示方法谓词逻辑法谓词逻辑法 状态空间法状态空间法问题归约法问题归约法语义网络法语义网络法 框架表示法框架表示法 面向对象表示面向对象表示 剧本剧本(script)(script)表示表示 过程过程(procedure)(procedure)表示表示 小结小结2024/8/273人工智能学科体系人工智能学科体系的层次人工智能学科体系的层次人工智能理论基础人工智能理论基础数学基础数学基础: :数理逻辑数

2、理逻辑，计算的数学理论，离散数学，计算的数学理论，离散数学, ,模糊数学模糊数学思维科学理论思维科学理论: :认知心理学认知心理学, ,逻辑或抽象思维学逻辑或抽象思维学, ,形象或直感思维学形象或直感思维学 计算机工程技术计算机工程技术: :硬件硬件, ,软件技术软件技术人工智能原理人工智能原理知识的表达知识的表达, ,知识的处理知识的处理, ,知识的获取与学习知识的获取与学习, ,利用知识求解问题利用知识求解问题. .人工智能工程系统人工智能工程系统专家咨询系统专家咨询系统, ,专家系统开发工具与环境专家系统开发工具与环境, ,自然语言理解系统自然语言理解系统, ,图像理图像理解与识别系统解

3、与识别系统, ,智能机器人系统智能机器人系统2024/8/274数理逻辑数理逻辑：用数学方法来研究推理的形式结构和推理规律数理逻辑：用数学方法来研究推理的形式结构和推理规律的数学学科的数学学科与数学其它分支、计算机科学、与数学其它分支、计算机科学、AI、语言学有密切的联、语言学有密切的联系系数理逻辑的内容数理逻辑的内容逻辑演算逻辑演算命题逻辑命题逻辑谓词逻辑谓词逻辑证明论证明论公理集合论公理集合论递归论递归论模型论模型论2024/8/275提纲提纲命题逻辑命题逻辑一阶谓词逻辑一阶谓词逻辑2024/8/276用形式逻辑（尤其是一阶谓词逻辑）表示知识是用形式逻辑（尤其是一阶谓词逻辑）表示知识是AI

4、研究中提出使用的一种普遍方法。研究中提出使用的一种普遍方法。命题逻辑和谓词逻辑是最先应用于人工智能的两种逻辑，命题逻辑和谓词逻辑是最先应用于人工智能的两种逻辑，谓词逻辑是在命题逻辑基础上发展起来的，命题逻辑可以谓词逻辑是在命题逻辑基础上发展起来的，命题逻辑可以看作是谓词逻辑的一种特殊形式。看作是谓词逻辑的一种特殊形式。2024/8/277一、命题逻辑命题命题定义：定义：能够判断真假的陈述句能够判断真假的陈述句真值真值真：正确的判断真：正确的判断;真值真值1,T假：错误的判断假：错误的判断;真值真值0,F例子：例子：2是素数是素数雪是黑色的雪是黑色的3能够被能够被2整除整除地球以外的星球上也有人

5、地球以外的星球上也有人2024/8/278一些不是命题的句子X+y5 X,y未知，真假不定未知，真假不定这朵花多美呀！这朵花多美呀！ 感叹句感叹句明天下午有会吗？明天下午有会吗？ 疑问句疑问句请你把门关上！请你把门关上！ 祈使句祈使句2024/8/279判断是否为命题的方法陈述句陈述句真值确定真值确定真值是确定的真值是确定的可以不知道可以不知道2024/8/2710原子命题与命题符号化原子命题（简单命题）原子命题（简单命题）不能够再分解的命题不能够再分解的命题命题符号化命题符号化使用小写的字母表示命题使用小写的字母表示命题放在命题的前面放在命题的前面p,q,r, pi,qi,rip:2是素数是

6、素数 真命题真命题q:雪是黑的雪是黑的 假命题假命题2024/8/2711命题常量和命题变量命题常量：其真值是确定的简单命题命题常量：其真值是确定的简单命题命题变量（命题变元）命题变量（命题变元）定义：真值不确定的简单陈述句定义：真值不确定的简单陈述句表示：也用小写字母表示：表示：也用小写字母表示：p,q,r, pi,qi,ri性质：命题变量不是命题性质：命题变量不是命题例子：例子：X+y52024/8/2712复合命题定义：由简单命题用联结词联结而成的命题定义：由简单命题用联结词联结而成的命题例子例子3不是偶数不是偶数2是素数和偶数是素数和偶数林芳学过英语或日语林芳学过英语或日语如果角如果角

7、A和角和角B是对顶角，则角是对顶角，则角A和角和角B相等相等2024/8/2713否定、合取联结词定义定义1：设：设p为任一命题，复合命题为任一命题，复合命题“非非p”称为称为p的否定式，记做的否定式，记做 p。 为否定联结词，为否定联结词， p为真当且仅当为真当且仅当p为假。为假。p:3是偶数是偶数 p:3不是偶数不是偶数定义定义2：设：设p,q为二命题，复合命题为二命题，复合命题“p并且并且q”称作称作p和和q的合取式，的合取式，记做记做p q， 为合取联结词，为合取联结词，p q为真当且仅当为真当且仅当p，q同时为真同时为真p:李平聪明李平聪明q:李平用功李平用功p q：李平不但聪明，而

8、且用功：李平不但聪明，而且用功p q：李平聪明：李平聪明,但不用功但不用功2024/8/2714析取联结词 定义定义3：设：设p,q为二命题，复合命题为二命题，复合命题“p或或q”称作称作p和和q的析取式，记做的析取式，记做p q， 为析取联结词，为析取联结词， p q为真当且仅当为真当且仅当p和和q中至少有一个为真中至少有一个为真p:李平聪明李平聪明q:李平用功李平用功p q：李平聪明或者用功：李平聪明或者用功p q：李平聪明或者不用功：李平聪明或者不用功2024/8/2715蕴涵联结词定义定义4：设：设p,q为二命题，复合命题为二命题，复合命题“如果如果p，则，则q”称作称作p和和q的蕴涵

9、的蕴涵式，记做式，记做pq， 为蕴涵联结词，为蕴涵联结词， pq为假当且仅当为假当且仅当p为真，为真，q为假为假如果如果pq为真，记做为真，记做pq，称为定理，称为定理与自然语言不一样，蕴涵式的前件和后件可以没有内在联系与自然语言不一样，蕴涵式的前件和后件可以没有内在联系 例如：如果例如：如果224，则太阳从西边出来，则太阳从西边出来蕴涵式的真值表蕴涵式的真值表2024/8/2716蕴涵联结词将下列命题符号化将下列命题符号化只要不下雨，我就骑自行车上班只要不下雨，我就骑自行车上班只有不下雨，我才骑自行车上班只有不下雨，我才骑自行车上班p:下雨下雨q:骑自行车上班骑自行车上班 pqq p2024

10、/8/2717等价联结词定义定义5：设：设p,q为二命题，复合命题为二命题，复合命题“p当且仅当当且仅当q”称作称作p和和q的等价的等价式，记做式，记做p q，为等价联结词，为等价联结词， pq为假当且仅当为假当且仅当p与与q的真值不相同的真值不相同与自然语言不一样，等价式的与自然语言不一样，等价式的2个命题可以没有内在联系个命题可以没有内在联系例如：例如：224，当且仅当太阳从西边出来，当且仅当太阳从西边出来蕴涵式的真值表蕴涵式的真值表2024/8/2718逻辑联结词的优先级2024/8/2719命题符号化的例子分析出简单命题，将之符号化分析出简单命题，将之符号化用联结词将简单命题联结起来，

11、形成复合命题的符号化用联结词将简单命题联结起来，形成复合命题的符号化例子：例子：1：小王是游泳冠军或是百米赛跑冠军：小王是游泳冠军或是百米赛跑冠军2：如果我上街，我就去书店看看，除非我很累：如果我上街，我就去书店看看，除非我很累1：p q,其中：其中：q:小王是游泳冠军；小王是游泳冠军；q:小王是百米赛跑冠军小王是百米赛跑冠军2： r (pq),其中其中p:我上街我上街,q:我去书店看看我去书店看看, r:我很累我很累2024/8/2720命题公式及分类复合命题：复合命题： p,p q, p q,pq,pq如果如果p,q为命题常量，这些复合命题为命题为命题常量，这些复合命题为命题如果如果p,q

12、为命题变量，这些复合命题为命题公式为命题变量，这些复合命题为命题公式命题公式：由命题常量、命题变量、逻辑联结词、命题公式：由命题常量、命题变量、逻辑联结词、括号等构成的有效字符串括号等构成的有效字符串2024/8/2721命题公式及分类定义定义6：1. 单个命题常项或变项单个命题常项或变项p,q,r,pi,qi,ri ,0,1是合式公式是合式公式2. 如果如果A是合式公式，则（是合式公式，则（ A）为合式公式）为合式公式3. 如果如果A,B是合式公式，则（是合式公式，则（A B）,（A B） ,（AB） , （A B）也是合式公式）也是合式公式4. 只有有限次地应用只有有限次地应用13组成的符

13、号串才是合式公式组成的符号串才是合式公式命题逻辑下的合式公式：命题公式，公式命题逻辑下的合式公式：命题公式，公式例子：例子：q qvr2024/8/2722公式的层次定义定义7若若A为单个命题（常项或变项）为单个命题（常项或变项）p,q,r,pi,qi, ri, ,0,1，则称，则称A为为0层公式层公式称称A是是n+1 (n=0)层公式是指层公式是指A符合下列情况之一：符合下列情况之一：A B,B为为n层公式层公式A B C, 其中其中B，C分别为分别为i,j层公式，且层公式，且n= max(i,j)A B C, 其中其中B,C的层次同的层次同2A B C, 其中其中B,C的层次同的层次同2A

14、 B C, 其中其中B,C的层次同的层次同22024/8/2723命题公式的赋值或解释命题公式中命题常项和变项，不是命题，只有对命题公式命题公式中命题常项和变项，不是命题，只有对命题公式中的所有命题变项进行赋值，公式的真值才能够确定下来中的所有命题变项进行赋值，公式的真值才能够确定下来，才能够变成命题，才能够变成命题定义定义8：设设A为一个命题公式，为一个命题公式，p1,p2,pn为出现在为出现在A中的所有命题变项，给指定一组真值，称为对中的所有命题变项，给指定一组真值，称为对A的一个的一个赋值或解释。如果指定的一组值使赋值或解释。如果指定的一组值使A的值为真，则称这组值为成真的值为真，则称这

15、组值为成真赋值，如果指定的一组值使赋值，如果指定的一组值使A的值为假，则称这组值为成假赋值。的值为假，则称这组值为成假赋值。2024/8/2724公式的真值表真值表：含有真值表：含有n个变项的公式，其赋值有个变项的公式，其赋值有2n个，将每一个赋值及公式在此赋值下的真值构成的表个，将每一个赋值及公式在此赋值下的真值构成的表例子例子: (p (pq) q2024/8/2725公式的性质定义定义9设设A为一个命题公式为一个命题公式若若A在它的各种赋值下取值均为真，则称在它的各种赋值下取值均为真，则称A为重言式或永真式（真为重言式或永真式（真值表最后一列全为值表最后一列全为1）若若A在它的各种赋值下

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

17、（数值上的相：不是逻辑联结词，一个等值的记号，不能够用（数值上的相等）代替等）代替等值本质上是指：公式等值本质上是指：公式A和和B在任何解释下都相等在任何解释下都相等2024/8/2727逻辑等值式2024/8/2728逻辑等值式2024/8/2729逻辑等值式2024/8/2730等值演算利用等值式，将一个公式变换成另外一种形式的过程利用等值式，将一个公式变换成另外一种形式的过程例子例子2024/8/2731等值演算2024/8/2732等值演算2024/8/2733简单析取式及简单合取式简单析取式和简单合取式简单析取式和简单合取式定义定义10：仅由有限个命题变项或其否定构成的析取式称为，简

18、单：仅由有限个命题变项或其否定构成的析取式称为，简单析取式；仅由有限个命题变项或其否定构成的合取式称为，简单析取式；仅由有限个命题变项或其否定构成的合取式称为，简单合取式合取式例子：例子：简单析取式：简单析取式：p, q, p q, p q, p q r简单合取式：简单合取式：p, q, p q, p q, p q r2024/8/2734合取范式定义定义11：仅有有限个简单析取式构成的合取式称为合取范式仅有有限个简单析取式构成的合取式称为合取范式A=A1 A2 An其中其中A1，A2，An为简单析取式为简单析取式例子：例子：A=( p q r) ( p q) (q q)任何公式都有与其对应的

19、合取范式任何公式都有与其对应的合取范式2024/8/2735化成合取范式的步骤1. 消去对消去对 ，来说冗余的联结词来说冗余的联结词2. 否定联结词的消除或内移否定联结词的消除或内移3. 利用分配率利用分配率2024/8/2736合取范式原子：命题常项或变项原子：命题常项或变项文字：原子或原子的否定文字：原子或原子的否定 子句：文字的析取子句：文字的析取合取范式：子句的合取合取范式：子句的合取子句集：合取范式的集合表示子句集：合取范式的集合表示每一个合取项作为集合的元素每一个合取项作为集合的元素元素之间的关系为合取元素之间的关系为合取2024/8/2737命题逻辑的问题命题作为命题演算的基本单

20、位，不再分解命题作为命题演算的基本单位，不再分解无法研究命题内部的结构和命题之间的联系无法研究命题内部的结构和命题之间的联系例子：苏格拉底三段论例子：苏格拉底三段论p:凡人都是要死的凡人都是要死的q:苏格拉底是人苏格拉底是人r:苏格拉底是要死的苏格拉底是要死的命题符号化：命题符号化： (p q)r 真值不定！真值不定！解决问题的办法解决问题的办法将命题进一步分解成：个体词，谓词和量词等将命题进一步分解成：个体词，谓词和量词等研究它们的形式结构和逻辑关系，总结出正确地推理形式和规则研究它们的形式结构和逻辑关系，总结出正确地推理形式和规则一阶谓词逻辑一阶谓词逻辑2024/8/2738二、一阶谓词逻

21、辑简单命题的分解：个体词和谓词简单命题的分解：个体词和谓词个体词个体词指可以独立存在的客体指可以独立存在的客体可以表示具体的事物：李明，玫瑰花，自然数可以表示具体的事物：李明，玫瑰花，自然数可以表示抽象的概念：思想可以表示抽象的概念：思想谓词谓词用于刻画个体词的性质或个体词之间的关系的词用于刻画个体词的性质或个体词之间的关系的词 2是有理数，是有理数， 是有理数是有理数 小李比小王高，小李比小王高， 比比高高2024/8/2739个体常项、个体变项和个体域个体常项个体常项定义：表示具体或特定的词定义：表示具体或特定的词表示：小写的英文字母表示：小写的英文字母a,b,c,a,b,c,表示表示个体

22、确定下来个体确定下来个体变项个体变项定义：泛指的个体的词定义：泛指的个体的词表示：小写的英文字母表示：小写的英文字母x,y,z,x,y,z,表示表示个体没有确定下来个体没有确定下来个体域个体域个体变项的取值范围个体变项的取值范围可以是一个有限的集合可以是一个有限的集合a,b,c也可以是一个无限的集合：全体自然数，全体实数也可以是一个无限的集合：全体自然数，全体实数全总个体域：宇宙间的一切事物组成的个体域全总个体域：宇宙间的一切事物组成的个体域2024/8/2740谓词常项、谓词变项谓词常项谓词常项定义：表示具体性质或关系的词定义：表示具体性质或关系的词表示：大写英文字母表示：大写英文字母F,G

23、,H,谓词变项谓词变项定义：表示抽象或泛指的性质或关系的词定义：表示抽象或泛指的性质或关系的词表示：大写英文字母表示：大写英文字母F,G,H, F(x): x很高，很高，x是无理数是无理数,; L(x,y):x比比y学习好学习好, x比比y大大,;2024/8/2741谓词的元数谓词的元数：谓词中包含的个体词的个数谓词的元数：谓词中包含的个体词的个数n元谓词：包含有元谓词：包含有n个个体词的谓词个个体词的谓词F(x)一元谓词一元谓词L(x,y)二元谓词二元谓词有时有时n元谓词：包含有元谓词：包含有n个个体变项的谓词个个体变项的谓词F(a): 0元谓词元谓词L(x,a):1元谓词元谓词2024/

24、8/2742谓词符号化的例子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)2024/8/2743全称量词和存在量词谓词符号化下面的句子谓词符号化下面的句子所有的人都是要死的所有的人都是要死的有的人活到有的人活到100岁以上岁以上量词：表示数量的词量词：表示数量的词全称量词全称量词对应于日常语言中的对应于日常语言中的“一切一切”，“任意的任意的”，“所有的所有的”表示：表示：xF(x）2024/8/2744全称量词和存

25、在量词存在量词存在量词对应于日常语言中的对应于日常语言中的“存在着存在着”，“有一个有一个”，“至少至少一个一个”等词等词表示：表示： xF(x)2024/8/2745谓词符号化的例子所有的人都是要死的所有的人都是要死的定义谓词：定义谓词：F(x），），x是要死的是要死的个体域为全体人类时：个体域为全体人类时： xF(x）全总个体域全总个体域(没有申明个体域没有申明个体域)： x(M(x) F(x)特性谓词：特性谓词：M(x)有的人活到有的人活到100岁以上岁以上定义谓词：定义谓词：G(x）x活到活到100岁以上岁以上个体域为全体人类时：个体域为全体人类时： xG(x）全总个体域全总个体域(没

26、有申明个体域没有申明个体域)： x(M(x) G(x)2024/8/2746量词使用的注意事项1. 不同的个体域，符号化的形式可能不一样不同的个体域，符号化的形式可能不一样2. 如果没有给出个体域，都应以全总个体域为个体域如果没有给出个体域，都应以全总个体域为个体域3. 引入特性谓词后，使用全称量词和存在量词符号化的形式引入特性谓词后，使用全称量词和存在量词符号化的形式不一样不一样4. 个体词和谓词的涵义确定之后，个体词和谓词的涵义确定之后，n元谓词转化成命题至少元谓词转化成命题至少要要n个量词个量词2024/8/2747量词使用的注意事项5. 当个体域为有限集时，当个体域为有限集时，D=a1

27、,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)2024/8/2748一阶谓词逻辑中的命题符号化凡是有理数都可以表示成分数凡是有理数都可以表示成分数不用引入特性谓词的情况不用引入特性谓词的情况xF(x)引入特性谓词的情况引入特性谓词的情况x(R(x) F(x)2024/8/2749一阶谓词逻辑中的命题符号化没有不

28、犯错误的人没有不犯错误的人没有指定个体域，以全总个体域作为个体域没有指定个体域，以全总个体域作为个体域谓词：谓词：M(x) x是人；是人；F(x): x犯错误犯错误 x(M(x) F(x)在北京工作的人未必是北京人在北京工作的人未必是北京人F(x): x在北京工作；在北京工作； G(x): x是北京人是北京人 x(F(x)G(x)2024/8/2750谓词公式的字母表定义定义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

29、, Fi,Gi,Hi, i=1量词符号量词符号: , 联结词符：联结词符： , , , , 逗号和括号：逗号和括号： （，），（，），2024/8/2751项的递归定义定义定义121. 个体常项和变项是项个体常项和变项是项2. 若若 (x1,x2,xn)是任意的是任意的n元函数，元函数，x1,x2,xn是项，则是项，则 (x1,x2,xn)是项是项3. 只有有限次地使用只有有限次地使用1，2生成的符号才是项生成的符号才是项a,b,x,y, f(x,y), f(x,g(a,b,z)2024/8/2752合式公式（谓词公式）原子公式原子公式定义定义13：设：设R(x1,x2,.,xn)是任意的是任

30、意的n元谓词，元谓词，t1,t2,tn为为项，则项，则R(t1,t2,tn)称为原子公式称为原子公式合式公式，定义合式公式，定义14：1. 原子公式是合式公式原子公式是合式公式2. 如果如果A是合式公式，则（是合式公式，则（ A）为合式公式）为合式公式3. 如果如果A,B是合式公式，则（是合式公式，则（A B）,（A B） , （AB） , （A B）也是合式公式）也是合式公式4. 如果如果A是合式公式，则是合式公式，则 xA， xA也是合式公式也是合式公式5. 只有有限次地应用只有有限次地应用14组成的符号串才是合式公式（谓词公式）组成的符号串才是合式公式（谓词公式）2024/8/2753指

31、导变项、辖域定义定义15：在合式公式：在合式公式 xA和和 xA中，称中，称x为为指导变项，称，称A为相应量词的为相应量词的辖域。在辖域中，。在辖域中，x的所有出现称为的所有出现称为约束出现（即（即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)2024/8/2754闭式定义定义16：设：设A为任一公式，若为任一公式，若A中无自由出现的

32、中无自由出现的个体变项，则称个体变项，则称A是是封闭的合式公式，简称，简称闭式。例子：例子：2024/8/2755换名规则和代替规则为了避免出现某个变项既是自由出现的又是约束出现的，为了避免出现某个变项既是自由出现的又是约束出现的，使用以下使用以下2种办法种办法换名规则：将量词辖域种出现的某个约束出现的个体变项及对应的指导变：将量词辖域种出现的某个约束出现的个体变项及对应的指导变项，改成另外一个辖域中未曾出现过的个体变项符号，公式其它项，改成另外一个辖域中未曾出现过的个体变项符号，公式其它部分不变部分不变xF(x) G(x,y) zF(z) G(x,y)代替规则：对某个自由出现的个体变项用与原

33、公式中的所有个体变项符号：对某个自由出现的个体变项用与原公式中的所有个体变项符号不同的变项符号来代替，且处处代替不同的变项符号来代替，且处处代替xF(x) G(x,y) xF(x) G(z,y)2024/8/2756公式的解释公式的解释：一阶谓词公式中含有：个体常项，个体变项（自由出现：一阶谓词公式中含有：个体常项，个体变项（自由出现或约束出现的），函数变项，谓词变项等。对各种变项指或约束出现的），函数变项，谓词变项等。对各种变项指定特殊的常项来代替，就构成公式的一个解释。定特殊的常项来代替，就构成公式的一个解释。解释，定义解释，定义17一个解释一个解释I由下面的由下面的4个部分构成个部分构成

34、1. 非空个体域非空个体域D2. D上的一部分特定的元素上的一部分特定的元素3. D上的一些特定的函数上的一些特定的函数4. D上的一些特定的谓词上的一些特定的谓词2024/8/2757解释的例子解释解释DI=2,3DI上的特定元素上的特定元素函数：函数：f(2)=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;2024/8/2758公式的解释2024/8/2759公式的性质定义定义18设设A为一个公式为一个公式(谓词公式谓词公式)若若A在它的任何解释下

35、取值均为真，则称在它的任何解释下取值均为真，则称A为为逻辑有效式或或永真式若若A在它的任何解释下取值均为假，则称在它的任何解释下取值均为假，则称A为为矛盾式或或永假式若若A至少存在一组解释是成真赋值，则称至少存在一组解释是成真赋值，则称A为为可满足式2024/8/2760代换实例定义定义19：设：设A0是含命题变项是含命题变项p1,p2,pn的命题公式，的命题公式，A1,A2,An是是n个谓词公式，用个谓词公式，用Ai(i=1n)处处代替处处代替pi，所得到的公式称为，所得到的公式称为A0的的代换实例例子例子命题公式：命题公式：p q A1 xF(x) A2 G(x,y)代换实例：代换实例：

36、( xF(x) G(x,y)2024/8/2761代换实例的一个结论命题公式的重言式的代换实例在谓词逻辑中，仍然是重言式；命题公式的矛盾式的代换实例在谓词逻辑中，仍然是矛盾式；例子：例子：2024/8/2762一阶逻辑等值式定义定义20：设：设A,B是一阶逻辑中的任意是一阶逻辑中的任意2公式，若公式，若A B是逻辑有效式，则称是逻辑有效式，则称A与与B是是等值的，记做的，记做A B，称，称A B为为等值式命题逻辑中的命题逻辑中的24条等值式的代换实例也是逻辑等值式条等值式的代换实例也是逻辑等值式2024/8/2763谓词逻辑中的逻辑等值式1 定理定理1：量词否定等值式：量词否定等值式2024/

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

38、束范式x(F(x) y(G(y)H(x) 非前束范式非前束范式2024/8/2768前束范式例题求下列公式的前束范式求下列公式的前束范式2024/8/2769谓词公式的合取范式和子句集对任一公式对任一公式量词辖域扩张和收缩定理，得到量词辖域扩张和收缩定理，得到前束范式对于母式，等值演算得到对于母式，等值演算得到合取范式合取项的集合，构成了该公式的合取项的集合，构成了该公式的子句集S前束范式前束范式母式母式原子：谓词原子：谓词文字：谓词或谓词的否定文字：谓词或谓词的否定子句：文字的析取子句：文字的析取合取范式：子句的合取合取范式：子句的合取子句集：合取范式的集合形式，元素之间的关系为合取关系子句

39、集：合取范式的集合形式，元素之间的关系为合取关系2024/8/2770一阶谓词逻辑一阶谓词逻辑语法和语义：语法和语义：谓词逻辑的基本组成、谓词符号、常量符谓词逻辑的基本组成、谓词符号、常量符号、变量符号、函数符号、项的递归定义、原子、谓词号、变量符号、函数符号、项的递归定义、原子、谓词演算语言的语义演算语言的语义连词和量词：连词和量词：合适公式、连词、合取、析取、蕴含、否合适公式、连词、合取、析取、蕴含、否定、等价、命题演算、全称量词、存在量词、约束变量、定、等价、命题演算、全称量词、存在量词、约束变量、自由变量、句子、一阶谓词演算自由变量、句子、一阶谓词演算表示方法 逻辑表示法2024/8/

40、2771谓词逻辑的基本组成谓词逻辑的基本组成：谓词符号、变量符号、函数符号和：谓词符号、变量符号、函数符号和常量符号，并用圆括弧、方括弧、花括弧和逗号隔开，以常量符号，并用圆括弧、方括弧、花括弧和逗号隔开，以表示论域内的关系。表示论域内的关系。谓词符号谓词符号：表示个体所具有的性质，或者若干个体之间的：表示个体所具有的性质，或者若干个体之间的关系的符号。习惯用大写字母关系的符号。习惯用大写字母P，Q，R或或GREATER，LOVE表示。表示。常量符号常量符号：用来表示论域内的物体或实体，它可以是实际：用来表示论域内的物体或实体，它可以是实际的物体和人，也可以是概念或具有名字的任何事情。一般的物

41、体和人，也可以是概念或具有名字的任何事情。一般用英文字母表中前几个带下标或不带下标的小写字母表示。用英文字母表中前几个带下标或不带下标的小写字母表示。如如a，b，.，a1，b2，c3，.。2024/8/2772变量符号变量符号：不必明确涉及是哪一个实体。习惯上用带下标：不必明确涉及是哪一个实体。习惯上用带下标或不带下标的小写字母表示。如或不带下标的小写字母表示。如x，y，.，x1，y2，。函数符号函数符号：表示论域内的函数。习惯用小写字母：表示论域内的函数。习惯用小写字母f，g，h表表示。示。2024/8/2773例如，要表示例如，要表示“机器人（机器人（ROBOT）在）在1号房间（号房间（R

42、OOM1）内）内”，简单的原子公式如下：简单的原子公式如下：INROOM（ROBOT，r1）式中，式中，INROOM为谓词符号，为谓词符号，ROBOT和和r1为常量符号。为常量符号。又如，要表示又如，要表示“李（李（LI）的母亲与他的父亲结婚）的母亲与他的父亲结婚”，原子公式如下：原子公式如下：MARRIEDfather（LI），），mother（LI）式中，函数符号式中，函数符号mother、father分别用来表示某人与他（她的）母亲、分别用来表示某人与他（她的）母亲、父亲之间的映射。父亲之间的映射。2024/8/2774谓词演算语言的语义谓词演算语言的语义：对于每个谓词符号，必须规定定义

43、域内的一个相应关系；对于每个谓词符号，必须规定定义域内的一个相应关系；对于每个常量符号，必须规定定义域内相应的一个实体；对于每个常量符号，必须规定定义域内相应的一个实体；对于每个函数符号，必须规定定义域内相应的一个函数。对于每个函数符号，必须规定定义域内相应的一个函数。2024/8/2775对于已定义了的某个解释的一个原子公式，只有对于已定义了的某个解释的一个原子公式，只有当其对应的语句在定义域内为真时，才具有值当其对应的语句在定义域内为真时，才具有值T（真）；而当其对应的语句在定义域内为假时，该真）；而当其对应的语句在定义域内为假时，该原子公式才具有值原子公式才具有值F（假）。因此，（假）。

44、因此，INROOM（ROBOT，r1）具有值）具有值T，而，而INROOM（ROBOT，r2）则具有值）则具有值F。2024/8/2776当一个原子公式含变量符号时，对定义域内实体当一个原子公式含变量符号时，对定义域内实体的变量可能有几个设定。对某几个设定的变量，的变量可能有几个设定。对某几个设定的变量，原子公式取值原子公式取值T；而对另外几个设定的变量，原子；而对另外几个设定的变量，原子公式取值公式取值F。2024/8/2777表示方法 逻辑表示法一阶谓词逻辑是谓词逻辑中最直观的一种逻辑。它以谓一阶谓词逻辑是谓词逻辑中最直观的一种逻辑。它以谓词形式来表示动作的主题、客体。客体可以多个。词形式

45、来表示动作的主题、客体。客体可以多个。如：张三与李四打网球（如：张三与李四打网球（ZhangandLiplaytennis），可写为：），可写为：play(Zhang,Li,tennis)这里谓词是这里谓词是play，动词主体是，动词主体是Zhang和和Li，而客体是，而客体是tennis。谓词逻辑规范表达式：谓词逻辑规范表达式：P(x1,x2,x3,)，这里这里P是谓词是谓词,xi是主体与客体。是主体与客体。2024/8/2778表示方法 逻辑表示法谓词比命题更加细致地刻画知识：谓词比命题更加细致地刻画知识：表达能力强表达能力强如：北京是个城市，如：北京是个城市，City(x)把城市这个概念

46、分割出来。把把城市这个概念分割出来。把“城市城市”与与“北京北京”两个概念连接在一起，而且说明两个概念连接在一起，而且说明“北京北京”是是“城市城市”的子概念。（有层）的子概念。（有层）谓词可以代表变化的情况谓词可以代表变化的情况如：如：City(北京北京),真。真。City(煤球煤球)，假，假在不同的知识之间建立联系在不同的知识之间建立联系.2024/8/2779表示方法 逻辑表示法在不同的知识之间建立联系在不同的知识之间建立联系如：如：Human(x)Lawed(x)，人人都受法律管制，人人都受法律管制，x是同一个人。是同一个人。Commit(x)Punished(x)，x不一定是人也可以

47、是动物。不一定是人也可以是动物。而，而，Human(x)Lawed(x)commit(x)Punished(x)，意为如果由于某个意为如果由于某个x是人而受法律管制，则这个人犯是人而受法律管制，则这个人犯了罪就一定要受到惩罚了罪就一定要受到惩罚。2024/8/2780表示方法 逻辑表示法谓词逻辑法是应用最广的方法之一，其原因是：谓词逻辑法是应用最广的方法之一，其原因是：谓词逻辑与数据库，特别是关系数据库就有密切的关系。在谓词逻辑与数据库，特别是关系数据库就有密切的关系。在关系数据库中，逻辑代数表达式是谓词表达式之一。因此，关系数据库中，逻辑代数表达式是谓词表达式之一。因此，如果采用谓词逻辑作为

48、系统的理论背景，则可将数据库系统如果采用谓词逻辑作为系统的理论背景，则可将数据库系统扩展改造成知识库。扩展改造成知识库。一阶谓词逻辑具有完备的逻辑推理算法。如果对逻辑的某些一阶谓词逻辑具有完备的逻辑推理算法。如果对逻辑的某些外延扩展后，则可把大部分的知识表达成一阶谓词逻辑的形外延扩展后，则可把大部分的知识表达成一阶谓词逻辑的形式。（知识易表达）式。（知识易表达）.2024/8/2781表示方法 逻辑表示法谓词逻辑法是应用最广的方法之一，其原因是：谓词逻辑法是应用最广的方法之一，其原因是：.谓词逻辑本身具有比较扎实的数学基础，知识的表达方式决谓词逻辑本身具有比较扎实的数学基础，知识的表达方式决定

49、了系统的主要结构。因此，对知识表达方式的严密科学性定了系统的主要结构。因此，对知识表达方式的严密科学性要求就比较容易得到满足。这样对形式理论的扩展导致了整要求就比较容易得到满足。这样对形式理论的扩展导致了整个系统框架的发展。个系统框架的发展。逻辑推理是公理集合中演绎而得出结论的过程。由于逻辑及逻辑推理是公理集合中演绎而得出结论的过程。由于逻辑及形式系统具有的重要性质，可以保证知识库中新旧知识在逻形式系统具有的重要性质，可以保证知识库中新旧知识在逻辑上的一致性（或通过相应的一套处理过程检验）、和所演辑上的一致性（或通过相应的一套处理过程检验）、和所演绎出来的结论的正确性。而其它的表示方法在这点上

50、还不能绎出来的结论的正确性。而其它的表示方法在这点上还不能与其相比。与其相比。2024/8/2782表示方法 逻辑表示法为此逻辑表示法在实际人工智能系统上得到应用。为此逻辑表示法在实际人工智能系统上得到应用。存在问题存在问题：谓词表示越细，推理越慢、效率越低，但表示清谓词表示越细，推理越慢、效率越低，但表示清楚。实际中是要折衷的。楚。实际中是要折衷的。2024/8/2783置换与合一2024/8/2784置换置换置换是形如是形如t1/v1，.，tn/vn的一个有限集。其中的一个有限集。其中vi是变是变量，而量，而ti是不同于是不同于vi的项（常量、变量、函数），且的项（常量、变量、函数），且v

51、ivj（ij），），i，j=1，2，.，n。假元推理假元推理，就是由合适公式，就是由合适公式W W1 1和和W W1 1WW2 2产生合适公式产生合适公式W W2 2的运算。的运算。全称化推理全称化推理，是由合适公式，是由合适公式( ( x)W(x)x)W(x)产生合适公式产生合适公式W(A)W(A)，其中，其中A A为任意常量符号。为任意常量符号。一个表达式的一个表达式的置换置换就是在该表达式中用置换项置换变量。就是在该表达式中用置换项置换变量。一般说来，置换是可结合的，但置换是不可交换的。一般说来，置换是可结合的，但置换是不可交换的。2024/8/2785置换例例1：表达式：表达式Px，f

52、（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），），B2024/8/2786合一寻找项对变量的置换，以使两表达式一致，叫做寻找项对变量的置换，以使两表达式一致，叫做合一合一(uni(unification)fication)。如果一个置换。如果一个置换s s作用于表达式集作

53、用于表达式集EiEi的每个的每个元素，则用元素，则用EiEis s来表示置换例的集。来表示置换例的集。称表达式集称表达式集EiEi是是可合一的可合一的，如果存在一个置换，如果存在一个置换s s使得使得：E1s=E2s=E3s=E1s=E2s=E3s=那么称此那么称此s s为为EiEi的合一者的合一者，因为，因为s s的的作用是使集合作用是使集合EiEi成为单一形式。成为单一形式。2024/8/2787合一例例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

54、如果如果s是的任一合一者，有存在某个是的任一合一者，有存在某个s，使得，使得Eis=Eis成立成立,则称则称为的最通用为的最通用(最一般最一般)的合一者的合一者,记为记为mgu.如上例如上例s是的一个合一者，但不是最简单的合一者，其是的一个合一者，但不是最简单的合一者，其最简单的合一者为最简单的合一者为=B/y2024/8/2788分歧集设有一非空有限公式集设有一非空有限公式集F=F1，F2，Fn,从从F中个公式的第一符号同时向右比较中个公式的第一符号同时向右比较,直到直到发现第一个彼此不仅、不尽相同的符号为止发现第一个彼此不仅、不尽相同的符号为止,从从F的各个公式中取出那些以第一个不一致符号

55、开始的各个公式中取出那些以第一个不一致符号开始的最大的子表达式为元素的最大的子表达式为元素,组成一个集合组成一个集合D,称为称为F的的分歧集分歧集.2024/8/2789合一算法合一算法合一算法：设：设F非空集合有限表达集合非空集合有限表达集合,则可按下列步骤则可按下列步骤求其求其mgu：置置k=0，Fk=F，k=（空置换，不含元素的置换）（空置换，不含元素的置换）若若Fk只含有一个表达式，则算法停止，只含有一个表达式，则算法停止，k=mgu。找出找出Fk的分歧集的分歧集Dk。若若Dk中存在元素中存在元素ak和和tk，其中，其中ak是变元，是变元，tk是项目，且是项目，且ak不在不在tk中出现

56、，则置：中出现，则置：k+1=k，Fk+1=Fktk/ak，k=k+1，转步骤（，转步骤（2）算法停止，算法停止，F的的mgu不存在。不存在。2024/8/2790合一算法举例例例3求公式集求公式集F=P(a,x,f(g(y),P(z,h(z,u),f(u)的最一般合一者的最一般合一者2024/8/2791合一算法举例（续）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不是单一表达式，有不是单

57、一表达式，有D1=x,h(a,u)2=1h(a,u)/x=a/z,h(a,u)/xF2=F1h(a,u)/x=P(a,h(a,u),f(g(y),P(a,h(a,u),f(u)2024/8/2792合一算法举例（续）K=2:F2不是单一表达式不是单一表达式D2=g(y),u3=2g(y)/u=a/z,h(a,g(y),g(y)/uF3=F2g(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的最一般合一者的最一般合一者2024/8/2793注意注意：1.在合式公式中，连接词的优先级别是在合式公式中，

58、连接词的优先级别是: ,2.位于量词后面的单个谓词或用括号括起来的合式公式称为量词辖域，辖域内与量位于量词后面的单个谓词或用括号括起来的合式公式称为量词辖域，辖域内与量词中同名变元称为约束变元，不受约束的变元称为自由变元。词中同名变元称为约束变元，不受约束的变元称为自由变元。如：如：( x)(P(x,y)Q(x,y)R(x,y)3.在谓词公式中，变元的名字是无关紧要的，可以把一个名字换成另一个名字，但在谓词公式中，变元的名字是无关紧要的，可以把一个名字换成另一个名字，但必须注意：必须注意：当对量词辖域内的约束变元更名时，必须把同名的约束变元统一改成相同的名字当对量词辖域内的约束变元更名时，必须

59、把同名的约束变元统一改成相同的名字，且不能与辖域内的自由变元同名；，且不能与辖域内的自由变元同名；当对量词辖域内的自由变元改名时，不能改成与约束变元相同的名字。当对量词辖域内的自由变元改名时，不能改成与约束变元相同的名字。2024/8/2794谓词逻辑是一种形式语言，也是到目前为止能够表达人谓词逻辑是一种形式语言，也是到目前为止能够表达人类思维活动规律的一种最精确的语言，它与人们的自然类思维活动规律的一种最精确的语言，它与人们的自然语言比较接近，又可方便地存储到计算机中去，并被精语言比较接近，又可方便地存储到计算机中去，并被精确地处理。因此，它成为最早应用于人工智能中表示知确地处理。因此，它成

60、为最早应用于人工智能中表示知识的一种逻辑。识的一种逻辑。知识的一阶谓词逻辑表示2024/8/2795谓词逻辑适合于表示事物的状态、属性、概念等事实性的谓词逻辑适合于表示事物的状态、属性、概念等事实性的知识，也可以用来表示事物间确定的因果关系，即规则。知识，也可以用来表示事物间确定的因果关系，即规则。事实通常用合式公式的事实通常用合式公式的“与与/或或”形表示（用合取符号形表示（用合取符号及析取符及析取符号号连接起来的公式）。连接起来的公式）。规则通常用蕴涵式规则通常用蕴涵式表示。表示。用谓词公式（合式公式）表示知识时，需要首先定义谓词用谓词公式（合式公式）表示知识时，需要首先定义谓词，指出每个

61、谓词的确切含义，然后再用连接词把有关的谓，指出每个谓词的确切含义，然后再用连接词把有关的谓词连接起来，形成一个谓词公式表达一个完整的含义。词连接起来，形成一个谓词公式表达一个完整的含义。2024/8/2796 例例1 有下列知识：有下列知识： 刘欢比他父亲出名。刘欢比他父亲出名。高扬是计算机系的一名学生，但他不喜欢编程序。高扬是计算机系的一名学生，但他不喜欢编程序。人人爱劳动。人人爱劳动。 为了用谓词公式表示上述知识，首先需要定义谓词：为了用谓词公式表示上述知识，首先需要定义谓词：Bigger(x,y): x 比比 y 出名。出名。Computer(x): x 是计算机系的学生。是计算机系的学

62、生。Like(x,y): x 喜欢喜欢 y 。Love(x,y): x 热爱热爱 y。Man(x): x 是人。是人。然后用谓词公式把上述知识表示为：然后用谓词公式把上述知识表示为：Bigger（Liuhong , father(Liuhong)Computer(Gaoyang) Like(Gaoyang , programing) ( x) (Man(x) Love(x, labour)2024/8/2797例例2 2 设有下列知识设有下列知识自然数都是大于零的整数自然数都是大于零的整数所有整数不是偶数就是奇数所有整数不是偶数就是奇数偶数除以偶数除以2 2是整数是整数首先定义谓词如下：首先定

63、义谓词如下：n(x):xn(x):x是自然数是自然数I(x):xI(x):x是整数是整数E(x):xE(x):x是偶数是偶数O(x):xO(x):x是奇数是奇数GZ(x):xGZ(x):x大于零大于零另外用函数另外用函数S(x)S(x)表示表示x x除以除以2.2.此时，上述知识可用谓词公式分别表示为：此时，上述知识可用谓词公式分别表示为：( ( x)x)（n(x)n(x)GZ(x)I(x)GZ(x)I(x)）( ( x) (I(x)x) (I(x)E(x) O(x)E(x) O(x)( ( x) (E(x)x) (E(x)I(s(x)I(s(x)2024/8/2798例例3. 3. 设在房内

64、设在房内c c处有一机器人，在处有一机器人，在a a及及b b处各有一张桌子，处各有一张桌子，a a桌上有一个盒子，为了让桌上有一个盒子，为了让机器人从机器人从c c处出发把盒子从处出发把盒子从a a处拿到处拿到b b处的桌上，然后再回到处的桌上，然后再回到c c处，需要制定相应处，需要制定相应的行动规划。下面用一阶谓词逻辑描述机器人的行动过程。的行动规划。下面用一阶谓词逻辑描述机器人的行动过程。该例子中，不仅要用谓词表示事物的状态、位置，还要表示其行动。该例子中，不仅要用谓词表示事物的状态、位置，还要表示其行动。cab设相关谓词的定义如下：设相关谓词的定义如下： table(x):xtabl

65、e(x):x是桌子是桌子 empty(y):yempty(y):y手中是空的手中是空的 at(yat(y，z)z)：y y在在z z的附近的附近 holds(y,w):yholds(y,w):y拿着拿着w w on(w,x):w on(w,x):w在在x x的上面的上面 其中，其中，x x的个体域是的个体域是a,b; a,b; y y的个体域是的个体域是robot; robot; z z的个体域是的个体域是a,b,c;a,b,c; w w的个体域是的个体域是boxbox2024/8/2799问题的初始状态是：问题的初始状态是：at(robot,c)empty(robot)on(box,a)ta

66、ble(a)table(b)问题的目标状态是：问题的目标状态是：at(robot,c)empty(robot)on(box,b)table(a)table(b)机机器器人人的的目目标标是是把把问问题题的的初初始始状状态态转转化化为为目目标标状状态态，其其间间它它必必须须完完成成一一系列的操作。系列的操作。cab2024/8/27100操作一般可以分为操作一般可以分为条件条件和和动作动作两部分。两部分。条件条件可以很容易的用谓词公式表示，可以很容易的用谓词公式表示，动动作作可可以以通通过过动动作作前前后后的的状状态态变变化化表表示示出出来来，即即只只要要指指出出动动作作后后应应从从动动作作前前的

67、的状态中删去和增加什么谓词就描述了相应的动作。状态中删去和增加什么谓词就描述了相应的动作。机器人为了把盒子从机器人为了把盒子从a处拿到处拿到b处，应执行如下三个操作：处，应执行如下三个操作：goto(x,y):从从x处走到处走到b处；处；pick_up(x):在在x处拿起盒子；处拿起盒子；set_done(x):在在x处放下盒子。处放下盒子。这三个操作分别用条件和动作表示如下：这三个操作分别用条件和动作表示如下：1.Goto(x,y)条件：条件：at(robot,x)动作动作删除：删除：at(robot,x)增加：增加：at(robot,y)2.Pick_up(x)条件：条件：on(box,x

68、)table(x)empty(robot)动作动作删除：删除：empty(robot)on(box,x)增加增加:holds(robot,box)2024/8/271013.Set_down(x)条件：条件：at(robot,x)table(x)holds(robot,box)动作动作删除：删除：holds(robot,box)增加：增加：empty(robot)on(box,x)操作步骤：操作步骤：机机器器人人在在执执行行每每一一个个操操作作前前，总总要要先先检检查查当当前前状状态态是是否否可可使使所所要要求求的的条条件件得得到到满满足足。若能满足，就执行相应的操作，否则就检查下一个操作所要

69、求的条件。若能满足，就执行相应的操作，否则就检查下一个操作所要求的条件。所所谓谓检检查查当当前前状状态态是是否否满满足足所所要要求求的的条条件件，其其实实是是一一个个定定理理证证明明的的过过程程，即即证证明明当当前前状态是否蕴含操作所要求的条件，若蕴含表示当前所要求的条件得到了满足。状态是否蕴含操作所要求的条件，若蕴含表示当前所要求的条件得到了满足。机器人行动规划问题的求解过程如下：机器人行动规划问题的求解过程如下：( (其中，在检查条件的满足性时要进行变量的代换。其中，在检查条件的满足性时要进行变量的代换。) )2024/8/27102At(robot,c)Empty(robot) 状态1(

70、初始状态)On(box,a) 用c代换xTable(a) 用a代换yTable(b)goto(x,y)At(robot,a)Empty(robot) 状态2On(box,a) 用a代换xTable(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代换代换xTab

71、le(a)用用c代换代换yTable(b) goto(x,y)At(robot,c)empty(robot)状态状态6on(box,b)(目标状态目标状态)Table(a)Table(b)cab2024/8/27103自然性：自然性：符合人类对问题的直觉理解；符合人类对问题的直觉理解；描述性：描述性：表示与知识分离；表示与知识分离；精确性：精确性：只有只有“真与假真与假”的值；的值；严密性：严密性：谓词逻辑具有严格的形式定义以及推理规则；谓词逻辑具有严格的形式定义以及推理规则；容易实现：容易实现：用谓词逻辑表示的知识可以比较容易地转换为计算机内部形用谓词逻辑表示的知识可以比较容易地转换为计算机

72、内部形式，易于模块化，便于对知识的增加、修改、删除；式，易于模块化，便于对知识的增加、修改、删除；不能表示不确定的知识；不能表示不确定的知识；组合爆炸：组合爆炸：不易表示启发式知识，当状态空间大时，当前数据库与知识不易表示启发式知识，当状态空间大时，当前数据库与知识库中操作的匹配以及操作层列的确定会出现时空上的膨胀。库中操作的匹配以及操作层列的确定会出现时空上的膨胀。效率低。效率低。谓词表示的特性2024/8/27104产生式规则系统表示1.Introduction产生式最早由产生式最早由P.Post于于1943年提出，用于构造年提出，用于构造Post机计算模型；机计算模型；1972年年A.N

73、ewell和和H.A.Simon在研究人类的认识模型中提出了在研究人类的认识模型中提出了Rule-Based产生式方法及规则表示模式；产生式方法及规则表示模式；Rule-Based的表示法是目前应用最为普遍的一种。的表示法是目前应用最为普遍的一种。产生式通常用于表示具有因果关系的知识。产生式通常用于表示具有因果关系的知识。2.产生式规则的基本形式产生式规则的基本形式基本形式：基本形式：PP QQ，或者或者IfPthenQIfPthenQ其其中中，P P是是产产生生式式的的前前提提，用用于于指指出出该该产产生生式式是是否否可可用用的的条条件件；Q Q是是一一组组结结论论或或操操作作，用用于于指指

74、出出当当前前题题P P所所指指示示的的条条件件被被满满足足时时，应应该该得得出出的的结结论论和和应应该该执执行行的的操作。操作。整整个个产产生生式式的的含含义义是是：如如果果前前提提P P所所指指示示的的条条件件被被满满足足时时，则则可可得得出出结结论论Q Q或或者者执执行行Q Q所规定的操作。所规定的操作。2024/8/27105例如例如规则规则1：if该动物有羽毛该动物有羽毛then该动物是鸟该动物是鸟规则规则2：if该动物是鸟该动物是鸟and有长脖子有长脖子and有长腿有长腿and不会飞不会飞then该动物是鸵鸟该动物是鸵鸟注意：注意： 谓词逻辑中的蕴含式与产生式的基本形式有相同的形式，

75、其实蕴含式只是产谓词逻辑中的蕴含式与产生式的基本形式有相同的形式，其实蕴含式只是产 生式的一种特殊情况，理由有二生式的一种特殊情况，理由有二： (1)(1)蕴含式只能表示精确知识，而产生式还可以表示不精确知识。蕴含式只能表示精确知识，而产生式还可以表示不精确知识。 例如例如 在疾病诊断专家系统中的一条产生式：在疾病诊断专家系统中的一条产生式： if if 本微生物的染色斑是革兰氏阴性本微生物的染色斑是革兰氏阴性 本微生物的形状呈杆状本微生物的形状呈杆状 病人是中间宿主病人是中间宿主 then then 该微生物是绿农杆菌，置信度为该微生物是绿农杆菌，置信度为0.60.6 它表示当前条件都被满足

76、时，结论的可相信的程度为它表示当前条件都被满足时，结论的可相信的程度为0.60.62024/8/27106(2) (2) 蕴含式只能精确匹配，而产生式可以是不精确匹配。蕴含式只能精确匹配，而产生式可以是不精确匹配。 用产生式表示的知识系统中，决定一条知识是否可用的方法是检查当前是用产生式表示的知识系统中，决定一条知识是否可用的方法是检查当前是 否有已知事实可与前提所规定的条件匹配，而且匹配可以是精确的也可以否有已知事实可与前提所规定的条件匹配，而且匹配可以是精确的也可以 是不精确的，只要按照某种算法求出的相似度落在某个预定的范围内就认是不精确的，只要按照某种算法求出的相似度落在某个预定的范围内

77、就认 为是可匹配的，但对谓词逻辑的蕴含式来说，其匹配总要求是精确的。为是可匹配的，但对谓词逻辑的蕴含式来说，其匹配总要求是精确的。 由于产生式与蕴含式存在这些区别，导致它们在处理方法及应用等由于产生式与蕴含式存在这些区别，导致它们在处理方法及应用等 方面都有较大差别。方面都有较大差别。 下面给出产生式的严格意义上的形式描述（下面给出产生式的严格意义上的形式描述（BNFBNF描述描述) )及语义：及语义： := 前提前提 结论结论 := 简单条件简单条件 符合条件符合条件 := 事实事实 操作操作 := 简单条件简单条件and and 简单条件简单条件and (and (简单条件简单条件) )

78、简单条件简单条件or or 简单条件简单条件or (or (简单条件简单条件) ) := 操作名操作名 （ 变元变元, ,)2024/8/271073 3产生式系统产生式系统 把一组产生式放在一起，让他们互相配合，协同作用，一个产生式生成的结把一组产生式放在一起，让他们互相配合，协同作用，一个产生式生成的结论可以供另一个产生式作为已知事实使用，以求得问题的解决，这样的系统称为论可以供另一个产生式作为已知事实使用，以求得问题的解决，这样的系统称为产生式系统。一般说来，一个产生式系统由以下三个基本部分组成：产生式系统。一般说来，一个产生式系统由以下三个基本部分组成： 控制系统控制系统 规则库规则库

79、综合数据库综合数据库(1)规则库规则库 用于描述相应领域中的知识的产生式集合称为规则库。用于描述相应领域中的知识的产生式集合称为规则库。用于描述相应领域中的知识的产生式集合称为规则库。用于描述相应领域中的知识的产生式集合称为规则库。知识是否完整，一致，表达是否准确灵活，对知识的组织是否合理，不知识是否完整，一致，表达是否准确灵活，对知识的组织是否合理，不仅将直接影响到系统的性能，而且还会影响到系统的运行效率，因此对规仅将直接影响到系统的性能，而且还会影响到系统的运行效率，因此对规则库的设计和组织应给与足够的重视。则库的设计和组织应给与足够的重视。2024/8/27108建立规则库时，应注意以下

80、问题：建立规则库时，应注意以下问题：建立规则库时，应注意以下问题：建立规则库时，应注意以下问题：(1) (1) 有效的表达领域内的过程性知识。有效的表达领域内的过程性知识。 例例: : 动物识别系统的规则库动物识别系统的规则库 这是一个用以识别虎这是一个用以识别虎 ，金钱豹，斑马，长颈鹿，企鹅，鸵鸟，信天翁等七，金钱豹，斑马，长颈鹿，企鹅，鸵鸟，信天翁等七 种动物的产生式系统。为了实现对这些动物的识别，该系统建立了如下规则库：种动物的产生式系统。为了实现对这些动物的识别，该系统建立了如下规则库： r1: If r1: If 该动物有毛发该动物有毛发 then then 该动物是哺乳动物该动物是

81、哺乳动物 r2: If r2: If 该动物有奶该动物有奶 then then 该动物是哺乳动物该动物是哺乳动物 r3: If r3: If 该动物有羽毛该动物有羽毛 then then 该动物是鸟该动物是鸟 r4: If r4: If 该动物会飞该动物会飞 and and 会下蛋会下蛋 then then 该动物是鸟该动物是鸟 r5: If r5: If 该动物吃肉该动物吃肉 then then 该动物是食肉动物该动物是食肉动物 r6: If r6: If 该动物有犬齿该动物有犬齿 and and 有爪有爪 and and 眼盯前方眼盯前方 then then 该动物是食肉动物该动物是食肉动

82、物 r7: If r7: If 该动物是哺乳动物该动物是哺乳动物 and and 有蹄有蹄 then then 该动物是有蹄类动物该动物是有蹄类动物 r8: If r8: If 该动物是哺乳动物该动物是哺乳动物 and and 是嚼反刍动物是嚼反刍动物 then then 该动物是有蹄类动物该动物是有蹄类动物 r9: If r9: If 该动物是哺乳动物该动物是哺乳动物 and and 是食肉动物是食肉动物 and and 是黄褐色是黄褐色 and and 身上有斑点身上有斑点 then then 该动物是金钱豹该动物是金钱豹 r10: If r10: If 该动物是哺乳动物该动物是哺乳动物

83、and and 是食肉动物是食肉动物 and and 是黄褐色是黄褐色 and and 身上有黑色条纹身上有黑色条纹 then then 该动物是虎该动物是虎2024/8/27109 r11: If r11: If 该动物是有蹄类动物该动物是有蹄类动物 and and 有长脖子有长脖子 and and 有长腿有长腿 and and 身上有暗斑点身上有暗斑点 then then 该动物是长颈鹿该动物是长颈鹿 r12: If r12: If 该动物是有蹄类动物该动物是有蹄类动物 and and 身上有黑色条纹身上有黑色条纹 then then 该动物是斑马该动物是斑马 r13: If r13: I

84、f 该动物是鸟该动物是鸟 and and 有长脖子有长脖子 and and 有长腿有长腿and and 不会飞不会飞 and and 有黑白俩色有黑白俩色 then then 该动物是鸵鸟该动物是鸵鸟 r14: If r14: If 该动物是鸟该动物是鸟 and and 会游泳会游泳 and and 不会飞不会飞 and and 有黑白二色有黑白二色 then then 该动物是企鹅该动物是企鹅 r15: If r15: If 该动物是鸟该动物是鸟 and and 善飞善飞 then then 该动物是信天翁该动物是信天翁 由上述产生式规则可以看出，虽然该系统是用来识别七种动物的，但它并没有由

85、上述产生式规则可以看出，虽然该系统是用来识别七种动物的，但它并没有简单的只设七种规则，而是设计了简单的只设七种规则，而是设计了1515条，首先根据一些比较简单的条件，如有毛发，条，首先根据一些比较简单的条件，如有毛发，会飞等对动物进行比较粗的分类，如分出哺乳动物，鸟等。然后随着条件的增加逐会飞等对动物进行比较粗的分类，如分出哺乳动物，鸟等。然后随着条件的增加逐步缩小分类范围，最后分别给出识别七种动物的规则。步缩小分类范围，最后分别给出识别七种动物的规则。 这样做起码有两种好处这样做起码有两种好处: : (1) (1) 当已知的事实不完全时，虽不能推出最终结论，但可以得到分类的结果；当已知的事实

86、不完全时，虽不能推出最终结论，但可以得到分类的结果； (2) (2) 当需要增加对其他动物的识别时，规则库只需增加关于这些动物个性方面当需要增加对其他动物的识别时，规则库只需增加关于这些动物个性方面 的知识。的知识。如如r9r15一样，而一样，而r1r8可直接利用，这样，就不会增加太多的可直接利用，这样，就不会增加太多的规则。规则。2024/8/27110虎虎长颈鹿长颈鹿黄褐色黄褐色食肉动物食肉动物黑条纹黑条纹长脖子长脖子有蹄类有蹄类长腿长腿有暗斑点有暗斑点有蹄有蹄嚼反刍嚼反刍吃肉吃肉有爪有爪有犬齿有犬齿眼盯前方眼盯前方有毛发有毛发有奶有奶哺乳动物哺乳动物r10r11r7r8r5r6r1r2

87、上述规则很容易形成各种动物的推理链，如虎和长颈鹿。上述规则很容易形成各种动物的推理链，如虎和长颈鹿。上述规则很容易形成各种动物的推理链，如虎和长颈鹿。上述规则很容易形成各种动物的推理链，如虎和长颈鹿。(2) (2) 对知识进行合理的组织与管理。对知识进行合理的组织与管理。 对规则库中的知识进行适当的组织采用合理的结构形式，可使推理避免访问那对规则库中的知识进行适当的组织采用合理的结构形式，可使推理避免访问那 些与当前问题求解无关的知识，从而提高求解问题的效率。些与当前问题求解无关的知识，从而提高求解问题的效率。如：将上述规则集分为两个子集如：将上述规则集分为两个子集r1r2r5r6r7r8r9

88、r10r11r12哺乳动物哺乳动物r3r4r13r14r15鸟鸟在求解过程中，可分别在各自的子集中查找，从而节约搜索时间。在求解过程中，可分别在各自的子集中查找，从而节约搜索时间。2024/8/27111(2) (2) 综合数据库系统综合数据库系统 综合数据库系统又称为事实库，上下文，黑板等。它是一个用于存放问题求解过程中各综合数据库系统又称为事实库，上下文，黑板等。它是一个用于存放问题求解过程中各综合数据库系统又称为事实库，上下文，黑板等。它是一个用于存放问题求解过程中各综合数据库系统又称为事实库，上下文，黑板等。它是一个用于存放问题求解过程中各种当前信息的数据结构，例如问题的初始状态，原始

89、证据，推理中得到的中间结论及最种当前信息的数据结构，例如问题的初始状态，原始证据，推理中得到的中间结论及最种当前信息的数据结构，例如问题的初始状态，原始证据，推理中得到的中间结论及最种当前信息的数据结构，例如问题的初始状态，原始证据，推理中得到的中间结论及最终结论。终结论。终结论。终结论。 当规则库中的某条产生式的前提可与综合数据库中的某些已知事实匹配时，该产生式就当规则库中的某条产生式的前提可与综合数据库中的某些已知事实匹配时，该产生式就被激活，并把用它推出的结论放入综合数据库中，作为后面推理的已知事实。显然，综被激活，并把用它推出的结论放入综合数据库中，作为后面推理的已知事实。显然，综合数

90、据库的内容是在不断变化的，是动态的。综合数据库中的已知事实通常用字符串、合数据库的内容是在不断变化的，是动态的。综合数据库中的已知事实通常用字符串、向量、集合、矩阵、表等数据结构表示。向量、集合、矩阵、表等数据结构表示。 如：在疾病诊断专家系统如：在疾病诊断专家系统(MYCIN)(MYCIN)中，对事实用如下一个四元组来表示：中，对事实用如下一个四元组来表示： （特性（特性 对象对象 值值 可信度因子）可信度因子） “张山大约张山大约2525岁岁”，可用四元组表示如下：，可用四元组表示如下： （age zhangshan 25 0.8age zhangshan 25 0.8）2024/8/27

91、112(3) (3) 控制系统控制系统 控制系统又称为推理机构，由一组程序组成，负责整个产生式系统的运行控制系统又称为推理机构，由一组程序组成，负责整个产生式系统的运行控制系统又称为推理机构，由一组程序组成，负责整个产生式系统的运行控制系统又称为推理机构，由一组程序组成，负责整个产生式系统的运行, , , ,实实实实 现对问题的求解。现对问题的求解。现对问题的求解。现对问题的求解。 它主要作以下几项工作：它主要作以下几项工作： (1) (1) 按一定策略从规则库中选择规则与综合数据库中的已知事实进行匹按一定策略从规则库中选择规则与综合数据库中的已知事实进行匹 (2)(2)匹配成功的规则可能不止

92、一条，这称为发生了冲突。此时，推理机构必须匹配成功的规则可能不止一条，这称为发生了冲突。此时，推理机构必须 调用相应的解决冲突的策略进行消解，以便从中选出一条执行。调用相应的解决冲突的策略进行消解，以便从中选出一条执行。 (3)(3)在执行某一条规则时，如果该规则的右部是一个或多个结论，则把这些结论在执行某一条规则时，如果该规则的右部是一个或多个结论，则把这些结论 加入到综合数据库中；如果该规则的右部是一个或多个操作，则执行这些操加入到综合数据库中；如果该规则的右部是一个或多个操作，则执行这些操 作。作。 (4)(4)对于不确定性知识，在执行每一条规则时还要按照一定算法计算结论的不确定对于不确

93、定性知识，在执行每一条规则时还要按照一定算法计算结论的不确定 性。性。 (5)(5)随时掌握结束产生式系统运行的时机，以便在适当的时候停止系统的运行。随时掌握结束产生式系统运行的时机，以便在适当的时候停止系统的运行。2024/8/27113举例说明产生式系统的求解过程：举例说明产生式系统的求解过程：举例说明产生式系统的求解过程：举例说明产生式系统的求解过程：例例: : 设在综合数据库中存放有下列已知事实：设在综合数据库中存放有下列已知事实： 该动物身上有暗斑点，长脖子，长腿，有奶，有蹄该动物身上有暗斑点，长脖子，长腿，有奶，有蹄 且假设综合数据库中的已知事实与规则库中的知识是从第一条开始，逐条

94、且假设综合数据库中的已知事实与规则库中的知识是从第一条开始，逐条 进行匹配的，进行匹配的， 则推理机构的工作过程如下：则推理机构的工作过程如下： (1) (1) 从规则库中取出第一条规则从规则库中取出第一条规则r r1 1，检查前提条件与综合数据库中的已知事实不匹配；，检查前提条件与综合数据库中的已知事实不匹配； 取第二条规则取第二条规则r r2 2，r r2 2的前提的前提“该动物有奶该动物有奶”与综合数据库中事实匹配，则与综合数据库中事实匹配，则r rr r被执行，其结被执行，其结 论被加入综合数据库中，此时综合数据库中的事实为：论被加入综合数据库中，此时综合数据库中的事实为： 该动物身上

95、有暗斑点，长脖子，长腿，有奶，有蹄，是哺乳动物该动物身上有暗斑点，长脖子，长腿，有奶，有蹄，是哺乳动物 (2) (2) 接着取接着取r3r4r5r6都不匹配，取到都不匹配，取到r7时，匹配成功，则将时，匹配成功，则将r7的结论加入综合数据库：的结论加入综合数据库： 该动物身上有暗斑点该动物身上有暗斑点, ,长脖子长脖子, ,长腿长腿, ,有奶有奶, ,有蹄有蹄, ,是哺乳动物是哺乳动物, ,是有蹄动物是有蹄动物(3) (3) 接着取规则，取到接着取规则，取到r11时，匹配成功，发现其前提条件与综合数据库完全匹配，则确定时，匹配成功，发现其前提条件与综合数据库完全匹配，则确定该动物是：该动物是：

96、长颈鹿长颈鹿至此，问题的求解结束了。至此，问题的求解结束了。2024/8/27114产生式问题的求解问题的一般步骤是：产生式问题的求解问题的一般步骤是：产生式问题的求解问题的一般步骤是：产生式问题的求解问题的一般步骤是：1 1初始化综合数据库，把问题的初始已知事实送入综合数据库中初始化综合数据库，把问题的初始已知事实送入综合数据库中2 2若规则库中存在尚未使用过的规则，而且它的前提可与综合数据库中的已知若规则库中存在尚未使用过的规则，而且它的前提可与综合数据库中的已知事实匹配，则转第事实匹配，则转第3 3步；若不存在这样的事实，则转第步；若不存在这样的事实，则转第5 5步。步。3 3执行当前选

97、中的规则，并对规则作上标记，把该规则执行后得到的结论送入执行当前选中的规则，并对规则作上标记，把该规则执行后得到的结论送入综合数据库中。如果该规则的结论部分指出的是某些操作，则执行这些操作。综合数据库中。如果该规则的结论部分指出的是某些操作，则执行这些操作。4 4检查综合数据库中是否已包含了问题的解，若已包含，则终止问题的求解过检查综合数据库中是否已包含了问题的解，若已包含，则终止问题的求解过程，否则转第程，否则转第2 2步。步。5 5要求用户提供进一步的关于问题的已知事实，若能提供，则转第要求用户提供进一步的关于问题的已知事实，若能提供，则转第2 2步，否则终步，否则终止问题的求解过程。止问

98、题的求解过程。6. 6. 若规则库中不再有未使用的规则，则终止问题的求解过程。若规则库中不再有未使用的规则，则终止问题的求解过程。2024/8/271154. .产生式系统的分类产生式系统的分类 按规则及综合数据库的性质及结构特征进行分类。产生式系统可分为三类：按规则及综合数据库的性质及结构特征进行分类。产生式系统可分为三类： 可交换的产生式系统；可交换的产生式系统；可分解的产生式系统；可分解的产生式系统；可恢复的产生式系统。可恢复的产生式系统。 (1)(1)可交换的产生式系统可交换的产生式系统 如果一个产生式系统对规则的使用次序是可交换的，无论先使用哪一条规则都可以达到如果一个产生式系统对规

99、则的使用次序是可交换的，无论先使用哪一条规则都可以达到目的，即规则的使用次序是无关紧要的，就称这样的产生式系统为可交换的产生式系统。目的，即规则的使用次序是无关紧要的，就称这样的产生式系统为可交换的产生式系统。 (2)(2)可分解的产生式系统可分解的产生式系统 把把一一个个规规模模较较大大的的且且比比较较复复杂杂的的问问题题分分解解为为若若干干个个规规模模较较小小的的且且比比较较简简单单的的子子问问题题，然然后对每个子问题分别进行求解。可分解的产生式系统就是基于这种思想提出来的。后对每个子问题分别进行求解。可分解的产生式系统就是基于这种思想提出来的。 (3)(3)可恢复的产生式系统可恢复的产生

100、式系统 在在求求解解问问题题的的过过程程中中，经经常常要要进进行行回回溯溯，即即当当问问题题求求解解到到某某一一步步骤骤时时发发现现无无法法继继续续下下去去，就撤销在此之前得到的某些结果，恢复到先前的某个状态。，就撤销在此之前得到的某些结果，恢复到先前的某个状态。2024/8/27116 用产生式系统求解问题时，当执行一条规则后，是综合数据库的状态由用产生式系统求解问题时，当执行一条规则后，是综合数据库的状态由DbDbi i变变 化到化到DBDBi+1i+1,如果发现由如果发现由DbDbi+1i+1不能得到问题的解，就需要撤销刚才执行规则所产不能得到问题的解，就需要撤销刚才执行规则所产 生的结果，使综合数据库恢复到先前的状态，然后选用别的规则继续求解。这生的结果，使综合数据库恢复到先前的状态，然后选用别的规则继续求解。这 样的产生式系统谓为可恢复的产生式系统。样的产生式系统谓为可恢复的产生式系统。5.产生式规则的特点产生式规则的特点产生式表示法的优点产生式表示法的优点 优点：优点： 1.1.自然性自然性 2.2.模块性模块性 3.3.有效性有效性 4.4.清晰性清晰性 不足：不足： 1.1.效率不高效率不高 2.2.不能表达具有结构性的知识不能表达具有结构性的知识