知识表示方法

1、知识表示方法2 知识知识是一切智能行为的基础，也是软件是一切智能行为的基础，也是软件智能化的重要研究对象。要使软件具有智能，智能化的重要研究对象。要使软件具有智能，就必须使它具有知识，而要使软件具有知识，就必须使它具有知识，而要使软件具有知识，首先必须解决知识的表示问题。首先必须解决知识的表示问题。 知识表示知识表示包括知识表示的概念和知识表包括知识表示的概念和知识表示方法。对知识表示方法，又可根据所表示知示方法。对知识表示方法，又可根据所表示知识的确定化程度，分为确定性知识表示和不确识的确定化程度，分为确定性知识表示和不确定性知识表示。定性知识表示。3 知识是人们在改造客观世界的实践中积累知

2、识是人们在改造客观世界的实践中积累起来的认识和经验。起来的认识和经验。 通常，人们对客观世界的描述是通过数据通常，人们对客观世界的描述是通过数据和信息来实现的。和信息来实现的。 数据数据和和信息信息是两个密切相关的概念。数据是两个密切相关的概念。数据是信息的载体和表示，信息是数据在特定场合是信息的载体和表示，信息是数据在特定场合下的含义，或者说信息是数据的语义。下的含义，或者说信息是数据的语义。知识与知识表示的概念知识与知识表示的概念一一. . 知识知识4 知识是对信息进行智能性加工所形成的对客知识是对信息进行智能性加工所形成的对客观世界规律性的认识。观世界规律性的认识。 把把有关信息关联在一

3、起所形成的信息结构有关信息关联在一起所形成的信息结构称称为为知识知识。 “信息信息”与与“关联关联”是构成知识的两个要是构成知识的两个要素。素。 信息之间关联的形式可以多种多样，其中信息之间关联的形式可以多种多样，其中最常用的一种形式是：最常用的一种形式是：如果如果，则，则。例如，例如，“如果他学过软件技术前沿课程，则他如果他学过软件技术前沿课程，则他应该知道什么叫软件智能化应该知道什么叫软件智能化”。5（1 1）真假性与相对性）真假性与相对性知识的属性：知识的属性： 真假性是指可以通过实践或推理来证真假性是指可以通过实践或推理来证明知识为真或为假。明知识为真或为假。 相对性是指知识的真与假是

4、相对于某相对性是指知识的真与假是相对于某些条件、环境及时间而言的，即知识一般些条件、环境及时间而言的，即知识一般不是无条件的真或无条件的假，而是相对不是无条件的真或无条件的假，而是相对于一定条件的。于一定条件的。6 知识的不确定性包括知识的不确定性包括不完备性不完备性、不确定性不确定性与与模糊性：模糊性： （2 2）不确定性）不确定性 知识的知识的不完备性不完备性是指在解决问题时不具备是指在解决问题时不具备解决该问题所需要的全部知识。解决该问题所需要的全部知识。 知识的知识的不确定性不确定性是指知识所具有的既不能是指知识所具有的既不能完全被确定为真，又不能完全被确定为假的完全被确定为真，又不能

5、完全被确定为假的特性。特性。知识的知识的模糊性模糊性是指知识的是指知识的“边界边界”不明确的不明确的特性。特性。7 矛盾性是指同一个知识集中的不同知识之矛盾性是指同一个知识集中的不同知识之间相互对立或不一致，即从这些知识出发，会间相互对立或不一致，即从这些知识出发，会推出不一致的结论。推出不一致的结论。 相容性是指同一个知识集中的所有知识之相容性是指同一个知识集中的所有知识之间互相不矛盾。间互相不矛盾。（3 3）矛盾性和相容性）矛盾性和相容性8 可表示性是指知识可以用适当的形式表可表示性是指知识可以用适当的形式表示出来。例如，语言、文字、图形、神经元网示出来。例如，语言、文字、图形、神经元网络

6、等。络等。 可利用性是指知识可以被用来解决各种可利用性是指知识可以被用来解决各种各样的问题。各样的问题。（4 4）可表示性与可利用性）可表示性与可利用性9（1 1）按知识的性质：）按知识的性质： 知识的类型：知识的类型： 概念概念 命题命题 公理公理 定理定理 规则规则 方法方法 10 常识性知识：是指通用通识的知识。即人常识性知识：是指通用通识的知识。即人们普遍知道的、适应于所有领域的知识。们普遍知道的、适应于所有领域的知识。 领域性知识：是指面向某个具体专业的专领域性知识：是指面向某个具体专业的专业性知识，这些知识只有该领域的专业人员才业性知识，这些知识只有该领域的专业人员才能够掌握和运用

7、它。能够掌握和运用它。（2 2）按知识的作用范围：）按知识的作用范围：11 事实性知识：事实性知识：亦称为叙述性知识，是用亦称为叙述性知识，是用来描述问题或事物的概念、属性、状态、环境来描述问题或事物的概念、属性、状态、环境及条件等情况的知识。及条件等情况的知识。 过程性知识：过程性知识：是用来描述问题求解过程是用来描述问题求解过程所需要的操作、演算或行为等规律性的知识，所需要的操作、演算或行为等规律性的知识，它指出在问题求解过程中如何使用那些与问题它指出在问题求解过程中如何使用那些与问题有关的事实性知识，即用来说明在那些叙述性有关的事实性知识，即用来说明在那些叙述性知识成立的时候该怎么办。知

8、识成立的时候该怎么办。 控制性知识：控制性知识：亦称元知识或超知识，是亦称元知识或超知识，是关于如何运用已有知识进行问题求解的知识，关于如何运用已有知识进行问题求解的知识，因此，也称为关于知识的知识。因此，也称为关于知识的知识。（3 3）按知识的作用）按知识的作用12 表层知识是指客观事物的现象以及这些现象表层知识是指客观事物的现象以及这些现象与结论之间关系的知识。与结论之间关系的知识。 深层知识是指事物本质、因果关系内涵、基深层知识是指事物本质、因果关系内涵、基本原理之类的知识。例如，理论知识、理性知本原理之类的知识。例如，理论知识、理性知识等。识等。（4 4）按知识的层次）按知识的层次13

9、 确定性知识：是可以给出其真值为确定性知识：是可以给出其真值为“真真”或或“假假”的知识。这些知识是可以精确的知识。这些知识是可以精确表示的知识。表示的知识。 不确定性知识：是指具有不确定性知识：是指具有“不确定不确定”特特性的知识。不确定性的概念包含不精确、性的知识。不确定性的概念包含不精确、不完备和模糊。不完备和模糊。（5 5）按知识的确定性）按知识的确定性14 逻辑性知识：是反映人类逻辑思维过程逻辑性知识：是反映人类逻辑思维过程的知识，例如人类的经验性知识。它对应着逻的知识，例如人类的经验性知识。它对应着逻辑思维。辑思维。 形象性知识：是通过事物的形象建立起形象性知识：是通过事物的形象建

10、立起来的知识，它对应着形象思维。例如，一个人来的知识，它对应着形象思维。例如，一个人的相貌，要用文字来描述非常困难，但要亲眼的相貌，要用文字来描述非常困难，但要亲眼见到这个人，就很容易在头脑中形成这个人的见到这个人，就很容易在头脑中形成这个人的概念。概念。（6 6）按知识的结构及表现形式）按知识的结构及表现形式15 所谓知识表示实际上就是对知识的一种描所谓知识表示实际上就是对知识的一种描述，即用一些约定的符号把知识编码成一组计述，即用一些约定的符号把知识编码成一组计算机可以接受的数据结构。所谓知识表示过程算机可以接受的数据结构。所谓知识表示过程就是把知识编码成某种数据结构的过程。一般就是把知识

11、编码成某种数据结构的过程。一般来说，同一知识可以有多种不同的表示形式，来说，同一知识可以有多种不同的表示形式，而不同表示形式所产生的效果又可能不一样。而不同表示形式所产生的效果又可能不一样。二二. . 知识表示知识表示16（1 1）表示能力）表示能力 知识表示能力是指能否正确、有效地将问题知识表示能力是指能否正确、有效地将问题求解所需要的各种知识表示出来。知识表示能力求解所需要的各种知识表示出来。知识表示能力包括以下三个方面：一是知识表示范围的广泛性包括以下三个方面：一是知识表示范围的广泛性；二是领域知识表示的高效性；三是对非确定性；二是领域知识表示的高效性；三是对非确定性知识表示的支持程度。

12、知识表示的支持程度。知识表示的要求：知识表示的要求：17 （2 2）可利用性）可利用性 知识的利用是指使用知识进行推理，以求知识的利用是指使用知识进行推理，以求得问题的解。知识的可利用性包括对推理的适得问题的解。知识的可利用性包括对推理的适应性和对高效算法的支持性。应性和对高效算法的支持性。（3 3）可组织性与可维护性）可组织性与可维护性 知识的组织是指把有关知识按照某种方式知识的组织是指把有关知识按照某种方式组成一种知识结构。知识维护是指在保证知识组成一种知识结构。知识维护是指在保证知识的一致性与完整性的前提下对知识所进行的增的一致性与完整性的前提下对知识所进行的增加、删除、修改等操作。加、

13、删除、修改等操作。18（4 4）可实现性）可实现性 所谓可实现性是指知识表示要便于在计算机所谓可实现性是指知识表示要便于在计算机上实现，便于直接由计算机对其进行处理。上实现，便于直接由计算机对其进行处理。（5 5）自然性与可理解性）自然性与可理解性 自然性是指知识表示形式要符合人们的日常自然性是指知识表示形式要符合人们的日常习惯和思维方式。可理解性是指所表示的知识应习惯和思维方式。可理解性是指所表示的知识应易读、易懂、易获取、易维护。易读、易懂、易获取、易维护。 19（1 1）陈述性观点）陈述性观点 陈述性知识表示（陈述性知识表示（Declarative knowledge represent

14、ation）是指以陈述的方式把知识用一是指以陈述的方式把知识用一定定 的数据结构表示出来，即把知识看作一种特的数据结构表示出来，即把知识看作一种特殊的数据，知识表示说明描述的对象是什么，不殊的数据，知识表示说明描述的对象是什么，不涉及如何运用知识的问题。涉及如何运用知识的问题。知识表示观点：知识表示观点：20（2 2）过程性观点）过程性观点 过程性知识表示（过程性知识表示（Procedural knowkdge Procedural knowkdge representationrepresentation）是指以程序（亦称为过程）是指以程序（亦称为过程）的方式把知识表示出来，即把知识寓于程序

15、之的方式把知识表示出来，即把知识寓于程序之中，把知识表示和运用知识结合起来。中，把知识表示和运用知识结合起来。21 知识表示方法又称为知识表示技术，其知识表示方法又称为知识表示技术，其表示形式被称为知识表示模式。目前，使用表示形式被称为知识表示模式。目前，使用较多的知识表示方法有较多的知识表示方法有1010余种，如余种，如: : 状态空间法状态空间法 问题归约法问题归约法 谓词逻辑法谓词逻辑法 语义网络法语义网络法 框架表示法框架表示法 剧本表示法剧本表示法 过程表示法过程表示法 面向对象表示法面向对象表示法知识表示方法：知识表示方法：22 对软件智能研究中运用的问题求解方法进对软件智能研究中

16、运用的问题求解方法进行综合分析，可以发现许多问题求解方法是行综合分析，可以发现许多问题求解方法是采用试探搜索方法的。采用试探搜索方法的。 也就是说，这种方法是通过在某个可能的也就是说，这种方法是通过在某个可能的解空间内寻找一个解来求解问题的。解空间内寻找一个解来求解问题的。 这种这种基于解答空间的问题表示和求解方法基于解答空间的问题表示和求解方法就是就是状态空间法状态空间法。 状态空间法是以状态空间法是以状态状态和和算符算符为基础来表示为基础来表示和求解问题的。和求解问题的。状态空间法状态空间法23实例实例：十五数码难题十五数码难题一一. . 问题的状态描述问题的状态描述如何把初始棋局变换为目

17、标棋局？如何把初始棋局变换为目标棋局？24最直接的求解方法最直接的求解方法：尝试各种不同的走步，尝试各种不同的走步，直到偶然得到目标棋局为止，即直到偶然得到目标棋局为止，即试探搜索试探搜索。25对十五数码难题的问题描述和求解过程进行分析：对十五数码难题的问题描述和求解过程进行分析：初始状态初始状态：初始棋局。：初始棋局。 1111，9 9，4 4，1515，1 1，3 3，0 0，1212，7 7，5 5，8 8，6 6，1313，2 2，1010，1414操作符操作符：走步。走步。 右移棋子右移棋子3 3，下移棋子，下移棋子4 4，左移棋子，左移棋子1212，. . （6060条）条） 或者

18、：移动空格或者：移动空格 （4 4条）条）目标状态目标状态：目标棋局。：目标棋局。 11，2 2，3 3，4 4，5 5，6 6，7 7，8 8，9 9，1010，1111，1212，1313，1414，1515，00状态空间法状态空间法：从某个初始状态开始，每次加一个：从某个初始状态开始，每次加一个操作符，递增地建立起操作符的试验序列，直到操作符，递增地建立起操作符的试验序列，直到达到目标状态为止。达到目标状态为止。状态图状态图：初始状态可达到的各状态所对应的节点：初始状态可达到的各状态所对应的节点组成的图。组成的图。26问题状态的描述：问题状态的描述：状态状态：为描述某类不同事物间的差别而

19、引入的一组最少变：为描述某类不同事物间的差别而引入的一组最少变量量q q0 0，q q1 1，q qn n的有序集合，其矢量形式如下：的有序集合，其矢量形式如下： Q=qQ=q0 0，q q1 1，q qn n 状态变量状态变量：状态集合中的每个元素：状态集合中的每个元素q qi i（i=0,1,i=0,1,n,n）。）。具体状态具体状态：给定每个分量的一组值。如：给定每个分量的一组值。如 Q Qk k=q=q0k0k，q q1k1k，q qnknk 操作符操作符：使问题从一种状态变换到另一种状态的手段，也：使问题从一种状态变换到另一种状态的手段，也叫算符。算符可以是走步、过程、规则、数学算子

20、、运算叫算符。算符可以是走步、过程、规则、数学算子、运算符号或逻辑符号等。符号或逻辑符号等。问题的状态空间：问题的状态空间：表示该问题全部可能状态及其关系的图。表示该问题全部可能状态及其关系的图。它包含三种说明的集合，即所有可能的问题它包含三种说明的集合，即所有可能的问题初始状态集合初始状态集合S S、操作符集合操作符集合F F以及以及目标状态集合目标状态集合G G。 因此，状态空间可记为三元组因此，状态空间可记为三元组（S S，F F，G G）。 27图论中的几个术语：图论中的几个术语： 图图；有向图有向图；后继节点（后裔）后继节点（后裔）；父辈节父辈节点（祖先）点（祖先）； 路径（长度为路

21、径（长度为k k的路径）的路径）；节点节点n nj j是从节点是从节点n ni i可达到的路径可达到的路径； 代价代价；两节点间路径的代价两节点间路径的代价。 当用一个图来表示某个状态空间时，图中当用一个图来表示某个状态空间时，图中各节点标上相应的状态描述，而有向弧线旁边各节点标上相应的状态描述，而有向弧线旁边标上算符。标上算符。 寻找从一种状态变换为另一种状态的某个寻找从一种状态变换为另一种状态的某个算符序列问题等价于寻找图的某一路径问题。算符序列问题等价于寻找图的某一路径问题。二二. . 状态图示法状态图示法28 图的显式说明图的显式说明：图中的各节点及其具有代价：图中的各节点及其具有代价

22、的弧线由一张图或表明确给出。的弧线由一张图或表明确给出。 图的隐式说明图的隐式说明：图中的节点集合是无限的，：图中的节点集合是无限的，但起始节点是已知的，而且引入后继算符的概念但起始节点是已知的，而且引入后继算符的概念是方便的。把后继节点算符作用于任一节点可以是方便的。把后继节点算符作用于任一节点可以产生该节点的全部后继节点和各连接弧线的代价。产生该节点的全部后继节点和各连接弧线的代价。 搜索某个状态空间以求得算符序列的一个解搜索某个状态空间以求得算符序列的一个解答过程，就是答过程，就是使隐式图足够大一部分变为显式以使隐式图足够大一部分变为显式以便包含目标便包含目标的过程，这是状态空间问题求解

23、的基的过程，这是状态空间问题求解的基础。础。 问题的表示对求解工作量有很大的影响。问题的表示对求解工作量有很大的影响。29 问题的状态表示方法涉及在状态描述中问题的状态表示方法涉及在状态描述中如何应用变量。应该用一个包含变量的表达如何应用变量。应该用一个包含变量的表达式来描述状态的全部集合，而不仅仅描述一式来描述状态的全部集合，而不仅仅描述一个状态。个状态。 用常量取代表达式中的变量，就可得到用常量取代表达式中的变量，就可得到一个具体的状态描述。用来描述一个状态集一个具体的状态描述。用来描述一个状态集合的含有变量的表达式，叫做合的含有变量的表达式，叫做状态描述模式状态描述模式。30三三. .

24、状态空间表示举例状态空间表示举例 实例实例： 猴子摘香蕉问题猴子摘香蕉问题a c b箱子箱子31 实例实例： 猴子摘香蕉问题猴子摘香蕉问题问题状态的表示：问题状态的表示：四元组（四元组（W，x，Y，z） W：猴子的水平位置。猴子的水平位置。W=a，b，c。 x：当猴子在箱子顶上时取当猴子在箱子顶上时取x=1；否则取否则取x=0。 Y：箱子的水平位置。箱子的水平位置。Y=a，b，c。 z：当猴子摘到香蕉时取当猴子摘到香蕉时取z=1；否则取否则取z=0。初始状态：初始状态：（a，0，b，0）目标状态：目标状态：（c，1，c，1）32算符集合：算符集合： goto(U)：猴子走到水平位置猴子走到水平

25、位置U。 （W，0，Y，z） goto(U) （U，0，Y，z） pushbox(V)：猴子把箱子推到水平位置猴子把箱子推到水平位置V。 （W，0，W，z） pushbox(V) （V，0，V，z） climbbox：猴子爬上箱顶。猴子爬上箱顶。 （W，0，W，z） climbbox （W，1，W，z） grasp：猴子摘到香蕉。猴子摘到香蕉。 （c，1，c，0） grasp （c，1，c，1）算符的适用性条件：强加于操作的实用性条件。算符的适用性条件：强加于操作的实用性条件。 如：应用算符如：应用算符pushbox(V)时，要求猴子与箱子必须时，要求猴子与箱子必须在同一位置。在同一位置。33

26、操作序列：操作序列：goto(b)，pushbox(c)，climbbox，grasp猴子摘香蕉问题的状态空间图如下图所示。猴子摘香蕉问题的状态空间图如下图所示。34练习题：练习题： 设有设有3个传教士和个传教士和3个野人来到河边，个野人来到河边，打算乘一只船从右岸渡到左岸去。该船的打算乘一只船从右岸渡到左岸去。该船的负载能力为两人。在任何时候，如果野人负载能力为两人。在任何时候，如果野人人数超过传教士人数，那么野人就会把传人数超过传教士人数，那么野人就会把传教士吃掉。他们怎样才能用这条船安全地教士吃掉。他们怎样才能用这条船安全地把所有人都渡过河去？把所有人都渡过河去？35问题归约法问题归约法

27、问题归约法问题归约法：在现实生活中，有许多问：在现实生活中，有许多问题可以通过一系列变换而最终变为一个题可以通过一系列变换而最终变为一个子问题集合；这些子问题的解可以直接子问题集合；这些子问题的解可以直接得到，通过解决这些子问题，从而就解得到，通过解决这些子问题，从而就解决了初始问题。这样一种解决问题的思决了初始问题。这样一种解决问题的思路就称为是问题归约法。路就称为是问题归约法。36实例实例：梵塔难题梵塔难题一一. . 问题的归约描述问题的归约描述如何由初始配置变换为目标配置？如何由初始配置变换为目标配置？ABC123ABC123初始配置初始配置目标配置目标配置37求解思路求解思路：（把原始

28、问题归约为一个比较简单的问题的集合）（把原始问题归约为一个比较简单的问题的集合）ABC123ABC123111122ABC123ABC123122322ABC123ABC123322333 要把所有圆盘都移至柱要把所有圆盘都移至柱子子3，必须先把圆盘，必须先把圆盘C移至移至柱子柱子3；而且在移动圆盘；而且在移动圆盘C至柱子至柱子3之前，柱子之前，柱子3必须必须是空的。是空的。 只有在移开圆盘只有在移开圆盘A和和B之之后，才能移动圆盘后，才能移动圆盘C；而而且圆盘且圆盘A和和B最好不要移至最好不要移至柱子柱子3。因此，应该把。因此，应该把A和和B移到柱子移到柱子2上。上。 把圆盘把圆盘C从柱子从

29、柱子1移动到移动到柱子柱子3，并继续解决其余部，并继续解决其余部分的移动问题。分的移动问题。 （移动移动A、B - 2）（移动移动C - 3）（移动移动A、B - 3）38通过以上分析，我们把原始问题归约为通过以上分析，我们把原始问题归约为3个子问题：个子问题：（1） 移动移动A、B - 2 双圆盘问题：可进一步归约双圆盘问题：可进一步归约（2） 移动移动C - 3 单圆盘问题：可直接求解单圆盘问题：可直接求解-本原问题本原问题（3） 移动移动A、B - 3 双圆盘问题：可进一步归约双圆盘问题：可进一步归约与或图与或图：可以有效说明问题归约法的求解过程。：可以有效说明问题归约法的求解过程。梵塔

30、问题归约图梵塔问题归约图39问题归约描述问题归约描述： 采用问题归约法采用问题归约法 描述与求解问题时描述与求解问题时 问题归约表示由问题归约表示由三部分组成：三部分组成：（1）一个一个初始问题描述初始问题描述 如：如：（111），（），（333）（2）一套把问题变换为子问题的操作符一套把问题变换为子问题的操作符问题归问题归约算符约算符 如：移动如：移动A、B - 2 等等（3）一套一套本原问题描述本原问题描述 如：如：（122），（），（322） 本原问题：本原问题：是可直接求解或具有已知解答的问题，出现是可直接求解或具有已知解答的问题，出现本原问题即可停止搜索。本原问题即可停止搜索。问题归

31、约法的实质问题归约法的实质：从目标（要解决的问题）出发：从目标（要解决的问题）出发逆向逆向推理推理，建立子问题以及子问题的子问题，直至最后把初，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个本原问题集合。始问题归约为一个本原问题集合。问题归约的目的问题归约的目的：最终产生具有明显解答的本原问题。：最终产生具有明显解答的本原问题。 40二二. . 与或图表示与或图表示用问题归约法描述和求解问题的过程可以用一个与或图用问题归约法描述和求解问题的过程可以用一个与或图来表示。来表示。关于与或图：关于与或图：例如：设想问题例如：设想问题A既可由求解问题既可由求解问题B和和C，也可由求解问题也

32、可由求解问题D、E和和F，或或者由单独求解问题者由单独求解问题H来解决。这一关来解决。这一关系可由右图所示的结构图来表示。系可由右图所示的结构图来表示。为了使含有一个以上后继问题的每个集合为了使含有一个以上后继问题的每个集合能够聚集在它们各自的父辈节点之下，我能够聚集在它们各自的父辈节点之下，我们在上述结构图中引入们在上述结构图中引入附加节点附加节点。如右图，。如右图，可以认为问题可以认为问题A被归约为单一子问题被归约为单一子问题N、M和和H，N、M和和H叫叫或节点或节点。问题。问题N被归被归约为子问题约为子问题B和和C的单一集合，要求解的单一集合，要求解N就必须求解所有的子问题，因此，就必须

33、求解所有的子问题，因此，B和和C叫做叫做与节点与节点。各个与节点用跨接指向他们。各个与节点用跨接指向他们后继节点的弧线的小段圆弧加以标记。后继节点的弧线的小段圆弧加以标记。这样形成的结构图就叫这样形成的结构图就叫与或图与或图。41关于与或图的几点说明：关于与或图的几点说明： 在与或图中，如果一个节点具有任何后继节点，在与或图中，如果一个节点具有任何后继节点，那么这些后继节点既可全为与节点，也可全为或节点。那么这些后继节点既可全为与节点，也可全为或节点。 特殊情况下，根本不出现任何与节点，如在状态特殊情况下，根本不出现任何与节点，如在状态空间图中就不存在与节点，即状态空间图是普通图，因空间图中就

34、不存在与节点，即状态空间图是普通图，因此可以说问题归约法是比状态空间法更通用的问题求解此可以说问题归约法是比状态空间法更通用的问题求解方法。方法。 通过与或图，在某个问题描述中应用问题归约算通过与或图，在某个问题描述中应用问题归约算符，可以依次产生出一个中间或节点和与节点后裔，从符，可以依次产生出一个中间或节点和与节点后裔，从而可以用与或图来表示问题归约方法的相关结构。而可以用与或图来表示问题归约方法的相关结构。 在与或图中，起始节点对应于原始问题描述，叶在与或图中，起始节点对应于原始问题描述，叶子节点对应于本原问题描述。子节点对应于本原问题描述。42 引入与或图后，问题求解过程就转换为与或图

35、引入与或图后，问题求解过程就转换为与或图上的搜索过程，搜索的目的是要表明起始节点有上的搜索过程，搜索的目的是要表明起始节点有解，在与或图中一个解，在与或图中一个可解节点可解节点的一般定义可以归的一般定义可以归纳如下：纳如下： （1）叶子节点是可解节点（本原问题）。叶子节点是可解节点（本原问题）。 （2）如果某个非叶节点含有或后继节点，那么只有当其如果某个非叶节点含有或后继节点，那么只有当其后继节点至少有一个可解时，该非叶节点才是可解的。后继节点至少有一个可解时，该非叶节点才是可解的。 （3）如果某个非叶节点含有与后继节点，那么只有当其如果某个非叶节点含有与后继节点，那么只有当其后继节点全部可解

36、时，该非叶节点才是可解的。后继节点全部可解时，该非叶节点才是可解的。 在上述定义基础上，可以给出解图的定义，在上述定义基础上，可以给出解图的定义，即即解图解图是那些可解节点的子图，这些节点能够证是那些可解节点的子图，这些节点能够证明其初始节点是可解的。明其初始节点是可解的。43 当与或图中某些非叶节点完全没有后继节点当与或图中某些非叶节点完全没有后继节点时，我们就说它是不可解的。这些不可解节点的时，我们就说它是不可解的。这些不可解节点的出现可能意味着图中另外一些节点也是不可解的。出现可能意味着图中另外一些节点也是不可解的。不可解节点不可解节点的一般定义可以归纳如下：的一般定义可以归纳如下： （

37、1）没有后裔的非叶节点是不可解节点。没有后裔的非叶节点是不可解节点。 （2）如果某个非叶节点含有或后继节点，那么只有当其如果某个非叶节点含有或后继节点，那么只有当其全部后继节点不可解时，该非叶节点才是不可解的。全部后继节点不可解时，该非叶节点才是不可解的。 （3）如果某个非叶节点含有与后继节点，那么只有当其如果某个非叶节点含有与后继节点，那么只有当其后继节点至少有一个不可解时，该非叶节点才是不可解的。后继节点至少有一个不可解时，该非叶节点才是不可解的。 与状态空间图求解一样，一般很少用显式图与状态空间图求解一样，一般很少用显式图来搜索，而是用由初始问题描述和问题归约算符来搜索，而是用由初始问题

38、描述和问题归约算符所定义的隐式图来搜索，这样，问题求解过程实所定义的隐式图来搜索，这样，问题求解过程实际上就是际上就是生成与或图的足够部分，以证明初始节生成与或图的足够部分，以证明初始节点可解点可解。44综上所述，与或图的构成规则可以概括如下：综上所述，与或图的构成规则可以概括如下：（1）与或图中的每个节点代表一个要解决的单一问题或问题集合，起与或图中的每个节点代表一个要解决的单一问题或问题集合，起始节点对应于原始问题。始节点对应于原始问题。（2）对应于本原问题的节点，叫做叶子节点，它没有后裔。对应于本原问题的节点，叫做叶子节点，它没有后裔。 （3）对于把问题归约算符应用于问题对于把问题归约算

39、符应用于问题A的每种可能情况，都把问题变换的每种可能情况，都把问题变换为一个子问题的集合，有向弧线由为一个子问题的集合，有向弧线由A指向后继节点，表示所求得的子问指向后继节点，表示所求得的子问题集合。如问题题集合。如问题A可归约为不同的子问题集合可归约为不同的子问题集合N、M和和H，只要只要N、M和和H有一个可解，则有一个可解，则A可解，所以可解，所以N、M和和H称为或节点。称为或节点。（4）对于代表两个或两个以上子问题集合的每个节点，有向弧线从该对于代表两个或两个以上子问题集合的每个节点，有向弧线从该节点指向该子问题集合中的各个节点。因为只有当集合中的所有项都有节点指向该子问题集合中的各个节

40、点。因为只有当集合中的所有项都有解时，该子问题才有解，所以这些子问题节点叫与节点。为了和或节点解时，该子问题才有解，所以这些子问题节点叫与节点。为了和或节点进行区分，把具有共同父辈的与节点后裔的所有弧线用另外一段小弧线进行区分，把具有共同父辈的与节点后裔的所有弧线用另外一段小弧线连接起来。连接起来。（5）特殊情况下，当只有一个算符可应用于问题特殊情况下，当只有一个算符可应用于问题A，而且这个算符产生而且这个算符产生具有一个以上子问题的某个集合时，由（具有一个以上子问题的某个集合时，由（3）和（）和（4）所产生的图可以得）所产生的图可以得到简化，将代表子问题集合的中间或节点略去。到简化，将代表子

41、问题集合的中间或节点略去。 利用上述规则生成的与或图中，每个节点代表一个问题或问题集合，利用上述规则生成的与或图中，每个节点代表一个问题或问题集合，除起始节点外，每个节点只有一个父节点，所以这样的与或图实际是除起始节点外，每个节点只有一个父节点，所以这样的与或图实际是与与或树或树。45三三. . 问题归约机理问题归约机理出发点出发点引入关键算符引入关键算符： 对于状态空间的搜索问题，虽然寻求某对于状态空间的搜索问题，虽然寻求某个解答中的整个算符序列比较困难，但规定个解答中的整个算符序列比较困难，但规定这些算符中的一个却往往比较容易。如果某这些算符中的一个却往往比较容易。如果某个算符被认为是求解

42、问题的决定性步骤，那个算符被认为是求解问题的决定性步骤，那么就很容易找到这样一个算符。例如，梵塔么就很容易找到这样一个算符。例如，梵塔难题中难题中“移动移动C - 3”这个算符就是求解问题这个算符就是求解问题的决定性步骤，也很容易找到该算符，这种的决定性步骤，也很容易找到该算符，这种具有决定性作用的算符叫做具有决定性作用的算符叫做关键算符关键算符。46关键算符的作用：关键算符的作用： 确定了某个关键算符后，就可以以该关键算确定了某个关键算符后，就可以以该关键算符为基础进行问题归约。例如，在三元状态（符为基础进行问题归约。例如，在三元状态（S，F，G）表示的问题中，假设表示的问题中，假设F中的某

43、个中的某个f是关键算是关键算符，那么可以认为（符，那么可以认为（S，F，G）的第一个后裔问的第一个后裔问题是一个对应于寻找一条通向某一题是一个对应于寻找一条通向某一f适用的状态的适用的状态的路径问题，令路径问题，令Gf表示表示f适用的所有状态的集合，则适用的所有状态的集合，则该后裔问题是由该后裔问题是由（S，F， Gf ）描述的子问题。一描述的子问题。一旦该子问题得到解决，就可以进一步解决由旦该子问题得到解决，就可以进一步解决由（g，F，f（g）所表示的子问题，其中所表示的子问题，其中g Gf ，f（g）表示把表示把f应用于应用于g而得到的状态，因为该子问而得到的状态，因为该子问题是仅由应用关

44、键算符题是仅由应用关键算符f就可以解决，所以是本原就可以解决，所以是本原问题。于是，剩下的就是解决由问题。于是，剩下的就是解决由（ f（g），F，G ）所描述的子问题。所描述的子问题。47关键算符的作用：关键算符的作用：可见，一旦确定了某个关键算符可见，一旦确定了某个关键算符f，就可以把问题归约就可以把问题归约为如下三个子问题：为如下三个子问题： （1）（S，F， Gf ）；）； （2）（g，F，f（g）；）； （3）（ f（g），F，G ）。问题（问题（2）是本原问题）是本原问题问题（问题（1）和（）和（3）可以用直接的状态空间搜索技术或）可以用直接的状态空间搜索技术或进一步的问题归约来求解

45、（寻找子问题的关键算符，进一步的问题归约来求解（寻找子问题的关键算符，进一步归约下去）。进一步归约下去）。48关键算符的作用：关键算符的作用： 对于许多问题，我们往往无法预先知道哪个对于许多问题，我们往往无法预先知道哪个算符是关键算符，我们只能推测某个算符的子集，算符是关键算符，我们只能推测某个算符的子集，该子集中的某个算符可能是关键算符。因此，用该子集中的某个算符可能是关键算符。因此，用该子集中的每个算符产生一对后裔子问题，这样该子集中的每个算符产生一对后裔子问题，这样就建立起了一个就建立起了一个与或图与或图。 可见，要应用这种方法，首先必须寻找任可见，要应用这种方法，首先必须寻找任何状态空

46、间搜索问题的何状态空间搜索问题的候选关键算符集合候选关键算符集合。 如何寻找候选关键算符呢？如何寻找候选关键算符呢？计算某个计算某个问题的问题的差别差别。49什么是差别？什么是差别？ 实例：猴子摘香蕉问题实例：猴子摘香蕉问题把把4个算符的作用结果和使用条件重写如下：个算符的作用结果和使用条件重写如下： f1：（：（W，0，Y，z） goto(U) （U，0，Y，z）f2：（：（W，0，W，z） pushbox(V) （V，0，V，z）f3：（：（W，0，W，z） climbbox （W，1，W，z）f4：（：（c，1，c，0） grasp （c，1，c，1）初始状态初始状态： （a，0，b，0

47、）算符集合：算符集合： F=f1，f2，f3，f4满足目标条件的状态集合：满足目标条件的状态集合：G50实例：猴子摘香蕉问题实例：猴子摘香蕉问题 应用关键算符和差别的归约过程如下：应用关键算符和差别的归约过程如下： 首先计算初始问题的差别，首先计算初始问题的差别， （a，0，b，0） 不满足目标测试的原因在于其最后一个元素不是不满足目标测试的原因在于其最后一个元素不是1。与归约这个差别相关的关键算符是。与归约这个差别相关的关键算符是f4=grasp，用用f4来归约初始问题，得到如下子问题：来归约初始问题，得到如下子问题： （1）（a，0，b，0），F，Gf4） （2）（S1，F，f4（S1）

48、（本原问题）本原问题） （3） （f4（S1），），F，G） （本原问题）本原问题） 其中其中Gf4是适用于算符是适用于算符f4的状态描述集合，的状态描述集合，S1 Gf4 。51 要求解问题（要求解问题（1），就要先计算其差别。由），就要先计算其差别。由（a，0，b，0）所描述的状态不在所描述的状态不在Gf4中，差别如下：中，差别如下：箱子不在箱子不在c处处猴子不在猴子不在c处处猴子不在箱子上猴子不在箱子上f2=pushbox（c）f1=goto（c）f3=climbbox 与差别相与差别相关的关键算关的关键算符号如右符号如右 用关键算符用关键算符f2归约问题（归约问题（1），得到如下子问题

49、：），得到如下子问题： （1-1）（a，0，b，0），F，Gf2） （1-2）（S11，F，f2（S11） （本原问题）本原问题） （1-3） （f2（S11），），F， Gf4 ） Gf2是适用于算符是适用于算符f2的状态描述集合，的状态描述集合，S11 Gf2 52 现在必须求解问题（现在必须求解问题（1-1），所以仍需要先计），所以仍需要先计算其差别。此差别为：算其差别。此差别为：猴子不在猴子不在b处处f1=goto（b） 与差别相关的关与差别相关的关键算符号如右键算符号如右用关键算符用关键算符f1归约问题（归约问题（1-1），得到如下子问题：），得到如下子问题：（1-11）（a，0，b

50、，0），F，Gf1） （差别为差别为0，本原问题，可直接用，本原问题，可直接用f1求解）求解）（1-12）（S111，F，f1（S111） （本原问题）本原问题）（1-13） （f1（S111），），F， Gf2 ） Gf1是适用于算符是适用于算符f1的状态描述集合，的状态描述集合，S111 Gf1 。53 现在需要求解问题（现在需要求解问题（1-13），由于），由于f1（S111）=（b，0，b，0），），所以问题所以问题（1-13）变为：）变为： （ （b，0，b，0） ，F， Gf2 ） ，这个问题也是本原问题，可以这个问题也是本原问题，可以直接用直接用f2求解。求解。 把先前产生的问题

51、求解过程继把先前产生的问题求解过程继续下去，直到最后解答此初始问题续下去，直到最后解答此初始问题为止。为止。54 通过该实例分析，可以看出：通过该实例分析，可以看出： 问题（问题（S，F，G）的的差别差别就是用就是用S的元对由集的元对由集合合G规定的目标进行测试失败原因的部分表列（如规定的目标进行测试失败原因的部分表列（如果果S的某个元是在的某个元是在G中，那么该问题就获得解决，中，那么该问题就获得解决，也就不存在差别）。例如，如果目标集合也就不存在差别）。例如，如果目标集合G由某个由某个状态条件集合所规定，而且某个状态条件集合所规定，而且某个s S满足这些条满足这些条件中的某些但不是全部条件

52、，那么差别可由不能件中的某些但不是全部条件，那么差别可由不能被被s满足的条件的部分表列组成。如果这些条件能满足的条件的部分表列组成。如果这些条件能够按其重要性分类，那么我们应该够按其重要性分类，那么我们应该选择最重要的选择最重要的不满足条件作为差别不满足条件作为差别。 当把每个可能的差别与某些算符或算符集合当把每个可能的差别与某些算符或算符集合结合起来时，这些算符就是结合起来时，这些算符就是候选关键算符候选关键算符。只有。只有当应用某个算符是与消去某个差别相关时，该算当应用某个算符是与消去某个差别相关时，该算符才与那个差别结合在一起。符才与那个差别结合在一起。55 谓词逻辑表示法是一种基于数理

53、逻辑的知识表示谓词逻辑表示法是一种基于数理逻辑的知识表示方式。数理逻辑是一门研究推理的科学，它作为软件方式。数理逻辑是一门研究推理的科学，它作为软件智能的基础，在软件智能的发展中占有重要地位。软智能的基础，在软件智能的发展中占有重要地位。软件智能中用到的逻辑可分为两大类：一类是一阶经典件智能中用到的逻辑可分为两大类：一类是一阶经典命题逻辑和谓词逻辑；另一类是除经典逻辑以外的那命题逻辑和谓词逻辑；另一类是除经典逻辑以外的那些逻辑。些逻辑。 这里所说的谓词逻辑法涉及一阶经典命题逻辑和这里所说的谓词逻辑法涉及一阶经典命题逻辑和谓词逻辑。谓词逻辑。谓词逻辑法谓词逻辑法56 一阶谓词逻辑知识表示中所需要

54、的逻辑基础包一阶谓词逻辑知识表示中所需要的逻辑基础包括有：括有：命题、谓词、连词、量词、谓词公式命题、谓词、连词、量词、谓词公式等。等。 一一. . 谓词逻辑表示法的逻辑基础谓词逻辑表示法的逻辑基础571 1命题与真值命题与真值 定义：定义：一个陈述句称为一个一个陈述句称为一个断言断言。凡有真假意义的。凡有真假意义的断言称为断言称为命题命题。 命题的意义通常称为命题的意义通常称为真值真值，它只有真假两种情况。，它只有真假两种情况。当命题的意义为真时，则称该命题的真值为真，记为当命题的意义为真时，则称该命题的真值为真，记为T T；反之，则称该命题的真值为假，记为反之，则称该命题的真值为假，记为F

55、 F。在命题逻辑中，在命题逻辑中，命题通常用大写的英文字母来表示。命题通常用大写的英文字母来表示。 一个命题不能同时既为真又为假一个命题不能同时既为真又为假。 例如：例如： “天安门城楼在长安街的北边天安门城楼在长安街的北边” 是一个真值为是一个真值为T T的命题的命题 “天安门广场在长安街的北边天安门广场在长安街的北边” 则是一个真值为则是一个真值为F F的命的命题题一一. . 谓词逻辑表示法的逻辑基础谓词逻辑表示法的逻辑基础58关于命题关于命题： 一个命题可在一定条件下为真，在另一种条件下一个命题可在一定条件下为真，在另一种条件下为假。例如，命题为假。例如，命题“北京今天有雨北京今天有雨”

56、，需要根据当，需要根据当天的实际情况来决定其真值。天的实际情况来决定其真值。没有真假意义的感叹句、疑问句等都不是命题。没有真假意义的感叹句、疑问句等都不是命题。例如，例如，“今天好冷啊！今天好冷啊！”和和“今天的温度有多少今天的温度有多少度？度？”都不是命题。都不是命题。命题的优点是简单、明确；其主要缺点是无法描命题的优点是简单、明确；其主要缺点是无法描述客观事物的结构及其逻辑特征，也无法表示不同述客观事物的结构及其逻辑特征，也无法表示不同事物间的共性。事物间的共性。一一. . 谓词逻辑表示法的逻辑基础谓词逻辑表示法的逻辑基础592 2论域和谓词论域和谓词 论域论域是由所讨论对象之全体构成的非

57、空集合。论域中的元素是由所讨论对象之全体构成的非空集合。论域中的元素称为称为个体个体，论域也常称为，论域也常称为个体域个体域。例如，整数的个体域是由所有整。例如，整数的个体域是由所有整数构成的集合，每个整数都是该个体域中的一个个体。数构成的集合，每个整数都是该个体域中的一个个体。 在谓词逻辑中，命题是用在谓词逻辑中，命题是用谓词谓词来表示的。来表示的。一个谓词可分为谓词一个谓词可分为谓词名和个体两部分名和个体两部分。其中，个体是命题中的主语，用来表示某个独立。其中，个体是命题中的主语，用来表示某个独立存在的事物或者某个抽象的概念；谓词名是命题的谓语，用来表示存在的事物或者某个抽象的概念；谓词名

58、是命题的谓语，用来表示个体的性质、状态或个体之间的关系等。例如，对于命题个体的性质、状态或个体之间的关系等。例如，对于命题“王宏是王宏是学生学生”可用谓词表示为可用谓词表示为STUDENTSTUDENT（WanghongWanghong）。其中，其中，WanghongWanghong是个体，代表王宏；是个体，代表王宏；STUDENTSTUDENT是谓词名，说明王宏是学生是谓词名，说明王宏是学生的这一特征。通常，谓词名用大写英文字母表示，个体用小写英文的这一特征。通常，谓词名用大写英文字母表示，个体用小写英文字母表示。字母表示。一一. . 谓词逻辑表示法的逻辑基础谓词逻辑表示法的逻辑基础60谓词

59、谓词可形式地定义如下：可形式地定义如下： 定义：定义：设设 D D是个体域，是个体域，P P：D Dn nT T，F F是一是一个映射，其中个映射，其中 D Dn n =(x =(x1 1,x,x2 2, ,x,xn n)|x)|x1 1,x,x2 2, ,x,xn nDD则 称则 称 P P 是 一 个是 一 个 n n 元元 谓 词谓 词 （ n = 1 , 2 ,n = 1 , 2 , ） , , 记 为记 为P(xP(x1 1,x,x2 2, ,x,xn n) )。其中其中, ,x x1 1,x,x2 2, ,x,xn n 为个体变元。为个体变元。 在谓词中，个体可以是常量、变元或函数

60、。在谓词中，个体可以是常量、变元或函数。 例如，例如，“x6x6”，可用谓词表示为可用谓词表示为GreaterGreater（x x，6 6）, ,其中其中x x是变元。再如，是变元。再如，“王宏的父亲是教师王宏的父亲是教师”可用谓词表示为可用谓词表示为TEACHERTEACHER（fatherfather（Wanghong)Wanghong)，其中其中 fatherfather（WanghongWanghong）是一个函数。是一个函数。一一. . 谓词逻辑表示法的逻辑基础谓词逻辑表示法的逻辑基础61函数函数可形式地定义如下：可形式地定义如下：定义：定义：设设 D D是个体域，是个体域，f f