《第四章逻辑推理精选文档.ppt》由会员分享，可在线阅读，更多相关《第四章逻辑推理精选文档.ppt（95页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第四章逻辑推理本讲稿第一页，共九十五页4.1 推理的基本概念推理的基本概念l按照某种策略从已知事实出发推出结论的过程。按照某种策略从已知事实出发推出结论的过程。l推理所用的事实分为两种：推理所用的事实分为两种：初始证据初始证据与与中间结论中间结论l智能系统的推理过程是通过推理机来完成的。所谓推理智能系统的推理过程是通过推理机来完成的。所谓推理机就是智能系统中用来实现推理的程序。机就是智能系统中用来实现推理的程序。一一.什么是推理什么是推理本讲稿第二页，共九十五页二二.推理方法及其分类推理方法及其分类l可以从不同角度对推理方式进行分类（可以从不同角度对推理方式进行分类（逻辑基础、逻辑基础、所用知
2、识的确定性、推理过程的单调性所用知识的确定性、推理过程的单调性）l1.按推理的逻辑基础分类按推理的逻辑基础分类 演绎推理演绎推理 归纳推理归纳推理 默认推理默认推理 本讲稿第三页，共九十五页演绎推理演绎推理l由一般到个别的推理方法。由一般到个别的推理方法。l核心是三段论，通常由一个大前提、一个小前提和一核心是三段论，通常由一个大前提、一个小前提和一个结论三部分组成的。个结论三部分组成的。l例：阿凡提的故事例：阿凡提的故事-两头驴的故事两头驴的故事 我肩上驮的是两头驴的东西我肩上驮的是两头驴的东西（大前提）（大前提）国王和大臣的衣衫是我肩上驮的（小前提）国王和大臣的衣衫是我肩上驮的（小前提）国王
3、和大臣的衣衫是两头驴的东西（结论）国王和大臣的衣衫是两头驴的东西（结论）本讲稿第四页，共九十五页归纳推理归纳推理l从一类事物的大量特殊事例出发，去推出该类事物的一般性结论。（从一类事物的大量特殊事例出发，去推出该类事物的一般性结论。（从从个别到一般）个别到一般）l基本思想是：先从已知事实中猜测出一个结论，然后对这个结论的基本思想是：先从已知事实中猜测出一个结论，然后对这个结论的正确性加以证明确认。（正确性加以证明确认。（归纳结论不具备逻辑必然性归纳结论不具备逻辑必然性）l数学归纳法就是归纳推理的一种典型例子。数学归纳法就是归纳推理的一种典型例子。l如果按照所选事例的广泛性可分为完全归纳推理和不
4、完全归纳推理；如果如果按照所选事例的广泛性可分为完全归纳推理和不完全归纳推理；如果按照推理所使用的方法可分为枚举归纳推理、类比归纳推理、统计归纳推按照推理所使用的方法可分为枚举归纳推理、类比归纳推理、统计归纳推理和差异归纳推理等。理和差异归纳推理等。本讲稿第五页，共九十五页l演绎推理所得出的结论蕴含在一般性知识的前提中，演绎推理所得出的结论蕴含在一般性知识的前提中，演绎推理只不过是将已有事实揭示出来，因此它不能演绎推理只不过是将已有事实揭示出来，因此它不能增殖新知识。增殖新知识。l在归纳推理中，所推出的结论是没有包含在前提内容在归纳推理中，所推出的结论是没有包含在前提内容中的。这种由个别事物或
5、现象推出一般性知识的过程，中的。这种由个别事物或现象推出一般性知识的过程，是增殖新知识的过程。是增殖新知识的过程。演绎推理与归纳推理的区别演绎推理与归纳推理的区别本讲稿第六页，共九十五页l 确定性推理确定性推理 推理所使用的知识和推出的结论都是可以精确表示的，其真值推理所使用的知识和推出的结论都是可以精确表示的，其真值要么为真，要么为假，不会有第三种情况出现。要么为真，要么为假，不会有第三种情况出现。经典逻辑推理经典逻辑推理l 不确定性推理不确定性推理 推理时所用的知识不都是确定的，推出的结论也不完全是确推理时所用的知识不都是确定的，推出的结论也不完全是确定的，其真值位于真与假之间。定的，其真
6、值位于真与假之间。概率概率(probability)，模糊，模糊(fuzzy)2.按所用知识的确定性分类按所用知识的确定性分类本讲稿第七页，共九十五页3.按推理过程的单调性分类按推理过程的单调性分类l单调推理单调推理 在推理过程中，每当使用新的知识后，所得到的结论会越来越在推理过程中，每当使用新的知识后，所得到的结论会越来越接近于目标，而不会出现反复情况，即不会由于新知识的加入接近于目标，而不会出现反复情况，即不会由于新知识的加入否定了前面推出的结论，从而使推理过程又退回到先前的某一否定了前面推出的结论，从而使推理过程又退回到先前的某一步。步。l 非单调推理非单调推理 在推理过程中，当某些新知
7、识加入后，会否定原来推出的结论，使在推理过程中，当某些新知识加入后，会否定原来推出的结论，使推理过程退回到先前的某一步。推理过程退回到先前的某一步。本讲稿第八页，共九十五页三三.推理控制策略推理控制策略l如何使用领域知识使推理过程尽快达到目标？如何使用领域知识使推理过程尽快达到目标？l推理控制策略可分为推理策略和搜索策略。推理控制策略可分为推理策略和搜索策略。推理策略主要解决推理策略主要解决推理方向推理方向、冲突消解冲突消解等问题，如等问题，如推理方向推理方向控制策略控制策略、求解策略求解策略、限制策略限制策略、冲突消解策略冲突消解策略等等搜索策略主要解决搜索策略主要解决推理线路推理线路、推理
8、效果推理效果、推理效推理效 率率等问题等问题本讲稿第九页，共九十五页1.推理策略推理策略l推理方向推理方向 正向推理、逆向推理、混合推理正向推理、逆向推理、混合推理l求解策略求解策略 一个解，所有解或最优解？一个解，所有解或最优解？l限制策略限制策略 对推理的深度对推理的深度,宽度宽度,时间时间,空间等进行限制空间等进行限制l冲突消解策略冲突消解策略 如何从多条可用知识中选择？如何从多条可用知识中选择？本讲稿第十页，共九十五页2.正向推理正向推理l从已知事实出发、正向使用推理规则从已知事实出发、正向使用推理规则l也称为数据驱动推理或前向链推理也称为数据驱动推理或前向链推理l基本思想：基本思想：
9、推理机根据推理机根据已有事实已有事实，寻找当前，寻找当前可用知识可用知识，然后按照冲突消解策，然后按照冲突消解策略，从当前可用知识集中选择一条知识进行略，从当前可用知识集中选择一条知识进行推理推理，并将新推出的，并将新推出的事实作为后面继续推理时可用的已知事实。重复上述过程，事实作为后面继续推理时可用的已知事实。重复上述过程，直到求出所需要的解或者知识库中再无可用知识。直到求出所需要的解或者知识库中再无可用知识。本讲稿第十一页，共九十五页3.逆向推理逆向推理l以假设目标作为出发点进行推理以假设目标作为出发点进行推理l也称为目标驱动推理或逆向链推理也称为目标驱动推理或逆向链推理l基本思想：基本思
10、想：首先将要求证的首先将要求证的目标（称为假设）目标（称为假设）构成假设集，从中逐个取出假设构成假设集，从中逐个取出假设进行验证。如该假设为进行验证。如该假设为已知事实已知事实或或原始证据原始证据，则假设成立；如，则假设成立；如该假设可由知识库中的一个或多个知识导出，则知识库中所有该假设可由知识库中的一个或多个知识导出，则知识库中所有可以导出该假设的知识构成当前可用知识集，从中选择一个知可以导出该假设的知识构成当前可用知识集，从中选择一个知识，将其前提中的所有子条件都作为新的假设放入假设集。重识，将其前提中的所有子条件都作为新的假设放入假设集。重复上述过程，直到假设集为空时成功退出，或假设集非
11、空但可复上述过程，直到假设集为空时成功退出，或假设集非空但可用知识集为空时失败退出。用知识集为空时失败退出。本讲稿第十二页，共九十五页正向推理逆向推理优点比较直观，允许用户主动提供有用的事实信息。推理过程的目标明确，同时也有利于向用户提供解释缺点推理无明确目标，会执行许多与解无关的操作，效率较低初始目标选择有盲目性，若选择不好，可能需要多次提出假设，影响系统效率本讲稿第十三页，共九十五页4.混合推理混合推理l把正向推理和逆向推理结合起来所进行的推理把正向推理和逆向推理结合起来所进行的推理l实现方法实现方法先正向后逆向先正向后逆向先逆向后正向先逆向后正向双向混合推理双向混合推理 同时作正向和逆向
12、推理，二者在某处碰头同时作正向和逆向推理，二者在某处碰头 本讲稿第十四页，共九十五页5.推理的冲突消解策略推理的冲突消解策略l在推理过程中，同时有多条知识可用，则发生在推理过程中，同时有多条知识可用，则发生“冲突冲突”。l如正向推理时有多条规则的前件与已有事实匹配成功，或逆向如正向推理时有多条规则的前件与已有事实匹配成功，或逆向推理时有多条规则的后件与已有事实匹配成功。推理时有多条规则的后件与已有事实匹配成功。l从多条可用知识中选择用于推理的最佳知识，称为从多条可用知识中选择用于推理的最佳知识，称为“冲突消解冲突消解”，其中所用策略称为，其中所用策略称为“冲突消解策略冲突消解策略”。本讲稿第十
13、五页，共九十五页冲突消解策略冲突消解策略l基本思想基本思想 对可用知识进行排序对可用知识进行排序l常用排序方法常用排序方法 1.按特殊性排序按特殊性排序 2.按新鲜性排序按新鲜性排序 3.差异性大的知识优先差异性大的知识优先 4.领域特点优先领域特点优先 5.上下文关系优先上下文关系优先 6.前提条件少者优先前提条件少者优先l 本讲稿第十六页，共九十五页4.2 推理的逻辑基础推理的逻辑基础l根据经典逻辑的逻辑规则进行的一种推理根据经典逻辑的逻辑规则进行的一种推理l 确定性推理确定性推理l主要推理方法包括主要推理方法包括 自然演绎推理自然演绎推理 归结演绎推理归结演绎推理 与与/或形演绎推理或形
14、演绎推理本讲稿第十七页，共九十五页推理的逻辑基础推理的逻辑基础l一阶谓词逻辑表示一阶谓词逻辑表示l谓词公式的解释谓词公式的解释l谓词公式的永真性与可满足性谓词公式的永真性与可满足性l谓词公式的等价性与永真蕴含性谓词公式的等价性与永真蕴含性l谓词公式的范式谓词公式的范式l置换与合一置换与合一本讲稿第十八页，共九十五页一、一阶谓词逻辑表示的逻辑基础一、一阶谓词逻辑表示的逻辑基础l命题与真值命题与真值l论域和谓词论域和谓词l连接词和量词连接词和量词l项与合式公式项与合式公式l自由变元和约束变元自由变元和约束变元本讲稿第十九页，共九十五页命题与真值l一个陈述句称为一个断言。凡有真假意义一个陈述句称为一
15、个断言。凡有真假意义的断言称为命题。的断言称为命题。l命题的意义通常称为真值，它只有真假命题的意义通常称为真值，它只有真假两种情况。真值为真记为两种情况。真值为真记为T；反之记为；反之记为F。l一个命题不能同时既为真又为假一个命题不能同时既为真又为假 例：例：“天安门城楼在长安街的北边天安门城楼在长安街的北边”是一个真值是一个真值为为T的命题，的命题，“天安门广场在长安街的北边天安门广场在长安街的北边”则则是一个真值为是一个真值为F的命题。的命题。本讲稿第二十页，共九十五页命题与真值l一个命题可在一定条件下为真，在另外的条件一个命题可在一定条件下为真，在另外的条件下为假下为假 例：例：“北京今
16、天有雨北京今天有雨”l没有真假意义的感叹句、疑问句等都不是命题。没有真假意义的感叹句、疑问句等都不是命题。l命题的优点是简单、明确；其主要缺点是无法描述命题的优点是简单、明确；其主要缺点是无法描述客观事物的结构及其逻辑特征，也无法表示不同事客观事物的结构及其逻辑特征，也无法表示不同事物间的共性。物间的共性。本讲稿第二十一页，共九十五页论域和谓词l论域是由所讨论对象之全体构成的非空集合。论域是由所讨论对象之全体构成的非空集合。l在谓词逻辑中，命题是用谓词来表示的。一个谓词可在谓词逻辑中，命题是用谓词来表示的。一个谓词可分为谓词名和个体两部分。分为谓词名和个体两部分。l谓词定义：谓词定义：设设D是
17、论域，是论域，P:DnT，F是一个映射，其中是一个映射，其中 Dn=(x1,x2,xn)|x1,x2,xnD，则称，则称P是一个是一个n元谓词（元谓词（n=1,2,）,记为记为P(x1,x2,xn)。其中。其中,x1,x2,xn 为个体变元。为个体变元。本讲稿第二十二页，共九十五页谓词l在谓词在谓词P(x1,x2,xn)中，如果中，如果xi(i=1,2,n)都是个体常量、变元或函数，都是个体常量、变元或函数，称它为一阶谓词。如果某个称它为一阶谓词。如果某个xi本身又是一个本身又是一个一阶谓词，则称它为二阶谓词。一阶谓词，则称它为二阶谓词。l例子例子 1.“王宏是学生王宏是学生”STUDENT(
18、Wanghong)。2.“x6”Greater(x,6)3.“王宏的父亲是教师王宏的父亲是教师”TEACHER(father(Wanghong)本讲稿第二十三页，共九十五页连接词l：“非非”或者或者“否定否定”P 对其后面命题的否定，使该命题的真值与原来相反。对其后面命题的否定，使该命题的真值与原来相反。l：“析取析取”PQ 两个命题之间具有两个命题之间具有“或或”的关系。的关系。l：“合取合取”PQ 两个命题之间具有两个命题之间具有“与与”的关系的关系。l：“条件条件”或或“蕴含蕴含”PQ 表示表示“若若则则”的语义。的语义。l：“双条件双条件”PQ 表示表示“当且仅当当且仅当”的语义的语义
19、同命题逻辑，连接简单命题成复合命题本讲稿第二十四页，共九十五页对以上连接词的定义，可用下表所给出的谓对以上连接词的定义，可用下表所给出的谓词逻辑真值表来表示。词逻辑真值表来表示。谓词逻辑真值表谓词逻辑真值表 P QPPQPQPQ PQTTFTTTTTFFTFFFFTTTFTFFFTFFTT本讲稿第二十五页，共九十五页量词l量词是由量词符号和被其量化的变元所组成的表达式，对量词是由量词符号和被其量化的变元所组成的表达式，对谓词中的个体作出量的规定谓词中的个体作出量的规定。l全称量词全称量词：命题命题(x)P(x)为真，当且仅当对论域中的所有为真，当且仅当对论域中的所有x，都有，都有P(x)为为真
20、。命题真。命题(x)P(x)为假，当且仅当至少存在一个为假，当且仅当至少存在一个x0D，使，使得得P(x0)为假为假。l存在量词存在量词 命题命题(x)P(x)为真，当且仅当至少存在一个为真，当且仅当至少存在一个 x0D，使得，使得P(x0)为为真。命题真。命题(彐彐x)P(x)为假，当且仅当对论域中的所有为假，当且仅当对论域中的所有x，都有，都有P(x)为假。为假。彐彐本讲稿第二十六页，共九十五页项与合式l谓词公式谓词公式合法的表达式称为合式公式合法的表达式称为合式公式l项项:（1）单独一个个体词是项；）单独一个个体词是项；（2）若）若t1，t2,，tn是项，是项，f是是n元函数元函数 ，则
21、，则f(t1,t2,tn)是项；是项；（3）由（）由（1）,（2）生成的表达式是项）生成的表达式是项l原子谓词公式原子谓词公式：若若t1，t2，tn是项，是项，P是谓词符号，则称是谓词符号，则称 P(t1,t2,tn)为原子谓词公式。为原子谓词公式。本讲稿第二十七页，共九十五页项与合式l合式公式：合式公式：（1）单个原子谓词公式是合式公式；）单个原子谓词公式是合式公式；（2）若）若A是合式公式，则是合式公式，则A也是合式公式；也是合式公式；（3）若）若A、B都是合式公式，则都是合式公式，则AB，AB ，AB，AB也都是合式公式；也都是合式公式；（4）若）若A是合式公式，是合式公式，x是项，则（
22、是项，则（x)A 和和(彐彐x)A也都是合式公式。也都是合式公式。本讲稿第二十八页，共九十五页自由变元和约束变元l当一个谓词公式含有量词时，区分个体变元是否受量词当一个谓词公式含有量词时，区分个体变元是否受量词的约束是很重要的。通常，把位于量词后面的单个谓的约束是很重要的。通常，把位于量词后面的单个谓词或者用括号括起来的合式公式称为该量词的辖域，词或者用括号括起来的合式公式称为该量词的辖域，辖域内与量词中同名的变元称为辖域内与量词中同名的变元称为约束变元约束变元，不受约束，不受约束的变元称为的变元称为自由变元自由变元。l （x)(P(x)(P(x x,y y)Q()Q(x x,y y)R()R
23、(x x,y y)本讲稿第二十九页，共九十五页谓词逻辑表示法 谓词逻辑可以用来表示知识谓词逻辑可以用来表示知识l 事物的状态、属性、概念等事实性知识，通常用否定、事物的状态、属性、概念等事实性知识，通常用否定、析取或合取符号连接起来的谓词公式表示。析取或合取符号连接起来的谓词公式表示。l 事物的因果关系，即规则，通常用蕴含式表示，例事物的因果关系，即规则，通常用蕴含式表示，例如，对如，对“如果如果x，则，则y”,可表示为可表示为“xy”。本讲稿第三十页，共九十五页谓词逻辑表示法例子谓词逻辑表示法例子l“每个人都有一个父亲每个人都有一个父亲”(x)(y)(PERSON(x)HASFATHER(x
24、,y)l“所有教师都有自己的学生所有教师都有自己的学生”(x)(y)(TEACHER(x)TEACHES(x,y)STUDENT(y)l“所有的整数不是偶数就是奇数所有的整数不是偶数就是奇数”(x)(I(x)E(x)O(x)彐彐彐彐本讲稿第三十一页，共九十五页例：机器人移盒子问题例：机器人移盒子问题例：机器人移盒子问题例：机器人移盒子问题 设在一房间里，设在一房间里，设在一房间里，设在一房间里，c c c c处有一个机器人，处有一个机器人，处有一个机器人，处有一个机器人，a a a a和和和和b b b b处各有一张桌子，分别称为处各有一张桌子，分别称为处各有一张桌子，分别称为处各有一张桌子，
25、分别称为a a a a桌和桌和桌和桌和b b b b桌，桌，桌，桌，a a a a桌子上有一盒子，如下图所示。要求机器人从桌子上有一盒子，如下图所示。要求机器人从桌子上有一盒子，如下图所示。要求机器人从桌子上有一盒子，如下图所示。要求机器人从c c c c处出发把盒子从处出发把盒子从处出发把盒子从处出发把盒子从a a a a桌上拿到桌上拿到桌上拿到桌上拿到b b b b桌上，然后再回到桌上，然后再回到桌上，然后再回到桌上，然后再回到c c c c处。请用谓词逻辑来描述机器人的行动过处。请用谓词逻辑来描述机器人的行动过处。请用谓词逻辑来描述机器人的行动过处。请用谓词逻辑来描述机器人的行动过程。程
26、。程。程。机器人移盒子机器人移盒子C谓词逻辑表示的应用谓词逻辑表示的应用本讲稿第三十二页，共九十五页 在这个例子中，不仅要用谓词公式来在这个例子中，不仅要用谓词公式来在这个例子中，不仅要用谓词公式来在这个例子中，不仅要用谓词公式来描述事物的状态、位置描述事物的状态、位置描述事物的状态、位置描述事物的状态、位置，而且还要用谓词公式而且还要用谓词公式而且还要用谓词公式而且还要用谓词公式表示动作表示动作表示动作表示动作。为此，需要定义如下谓词公式：。为此，需要定义如下谓词公式：。为此，需要定义如下谓词公式：。为此，需要定义如下谓词公式：TABLE(x)TABLE(x)TABLE(x)TABLE(x)
27、:x:x:x:x是桌子是桌子是桌子是桌子 EMPTY(y)EMPTY(y)EMPTY(y)EMPTY(y):y:y:y:y手中是空的手中是空的手中是空的手中是空的 AT(y,z)AT(y,z)AT(y,z)AT(y,z):y:y:y:y在在在在z z z z的附近的附近的附近的附近 HOLDS(y,w)HOLDS(y,w)HOLDS(y,w)HOLDS(y,w):y:y:y:y拿着拿着拿着拿着w w w w ONONONON（w w w w，x x x x）：w w w w在在在在x x x x桌面上。桌面上。桌面上。桌面上。其中：其中：x x的个体域是：的个体域是：y y的个体域是：的个体域
28、是：z z的个体域是：的个体域是：w w的个体域是：的个体域是：a a，b brobotrobot a a，b b，c c box box 本讲稿第三十三页，共九十五页 问题的问题的问题的问题的初始状态初始状态初始状态初始状态是：是：是：是：ATATATAT（robot,crobot,crobot,crobot,c）EMPTYEMPTYEMPTYEMPTY（robotrobotrobotrobot）ONONONON（boxboxboxbox，a a a a）TABLETABLETABLETABLE（a a a a）TABLETABLETABLETABLE（b b b b）问题的问题的目标状态目
29、标状态是：是：ATAT（robotrobot，c c）EMPTYEMPTY（robotrobot）ONON（boxbox，b b）TABLETABLE（a a）TABLETABLE（b b）使用规则！使用规则！本讲稿第三十四页，共九十五页 机器人行动的目标是把问题的初始状态转换为目标状态，而要实现机器人行动的目标是把问题的初始状态转换为目标状态，而要实现机器人行动的目标是把问题的初始状态转换为目标状态，而要实现机器人行动的目标是把问题的初始状态转换为目标状态，而要实现问题状态的转换需要完成一系列的操作。对于每个操作，一般都可分为问题状态的转换需要完成一系列的操作。对于每个操作，一般都可分为问题
30、状态的转换需要完成一系列的操作。对于每个操作，一般都可分为问题状态的转换需要完成一系列的操作。对于每个操作，一般都可分为条件条件条件条件和和和和动作动作动作动作两个部分两个部分两个部分两个部分 条件部分条件部分条件部分条件部分用来说明执行该操作必须具备的先决条件，用来说明执行该操作必须具备的先决条件，用来说明执行该操作必须具备的先决条件，用来说明执行该操作必须具备的先决条件，动作部分动作部分动作部分动作部分给出了该操作对问题状态的改变情况。给出了该操作对问题状态的改变情况。给出了该操作对问题状态的改变情况。给出了该操作对问题状态的改变情况。条件部分条件部分条件部分条件部分可用谓词公式来表示，可
31、用谓词公式来表示，可用谓词公式来表示，可用谓词公式来表示，动作部分动作部分动作部分动作部分则是通过在执行该操作前的则是通过在执行该操作前的则是通过在执行该操作前的则是通过在执行该操作前的问题状态中删去和增加相应的谓词来实现的。问题状态中删去和增加相应的谓词来实现的。问题状态中删去和增加相应的谓词来实现的。问题状态中删去和增加相应的谓词来实现的。在本问题中，机器人需要执行以下三个操作：在本问题中，机器人需要执行以下三个操作：在本问题中，机器人需要执行以下三个操作：在本问题中，机器人需要执行以下三个操作：GotoGotoGotoGoto（x x x x，y y y y）：从：从：从：从x x x
32、x处走到处走到处走到处走到y y y y处。处。处。处。PickupPickupPickupPickup（x x x x）：在：在：在：在x x x x处拿起盒子。处拿起盒子。处拿起盒子。处拿起盒子。SetdownSetdownSetdownSetdown（x x x x）：在：在：在：在x x x x处放下盒子。处放下盒子。处放下盒子。处放下盒子。本讲稿第三十五页，共九十五页 这三个操作对应的条件与动作如下：这三个操作对应的条件与动作如下：这三个操作对应的条件与动作如下：这三个操作对应的条件与动作如下：GotoGotoGotoGoto（x,yx,yx,yx,y）条件：条件：条件：条件：ATA
33、TATAT（robot,xrobot,xrobot,xrobot,x）动作：删除表：动作：删除表：动作：删除表：动作：删除表：ATATATAT（robot,xrobot,xrobot,xrobot,x）添加表：添加表：添加表：添加表：ATATATAT（robot,yrobot,yrobot,yrobot,y）PickupPickupPickupPickup（x x x x）条件：条件：条件：条件：ONONONON（box,xbox,xbox,xbox,x），），），），TABLETABLETABLETABLE（x x x x），），），），ATATATAT（robot,xrobot,xrobo
34、t,xrobot,x），），），），EMPTYEMPTYEMPTYEMPTY（robotrobotrobotrobot）动作：删除表：动作：删除表：动作：删除表：动作：删除表：EMPTYEMPTYEMPTYEMPTY（robotrobotrobotrobot），），），），ONONONON（boxboxboxbox，x x x x）添加表：添加表：添加表：添加表：HOLDSHOLDSHOLDSHOLDS（robot,boxrobot,boxrobot,boxrobot,box）SetdownSetdownSetdownSetdown（x x x x）条件：条件：条件：条件：ATATATAT（r
35、obot,xrobot,xrobot,xrobot,x），），），），TABLETABLETABLETABLE（x x x x），），），），HOLDSHOLDSHOLDSHOLDS（robot,boxrobot,boxrobot,boxrobot,box）动作：删除表：动作：删除表：动作：删除表：动作：删除表：HOLDSHOLDSHOLDSHOLDS（robot,boxrobot,boxrobot,boxrobot,box）添加表：添加表：添加表：添加表：EMPTYEMPTYEMPTYEMPTY（robotrobotrobotrobot），），），），ONONONON（box,xbox,xb
36、ox,xbox,x）本讲稿第三十六页，共九十五页 机器人在执行每一操作之前，都需要检查当前状态是否机器人在执行每一操作之前，都需要检查当前状态是否可以满足该操作的先决条件。如果满足，就执行相应的操可以满足该操作的先决条件。如果满足，就执行相应的操作，否则就检查下一个操作所要求的先决条件。作，否则就检查下一个操作所要求的先决条件。作为谓词逻辑知识表示方法的应用，下面给出这个机器作为谓词逻辑知识表示方法的应用，下面给出这个机器人行动规划问题的求解过程。其中，在检查先决条件是否满足人行动规划问题的求解过程。其中，在检查先决条件是否满足时还需要进行变量的置换。时还需要进行变量的置换。谓词逻辑表示的应用
37、谓词逻辑表示的应用本讲稿第三十七页，共九十五页 状态状态状态状态l l l l（初始状态）（初始状态）（初始状态）（初始状态）AT(robot,c)AT(robot,c)AT(robot,c)AT(robot,c)开始开始开始开始 EMPTYEMPTYEMPTYEMPTY（robotrobotrobotrobot）=ON=ON=ON=ON（boxboxboxbox，a a a a）TABLETABLETABLETABLE（a a a a）TABLETABLETABLETABLE（b b b b）GotoGoto（x x，y y）=用用 c c代换代换 x x，a a代换代换 y y状态状态2
38、2ATAT（robot,arobot,a）EMPTYEMPTY（robotrobot）ONON（box,abox,a）TABLETABLE（a a）TABLETABLE（b b）PickupPickup（x x）用用a a代换代换x x 状态状态3 3 ATAT（robotrobot，a a）HOLDSHOLDS（robotrobot，boxbox）TABLETABLE（a a）TABLETABLE（b b）GotoGoto（x x，y y）用用a a代换代换x x，b b代换代换y y 状态状态4 4ATAT（robotrobot，b b）HOLDSHOLDS（robotrobot，boxb
39、ox）TABLETABLE（a a）TABLETABLE（b b）SetdownSetdown（x x）=用用b b代换代换x x状态状态5 5AT(robot,b)AT(robot,b)EMPTYEMPTY（robotrobot）ON(box,b)ON(box,b)TABLETABLE（a a）TABLETABLE（b b）Goto Goto（x x，y y）=用用b b代换代换x x，c c代换代换y y状态状态6 6（目标状态）（目标状态）ATAT（robotrobot，c c）EMPTYEMPTY（robotrobot）ON(box,b)ON(box,b)TABLETABLE（a a）
40、TABLETABLE（b b）本讲稿第三十八页，共九十五页二二.谓词公式的解释谓词公式的解释l设设D是谓词公式是谓词公式P的非空个体域，若对的非空个体域，若对P中的个体常量、函中的个体常量、函数和谓词按如下规定赋值：数和谓词按如下规定赋值：（1）为每个个体常量指派）为每个个体常量指派D中的一个元素；中的一个元素；（2）为每个）为每个n元函数指派一个从元函数指派一个从Dn到到D的一个映射，的一个映射，其中其中 Dn(x1,x2,xn)|x1,x2,xn D （3）为每个）为每个n元谓词指派一个从元谓词指派一个从Dn到到T,F的映射的映射 则称这些指派为则称这些指派为P在在D上的一个解释。上的一个
41、解释。本讲稿第三十九页，共九十五页例例1：设个体域设个体域D=1,2，求公式，求公式A=(x)(y)P(x,y)在在D上的上的解释，并指出在每一种解释下公式解释，并指出在每一种解释下公式A的真值。的真值。P(1,1)P(1,2)P(2,1)P(2,2)TFTFP(1,1)P(1,2)P(2,1)P(2,2)TTFF由上面的例子可以看出，谓词公式的其值都是针对由上面的例子可以看出，谓词公式的其值都是针对某一个解释而言的，它可能在某一个解释下真值为某一个解释而言的，它可能在某一个解释下真值为 T，而在另一个解释下为，而在另一个解释下为 F。本讲稿第四十页，共九十五页例例2：设个体域设个体域D=1，
42、2，求公式，求公式B=（x）P（F（x），），a）在）在D上的解释，并指出在该解释下公式上的解释，并指出在该解释下公式B的真值。的真值。aF(1)F(2)112对个体常量和函数的指派对个体常量和函数的指派P(1,1)P(1,2)P(2,1)P(2,2)TT对谓词的指派对谓词的指派本讲稿第四十一页，共九十五页三三.谓词公式的永真性与可满足性谓词公式的永真性与可满足性l如果谓词公式如果谓词公式P对非空个体域对非空个体域D上的任一解释都取得真值上的任一解释都取得真值T(F)，则称则称P在在D上是上是永真永真(假假)的的；如果；如果P在任何非空个体域上均是永真在任何非空个体域上均是永真(假假)的，则称
43、的，则称P永真永真(假假)。l永假性又称永假性又称不可满足性或不相容性不可满足性或不相容性。l对于谓词公式对于谓词公式 P，如果至少存在，如果至少存在D上的一个解释，使公式上的一个解释，使公式P在在此解释下的真值为此解释下的真值为T，则称公式，则称公式 P在在D上是上是可满足的可满足的。谓词公式。谓词公式的的可满足性可满足性又称为又称为相容性相容性.本讲稿第四十二页，共九十五页四四.谓词公式的等价性与永真蕴含性谓词公式的等价性与永真蕴含性l 谓词公式的等价性和永真蕴含性可分别用相应的等价式和永真蕴谓词公式的等价性和永真蕴含性可分别用相应的等价式和永真蕴含式来表示。含式来表示。l 这些等价式和永
44、真蕴含式都是演绎推理的主要依据，因此也称它这些等价式和永真蕴含式都是演绎推理的主要依据，因此也称它们为们为推理规则推理规则。1 1等价式等价式 谓词公式的等价式可定义如下：谓词公式的等价式可定义如下：定义定义：设：设P P与与Q Q是是D D上的两个谓词公式，若对上的两个谓词公式，若对D D上的任意解释，上的任意解释，P P与与Q Q都有相同的真值，则称都有相同的真值，则称 P P与与Q Q在在D D上是上是等价的等价的。如果。如果D D是任意非空个体是任意非空个体域，则称域，则称 P P与与Q Q是等价的，记作是等价的，记作P PQ Q。本讲稿第四十三页，共九十五页 （1 1 1 1）双重否
45、定率）双重否定率）双重否定率）双重否定率 p p p p p p p p （2 2 2 2）交换率）交换率）交换率）交换率 PQ PQ PQ PQ QP QP QP QP，PQ PQ PQ PQ QPQPQPQP （3 3 3 3）结合率）结合率）结合率）结合率 （PQPQPQPQ）R PR PR PR P（QRQRQRQR）,（PQPQPQPQ）RP RP RP RP（QRQRQRQR）（4 4 4 4）分配率）分配率）分配率）分配率 PPPP（QRQRQRQR）（PQPQPQPQ）（PRPRPRPR）PPPP（QRQRQRQR）（PQPQPQPQ）（PRPRPRPR）（5 5 5 5）狄）
46、狄）狄）狄 摩根定律摩根定律摩根定律摩根定律 （PQPQPQPQ）P Q P Q P Q P Q （PQPQPQPQ）P Q P Q P Q P Q （6 6 6 6）吸收率）吸收率）吸收率）吸收率 PPPP（PQPQPQPQ）PPPP，PPPP（P QP QP QP Q）PPPP （7 7 7 7）补余率）补余率）补余率）补余率 P P T,P P F P P T,P P F P P T,P P F P P T,P P F （8 8 8 8）连词化归率）连词化归率）连词化归率）连词化归率 PQ P QPQ P QPQ P QPQ P Q本讲稿第四十四页，共九十五页2.2.永真蕴含式永真蕴含式
47、定义：定义：定义：定义：对谓词公式对谓词公式对谓词公式对谓词公式 P P P P和和和和 Q Q Q Q，如果，如果，如果，如果 PQPQPQPQ永真，则称永真，则称永真，则称永真，则称 P P P P永真蕴含永真蕴含永真蕴含永真蕴含 Q Q Q Q，且，且，且，且称称称称 Q Q Q Q为为为为 P P P P的逻辑结论，的逻辑结论，的逻辑结论，的逻辑结论，P P P P为为为为Q Q Q Q的前提，记作的前提，记作的前提，记作的前提，记作P=QP=QP=QP=Q。（1 1 1 1）化简式）化简式）化简式）化简式 PQ=PPQ=PPQ=PPQ=P，PQ=QPQ=QPQ=QPQ=Q （2 2
48、2 2）附加式）附加式）附加式）附加式 P=PQP=PQP=PQP=PQ，Q=PQQ=PQQ=PQQ=PQ （3 3 3 3）析取三段论）析取三段论）析取三段论）析取三段论 P P P P，P V Q=QP V Q=QP V Q=QP V Q=Q （4 4 4 4）假言推理）假言推理）假言推理）假言推理 P P P P，PQ=QPQ=QPQ=QPQ=Q （5 5 5 5）拒取式）拒取式）拒取式）拒取式 Q Q Q Q，P Q=PP Q=PP Q=PP Q=P （6 6 6 6）假言三段论）假言三段论）假言三段论）假言三段论 P QP QP QP Q，Q R=P R Q R=P R Q R=P
49、R Q R=P R （7 7 7 7）二难推理）二难推理）二难推理）二难推理 P QP QP QP Q，P RP RP RP R，Q R=RQ R=RQ R=RQ R=R （8 8 8 8）全称固化）全称固化）全称固化）全称固化 （x x x x）P P P P（x x x x）=P=P=P=P（y y y y）其中，其中，y y是个体域中的任一个体，利用此永真蕴含式可消是个体域中的任一个体，利用此永真蕴含式可消去谓词公式中的全程量词。去谓词公式中的全程量词。（9 9 9 9）存在固化）存在固化）存在固化）存在固化 （彐（彐（彐（彐x x x x）P P P P（x x x x）=P=P=P=
50、P（y y y y）其中，其中，y y是个体域中某一个可以使是个体域中某一个可以使P P（y y）为真的个体，利用此）为真的个体，利用此永真蕴含式可消去谓词公式中的存在量词。永真蕴含式可消去谓词公式中的存在量词。本讲稿第四十五页，共九十五页l l 范式范式范式范式是公式的标准形式，公式往往需要变换为同它等价的是公式的标准形式，公式往往需要变换为同它等价的是公式的标准形式，公式往往需要变换为同它等价的是公式的标准形式，公式往往需要变换为同它等价的范式，以便对它们作一般性的处理。范式，以便对它们作一般性的处理。范式，以便对它们作一般性的处理。范式，以便对它们作一般性的处理。l l 在谓词逻辑中，根