第二章知识表示方法

人工智能第二章：知识表示方法知识的概念知识的一般概念：知识是人们在改造客观世界的实践中积累起来的认识和经验认识：包括对事物现象、本质、属性、状态、联系等的认识经验：包括解决问题的微观方法和宏观方法微观方法：如步骤、操作、规则、过程、技巧等宏观方法：如战略、战术、计谋、策略等

eg：“if

大雁向南飞，then

冬天就要来临了。”这样一条知识就是人们经过长期的观察，将“大雁向南飞”与“冬天来临”这两条信息关联在一起。“雪是白色的”反映雪与颜色的一种关系。知识表示知识表示：是研究用机器表示知识的可行性、有效性的一般方法，是一种数据结构与控制结构的统一体，既考虑知识的存储又考虑知识的使用。以知识和符号操作为基础的智能系统，其问题的求解都需要某种对解答的搜索。在搜索过程开始之前，必须先将问题表示出来。表示问题的方法，可能涉及状态空间、问题归约、语义网络、框架或谓词公式，或者把问题表示为一条要证明的定理，或者采用结构化方法等。对于传统人工智能问题，任何复杂的求解技术都离不开两方面的内容：1.表示2.搜索

本章内容2.1状态空间表示2.2问题归约表示2.3谓词逻辑表示2.4语义网络表示2.5框架表示2.6本体技术2.7过程表示2.1状态空间表示状态空间法（StateSpaceRepresentation）：

状态空间法就是用来表示问题及其搜索过程的一种方法。它是人工智能中最基本的形式化方法，用“状态（state）”和“算符（operator）”来表示问题。2.1状态空间表示2.1.1问题状态描述(1)状态（state）：描述某类不同事物间的差别而引入的一组最少变量q0，q1，…，qn的有序集合，是表示问题解法中每一步问题状况的数据结构。有序集合中每个元素qi（i=0,1,...,n）为集合的分量，称为状态变量。给定每个分量的一组值就得到一个具体的状态。

(2)算符（operator）：使问题从一种状态变化为另一种状态的手段称为操作符或算符。

(3)状态空间方法：是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合，即三元状态（S，F，G）。S：所有可能的问题初始状态集合；F：操作符集合；G：目标状态集合。2.1状态空间表示状态空间法举例：十五数码难题(15puzzle)：由15个编有1至15并放在4×4方格棋盘上的可走动的棋子组成。119415131275861321014123456789101112131415初始棋局目标棋局十五数码难题119415131275861321014119151341275861321014119415131275861321014119415138127561321014119415131275861321014123456789101112131415初始状态目标状态如何把初试棋局变成目标棋局？首先把适用的算符用于初始状态，以产生新的状态再把另一些适用算符用于这些新的状态；这样继续下去，直至产生目标状态为止2.1状态空间表示2.1.2状态图示法状态空间的图示形式称为状态空间图。状态图中有几个术语。节点(Node)：图形上的汇合点，用来表示状态、事件和时间关系的汇合。弧线(Arc)：节点间的连接线，表示算符；有向图(DirectedGraph)：一对节点用弧线连接起来，从一个节点指向另一个节点。后继节点(Descendantnode)与父辈节点(Parentnode)：如果某条弧线从节点ni指向节点nj，那么节点nj就叫做节点ni的后继节点或后裔，而节点ni叫做节点nj的父辈节点或祖先。2.1状态空间表示路径(Path)：某个节点序列(ni1,ni2,…,nik)当j=2,3,…,k时，如果对于每一个ni,j-1都有一个后继节点nij存在，那么就把这个节点序列叫做从节点ni1至节点nik的长度为k的路径。代价(Cost)：用c(ni,nj)来表示从节点ni指向节点nj的那段弧线的代价。两节点间路径的代价等于连接该路径上各节点的所有弧线代价之和。图的显示说明/隐示说明：指各节点及其具有代价的弧线可以/不可以由一张表明确给出。显然，显示说明对于大型的图是不切实际的，而对于具有无限节点集合的图则是不可能的。2.1状态空间表示问题的表示对求解工作有很大影响。人们希望有较小的状态空间表示。例如，对于十五数码问题：可以规定15×4＝60条规则，即“上移棋子4，下移棋子4，左移棋子4，右移棋子4···”，如果用“上下左右移动空格”，则只需4条规则。所以，移动空格是一种较好的表示。各种问题都可用状态空间加以表示，并用状态空间搜索法来求解。2.2问题归约表示问题归约的概念问题归约(problemreduction)是另一种基于状态空间的问题描述与求解方法。已知问题的描述，通过一系列变换把此问题最终变为一个子问题集合；这些子问题的解可以直接得到，从而解决了初始问题2.2问题归约表示问题归约表示的组成问题归约表示可由下列3部分组成：

(1)一个初始问题描述；

(2)一套把问题变换为子问题的操作符；

(3)一套本原问题描述。2.2问题归约表示问题归约的方法从目标（要解决的问题）出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个平凡的本原问题集合。这就是问题归约的实质。2.2问题归约表示2.2.1问题归约描述

梵塔难题问题描述2.2问题归约表示2.2问题归约表示2.2问题归约表示2.问题归约描述问题归约方法应用算符来把问题描述变换为子问题描述。问题描述可以有各种数据结构形式，表列、树、字符串、矢量、数组和其他形式都曾被采用过。对于梵塔难题，其子问题可用一个包含两个数列的表列来描述。于是，问题描述[（113），（333）]就意味着“把配置（113)变换为配置（333)”。2.2问题归约表示可以用状态空间表示的三元组合(S,F.G)来规定与描述问题。有关子问题可当作状态空间中两个一定的“脚踏石”之间寻找路径的问题来辨别。对于梵塔问题，子问题[(111)⇒(122)]，[(122)⇒(322)]以及[(322)⇒(333)]规定了最后解答路径将要通过的脚踏石状态（122）和（322）。问题归约方法可以应用状态、算符和目标这些表示法来描述问题，这并不意味着问题归约法和状态空间法是一样的。2.2问题归约表示2.2.2与或图表示与或图表示能够方便地用一个类似于图的结构来表示把问题归约为后继问题的替换集合，画出归约问题图。例如，设想问题A既可由求解问题B和C,也可由求解问题D,E和F，或者由单独求解问题H来解决。2.2问题归约表示2.2问题归约表示终叶节点模拟问题归约方法的相关结构是一个与或图。与或图中的节点之一—起始节点对应于原始问题描述，而对应于本原问题的节点叫做终叶节点。2.2问题归约表示在与或图上执行的搜索过程，其目的在于表明起始节点是有解的。与或图中一个可解节点的一般定义可以归纳如下：(1)终叶节点是可解节点。

(2)如果某个非终叶节点含有或后继节点，那么只有当其后继节点至少有一个是可解的，此非终叶节点才是可解的。

(3)如果某个非终叶节点含有与后继节点，那么只要当其后继节点全部为可解的，此非终叶节点才是可解的。2.2问题归约表示与或图的一些例子。图中，终叶节点用字母t标示，有解节点用小圆点表示，不可解节点用小圆圈表示。2.3谓词逻辑表示命题逻辑的局限性虽然命题逻辑(propositionallogic)能够把客观世界的各种事实表示为逻辑命题，但是它具有较大的局限性，不适合于表示比较复杂的问题Eg:10是一个整数T；雪是黑色的F谓词逻辑相对于命题逻辑的优势谓词逻辑(predicatelogic)允许表达那些无法用命题逻辑表达的事情。Eg:RUNS（LIUHUA，FASTEST）→WINS(LIUHUA，CHAMPION）2.3谓词逻辑表示逻辑语句，逻辑语句，更具体地说，一阶谓词演算(firstorderpredicatecalculus)是一种形式语言，其根本目的在于把数学中的逻辑论证符号化。如果能够采用数学演绎的方式证明一个新语句是从那些已知正确的语句导出的，那么也就能断定这个新语句也是正确的。2.3谓词逻辑表示2.3.1谓词演算1.语法和语义谓词逻辑的基本组成部分是谓词符号、变量符号、函数符号和常量符号，并用圆括弧、方括弧、花括弧和逗号隔开，以表示论域内的关系。例如，要表示“机器人(ROBOT)在1号房间(ROOM1)内”，可应用简单的原子公式：

INROOM（ROBOT，r1）上式中，ROBOT和r1为常量符号INROOM为谓词符号。

2.3谓词逻辑表示例如，函数符号mother可用来表示某人与他（或她）的母亲之间的一个映射。用下列原子公式表示“李（LI）的母亲与他的父亲结婚”这个关系：

MARRIED[father（LI），mother（LI）]2.3谓词逻辑表示计算方法：

对于已定义了的某个解释的一个原子公式，只有当其对应的语句在定义域内为真时，才具有值T(真）；而当其对应的语句在定义域内为假时，该原子公式才具有值F(假）。因此，INROOM(ROBOT,r1)具有值T.而INROOM(ROBOT,r2)则具有值F。当一个原子公式含有变量符号时，对定义域内实体的变量可能有几个设定。对某几个设定的变量，原子公式取值T;而对另外几个设定的变量．原子公式则取值F。2.3谓词逻辑表示2.连词和量词原子公式是谓词演算的基本积木块，应用连词∧（与）∨（或）以及⇒(蕴涵或隐含)等（在某些文献中，也用→来表示隐含关系），能够组合多个原子公式以构成比较复杂的合式公式。2.3谓词逻辑表示连词∧用来表示复合句子。例如，句子“我喜爱音乐和绘画”可写成：

LIKE（I，MUSIC）∧LIKE（I，PAINTING）此外，某些较简单的句子也可写成复合形式。例如．“李住在一幢黄色的房子里”即可用

LIVES（LI，HOUSE-1）∧COLOR（HOUSE-1，YELLOW）

用连词∧把几个公式连接起来而构成的公式叫做合取（式），而此合取式的每个组成部分叫做合取项。2.3谓词逻辑表示连词∨用来表示可兼有的“或”。例如，句子“李明打篮球或踢足球”可表示为：PLAYS（LIMING，BASKETBALL）∨PLAYS（LIMING，FOOTBALL）用连词∨把几个公式连接起来所构成的公式叫做析取（式），而此析取式的每一组成部分叫做析取项。由一些合式公式所构成的任一析取也是一个合式公式。2.3谓词逻辑表示连词→用来表示“如果-那么”的词句。例如，“如果该书是何平的，那么它是蓝色（封面）的”可表示为：

OWNS（HEPING，BOOK-1）→COLOR（BOOK-1，BLUE）又如，“如果刘华跑得最快，那么他取得冠军”可表示为：

RUNS（LIUHUA，FASTEST）→WINS(LIUHUA，CHAMPION）用连词→连接两个公式所构成的公式叫做蕴涵。蕴涵的左式叫做前项，右式叫做后项。2.3谓词逻辑表示符号~（非）用来否定一个公式的真值，也就是说，把一个合式公式的取值从T变为F,或从F变为T。如，子句“机器人不在2号房间内”可表示为：～INROOM（ROBOT，r2）前面具有符号~的公式叫做否定。2.3谓词逻辑表示使公式中的命题带有变量如果把句子限制为至今己介绍过的造句法所能表示的那些句子，而且也不使用变量项，那么可以把这个谓词演算的子集叫做命题演算。命题演算对于许多简化了的定义域来说，是一种有效的表示，但它缺乏用有效的方法来表达多个命题（如“所有的机器人都是灰色的”）的能力。要扩大命题演算的能力，需要使公式中的命题带有变量。2.3谓词逻辑表示使公式中的命题带有变量的例子一个原子公式如P（x),对于所有可能的变量x都具有值T。这个特性可由在P（x)前面加上全称量词（∀x来表示。如果至少有一个x值可使P(x)具有值T，那么这一特性可由在P(x)前面加上存在量词（∃x)来表示。例如，句子“所有的机器人都是灰色的”可表示为（∀x）［ROBOT（x）→COLOR（x，GRAY）]而句子“1号房间内有个物体”可表示为（∃x）INROOM（x，r1）这里，x是被量化了的变量，即x是经过量化的。2.3谓词逻辑表示2.3.2谓词公式

1.谓词公式的定义定义2.1用P（x1,x2,...,xn）表示一个n元谓词公式，其中P为n元谓词,x1,x2，…，xn为客体变量或变元。通常把P(x1,x2，…，xn）叫做谓词演算的原子公式，或原子谓词公式。可以用连词把原子谓词公式组成复合谓词公式，并把它叫做分子谓词公式。2.3谓词逻辑表示用归纳法给出谓词公式的定义。在谓词演算中合式公式的递归定义如下：（1)原子谓词公式是合式公式。

(2)若A为合式公式，则~A也是一个合式公式。

(3)若A和B都是合式公式，则(A∧B)，(A∨B)，(A→B）和(A←→B)也都是合式公式。

(4)若A是合式公式，x为A中的自由变元，则(∀x)A和（∃x）A都是合式公式。

(5)只有按上述规则(1)至（4）求得的那些公式，才是合式公式。2.3谓词逻辑表示例:试把下列命题表示为谓词公式：任何整数或者为正或者为负。解把上述命题意译如下：对于所有的x，如果x是整数，则x或为正的或者为负的。用I（x）表示“x是整数”，P（x）表示“x是正数”，N（x）表示"x是负数”。于是，可把给定命题用下列谓词公式来表示：

(∀x)（I（x）→（P（x）∨N（x）））2.3谓词逻辑表示2.合式公式的性质如果P和Q是两个合式公式，则由这两个合式公式所组成的复合表达式可由下列真值表给出。2.3谓词逻辑表示等价关系：（1）否定之否定

~（~P）等价于P

（2)P∨Q等价于~P→Q(3)狄·摩根定律

~(P∨Q)等价于~P∧~Q~(P∧Q)等价于~P∨~Q

（4)分配律

P∧(Q∨R)等价于(P∧Q)∨(P∧R)P∨(Q∧R)等价于(P∨Q)∧(P∨R)2.3谓词逻辑表示（5）交换律

P∧Q等价于Q∧PP∨Q等价于Q∨P

（6）结合律（P∧Q）∧R等价于P∧(Q∧R)

（P∨Q）∨R等价于P∨(Q∨R)

（7）逆否律

P→Q等价于~P→~Q2.3谓词逻辑表示2.3.3置换与合一

1．置换一个表达式的项可为变量符号、常量符号或函数表达式。函数表达式由函数符号和项组成。一个表达式的置换就是在该表达式中用置换项置换变量。2.3谓词逻辑表示置换实例2.3谓词逻辑表示2.合一寻找项对变量的置换，以使两表达式一致．叫做合一(unification)。合一是人工智能中很重要的过程。2.3谓词逻辑表示2.4语义网络表示

语义网络语义网络是知识的一种结构化图解表示．它由节点和弧线或链线组成。节点用于表示实体、概念和情况等，弧线用于表示节点间的关系。2.4语义网络表示

语义网络的组成：

(1)词法部分决定词汇表中允许有哪些符号，它涉及各个节点和弧线。

(2)结构部分叙述符号排列的约束条件，指定各弧线连接的节点对。

(3)过程部分说明访问过程，这些过程能用来建立和修正描述，以及回答相关问题。

(4)语义部分确定与描述相关的（联想）意义的方法，即确定有关节点的排列及其占有物和对应弧线。2.4语义网络表示

语义网络的特点：

(1)能把实体的结构、属性与实体间的因果关系显式和简明地表达出来，与实体相关的事实、特征和关系可以通过相应的节点弧线推导出来。这样便于以联想方式实现对系统的解释。

(2)由于与概念相关的属性和联系被组织在一个相应的节点中，因而使概念易于受访和学习。

(3)表现问题更加直观，更易于理解，适于知识工程师与领域专家沟通。语义网络中的继承方式也符合人类的思维习惯。

(4)语义网络结构的语义解释依赖于该结构的推理过程而没有结构的约定，因而得到的推理不能保证像谓词逻辑法那样有效。

(5)节点间的联系可能是线状、树状或网状的，甚至是递归状的结构，使相应的知识存储和检索可能需要比较复杂的过程。

2.4语义网络表示

2.4.1二元语义网络的表示

首先用语义网络来表示一些简单的事实。例如，所有的燕子（swallow）都是鸟(bird)小燕(xiaoyan)是一只燕子。用语义网络表示鸟有翅膀2.4语义网络表示

2.4语义网络表示

Eg1:表示小燕有一个巢(nest)2.4语义网络表示

Eg2:小燕从春天到秋天占有一个巢的信息加到语义网络中。使用现有的语义网络不能实现这一点。因为占有关系在语义网络中表示为一根链，它只能表示二元关系。如果用谓词运算来表示所讨论的例子，则要用一个四元的谓词演算。现在所需要的是一个和这样的四元谓词演算等价的，能够表示占有关系的起始时间、终止时间、占有者和所有物的语义网络2.4语义网络表示

由西蒙斯（Simmons）和斯洛克姆（Slocum）提出来的方法允许节点既可以表示一个物体或一组物体，也可以表示情况和动作。每一情况节点可以有一组向外的弧（事例弧），称为事例框，用以说明与该事例有关的各种变量。2.4语义网络表示

2.4语义网络表示

语义网络结点的选择在选择节点时，首先要弄清节点是用于表示基本的物体或概念的，或是用于多种自的的。否则，如果语义网络只用来表示一个特定的物体或概念，那么当有更多的实例时就需要更多的语义网络，这样就使问题复杂化。2.4语义网络表示

2.4语义网络表示

通常把有关一个物体或概念，或一组有关的物体或概念的知识用一个语义网络来表示。不然的话，会造成过多的网络，使间题复杂化。与此相关的是寻找基本概念和某些基本弧