第二章知识表示方法

1、中南大学 智能系统与智能软件研究所第二章 知识表示方法2.1 状态空间法2.2 问题归约法2.3 谓词逻辑法2.4 语义网络法2.5 框架表示法2.6 本体技术2.7 过程表示CSUCSUCSUCSUCSUCSUCSUCSUCSU每种以每种以知识知识和和符号操作符号操作为基础的智能系统，其为基础的智能系统，其问题求解方法一般需要对解答过程进行某种搜索。问题求解方法一般需要对解答过程进行某种搜索。不过，在搜索过程开始之前，必须先用某种方法或不过，在搜索过程开始之前，必须先用某种方法或某几种方法的混合来某几种方法的混合来表示问题表示问题。本章主要讨论知识表示的问题，介绍了本章主要讨论知识表示的问题

2、，介绍了7种知种知识表示方法：状态空间法、问题归约法、谓词演算识表示方法：状态空间法、问题归约法、谓词演算法、语义网络法、框架表示法、本体技术和过程表法、语义网络法、框架表示法、本体技术和过程表示法。其中要求掌握示法。其中要求掌握状态空间法、问题归约法、谓状态空间法、问题归约法、谓词演算法、语义网络法的要点及其之间的关系词演算法、语义网络法的要点及其之间的关系。CSUCSUCSUCSUCSUCSUCSUCSUCSU1.1.知识表示的基本概念知识表示的基本概念知识表示实际上就是对人类知识的一种描述，知识表示实际上就是对人类知识的一种描述，以以把人类知识表示成机器能够处理的数据结构。知识表把人类知

3、识表示成机器能够处理的数据结构。知识表示的过程就是把知识编码成某种数据结构的过程示的过程就是把知识编码成某种数据结构的过程。 2. 知识表示方法分类知识表示方法分类(1)(1)从作用范围来划分从作用范围来划分: :常识性、领域性常识性、领域性 (2)(2)从知识的作用及表示来划分：事实性、过程从知识的作用及表示来划分：事实性、过程性、控制性性、控制性 (3)(3)从知识的确定性来划分：确定性、不确定性从知识的确定性来划分：确定性、不确定性 (4)(4)从知识的结构及表现形式来划分：逻辑性、从知识的结构及表现形式来划分：逻辑性、形象性形象性CSUCSUCSUCSUCSUCSUCSUCSUCSU2

4、.1 状态空间法问题求解涉及归约、推断、决策、规划、常识推理、定问题求解涉及归约、推断、决策、规划、常识推理、定理证明等相关的过程。现实世界中理证明等相关的过程。现实世界中问题求解过程问题求解过程可以可以看做是看做是一个一个搜索搜索或者或者推理推理过程。过程。 推理过程实际上也是一个搜索过程推理过程实际上也是一个搜索过程，它在知识库中搜索，它在知识库中搜索和前提条件相匹配的规则，而后利用这些规则进行推理。所和前提条件相匹配的规则，而后利用这些规则进行推理。所以，以，任何问题求解的本质都是一个搜索过程任何问题求解的本质都是一个搜索过程，并且发现许多，并且发现许多问题求解方法常常采用问题求解方法常

5、常采用试探式搜索方法试探式搜索方法。也就是说，这些方。也就是说，这些方法是通过在某个可能的解空间内搜寻一个解来求解问题。这法是通过在某个可能的解空间内搜寻一个解来求解问题。这种种基于解答空间的问题表示和求解方法就是状态空间法基于解答空间的问题表示和求解方法就是状态空间法，它，它是是以状态和算符为基础来表示和求解问题以状态和算符为基础来表示和求解问题的。的。CSUCSUCSUCSUCSUCSUCSUCSUCSU状态状态(state)(state)：表示问题解法过程中每：表示问题解法过程中每一步问题状况的数据结构；一步问题状况的数据结构； 举例：天气、身体指标、棋局对弈等举例：天气、身体指标、棋局

6、对弈等算符算符(operator)(operator)：把问题从一种状态变：把问题从一种状态变换为另一种状态的手段或操作；换为另一种状态的手段或操作；CSUCSUCSUCSUCSUCSUCSUCSUCSU例例1 1 农夫、狐狸、鸡、小米在一条河的左岸，现在要农夫、狐狸、鸡、小米在一条河的左岸，现在要把它们全部送到右岸去。农夫有一条船，过河时，除把它们全部送到右岸去。农夫有一条船，过河时，除农夫外，船上至多能载狐狸、鸡和小米中的一样，且农夫外，船上至多能载狐狸、鸡和小米中的一样，且狐狸要吃鸡，鸡要吃小米，除非农夫在。试用状态表狐狸要吃鸡，鸡要吃小米，除非农夫在。试用状态表示法规划出一个确保全部对

7、象安全过河的计划。示法规划出一个确保全部对象安全过河的计划。提示：提示：用四元向量用四元向量(农夫、狐狸、鸡、小米农夫、狐狸、鸡、小米)表示状态表示状态，每个每个分量取分量取0或或1，1表示船在左岸，表示船在左岸，0在右岸；在右岸； 把每次过河的一种具体安排作为一个算符，例如把每次过河的一种具体安排作为一个算符，例如可用可用L(f，j)表示从左岸将第表示从左岸将第j样东西送到右岸样东西送到右岸(j1是狐是狐狸，狸，j2是鸡，是鸡，j3是小米，是小米，j0表示除农夫外不载任表示除农夫外不载任何东西何东西)，f表示农夫始终在船上。表示农夫始终在船上。R(f，j)表示从右岸表示从右岸将第将第j样东西

8、送到左岸样东西送到左岸。CSUCSUCSUCSUCSUCSUCSUCSUCSU(1,1,1,1)(1,1,1,1)(0,1,0,1)(0,1,0,1)L(f,2)L(f,2)R(f,2)R(f,2)(1,1,0,1)(1,1,0,1)R(f,0)R(f,0)L(f,0)L(f,0)L(f,3)L(f,3)L(f,1)L(f,1)(0,0,0,1)(0,0,0,1)(0,1,0,0)(0,1,0,0)R(f,2)R(f,2)L(f,2)L(f,2)L(f,2)L(f,2)R(f,2)R(f,2)(1,1,1,0)(1,1,1,0)(1,0,1,1)(1,0,1,1)（农夫、狐狸、鸡、小米）过河问

9、题（农夫、狐狸、鸡、小米）过河问题L(f,1)L(f,1)L(f,3)L(f,3)(0,0,1,0)(0,0,1,0)R(f,0)R(f,0)L(f,0)L(f,0)(1,0,1,0)(1,0,1,0)(0,0,0,0)(0,0,0,0)L(f,2)L(f,2)R(f,2)R(f,2)CSUCSUCSUCSUCSUCSUCSUCSUCSU2.1.1 问题状态描述1.形式化形式化定义定义状态状态(state)：为描述某类不同事物间差别而引入的一组：为描述某类不同事物间差别而引入的一组最少最少变变量量 q0, q1, , qn 的的有序集合，其矢量形式为：有序集合，其矢量形式为：Q=q0, q1,

10、 , qnT 式中每个元素式中每个元素qi (i=0,1，n)为集合的分量，称为为集合的分量，称为状态变量状态变量。算符算符：使问题从一种状态变化为另一种状态的手段称为操作：使问题从一种状态变化为另一种状态的手段称为操作符或算符。操作符可为符或算符。操作符可为走步走步、过程过程、规则规则、数学算子数学算子、运算符号运算符号或或逻辑符号逻辑符号等。等。问题的状态空间问题的状态空间：是一个表示某问题全部可能状态及其关系：是一个表示某问题全部可能状态及其关系的的图图，状态空间记为三元结构，状态空间记为三元结构(S，F，G)，即，即初始状态集合初始状态集合S、操操作算符集合作算符集合F以及以及目标状态

11、集合目标状态集合G。CSUCSUCSUCSUCSUCSUCSUCSUCSU2.状态空间表示法详释状态空间表示法详释我们先用我们先用数码难题数码难题(puzzle problem)来说明状态空间表示的来说明状态空间表示的概念。由概念。由15个编有个编有1至至15并放在并放在44方格棋盘上的可走动的棋子方格棋盘上的可走动的棋子组成。棋盘上总有一格是空的，以便可能让空格周围的棋子走进组成。棋盘上总有一格是空的，以便可能让空格周围的棋子走进空格，这也可以理解为移动空格。图中绘出了两种棋局，即空格，这也可以理解为移动空格。图中绘出了两种棋局，即初始初始棋局和目标棋局棋局和目标棋局（书本（书本29页图页图

12、2.1），它们对应于该下棋问题的），它们对应于该下棋问题的初始状态初始状态和和目标状态目标状态。如何把初始棋局变换为目标棋局呢？问题的解答就是某个合如何把初始棋局变换为目标棋局呢？问题的解答就是某个合适的棋子走步序列，如适的棋子走步序列，如“左移棋子左移棋子12，下移棋子，下移棋子15，右移棋子，右移棋子4，”等等。等等。1515数码难题数码难题最直接的求解方法是尝试各种不同走步最直接的求解方法是尝试各种不同走步，直到偶，直到偶然得到目标棋局为止，这种尝试然得到目标棋局为止，这种尝试本质上是本质上是一种试探性的搜索一种试探性的搜索。 CSUCSUCSUCSUCSUCSUCSUCSUCSU从初始

13、棋局开始，试探由每一合法走步得到的各种新棋局，从初始棋局开始，试探由每一合法走步得到的各种新棋局，然后计算再走一步而得到的下一组棋局。这样继续下去，直至达然后计算再走一步而得到的下一组棋局。这样继续下去，直至达到目标棋局为止。到目标棋局为止。把初始状态可达到的各状态所组成的空间设想把初始状态可达到的各状态所组成的空间设想为一幅由各种状态对应的节点组成的图，为一幅由各种状态对应的节点组成的图，这种图称为这种图称为状态图。状态图。图图中中每个节点标有它所代表的棋局每个节点标有它所代表的棋局。首先把适用的算符用于初始状。首先把适用的算符用于初始状态，产生新的状态；然后，再把另一些适用算符用于这些新的

14、状态，产生新的状态；然后，再把另一些适用算符用于这些新的状态；这样继续下去，直至产生目标状态为止。（态；这样继续下去，直至产生目标状态为止。（29页图页图2.2） CSUCSUCSUCSUCSUCSUCSUCSUCSU我们用我们用状态空间法状态空间法表示下述过程：表示下述过程：首先将适用的首先将适用的算符算符作用于初始状态作用于初始状态，产生中间状态，再选择适用的，产生中间状态，再选择适用的算符算符作用于当前状态；递增地作用于当前状态；递增地建立起算符试验序列，建立起算符试验序列，直到达到目标状态为止直到达到目标状态为止。某个问题的状态描述，须经历如下某个问题的状态描述，须经历如下3个步骤个步

15、骤： （1）定义）定义状态的描述方式状态的描述方式； （2）用所定义的状态描述形式把问题的所有可能）用所定义的状态描述形式把问题的所有可能状态表示出来，关键是状态表示出来，关键是确定问题的初始状态确定问题的初始状态描述描述集合集合和和目标状态目标状态描述描述集合集合； （3 3）定义）定义一组算符一组算符，利用这组算符可把问题由一，利用这组算符可把问题由一种状态转变为另一种状态。种状态转变为另一种状态。CSUCSUCSUCSUCSUCSUCSUCSUCSU需要说明的是：需要说明的是： 可能存在可能存在多个算符序列多个算符序列都可使问题达到目标状都可使问题达到目标状态，这就得到态，这就得到多个解

16、多个解。其中，有的所使用算符较少，。其中，有的所使用算符较少，有的则较多，把有的则较多，把使用算符最少的解使用算符最少的解称为称为最优解最优解。 对任何一个状态，可对任何一个状态，可适用算符可能不止一个适用算符可能不止一个，这样由一个状态所这样由一个状态所生成的后继状态可能有多个生成的后继状态可能有多个，首先，首先使用哪一个适用的算符呢？这属于使用哪一个适用的算符呢？这属于搜索策略搜索策略问题（问题（搜搜索算法索算法），不同搜索策略其算符操作的顺序可能不相），不同搜索策略其算符操作的顺序可能不相同，这就可能导致多组不同的解。同，这就可能导致多组不同的解。CSUCSUCSUCSUCSUCSUCS

17、UCSUCSU2.1.2 状态图示法对于下棋问题曾用状态图来描述状态空间，这里介绍一下图对于下棋问题曾用状态图来描述状态空间，这里介绍一下图论中的几个术语和图的正式表示法。论中的几个术语和图的正式表示法。1. 图论中的几个术语图论中的几个术语 节点节点(node)：图形上的汇合点，用来表示状态、事件和时：图形上的汇合点，用来表示状态、事件和时间关系的汇合，如下棋中的每一步棋局；间关系的汇合，如下棋中的每一步棋局； 弧线弧线(arc)：节点间的连接线，代表算符；：节点间的连接线，代表算符； 有向图有向图(directed graph)：一对节点用弧线连接起来，从一：一对节点用弧线连接起来，从一个

18、节点指向另一个节点，反映了状态的变更情况；个节点指向另一个节点，反映了状态的变更情况； 后继节点后继节点(descendant node)与与父辈节点父辈节点(parent node)：如果：如果某条弧线从节点某条弧线从节点 ni 指向节点指向节点 nj ，那么节点，那么节点 nj 就叫做节点就叫做节点 ni 的后的后继节点或后裔，而节点继节点或后裔，而节点 ni 叫做节点叫做节点 nj 的父辈节点或祖先；的父辈节点或祖先；CSUCSUCSUCSUCSUCSUCSUCSUCSU 路径路径：某个节点序列：某个节点序列 (ni1, ni2, , nik ) ，当，当j=2，3，k时，如果对于每一个

19、时，如果对于每一个ni, j-1都有一个后继节点都有一个后继节点nij存在，那么就把存在，那么就把这个节点序列叫做从节点这个节点序列叫做从节点ni1至节点至节点nik的长度为的长度为k的路径。的路径。 代价代价：用：用c(ni, nj) 来表示从节点来表示从节点ni指向指向nj的弧线的代价。的弧线的代价。两节点间路径代价等于连接该路径上各节点所有弧线代价之和。两节点间路径代价等于连接该路径上各节点所有弧线代价之和。 显式表示显式表示：各状态节点及其具有代价的弧线由一张表明：各状态节点及其具有代价的弧线由一张表明确给出。此表可能列出该图中的每一节点、它的后继节点以及确给出。此表可能列出该图中的每

20、一节点、它的后继节点以及连接弧线的代价。连接弧线的代价。 隐式表示隐式表示：节点的无限集合：节点的无限集合si作为作为起始节点是已知起始节点是已知。后后继节点算符继节点算符L也已知也已知，它作用于任一节点以产生该节点的全部，它作用于任一节点以产生该节点的全部后继节点和各连接弧线的代价。后继节点和各连接弧线的代价。CSUCSUCSUCSUCSUCSUCSUCSUCSU2.图的显式和隐式表示图的显式和隐式表示 图可以被显式说明或隐式说明，图可以被显式说明或隐式说明，显式表示对于大型的图显式表示对于大型的图不切实际的不切实际的，而对于有无限节点集合的图更是不可能。，而对于有无限节点集合的图更是不可能

21、。考虑引入后继节点算符的方法来隐式表示状态空间图。考虑引入后继节点算符的方法来隐式表示状态空间图。后继节点算符集后继节点算符集L也是已知的，也是已知的，把适用的后继算符应用于把适用的后继算符应用于si的成员和它们的后继节点以及这些后继节点的后继节点的成员和它们的后继节点以及这些后继节点的后继节点，如，如此无限制地进行下去，此无限制地进行下去，最后由最后由L和和si所规定的隐式图变为显所规定的隐式图变为显示图示图。把后继算符作用于节点的过程，实际上就是扩展该节。把后继算符作用于节点的过程，实际上就是扩展该节点的过程。因此，通过搜索状态空间以求得算符序列的解答点的过程。因此，通过搜索状态空间以求得

22、算符序列的解答过程，就是使隐式图变为显式并包含目标的过程。过程，就是使隐式图变为显式并包含目标的过程。 CSUCSUCSUCSUCSUCSUCSUCSUCSU问题的表示对求解工作量有很大的影响。人们显然希望问题的表示对求解工作量有很大的影响。人们显然希望用用较小的状态空间表示较小的状态空间表示。许多似乎很难的问题，当表示适当时就。许多似乎很难的问题，当表示适当时就可能具有小而简单的状态空间。如对十五数码难题的初始状态可能具有小而简单的状态空间。如对十五数码难题的初始状态表示，可规定表示，可规定15460条算符，即左移棋子条算符，即左移棋子1，右移棋子，右移棋子1，上移棋子上移棋子1，下移棋子，

23、下移棋子1，左移棋子，左移棋子2，下移棋子，下移棋子15，但我们，但我们很快就会发现，只要左右上下移动空格，那么就可用很快就会发现，只要左右上下移动空格，那么就可用4条算符条算符代替上述代替上述60条算符。可见，移动空格是一种较好的表示。因条算符。可见，移动空格是一种较好的表示。因此，此，对于同一问题，表示方法可能有多种。对于同一问题，表示方法可能有多种。在求解问题时在求解问题时, ,首首先应考虑如何表示问题，之后再改进表示方法先应考虑如何表示问题，之后再改进表示方法。 2.1.3 状态空间表示举例 下面介绍另一个状态空间表示的例子下面介绍另一个状态空间表示的例子CSUCSUCSUCSUCSU

24、CSUCSUCSUCSU例例2猴子和香蕉问题猴子和香蕉问题( monkey and banana problem )在一个房间内有一只猴子在一个房间内有一只猴子(可把这只猴子看做一个机器人可把这只猴子看做一个机器人)、一个箱子和一束香蕉。香蕉挂在天花板下方，但猴子的高度不足一个箱子和一束香蕉。香蕉挂在天花板下方，但猴子的高度不足以碰到它。那么这只猴子怎样才能摘到香蕉呢？图以碰到它。那么这只猴子怎样才能摘到香蕉呢？图2.4表示出猴表示出猴子、香蕉和箱子在房间内的相对位置。子、香蕉和箱子在房间内的相对位置。 用一个四元表列用一个四元表列(W, x, Y, z)来表示这个问题的状态，来表示这个问题的

25、状态，W猴子的水平位置猴子的水平位置x当猴子在箱子顶上时取当猴子在箱子顶上时取x=1；否则取；否则取x=0Y箱子的水平位置箱子的水平位置 z当猴子摘到香蕉时取当猴子摘到香蕉时取z=1；否则取；否则取z=0CSUCSUCSUCSUCSUCSUCSUCSUCSU这个问题中的这个问题中的操作操作(算符算符)用产生式规则表示用产生式规则表示如下：如下：(1) goto(U)：表示猴子走到水平位置：表示猴子走到水平位置U，用产生式，用产生式规则表示为规则表示为（W，0，Y，z） （U，0，Y，z）(2) pushbox(V)：表示猴子把箱子推到了水平位置：表示猴子把箱子推到了水平位置V，即有，即有（W，

26、0，W，z） （V，0，V，z）注意：要应用算符注意：要应用算符pushbox(V)，就要求产生式规则，就要求产生式规则的左边，猴子与箱子必须在同一位置上，且猴子不在箱的左边，猴子与箱子必须在同一位置上，且猴子不在箱子顶上子顶上，即，即x=0=0。这种强加于操作的适用性条件，叫做。这种强加于操作的适用性条件，叫做产生式规则的先决条件产生式规则的先决条件。CSUCSUCSUCSUCSUCSUCSUCSUCSU (3) climbbox：猴子爬上箱顶，即有：猴子爬上箱顶，即有（W，0，W，z） （W，1，W，z）在应用算符在应用算符climbbox时也必须注意到，猴子和箱子时也必须注意到，猴子和箱

27、子应当在同一位置上，而且猴子不在箱顶上，即应当在同一位置上，而且猴子不在箱顶上，即x=0。(4) grasp：猴子摘到香蕉，即有：猴子摘到香蕉，即有（c，1，c，0） （c，1，c，1）其中，其中，c是香蕉正下方的地板位置，在应用算符是香蕉正下方的地板位置，在应用算符grasp时，要求猴子和箱子都在位置时，要求猴子和箱子都在位置c上，并且猴子已在上，并且猴子已在箱子顶上，即箱子顶上，即x=1。 CSUCSUCSUCSUCSUCSUCSUCSUCSU本问题中，令初始状态为本问题中，令初始状态为(a, 0, b, 0)。这时，。这时，goto(U)是唯一是唯一适用的操作，并导致下一状态适用的操作，

28、并导致下一状态(U, 0, b, 0)，把所有适用的操作继，把所有适用的操作继续应用于每个状态，直至任何最后一列元素为续应用于每个状态，直至任何最后一列元素为1的目标状态表列的目标状态表列出现，我们就能够得到状态空间图出现，我们就能够得到状态空间图。goto(b)，pushbox(c)，climbbox，grasp 目标状态目标状态V=c，climbbox(b，1，b，0)（U，0，b，0）（V，0，V，0）（c，1，c，0）（U，0，V，0）（c，1，c，1）（a，0，b，0）goto（U）goto（U）U=b，climbboxgoto（U）U=bpushbox（V）goto（U）U=Vgr

29、aspCSUCSUCSUCSUCSUCSUCSUCSUCSU2.2 问题归约法问题归约是一种问题表示与求解方法问题归约是一种问题表示与求解方法。已知原始问题的描已知原始问题的描述，通过一系列变换把原问题变为一个子问题的集合，集合里述，通过一系列变换把原问题变为一个子问题的集合，集合里的每个子问题被进一步简化为子子问题，最终的这些子问题的每个子问题被进一步简化为子子问题，最终的这些子问题的解答可以直接得到，从而得到原始问题的解答。的解答可以直接得到，从而得到原始问题的解答。本原问题本原问题其解答可其解答可通过一步通过一步（运算、走步、操作等）而（运算、走步、操作等）而直接得到的子问题。直接得到的

30、子问题。CSUCSUCSUCSUCSUCSUCSUCSUCSU2.2.1 问题归约描述示例：梵塔难题（河内塔、汉诺塔，起源于古印度）示例：梵塔难题（河内塔、汉诺塔，起源于古印度）最初，由大到小的最初，由大到小的3 3个圆盘自下而上都堆在柱子个圆盘自下而上都堆在柱子1 1上，要上，要求把所有圆盘都移到柱子求把所有圆盘都移到柱子3 3上。上。要求：要求：(1) (1) 一次只能移一个盘子；一次只能移一个盘子；(2) (2) 盘子只许在三根柱子上存放；盘子只许在三根柱子上存放； (3) (3) 永远不许有大盘压着小盘。永远不许有大盘压着小盘。 CSUCSUCSUCSUCSUCSUCSUCSUCSU分

31、析过程：分析过程：1、要把所有圆盘移至柱子、要把所有圆盘移至柱子3，必须先把最大的圆盘，必须先把最大的圆盘C移至柱子移至柱子3；而且在移动圆盘；而且在移动圆盘C至柱子至柱子3之前，要求柱之前，要求柱子子3必须是空的。必须是空的。2、只有在移开圆盘、只有在移开圆盘A和和B之后，才能移动圆盘之后，才能移动圆盘C；且圆；且圆盘盘A和和B最好不要移至柱子最好不要移至柱子3，否则会出现大盘压着小，否则会出现大盘压着小盘，就不能把圆盘盘，就不能把圆盘C移至柱子移至柱子3。因此，首先应该把圆。因此，首先应该把圆盘盘A和和B从柱子从柱子1移到柱子移到柱子2上；上；3、然后才能、然后才能进行关键的一步进行关键的

32、一步，把圆盘，把圆盘C从柱子从柱子1移至移至柱子柱子3，并继续解决问题的余下部分，把圆盘，并继续解决问题的余下部分，把圆盘A和和B从从柱子柱子2移至柱子移至柱子3。CSUCSUCSUCSUCSUCSUCSUCSUCSU归约过程：归约过程：上述讨论使得原始问题归约（简化）为下上述讨论使得原始问题归约（简化）为下列列3 3个子问题：个子问题： （1）移动圆盘）移动圆盘A和和B从柱子从柱子1至柱子至柱子2的的双圆双圆盘问题盘问题；CSUCSUCSUCSUCSUCSUCSUCSUCSU（2）移动圆盘）移动圆盘C从柱子从柱子1至柱子至柱子3的单圆盘问题；的单圆盘问题；（3）移动圆盘）移动圆盘A和和B从柱

33、子从柱子2至柱子至柱子3的双圆盘问题。的双圆盘问题。CSUCSUCSUCSUCSUCSUCSUCSUCSU可以看出，分解后的子问题都比原始问题要简单。其可以看出，分解后的子问题都比原始问题要简单。其中子问中子问题题2 2可作为本原问题可作为本原问题考虑，因为它的求解只包含一步移动操作。考虑，因为它的求解只包含一步移动操作。应用一系列相似的推理，应用一系列相似的推理，子问题子问题1 1和和子问题子问题3 3也也可进一步被归约为可进一步被归约为本原问题本原问题。下面给出梵塔问题的。下面给出梵塔问题的归约过程图归约过程图（也称做（也称做与或图与或图）。）。思考：思考：1 1圆盘问题要走几步？圆盘问题

34、要走几步？2 2圆盘问题要走几步？圆盘问题要走几步？3 3个，个，4 4个，个， ,64 ,64个呢？个呢？CSUCSUCSUCSUCSUCSUCSUCSUCSU解题过程（解题过程（3 3个圆盘问题）个圆盘问题）按照前面的归约过程图可以给出详细的解题过程图。按照前面的归约过程图可以给出详细的解题过程图。123123123123123123123123CSUCSUCSUCSUCSUCSUCSUCSUCSU问题归约法的实质：问题归约法的实质：从目标从目标（要解决的问题要解决的问题）出发逆向推理，原问题分解为若干出发逆向推理，原问题分解为若干个子问题以及子子问题，直至最后把初始问题归约（简化）为个子

35、问题以及子子问题，直至最后把初始问题归约（简化）为一个平凡的本原问题集合。一个平凡的本原问题集合。问题归约表示法可由下面三部分组成：问题归约表示法可由下面三部分组成： 一个初始问题描述一个初始问题描述（可用表列、数组、树、字符串等形式）（可用表列、数组、树、字符串等形式） 一套把问题变换为子问题的操作符一套把问题变换为子问题的操作符（通过一系列操作将原问题（通过一系列操作将原问题变换为等价问题）变换为等价问题） 一套本原问题描述一套本原问题描述（本原子问题的解答可直接由一步得到）（本原子问题的解答可直接由一步得到）CSUCSUCSUCSUCSUCSUCSUCSUCSU问题归约方法可以应用状态、

36、算符和目标这些问题归约方法可以应用状态、算符和目标这些表示法来描述问题，这表示法来描述问题，这并不意味着问题归约法和状并不意味着问题归约法和状态空间法是一样态空间法是一样的。的。 把一个初始问题描述变换为一个归约或后继问把一个初始问题描述变换为一个归约或后继问题描述的集合，题描述的集合，由问题归约算符进行由问题归约算符进行，变换所得所，变换所得所有后继问题的解就是父辈问题的一个解。有后继问题的解就是父辈问题的一个解。 所所有问题归约的目的是产生具有明显解答的本有问题归约的目的是产生具有明显解答的本原子问题原子问题。本原子问题可由解答空间搜索走动一步。本原子问题可由解答空间搜索走动一步解决或能直

37、接得到解答。解决或能直接得到解答。 CSUCSUCSUCSUCSUCSUCSUCSUCSU2.2.2 与或图表示1.与或图的概念与或图的概念一般，我们用一个类似图的结构来表示把问题归约为后继一般，我们用一个类似图的结构来表示把问题归约为后继问题的替换集合，这种结构图叫做问题的替换集合，这种结构图叫做问题归约图问题归约图，或叫，或叫与或图与或图。如下图所示：如下图所示： ABCD与图ABC或图CSUCSUCSUCSUCSUCSUCSUCSUCSUBCDEFGAHMBCDEFGANCSUCSUCSUCSUCSUCSUCSUCSUCSU2.一些关于一些关于与或图的术语与或图的术语介绍一些术语：介绍一

38、些术语：父节点父节点、子子( (后继后继) )节点节点、弧线弧线、起始节点起始节点。终叶节点终叶节点：对应于本原问题的节点。：对应于本原问题的节点。或节点或节点：只要解决该问题就可解决其父辈问题的节点集合，如：只要解决该问题就可解决其父辈问题的节点集合，如( (M，N，H) )。与节点与节点：只有解决所有子问题，才能解决其父辈问题的节点集：只有解决所有子问题，才能解决其父辈问题的节点集合，如合，如( (B，C)和和( (D，E，F)各结点之间用一段小圆弧连接标记。各结点之间用一段小圆弧连接标记。HMBCDEFGAN父节点与节点弧线或节点子节点终叶节点CSUCSUCSUCSUCSUCSUCSUC

39、SUCSU 与或图中与或图中可解节点可解节点的一般定义：的一般定义： (1) 终叶节点是可解节点终叶节点是可解节点（因为它们（因为它们与本原问题相关连与本原问题相关连）。）。 (2) 如果某个如果某个非终叶节点含有或后继节点非终叶节点含有或后继节点，那么只要当其后继，那么只要当其后继节点至少有一个是可解的时，此非终叶节点才是可解的。节点至少有一个是可解的时，此非终叶节点才是可解的。 (3) 如果某个如果某个非终叶节点含有与后继节点非终叶节点含有与后继节点，那么只有当其后继，那么只有当其后继节点全部为可解时，此非终叶节点才是可解的。节点全部为可解时，此非终叶节点才是可解的。 终叶节点用字母终叶节

40、点用字母t表示表示（对应于本原问题），（对应于本原问题），有解节点用小圆有解节点用小圆点表示，不可解节点用小圆圈表示点表示，不可解节点用小圆圈表示。 相应地可给出相应地可给出不可解节点不可解节点的一般定义：的一般定义： (1) 完全没有后继节点的非终叶节点为不可解节点。完全没有后继节点的非终叶节点为不可解节点。 (2) 如果某个非终叶节点含有或后继节点，那么只有当其全部如果某个非终叶节点含有或后继节点，那么只有当其全部后裔为不可解时，此非终叶节点才是不可解的。后裔为不可解时，此非终叶节点才是不可解的。 (3) 如果某个非终叶节点含有与后继节点，那么只要当其后裔如果某个非终叶节点含有与后继节点，

41、那么只要当其后裔至少有一个为不可解时，此非终叶节点才是不可解的。至少有一个为不可解时，此非终叶节点才是不可解的。 CSUCSUCSUCSUCSUCSUCSUCSUCSUt有解节点终叶节点与或图例子与或图例子无解节点tttttttt（a）（c）CSUCSUCSUCSUCSUCSUCSUCSUCSU 综合前面所述，下面给出与或图的构成规则：综合前面所述，下面给出与或图的构成规则： (1) 与或图中的每个节点代表一个要解决的单一问题或问题与或图中的每个节点代表一个要解决的单一问题或问题集合。图中所含集合。图中所含起始节点对应于原始问题起始节点对应于原始问题。 (2) 对应于本原问题的节点，叫做终叶节

42、点，它没有后裔对应于本原问题的节点，叫做终叶节点，它没有后裔。 (3) 有向弧线自问题有向弧线自问题A指向后继节点表示所求得的子问题集合：指向后继节点表示所求得的子问题集合：N，M和和H。子问题集合子问题集合：N，M和和H中任何一个有解答，问题中任何一个有解答，问题A就可解答就可解答。所以。所以N，M和和H叫做叫做或节点或节点。 (4) 一般对于代表一般对于代表有两个或两个以上子问题集合的每个非终有两个或两个以上子问题集合的每个非终叶节点叶节点，有向弧线从此节点指向此子问题集合中的各个节点。由，有向弧线从此节点指向此子问题集合中的各个节点。由于只有当于只有当该集合中所有的项都有解时该集合中所有

43、的项都有解时，这，这个子问题的集合才能获个子问题的集合才能获得解答得解答，所以这些子问题节点叫做，所以这些子问题节点叫做与节点与节点。 (5) 在特殊情况下，当只有一个算符可应用于问题在特殊情况下，当只有一个算符可应用于问题A，而且这，而且这个算符产生具有一个以上子问题的某个集合时，由上述规则个算符产生具有一个以上子问题的某个集合时，由上述规则3和和规则规则4所产生的图可以得到简化。因此，代表子问题集合的中间所产生的图可以得到简化。因此，代表子问题集合的中间或节点可以被略去。或节点可以被略去。 除起始节点外，每个节点有且只有一个父辈节点。除起始节点外，每个节点有且只有一个父辈节点。CSUCSU

44、CSUCSUCSUCSUCSUCSUCSU2.3 谓词逻辑法谓词演算能够表达命题逻辑所不能表达的复杂问题。更具谓词演算能够表达命题逻辑所不能表达的复杂问题。更具体地说，一阶谓词逻辑法具有：体地说，一阶谓词逻辑法具有：自然性自然性、精确性精确性、有限性有限性和和易易实现实现的特点，适宜于精确知识表示和相应的逻辑推理。的特点，适宜于精确知识表示和相应的逻辑推理。2.3.1 谓词演算1.语法和语义语法和语义(Syntax & Semantics)基本符号基本符号：谓词符号、变量符号、函数符号、常量符号、：谓词符号、变量符号、函数符号、常量符号、括号和逗号。括号和逗号。 常量符号常量符号：用来

45、表示论域内的物体或实体，可以是具体的，：用来表示论域内的物体或实体，可以是具体的，也可以是抽象的。也可以是抽象的。变量符号变量符号：表示不明确涉及哪一个个体。：表示不明确涉及哪一个个体。函数符号函数符号：表示某个体与其他个体之间的：表示某个体与其他个体之间的映射关系映射关系。 谓词符号谓词符号：用于刻画个体的性质、状态或个体间的：用于刻画个体的性质、状态或个体间的非映射非映射关系关系，谓词的语义是由使用者根据需要人为地定义，当谓词的，谓词的语义是由使用者根据需要人为地定义，当谓词的变量用特定个体取代时，谓词就具有一确定的逻辑真值变量用特定个体取代时，谓词就具有一确定的逻辑真值T或或F。 CSU

46、CSUCSUCSUCSUCSUCSUCSUCSU原子公式原子公式：由单个谓词符号和项（个体常量、变量、函数）：由单个谓词符号和项（个体常量、变量、函数）构成的公式。原子公式是谓词演算基本积木块。构成的公式。原子公式是谓词演算基本积木块。例如，要表示例如，要表示“机器人（机器人（ROBOT）在号房间（）在号房间（r1）内）内”，如下图所示，可以应用原子公式：如下图所示，可以应用原子公式： 当机器人（当机器人（ROBOT）移到房间移到房间r2时，原子公式可以表示为：时，原子公式可以表示为：INROOM (ROBOT，r2) 这两个原子公式的通用形式就是：这两个原子公式的通用形式就是： CSUCSU

47、CSUCSUCSUCSUCSUCSUCSU2.连词和量词连词和量词(Connective & Quantifiers)(1) 连词连词与与合取合取（conjunction）：合取就是用连词）：合取就是用连词把几个谓词公把几个谓词公式连接起来而构成的公式，式连接起来而构成的公式，合取项是合取式的每个组成部分合取项是合取式的每个组成部分。 例：例：LIKE( I，MUSIC )LIKE( I，PAINTING ) 或或析取析取（disjunction）：析取就是用连词）：析取就是用连词把几个谓词公式把几个谓词公式连接起来而构成的公式，连接起来而构成的公式，析取项是析取式的每个组成部分析取项

48、是析取式的每个组成部分。 例：例：PLAYS( LIULI，BASKETBALL )PLAYS( LIULI，FOOTBALL )又如又如，“李的母亲和他的父李的母亲和他的父亲结婚亲结婚”这句话的原子公式为：这句话的原子公式为：这里使用了两个函数关系。这里使用了两个函数关系。CSUCSUCSUCSUCSUCSUCSUCSUCSU蕴涵蕴涵（Implication）：蕴涵）：蕴涵“”表示表示“如果如果-那么那么”的语句。的语句。用连词用连词连接两个公式所构成的公式叫做蕴涵。连接两个公式所构成的公式叫做蕴涵。IFA THEN B 前项前项（左部左部） 后项后项（右部右部） 例：例：RUNS( LIU

49、HUA，FASTEST ) WINS( LIUHUA，CHAMPION ) 非（非（NOT）：表示否定，、：表示否定，、均可表示。均可表示。 例：例：INROOM( ROBOT，r2 )（机器人不在（机器人不在2号房间内。）号房间内。） (2) 量量词词全称量词全称量词(Universal Quantifier)：若一个原子公式：若一个原子公式P(x)，对，对于所有可能变量于所有可能变量x都具有都具有T值，则用值，则用( x)P(x)表示。表示。 例：例：( x)ROBOT(x) COLOR(x，GRAY) ( x)Student(x) Uniform(x，Color) CSUCSUCSUCS

50、UCSUCSUCSUCSUCSU存在量词存在量词(Existential Quantifier)：若一个原子公式：若一个原子公式P(x)，至，至少有一个变元少有一个变元x，可使得，可使得P(x)为为T值，则用值，则用( x)P(x)表示。表示。 例：例：( x)INROOM(x，r1)（1号房间内有个物体）号房间内有个物体）量化变元量化变元(Quantified Variables)：被全称或存在量词量化了：被全称或存在量词量化了的变元的变元x，也称，也称约束变量约束变量，没有被量化的变量称为，没有被量化的变量称为自由变量自由变量。 2.3.2 谓词公式1.谓词公式的定义谓词公式的定义原子谓词

51、公式原子谓词公式：用：用P(x1，x2，xn)表示一个表示一个n元谓词公式元谓词公式其中其中P为为n元谓词，元谓词，x1，x2，xn为客体变量或变元。通常把为客体变量或变元。通常把P(x1，x2，xn)叫做原子公式，或原子谓词公式。叫做原子公式，或原子谓词公式。 CSUCSUCSUCSUCSUCSUCSUCSUCSU合式谓词公式合式谓词公式：由连词、量词把原子公式组成：由连词、量词把原子公式组成复合谓词公式复合谓词公式合式公式合式公式(WFF，well-formed formulas)的递归定义的递归定义：(1) 原子谓词公式是合式公式。原子谓词公式是合式公式。(2) 若若A为合式公式，则为合

52、式公式，则A也是一个合式公式。也是一个合式公式。(3) 若若A和和B都是合式公式，则都是合式公式，则(AB)，(AB)，(AB), (AB)也都是合式公式。也都是合式公式。(4) 若若A是合式公式，是合式公式，x为为A中的自由变元，则中的自由变元，则( x)A，( x)A是合是合式公式。式公式。(5) 只有按上述规则只有按上述规则(1)至至(4)求得的那些公式，才是合式公式。求得的那些公式，才是合式公式。例题：对于所有的例题：对于所有的x，如果，如果x是整数，则是整数，则x为正的或者为负的。为正的或者为负的。设设I(x)表示表示“x是整数是整数”，P(x)表示表示“x是正数是正数”，N(x)表

53、示表示“x是是负数负数”( x) I(x) (P(x)N(x) CSUCSUCSUCSUCSUCSUCSUCSUCSU2. 合式公式的性质合式公式的性质如果如果P和和Q是两个合式公式，则由这两个合式公式所组成的是两个合式公式，则由这两个合式公式所组成的复合表达式可由下列真值表给出：复合表达式可由下列真值表给出： 等价等价（）：如果两个合式公式，无论如何解释，其真值表：如果两个合式公式，无论如何解释，其真值表都是相同的，那么我们就称此两合式公式是都是相同的，那么我们就称此两合式公式是等价或等值等价或等值的。的。应用上述真值表，能够确立下列应用上述真值表，能够确立下列等价关系等价关系：(1) 否定

54、之否定否定之否定(P)等价于等价于P (2) PQ等价于等价于PQ（该公式常用来消除逻辑蕴含符号）（该公式常用来消除逻辑蕴含符号） CSUCSUCSUCSUCSUCSUCSUCSUCSU(3) 狄狄摩根定律摩根定律(PQ)等价于等价于PQ (PQ)等价于等价于PQ(4) 分配律分配律P(QR)等价于等价于(PQ)(PR)P(QR)等价于等价于(PQ)(PR)(5) 交换律交换律PQ等价于等价于QP PQ等价于等价于QP(6) 结合律结合律(PQ)R等价于等价于P(QR)(PQ)R等价于等价于P(QR)(7) 逆否律逆否律PQ等价于等价于QPCSUCSUCSUCSUCSUCSUCSUCSUCSU

55、此外，由对量词的处理还可建立下列等价关系：此外，由对量词的处理还可建立下列等价关系：(8) ( x) P(x)等价于等价于( x)P(x) ( x) P(x)等价于等价于( x)P(x)(9) ( x)P(x)Q(x)等价于等价于( x)P(x)( x)Q(x) ( x)P(x)Q(x)等价于等价于( x)P(x)( x)Q(x)(10) ( x)P(x)等价于等价于( y)P(y)( x)P(x)等价于等价于( y)P(y)上述最后两个等价关系说明，上述最后两个等价关系说明，在一个量化表达式中出现的在一个量化表达式中出现的量化变量是一类虚元量化变量是一类虚元，它可以用任何一个不在表达式中出现

56、过，它可以用任何一个不在表达式中出现过的其它变量符号来代替。的其它变量符号来代替。 CSUCSUCSUCSUCSUCSUCSUCSUCSU下面举一个用谓词演算来表示的英文句子的实例：下面举一个用谓词演算来表示的英文句子的实例：For every set x，there is a set y，such that the cardinality of y is greater than the cardinality of x这个英文句子可用谓词演算表示为：这个英文句子可用谓词演算表示为：( x)SET(x) ( y)( u)( v)SET(y)CARD(x，u)CARD(y，v)G(v，u)用用

57、一阶谓词逻辑法表示知识的步骤一阶谓词逻辑法表示知识的步骤如下：如下：(a)定义定义谓词谓词及及个体个体，确定每个谓词和个体的确切含义；，确定每个谓词和个体的确切含义；(b)根据所要表达的事物或概念，为每个谓词中的根据所要表达的事物或概念，为每个谓词中的变元赋以变元赋以特定的值，并考虑量化情况特定的值，并考虑量化情况；(c)根据所要表达的知识的语义，用根据所要表达的知识的语义，用适当的连接符号将各个适当的连接符号将各个谓词连接起来谓词连接起来，形成谓词公式。，形成谓词公式。 CSUCSUCSUCSUCSUCSUCSUCSUCSU例：太原市的夏天既干燥又炎热例：太原市的夏天既干燥又炎热首先定义谓词

58、及个体：设首先定义谓词及个体：设STATE（x，y，z）表示）表示x市在市在y季季节气候处于节气候处于z状态。这是一个三元一阶谓词，涉及的个体有：太状态。这是一个三元一阶谓词，涉及的个体有：太原，夏天，干燥或炎热。将个体代入谓词有原，夏天，干燥或炎热。将个体代入谓词有STATE（太原，夏天，干燥）和（太原，夏天，干燥）和STATE（太原，夏天，炎热）（太原，夏天，炎热）最后根据语义用联结词将它们联结起来，得到最后根据语义用联结词将它们联结起来，得到STATE（太原，夏天，干燥）（太原，夏天，干燥）STATE（太原，夏天，炎热）（太原，夏天，炎热） 例：人人爱劳动；所有整数要么是偶数要么就是奇数

59、例：人人爱劳动；所有整数要么是偶数要么就是奇数首先定义谓词如下：首先定义谓词如下：MAN（x）：）：x是人；是人；LOVE（x，y）：）：x爱爱y； I（x）：）：x是整数；是整数； E（x）：）：x是偶数；是偶数； O（x）：）：x是奇数；是奇数；根据题意用适当的连接符联结起来，则有根据题意用适当的连接符联结起来，则有 （ x x）（）（MAN（x） LOVE（x，labour） （ x x）I（x）（E（x）O（x） CSUCSUCSUCSUCSUCSUCSUCSUCSU例例3：要想出国留学，必须通过外语考试：要想出国留学，必须通过外语考试(默认的论域为人默认的论域为人)定义谓词：设定义谓

60、词：设Want（x，y）表示）表示x想要想要y， Pass（x，y）表示）表示x通过通过y； 定义个体：定义个体：goabroad表示出国留学，表示出国留学，flanguage表示外语考试；表示外语考试； 将个体代入谓词，并按题意用适当的连接符联结起来，将个体代入谓词，并按题意用适当的连接符联结起来，（ x）Pass（x，flanguage）Want（x，goabroad）3. 一阶谓词逻辑表示的特点一阶谓词逻辑表示的特点(1)自然性自然性：接近于自然语言的形式，表示问题易于被人理解；：接近于自然语言的形式，表示问题易于被人理解；(2)精确性精确性：具有精确的逻辑真值，适宜于表示精确性知识；：具有精确的逻辑真