AI第2章-知识表示方法

1、 Artificial Intelligence (AI) 人工智能人工智能第第2 2章章 知识表示方法知识表示方法内容提要内容提要1 1、预备知识、预备知识2 2、状态空间表示、状态空间表示3 3、问题归约表示、问题归约表示4 4、谓词逻辑表示、谓词逻辑表示5 5、语义网络表示、语义网络表示预备知识预备知识 人类智能活动过程是一个人类智能活动过程是一个获得并运用知识获得并运用知识的过程。的过程。 符号主义符号主义的观点：知识是一切智能行为的的观点：知识是一切智能行为的基础基础，要使计，要使计算机具有智能，首先必须使它拥有知识。算机具有智能，首先必须使它拥有知识。1 1、需要、需要明确几个问题

2、明确几个问题： 什么是知识什么是知识 知识的划分知识的划分 人工智能系统中的知识人工智能系统中的知识 什么是知识表示什么是知识表示、知识的一般概念、知识的一般概念 知识是人们在改造客观世界的实践中，积累起来的知识是人们在改造客观世界的实践中，积累起来的“认认识识”和和“经验经验”。认识认识：对事物现象、本质、属性、状态、联系等的认知。：对事物现象、本质、属性、状态、联系等的认知。经验经验：解决问题的：解决问题的“宏观方法宏观方法”和和“微观方法微观方法”。 宏观方法宏观方法：如战略、战术、计谋、策略等。：如战略、战术、计谋、策略等。 微观方法微观方法：如步骤、操作、规则、过程、技巧等。：如步骤

3、、操作、规则、过程、技巧等。如：如：“ifif大雁南飞，大雁南飞，thenthen冬天来临冬天来临”这样的知识就是人们经过长期观察，将这样的知识就是人们经过长期观察，将“大雁向大雁向 南飞南飞”与与“冬天来临冬天来临”这两条信息关联在一起。这两条信息关联在一起。 “ “雪是白色的雪是白色的”反映雪与颜色的一种关系。反映雪与颜色的一种关系。知识的概念知识的概念、知识、信息、数据及其关系、知识、信息、数据及其关系 数据数据：是：是信息的载体信息的载体，本身无确切含义。，本身无确切含义。 如：水的温度如：水的温度100100，树的高度，树的高度1010米米 。 信息信息：是：是数据的关联数据的关联，

4、赋予数据特定的含义，仅可理解为描述，赋予数据特定的含义，仅可理解为描述 性知识。数据是没有联系的，孤立的，只有当数据用来性知识。数据是没有联系的，孤立的，只有当数据用来 描述一个客观事物及其关系，形成有逻辑的数据流，才描述一个客观事物及其关系，形成有逻辑的数据流，才 能被称为信息。能被称为信息。 知识知识：可以是对：可以是对信息的关联信息的关联，也可以是对已有知识的再认识。，也可以是对已有知识的再认识。如：如：武汉武汉8 8月月1 1日气温为日气温为3737度，度，1212月月1 1日气温为日气温为5 5度。度。 当对这类数据进行当对这类数据进行归纳和对比归纳和对比后，产生信息，我们知道武汉每

5、年后，产生信息，我们知道武汉每年8 8月气温比较高，月气温比较高，1212月气温比较低，于是有价值的信息月气温比较低，于是有价值的信息沉淀并结构化沉淀并结构化后，即形成了知识。后，即形成了知识。、性质性质 概念、命题、公理、定理、规则和方法。概念、命题、公理、定理、规则和方法。、作用域作用域 常识性知识，领域性知识。常识性知识，领域性知识。、等级等级 零级零级：事实性事实性知识。用于描述事物的概念、定义、属性等；知识。用于描述事物的概念、定义、属性等； 或用于描述问题的状态、环境、条件等。或用于描述问题的状态、环境、条件等。 一级一级：过程性过程性知识。用于问题求解过程的操作、演算和行为。知识

6、。用于问题求解过程的操作、演算和行为。 表示方式：产生式、谓词、语义网络等。表示方式：产生式、谓词、语义网络等。 二级二级：控制性控制性知识，元知识或超知识。是关于如何使用过程性知识，元知识或超知识。是关于如何使用过程性 知识的知识。如：推理策略、搜索策略、知识的知识。如：推理策略、搜索策略、 不确定性的传播策略。不确定性的传播策略。知识的划分知识的划分、层次层次 表层表层：描述客观事物现象的知识。如感性、事实性知识。：描述客观事物现象的知识。如感性、事实性知识。 深层深层：描述客观事物本质、内涵等的知识。如理论知识。：描述客观事物本质、内涵等的知识。如理论知识。、确定性确定性 确定性确定性：

7、可说明其值为真或为假的知识。：可说明其值为真或为假的知识。 不确定性不确定性：不精确、模糊、不完备知识。：不精确、模糊、不完备知识。 不精确：不精确：知识本身有真假，但由于认知水平限制却不能知识本身有真假，但由于认知水平限制却不能 肯定知识的真假。肯定知识的真假。 表示：用可信度、概率等描述。表示：用可信度、概率等描述。 模糊：模糊：知识本身的边界就是不清楚的。如大，小等。知识本身的边界就是不清楚的。如大，小等。 表示：用可能性、隶属度来描述。表示：用可能性、隶属度来描述。 不完备：不完备：解决问题时不具备解决该问题的全部知识。解决问题时不具备解决该问题的全部知识。 如医生看病。如医生看病。

8、、人类的思维及认识方法人类的思维及认识方法 逻辑性逻辑性：反映人类逻辑思维过程的知识，一般具有因果关系或难以：反映人类逻辑思维过程的知识，一般具有因果关系或难以 精确描述的特点，是人类的经验性知识和直观感觉。精确描述的特点，是人类的经验性知识和直观感觉。 如：为人处事的经验与风格。如：为人处事的经验与风格。 形象性形象性：通过事物的形象建立起来的知识。如：通过事物的形象建立起来的知识。如: :什么是人？什么是人？、获取方式获取方式 显性显性：通过文字、语言、图形、声音等形式：通过文字、语言、图形、声音等形式, ,编码记录和传播的知识。编码记录和传播的知识。 如：教材、音视频光盘。如：教材、音视

9、频光盘。 隐性隐性：长期实践中积累获得的知识，不易于显性表达的知识。：长期实践中积累获得的知识，不易于显性表达的知识。 如：每个人都有不同的审美观。如：每个人都有不同的审美观。 一个一个智能程序智能程序高水平运行高水平运行需要的知识包括：需要的知识包括：事实知识事实知识、规则知识规则知识、控制知识控制知识和和元知识元知识。、事实知识事实知识 有关问题环境的一些事物的知识，常以有关问题环境的一些事物的知识，常以“是是”的形式出现。的形式出现。 如：事物的分类、属性、事物间关系、科学事实、客观事实等。如：事物的分类、属性、事物间关系、科学事实、客观事实等。 事实是事实是静态静态的，为人们共享、可公

10、开获得且公认的知识，在知识库的，为人们共享、可公开获得且公认的知识，在知识库中属低层知识。如：雪是白色的、鸟有翅膀、这辆车是张三的中属低层知识。如：雪是白色的、鸟有翅膀、这辆车是张三的 。、规则知识规则知识 有关问题中与事物的行动、动作相联系的有关问题中与事物的行动、动作相联系的因果关系因果关系知识，是知识，是动态动态的，的，常以常以“如果如果那么那么”的形式出现。的形式出现。人工智能系统中的知识人工智能系统中的知识、控制知识控制知识 有关问题的有关问题的求解步骤、技巧求解步骤、技巧的知识。告诉人们怎样做一件事，也包的知识。告诉人们怎样做一件事，也包括当有多个动作同时被激活时，应选哪一个动作来

11、执行的知识。括当有多个动作同时被激活时，应选哪一个动作来执行的知识。 控制知识常与程序结合在一起出现，如一个问题控制知识常与程序结合在一起出现，如一个问题求解的算法求解的算法可以看可以看做是一种知识表示。做是一种知识表示。、元知识元知识 有关知识的知识，是知识库中的高层知识。有关知识的知识，是知识库中的高层知识。 包括：怎样使用规则、解释规则、校验规则、解释程序结构等。包括：怎样使用规则、解释规则、校验规则、解释程序结构等。 元知识与控制知识会有重迭元知识与控制知识会有重迭。对一个大的程序来说，以元知识（或。对一个大的程序来说，以元知识（或元规则形式）体现控制知识更方便。因为元知识存于知识库中

12、，而控制元规则形式）体现控制知识更方便。因为元知识存于知识库中，而控制知识常与程序结合在一起出现，不易修改。知识常与程序结合在一起出现，不易修改。 研究研究用机器表示知识用机器表示知识的的可行性可行性与与有效性有效性的的一般方法一般方法，是一种是一种数据结构数据结构与与控制结构控制结构的的统一体统一体，既考虑，既考虑知识的存储知识的存储又考虑又考虑知识的使用知识的使用。知识表示知识表示表示能力表示能力：能否正确、有效地表示问题。：能否正确、有效地表示问题。 包括：表示范围的广泛性、领域知识表示的高效性、对非包括：表示范围的广泛性、领域知识表示的高效性、对非 确定性知识表示的支持程度。确定性知识

13、表示的支持程度。可利用性可利用性：可利用这些知识进行有效推理。：可利用这些知识进行有效推理。 包括：对推理的适应性，对高效算法的支持程度。包括：对推理的适应性，对高效算法的支持程度。可实现性可实现性：要便于计算机直接对其进行处理。：要便于计算机直接对其进行处理。可组织性可组织性：可以按某种方式把知识组织成某种知识结构。：可以按某种方式把知识组织成某种知识结构。可维护性可维护性：便于对知识的增、删、改等操作。：便于对知识的增、删、改等操作。自自 然然 性性：符合人们的日常习惯。：符合人们的日常习惯。可理解性可理解性：知识应易读、易懂、易获取等。：知识应易读、易懂、易获取等。知识表示的要求：知识表

14、示的要求： 各种以各种以知识知识和和符号操作符号操作为基础的智能系统，其问题求解方法都需要为基础的智能系统，其问题求解方法都需要某种某种对解答的搜索对解答的搜索。 不过，在搜索过程开始之前，必须先用某种方法或某几种方法不过，在搜索过程开始之前，必须先用某种方法或某几种方法集成集成来表示问题。来表示问题。 对于传统人工智能问题，任何比较复杂的求解技术，都离不开两方对于传统人工智能问题，任何比较复杂的求解技术，都离不开两方面的内容面的内容-表示表示与与搜索搜索。 同一问题可以有多种不同的同一问题可以有多种不同的表示方法表示方法，且具有不同的，且具有不同的表示空间表示空间。 问题表示的优劣问题表示的

15、优劣，对求解，对求解结果结果和求解和求解效率效率影响很大。影响很大。知识表示与问题求解的关系：知识表示与问题求解的关系： 人工智能虽有多个研究领域，且每个研究领域又各有自己的规律和人工智能虽有多个研究领域，且每个研究领域又各有自己的规律和特点，但在分析其研究中运用的问题求解方法后，发现许多问题的求解特点，但在分析其研究中运用的问题求解方法后，发现许多问题的求解都是采用都是采用“试探搜索方法试探搜索方法”。 也就是说，这些方法是通过也就是说，这些方法是通过在某个可能的解空间内在某个可能的解空间内寻找一个解寻找一个解来求来求解问题。因此，无论采用何种方法，都可抽象为一个解问题。因此，无论采用何种方

16、法，都可抽象为一个“问题求解问题求解”过程。过程。所以，问题求解过程所以，问题求解过程实际上就是实际上就是一个一个搜索过程搜索过程。 问题求解技术的问题求解技术的两个主要方面两个主要方面：问题的表示、求解的方法。：问题的表示、求解的方法。状态空间表示的状态空间表示的定义：定义： 基于基于解答空间解答空间的问题表示和求解方法，以的问题表示和求解方法，以状态状态（StateState）和）和算符算符（operatoroperator）为基础来）为基础来表示表示和和求解求解问题。问题。2.1 2.1 状态空间表示状态空间表示（State Space Representation）、状态状态（stat

17、e） 为描述某类不同事物间的差别，引入的一组最少变量为描述某类不同事物间的差别，引入的一组最少变量q0,q1,qn的有的有序集合，是表示问题解法中，序集合，是表示问题解法中，每一步问题状况每一步问题状况的的数据结构数据结构。 有序集合中的每个元素有序集合中的每个元素qi(i=0,1,.,n)是集合的是集合的分量分量，称为，称为“状态变状态变量量”。给定每个分量的一组值，就得到一个具体的状态。给定每个分量的一组值，就得到一个具体的状态。、算符算符（operator） 使问题从一种状态使问题从一种状态变化为变化为另一种状态的手段。（另一种状态的手段。（操作符操作符）、状态空间方法状态空间方法 是一

18、个表示某个问题是一个表示某个问题全部可能状态及其关系全部可能状态及其关系的的图图。 是一个包含是一个包含三种说明三种说明的的集合集合，即，即三元状态三元状态（S,F,G）。 S：所有可能问题的初始状态集合；所有可能问题的初始状态集合；F：操作符集合；操作符集合；G：目标状态集合。目标状态集合。1 1、状态空间表示的三要素、状态空间表示的三要素 十五数码难题十五数码难题(15 puzzle)：由：由1515个编有个编有1 1至至1515，放在，放在44方格棋盘上可走动的棋子组成。方格棋盘上可走动的棋子组成。如何将初始棋局变换为目标棋局？如何将初始棋局变换为目标棋局？问题解答：问题解答：某个合适的

19、棋子走步序列。某个合适的棋子走步序列。2 2、状态空间表示举例、状态空间表示举例初始状态初始状态目标状态目标状态如何将初始棋局如何将初始棋局变成目标棋局？变成目标棋局？首先将适用首先将适用的算符用于的算符用于初始状态，初始状态，以产生新的以产生新的状态。状态。再将另一些再将另一些适用算符用适用算符用于这些新的于这些新的状态；如此状态；如此继续下去，继续下去，直至产生目直至产生目标状态为止。标状态为止。说明：说明： 最直接的求解方法最直接的求解方法，是，是尝试各种不同的走步尝试各种不同的走步，直到，直到偶然得到偶然得到目标棋目标棋局为止，这种尝试局为止，这种尝试本质上本质上涉及某种涉及某种试探搜

20、索试探搜索。 即，从初始棋局开始，试探着由即，从初始棋局开始，试探着由每一合法走步每一合法走步得到各种得到各种新棋局新棋局，然，然后计算再走下一步得到的下一组棋局。如此继续下去，直至得到目标棋后计算再走下一步得到的下一组棋局。如此继续下去，直至得到目标棋局为止。（实质上就是由初始状态，通过不同棋子（节点）的移动，不局为止。（实质上就是由初始状态，通过不同棋子（节点）的移动，不断形成多种新的状态，直至得到目标状态的过程）断形成多种新的状态，直至得到目标状态的过程） 因此，我们将初始状态可达到的因此，我们将初始状态可达到的各个状态所组成的空间各个状态所组成的空间，设想为一，设想为一幅由幅由各种状态

21、对应的节点各种状态对应的节点组成的图组成的图，并将这个图称为，并将这个图称为“状态图状态图”或或“状状态空间图态空间图”。（即每个节点都有其所表示的棋局。（即每个节点都有其所表示的棋局( (状态状态) )）首先首先，将适用的，将适用的“算符（操作符）算符（操作符）”用于初始状态，以产生新的状态；用于初始状态，以产生新的状态；然后然后，再将另一些适用算符作用于这些新的状态；，再将另一些适用算符作用于这些新的状态；继续下去继续下去，直至产生目标状态为止。，直至产生目标状态为止。 可用可用“状态空间法状态空间法”这个术语表示：从某个初始状态开始，每次加这个术语表示：从某个初始状态开始，每次加一一个操

22、作符，递增地建立起个操作符，递增地建立起操作符的试验序列操作符的试验序列，直至达到目标状态为止。，直至达到目标状态为止。 不过，对某些不过，对某些最优化最优化问题，仅仅找到到达目标的任一路径是不够的问题，仅仅找到到达目标的任一路径是不够的, ,还必须找到还必须找到按某个准则按某个准则实现实现最优化最优化的路径。（如下棋的走步最少）的路径。（如下棋的走步最少）综上所述，要完成对某个问题的状态描述，必须确定综上所述，要完成对某个问题的状态描述，必须确定3 3件事件事： 该状态描述方式，特别是初始状态描述；该状态描述方式，特别是初始状态描述； 操作符集合及其对初始状态描述的作用；操作符集合及其对初始

23、状态描述的作用； 目标状态描述的特性。目标状态描述的特性。 状态空间的图示形式状态空间的图示形式，称为，称为“状态空间图状态空间图”。状态图状态图中有中有几个术语几个术语：节点节点(Node)：图形上的汇合点，表示：图形上的汇合点，表示状态状态、事件事件和和时间时间关系的汇合。关系的汇合。 弧线弧线(Arc)：节点间的连接线，表示算符。：节点间的连接线，表示算符。有向图有向图(Directed Graph)：一对节点用弧线连接起来，从一个节点指向：一对节点用弧线连接起来，从一个节点指向 另一个节点。另一个节点。后继节点后继节点(Descendant node)与与父辈节点父辈节点(Parent

24、 node)：如果某条弧线从：如果某条弧线从 节点节点ni指向节点指向节点nj，那么节点，那么节点nj就叫做节点就叫做节点ni的的后继节点后继节点或或后裔后裔，而，而 节点节点ni叫做节点叫做节点nj的的父辈节点父辈节点或或祖先祖先。3 3、状态图示法、状态图示法路径路径(Path)：某个节点序列：某个节点序列(ni1,ni2,nik)，当当j=2,3,k时，若对于每一时，若对于每一 个个ni,j-1都有一个后继节点都有一个后继节点nij存在，那么就把这个节点序列叫存在，那么就把这个节点序列叫 做从节点做从节点ni1至节点至节点nik的长度为的长度为k的路径。的路径。代价代价(Cost)：用：

25、用c(ni,nj)来表示从节点来表示从节点ni指向节点指向节点nj的那段弧线的代价。两的那段弧线的代价。两 节点间路径的代价等于连接该路径上各节点的所有弧线代节点间路径的代价等于连接该路径上各节点的所有弧线代 价之和。价之和。图的显式说明图的显式说明/ /隐式说明隐式说明：指各节点及其具有代价的弧线：指各节点及其具有代价的弧线可以可以/ /不可以不可以由由 一张表明确给出。显式说明对于大型的图是一张表明确给出。显式说明对于大型的图是 不切实际的，而对于具有无限节点集合的图不切实际的，而对于具有无限节点集合的图 则是不可能的。则是不可能的。问题的表示问题的表示对求解工作有很大影响，通常希望有较小

26、的状态空间表示。对求解工作有很大影响，通常希望有较小的状态空间表示。如如，针对十五数码问题：，针对十五数码问题： 可以规定可以规定15460条规则，即条规则，即“上移棋子上移棋子4 4，下移棋子，下移棋子4 4，左移棋，左移棋子子4 4，右移棋子，右移棋子4”4”。 如果如果用用“上下左右移动空格上下左右移动空格”，则只需，则只需4 4条规则。因此，移动空格条规则。因此，移动空格是一种较好的表示。是一种较好的表示。 各种问题都可用各种问题都可用状态空间状态空间加以表示，并用加以表示，并用状态空间搜索法状态空间搜索法来求解。来求解。猴子和香蕉问题：猴子和香蕉问题： 一个房间内有一只猴子、一个箱子

27、和一束香蕉。香蕉挂在天花板下一个房间内有一只猴子、一个箱子和一束香蕉。香蕉挂在天花板下方，但猴子的高度不足以拿到。那么这只猴子怎样才能拿到香蕉方，但猴子的高度不足以拿到。那么这只猴子怎样才能拿到香蕉? ?状态空间法举例：状态空间法举例：解题过程：解题过程： 用一个四元组（用一个四元组（W,x,Y,z）来表示这个问题状态。）来表示这个问题状态。 其中，其中，W：猴子的水平位置；：猴子的水平位置； x：当猴子在箱子顶上时取：当猴子在箱子顶上时取1；否则取；否则取0； Y：箱子的水平位置；：箱子的水平位置； z：当猴子摘到香蕉时取：当猴子摘到香蕉时取1；否则取；否则取0。 初始状态初始状态为为(a,

28、0,b,0)， 目标状态目标状态为为(c,1,c,1)操作操作( (算符算符) )：goto(U)：表示猴子走到水平位置表示猴子走到水平位置U 产生式规则表示：产生式规则表示：pushbox(V)：猴子把箱子推到水平位置猴子把箱子推到水平位置V 产生式规则表示：产生式规则表示：climbbox：猴子爬上箱顶猴子爬上箱顶 产生式规则表示：产生式规则表示：grasp：猴子拿到香蕉猴子拿到香蕉 产生式规则表示：产生式规则表示：由由初始状态初始状态变换为变换为目标状态目标状态的的操作序列操作序列： Step1: goto(b) Step2: pushbox(c) Step3: climbbox Ste

29、p4: grasp goto(b), pushbox(c), climbbox, grasp状态空间图：状态空间图：猴子和香蕉问题自动演示：猴子和香蕉问题自动演示： 猴子猴子香蕉香蕉箱子箱子 猴子猴子香蕉香蕉箱子箱子 Ha!Ha!2.2 2.2 问题归约表示问题归约表示（Problem Reduction）是另一种是另一种基于状态空间基于状态空间的问题描述与求解方法。的问题描述与求解方法。基本思想：基本思想：已知问题的描述，通过已知问题的描述，通过一系列变换一系列变换将此问题将此问题变为变为一个一个子问子问 题集合题集合，而这些子问题的解可以，而这些子问题的解可以直接得到直接得到( (本原问题

30、本原问题) )，从，从 而解决初始问题。而解决初始问题。本原问题：本原问题：不能再分解或变换，且直接可解的子问题。不能再分解或变换，且直接可解的子问题。1 1、问题归约表示的、问题归约表示的组成部分组成部分 问题归约表示也是一个问题归约表示也是一个3元组元组（S,F,G），组成部分为：，组成部分为： 一个初始问题描述一个初始问题描述S 一套把问题变换为子问题的操作符一套把问题变换为子问题的操作符F 一套本原问题描述一套本原问题描述G2 2、问题归约的、问题归约的实质实质 从目标（即要解决的问题）出发，逆向推理，建立子问题以及子从目标（即要解决的问题）出发，逆向推理，建立子问题以及子问题的子问题

31、，直到最后将初始问题问题的子问题，直到最后将初始问题归约为归约为一个一个平凡的本原问题集合平凡的本原问题集合。问题归约举例：问题归约举例：梵塔梵塔（汉诺塔）（汉诺塔）难题难题问题：问题：从从1 1移到移到3 3、每次移动一个盘子、大盘在下小盘在上。、每次移动一个盘子、大盘在下小盘在上。子问题子问题1 1：移动圆盘移动圆盘A A和和B B至柱子至柱子2 2的双圆盘难题。的双圆盘难题。 （借助柱子（借助柱子3 3）子问题子问题2 2：移动圆盘移动圆盘C C至柱子至柱子3 3的单圆盘难题。的单圆盘难题。子问题子问题3 3：将圆盘将圆盘A A和和B B移至柱子移至柱子3 3的双圆盘难题。的双圆盘难题。

32、 （借助柱子（借助柱子1 1）原始问题可以归约为下列原始问题可以归约为下列3 3个子问题个子问题：归约过程：归约过程：问题归约法是比状态空间法问题归约法是比状态空间法更通用更通用的一种问题求解方法。的一种问题求解方法。 问题归约图问题归约图: :CBA本原问题本原问题与或图与或图本原问题本原问题与或图表示与或图表示: : 用一个类似于图的结构，表示把问题归约为用一个类似于图的结构，表示把问题归约为后继问题后继问题的替换集合的替换集合。与图与图：把一个复杂问题分解为若干个：把一个复杂问题分解为若干个 较为简单的子问题，形成较为简单的子问题，形成“与与”树。树。或图或图：把原问题变换为若干个较为容

33、易：把原问题变换为若干个较为容易 求解的新问题，形成求解的新问题，形成“或或”树。树。 各个各个与节点与节点用用跨接跨接指向它们后继节点的弧线的小段圆弧加以标记指向它们后继节点的弧线的小段圆弧加以标记的结构图的结构图-与或图与或图。引入附加节点，使含有一个以上后继问题的引入附加节点，使含有一个以上后继问题的每个集合，可聚集在各自的父辈节点之下。每个集合，可聚集在各自的父辈节点之下。父节点：父节点：一个初始问题，或是可分解为子问题的问题节点。一个初始问题，或是可分解为子问题的问题节点。子节点：子节点：一个子问题，或是子问题分解的子问题节点。一个子问题，或是子问题分解的子问题节点。或节点：或节点：

34、只要解决某个问题，就可解决其父辈问题的节点集。只要解决某个问题，就可解决其父辈问题的节点集。与节点：与节点：只有解决所有子问题后，才能解决其父辈问题的节点集。只有解决所有子问题后，才能解决其父辈问题的节点集。弧线：弧线：父辈节点指向子节点的圆弧连线。父辈节点指向子节点的圆弧连线。终叶节点：终叶节点：对应于原问题的本原节点。对应于原问题的本原节点。关于与或图的术语：关于与或图的术语：与或图的构成规则与或图的构成规则: : 与或图中的与或图中的每个节点每个节点，代表一个要解决的，代表一个要解决的单单 一问题一问题或或问题集合问题集合。图中所含。图中所含起始节点起始节点，对，对 应于应于原始问题原始

35、问题A A。 对应于本原问题的节点称为对应于本原问题的节点称为终叶节点终叶节点，它没，它没 有后继节点。有后继节点。 对于将算符应用于问题对于将算符应用于问题A A的每种可能情况，的每种可能情况， 都把问题变换为一个都把问题变换为一个子问题集合子问题集合；有向弧线；有向弧线 自自A A指向后继节点，表示所求得的子问题集合。指向后继节点，表示所求得的子问题集合。 一般对于代表一般对于代表两个或两个以上两个或两个以上子问题集子问题集 合的每个节点，有向弧线从此节点指向合的每个节点，有向弧线从此节点指向 次子问题集合中的各个节点。次子问题集合中的各个节点。由于只有由于只有 当集合中所有项都有解时，这

36、个子问题当集合中所有项都有解时，这个子问题 的集合才能获得解答的集合才能获得解答，所以这些子问题，所以这些子问题 节点叫做节点叫做与节点与节点。 特殊情况下，当只有一个算符可应用于特殊情况下，当只有一个算符可应用于 问题问题A A，而且这个算符产生具有一个以，而且这个算符产生具有一个以 上子问题的某个集合时，由上述规则上子问题的某个集合时，由上述规则 和规则和规则所产生的图可以得到简化。所产生的图可以得到简化。与或图的搜索与或图的搜索: :目的在于表明起始节点是有解的。目的在于表明起始节点是有解的。可解节点可解节点: : 终叶节点终叶节点是可解节点（对应于本原问题）。是可解节点（对应于本原问题

37、）。 如果某个非终叶节点含有如果某个非终叶节点含有或后继节点或后继节点，那么只要当其后继节，那么只要当其后继节 点点至少有一个是可解至少有一个是可解时，此非终叶节点才是可解的。时，此非终叶节点才是可解的。 如果某个非终叶节点含有如果某个非终叶节点含有与后继节点与后继节点，那么只有当其后继节，那么只有当其后继节 点点全部为可解时全部为可解时，此非终叶节点才是可解的。，此非终叶节点才是可解的。不可解节点：不可解节点： 没有后裔的没有后裔的非终叶节点非终叶节点为不可解节点。为不可解节点。 如果某个如果某个非终叶节点非终叶节点含有含有或后继节点或后继节点，那么只有当其，那么只有当其全部后裔为不全部后裔

38、为不可解时可解时，此非终叶节点才是不可解的。，此非终叶节点才是不可解的。 如果某个如果某个非终叶节点非终叶节点含有含有与后继节点与后继节点，那么只要当其后裔，那么只要当其后裔至少有一至少有一个为不可解时个为不可解时，此非终叶节点才是不可解的。，此非终叶节点才是不可解的。ttttttttt有解节点有解节点无解节点无解节点终叶节点终叶节点与或图例子与或图例子原始问题原始问题有一个有一个以上的解以上的解原始问题有原始问题有解解2.3 2.3 谓词逻辑表示谓词逻辑表示1 1、命题逻辑与谓词逻辑、命题逻辑与谓词逻辑 命题逻辑命题逻辑与与谓词逻辑谓词逻辑是最先用于人工智能的两种逻辑，对于知识的是最先用于人

39、工智能的两种逻辑，对于知识的形式化表示，特别是定理的证明发挥了重要作用。形式化表示，特别是定理的证明发挥了重要作用。 虽然命题逻辑能够将客观世界的各种事实表示为逻辑命题，但是它虽然命题逻辑能够将客观世界的各种事实表示为逻辑命题，但是它具有较大的局限性。命题逻辑只能进行具有较大的局限性。命题逻辑只能进行命题间关系命题间关系的推理，无法解决与的推理，无法解决与命题结构命题结构和和成分成分有关的推理问题，有关的推理问题，不适合表示比较复杂的问题不适合表示比较复杂的问题。 谓词逻辑谓词逻辑是在命题逻辑的基础上发展而来的，命题逻辑可以看作是是在命题逻辑的基础上发展而来的，命题逻辑可以看作是谓词逻辑的一种

40、谓词逻辑的一种特殊形式特殊形式。 命题命题是具有是具有真假意义真假意义的语句。的语句。 命题代表人进行思维时的一种命题代表人进行思维时的一种判断判断。若命题的意义为真，称它的真。若命题的意义为真，称它的真值为值为“真真”，记作，记作“T”T”；若命题的意义为假，称它的真值为；若命题的意义为假，称它的真值为“假假”，记，记作作“F”F”。 例如例如：“武汉是湖北省省会武汉是湖北省省会”、“1010大于大于6”6”是真值为是真值为“T”T”的命题。的命题。 “ “月亮是方的月亮是方的”、“煤炭是白的煤炭是白的”是真值为是真值为“F”F”的命题。的命题。 一个命题不能同时即为真又为假，但可以在一定条

41、件下为真，在另一个命题不能同时即为真又为假，但可以在一定条件下为真，在另一种条件下为假。一种条件下为假。 例如例如：“1+1=10”1+1=10”在在二进制二进制情况下为真，情况下为真，十进制十进制情况下为假。情况下为假。 没有真假意义的语句没有真假意义的语句，如感叹句、疑问句等，如感叹句、疑问句等，不是命题不是命题。 通常用通常用大写英文字母大写英文字母表示一个命题。表示一个命题。 例如例如：P P：北京是座古老的城市。：北京是座古老的城市。 2 2、命题、命题客观事物的结构及逻辑特征？客观事物的结构及逻辑特征？ 不同事物间的共同特征？不同事物间的共同特征？ 命题这种表示方法，无法将它所描述

42、的客观事物的命题这种表示方法，无法将它所描述的客观事物的结构及逻辑特征结构及逻辑特征反映出来，也不能将不同事物间的反映出来，也不能将不同事物间的共同特征共同特征表述出来。表述出来。 例如例如，用字母，用字母P P表示表示“小张是老张的儿子小张是老张的儿子”这一命题，则无法表述出这一命题，则无法表述出老张与小张是父子关系。老张与小张是父子关系。 又如又如，“张三是学生张三是学生”，“李四是学生李四是学生”这两个命题，用命题逻辑这两个命题，用命题逻辑表示时，无法把两者的共同特征表示时，无法把两者的共同特征“都是学生都是学生”形式的表示出来。形式的表示出来。 可否用可否用 StudentStuden

43、t（“张三张三”），）， StudentStudent（“李四李四”）表示上述命）表示上述命题？题？ - 谓词逻辑谓词逻辑3 3、命题逻辑的局限性、命题逻辑的局限性 在在谓词逻辑谓词逻辑中，中，命题命题是用形式如是用形式如P(xP(x1 1,x,x2 2,x,xn n) )的的谓词谓词来表述的。来表述的。 一个谓词可分为一个谓词可分为谓词名谓词名与与个体个体两个部分。两个部分。个体个体： 是是命题命题的的主语主语，表示，表示独立存在的事物独立存在的事物或或某个抽象的概念某个抽象的概念。 “ “x x1 1,x,x2 2,x,xn n”是个体，一般用小写字母表示。是个体，一般用小写字母表示。 个

44、体可以是常量、变元或函数。个体可以是常量、变元或函数。谓词名谓词名：表示个体的：表示个体的性质性质、状态状态或个体之间的或个体之间的关系关系。 “ “P”是谓词名，一般用大写字母表示。是谓词名，一般用大写字母表示。称称P是一个是一个n元谓词元谓词。 是到目前为止，能够表达人类思维活动规律的一种最精确的语言是到目前为止，能够表达人类思维活动规律的一种最精确的语言, ,与人们的自然语言比较接近，可方便地存储到计算机中去，并被精确与人们的自然语言比较接近，可方便地存储到计算机中去，并被精确地处理，是最早应用于人工智能中表示知识的一种逻辑。地处理，是最早应用于人工智能中表示知识的一种逻辑。4 4、谓词

45、、谓词 对于命题：对于命题：“张三是学生张三是学生”，用谓词可以表示为：，用谓词可以表示为： Student（“张三张三”） 其中，其中，Student是谓词名，是谓词名，“张三张三”是个体，是个体，Student刻画了刻画了“张三张三”是个学生这一特征。是个学生这一特征。 在谓词中，个体可以是在谓词中，个体可以是常量常量，也可以是，也可以是变元变元，还可以是一个，还可以是一个函数函数。例如例如，命题，命题“x10”可以表示为可以表示为more(x,10)，其中，其中x是变元。是变元。又如又如，命题，命题“小张的父亲是老师小张的父亲是老师”，可表示为，可表示为Teacher(father(Zh

46、ang)， 其中，其中，father(Zhang)是一个函数。是一个函数。 当谓词中的当谓词中的变元变元都用都用特定的个体特定的个体取代时，谓词就具有一个取代时，谓词就具有一个确定的确定的真值真值“T”或或“F”。 在在n元谓词元谓词P(x1,x2,xn)中，若每个个体均为常量、变元或函数，中，若每个个体均为常量、变元或函数，则称为则称为“一阶谓词一阶谓词”。一阶谓词逻辑是谓词逻辑中。一阶谓词逻辑是谓词逻辑中最直观最直观的一种逻辑，的一种逻辑，它以谓词形式来表示动作的主体和客体。它以谓词形式来表示动作的主体和客体。 如：如：张三与李四打网球（张三与李四打网球（Zhang and Li play

47、 tennis） 可写为：可写为：play (Zhang, Li, tennis) 这里这里谓词谓词是是play，动词，动词主体主体是是Zhang和和 Li，而，而客体客体是是tennis。谓词逻辑规范表达式：谓词逻辑规范表达式： P ( x1, x2, x3, ) 其中：其中：P是谓词是谓词, xi是主体与客体。是主体与客体。谓词比命题能更加细致地刻画知识：谓词比命题能更加细致地刻画知识： 表达能力强表达能力强 如：如：北京是个城市，北京是个城市，City(x)City(x) 将城市这个概念分割出来。把将城市这个概念分割出来。把“城市城市”与与“北京北京”两个概念两个概念连接连接 在一起，而

48、且说明在一起，而且说明“北京北京”是是“城市城市”的子概念。的子概念。 可以代表变化的情况可以代表变化的情况 如：如：City(City(北京北京),),真。真。 City(City(煤球煤球),),假。假。特点：特点：在不同的知识之间建立联系在不同的知识之间建立联系 如：如：Human(x)Lawed(x)Human(x)Lawed(x)，人人都受法律管制，人人都受法律管制，x x是同一个人。是同一个人。 Commit(x)Punished(x)Commit(x)Punished(x)，x x不一定是人也可以是动物。不一定是人也可以是动物。 而，而，Human(x)Lawed(x)commi

49、t(x)Punished(x)Human(x)Lawed(x)commit(x)Punished(x)，含义：含义：如果由于某个如果由于某个x x是人而受法律管制，则这个人犯了罪是人而受法律管制，则这个人犯了罪 就一定要受到惩罚。就一定要受到惩罚。2.3.1 2.3.1 谓词演算谓词演算1 1、谓词逻辑的语法和语义、谓词逻辑的语法和语义基本符号基本符号：谓词符号、变量符号、函数符号、常量符号、括号和逗号。：谓词符号、变量符号、函数符号、常量符号、括号和逗号。原子公式原子公式：由若干：由若干谓词符号谓词符号和和项项组成。组成。 谓词符号谓词符号规定定义域内的一个相应关系。规定定义域内的一个相应关

50、系。 常量符号常量符号是最简单的项，表示论域内的物体或实体。是最简单的项，表示论域内的物体或实体。 变量符号变量符号也是项，不明确涉及是哪一个实体。也是项，不明确涉及是哪一个实体。 函数符号函数符号表示论域内的函数，是从论域内的一个实体到另外表示论域内的函数，是从论域内的一个实体到另外 一个实体的映射。一个实体的映射。例如：例如：原子公式原子公式 Marriedfather(LI),mother(LI) 表示：表示：“李李(LI)(LI)的父亲和他的母亲结婚的父亲和他的母亲结婚”、连词、连词 合取合取：“”， 表示所连结的表示所连结的两个命题之间两个命题之间具有具有“与与”的关系。的关系。 析

51、取析取：“”，表示所连结的，表示所连结的两个命题之间两个命题之间具有具有“或或”的关系。的关系。 蕴涵蕴涵：“”，表示，表示“若若则则”的语义。（的语义。（如果如果那么那么） PQ读作读作“如果如果P P，则则Q”Q”。 其中，其中，P称为称为条件的条件的前件前件，Q称为称为条件的条件的后件后件。 非非：“ “ ” ”（或（或“”），表示），表示对其后面命题对其后面命题的的否定否定。 双条件双条件：符号：符号“”（或（或“”），表示），表示“当且仅当当且仅当”的语义。的语义。 PQ读作读作“P当且仅当当且仅当Q”。2 2、连词和量词、连词和量词 合取合取 用连词用连词“”将几个公式连接起来而构

52、成的公式叫做合将几个公式连接起来而构成的公式叫做合取取, ,合取式的每个组成部分叫合取式的每个组成部分叫合取项合取项。 例如：例如：我喜爱音乐和绘画我喜爱音乐和绘画 可写成：可写成：LIKE(I , MUSIC)LIKE(I , PAINTING) 又如：又如：“李李”住在一幢黄色的房子里住在一幢黄色的房子里 LIVES(LI , HOUSE-1)COLOR(HOUSE-1 , YELLOW) 析取析取 用连词用连词“”将几个公式连接起来而构成的公式叫做析将几个公式连接起来而构成的公式叫做析取取, ,析取式的每个组成部分叫析取式的每个组成部分叫析取项析取项。 例如：例如：李明打篮球或踢足球李明

53、打篮球或踢足球可写成：可写成： PLAYS(LIMING , BASKETBALL)PLAYS(LIMING , FOOTBALL) 蕴涵蕴涵 用连词用连词“”（或（或“=”=”）连接两个公式所构成的公式）连接两个公式所构成的公式叫做叫做蕴涵。蕴涵的蕴涵。蕴涵的左式左式叫做叫做前项前项，右式右式叫做叫做后项后项。 例如：例如：如果该书是何平的，那么它是兰色封面的如果该书是何平的，那么它是兰色封面的 可表示为：可表示为： OWNS(HEPING , BOOK-1) COLOR(BOOK-1 , BLUE) 又如：又如：如果李华跑得最快，那么他取得冠军如果李华跑得最快，那么他取得冠军 可表示为：可

54、表示为： RUNS(LIHUA , FASTEST) WINS(LIHUA , CHAMPION) 否定否定 前面具有符号前面具有符号“”（或（或“”）的公式叫做否定。）的公式叫做否定。 例如例如，子句，子句“机器人不在机器人不在2 2号房间内号房间内” 可表示为：可表示为： INROOM(ROBOT , r2) 等价等价 PQ为真，当且仅当为真，当且仅当P、Q同时为真或者同时为假。同时为真或者同时为假。 命题演算命题演算 如果我们把句子如果我们把句子限制为：限制为：用用已介绍过已介绍过的造句法所能表示的那些句子的造句法所能表示的那些句子, ,而且而且也不使用也不使用变量项，则将这个变量项，则

55、将这个谓词演算的子集谓词演算的子集叫做命题演算。叫做命题演算。 如想表达由古典句子指出的明显事实：如想表达由古典句子指出的明显事实：WANGGANG IS A MAN ZHANGWEI IS A MAN 可表示为：可表示为：MAN(WANGGANG) MAN(ZHANGWEI) 命题演算命题演算缺乏缺乏用有效的方法表达多个命题的能力。用有效的方法表达多个命题的能力。 如：如：无法表达无法表达“所有的机器人都是灰色的所有的机器人都是灰色的”。、量词、量词 全称量词全称量词 符号符号“ ”，意思是，意思是“所有的所有的”、“任一个任一个”。 x读作读作“对一切对一切x”，或，或“对每一对每一x”，

56、或，或“对任一对任一x”。 命题命题( x)P(x)为真，当且仅当对论域中的所有为真，当且仅当对论域中的所有x，都有，都有P(x)为真。为真。 命题命题( x)P(x)为假，当且仅当至少存在论域中的一个为假，当且仅当至少存在论域中的一个x，使得，使得P(x)为假。为假。 例如，例如，所有的机器人是灰色的所有的机器人是灰色的 可表示为：可表示为：( x)ROBOT(X) = COLOR(x , GRAY) 存在量词存在量词 符号符号“ ”，意思是，意思是“至少有至少有”、“存在存在”。 x读作读作“存在一个存在一个x”,或或“对某些对某些x”，或，或“至少有一至少有一x”。 命题命题( x)P(

57、x)为真，当且仅当至少存在论域中的一个为真，当且仅当至少存在论域中的一个x，使得，使得P(x)为真。为真。 命题命题( x)P(x)为假，当且仅当对论域中的所有为假，当且仅当对论域中的所有x，都有，都有P(x)为假。为假。 例如，例如，1号房间内有个物体号房间内有个物体 可表示为：可表示为： ( x)INROOM(x , r1)2.3.2 2.3.2 谓词公式谓词公式、原子谓词公式原子谓词公式 由由谓词符号谓词符号和和若干项若干项组成的组成的谓词演算谓词演算。即，。即，用用P(x1,x2,.,xn)表示一个表示一个n元谓词公式，其中元谓词公式，其中P为为n元谓词元谓词， x1,x2,.,xn为

58、为客体变量客体变量或或变元变元。 通常将通常将P( x1,x2,.,xn )叫做谓词演算的叫做谓词演算的原子公式原子公式。、分子谓词公式分子谓词公式 将用将用连词连词把原子谓词公式组成的把原子谓词公式组成的复合谓词公式复合谓词公式，叫做，叫做分子谓词公式分子谓词公式。、合式公式、合式公式 用用归纳法归纳法给出合式公式的给出合式公式的递归定义递归定义如下：如下： 原子谓词公式是合式公式。原子谓词公式是合式公式。 若若A为合式公式，则为合式公式，则“A”（或（或“A”）也是一个合式公式。）也是一个合式公式。 若若A,B是合式公式，则是合式公式，则AB，AB，AB，AB也都是合式公式。也都是合式公式

59、。 若若A是合式公式，是合式公式，x为为A中的自由变元，则中的自由变元，则 ( x)A和和( x)A都是合式公式。都是合式公式。 只有按上述规则只有按上述规则至至求得的那些公式，才是合式公式。求得的那些公式，才是合式公式。 用谓词公式表示知识时，需要首先用谓词公式表示知识时，需要首先定义谓词定义谓词，然后再用，然后再用连接词连接词把有关的谓词连接起来，形成一个谓词公式，以表达把有关的谓词连接起来，形成一个谓词公式，以表达一个完整的意思。一个完整的意思。 例：例：设有下列知识设有下列知识 刘欢比他父亲出名。刘欢比他父亲出名。 高扬是计算机系的一名学生，但他不喜欢编程。高扬是计算机系的一名学生，但

60、他不喜欢编程。 任何整数或者为正或者为负。任何整数或者为正或者为负。为了用谓词公式表示上述知识，首先需要定义谓词：为了用谓词公式表示上述知识，首先需要定义谓词： FAMOUS(x,y)：x比比y出名出名 COMPUTER(x)：x是计算机系的是计算机系的 LIKE(x,y)：x喜欢喜欢y I(x)：x是整数是整数 P(x)：x是正数是正数 N(x)：x是负数是负数此时可用谓词公式把上述知识表示为此时可用谓词公式把上述知识表示为: : 刘欢比他父亲出名刘欢比他父亲出名 FAMOUS(Liuhuan , father(Liuhuan) 高扬是计算机系的一名学生，但他不喜欢编程高扬是计算机系的一名学