人工智能及其应用知识

第二章知识表示

本章主要讨论知识表示问题，介绍7种知识表示方法：状态空间法、问题归约法、谓词演算法、语义网络法、框架表示、本体技术、过程表示。

掌握状态空间法、问题归约法、谓词演算法、语义网络法关键点及其之间关系，了解框架表示、本体技术、过程表示。人工智能及其应用知识第1页知识表示基本概念

知识表示：研究用机器表示知识可行性、有效性普通方法，是一个数据结构与控制结构统一体，既考虑知识存放又考虑知识使用。知识表示可看成是一组描述事物约定，以把人类知识表示成机器能处理数据结构。人工智能及其应用知识第2页人工智能系统所关心知识事实

相关问题环境一些事物知识，常以“…是…”形式出现。如事物分类、属性、事物间关系、科学事实、客观事实等。如雪是白色、鸟有翅膀、张三李四是好朋友、这辆车是张三。规则相关问题中与事物行动、动作相联络因果关系知识，是动态，常以“假如…那么…”形式出现。

控制相关问题求解步骤、技巧性知识，告诉怎么做一件事。

元知识相关知识知识，是知识库中高层知识。包含怎样使用规则、解释规则、校验规则、解释程序结构等知识。人工智能及其应用知识第3页2.1状态空间法问题求解问题求解(problemsolving)是个大课题，它包括归约、推断、决议、规划、常识推理、定理证实和相关过程关键概念。在分析了人工智能研究中利用问题求解方法之后，就会发觉许多问题求解方法是采取试探搜索方法。也就是说，这些方法是经过在某个可能解空间内寻找一个解来求解问题。状态空间法：基于解答空间问题表示和求解方法，它是以状态和算符(operator)为基础来表示和求解问题。人工智能及其应用知识第4页2.1状态空间法1.问题求解技术两个主要方面

(1)问题表示：假如描述方法不对，对问题求解会带来很大困难；(2)求解方法：采取试探搜索方法。

2.状态空间法三关键点

(1)状态（state）(2)算符（operator）(3)状态空间方法人工智能及其应用知识第5页2.1状态空间法2.1.1问题状态描述

1.定义

状态(state)：为描述某类不一样事物间差异而引入一组最少变量q0，q1，…，qn有序集合，其矢量形式以下：Q=[q0,q1,…,qn]T式中每个元素qi(i=0,1,,n)为集合分量,称为状态变量,给定每个分量一组值就得到一个详细状态,如Qk=[q0k,q1k,…,qnk]T式中每个元素qi(i=0,1，…，n)为集合分量，称为状态变量。算符：使问题从一个状态改变为另一个状态伎俩称为操作符或算符。操作符可为走步、过程、规则、数学算子、运算符号或逻辑符号等。问题状态空间(statespace)：是一个表示该问题全部可能状态及其关系图，它包含三种说明集合，即全部可能问题初始状态集合S、操作符集合F以及目标状态集合G。可把状态空间记为三元状态(S，F，G)。人工智能及其应用知识第6页2.1状态空间法2.状态空间表示详释

让我们先用数码难题(puzzleproblem)来说明状态空间表示概念。由15个编有1至15并放在4×4方格棋盘上可走动棋子组成。棋盘上总有一格是空，方便可能让空格周围棋子走进空格，这也能够了解为移动空格。图中绘出了两种棋局，即初始棋局和目标棋局，它们对应于该下棋问题初始状态和目标状态。

怎样把初始棋局变换为目标棋局呢？问题解答就是某个适当棋子走步序列，如"左移棋子12，下移棋子15，右移棋子4，…"等等。

人工智能及其应用知识第7页2.1状态空间法2.状态空间表示详释状态空间法：从某个初始状态开始，每次加一个操作符，递增建立起操作符试验序列，直到抵达目标状态为止。寻找状态空间全部过程包含从旧状态描述产生新状态描述，以及今后检验这些新状态描述，看是否抵达了该目标状态。对于最优化问题找到任一目标状态是不够，必须按某个准则实现最优化路径。P26完成目标状态三件事：１状态描述方式，尤其是初始状态描述；２操作符集合及其对状态描述作用；３目标状态特征。人工智能及其应用知识第8页2.1状态空间法2.1.2状态图示法

为了对状态空间图有更深入了解，这里介绍一下列图论中几个术语和图正式表示法。

1.图论中几个术语

节点(node)：图形上汇合点，用来表示状态、事件和时间关系汇合，也可用来指示通路汇合；弧线(arc)：节点间连接线；

有向图(directedgraph)：一对节点用弧线连接起来，从一个节点指向另一个节点。后继节点(descendantnode)与父辈节点(parentnode)：假如某条弧线从节点ni指向节点nj，那么节点nj就叫做节点ni后继节点或后代，而节点ni叫做节点nj父辈节点或祖先。人工智能及其应用知识第9页2.1状态空间法2.1.2状态图示法

1.图论中几个术语

路径：某个节点序列(ni1,ni2,…,nik)当j=2，3，…，k时，假如对于每一个ni，j-1都有一个后继节点nij存在，那么就把这个节点序列叫做从节点ni1至节点nik长度为k路径。代价：用c(ni,nj)来表示从节点ni指向节点nj那段弧线代价。两节点间路径代价等于连接该路径上各节点全部弧线代价之和。显式表示：各节点及其含有代价弧线由一张表明确给出。此表可能列出该图中每一节点、它后继节点以及连接弧线代价。隐式表示：节点无限集合{si}作为起始节点是已知。后继节点算符Γ也是已知，它能作用于任一节点以产生该节点全部后继节点和各连接弧线代价。人工智能及其应用知识第10页2.1状态空间法2.1.2状态图示法

2.图显式和隐式表示

一个图可由显式说明也可由隐式说明。显然，显式说明对于大型图是不切实际，而对于含有没有限节点集合图则是不可能。

另外，引入后继节点算符概念是方便。后继节点算符Γ也是已知，它能作用于任一节点以产生该节点全部后继节点和各连接弧线代价把后继算符应用于{si}组员和它们后继节点以及这些后继节点后继节点，如此无限制地进行下去，最终使得由Γ和{si}所要求隐式图变为显示图。问题表示对求解工作量有很大影响。人们显然希望有较小状态空间表示。许多似乎极难问题，当表示适当初就可能含有小而简单状态空间。人工智能及其应用知识第11页2.1状态空间法2.1.2状态图示法依据问题状态、操作符和目标条件选择各种表示，是高效率问题求解必须。各种问题都能够用状态空间加以表示，并用状态空间搜索法来求解。人工智能及其应用知识第12页2.1状态空间法2.1.2状态图示法

1.产生式系统（ProductionSystem）

·一个总数据库(globaldatabase)：它含有与详细任务相关信息；伴随应用情况不一样，这些数据库可能小得像数字矩阵那样简单，或许大得如检索文件结构那么复杂。·一套规则：它对数据库进行操作运算。每条规则由左右两部分组成，左部判别规则适用性或先决条件，右部描述规则应用时所完成动作。用规则来改变数据库就象用算符来改变状态一样。·一个控制策略：它确定应该采取哪一条适用规则，而且当数据库终止条件满足时，就停顿计算。控制策略由控制系统选择和确定。人工智能及其应用知识第13页推销员旅行问题总数据库：到当前为止所访问城市；规则对应于决议：即下一步走向城市Ａ，下一步走向城市Ｂ，…，下一步走向城市Ｅ，一条规则必须能把某个数据库变为一个正当数据库，不然不适应这个数据库；任一以Ａ为起点和终点，并出现全部其它城市总数据库，都满足终止条件．人工智能及其应用知识第14页2.1状态空间法2.1.2状态图示法

2.状态空间表示举例

例2猴子和香蕉问题(monkeyandbananaproblem)

在一个房间内有一只猴子(可把这只猴子看做一个机器人)、一个箱子和一束香蕉。香蕉挂在天花板下方，但猴子高度不足以碰到它。那么这只猴子怎样才能摘到香蕉呢?图2.4表示出猴子、香蕉和箱子在房间内相对位置。猴子和香蕉...

用一个四元表列(W,X,Y,Z)来表示这个问题状态，

其中

W－猴子水平位置

X－当猴子在箱子顶上时取X=1；不然取X=0

Y－箱子水平位置

Z－当猴子摘到香蕉时取Z=1；不然取Z=0

图2.4猴子和香蕉问题人工智能及其应用知识第15页2.1状态空间法2.1.2状态图示法

这个问题中操作(算符)以下：

(1)goto(U)猴子走到水平位置U，或者用产生式规则表示为：(W，0，Y，z)

(U，0，Y，z)(2.3)即应用操作goto(U)，能把状态(W，0，Y，z)变换为状态(U，0，Y，z)。

(2)pushbox(V)猴子把箱子推到水平位置V，即有(W，0，W，z)

(V，0，V，z)(2.4)应该注意是，要应用算符pushbox(V)，就要求产生式规则左边，猴子与箱子必须在同一位置上，而且，猴子不是在箱子顶上。这种强加于操作适用性条件，叫做产生式规则先决条件。

人工智能及其应用知识第16页2.1状态空间法2.1.2状态图示法

这个问题中操作(算符)以下：

(3)climbbox猴子爬上箱顶，即有(W，0，W，z)

(W，1，W，z)(2.5)在应用算符climbbox时也必须注意到，猴子和箱子应该在同一位置上，而且猴子不在箱顶上。

(4)grasp猴子摘到香蕉，即有(c,1,c,0)

(c,1,c,1)(2.6)其中，c是香蕉正下方地板位置，在应用算符grasp时，要求猴子和箱子都在位置c上，而且猴子已在箱子顶上。人工智能及其应用知识第17页2.1状态空间法

对于规则(2)，只有当算符pushbox(V)先决条件，即猴子与箱子在同一位置上而且猴子不在箱顶上这些条件得到满足时，算符pushbox(V)才是适用。这一操作算符作用是猴子把箱子推到位置V。在这一表示中，目标状态集合可由任何最终元素为1表列来描述。令初始状态为(a,0,b,0)

这时，goto(U)是唯一适用操作，并造成下一状态(U,0,b,0)。现在有3个适用操作，即goto(U)，pushbox(V)和climbbox(若U=b)。猴子和香蕉问题状态空间图人工智能及其应用知识第18页2.2问题归约法

2.2.1问题归约描述

先把问题分解为子问题和子-子问题，然后处理较小问题。对该问题某个详细子集解答就意味着对原始问题一个解答。问题归约表示组成部分：一个初始问题描述；一套把问题变换为子问题操作符；一套本原问题描述。问题归约实质：从目标(要处理问题)出发逆向推理，建立子问题以及子问题子问题，直至最终把初始问题归约为一个平凡本原问题集合。

人工智能及其应用知识第19页2.2问题归约法

2.2.1问题归约描述１梵塔难题

有3个柱子(1，2和3)和3个不一样尺寸圆盘（A，B和C）。在每个圆盘中心有一个孔，所以圆盘能够堆叠在柱子上。最初，3个圆盘都堆在柱子1上：最大圆盘C在底部，最小圆盘A在顶部。要求把全部圆盘都移到柱子3上，每次只许移动一个，而且只能先搬动柱子顶部圆盘，还不许把尺寸较大圆盘堆放在尺寸较小圆盘上。这个问题初始配置和目标配置如图2.6所表示。人工智能及其应用知识第20页2.2问题归约法

解题过程：

将原始问题归约为一个较简单问题集合，要把全部圆盘都移至柱子3，我们必须首先把圆盘C移至柱子3；而且在移动圆盘C至柱子3之前，要求柱子3必须是空。只有在移开圆盘A和B之后，才能移动圆盘C；而且圆盘A和B最好不要移至柱子3，不然就不能把圆盘C移至柱子3。所以，首先应该把圆盘A和B移到柱子2上。然后才能够进行关键一步，把圆盘C从柱子1移至柱子3，并继续处理难题其余部分。

将原始难题归约（简化）为以下子难题：移动圆盘A和B至柱子2双圆盘难题，如图(a)所表示。人工智能及其应用知识第21页2.2问题归约法

图2.7梵塔问题解答(a)图2.8梵塔问题解答(b)图2.9梵塔问题解答(c)人工智能及其应用知识第22页2.2问题归约法

梵塔问题归约图：子问题2可作为本原问题考虑，因为它解只包含一步移动。应用一系列相同推理，子问题1和子问题3也可被归约为本原问题，如图2.10所表示。这种图式结构，叫做与或图(AND/ORgraph)。

它能有效地说明怎样由问题归约法求得问题解答。梵塔问题归约图人工智能及其应用知识第23页2.2问题归约法

2.2.1问题归约描述２问题归约描述问题归约方法应用算符把问题描述变换为子问题描述，问题描述能够用各种数据结构形式，包含表列、树、字符串、矢量、数组等。梵塔问题采取包含两个数列表列来描述,[(113),（333)]表示把配置（113）变换为配置（333）。用状态空间表示三元组合（S，F，G）来要求与描述问题，相关子问题能够看成状态空间中两个一定“脚踏石”之间寻找路径来区分。梵塔问题中子问题[（111）=>（122）]，[（122）=>（322）]，[（322）=>（333）]，要求了最终路径将要经过“脚踏石”状态（122）和（322）。人工智能及其应用知识第24页2.2问题归约法

2.2.2与或图表示

与图、或图、与或图：

普通地，我们用一个类似图结构来表示把问题归约为后继问题替换集合，这种结构图叫做问题归约图，或叫与或图。以下列图所表示:（引入附加节点使含有一个以上后继问题每个集合能够聚集在它们各自父辈节点之下。）子问题替换集合结构图与或图

人工智能及其应用知识第25页2.2问题归约法

2.2.2问题归约描述

一些关于与或图术语：终叶节点：对应于原问题本原节点。或节点：只要处理某个问题就可处理其父辈问题节点集合，如（M，N，H）。与节点：只有处理全部子问题，才能处理其父辈问题节点集合，如（B,C)和（D,E,F）各个结点之间用一端小圆弧连接标识。

人工智能及其应用知识第26页2.2问题归约法

2.2.2问题归约描述

与或图：由与节点及或节点组成结构图。可解节点普通定义：

(1)终叶节点是可解节点(因为它们与本原问题相关连)。

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

(3)假如某个非终叶节点含有与后继节点，那么只有当其后继节点全部为可解时，此非终叶节点才是可解。图2.15与或图例子人工智能及其应用知识第27页2.2问题归约法

2.2.2问题归约描述

不可解节点普通定义:

(1)没有后代非终叶节点为不可解节点。(2)假如某个非终叶节点含有或后继节点，那么只有当其全部后代为不可解时，此非终叶节点才是不可解。(3)假如某个非终叶节点含有与后继节点，那么只要当其后代最少有一个为不可解时，此非终叶节点才是不可解。

人工智能及其应用知识第28页2.2问题归约法

2.2.2问题归约描述

与或图组成规则

(1)与或图中每个节点代表一个要处理单一问题或问题集合。图中所含起始节点对应于原始问题。

(2)对应于本原问题节点，叫做终叶节点，它没有后代。

(3)对于把算符应用于问题A每种可能情况，都把问题变换为一个子问题集合；有向弧线自A指向后继节点表示所求得子问题集合，以下列图所表示，把问题A归约为3个不一样子问题集合N，M，H(或节点)。

图2.16与或树人工智能及其应用知识第29页2.2问题归约法

2.2.2问题归约描述

与或图组成规则(4)普通对于代表两个或两个以上子问题集合每个节点，有向弧线从此节点指向此子问题集合中各个节点。因为只有当集合中全部项都有解时，这个子问题集合才能取得解答，所以这些子问题节点叫做与节点。

(5)在特殊情况下，当只有一个算符可应用于问题A，而且这个算符产生含有一个以上子问题某个集合时，由上述规则3和规则4所产生图能够得到简化。

所以，代表子问题集合中间或节点能够被略去，如右图所表示。

图2.16与或树人工智能及其应用知识第30页2.3

谓词逻辑法

2.3.1谓词演算（PredicateCalculus）

1.语法和语义(Syntax&Semantics)

谓词逻辑基本组成部分：谓词符号、变量符号、函数符号和常量符号，并用圆括号、方括号、花括号和逗号隔开，表示论域内关系。原子公式(atomicformulas)由若干谓词符号和项组成谓词演算。原子公式是谓词演算基本积木块。比如，要表示＂机器人(ROBOT)在１号房间(r1)内＂，如图2.19所表示，能够应用原子公式:人工智能及其应用知识第31页2.3

谓词逻辑法

2.3.1谓词演算（PredicateCalculus）

1.语法和语义(Syntax&Semantics)

当机器人ROBOT移到房间r2时，原子公式能够表示为：INROOM(ROBOT,r2)这两个原子公式通用形式就是

又如,“李母亲和他父亲结婚”这句话原子公式表示以下：人工智能及其应用知识第32页2.3

谓词逻辑法

2.3.1谓词演算（PredicateCalculus）

2.连词和量词(Connective&Quantifiers)(1)连词

与·合取（conjunction）合取就是用连词∧把几个公式连接起来而组成公式。合取项是合取式每个组成部分。例：LIKE(I，MUSIC)∧LIKE(I，PAINTING)(我喜爱音乐和绘画。)

人工智能及其应用知识第33页2.3

谓词逻辑法

2.3.1谓词演算（PredicateCalculus）

2.连词和量词(Connective&Quantifiers)或·析取（disjunction）析取就是用连词∨把几个公式连接起来而组成公式。析取项是析取式每个组成部分。例：PLAYS(LILI，BASKETBALL)∨PLAYS(LILI，FOOTBALL)(李力打篮球或踢足球。)

人工智能及其应用知识第34页2.3

谓词逻辑法

2.3.1谓词演算（PredicateCalculus）

2.连词和量词(Connective&Quantifiers)

(1)连词

蕴涵"=>"表示"假如-那么"语句。用连词=>连接两个公式所组成公式叫做蕴涵。IF=>THEN前项后项(左式)(右式)例：RUNS(LIUHUA，FASTEST)=>TWINS(LIUHUA，CHAMPION)(假如刘华跑得最快，那么他取得冠军)非（NOT）表示否定，～、┑均可表示否定。例：～INROOM(ROBOT，r2)(机器人不在2号房间内。)人工智能及其应用知识第35页2.3

谓词逻辑法

2.3.1谓词演算（PredicateCalculus）

2.连词和量词(Connective&Quantifiers)

(2)量词

全称量词(UniversalQuantifier)若一个原子公式P(x)，对于全部可能变量x都含有T值，则用(x)P(x)表示。例：(x)[ROBOT(x)=>COLOR(x,GRAY)](全部机器人都是灰色）(x)[Student(x)=>Uniform(x,Color)](全部学生都穿彩色制服)人工智能及其应用知识第36页2.3

谓词逻辑法

2.3.1谓词演算（PredicateCalculus）

2.连词和量词(Connective&Quantifiers)

(2)量词

存在量词(ExistentialQuantifier)

若一个原子公式P(x)，最少有一个变元X，可使P(X)为T值，则用(x)P(x)表示。例：(x)INROOM(x,r1)(1号房间内有个物体)量化变元(QuantifiedVariables)被量化了变元x-约束变量。人工智能及其应用知识第37页2.3

谓词逻辑法

2.3.2谓词公式（PredicateFormulas）

1.谓词公式定义

原子谓词公式：用P(x1,x2,…,xn)表示一个n元谓词公式，其中P为n元谓词，x1,x2,…xn为客体变量或变元。通常把P(x1,x2,…,xn)叫做谓词演算原子公式，或原子谓词公式。

分子谓词公式：能够用连词把原子谓词公式组成复合谓词公式，并把它叫做分子谓词公式。

适当公式(WFF,well-formedformulas)递归定义：

(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)求得那些公式，才是适当公式。人工智能及其应用知识第38页2.3

谓词逻辑法

2.3.2谓词公式（PredicateFormulas）

1.谓词公式定义

例题："对于全部x，假如x是整数，则x或为正或者为负。"(x)(I(x)=>(P(x)∨N(x)))I(x)表示"x是整数"，P(x)表示"x是正数"，N(x)表示"x是负数"。人工智能及其应用知识第39页2.3

谓词逻辑法

2.3.2谓词公式（PredicateFormulas）

2.适当公式性质

适当公式真值：p36表2-1真值表人工智能及其应用知识第40页2.3

谓词逻辑法

2.3.3置换与合一（Substitution&Unification）

1.置换

在谓词逻辑中，有些推理规则可应用于一定适当公式和适当公式集，以产生新适当公式。一个主要推理规则是假元推理，这就是由适当公式W1和W1=>W2产生适当公式W2运算。另一个推理规则叫做全称化推理，它是由适当公式(x)W(x)产生适当公式W(A)，其中A为任意常量符号。

假元推理：

全称化推理：

综合推理：

人工智能及其应用知识第41页2.3

谓词逻辑法

2.3.3置换与合一（Substitution&Unification）

1.置换

置换：用项(A)替换函数表示式中变量(x)，记为ES，即表示一个表示式E(Expression)用一个置换S(Substitution)而得到表示式置换。

例1表示式P[x,f(y),B]4个置换为s1={z/x,w/y}s2={A/y}s3={q(z)/x,A/y}s4={c/x,A/y}我们用Es来表示一个表示式E用置换s所得到表示式置换。于是，我们可得到P[x,f(y),B]4个置换例，以下：P[x,f(y),B]s1=P[z,f(w),B]P[x,f(y),B]s2=P[x,f(A),B]P[x,f(y),B]s3=P[q(z),f(A),B]P[x,f(y),B]s4=P[c,f(A),B]

人工智能及其应用知识第42页2.3

谓词逻辑法

2.3.3置换与合一（Substitution&Unification）

2.性质

可结合律(LS1)S2=L(S1S2)(L表示一表示式)(S1S2)S3=S1(S2S3)置换是可结合。用s1s2表示两个置换s1和s2合成。L表示一表示式，则有(Ls1)s2=L(s1s2)以及(s1s2)s3=s1(s2s3)

即用s1和s2相继作用于表示式L是同用s1s2作用于L一样。

普通说来，置换是不可交换，即s1s2≠s2s13.合一(unification)P38合一：寻找项对变量置换，以使两表示式一致。

可合一：假如一个置换s作用于表示式集{Ei}每个元素，则我们用{Ei}s来表示置换例集。我们称表示式集{Ei}是可合一。人工智能及其应用知识第43页2.3

谓词逻辑法2.3.3置换与合一（Substitution&Unification）

例:表示式集P[x,f(y),B],P[x,f(B),B]合一者为:s={A/x,B/y}因为P[x,f(y),B]s=P[x,f(B),B]=P[A,f(B),B]

即s使表示式成为单一形式:P[A,f(B),B],但最简单合一者为:s’={B/Y}

人工智能及其应用知识第44页2.4语义网络法

语义网络是1968年Quilian在研究人类联想记忆时提出心理学模型，认为记忆是由概念间联络来实现。1972年，Simmons首先将语义网络表示法用于自然语言了解系统。

语义网络结构：语义网络是知识一个图解表示，它由节点和弧线或链线组成。节点用于表示实体、概念和情况等，弧线用于表示节点间关系。组成部分:1词法部分：决定表示词汇表中允许有哪些符号，它包括各个节点和弧线。2结构部分：叙述符号排列约束条件，指定各弧线连接节点对。3过程部分：说明访问过程，这些过程能用来建立和修正描述，以及回答相关问题。4语义部分：确定与描述相关(联想)意义方法即确定相关节点排列及其占有物和对应弧线。人工智能及其应用知识第45页2.4语义网络法2.4.1二元语义网络表示(RepresentationofTwo-ElementSemanticNetwork)

1.表示简单事实

例1.全部燕子都是鸟

人工智能及其应用知识第46页2.4语义网络法2.4.1二元语义网络表示(RepresentationofTwo-ElementSemanticNetwork)

2.表示占相关系和其它情况P40例2.小燕是一只燕子，燕子是鸟；巢-1是小燕巢，巢-1是巢中一个。

3.选择语义基元

试图用一组基元来表示知识，方便简化表示，并可用简单知识来表示更复杂知识。

人工智能及其应用知识第47页人工智能及其应用知识第48页2.4语义网络法例3.我椅子颜色是咖啡色；椅子包套是皮革；椅子是一个家俱；椅子是座位一部分；椅子全部者是X；X是个人，以下列图所表示：

人工智能及其应用知识第49页2.4语义网络法

2.4.2多元语义网络表示

语义网络是一个网络结构。节点之间以链相连。多元语义网络表示实质：把多元关系转化为一组二元关系组合，或二元关系合取。假如所要表示知识是一元关系，比如，要表示李明是一个人，这在谓词逻辑中可表示为MAN(LIMING)。用语义网络，这就能够表示为:与这么表示法相等效关系在谓词逻辑中表示为ISA(LIMING，MAN)。这说明语义网络能够毫无困难地表示一元关系。人工智能及其应用知识第50页2.4语义网络法

比如：要表示北京大学(BEIJINGUniversity,简称BU)和清华大学(TSINGHUAUniversity,简称TU)两校篮球队在北大进行一场比赛比分是85比89。若用谓词逻辑可表示为SCORE(BU，TU，(85-89))。这个表示式中包含3项，而语义网络从本质上来说，只能表示二元关系。处理这个矛盾一个方法是把这个多元关系转化成一组二元关系组合，或二元关系合取。详细来说，多元关系R(X1，X2，…，Xn)总能够转换成R1(X11，X12)∧R2(X21，X22)∧…∧Rn(Xn1,Xn2)图2.20多元关系语义网络表示

人工智能及其应用知识第51页2.4语义网络法

2.4.3语义网络推理过程

在语义网络知识表示方法中，赋予网络结构含义完全决定于管理这个网络过程特征。为了便于以下叙述，对所用符号作深入要求。区分在链头部和在链尾部节点，把在链尾部节点称为值节点。另外，我们还要求节点槽相当于链，不过取不一样名字而已。在图2.28中砖块12(BRICK12)有3个链，构成两个槽。其中一个槽只有一个值，另外一个槽有两个值。我们说颜色槽(COLOR)填入红色(RED)，ISA槽填入了砖块(BRICK)和玩具(TOY)。图2.28语义网络槽和数值人工智能及其应用知识第52页2.4语义网络法

2.4.3语义网络推理过程

语义网络中推理过程主要有两种:一个是继承，另一个是匹配。以下我们分别介绍这两种过程。

1.继承

在语义网络中所谓继承是把对事物描述从概念节点或类节点传递到实例节点。比如在图2.29上所表示语义网络中BRICK是概念节点，BRICK12是一个实例节点。BRICK节点在SHAPE(外形)槽，其中填入了RECTANGULAR(矩形)，说明砖块外形是矩形。这个描述能够经过ISA链传递给实例节点BRICK12。所以，即使BRICK12节点没有SHAPE槽，但能够从这个语义网络推理出BRICK12外形是矩形。图2.29语义网络值继承人工智能及其应用知识第53页2.4语义网络法

2.4.3语义网络推理过程

1.继承

这种推理过程，类似于人思维过程。一旦知道了某种事物身份以后，能够联想起很多关于这件事物普通描述。比如，我们通常认为鲸鱼很大，鸟比较小，城堡很古老，运动员很健壮。这就像我们用每种事物经典情况来描述各种事物--鲸鱼、鸟、城堡和运动员--那样。

一共有3种继承过程：值继承、"假如需要"继承和"默认"继承。

人工智能及其应用知识第54页2.4语义网络法

2.4.3语义网络推理过程

语义网络中推理过程主要有两种:一个是继承，另一个是匹配。以下我们分别介绍这两种过程。

1.继承

(1)值继承

除了ISA链以外，另外还有一个AKO(是某种)链也可被用于语义网络中描述或特征继承。AKO是A-KIND-OF缩写。

总之，ISA和AKO链直接地表示类组员关系以及子类和类之间关系，提供了一个把知识从某一层传递到另一层路径。

为了能利用语义网络继承特征进行推理我们还需要一个搜索程序用来在适当节点寻找适当槽。

人工智能及其应用知识第55页2.4语义网络法

2.4.3语义网络推理过程

1.继承

(2)“假如需要”继承

在一些情况下，当我们不知道槽值时，能够利用已知信息来计算。比如，我们能够依据体积和物质密度来计算积木重量。进行上述计算程序称为if-needed(假如需要)程序。

为了储存进行上述计算程序，我们需要改进节点槽值结构，允许槽有几个类型值，而不只是一个类型。为此，每个槽又能够有若干个侧面，以储存这些不一样类型值。这么，以前我们讨论原始意义上值就放“值侧面”中，if-needed程序，存放在IF-NEEDED侧面中。

比如在图2.30(a)中，一个重量确定程序存放在BLOCK节点WEIGHT槽IF-NEEDED侧面中。人工智能及其应用知识第56页图2.30语义网络"假如需要"继承人工智能及其应用知识第57页2.4语义网络法

2.4.3语义网络推理过程

1.继承

(3)“缺省”继承

一些情况下，当我们对事物所作假设不是十分有把握时，最好对所作假设加上“可能”这么字眼。比如，我们能够认为法官可能是老实，但不一定是；或认为宝石可能是很昂贵，但不一定是。

我们把这种含有相当程度真实性，但又不能十分必定值称为“缺省”值。这种类型值被放入槽DEFAULT(缺省)侧面中.比如，在图2.31中，网络所表示含义是：从整体来说，积木颜色很可能是蓝色，但在砖块中，颜色可能是红。对BLOCK和BRICK节点来说，在COLOR槽中找到侧面都是DEFAULT侧面，在图中以括弧加以标志图2.31语义网络"缺省"继承人工智能及其应用知识第58页2.4语义网络法

2.4.3语义网络推理过程

2.匹配

至今我们所讨论是类节点和实例节点，比如BRICK和BRICK12之间继承值。现在我们转向讨论更为困难一些问题。当处理包括由几部分组成事物时，如图2.32中玩具房(TOY-HOUSE)和玩具房-77(TOY-HOUSE77)，继承过程将怎样进行。我们不但必须制订怎样把值从玩具房传递到玩具房-77路径，而且必须制订把值从玩具房部件传递到玩具房-77部件路径。

人工智能及其应用知识第59页

比如，很显著，因为TOY-HOUSE77是TOY-HOUSE一个实例，所以它必须有两个部件，一个是砖块，另一个是楔块(wedge)。另外，作为玩具房一个部件砖块必须支撑楔块。在图2.32中，玩具房-77部件以及它们之间链，都用虚线画节点箭头来表示。因为这些知识是经过继承而间接知道，并不是经过实际节点和链直接知道。所以，我们说虚线所表示节点和箭头表示链是虚节点和虚链。图2.32虚节点和虚链

人工智能及其应用知识第60页图2.32虚节点和虚链

没有必要从TOYHOUSE节点把这些节点和链复制到TOY-HOUSE77节点去，除非我们需要在这些复制节点加上玩具房-77所特有信息。比如，假如我们要表示玩具房-77砖块颜色是红，就必须为TOY-HOUSE77建立一个BRICK节点，并把RED放在这个BRICK节点COLOR槽中。假设我们把RED放在作为玩具房部件BRICK节点COLOR槽中，这将意味着全部玩具房砖都是红色，而不是只在由玩具房-77所描述特定房子中砖是红色。人工智能及其应用知识第61页2.4语义网络法

2.4.3语义网络推理过程

现在我们来研究图2.33中结构35(STRUCTURE35)。已知这个结构有两个部件，一个砖块BRICK12和一个楔块WEDGE18。一旦在STRUCTURE35和TOY-HOUSE之间放上ISA链，我们就知道BRICK12必须支撑WEDGE18。在图2.18上用虚线箭头表示BRICK12和WEDGE18之间SUPPORT虚链。因为很轻易做部件匹配，所以虚线箭头位置和方向很轻易确定。WEDGE18必定和作为TOY-HOUSE一个部件楔块相匹配，而BRICK12必定和砖块相匹配。图2.33部件匹配人工智能及其应用知识第62页2.5框架表示法心理学研究结果表明，在人类日常思维和了解活动中，当分析和解释碰到新情况时，要使用到过去经验中积累知识。这些知识规模巨大而且以很好组织形式保留在人们记忆中。比如:当我们走进一家从来没来过饭店时，依据以往经验，能够预见在这家饭店我们将会看到菜单、桌子、服务员等等。当我们走进教室时，能够预见在教室里能够看到椅子、黑板等等。我们试图用以往经验来分析解释当前所碰到情况。人工智能及其应用知识第63页2.5框架表示法当然，我们无法把过去经验一一都存在脑子里，而只能以一个通用数据结构形式存放以往经验。这么数据结构称为框架。框架提供了一个结构，一个组织。在这个结构或组织中，新资料能够用从过去经验中得到概念来分析和解释。所以，框架是一个结构化表示法。

通常框架采取语义网络中节点-槽-值表示结构。所以框架也能够定义为是一组语义网络节点和槽，这组节点和槽能够描述格式固定事物、行动和事件。语义网络可看做节点和弧线集合，也能够视为框架集合。

人工智能及其应用知识第64页2.5框架表示法2.5.1框架组成

框架通常由描述事物各个方面槽组成，每个槽能够拥有若干个侧面，而每个侧面又能够拥有若干个值。这些内容能够依据详细问题详细需要来取舍，一个框架普通结构以下：

<框架名>

<槽1><侧面11><值111>…<侧面12><值121>……

<槽2><侧面21><值211>…

…

…

<槽n><侧面n1><值n11>…

…

<侧面nm><值nm1>…

人工智能及其应用知识第65页2.5框架表示法2.5.1框架组成较简单情景是用框架来表示诸如人和房子等事物。比如，一个人能够用其职业、身高和体重等项描述，因而能够用这些项目组成框架槽。当描述一个详细人时，再用这些项目标详细值填入到对应槽中。表2.3给出是描述John框架。

对于大多数问题，不能这么简单地用一个框架表示出来，必须同时使用许多框架,组成一个框架系统。表2.3简单框架示例JOHN描述框架人工智能及其应用知识第66页2.5框架表示法一个框架系统

图2.32所表示就是表示立方体一个视图框架。图中，最高层框架，用isa槽说明它是一个立方体，并由region槽指示出它所拥有3个可见面A、B、E。而A、B、E又分别用3个框架来详细描述。用mustbe槽指示出它们必须是一个平行四边形。

图2.32一个立体视图框架表示人工智能及其应用知识第67页2.5框架表示法一个框架系统

为了能从各个不一样角度来描述物体，能够对不一样角度视图分别建立框架，然后再把它们联络起来组成一个框架系统。图2.35所表示就是从3个不一样角度来研究一个立方体例子。为了简便起见，图中略去了一些细节，在表示立方体表面槽中，用实线与可见面连接，用虚线与不可见面连接。

图2.35表示立方体框架系统人工智能及其应用知识第68页2.5框架表示法以下是另一个框架系统例子

"今天一次强度为里氏8.5级强烈地震攻击了下斯洛文尼亚(LowSlabovia)地域，造成25人死亡和5亿美元财产损失。下斯洛文尼亚地域主席说，多年来，靠近萨迪豪金斯断层重灾区一直是一个危险地域。能够用图2.36中虚线部分所表示EARTHQUAKE13框架来表示这一新闻。图2.36表示灾害事件框架系统

人工智能及其应用知识第69页

图中在链上标明地点(place)、日期(day)、伤亡(fatalities)、损失(damage)、震级(magnitude)、断层(fault)是槽名称。在节点中填入对应填充值。

这个框架能够发展成框架系统，以描述更复杂更广泛事件。比如，向上移动一层话，能够把地震看成是一个灾害事件(disasterevent)，除此之外还能够有洪水(flood)、飓风(huricane)等灾害事件、它们组成一个DISASTEREVENT基本框架。如向下移动一层，在每个槽中也能够填入一个框架。比如FATALITIES、也能够用一个框架来描述。

人工智能及其应用知识第70页2.5框架表示法

显而易见，这种框架系统含有树状结构。树状结构框架系统每个节点含有以下框架结构形式：框架名AKOVALUE<值>PROPDEFAULT<表1>SFIF-NEEDED<算术表示式>CONFLICTADD<表2>其中框架名用类名表示。AKO是一个槽，VALUE是它侧面，经过填写<值>内容表示出该框架属于哪一类。PROP槽用来统计该节点所含有特征，其侧面DEFAULT表示该槽内容是能够进行缺省继承，即当<表1>为非NIL时，PROP槽值为<表1>，当<表1>为NIL时，PROP槽值用其父节点PROP槽值来代替。人工智能及其应用知识第71页2.5框架表示法2.5.2框架推理

框架是一个复杂结构语义网络。所以语义网络推理中匹配和特征继承在框架系统中也能够实施。除此以外，因为框架用于描述含有固定格式事物、动作和事件，所以能够在新情况下，推论出未被观察到事实。框架用以下几个路径来帮助实现这一点：

(1)框架包含它所描述情况或物体多方面信息。这些信息能够被引用，就像已经直接观察到这些信息一样。(2)框架包含物体必须含有属性。在填充框架各个槽时，要用到这些属性。

(3)框架描述它们所代表概念经典事例。假如某一情况在很多方面和一个框架相匹配，只有少部分相互之间存在不一样之处。这些不一样之处很可能对应于当前情况主要方面，可能应该对这些不一样之处作出解答。所以，假如一个椅子被认为应有4条腿，而某一椅子只有3条腿，那么或许这把椅子需要修理。

人工智能及其应用知识第72页2.5框架表示法2.5.2框架推理

用一个框架来详细表达一个特定情况过程，经常不是很顺利。但当这个过程碰到障碍时，经常无须放弃原来努力去从头开始，而是有很多方法可想：(1)选择和当前情况相对应当前框架片断，并把这个框架片断和候补框架相匹配。选择最正确匹配。假如当前框架，总来说差不多是能够接收，则许多已经做，相关建立子结构以填入这个框架工作将可保留。(2)尽管当前框架和要描述情况之间有不相匹配地方，不过依然能够继续应用这个框架。比如，所研究只有3条腿椅子，可能是一个破椅子或是有另一个在椅子前面物体挡住了一条腿。框架某一部分包含关于哪些特征是允许不相匹配信息。一样，也有普通启发性标准，比如一个漏失某项期望特征框架(可能因为被挡住视线造成)比另一个多了某一项不应有特征框架更适合当前情况。举例来说，一个人只有一条腿比说一个人有3条腿或有尾巴更合乎情理些。

人工智能及其应用知识第73页2.5框架表示法2.5.2框架推理

(3)查询框架之间专门保留链，以提出应朝哪个方向进行试探提议。这种链例子与图2.35所表示网络相同。比如，假如和CHAIR框架匹配时，发觉没有靠背，而且太宽，这时就提议用BENCH(条凳)框架；假如太高，而且没有靠背，就提议用STOOL(凳子)框架。图2.37相同网络人工智能及其应用知识第74页2.5框架表示法2.5.2框架推理

(4)沿着框架系统排列层次结构向上移动(即从狗框架→哺乳动物框架→动物框架)，直到找到一个足够通用，并不与已经有事实矛盾框架。假如框架足够详细，能够提供所要求知识，那就采取这个框架。或者建立一个新、恰好在匹配框架下一层框架。

人工智能及其应用知识第75页2.6剧本(script)表示

剧本是框架一个特殊形式，它用一组槽来描述一些事件发生序列，就像剧本中事件序列一样，故称为"剧本"。

2.6.1剧本组成

一个剧本普通由以下各部分组成：

(1)开场条件给出在剧本中描述事件发生前提条件。

(2)角色用来表示在剧本所描述事件中可能出现相关人物一些槽。

(3)道具这是用来表示在剧本所描述事件中可能出现相关物体一些槽。

(4)场景描述事件发生真实次序，能够由多个场景组成，每个场景又能够是其它剧本。

(5)结果给出在剧本所描述事件发生以后通常所产生结果。

人工智能及其应用知识第76页2.6剧本(script)表示

剧本是框架一个特殊形式，它用一组槽来描述一些事件发生序列，就像剧本中事件序列一样，故称为“剧本”。

2.6.1剧本组成

下面以餐厅剧本为例说明剧本各个部分组成。

(1)开场条件

(a)用户饿了，需要进餐。(b)用户有足够钱(2)角色

用户，服务员，厨师，老板。

(3)道具

食品，桌子，菜单，钱。

人工智能及其应用知识第77页2.6剧本(script)表示

2.6.1剧本组成(4)场景

场景1进入餐厅

(a)用户走入餐厅。(b)寻找桌子。

(c)在桌子旁坐下。

场景2点菜

(a)服务员给用户菜单。(b)用户点菜。

(c)用户把菜单还给服务员。(d)用户等候服务员送菜。场景3等候

(a)服务员把用户所点菜告诉厨师。(b)厨师做菜。场景4吃菜

(a)厨师把做好菜给服务员。(b)服务员给用户送菜。

(c)用户吃菜。

场景5离开

(a)服务员拿来帐单。(b)用户付钱给服务员。

(c)用户离开餐厅。

人工智能及其应用知识第78页2.6剧本(script)表示

2.6.1剧本组成

(5)结果

(a)用户吃了饭，不饿了。(b)用户花了钱。

(c)老板挣了钱。(d)餐厅食品少了。人工智能及其应用知识第79页2.6剧本(script)表示

2.6.2剧本推理

剧本是有用知识表示结构，因为在现实世界中事件发生某种模式来自事件之间因果关系。事件中主人公完成一个动作后才能完成另一个动作。剧本中所描述事件形成一个巨大因果链，这个链起点是一组开场条件，满足这些开场条件，剧本中事件才能产生。链终点是一组结果，有了这组结果，以后事件或事件序列(可能用其它剧原来描述)才能发生。在这个链内一件事情和前后事情都相互联络。前面事件，使当前事件有可能产生，而当前事件又使后面事件有可能产生。人工智能及其应用知识第80页2.6剧本(script)表示

2.6.2剧本推理

如已知某一剧本适合用于所给定情形，剧本在预言一些没有直接提到事件方面尤其有用。同时剧本对表示已经提到事件之间关系也很有用。比如，要表示某人点了炖牛肉这道菜和此人吃牛肉之间是什么联络，就能够利用剧本。但在应用某一剧本以前，必须先准备好剧本，也就是先要确定这个剧本适合用于当前情形。依据剧本主要性，能够有二种准备剧本方法。

(1)对于不属于事件关键部分剧本，只需设置指向该剧本指针即可，方便当它成为关键时启用，如对于餐厅剧本，在下述事件中应采取这种方法：

苏珊在去博物馆路上经过她喜欢餐厅。她非常喜欢这次毕加索作品展览会。

(2)对于符合事件关键部分剧本，则应使用在当前事件中包括到详细对象和人物去填写剧本槽。剧本前提、道具、角色和事件等常能起到启用剧本指示器作用。

一旦剧本被启用，则能够应用它来进行推理。其中最主要是利用剧本能够预测没有显著提及事件发生。

人工智能及其应用知识第81页2.6剧本(script)表示

2.6.2剧本推理

比如，对于以下情节：

"昨晚，约翰到了餐厅。他订了牛排。当他要付款时发觉钱已用光。因为开始下雨了，所以他赶快回家了"。

假如有些人提问：

"昨晚，约翰吃饭了吗?"

即使在上面情节中并没有提到约翰吃没吃饭问题，但借助于餐厅剧本，能够回答：“他吃了。”这是因为启用了餐厅剧本，情节中全部事件与剧本中所预测事件序列相对应，因而能够推断出整个事件正常进行时所得出结果。

不过，一旦一个经典事件被中止，也就是给定情节中某个事件与剧本中事件不能对应时，则剧本便不能预测被中止以后事件了。人工智能及其应用知识第82页2.6剧本(script)表示

2.7.2剧本推理

比如以下情节：

“约翰走进餐厅。他被带到餐桌旁。订了一大块牛排之后，他坐在那儿等了许久。于是，他生气地走了。”

该情节中，因为要久等，所以约翰走了，这一事件改变了餐厅剧本中所预测事件序列，因而被中止了，这时就不能推断约翰是否付了帐等情节，但依然能够推断出他看了菜单，这是因为看菜单事件发生在中止之前。从该例也能够看出，利用剧本能够将事情注意力集中在“因为久等，约翰生气了”这么一些特殊事件发生上。

剧本结构，比起框架这么一些通用结构来，要呆板得多，知识表示范围也很窄，所以不适合用于表示各种知识，但对于表示预先构思好特定知识，如了解故事情节等，是非常有效。人工智能及其应用知识第83页2.7过程(procedure)表示

过程式表示就是将相关某一问题领域知识，连同怎样使用这些知识方法，均隐式地表示为一个求解问题过程。过程式不像陈说式那样含有固定形式，怎样描述知识完全取决于详细问题。下面以八数码问题为例，给出一个求解该问题过程式描述。

我们用一个3×3方格阵来表示该问题一个状态，为叙述上方便，我们用a～i来标识这9个方格，如图2.38(a)所表示。问题目标状态设定为图2.38(b)。当任意给定一初始状态后，求解该问题过程以下：

图2.38状态描述及其目标状态人工智能及其应用知识第84页2.7过程(procedure)表示

(1)首先移动棋牌，使得棋子1和空格均不在位置c上。

(2)依次移动棋牌，使得空格位置沿图2.39(a)所表示箭头方向移动，直到棋子1位于a为止。

(3)依次移动将牌，使得空格位置沿图2.39(b)所表示箭头方向移动，直到数码2位于b为止。若这时刚好数码3在位置c，则转(6)。图2.39空格移动方向示意图

人工智能及其应用知识第85页2.7过程(procedure)表示

(4)依次移动将牌，使得空格位置沿图2.39(c)所表示箭头方向移动，直到数码3位于e为止。这时空格刚好在位置d。

经过以上4步，得到状态如图2.40(a)所表示。其中"×"表示除空格以外任何将牌。

(5)依次移动将牌，使得空格位置沿图2.39(d)所表示箭头方向移动，直到空格又回到了d为止。此时状态如图2.40(b)所表示。

(6)依次移动将牌，使得空格位置沿图2.39(e)所表示箭头方向移动，直到数码4在位置f为止。若这时刚好数码5在位置i则转(9)。人工智能及其应用知识第86页2.7过程(procedure)表示

(7)依次移动将牌，使得空格位置沿图2.39(f)所表示箭头方向移动，直到数码5位于e为止。这时空格刚好在位置d。

(8)依次移动将牌，使得空格位置沿图2.39(g)所表示箭头方向移动，直到空格又回到位置d为止。

(9)依次移动将牌，使得空格位置沿图2.39(h)所表示箭头方向移动，直到数码6在位置h为止，若这时数码7、8分别在位置g和d，则问题得解，不然，说明由所给初始状态达不到所要求目标状态。

人工智能及其应用知识第87页2.7过程(procedure)表示

图2.41给出了应用以上过程求解一个详细八数码问题例子，其中(1)～(9)9个状态分别对应了以上过程(1)～(9)9个步骤结束时所到达状态。

从图2.41能够看出，这么得到解路显然不是最正确，但是按这么一个过程编写计算机程序具有非常高求解效率.

人工智能及其应用知识第88页2.8小结本章所讨论知识表示问题是人工智能研究关键问题之一。知识表示方法很多，本章介绍了其中7种，有图示法和公式法，陈说式表示和过程式表示等。

状态空间法是一个基于解答空间问题表示和求解方法，它是以状态和操作符为基础。在利用状态空间图表示时，我们从某个初始状态开始，每次加一个操作符，递增地建立起操作符试验序列，直到抵达目标状态为止。因为状态空间法需要扩展过多节点，轻易出现"组合爆炸"，因而只适合用于表示比较简单问题。

问题归约法从目标(要处理问题)出发，逆向推理，经过一系列变换把初始问题变换为子问题集合和子-子问题集合，直至最终归约为一个平凡本原问题集合。这些本原问题解能够直接得到从而处理了初始问题，用与或图来有效地说明问题归约法求解路径。

人工智能及其应用知识第89页2.8小结人工智能及其应用知识第90页2.8小结

谓词逻辑法采取谓词适当公式和一阶谓词演算把要处理问题变为一个有待证实问题，然后采取消解定理和消解反演来证实一个新语句是从已知正确语句导出，从而证实这个新语句也是正确。

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

框架是一个结构化表示方法。框架通常由指定事物各个方面槽组成，每个槽拥有若干个侧面，而每个侧面又可拥有若干个值。大多数实用系统必须同时使用许多框架，并可把它们联成一个框架系统。

剧本是框架一个特殊形式，它使用一组槽来描述事件