第二章 知识表示与推理

1、第二部分 知识表示方法问题求解(Problem solving)涉及许多研究领域，但知识表示是其三大基本功能之一。本章主要讨论几中基本的知识表示方法技术，如状态空间表示法、问题归约法、谓词逻辑法、语义网络法等方法。2-1状态(state)空间表示法一.2-1-1 问题Q的状态描述(S, F, G)目标状态集合操作算子集合初始状态集合 State:为描述某类不同事物间差异而引入的一组变量之有序集合。即,其中，表示状态分量或状态变量。表示Q的每一元素都赋予一个值之后的某种状态。(1) 操作符/算符：是问题从一种状态变迁到另外一种状态的过程或手段。如走步、过程、规则、算子、逻辑运算符号等。(2) 问

2、题状态空间：表示问题全部可能状态及其关系的图。其构成由三部分构成（如图所示）原始问题描述：每次移动一步，只能移动跟空格相邻的数字单元。是否能从状态1变成状态2？(3) 15数码难题（15 puzzle problem）114121321011315984567412111321014315981567Shift 需要解决的问题如下： 问题的状态描述方法页：1矩阵或向量表示 问题的初始状态描述 问题的目标状态描述 问题描述状态转换的操作算子及其对状态描述的作用 两种状态的比较 119415131275861321014119415131275861321014119151341275861321

3、014119415131275861321014119415138127561321014 119415131275861321014119151341275861321014119151341275861321014 图 2-1 十五数码难题的部分状态图表示2-1-2 问题的状态图示法（1）基本概念状态图：由若干（不一定是有限）节点的集合构成（有向图或无向图）。路径：节点序列中，除外，所有节点都有一个后继，则该序列称为节点到节点的长度为的一条路径。可达节点：若节点到之间存在一条路径，则称节点到节点可达，节点称为节点的可达节点。边上带权重的图：给状态图中的弧线的值，即为边的权重，则该状态图被称

4、为带权重的图。（2）能够表示的问题 求解问题状态图中指定节点（初始状态）与另一节点（目标状态）之间的一条路径（或所有路径）。 求节点与节点集合中任一个节点之间的距离（最小距离，最大距离等）。 求节点集合中任一个节点与节点集合中任一个节点之间的路径。2-1-3 状态空间表示举例（从要解决的五个基本问题分析）例1 十五数码问题（表示如图2-1，可用矩阵形式表示）原始问题描述：有一个44的方格棋盘，其中的每一方格放入一1-15之间的数字值，一个空格方格，每次（只能）通过交换空格方格和其（水平和垂直方向上）相邻四个方格中的一个数进入下一状态。问是否能从给定棋盘初始状态，进入目标状态？或给定两棋盘格局，

5、能否从一个状态达到另一状态？等等。(AD)图2-3 推销员旅行问题的状态空间图(ACDE)(ACDEB)10目标节点7(ACDEBA)6597(ACD)(AB)101367(AE)(A) 起始节点(AC)例2 推销员旅行问题（如图2-2的形式表示，其状态空间图如2-3）。原始问题描述：推销员要在n个城市之间旅行推销产品，从一个城市出发，经过每个城市一次，最后回到起点城市。问：如果按照总路程的长短为评判标准，如何设计旅行路径，使得他能够旅行所有城市一次，且仅一次，同时，又能旅行路径最短？图2-2 推销员旅行问题69513106107710CDEBA例3 猴子和香蕉问题原始问题描述：在一个房间内有

6、只猴子（或狗），一只箱子和悬挂在天花板上的香蕉，猴子的高度不容易取得香蕉，但站在箱子上就可以。如果将其看成机器人，猴子怎么才能摘得香蕉？图中，A,B,C表示猴子、香蕉和箱子在房间内的相对位置。图2-4 猴子和香蕉问题BA猴子箱子香蕉C 问题的状态描述方法用一个四元组向量表示整个问题的各种状态，其中：表示猴子的水平位置；表示猴子是否在箱子顶上取香蕉，是时，否则；表示箱子所在的水平位置；表示猴子是否摘到香蕉，摘到，否则，。 问题的初始状态描述 问题描述状态转换的操作算子及其对状态描述的作用本问题有四个算子：(1)表示猴子走到水平位置。用产生式规则表示成：。即猴子在水平位置处，箱子在处，没有站在箱子

7、上，是否摘到香蕉处于值状态，在算子作用下，会进入下一个状态。（2）表示猴子把箱子推到水平位置。用产生式规则表示成：。即猴子与箱子在同一位置，且猴子不在箱子顶上时，它通过算子将箱子推到水平位置，进入状态。（3）算子表示猴子爬上箱子顶去。即：。（4）算子表示猴子在箱子顶上摘香蕉。即：。 问题的目标状态描述图2-4 猴子和香蕉问题的状态空间图目标状态初始状态2-2问题归约法（Problem Reduction）2-2-1 问题归约描述三个组成部分：(1) 初始问题描述；(2) 将问题变成子问题的操作符集合；(3) 一套本原问题的描述机制。基本思想：已知问题描述，希望通过对原始问题进行变换或分解，变成

8、难度较小的子问题，通过解决子问题，达到解决原始问题的目的。（1） Hanoi Puzzle（图示略） 问题的原始描述 原始问题的归约（将其变成三个难度较小的子问题） 归约的图表示（2） 归约问题的描述方法123 已有的问题描述方法：列表(list)、树(tree)、字符串(string)、矢量(array)、数组(array)等。 问题归约法利用状态空间法中的状态、算子和目标等概念来描述问题，但不等同于状态空间法。实际上是比状态空间法更一般的问题求解方法。其目的是产生具有明显解的本原问题。 “与或图”概念子问题集合本原问题图2-6 “与或图”的结构原始问题FEDMHNABC1) 每一节点代表要

9、求解问题的一个单一子问题或者子问题集合2) 叶子节点表示本原问题3) 带小弧线连接的分支节点集合称为与节点，当左右这些子问题得解时，其父问题才可解。4) 没有小弧线连接的分支节点称为或节点，只要其中任一个得解，其父问题即可解。（3） 问题归约机理 关键算符：对问题求解具有决定作用的算符。 差别：三元状态中，用中的元对集合中的目标进行测试，其中，不能满足的原因列表。 归约方法：将状态空间中的算符或者算符集合与求得的差别中之每一个原因进行比较，如果可以消去该差别，则结合成功，该算符成为关键算符。直到遇到本原问题为止。 可解节点、不可解节点和与或图的构成规则：（参见教材P31-33）注：因为，算符集

10、合本身在问题描述中不会发生变化，所以，描述中约定省略算符集合符号。2-2-2 例子猴子的初始状态为；该问题的算符集合为：第一步：计算初始问题的差别。最后一个元素为0，而与之相关的关键操作是，所以用对初始问题进行归约，得到两个子问题，即：和。第二步：对计算和初始问题的差别，然后获取关键算符，并依次进行归约。第N步：绘制归约过程的“与或图”组成：谓词符号、变量符号、函数符号、常量符号，并用圆括号、花括号和逗号分隔的符号体系。如：Married (father (L), mother (L)2-3谓词逻辑法2-3-1 谓词演算2-3-2 谓词公式符号体系：等。谓词公式定义：(1) 原子谓词公式是合式

11、公式(2) 若A和B都是合式公式，则都是合式公式(3) 若A是合式公式，则也是合适公式(4) 若A是合式公式，x是A中的自由变量，则都是合适公式(5) 只有按照上述(1)(4)的原则求得的公式，才是合式公式。基本运算定律及推论：否定律： 狄.摩根定律： 分配律： 交换律： 结合律： 逆否律：其它等价关系： 其它相关概念：约束变量、自由变量、析取式、合取式、真值表等。2-3-3 置换与合一(1) 置换(Substitution)：表达式的项可为变量符号、常量符号和函数表达式。在谓词逻辑中，利用假元推理（即）和全称化推理（即），用置换项对变量进行置换，使得与保持一致的变换过程。例2-3 对表达式可

12、以有以下4个置换：假定用表示对表达式用置换所得到的表达式的置换，则对以上表达式进行的置换结果分别为：置换是可结合的，但是，一般是不可交换的。例如：；但一般来说。(2) 合一(Unification)：寻找项对变量的置换，以使两个表达式一致的过程。表达式集合的置换表示：表示置换作用于其中的每个元素。表达式集合是可合一的：如果存在一个置换，使得，则称此为表达式集合的合一者。显然，使得表达式集合成为单一形式。例2-4 表达式集合的合一者为：。因为，经过置换后，集合中的表达式为单一形式。表达式集合的最通用/最一般合一者（mgu）：如果置换是的任一合一者，又存在一个，使得，则称为的最通用/最一般合一者。

13、例如，上例中的最简单的最一般合一者为：。(3) 合一算法（略）2-4 语义网络法1.概念：（最早由Quillian1966年在博士论文中提出）有关一个物体/一组物体或概念知识的图解表示。它由节点和弧线组成。节点表示实体、概念或情况等，弧线则表示节点之间关系。2. 组成：(1) 词法：指语义网络表示中涉及的符号、节点和弧线。(2) 结构：叙述符号排列的约束条件，指定各弧线连接的节点对。(3) 过程：说明访问过程，以便修改、建立和回答相关问题。(4) 语义：确定与描述相关的（联想）意义。3. 语义网络的特点： (1) 能够把实体的结构、属性与实体间的因果关系显式地表达出来。而与实体相关的属性、事实

14、、特征、关系等可通过相应节点的弧线推导出来。以便以联想的方式解释系统。(2) 表达的概念容易理解和学习。(3) 表达问题直观，符合人的思维习惯，便于与领域专家沟通。(4) 对网络结构的语义解释依赖于对结构的推理过程（没有结构约定），因此，推理的有效性不如谓词逻辑。(5) 节点间的联系可以是线状、树状、网状或递归形式。知识的检索和存储比较复杂。图2-7 简单事实的语义网络示例图 (c)图 (b)图 (a)HAS-PARTWINGSBIRDBIRDISAISABIRDSWALLOWSWALLOWISAISAISAXIAOYANXIAOYANSWALLOW4. 二元语义网络的表示图 (b) 表示小燕

15、子从春天到秋天占有一个巢的事实（从谓词演算的角度表达时，它需要用一个四元谓词表示）图2-8 具有多元关系的概念之二元语义网络示例图 (a) 表示小燕子是鸟类，且小燕子有一个巢的事实SITUATIONOWNERSHIPISAISASTARTTIMEOWN-1ENDTIMEISAFALLSPRINGTIMEISANEST-1NEST-1OWNEROWNEEISANESTOWNSNESTISAISAXIAOYANBIRDISASWALLOWBIRDISASWALLOWISAXIAOYAN概念节点：表示一种通用概念的语义节点。实例节点：表示某一具体物体和事实的节点。语义基元：基本概念和基本关系。以之能

16、够表达更一般的概念及其关系。图2-9 概念节点和实例节点ISAISACOLORCOLORREDGREENLIUHUAS CARCARMY CAR如图2-9中的CAR概念和MY CAR、LIUHUAS CAR实例；图2-7中的BIRD概念等。其中，图2-9中的CAR概念是语义基元。5. 多元语义网络的表示因为语义网络本质上只能表达二元关系，所以，对多元关系的语义表示，应当首先划分成相应的二元关系组合表达形式，或者合取。HOME TEAMISA图2-10 多元关系的语义网络表示VISITINGTEAM85-89TUGAMEBUG25SCORE例如：“北京大学和清华大学两校篮球队在北京大学进行的一场

17、比分为85比89的比赛”。用谓词逻辑可表示为：表示，但用语义网络时，需要将其分解为，如图2-10所示的四个二元关系来描述。6. 谓词逻辑中的量词和连接关系在语义网络中的表示方法(1) 合取如图2-10所表示的方法。又如：对“John gave Mary the book”的谓词逻辑表示为GIVE(JOHN,MARY,BOOK)，但用语义网络表示为图2-11所示。其中G1表示“一个特定的给某人东西的事件”，B23表示给出去的东西。ISABOOKGIVERISA图2-11用语义网络表示的合取B23JOHNGIVEMARYRECIPIENTG1OBJECT(2) 析取 在析取关系的语义网络表达中，其

18、析取连接上用加标注的方式加以界定（如图2-12中的DIS框）。 对析取中的合取，需要用合取标注界限CONJ界定（如图2-12所示）。(3) 否定用，或界限进行标注（图2-13）。图2-12 合取、析取及析取中嵌套合取结构时的语义网络表示(c) 语义网络表示中，析取结构中含有合取时的CONJ界限标注方法，即对（b）图的改进表示。(b) “John is a programmer or Mary is a lawyer”的语义网络之析取表示及DIS界限标注OCCUPATION EVENTSLAWYERRMARY(a) 两个特定的职业事件OC1和OC2之间的析取关系DISDISISAISACONJC

19、ONJISAPROGRAMMERPROFESSIONPROFESSIONWORKERWORKERJOHNOC1JOHNPROGRAMMERMARYLAWEROC2PROFESSIONWORKEROC1OCCUPATION EVENTSPROFESSIONWORKERISAOC2OC2OC1ISADISISAOCCUPATION EVENTS(4) 蕴涵用ANTE（antecedent）和CONSE（consequence）分别标注蕴涵的先决条件和结果界限。（用虚线标注）（图2-14）(5) 量化对存在量词的表示，可用ISA链完成。图2-13 否定的语义网络表示“Every one who li

20、ves at 37 Maple Street is a programmer” 的语义网络表示。其中，Y表示地址；O(X,Y)表示一个特定的职业事件；X表示与此事件相关联的人。图2-14 蕴涵的语义网络表示图13（c）图13（b）图13（a）PART-OFBCCISABPART-OFANEGCONSEANTEISALOCISAPROFESSIONWORKERO(X,Y)PERSONADDRESSY37-MAPLEXPROGRAMMEROCCUPATIONISABA2-15 (c)2-15 (b)2-15 (a)NOTE: 分割成空间分层集合方法的运用。“Every dog has bitten

21、 every postman”的语义网络表示。可见，断言G不发生改变。GS概念节点和断言G之间的关系不变，只是增加一条全称量词连接关系来表示“Every postman has been bitten”。FORM“Every dog has bitten a postman”的语义网络表示。其中，S1是一个特定的分割，表示断言G:“A dog has bitten a postman”。GS是一个概念节点，表示具有全称化的一般事件，而G只是GS的一个实例。“The dog bits the postman”的语义网络表示。其中，D表示特定的狗，P表示特定的邮递员，B表示特定的咬人事件。POST

22、MANBITEDOG图2-15 量化在语义网络中的表示RFORMISADOGISAGSGASSAILIANTISAISAISAPBDS1ISAASSAILIANTISAISAPBDPOSTMANBITEDOGVICTIMGISAGSPBITEPOSTMANISAISABDVICTIM对全称量词的表示，需要采取分割的方法，将语义网络分割成空间分层的集合，其中的每一个空间对应于一个或几个变量的范围。如图2-15所示。其中，对图2-15 (b)，其谓词形式为： 。其中，D是全称量化变量，B和P是存在量化变量。断言G由两个部分构成：一是断言本身（见图中虚线部分），用于表明断定关系，称为FORM；一是代

23、表全称量词的符号。7. 基于语义网的推理过程ISABRICKTOY图2-17 语义网络的槽与值COLORREDBRICK12(1) 几个概念值节点：在语义网络链的尾部处的节点。例如，图2-17中，尾部节点BRICK和TOY为实例BRICK12之ISA槽的两个值节点；其COLOR槽的值节点为RED值。槽(Slot)：节点之间的链接关系。例如图2-17中的ISA槽和COLOR槽。(2) 继承继承：在语义网络中，把对事物的描述从概念节点或类节点传递到实例节点的过程。图2-18 语义网络的值继承ISAISABLOCKRECTANGULARSHAPEBRICKTRIANGULARSHAPEWEDGEAK

24、OWEDGE18BRICK12AKO例如，在图2-18中，BRICK是概念节点，BRICK12是实例节点。BRICK在SHAPE槽中的RECTANGULAR属性值，在对BRICK12实例节点进行描述时，虽然没有关于BRICK12的SHAPE槽描述，但通过ISA链，可以将SHAPE槽的值传递给BRICK12实例。此即基于语义网络表示下的值的继承。特点：类似于人的思维习惯。对事物的属性和特征的一般化描述可以被认为是具体实例所具有的值。例如，鸟比较小，鲸鱼比较大，飞机可以飞翔等。三种继承过程：1) 值继承：通过ISA和AKO（A-Kind-Of）链用于语义网络中的描述或特性的继承。2) “如果需要”

25、继承：当不知道槽值时，可以利用当前已知的信息计算之。3) 缺省继承。(3) 匹配：当事物由多个部分构成时的继承过程。（见教材P43-44）2-5 框架法（Framework）2-5-1 概述概念：以一个通用数据结构的形式存储以往的经验，该结构即称为框架。特点：在次结构下，新的资料可以从过去的经验得到的概念来进行分析和解释。2-5-2 框架的构成(1) 构成：由描述事物的各个方面的槽(Slot)组成，每个槽有若干侧面(Face)构成，每个侧面又可以拥有多个值。(2) 结构（见教材P45）例如：JOHN有ISA，Profession，Height，Weight等槽，而其槽值分别为PERSON，PR

26、OGRAMMER，1.8m，79kg。（如表2-2所示）表2-2简单框架示例表框架结构槽的侧面或值备注JOHNFrame-Name ISA:PERSONSlot-1: Value Profession:PROGRAMMERSlot-2: Value Height:1.8mSlot-3: Value Weight:79kgSlot-4: Value(3) 框架系统大多数问题的框架表示，往往需要由多个框架同时进行。例如，表示立方体的视图的框架问题（见教材P45-46）。注：1) 一个框架结构可以包含一个或多个框架槽值；2) 一个框架结构可以同时被几个其它框架结构所使用；3) 框架是一种通用的知识表示形式，常常以树的形式展现框架系统。树状结构的框架系统基本构成如下：框架名 用类名表示AKO VALUE AKO槽具有VALUE侧面，值可以填写PROP DEFAULT PROP槽记录节点的特性信息，其侧面可缺省继承SF IF-NEEDED SF槽的“如果需要”侧面将进行相应计算CONFLICT ADD CONFLICT槽记录冲突表(4) 基于框架表示的推理过程（略）（见教材P47-48简介）2-6 剧本法（Script）剧本是一种特殊的框