确定性知识系统综述课件

1第第2章章 确定性知识系统确定性知识系统 按照符号主义的观点，知识是一切智能行为的基础，要使计算机具有智能，按照符号主义的观点，知识是一切智能行为的基础，要使计算机具有智能，首先必须使它拥有知识，并且能够使用知识。首先必须使它拥有知识，并且能够使用知识。2.1 确定性知识系统概述确定性知识系统概述2.2 确定性知识表示方法确定性知识表示方法2.3 确定性知识推理方法确定性知识推理方法2.4 确定性知识系统简介确定性知识系统简介22.1 确定性知识系统概述确定性知识系统概述2.1.1 确定性知识表示概述确定性知识表示概述 1.知识的概念知识的概念 2.知识的类型知识的类型 3.知识表示的概念知识表示的概念 4.知识表示方法知识表示方法2.1.2 确定性知识推理概述确定性知识推理概述31.知识的概念知识的概念一般性观点一般性观点 知识是人们在改造客观世界的实践中积累起来的知识是人们在改造客观世界的实践中积累起来的认识认识和和经验经验信息加工观点信息加工观点 知识是对信息进行智能性加工所形成的对客观世界规律性的认识。知识是对信息进行智能性加工所形成的对客观世界规律性的认识。知识知识=信息信息+关联关联 常用的关联形式：常用的关联形式：如果如果 ,则则 代表性解释代表性解释 (1)Feigenbaum:知识是经过剪裁、塑造、解释、选择和转换了的信息知识是经过剪裁、塑造、解释、选择和转换了的信息 (2)Bernstein：知识由特定领域的描述、关系和过程组成知识由特定领域的描述、关系和过程组成 (3)Heyes-Roth：知识知识=事实事实+信念信念+启发式启发式42.知识的类型知识的类型按知识的适用范围按知识的适用范围 常识性知识：常识性知识：通用通识的、普遍知道的、适应所有领域的知识。通用通识的、普遍知道的、适应所有领域的知识。领域性知识：领域性知识：面向某个具体专业领域的知识。如：专家经验。面向某个具体专业领域的知识。如：专家经验。按知识的作用效果按知识的作用效果 陈述性知识或事实性知识（零级）：陈述性知识或事实性知识（零级）：用于描述事物的概念、定义、属性，用于描述事物的概念、定义、属性，或状态、环境、条件等；回答或状态、环境、条件等；回答“是什么？是什么？”、“为什么？为什么？”过程性知识或程序性知识（一级）：过程性知识或程序性知识（一级）：用于问题求解过程的操作、演算和行用于问题求解过程的操作、演算和行为的知识，即如何使用事实性知识的知识。回答为的知识，即如何使用事实性知识的知识。回答“怎么做？怎么做？”控制性知识或策略性知识（二级）：控制性知识或策略性知识（二级）：是关于如何使用过程性知识的知识，是关于如何使用过程性知识的知识，如：推理策略、搜索策略、不确定性的传播策略。如：推理策略、搜索策略、不确定性的传播策略。按知识的确定性按知识的确定性 确定性知识：确定性知识：可以给出其可以给出其“真真”、“假假”的知识。的知识。不确定性知识：不确定性知识：具有不确定特性（不精确、模糊、不完备）的知识。具有不确定特性（不精确、模糊、不完备）的知识。53.知识表示的概念知识表示的概念知识表示的解释知识表示的解释 知识表示是对知识的描述，即用一组符号把知识编码成计算机可以接受的知识表示是对知识的描述，即用一组符号把知识编码成计算机可以接受的某种结构。其表示方法不唯一。某种结构。其表示方法不唯一。知识表示的要求知识表示的要求 表示能力：表示能力：是指能否正确、有效地将问题求解所需要的知识表示出来。是指能否正确、有效地将问题求解所需要的知识表示出来。可利用性：可利用性：是指表示方法应有利于进行有效的知识推理。包括：对推理的是指表示方法应有利于进行有效的知识推理。包括：对推理的适应性，对高效算法的支持程度适应性，对高效算法的支持程度 可组织性与可维护性：可组织性与可维护性：可组织性是指可以按某种方式把知识组织成某种知识结构。可组织性是指可以按某种方式把知识组织成某种知识结构。可维护性是指要便于对知识的增、删、改等操作可维护性是指要便于对知识的增、删、改等操作 可理解性与可实现性：可理解性与可实现性：可理解性是指知识应易读、易懂、易获取等可理解性是指知识应易读、易懂、易获取等 可实现性是指知识的表示要便于计算机上实现可实现性是指知识的表示要便于计算机上实现64.知识表示方法知识表示方法 知识表示方法也称知识表示技术，其表示形式被称为知识表示模式。知识表示方法也称知识表示技术，其表示形式被称为知识表示模式。知识表示的类型知识表示的类型 按知识的不同存储方式：按知识的不同存储方式：陈述性知识：陈述性知识：知识用某种数据结构来表示；知识用某种数据结构来表示；知识本身和使用知识的过程相分离。知识本身和使用知识的过程相分离。过程性知识：过程性知识：知识和使用知识的过程结合在一起。知识和使用知识的过程结合在一起。知识表示的基本方法知识表示的基本方法 非结构化方法：非结构化方法：一阶谓词逻辑一阶谓词逻辑 产生式规则产生式规则 结构化方法：结构化方法：语义网络语义网络 框架框架知识表示的其它方法知识表示的其它方法 状态空间法和问题归约法。放在搜索中讨论。状态空间法和问题归约法。放在搜索中讨论。72.1 确定性知识系统概述确定性知识系统概述2.1.1 确定性知识表示概述确定性知识表示概述2.1.2 确定性知识推理概述确定性知识推理概述 1.推理的概念推理的概念 2.推理方法及其分类推理方法及其分类 3.推理控制策略及其分类推理控制策略及其分类8 按照心理学的观点，推理是由具体事例归纳出一般规律，或者根据已有知按照心理学的观点，推理是由具体事例归纳出一般规律，或者根据已有知识推出新的结论的思维过程。心理学对推理有两种解释：识推出新的结论的思维过程。心理学对推理有两种解释：从结构的角度：从结构的角度：推理由两个以上的判断所组成推理由两个以上的判断所组成，是一种对已有判断进行分析和综合，再得，是一种对已有判断进行分析和综合，再得出新的判断的过程。例如，若有以下两个判断：出新的判断的过程。例如，若有以下两个判断：计算机系的学生都会编程序；计算机系的学生都会编程序；程强是计算机系的一名学生；程强是计算机系的一名学生；则可得出下面第三个判断：则可得出下面第三个判断：程强会编程序。程强会编程序。从过程的角度：从过程的角度：认为推理是在给定信息和已有知识的基础上的一系列加工操作，提出了如认为推理是在给定信息和已有知识的基础上的一系列加工操作，提出了如下人类推理的公式：下人类推理的公式：y=F(x,k)其中，其中，x为推理时给出的信息，为推理时给出的信息，k为推理时可用的领域知识和特殊事例，为推理时可用的领域知识和特殊事例，F为为可用的一系列操作，可用的一系列操作，y为推理过程所得到的结论。为推理过程所得到的结论。1.推理的概念推理的概念推理的心理学观点推理的心理学观点9推理过程的心理形式推理过程的心理形式 从心理学的角度，推理是一种心理过程。可有以下几种主要形式：从心理学的角度，推理是一种心理过程。可有以下几种主要形式：(1)三段论推理三段论推理 由两个假定真实的前提和一个可能符合也可能不符合这两前提的结论组成。由两个假定真实的前提和一个可能符合也可能不符合这两前提的结论组成。(2)线性推理线性推理 或称线性三段论，这种推理的三个判断之间具有线性关系。或称线性三段论，这种推理的三个判断之间具有线性关系。(3)条件推理条件推理 即前一命题是后一命题的条件。即前一命题是后一命题的条件。(4)概率推理概率推理 即用概率来表示知识的不确定性，并根据所给出的概率来估计新的概率。即用概率来表示知识的不确定性，并根据所给出的概率来估计新的概率。推理的机器实现推理的机器实现 人工智能中的推理是由推理机完成的。所谓推理机，是指系统中用来实现人工智能中的推理是由推理机完成的。所谓推理机，是指系统中用来实现推理的那段程序。推理的那段程序。根据推理所用知识的不同，推理方式和推理方法的不同，推理机的构造也根据推理所用知识的不同，推理方式和推理方法的不同，推理机的构造也有所不同。有所不同。1.推理的概念推理的概念推理的心理过程推理的心理过程102.推理方法及其分类推理方法及其分类推理方法解决的主要问题：推理方法解决的主要问题：推理过程中前提与结论之间的逻辑关系；推理过程中前提与结论之间的逻辑关系；不确定性推理中不确定性的传递问题。不确定性推理中不确定性的传递问题。推理方法的分类形式：推理方法的分类形式：可有多种不同的分类方法可有多种不同的分类方法.例如例如:分类分类按推理的逻辑基础按推理的逻辑基础按知识的确定性按知识的确定性按推理的控制策略按推理的控制策略演绎推理演绎推理归纳推理归纳推理确定性推理确定性推理不确定性推理不确定性推理(第第5章单独讨论章单独讨论)推理策略推理策略搜索理策略搜索理策略(第第3章单独讨论章单独讨论)112.推理方法及其分类推理方法及其分类按推理的逻辑基础分类按推理的逻辑基础分类(1/3)演绎推理演绎推理 是一种由一般到个别的推理方法。是一种由一般到个别的推理方法。其其核心是三段论核心是三段论，如假言推理、拒取式和假言三段论。，如假言推理、拒取式和假言三段论。例：例：假言三段论假言三段论 AB，BC AC 常用的三段论是以下三部分组成的：常用的三段论是以下三部分组成的：大前提：大前提：是已知的一般性知识或推理过程得到的判断；是已知的一般性知识或推理过程得到的判断；小前提：小前提：是关于某种具体情况或某个具体实例的判断；是关于某种具体情况或某个具体实例的判断；结论：结论：是由大前提推出的，并且适合于小前提的判断。是由大前提推出的，并且适合于小前提的判断。例如，前面所提到的例子有如下三个判断：例如，前面所提到的例子有如下三个判断：计算机系的学生都会编程序；计算机系的学生都会编程序；（是大前提，一般性知识）是大前提，一般性知识）程强是计算机系的一位学生；程强是计算机系的一位学生；（是小前提，具体情况）是小前提，具体情况）程强会编程序。程强会编程序。（是经演绎推出来的结论结论）是经演绎推出来的结论结论）122.推理方法及其分类推理方法及其分类按推理的逻辑基础分类按推理的逻辑基础分类(2/3)归纳推理归纳推理是一种由个别到一般的推理方法。归纳推理的类型是一种由个别到一般的推理方法。归纳推理的类型 按照所选事例的广泛性按照所选事例的广泛性可分为完全归纳推理和不完全归纳推理可分为完全归纳推理和不完全归纳推理 按照推理所使用的方法按照推理所使用的方法可分为枚举、类比、统计和差异归纳推理等可分为枚举、类比、统计和差异归纳推理等 完全归纳推理完全归纳推理 是指在进行归纳时需要考察相应事物的全部对象，并根据这些对象是否都是指在进行归纳时需要考察相应事物的全部对象，并根据这些对象是否都具有某种属性，推出该类事物是否具有此属性。具有某种属性，推出该类事物是否具有此属性。所有的太阳系大行星都是沿着椭圆轨道绕太阳运行的所有的太阳系大行星都是沿着椭圆轨道绕太阳运行的 不完全归纳推理不完全归纳推理 是指在进行归纳时只考察了相应事物的部分对象，就得出了关于该事物的是指在进行归纳时只考察了相应事物的部分对象，就得出了关于该事物的结论。结论。内经内经针刺篇针刺篇：患头痛的樵夫：患头痛的樵夫 132.推理方法及其分类推理方法及其分类按推理的逻辑基础分类按推理的逻辑基础分类(2/3)归纳推理归纳推理枚举归纳推理枚举归纳推理 是指在进行归纳时，如果已知某类事物的有限可数个具体事物都具有某种是指在进行归纳时，如果已知某类事物的有限可数个具体事物都具有某种属性，则可推出该类事物都具有此种属性。属性，则可推出该类事物都具有此种属性。-以偏概全以偏概全 种瓜得瓜，种豆得豆；瑞雪兆丰年种瓜得瓜，种豆得豆；瑞雪兆丰年 类比归纳推理类比归纳推理 是指在两个或两类事物有许多属性都相同或相似的基础上，推出它们在其是指在两个或两类事物有许多属性都相同或相似的基础上，推出它们在其他属性上也相同或相似的一种归纳推理。其推理模式可表示为：他属性上也相同或相似的一种归纳推理。其推理模式可表示为：IF A有属性有属性abc AND B有属性有属性ab THEN B可能有属性可能有属性c阳光：紫外线A.电脑：辐射 B.海水：氯化钠 C.混合物：单质 D.微波炉：微波考试：学生：成绩A.往来：网民：电子邮件 B.汽车：司机：驾驶执照C.工作：职员：工资待遇 D.饭菜：厨师：色鲜味美142.推理方法及其分类推理方法及其分类 按推理的逻辑基础分类按推理的逻辑基础分类(3/3)演绎推理与归纳推理的区别演绎推理与归纳推理的区别 演绎推理演绎推理是在已知领域内的一般性知识的前提下，通过演绎求解一个具体是在已知领域内的一般性知识的前提下，通过演绎求解一个具体问题或者证明一个结论的正确性。它所得出的结论实际上早已蕴含在一般性问题或者证明一个结论的正确性。它所得出的结论实际上早已蕴含在一般性知识的前提中，演绎推理只不过是将已有事实揭露出来，因此它知识的前提中，演绎推理只不过是将已有事实揭露出来，因此它不能增殖新不能增殖新知识知识。归纳推理归纳推理所推出的结论是没有包含在前提内容中的。这种由个别事物或现所推出的结论是没有包含在前提内容中的。这种由个别事物或现象推出一般性知识的过程，象推出一般性知识的过程，是增殖新知识是增殖新知识的过程。的过程。例如，例如，一位计算机维修员，从书本知识，到通过大量实例积累经验，是一一位计算机维修员，从书本知识，到通过大量实例积累经验，是一种种归纳归纳推理方式。运用这些一般性知识知识去维修计算机的过程则是推理方式。运用这些一般性知识知识去维修计算机的过程则是演绎演绎推推理。理。152.推理方法及其分类推理方法及其分类 按所用知识的确定性分类按所用知识的确定性分类 确定性推理确定性推理 指推理所用知识和推出的结论都是可以精确表示的。本章讨论：指推理所用知识和推出的结论都是可以精确表示的。本章讨论：产生式推理产生式推理 自然演绎推理自然演绎推理 归结演绎推理归结演绎推理 不确定性推理不确定性推理 指推理所用知识和推出的结论都是不确定的。放在第指推理所用知识和推出的结论都是不确定的。放在第5章讨论：章讨论：可信度推理可信度推理 主观主观Bayes推理推理 证据理论证据理论 模糊推理模糊推理 概率推理概率推理163.推理控制策略及其分类推理控制策略及其分类推理的控制策略推理的控制策略 推理的控制策略是指推理的控制策略是指如何使用领域知识使推理过程尽快达到目标的策略。如何使用领域知识使推理过程尽快达到目标的策略。它它可分为可分为推理策略和搜索策略推理策略和搜索策略。推理策略推理策略 主要解决推理方向、冲突消解等问题，如推理方向控制策略、求解策略、主要解决推理方向、冲突消解等问题，如推理方向控制策略、求解策略、限制策略、冲突消解策略等限制策略、冲突消解策略等 推理方向控制策略推理方向控制策略用于确定推理的控制方向，可分为正向推理、逆向推理、用于确定推理的控制方向，可分为正向推理、逆向推理、混合推理及双向推理。混合推理及双向推理。求解策略求解策略是指仅求一个解，还是求所有解或最优解等。是指仅求一个解，还是求所有解或最优解等。限制策略限制策略是指对推理的深度、宽度、时间、空间等进行的限制。是指对推理的深度、宽度、时间、空间等进行的限制。冲突消解策略冲突消解策略是指当推理过程有多条知识可用时，如何从这多条可用知识是指当推理过程有多条知识可用时，如何从这多条可用知识中选出一条最佳知识用于推理的策略。中选出一条最佳知识用于推理的策略。搜索策略搜索策略 主要解决主要解决推理线路、推理效果、推理效率等问题推理线路、推理效果、推理效率等问题。本章主要讨论推理策略，本章主要讨论推理策略，至于搜索策略将放到下一章单独讨论。至于搜索策略将放到下一章单独讨论。17第第2章章 确定性知识系统确定性知识系统 按照符号主义的观点，知识是一切智能行为的基础，要使计算机具有智能，按照符号主义的观点，知识是一切智能行为的基础，要使计算机具有智能，首先必须使它拥有知识，并且能够使用知识。首先必须使它拥有知识，并且能够使用知识。2.1 确定性知识系统概述确定性知识系统概述2.2 确定性知识表示方法确定性知识表示方法2.3 确定性知识推理方法确定性知识推理方法2.4 确定性知识系统简介确定性知识系统简介182.2 确定性知识表示方法确定性知识表示方法2.2.1 谓词逻辑表示法谓词逻辑表示法 1.谓词逻辑表示的逻辑学基础谓词逻辑表示的逻辑学基础 2.谓词逻辑表示方法谓词逻辑表示方法 3.谓词逻辑表示的应用谓词逻辑表示的应用 4.谓词逻辑表示的特性谓词逻辑表示的特性2.2.2 产生式表示法产生式表示法2.2.3 语义网络表示法语义网络表示法2.2.4 框架表示法框架表示法191.谓词逻辑表示的逻辑学基础谓词逻辑表示的逻辑学基础命题、真值、论域命题、真值、论域命题命题 断言：断言：一个陈述句称为一个断言一个陈述句称为一个断言.命题：命题：具有真假意义的断言称为命题具有真假意义的断言称为命题.（定义（定义2.1）真值真值 T：表示命题的意义为真表示命题的意义为真 F：表示命题的意义为假表示命题的意义为假论域论域 由所讨论对象的全体构成的集合。也称为个体域由所讨论对象的全体构成的集合。也称为个体域 论域中的元素称为个体论域中的元素称为个体201.谓词表示的逻辑学基础谓词表示的逻辑学基础谓词、函数谓词、函数 谓词谓词 用来表示谓词逻辑中命题，形如用来表示谓词逻辑中命题，形如P(x1,x2,xn)。其中。其中 P是谓词名，即命题的谓语，表示个体的性质、状态或个体之间的关系；是谓词名，即命题的谓语，表示个体的性质、状态或个体之间的关系；x1,x2,xn是个体，即命题的主语，表示独立存在的事物或概念。是个体，即命题的主语，表示独立存在的事物或概念。定义定义2.2：设设D是个体域，是个体域，P：DnT，F是一个映射，其中是一个映射，其中 则称则称P是一个是一个n元谓词，记为元谓词，记为P(x1,x2,xn)，其中，其中，x1,x2,xn为个体，可以是为个体，可以是个体常量、变元和函数。个体常量、变元和函数。例如：例如：GREATER(x,6)，表示，表示x大于大于6，函数：函数：可作为谓词的个体可作为谓词的个体 定义定义2.3：设设D是个体域，是个体域，f：DnD是一个映射，其中是一个映射，其中谓词与函数的区别：谓词与函数的区别：谓词是谓词是D到到T，F的映射，函数是的映射，函数是D到到D的映射的映射 谓词的真值是谓词的真值是T和和F，函数的值（无真值）是，函数的值（无真值）是D中的元素中的元素 谓词可独立存在，函数只能作为谓词的个体谓词可独立存在，函数只能作为谓词的个体211.谓词逻辑表示逻辑学基础谓词逻辑表示逻辑学基础连词和量词连词和量词连词：连词：“非非”或者或者“否定否定”。表示对其后面的命题的否定表示对其后面的命题的否定 ：“析取析取”。表示所连结的两个命题之间具有表示所连结的两个命题之间具有“或或”的关系的关系 ：“合取合取”。表示所连结的两个命题之间具有表示所连结的两个命题之间具有“与与”的关系。的关系。：“条件条件”或或“蕴含蕴含”。表示表示“若若则则”的语义。读作的语义。读作“如果如果P，则，则Q”其中，其中，P称为条件的前件，称为条件的前件，Q称为条件的后件。称为条件的后件。：称为：称为“双条件双条件”。它表示它表示“当且仅当当且仅当”的语义。即读作的语义。即读作“P当且仅当当且仅当Q”。例如，对命题例如，对命题P和和Q，PQ表示表示“P当且仅当当且仅当Q”，量词：量词：全称量词。：全称量词。意思是意思是“所有的所有的”、“任一个任一个”命题命题(x)P(x)为真，当且仅当对论域中的所有为真，当且仅当对论域中的所有x，都有，都有P(x)为真为真 命题命题(x)P(x)为假，当且仅当至少存在一个为假，当且仅当至少存在一个xi D，使得，使得P(xi)为假为假 ：存在量词，：存在量词，意思是意思是“至少有一个至少有一个”、“存在有存在有”命题命题(x)P(x)为真，当且仅当至少存在一个为真，当且仅当至少存在一个xi D，使得，使得P(xi)为真为真 命题命题(x)P(x)为假，当且仅当对论域中的所有为假，当且仅当对论域中的所有x，都有，都有P(x)为假为假 221.谓词逻辑表示的逻辑学基础谓词逻辑表示的逻辑学基础自由变元和约束变元自由变元和约束变元辖域：辖域：指位于量词后面的单个谓词或者用括弧括起来的合式公式指位于量词后面的单个谓词或者用括弧括起来的合式公式约束变元：约束变元：辖域内与量词中同名的变元称为约束变元辖域内与量词中同名的变元称为约束变元自由变元：自由变元：不受约束的变元称为自由变元不受约束的变元称为自由变元 例子：例子：(x)(P(x，y)Q(x，y)R(x，y)其中，其中，(P(x，y)Q(x，y)是是(x)的辖域的辖域 辖域内的变元辖域内的变元x是受是受(x)约束的变元约束的变元 R(x，y)中的中的x和所有的和所有的y都是自由变元都是自由变元变元的换名：变元的换名：谓词公式中的变元可以换名。但需注意：谓词公式中的变元可以换名。但需注意：第一：对约束变元，必须把同名的约束变元都统一换成另外一个相同的名第一：对约束变元，必须把同名的约束变元都统一换成另外一个相同的名字，且不能与辖域内的自由变元同名。字，且不能与辖域内的自由变元同名。例，对例，对(x)P(x，y)，可把约束变元，可把约束变元x换成换成z，得到公式，得到公式(z)P(z，y)。第二：对辖域内的自由变元，不能改成与约束变元相同的名字。第二：对辖域内的自由变元，不能改成与约束变元相同的名字。例，对例，对(x)P(x，y)，可把，可把y换成换成t，得到，得到(x)P(x，t)，但不能换成，但不能换成x。232.谓词逻辑表示方法谓词逻辑表示方法表示步骤及简例表示步骤及简例(1/2)表示步骤表示步骤 (1)先根据要表示的知识定义谓词先根据要表示的知识定义谓词 (2)再用连词、量词把这些谓词连接起来再用连词、量词把这些谓词连接起来简例简例 例例2.1 表示知识表示知识“所有教师都有自己的学生所有教师都有自己的学生”。解：解：先定义谓词：先定义谓词：T(x)：表示：表示x 是教师。是教师。S(y)：表示：表示y是学生。是学生。TS(x,y)：表示：表示x是是y的老师。的老师。然后将知识表示如下：然后将知识表示如下：(x)(y)(T(x)TS(x,y)S(y)可读作：对所有可读作：对所有x，如果，如果x是一个教师，那么一定存在一个个体是一个教师，那么一定存在一个个体y，y是学是学生，且生，且x是是y的老师。的老师。242.谓词逻辑表示方法谓词逻辑表示方法表示步骤及简例表示步骤及简例(2/2)例例2.2 表示知识表示知识“所有的整数不是偶数就是奇数所有的整数不是偶数就是奇数”。解：解：先定义谓词：先定义谓词：I(x)：x是整数，是整数，E(x)：x是偶数，是偶数，O(x)：x是奇数是奇数然后再将知识表示为：然后再将知识表示为：(x)(I(x)E(x)O(x)例例2.3 表示如下知识：表示如下知识：王宏是计算机系的一名学生。王宏是计算机系的一名学生。王宏和李明是同班同学。王宏和李明是同班同学。凡是计算机系的学生都喜欢编程序。凡是计算机系的学生都喜欢编程序。解：解：先定义谓词：先定义谓词：CS(x)：表示：表示x是计算机系的学生。是计算机系的学生。CM(x,y)：表示：表示x和和y是同班同学。是同班同学。L(x,y)：表示：表示x喜欢喜欢y。然后再将知识表示为：然后再将知识表示为：CS(Wang hong)CM(Wanghong,Li ming)(x)(CS(x)L(x,programming)25谓词逻辑表示的应用谓词逻辑表示的应用-机器人移盒子问题（一）机器人移盒子问题（一）智能规划智能规划NP旅行规划、自动武器等旅行规划、自动武器等谓词可用来描述状态、动作谓词可用来描述状态、动作:机器人从机器人从c点出发，将盒子从点出发，将盒子从a桌拿到桌拿到b桌，然后再桌，然后再回到回到c处。处。研究的对象：研究的对象：桌子桌子x的个体域是的个体域是a,b 机器人机器人y的个体域是的个体域是robot 位置位置z的个体域是的个体域是a,b,c 物体物体w的个体域是的个体域是box描述状态的谓词：描述状态的谓词：TABLE(x)：x是桌子是桌子 EMPTY(y)：y手中是空的手中是空的 AT(y,z)：y在在z的附近的附近 HOLDS(y,w)：y拿着拿着w ON(w,x)：w在在x桌面上桌面上abc26谓词逻辑表示的应用谓词逻辑表示的应用-机器人移盒子问题（二）机器人移盒子问题（二）问题的初始状态问题的初始状态 AT(robot,c)EMPTY(robot)ON(box,a)TABLE(a)TABLE(b)问题的目标状态问题的目标状态 AT(robot,c)EMPTY(robot)ON(box,b)TABLE(a)TABLE(b)机器人行动的目标把问题的初始状态转换为目标状态，而要实现问题机器人行动的目标把问题的初始状态转换为目标状态，而要实现问题状态的转换需要完成一系列的操作状态的转换需要完成一系列的操作abc27谓词逻辑表示的应用谓词逻辑表示的应用-机器人移盒子问题（三）机器人移盒子问题（三）操作的表示方法操作的表示方法 由由条件和动作条件和动作两部分两部分 条件部分条件部分用来说明执行该操作必须具备的先决条件用来说明执行该操作必须具备的先决条件 可用谓词公式来表示可用谓词公式来表示 动作部分动作部分给出了该操作对问题状态的改变情况给出了该操作对问题状态的改变情况 动作部分则是通过在执行该操作前的问题状态中删去和增加相应动作部分则是通过在执行该操作前的问题状态中删去和增加相应的谓词来实现的的谓词来实现的机器人需要执行的操作机器人需要执行的操作 Goto(x,y)：从：从x处走到处走到y处。处。Pickup(x)：在：在x处拿起盒子。处拿起盒子。Setdown(x)：在：在x处放下盒子。处放下盒子。abc28谓词逻辑表示的应用谓词逻辑表示的应用-机器人移盒子问题（三）机器人移盒子问题（三）操作对应的条件和动作如下操作对应的条件和动作如下Goto(x，y)条件：条件：AT(robot，x)动作：删除表：动作：删除表：AT(robot，x)添加表：添加表：AT(robot，y)Pickup(x)条件：条件：ON(box，x)，TABLE(x)，AT(robot，x)，EMPTY(robot)动作：删除表：动作：删除表：EMPTY(robot)，ON(box，x)添加表：添加表：HOLDS(robot，box)Setdown(x)条件：条件：AT(robot，x)，TABLE(x)，HOLDS(robot，box)动作：删除表：动作：删除表：HOLDS(robot，box)添加表：添加表：EMPTY(robot)，ON(box，x)机器人在执行每一操作之前，都需要检查当前状态是否可以满足该机器人在执行每一操作之前，都需要检查当前状态是否可以满足该操作的先决条件。操作的先决条件。如果满足，如果满足，就执行相应的操作，就执行相应的操作，否则否则就检查下一个操就检查下一个操作所要求的先决条件。作所要求的先决条件。(归结理论归结理论)abc29谓词逻辑表示的应用谓词逻辑表示的应用-机器人移盒子问题（四）机器人移盒子问题（四）这个这个机器人行动规划机器人行动规划问题的问题的求解过程如下：求解过程如下：状态状态1(初始状态初始状态)AT(robot,c)开始开始 EMPTY(robot)=ON(box,a)TABLE(a)TABLE(b)状态状态2 AT(robot,a)Goto(x,y)EMPTY(robot)=ON(box,a)用用c代换代换x TABLE(a)a代换代换y TABLE(b)状态状态3 AT(robot,a)Pickup(x)HOLDS(robot,box)=TABLE(a)用用a代换代换x TABLE(b)abc30谓词逻辑表示的应用谓词逻辑表示的应用-机器人移盒子问题（五）机器人移盒子问题（五）状态状态4 AT(robot,b)Goto(x,y)HOLDS(robot,box)=TABLE(a)用用a代换代换x TABLE(b)b代换代换y 状态状态5 AT(robot,b)Setdown(x)EMPTY(robot)=ON(box,b)用用b代换代换x TABLE(a)TABLE(b)状态状态6(目标状态目标状态)AT(robot,c)Goto(x,y)EMPTY(robot)=ON(box,b)用用b代换代换x TABLE(a)c代换代换y TABLE(b)abc31谓词逻辑表示的应用（续）32谓词逻辑表示的应用谓词逻辑表示的应用-机器人摞积木问题（一）机器人摞积木问题（一）描述状态的谓词描述状态的谓词(看图找谓词，看图找谓词，TABLEEMPTY)CLEAR(x)：积木：积木x上面是空的上面是空的 ON(x,y)：积木：积木x在积木在积木y的上面的上面 ONTABLE(x)：积木：积木x在桌子上在桌子上 HOLDING(x)：机械手抓住：机械手抓住x HANDEMPTY：机械手是空的：机械手是空的其中，其中，x和和y的个体域都是的个体域都是A,B,C问题的初始状态问题的初始状态 CLEAR(B),ON(C,A),ONTABLE(A),CLEAR(C)HANDEMPTY,ONTABLE(B)问题的目标状态是问题的目标状态是 ON(B,C),ON(A,B),ONTABLE(C)CLEAR(A),HANDEMPTYABCABC初态目标机械手33谓词逻辑表示的应用谓词逻辑表示的应用-机器人摞积木问题（二）机器人摞积木问题（二）需要的需要的4个操作个操作 Pickup(x)：从桌面上拣起一块积木：从桌面上拣起一块积木x Putdown(x)：将手中的积木：将手中的积木x放到桌子上放到桌子上 Stack(x,y)：把积木：把积木x摞在积木摞在积木y上上 Upstack(x,y)：把积木：把积木x从积木从积木y上面拣起上面拣起操作对应的先决条件及动作操作对应的先决条件及动作 Pickup(x)(从桌面上拣起一块积木从桌面上拣起一块积木x)条件：条件：ONTABLE(x)，HANDEMPTY，CLEAR(x)动作：删除表：动作：删除表：ONTABLE(x)，HANDEMPTY，CLEAR(x)添加表：添加表：HOLDING(x)Putdown(x)（将手中的积木（将手中的积木x放到桌子上）放到桌子上）条件：条件：HOLDING(x)动作：删除表：动作：删除表：HOLDING(x)添加表：添加表：ONTABLE(x)，HANDEMPTY，CLEAR(x)ABC初态目标机械手34谓词逻辑表示的应用谓词逻辑表示的应用-机器人摞积木问题（三）机器人摞积木问题（三）Stack(x,y)（把积木（把积木x摞在积木摞在积木y上）上）条件：条件：HOLDING(x)，CLEAR(y)动作：删除表：动作：删除表：HOLDING(x)，CLEAR(y)添加表：添加表：HANDEMPTY，ON(x,y)，CLEAR(x)Upstack(x,y)（把积木（把积木x从积木从积木y上面拣起）上面拣起）条件：条件：HANDEMPTY，CLEAR(x)，ON(x,y)动作：删除表：动作：删除表：HANDEMPTY，ON(x,y)添加表：添加表：HOLDING(x)，CLEAR(y)利用上述谓词和操作，即可完成积木世界的求解问题。至于其求解利用上述谓词和操作，即可完成积木世界的求解问题。至于其求解过程，和前述机器人搬盒子问题类似，这里从略。过程，和前述机器人搬盒子问题类似，这里从略。ABC初态目标机械手35谓词逻辑表示的练习谓词逻辑表示的练习-猴子摘香蕉问题（一）猴子摘香蕉问题（一）描述状态的谓词描述状态的谓词 AT(x,y)：x在在y处处 ONBOX：猴子在箱子上：猴子在箱子上 HB：猴子得到香蕉：猴子得到香蕉其中，其中，x 的个体域是的个体域是 Monkey,Box,BananaY 的个体域是的个体域是 a,b,c问题的初始状态问题的初始状态 AT(Monkey,a)AT(Box,b)ONBOX，HB问题的目标状态问题的目标状态 AT(Monkey,c)，AT(Box,c)ONBOX，HBabc36谓词逻辑表示的应用谓词逻辑表示的应用-猴子摘香蕉问题（二）猴子摘香蕉问题（二）需要的操作需要的操作 Goto(u,v)：猴子从猴子从u处走到处走到v处处 Pushbox(v,w)：猴子推着箱子从：猴子推着箱子从v处移到处移到w处处 Climbbox：猴子爬上箱子猴子爬上箱子 Grasp：猴子摘取香蕉猴子摘取香蕉 abc37谓词逻辑表示的应用谓词逻辑表示的应用-猴子摘香蕉问题（二）猴子摘香蕉问题（二）操作对应的先决条件及动作操作对应的先决条件及动作Goto(u,v)条件：条件：ONBOX，AT(Monkey,u)，动作：删除表：动作：删除表：AT(Monkey,u)添加表：添加表：AT(Monkey,v)Pushbox(v,w)条件：条件：ONBOX，AT(Monkey,v)，AT(Box,v)动作：删除表：动作：删除表：AT(Monkey,v)，AT(Box,v)添加表：添加表：AT(Monkey,w)，AT(Box,w)Climbbox 条件：条件：ONBOX，AT(Monkey,w)，AT(Box,w)动作：删除表：动作：删除表：ONBOX 添加表：添加表：ONBOXGrasp 条件：条件：ONBOX，AT(Box,c)动作：删除表：动作：删除表：HB 添加表：添加表：HBabcl请写出猴子摘香蕉的求解过程请写出猴子摘香蕉的求解过程38猴子摘香蕉问题的求解过程如下：猴子摘香蕉问题的求解过程如下：状态状态1（初始状态）（初始状态）AT(monkey,a)开始开始 AT(box,b)=ONBOX HB 状态状态2 AT(monkey,b)Goto(a,b)AT(box,b)=ONBOX HB 状态状态3 AT(monkey,c)Pushbox(b,c)AT(box,c)=ONBOX HB 3.谓词逻辑表示的经典例子谓词逻辑表示的经典例子猴子摘香蕉猴子摘香蕉(3/4)39 状态状态4 AT(monkey,c)Climbbox AT(box,c)=ONBOX HB 状态状态5(目标状态目标状态)AT(monkey,c)Grasp AT(box,c)=ONBOX HB 3.谓词逻辑表示的经典例子谓词逻辑表示的经典例子猴子摘香蕉猴子摘香蕉(4/4)404.谓词逻辑表示的特征谓词逻辑表示的特征主要优点主要优点 自然：自然：一阶谓词逻辑是一种接近于自然语言的形式语言系统，谓词逻辑表一阶谓词逻辑是一种接近于自然语言的形式语言系统，谓词逻辑表示法接近于人们对问题的直观理解示法接近于人们对问题的直观理解 明确：明确：有一种标准的知识解释方法，因此用这种方法表示的知识明确、易有一种标准的知识解释方法，因此用这种方法表示的知识明确、易于理解于理解 精确：精确：谓词逻辑的真值只有谓词逻辑的真值只有“真真”与与“假假”，其表示、推理都是精确的，其表示、推理都是精确的 灵活：灵活：知识和处理知识的程序是分开的，无须考虑处理知识的细节知识和处理知识的程序是分开的，无须考虑处理知识的细节 模块化：模块化：知识之间相对独立，这种模块性使得添加、删除、修改知识比知识之间相对独立，这种模块性使得添加、删除、修改知识比较容易进行较容易进行主要缺点主要缺点 知识表示能力差：知识表示能力差：只能表示确定性知识，而不能表示非确定性知识、过程只能表示确定性知识，而不能表示非确定性知识、过程性知识和启发式知识性知识和启发式知识 知识库管理困难：知识库管理困难：缺乏知识的组织原则，知识库管理比较困难缺乏知识的组织原则，知识库管理比较困难 存在组合爆炸：存在组合爆炸：由于难以表示启发式知识，因此只能盲目地使用推理规则，由于难以表示启发式知识，因此只能盲目地使用推理规则，这样当系统知识量较大时，容易发生组合爆炸这样当系统知识量较大时，容易发生组合爆炸 系统效率低：系统效率低：它把推理演算与知识含义截然分开，抛弃了表达内容中所含它把推理演算与知识含义截然分开，抛弃了表达内容中所含有的语义信息，往往使推理过程冗长，降低了系统效率有的语义信息，往往使推理过程冗长，降低了系统效率 作作 业业 1.用谓词逻辑知识表示方法表示如下知识：用谓词逻辑知识表示方法表示如下知识：(1)有人喜欢梅花，有人喜欢菊花，有人既喜欢梅花又喜欢菊有人喜欢梅花，有人喜欢菊花，有人既喜欢梅花又喜欢菊花。花。(2)不是每个计算机系的学生都喜欢在计算机上编程序。不是每个计算机系的学生都喜欢在计算机上编程序。解：解：(1)定义谓词定义谓词 P(x)：x是人是人 L(x,y)：x喜欢喜欢y 其中，其中，y的个体域是的个体域是梅花，菊花梅花，菊花。将知识用谓词表示为：将知识用谓词表示为：(x)(P(x)L(x,梅花梅花)L(x,菊花菊花)L(x,梅花梅花)L(x,菊花菊花)解：解：(2)定义谓词定义谓词 S(x)：x是计算机系学生是计算机系学生 L(x,pragramming)：x喜欢编程序喜欢编程序 U(x,computer)：x使用计算机使用计算机 将知识用谓词表示为：将知识用谓词表示为：(x)(S(x)L(x,pragramming)U(x,computer)作作 业业43442.2 确定性知识表示方法确定性知识表示方法2.2.1 谓词逻辑表示法谓词逻辑表示法2.2.2 产生式表示法产生式表示法 1.产生式表示的基本方法产生式表示的基本方法 2.产生式表示的例子产生式表示的例子 3.产生式表示的特性产生式表示的特性2.2.3 语义网络表示法语义网络表示法2.2.4 框架表示法框架表示法451.产生式表示的基本方法产生式表示的基本方法事实的表示事实的表示事实的概念事实的概念 事实是断言一个语言变量的值或断言多个语言变量之间关系的陈述句。事实是断言一个语言变量的值或断言多个语言变量之间关系的陈述句。语言变量的值：语言变量的值：例如，例如，“雪是白的雪是白的”语言变量之间的关系：语言变量之间的关系：例如，例如，“王峰热爱祖国王峰热爱祖国”事实的表示方法事实的表示方法 （对象，属性，值）（对象，属性，值）例如，例如，(snow,color,white)或（雪，颜色，白）。其中，对象就是语言变量。或（雪，颜色，白）。其中，对象就是语言变量。（关系，对象（关系，对象1，对象，对象2）例如，例如，(love,Wang Feng,country)或或（热爱，王峰，祖国）（热爱，王峰，祖国）461.产生式表示的基本方法产生式表示的基本方法规则的表示规则的表示 产生式也叫产生式规则，或简称规则。产生式也叫产生式规则，或简称规则。规则的基本形式规则的基本形式 IF P THEN Q 或者或者 PQ 其中，其中，P是前提，也称或前件，给出了该产生式可否使用的先决条件。是前提，也称或前件，给出了该产生式可否使用的先决条件。Q是结是结论或操作，也称后件，给出当论或操作，也称后件，给出当P满足时，应该推出的结论或执行的动作。满足时，应该推出的结论或执行的动作。形式化描述形式化描述 ：=：=|：=|：=And (And )|Or (OR )：=|(,)472.产生式表示简例产生式表示简例 下面给出一个简化的动物识别例子（完整例子后面讨论），仅包括动物识下面给出一个简化的动物识别例子（完整例子后面讨论），仅包括动物识别系统中的两条规则：别系统中的两条规则：r3：IF 动物有羽毛动物有羽毛 THEN 动物是鸟动物是鸟 r15：IF 动物是鸟动物是鸟 AND 动物善飞动物善飞 THEN 动物是信天翁动物是信天翁其中，其中，r3和和r15是上述两条规则在动物识别系统中的规则编号，一般称为规则是上述两条规则在动物识别系统中的规则编号，一般称为规则号。号。r3：前提条件是前提条件是“动物有羽毛动物有羽毛”结论是结论是“动物是鸟动物是鸟”r15：前提条件是一个复合条件前提条件是一个复合条件“动物是鸟动物是鸟 AND 动物善飞动物善飞”，它是两个子，它是两个子条件的合取。条件的合取。结论是结论是“动物是信天翁动物是信天翁”48产生式系统的特点产生式系统的特点主要优点主要优点自然性自然性 产生式表示法用产生式表示法用“如果如果，则，则”的形式表示知识，这种表示形的形式表示知识，这种表示形式与人类的判断性知识基本一致，既直观、自然，又便于进行推理。式与人类的判断性知识基本一致，既直观、自然，又便于进行推理。模块性模块性 产生式规则是规则库中最基本的知识单元，各规则之间只能通过综合产生式规则是规则库中最基本的知识单元，各规则之间只能通过综合数据库发生联系，而不能相互调用，从而增加了规则的模块性，有利于数据库发生联系，而不能相互调用，从而增加了规则的模块性，有利于对知识的增加、删除、修改和扩充。对知识的增加、删除、修改和扩充。有效性有效性 产生式知识表示法既可以表示确定性知识，又可以表示不确定性知识，产生式知识表示法既可以表示确定性知识，又可以表示不确定性知识，既有利于表示启发性知识，又有利于表示过程性知识。既有利于表示启发性知识，又有利于表示过程性知识。一致性一致性 规则库中的所有规则都具有相同的格式，并且综合数据库可被所有规规则库中的所有规则都具有相同的格式，并且综合数据库可被所有规则访问，不存在只属于某些规则的局部数据库，因此规则库中的规则可则访问，不存在只属于某些规则的局部数据库，因此规则库中的规则可以统一处理。以统一处理。49产生式系统的特点产生式系统的特点主要缺点主要缺点效率较低效率较低 在产生式表示中，各规则之间的联系必须以综合数据库为媒介。并在产生式表示中，各规则之间的联系必须以综合数据库为媒介。并且，其求解过程是一种反复进行的且，其求解过程是一种反复进行的“匹配匹配冲突消解冲突消解执行执行”过程。过程。即先用规则前提与综合数据库中的已知事实进行匹配，从规则库中选即先用规则前提与综合数据库中的已知事实进行匹配，从规则库中选择可用规则，当有多条规则可用时还需要按一定策略进行择可用规则，当有多条规则可用时还需要按一定策略进行“冲突消解冲突消解”，然后才能执行选中的规则。这样的执行方式将导致执行的低效率。，然后才能执行选中的规则。这样的执行方式将导致执行的低效率。不能表示结构性知识不能表示结构性知识 由于产生式表示中的知识具有一致格式，且由于产生式表示中的知识具有一致格式，且规则之间不能相互调用规则之间不能相互调用，因此那种具有结构关系或层次关系的知识则很难以自然的方式来表示。因此那种具有结构关系或层次关系的知识则很难以自然的方式来表示。实际上，产生式系统除作为一种独立的知识表示方式外，还常常和实际上，产生式系统除作为一种独立的知识表示方式外，还常常和其它方法结合起来使用。其它方法结合起来使用。502.2 确定性知识表示方法确定性知识表示方法2.2.1 谓词逻辑表示法谓词逻辑表示法2.2.2 产生式表示法产生式表示法2.2.3 语义网络表示法语义网络表示法 1.语义网络概述语义网络概述 2.事物和概念的表示事物和概念的表示 3.情况和动作的表示情况和动作的表示 4.语义网络的基本推理过程语义网络的基本推理过程 5.语义网络表示的特征语义网络表示的特征2.2.4 框架表示法框架表示法语义网络表示法语义网络表示法 语义网络是语义网络是J.R.Quillian于于1968年在他的博士年在他的博士论文中作为人类联想记忆的一个心理模型最先提出论文中作为人类联想记忆的一个心理模型最先提出的。语义网络最初主要用于自然语言理解的研究，的。语义网络最初主要用于自然语言理解的研究，Quillian主张应当把语义放在第一位，一个词的含主张应当把语义放在第一位，一个词的含义只有根据它所处的上下文环境才能准确的把握，义只有根据它所处的上下文环境才能准确的把握，一个句子中相关单词的语义或意思可以通过这种网一个句子中相关单词的语义或意思可以通过这种网络来表示。络来表示。基于基于Quillian的工作，的工作，Simon于于1970年正式提年正式提出了语义网络的概念。出了语义网络的概念。语义网络表示法语义网络表示法1.语义网络的概念及结构语义网络的概念及结构 语义网络是通过概念及其语义关系来表示知识的一种语义网络是通过概念及其语义关系来表示知识的一种网络图，它是一个带标记的网络图，它是一个带标记的有向图有向图。其中有向图的各。其中有向图的各节点节点用来表示各种概念、事物、属性、情况、动作、状态等，用来表示各种概念、事物、属性、情况、动作、状态等，节点上的标注用来区分各节点所表示的不同对象，每个节节点上的标注用来区分各节点所表示的不同对象，每个节点可以带有若干个属性，以表示其所代表的不同对象的特点可以带有若干个属性，以表示其所代表的不同对象的特性；性；弧弧是有方向、有标注的，方向用来体现节点间的主次是有方向、有标注的，方向用来体现节点间的主次关系，而其上的标注则表示被联接的两个节点间的某种语关系，而其上的标注则表示被联接的两个节点间的某种语义联系或语义关系。义联系或语义关系。语义网络表示法语义网络表示法 一个最简单的语义网络可由一个三元组表一个最简单的语义网络可由一个三元组表示：示：（节点（节点1，弧，节点，弧，节点2）可用如下图所示的有向图表示，称作基本网可用如下图所示的有向图表示，称作基本网元。元。ABR 其中，A和B分别代表节点，而R则表示A和B之间某种语义联系。1.语义网络概述语义网络概述概念概念 例如：例如：语义基元（语义基元（A,R,B）所对应的基）所对应的基本网元，如图本网元，如图2-3所示。所示。例例2.6 用语义基元表示用语义基元表示“鸵鸟是一种鸟鸵鸟是一种鸟”这一事实。这一事实。解：解：如图如图2-4所示。所示。说明：说明：弧的方向不可随意调换。弧的方向不可随意调换。ABR图图2-4鸵鸟鸵鸟鸟鸟是一种是一种图图2-355鸟鸟人人ISA 实例关系：实例关系：ISA 体现的是体现的是“具体与抽象具体与抽象”的概念，含义为的概念，含义为“是一个是一个”，表示一个事物是另一个事物的一个，表示一个事物是另一个事物的一个实例。例实例。例“李刚是一个人李刚是一个人”，如图，如图2-6。图图2-6 实例关系实例关系张强张强共青团共青团 A-Member-of图图2-8 成员关系成员关系 成员关系：成员关系：A-Member-of 体现的是体现的是“个体与集体个体与集体”的关系，含义为的关系，含义为“是一员是一员”，表示一个事物是另一个事物的一个，表示一个事物是另一个事物的一个成员。例成员。例“张强是共青团员张强是共青团员”，如图，如图2-8。上述关系的主要特征上述关系的主要特征 属性的继承性属性的继承性，即处在具体层的结点可以继承抽象层结点的所有属性，即处在具体层的结点可以继承抽象层结点的所有属性.分类关系：分类关系：AKO 也称泛化关系，体现的是也称泛化关系，体现的是“子类与超类子类与超类”的概念，含义为的概念，含义为“是一种是一种”，表，表示一个事物是另一个事物的一种类型。例示一个事物是另一个事物的一种类型。例“机器人是一种机器机器人是一种机器”，如图，如图2-7。李刚李刚动物动物图图2-7 分类关系分类关系AKO1.语义网络概述语义网络概述基本语义关系基本语义关系(1/3)561.语义网络概述语义网络概述基本语义关系基本语义关系(2/3)属性关系属性关系 指事物和其属性之间的关系。常用的有指事物和其属性之间的关系。常用的有：Have：含义为含义为“有有”，表示一个结点具有另一，表示一个结点具有另一个结点所描述的属性个结点所描述的属性 Can：含义为含义为“能能”、“会会”，表示一个结点，表示一个结点能做另一个结点的事情能做另一个结点的事情 例如：例如：“鸟有翅膀鸟有翅膀”，如图，如图2-9 包含关系（聚类关系）包含关系（聚类关系）指具有组织或结构特征