人工智能学科体系课件

数理逻辑数理逻辑数理逻辑：用数学方法来研究推理的形式结构和数理逻辑：用数学方法来研究推理的形式结构和推理规律的数学学科推理规律的数学学科与数学其它分支、计算机科学、与数学其它分支、计算机科学、AI、语言学有密、语言学有密切的联系切的联系数理逻辑的内容数理逻辑的内容逻辑演算逻辑演算命题逻辑命题逻辑谓词逻辑谓词逻辑证明论证明论公理集合论公理集合论递归论递归论模型论模型论5/26/20241提纲提纲命题逻辑命题逻辑:客观世界的各种事实客观世界的各种事实一阶谓词逻辑：一阶谓词逻辑：逻辑论证的符逻辑论证的符号化，能够表示复杂的问题（具有号化，能够表示复杂的问题（具有较强的表达能力）较强的表达能力）5/26/20242用形式逻辑（尤其是一阶谓词逻辑）表示知识是用形式逻辑（尤其是一阶谓词逻辑）表示知识是AI研究中提出使用的一种普遍方法。研究中提出使用的一种普遍方法。命题逻辑和谓词逻辑是最先应用于人工智能的两命题逻辑和谓词逻辑是最先应用于人工智能的两种逻辑，谓词逻辑是在命题逻辑基础上发展起来种逻辑，谓词逻辑是在命题逻辑基础上发展起来的，命题逻辑可以看作是谓词逻辑的一种特殊形的，命题逻辑可以看作是谓词逻辑的一种特殊形式。式。5/26/20243一、命题逻辑一、命题逻辑命题命题定义：定义：能够判断真假的陈述句能够判断真假的陈述句真值真值真：正确的判断真：正确的判断;真值真值1,T假：错误的判断假：错误的判断;真值真值0,F例子：例子：2是素数是素数雪是黑色的雪是黑色的3能够被能够被2整除整除地球以外的星球上也有人地球以外的星球上也有人5/26/20244一些不是命题的句子一些不是命题的句子X+y5 X,y未知，真假不定未知，真假不定这朵花多美呀！这朵花多美呀！感叹句感叹句明天下午有会吗？明天下午有会吗？疑问句疑问句请你把门关上！请你把门关上！祈使句祈使句5/26/20245判断是否为命题的方法判断是否为命题的方法陈述句陈述句真值确定真值确定真值是确定的真值是确定的可以不知道可以不知道5/26/20246原子命题与命题符号化原子命题与命题符号化原子命题（简单命题）原子命题（简单命题）不能够再分解的命题不能够再分解的命题命题符号化命题符号化使用小写的字母表示命题使用小写的字母表示命题放在命题的前面放在命题的前面p,q,r,pi,qi,rip:2是素数是素数 真命题真命题q:雪是黑的雪是黑的 2假命题假命题5/26/20247命题常量和命题变量命题常量和命题变量命题常量：其真值是确定的简单命题命题常量：其真值是确定的简单命题命题变量（命题变元）命题变量（命题变元）定义：真值不确定的简单陈述句定义：真值不确定的简单陈述句表示：也用小写字母表示：表示：也用小写字母表示：p,q,r,pi,qi,ri性质：命题变量不是命题性质：命题变量不是命题例子：例子：X+y55/26/20248复合命题复合命题定义：由简单命题用联结词联结而成的命题定义：由简单命题用联结词联结而成的命题例子例子3不是偶数不是偶数2是素数和偶数是素数和偶数林芳学过英语或日语林芳学过英语或日语如果角如果角A和角和角B是对顶角，则角是对顶角，则角A和角和角B相等相等5/26/20249否定、合取联结词否定、合取联结词定义定义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：李平不但聪明，而且用功：李平不但聪明，而且用功p q：李平聪明：李平聪明,但不用功但不用功5/26/202410析取联结词析取联结词 定义定义3：设：设p,q为二命题，复合命题为二命题，复合命题“p或或q”称作称作p和和q的析取式，记做的析取式，记做p q，为析为析取联结词，取联结词，p q为真当且仅当为真当且仅当p和和q中至少中至少有一个为真有一个为真p:李平聪明李平聪明q:李平用功李平用功p q：李平聪明或者用功：李平聪明或者用功p q：李平聪明或者不用功：李平聪明或者不用功5/26/202411蕴涵联结词蕴涵联结词定义定义4：设：设p,q为二命题，复合命题为二命题，复合命题“如果如果p，则，则q”称作称作p和和q的蕴涵式，记做的蕴涵式，记做pq，为蕴涵联结词，为蕴涵联结词，pq为为假当且仅当假当且仅当p为真，为真，q为假为假如果如果pq为真，记做为真，记做pq，称为定理，称为定理与自然语言不一样，蕴涵式的前件和后件可以没有内在联与自然语言不一样，蕴涵式的前件和后件可以没有内在联系系 例如：如果例如：如果224，则太阳从西边出来，则太阳从西边出来蕴涵式的真值表蕴涵式的真值表5/26/202412蕴涵联结词蕴涵联结词将下列命题符号化将下列命题符号化只要不下雨，我就骑自行车上班只要不下雨，我就骑自行车上班只有不下雨，我才骑自行车上班只有不下雨，我才骑自行车上班p:下雨下雨q:骑自行车上班骑自行车上班 pq qp5/26/202413等价联结词等价联结词定义定义5：设：设p,q为二命题，复合命题为二命题，复合命题“p当且仅当当且仅当q”称作称作p和和q的等价式，记做的等价式，记做p q，为等价联结词，为等价联结词，pq为为假当且仅当假当且仅当p与与q的真值不相同的真值不相同与自然语言不一样，等价式的与自然语言不一样，等价式的2个命题可以没有内在联系个命题可以没有内在联系例如：例如：224，当且仅当太阳从西边出来，当且仅当太阳从西边出来蕴涵式的真值表蕴涵式的真值表5/26/202414逻辑联结词的优先级逻辑联结词的优先级5/26/202415命题符号化的例子命题符号化的例子分析出简单命题，将之符号化分析出简单命题，将之符号化用联结词将简单命题联结起来，形成复合命题的用联结词将简单命题联结起来，形成复合命题的符号化符号化例子：例子：1：小王是游泳冠军或是百米赛跑冠军：小王是游泳冠军或是百米赛跑冠军2：如果我上街，我就去书店看看，除非我很累：如果我上街，我就去书店看看，除非我很累1：p q,其中：其中：q:小王是游泳冠军；小王是游泳冠军；q:小王是百米赛小王是百米赛跑冠军跑冠军2：r(pq),其中其中p:我上街我上街,q:我去书店看看我去书店看看,r:我很累我很累5/26/202416命题公式及分类命题公式及分类复合命题：复合命题：p,p q,p q,pq,pq如果如果p,q为命题常量，这些复合命题为命题为命题常量，这些复合命题为命题如果如果p,q为命题变量，这些复合命题为命题公为命题变量，这些复合命题为命题公式式命题公式：由命题常量、命题变量、逻辑命题公式：由命题常量、命题变量、逻辑联结词、括号等构成的有效字符串联结词、括号等构成的有效字符串5/26/202417命题公式及分类命题公式及分类定义定义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组成的符号串才是合式公式组成的符号串才是合式公式命题逻辑下的合式公式：命题公式，公式命题逻辑下的合式公式：命题公式，公式例子：例子：q qvr5/26/202418公式的层次公式的层次定义定义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 B C,其中其中B,C的层次同的层次同25/26/202419命题公式的赋值或解释命题公式的赋值或解释命题公式中命题常项和变项，不是命题，只有对命题公式中命题常项和变项，不是命题，只有对命题公式中的所有命题变项进行赋值，公式的真命题公式中的所有命题变项进行赋值，公式的真值才能够确定下来，才能够变成命题值才能够确定下来，才能够变成命题定义定义8：设设A为一个命题公式，为一个命题公式，p1,p2,pn为出现在为出现在A中的所中的所有命题变项，给指定一组真值，称为对有命题变项，给指定一组真值，称为对A的一个的一个赋值赋值或或解释解释。如果指定的一组值使。如果指定的一组值使A的值为真，则称这组的值为真，则称这组值为成真赋值，如果指定的一组值使值为成真赋值，如果指定的一组值使A的值为假，则的值为假，则称这组值为成假赋值。称这组值为成假赋值。5/26/202420公式的真值表公式的真值表真值表：含有真值表：含有n个变项的公式，其赋值有个变项的公式，其赋值有2n个，个，将每一个赋值及公式在此赋值下的真值构成的表将每一个赋值及公式在此赋值下的真值构成的表例子例子:(p(pq)q5/26/202421公式的性质公式的性质定义定义9设设A为一个命题公式为一个命题公式若若A在它的各种赋值下取值均为真，则称在它的各种赋值下取值均为真，则称A为重言式或为重言式或永真式（真值表最后一列全为永真式（真值表最后一列全为1）若若A在它的各种赋值下取值均为假，则称在它的各种赋值下取值均为假，则称A为矛盾式或为矛盾式或永假式（真值表最后一列全为永假式（真值表最后一列全为0）若若A至少存在一组赋值是成真赋值，则称至少存在一组赋值是成真赋值，则称A为可满足式为可满足式（真值表最后一列有（真值表最后一列有1）5/26/202422等值演算等值演算判断公式性质的办法判断公式性质的办法真值表真值表等值演算将之演算成简单形式，判断其性质等值演算将之演算成简单形式，判断其性质定义定义10设设A,B为为2个命题公式，若等价式个命题公式，若等价式A B是重言式，则是重言式，则称称A与与B是等值的，记做是等值的，记做A B：不是逻辑联结词，一个等值的记号，不能够用：不是逻辑联结词，一个等值的记号，不能够用（数值上的相等）代替（数值上的相等）代替等值本质上是指：公式等值本质上是指：公式A和和B在任何解释下都相等在任何解释下都相等5/26/202423逻辑等值式逻辑等值式5/26/202424逻辑等值式逻辑等值式5/26/202425逻辑等值式逻辑等值式5/26/202426等值演算等值演算利用等值式，将一个公式变换成另外一种形式的利用等值式，将一个公式变换成另外一种形式的过程过程例子例子5/26/202427等值演算等值演算5/26/202428等值演算等值演算5/26/202429简单析取式及简单合取式简单析取式及简单合取式简单析取式和简单合取式简单析取式和简单合取式定义定义10：仅由有限个命题变项或其否定构成的析取式称：仅由有限个命题变项或其否定构成的析取式称为，简单析取式；仅由有限个命题变项或其否定构成为，简单析取式；仅由有限个命题变项或其否定构成的合取式称为，简单合取式的合取式称为，简单合取式例子：例子：简单析取式：简单析取式：p,q,p q,p q,p q r简单合取式：简单合取式：p,q,p q,p q,p q r5/26/202430合取范式合取范式定义定义11：仅有有限个简单析取式构成的合取式称为合取仅有有限个简单析取式构成的合取式称为合取范式范式A=A1 A2 An其中其中A1，A2，An为简单析取式为简单析取式例子：例子：A=(p q r)(p q)(q q)任何公式都有与其对应的合取范式任何公式都有与其对应的合取范式5/26/202431化成合取范式的步骤化成合取范式的步骤1.消去对消去对，来说冗余的联结词来说冗余的联结词2.否定联结词的消除或内移否定联结词的消除或内移3.利用分配率利用分配率5/26/202432合取范式合取范式原子：命题常项或变项原子：命题常项或变项文字：原子或原子的否定文字：原子或原子的否定 子句：文字的析取子句：文字的析取合取范式：子句的合取合取范式：子句的合取子句集：合取范式的集合表示子句集：合取范式的集合表示每一个合取项作为集合的元素每一个合取项作为集合的元素元素之间的关系为合取元素之间的关系为合取5/26/202433命题逻辑的问题命题逻辑的问题命题作为命题演算的基本单位，不再分解命题作为命题演算的基本单位，不再分解无法研究命题内部的结构和命题之间的联系无法研究命题内部的结构和命题之间的联系例子：苏格拉底三段论例子：苏格拉底三段论p:凡人都是要死的凡人都是要死的q:苏格拉底是人苏格拉底是人r:苏格拉底是要死的苏格拉底是要死的命题符号化：命题符号化：(p q)r 真值不定！真值不定！解决问题的办法解决问题的办法将命题进一步分解成：个体词，谓词和量词等将命题进一步分解成：个体词，谓词和量词等研究它们的形式结构和逻辑关系，总结出正确地推理研究它们的形式结构和逻辑关系，总结出正确地推理形式和规则形式和规则一阶谓词逻辑一阶谓词逻辑5/26/202434二、一阶谓词逻辑二、一阶谓词逻辑简单命题的分解：个体词和谓词简单命题的分解：个体词和谓词个体词个体词指可以独立存在的客体指可以独立存在的客体可以表示具体的事物：李明，玫瑰花，自然数可以表示具体的事物：李明，玫瑰花，自然数可以表示抽象的概念：思想可以表示抽象的概念：思想谓词谓词用于刻画个体词的用于刻画个体词的性质性质或个体词之间的或个体词之间的关系关系的词的词 2是有理数，是有理数，是有理数是有理数 小李比小王高，小李比小王高，比比高高5/26/202435个体常项、个体变项和个体域个体常项、个体变项和个体域个体常项个体常项定义：表示具体或特定的词定义：表示具体或特定的词表示：小写的英文字母表示：小写的英文字母a,b,c,a,b,c,表示表示个体确定下来个体确定下来个体变项个体变项定义：泛指的个体的词定义：泛指的个体的词表示：小写的英文字母表示：小写的英文字母x,y,z,x,y,z,表示表示个体没有确定下来个体没有确定下来个体域个体域个体变项的取值范围个体变项的取值范围可以是一个有限的集合可以是一个有限的集合a,b,c也可以是一个无限的集合：全体自然数，全体实数也可以是一个无限的集合：全体自然数，全体实数全总个体域：宇宙间的一切事物组成的个体域全总个体域：宇宙间的一切事物组成的个体域5/26/202436谓词常项、谓词变项谓词常项、谓词变项谓词常项谓词常项定义：表示具体性质或关系的词定义：表示具体性质或关系的词表示：大写英文字母表示：大写英文字母F,G,H,谓词变项谓词变项定义：表示抽象或泛指的性质或关系的词定义：表示抽象或泛指的性质或关系的词表示：大写英文字母表示：大写英文字母F,G,H,F(x):x很高，很高，x是无理数是无理数,;L(x,y):x比比y学习好学习好,x比比y大大,;5/26/202437谓词的元数谓词的元数谓词的元数：谓词中包含的个体词的个数谓词的元数：谓词中包含的个体词的个数n元谓词：包含有元谓词：包含有n个个体词的谓词个个体词的谓词F(x)一元谓词一元谓词L(x,y)二元谓词二元谓词有时有时n元谓词：包含有元谓词：包含有n个个体变项的谓词个个体变项的谓词F(a):0元谓词元谓词L(x,a):1元谓词元谓词5/26/202438谓词符号化的例子谓词符号化的例子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)5/26/202439全称量词和存在量词全称量词和存在量词谓词符号化下面的句子谓词符号化下面的句子所有的人都是要死的所有的人都是要死的有的人活到有的人活到100岁以上岁以上量词：表示数量的词量词：表示数量的词全称量词全称量词对应于日常语言中的对应于日常语言中的“一切一切”，“任意的任意的”，“所有的所有的”表示：表示：xF(x）5/26/202440全称量词和存在量词全称量词和存在量词存在量词存在量词对应于日常语言中的对应于日常语言中的“存在着存在着”，“有一个有一个”，“至少一个至少一个”等词等词表示：表示：xF(x)5/26/202441谓词符号化的例子谓词符号化的例子所有的人都是要死的所有的人都是要死的定义谓词：定义谓词：F(x），），x是要死的是要死的个体域为全体人类时：个体域为全体人类时：xF(x）全总个体域全总个体域(没有申明个体域没有申明个体域)：x(M(x)F(x)特性谓词：特性谓词：M(x)有的人活到有的人活到100岁以上岁以上定义谓词：定义谓词：G(x）x活到活到100岁以上岁以上个体域为全体人类时：个体域为全体人类时：xG(x）全总个体域全总个体域(没有申明个体域没有申明个体域)：x(M(x)G(x)5/26/202442量词使用的注意事项量词使用的注意事项1.不同的个体域，符号化的形式可能不一样不同的个体域，符号化的形式可能不一样2.如果没有给出个体域，都应以全总个体域为个体如果没有给出个体域，都应以全总个体域为个体域域3.引入引入特性谓词特性谓词后，使用全称量词和存在量词符号后，使用全称量词和存在量词符号化的形式不一样化的形式不一样4.个体词和谓词的涵义确定之后，个体词和谓词的涵义确定之后，n元谓词转化成元谓词转化成命题至少要命题至少要n个量词个量词5/26/202443量词使用的注意事项量词使用的注意事项5.当个体域为有限集时，当个体域为有限集时，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)5/26/202444一阶谓词逻辑中的命题符号化一阶谓词逻辑中的命题符号化凡是有理数都可以表示成分数凡是有理数都可以表示成分数不用引入特性谓词的情况不用引入特性谓词的情况 xF(x)引入特性谓词的情况引入特性谓词的情况 x(R(x)F(x)5/26/202445一阶谓词逻辑中的命题符号化一阶谓词逻辑中的命题符号化没有不犯错误的人没有不犯错误的人没有指定个体域，以全总个体域作为个体域没有指定个体域，以全总个体域作为个体域谓词：谓词：M(x)x是人；是人；F(x):x犯错误犯错误 x(M(x)F(x)在北京工作的人未必是北京人在北京工作的人未必是北京人F(x):x在北京工作；在北京工作；G(x):x是北京人是北京人 x(F(x)G(x)5/26/202446谓词公式的字母表谓词公式的字母表定义定义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量词符号量词符号:,联结词符：联结词符：,逗号和括号：逗号和括号：（，），（，），5/26/202447项的递归定义项的递归定义定义定义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)5/26/202448合式公式（谓词公式）合式公式（谓词公式）原子公式原子公式定义定义13：设：设R(x1,x2,.,xn)是任意的是任意的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组成的符号串才是合式公式组成的符号串才是合式公式（谓词公式）（谓词公式）5/26/202449指导变项、辖域指导变项、辖域定义定义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)5/26/202450闭式闭式定义定义16：设：设A为任一公式，若为任一公式，若A中无自由中无自由出现的个体变项，则称出现的个体变项，则称A是是封闭的合式公式，简称简称闭式。例子：例子：5/26/202451换名规则和代替规则换名规则和代替规则为了避免出现某个变项既是自由出现的又是约束为了避免出现某个变项既是自由出现的又是约束出现的，使用以下出现的，使用以下2种办法种办法换名规则：将量词辖域种出现的某个约束出现的个体：将量词辖域种出现的某个约束出现的个体变项及对应的指导变项，改成另外一个辖域中未曾出变项及对应的指导变项，改成另外一个辖域中未曾出现过的个体变项符号，公式其它部分不变现过的个体变项符号，公式其它部分不变 xF(x)G(x,y)zF(z)G(x,y)代替规则：对某个自由出现的个体变项用与原公式中：对某个自由出现的个体变项用与原公式中的所有个体变项符号不同的变项符号来代替，且处处的所有个体变项符号不同的变项符号来代替，且处处代替代替 xF(x)G(x,y)xF(x)G(z,y)5/26/202452公式的解释公式的解释公式的解释：一阶谓词公式中含有：个体常项，：一阶谓词公式中含有：个体常项，个体变项（自由出现或约束出现的），函数变项，个体变项（自由出现或约束出现的），函数变项，谓词变项等。对各种变项指定特殊的常项来代替，谓词变项等。对各种变项指定特殊的常项来代替，就构成公式的一个解释。就构成公式的一个解释。解释，定义解释，定义17一个解释一个解释I由下面的由下面的4个部分构成个部分构成1.非空个体域非空个体域D2.D上的一部分特定的元素上的一部分特定的元素3.D上的一些特定的函数上的一些特定的函数4.D上的一些特定的谓词上的一些特定的谓词5/26/202453解释的例子解释的例子解释解释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;5/26/202454公式的解释公式的解释5/26/202455公式的性质公式的性质定义定义18设设A为一个公式为一个公式(谓词公式谓词公式)若若A在它的任何解释下取值均为真，则称在它的任何解释下取值均为真，则称A为为逻辑有效式或或永真式若若A在它的任何解释下取值均为假，则称在它的任何解释下取值均为假，则称A为为矛盾式或或永假式若若A至少存在一组解释是成真赋值，则称至少存在一组解释是成真赋值，则称A为为可满足式5/26/202456代换实例代换实例定义定义19：设：设A0是含命题变项是含命题变项p1,p2,pn的命题的命题公式，公式，A1,A2,An是是n个谓词公式，用个谓词公式，用Ai(i=1n)处处代替处处代替pi，所得到的公式称为，所得到的公式称为A0的的代换实例例子例子命题公式：命题公式：p q A1 xF(x)A2 G(x,y)代换实例：代换实例：(xF(x)G(x,y)5/26/202457代换实例的一个结论代换实例的一个结论命题公式的重言式的代换实例在谓词逻辑中，仍然是重言式；命题公式的矛盾式的代换实例在谓词逻辑中，仍然是矛盾式；例子：例子：5/26/202458一阶逻辑等值式一阶逻辑等值式定义定义20：设：设A,B是一阶逻辑中的任意是一阶逻辑中的任意2公式，若公式，若A B是逻辑有效式，则称是逻辑有效式，则称A与与B是是等值的，记的，记做做A B，称，称A B为为等值式命题逻辑中的命题逻辑中的24条等值式的代换实例也是逻辑等条等值式的代换实例也是逻辑等值式值式5/26/202459谓词逻辑中的逻辑等值式谓词逻辑中的逻辑等值式1 定理定理1：量词否定等值式：量词否定等值式5/26/202460谓词逻辑中的逻辑等值式谓词逻辑中的逻辑等值式2定理定理2：量词的：量词的辖域收缩和和扩张等值式等值式5/26/202461谓词逻辑中的逻辑等值式谓词逻辑中的逻辑等值式3定理定理3：量词分配等值式等值式5/26/202462谓词逻辑中的逻辑等值式谓词逻辑中的逻辑等值式4定理定理4量词的性质相同，可以交换位置量词的性质不同，不可交换位置5/26/202463前束范式前束范式定义定义21：设：设A为一谓词公式，如果为一谓词公式，如果A具有具有如下形式：如下形式：Q1x1Q2x2QkxkB 则称则称A是是前束范式。其中每一个。其中每一个Qi为为 或或 B为不含量词的谓词公式（为不含量词的谓词公式（母式）例如：例如：x y(F(x,y)G(x,y)前束范式前束范式 x(F(x)y(G(y)H(x)非前束范式非前束范式5/26/202464前束范式例题前束范式例题求下列公式的前束范式求下列公式的前束范式5/26/202465谓词公式的合取范式和子句集谓词公式的合取范式和子句集对任一公式对任一公式量词辖域扩张和收缩定理，得到量词辖域扩张和收缩定理，得到前束范式对于母式，等值演算得到对于母式，等值演算得到合取范式合取项的集合，构成了该公式的合取项的集合，构成了该公式的子句集S前束范式前束范式母式母式原子：谓词原子：谓词文字：谓词或谓词的否定文字：谓词或谓词的否定子句：文字的析取子句：文字的析取合取范式：子句的合取合取范式：子句的合取子句集：合取范式的集合形式，元素之间的关系为合子句集：合取范式的集合形式，元素之间的关系为合取关系取关系5/26/202466一阶谓词逻辑一阶谓词逻辑语法和语义：语法和语义：谓词逻辑的基本组成、谓词符号、谓词逻辑的基本组成、谓词符号、常量符号、变量符号、函数符号、项的递归定常量符号、变量符号、函数符号、项的递归定义、原子、谓词演算语言的语义义、原子、谓词演算语言的语义连词和量词：连词和量词：合适公式、连词、合取、析取、合适公式、连词、合取、析取、蕴含、否定、等价、命题演算、全称量词、存蕴含、否定、等价、命题演算、全称量词、存在量词、约束变量、自由变量、句子、一阶谓在量词、约束变量、自由变量、句子、一阶谓词演算词演算表示方法表示方法 逻辑表示法逻辑表示法5/26/202467谓词逻辑的基本组成谓词逻辑的基本组成：谓词符号、变量符号、函：谓词符号、变量符号、函数符号和常量符号，并用圆括弧、方括弧、花括数符号和常量符号，并用圆括弧、方括弧、花括弧和逗号隔开，以表示论域内的关系。弧和逗号隔开，以表示论域内的关系。谓词符号谓词符号：表示个体所具有的性质，或者若干个：表示个体所具有的性质，或者若干个体之间的关系的符号。习惯用大写字母体之间的关系的符号。习惯用大写字母P，Q，R或或GREATER，LOVE表示。表示。常量符号常量符号：用来表示论域内的物体或实体，它可：用来表示论域内的物体或实体，它可以是实际的物体和人，也可以是概念或具有名字以是实际的物体和人，也可以是概念或具有名字的任何事情。一般用英文字母表中前几个带下标的任何事情。一般用英文字母表中前几个带下标或不带下标的小写字母表示。如或不带下标的小写字母表示。如a，b，.，a1，b2，c3，.。5/26/202468变量符号变量符号：不必明确涉及是哪一个实体。习惯上：不必明确涉及是哪一个实体。习惯上用带下标或不带下标的小写字母表示。如用带下标或不带下标的小写字母表示。如x，y，.，x1，y2，。函数符号函数符号：表示论域内的函数。习惯用小写字母：表示论域内的函数。习惯用小写字母f，g，h表示。表示。5/26/202469例如，要表示例如，要表示“机器人（机器人（ROBOT）在）在1号房间号房间（ROOM1）内）内”，简单的原子公式如下：，简单的原子公式如下：INROOM（ROBOT，r1）式中，式中，INROOM为谓词符号，为谓词符号，ROBOT和和r1为常量符号。为常量符号。又如，要表示又如，要表示“李（李（LI）的母亲与他的父亲结婚）的母亲与他的父亲结婚”，原原子公式如下：子公式如下：MARRIEDfather（LI），），mother（LI）式中，函数符号式中，函数符号mother、father分别用来表示某人与他分别用来表示某人与他（她的）母亲、父亲之间的（她的）母亲、父亲之间的映射映射。5/26/202470谓词演算语言的语义谓词演算语言的语义：对于每个谓词符号，必须规定定义域内的一个对于每个谓词符号，必须规定定义域内的一个相应关系；相应关系；对于每个常量符号，必须规定定义域内相应的对于每个常量符号，必须规定定义域内相应的一个实体；一个实体；对于每个函数符号，必须规定定义域内相应的对于每个函数符号，必须规定定义域内相应的一个函数。一个函数。5/26/202471对于已定义了的某个解释的一个原子公式，对于已定义了的某个解释的一个原子公式，只有当其对应的语句在定义域内为真时，只有当其对应的语句在定义域内为真时，才具有值才具有值T（真）；而当其对应的语句在定（真）；而当其对应的语句在定义域内为假时，该原子公式才具有值义域内为假时，该原子公式才具有值F（假）（假）。因此，。因此，INROOM（ROBOT，r1）具有）具有值值T，而，而INROOM（ROBOT，r2）则具有）则具有值值F。5/26/202472当一个原子公式含变量符号时，对定义域当一个原子公式含变量符号时，对定义域内实体的变量可能有几个设定。对某几个内实体的变量可能有几个设定。对某几个设定的变量，原子公式取值设定的变量，原子公式取值T；而对另外几；而对另外几个设定的变量，原子公式取值个设定的变量，原子公式取值F。5/26/202473表示方法表示方法 逻辑表示法逻辑表示法一阶谓词逻辑是谓词逻辑中一阶谓词逻辑是谓词逻辑中最直观最直观的一种逻辑。的一种逻辑。它以谓词形式来表示动作的主题、客体。客体它以谓词形式来表示动作的主题、客体。客体可以多个。可以多个。如：张三与李四打网球（如：张三与李四打网球（ZhangandLiplaytennis），可写为：），可写为：play(Zhang,Li,tennis)这里谓词是这里谓词是play，动词主体是，动词主体是Zhang和和Li，而，而客体是客体是tennis。谓词逻辑规范表达式：谓词逻辑规范表达式：P(x1,x2,x3,)，这里这里P是谓词是谓词,xi是主体与客是主体与客体。体。5/26/202474表示方法表示方法 逻辑表示法逻辑表示法谓词比命题更加细致地刻画知识：谓词比命题更加细致地刻画知识：表达能力强表达能力强如：北京是个城市，如：北京是个城市，City(x)把城市这个概念分割出来。把把城市这个概念分割出来。把“城市城市”与与“北京北京”两个两个概念连接在一起，而且说明概念连接在一起，而且说明“北京北京”是是“城市城市”的子概的子概念。（有层）念。（有层）谓词可以代表变化的情况谓词可以代表变化的情况如：如：City(北京北京),真。真。City(煤球煤球)，假，假5/26/202475表示方法表示方法 逻辑表示法逻辑表示法在不同的知识之间建立联系在不同的知识之间建立联系如：如：Human(x)Lawed(x)，人人都受法人人都受法律管制，律管制，x是同一个人。是同一个人。Commit(x)Punished(x)，x不一定是人也不一定是人也可以是动物。可以是动物。而，而，Human(x)Lawed(x)commit(x)Punished(x)，意为如果由于某个意为如果由于某个x是人而受法律管制，则是人而受法律管制，则这个人犯了罪就一定要受到惩罚这个人犯了罪就一定要受到惩罚。5/26/202476表示方法表示方法 逻辑表示法逻辑表示法谓词逻辑法是应用最广的方法之一，其原因是：谓词逻辑法是应用最广的方法之一，其原因是：谓词逻辑与数据库，特别是关系数据库就有密切的谓词逻辑与数据库，特别是关系数据库就有密切的关系。在关系数据库中，逻辑代数表达式是谓词表关系。在关系数据库中，逻辑代数表达式是谓词表达式之一。因此，如果采用谓词逻辑作为系统的理达式之一。因此，如果采用谓词逻辑作为系统的理论背景，则可将数据库系统扩展改造成知识库。论背景，则可将数据库系统扩展改造成知识库。一阶谓词逻辑具有完备的逻辑推理算法。如果对逻一阶谓词逻辑具有完备的逻辑推理算法。如果对逻辑的某些外延扩展后，则可把大部分的知识表达成辑的某些外延扩展后，则可把大部分的知识表达成一阶谓词逻辑的形式。（知识易表达）一阶谓词逻辑的形式。（知识易表达）5/26/202477表示方法表示方法 逻辑表示法逻辑表示法谓词逻辑法是应用最广的方法之一，其原因是：谓词逻辑法是应用最广的方法之一，其原因是：谓词逻辑本身具有比较扎实的数学基础，知识的表谓词逻辑本身具有比较扎实的数学基础，知识的表达方式决定了系统的主要结构。因此，对知识表达达方式决定了系统的主要结构。因此，对知识表达方式的严密科学性要求就比较容易得到满足。这样方式的严密科学性要求就比较容易得到满足。这样对形式理论的扩展导致了整个系统框架的发展。对形式理论的扩展导致了整个系统框架的发展。逻辑推理是公理集合中演绎而得出结论的过程。由逻辑推理是公理集合中演绎而得出结论的过程。由于逻辑及形式系统具有的重要性质，可以保证知识于逻辑及形式系统具有的重要性质，可以保证知识库中新旧知识在逻辑上的一致性（或通过相应的一库中新旧知识在逻辑上的一致性（或通过相应的一套处理过程检验）、和所演绎出来的结论的正确性。套处理过程检验）、和所演绎出来的结论的正确性。而其它的表示方法在这点上还不能与其相比。而其它的表示方法在这点上还不能与其相比。5/26/202478表示方法表示方法 逻辑表示法逻辑表示法为此逻辑表示法在实际人工智能系统上得为此逻辑表示法在实际人工智能系统上得到应用。到应用。存在问题存在问题：谓词表示越细，推理越慢、效率越低，但谓词表示越细，推理越慢、效率越低，但表示清楚。实际中是要折衷的。表示清楚。实际中是要折衷的。5/26/202479置换置换置换置换是形如是形如t1/v1，.，tn/vn的一个有限集。其的一个有限集。其中中vi是变量，而是变量，而ti是不同于是不同于vi的项（常量、变量、的项（常量、变量、函数），且函数），且vivj（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为任意常量符号。为任意常量符号。一个表达式的一个表达式的置换置换就是在该表达式中用置换项置就是在该表达式中用置换项置换换变量变量。一般说来，置换是可结合的，但置换是不可交换一般说来，置换是可结合的，但置换是不可交换的。的。5/26/202480置换置换例例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），），B5/26/202481合一合一寻找项对变量的置换，以使两表达式一致，叫做寻找项对变量的置换，以使两表达式一致，叫做合一合一(unification)(unification)。如果一个置换。如果一个置换s s作用于表达作用于表达式集式集EiEi的每个元素，则用的每个元素，则用EiEis s来表示置来表示置换例的集。换例的集。称表达式集称表达式集EiEi是是可合一的可合一的，如果存在一个置，如果存在一个置换换s s使得：使得：E1s=E2s=E3s=E1s=E2s=E3s=那么称此那么称此s s为为EiEi的的合一者合一者，因为，因为s s的作用是使集合的作用是使集合EiEi成为单一成为单一形式。形式。5/26/202482合一合一例例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/y5/26/202483分歧集分歧集设有一非空有限公式集设有一非空有限公式集F=F1，F2，Fn,从从F中个公式的第一符号同时向右比较中个公式的第一符号同时向右比较,直到发现第一个彼此不仅、不尽相同的符直到发现第一个彼此不仅、不尽相同的符号为止号为止,从从F的各个公式中取出那些以第一的各个公式中取出那些以第一个不一致符号开始的最大的子表达式为元个不一致符号开始的最大的子表达式为元素素,组成一个集合组成一个集合D,称为称为F的的分歧集分歧集.5/26/202484合一算法合一算法合一算法合一算法：设：设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不存在。不存在。5/26/202485合一算法举例合一算法举例例例3求公式集求公式集F=P(a,x,f(g(y),P(z,h(z,u),f(u)的最一般合一者的最一般合一者5/26/202486合一算法举例（续）合一算法举例（续）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)/xF2=F1h(a,u)/x=P(a,h(a,u),f(g(y),P(a,h(a,u),f(u)5/26/202487合一算法举例（续）合一算法举例（续）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的最一般合一的最一般合一者者5/26/202488注意注意：1.在合式公式中，连接词的优先级别是在合式公式中，连接词的优先级别是:,2.位于量词后面的单个谓词或用括号括起来的合式公式称为量词辖域，辖位于量词后面的单个谓词或用括号括起来的合式公式称为量词辖域，辖域内与量词中同名变元称为约束变元，不受约束的变元称为自由变元。域内与量词中同名变元称为约束变元，不受约束的变元称为自由变元。如：如：(x)(P(x,y)Q(x,y)R(x,y)3.在谓词公式中，变元的名字是无关紧要的，可以把一个名字换成另一个在谓词公式中，变元的名字是无关紧要的，可以把一个名字换成另一个名字，但必须注意：名字，但必须注意：当对量词辖域内的约束变元更名时，必须把同名的约束变元统一改成相同当对量词辖域内的约束变元更名时，必须把同名的约束变元统一改成相同的名字，且不能与辖域内的自由变元同名；的名字，且不能与辖域内的自由变元同名；当对量词辖域内的自由变元改名时，不能改成与约束变元相同的名字。当对量词辖域内的自由变元改名时，不能改成与约束变元相同的名字。5/26/202489谓词逻辑是一种形式语言，也是到目前为止能谓词逻辑是一种形式语言，也是到目前为止能够表达人类思维活动规律的一种最精确的语言，够表达人类思维活动规律的一种最精确的语言，它与人们的自然语言比较接近，又可方便地存它与人们的自然语言比较接近，又可方便地存储到计算机中去，并被精确地处理。因此，它储到计算机中去，并被精确地处理。因此，它成为最早应用于人工智能中表示知识的一种逻成为最早应用于人工智能中表示知识的一种逻辑。辑。知识的一阶谓词逻辑表示知识的一阶谓词逻辑表示5/26/202490谓词逻辑适合于表示事物的状态、属性、概念等谓词逻辑适合于表示事物的状态、属性、概念等事实性的知识，也可以用来表示事物间确定的事实性的知识，也可以用来表示事物间确定的因因果关系果关系，即规则。，即规则。事实通常用合式公式的事实通常用合式公式的“与与/或或”形表示（用合取符号形表示（用合取符号及析取符号及析取符号连接起来的公式）。连接起来的公式）。规则通常用蕴涵式规则通常用蕴涵式表示。表示。用谓词公式（合式公式）表示知识时，需要首先用谓词公式（合式公式）表示知识时，需要首先定义定义谓词谓词，指出每个谓词的确切含义，然后再用，指出每个谓词的确切含义，然后再用连接词把有关的谓词连接起来，形成一个谓词公连接词把有关的谓词连接起来，形成一个谓词公式表达一个完整的含义。式表达一个完整的含义。5/26/202491 例例1 有下列知识：有下列知识：刘欢比他父亲出名。刘欢比他父亲出名。高扬是计算机系的一名学生，但他不喜欢编程序。高扬是计算机系的一名学生，但他不喜欢编程序。人人爱劳动。人人爱劳动。为了用谓词公式表示上述知识，首先需要定义谓词：为了用谓词公式表示上述知识，首先需要定义谓词：Bigger(x,y):x 比比 y 出名。出名。Computer(x):x 是计算机系的学生。是计算机系的学生。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)5/26/202492例例2 2 设有下列知识设有下列知识自然数都是大于零的整数自然数都是大于零的整数所有整数不是偶数就是奇数所有整数不是偶数就是奇数偶数除以偶数除以2 2是整数是整数首先定义谓词如下：首先定义谓词如下：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)5/26/202493例例3.3.设在房内设在房内c c处有一机器人，在处有一机器人，在a a及及b b处各有一张桌子，处各有一张桌子，a a桌上有一个盒桌上有一个盒子，为了让机器人从子，为了让机器人从c c处出发把盒子从处出发把盒子从a a处拿到处拿到b b处的桌上，然后再回到处的桌上，然后再回到c c处，需要制定相应的行动规划。下面用一阶谓词逻辑描述机器人的行处，需要制定相应的行动规划。下面用一阶谓词逻辑描述机器人的行动过程。动过程。该例子中，不仅要用谓词表示事物的状态、位置，还要表示其行动。该例子中，不仅要用谓词表示事物的状态、位置，还要表示其行动。cab设相关谓词的定义如下：设相关谓词的定义如下：table(x):x table(x):x是桌子是桌子 empty(y):y empty(y):y手中是空的手中是空的 at(y at(y，z)z)：y y在在z z的附近的附近 holds(y,w):y holds(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的个体域是的个体域是boxbox5/26/202494问题的初始状态是：问题的初始状态是：at(robot,c)empty(robot)on(box,a)table(a)table(b)问题的目标状态是：问题的目标状态是：at(robot,c)empty(robot)on(box,b)table(a)table(b)机机器器人人的的目目标标是是把把问问题题的的初初始始状状态态转转化化为为目目标标状状态态，其其间间它它必必须须完成一系列的操作。完成一系列的操作。cab5/26/202495操作一般可以分为操作一般可以分为条件条件和和动作动作两部分。两部分。条件条件可以很容易的用谓词公式表示，可以很容易的用谓词公式表示，动动作作可可以以通通过过动动作作前前后后的的状状态态变变化化表表示示出出来来，即即只只要要指指出出动动作作后后应应从从动动作前的状态中删去和增加什么谓词就描述了相应的动作。作前的状态中删去和增加什么谓词就描述了相应的动作。机器人为了把盒子从机器人为了把盒子从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)table(x)empty(robot)动作动作删除：删除：empty(robot)on(box,x)增加增加:holds(robot,box)5/26/2024963.Set_down(x)条件：条件：at(robot,x)table(x)h