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