人工智能及其应用知识

第二章知识表示

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

掌握状态空间法、问题归约法、谓词演算法、语义网络法的要点及其之间的关系，了解框架表示、本体技术、过程表示。知识表示的基本概念

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

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

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

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

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

2.状态空间法三要点

(1)状态（state）(2)算符（operator）(3)状态空间方法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)。2.1状态空间法2.状态空间表示详释

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

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

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

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

1.图论中的几个术语

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

有向图(directedgraph)：一对节点用弧线连接起来，从一个节点指向另一个节点。后继节点(descendantnode)与父辈节点(parentnode)：如果某条弧线从节点ni指向节点nj，那么节点nj就叫做节点ni的后继节点或后裔，而节点ni叫做节点nj的父辈节点或祖先。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}作为起始节点是已知的。后继节点算符Γ也是已知的，它能作用于任一节点以产生该节点的全部后继节点和各连接弧线的代价。2.1状状态空空间法法状状态图图示法法2.图图的显显式和和隐式式表示示一一个个图可可由显显式说说明也也可由由隐式式说明明。显显然，，显式式说明明对于于大型型的图图是不不切实实际的的，而而对于于具有有无限限节点点集合合的图图则是是不可可能的的。此此外外，引引入后后继节节点算算符的的概念念是方方便的的。后后继节节点算算符ΓΓ也是是已知知的，，它能能作用用于任任一节节点以以产生生该节节点的的全部部后继继节点点和各各连接接弧线线的代代价把把后继继算符符应用用于{si}的的成员员和它它们的的后继继节点点以及及这些些后继继节点点的后后继节节点，，如此此无限限制地地进行行下去去，最最后使使得由由Γ和和{si}所规规定的的隐式式图变变为显显示图图。问题的的表示示对求求解工工作量量有很很大的的影响响。人人们显显然希希望有有较小小的状状态空空间表表示。。许多多似乎乎很难难的问问题，，当表表示适适当时时就可可能具具有小小而简简单的的状态态空间间。2.1状状态空空间法法状状态图图示法法根据问问题状状态、、操作作符和和目标标条件件选择择各种种表示示，是是高效效率问问题求求解必必须的的。各种问问题都都可以以用状状态空空间加加以表表示，，并用用状态态空间间搜索索法来来求解解。2.1状状态空空间法法状状态图图示法法1.产产生式式系统统（ProductionSystem））·一个总总数据据库(globaldatabase)：它含含有与与具体体任务务有关关的信信息；；随着着应用用情况况的不不同，，这些些数据据库可可能小小得像像数字字矩阵阵那样样简单单，或或许大大得如如检索索文件件结构构那么么复杂杂。·一套规规则：它对对数据据库进进行操操作运运算。。每条条规则则由左左右两两部分分组成成，左左部鉴鉴别规规则的的适用用性或或先决决条件件，右右部描描述规规则应应用时时所完完成的的动作作。用用规则则来改改变数数据库库就象象用算算符来来改变变状态态一样样。·一个控控制策策略：它确确定应应该采采用哪哪一条条适用用规则则，而而且当当数据据库的的终止止条件件满足足时，，就停停止计计算。。控制制策略略由控控制系系统选选择和和确定定。推销员员旅行行问题题总数据据库：：到目目前为为止所所访问问的城城市；；规则对对应于于决策策：即即下一一步走走向城城市ＡＡ，下下一步步走向向城市市Ｂ，，…，，下一一步走走向城城市ＥＥ，一一条规规则必必须能能把某某个数数据库库变为为一个个合法法数据据库，，否则则不适适应这这个数数据库库；任一以以Ａ为为起点点和终终点，，并出出现所所有其其它城城市的的总数数据库库，都都满足足终止止条件件．2.1状状态空空间法法状状态图图示法法2.状状态空空间表表示举举例例2猴猴子子和香香蕉问问题(monkeyandbananaproblem)在在一个个房间间内有有一只只猴子子(可可把这这只猴猴子看看做一一个机机器人人)、、一个个箱子子和一一束香香蕉。。香蕉蕉挂在在天花花板下下方，，但猴猴子的的高度度不足足以碰碰到它它。那那么这这只猴猴子怎怎样才才能摘摘到香香蕉呢呢?图图2.4表表示出出猴子子、香香蕉和和箱子子在房房间内内的相相对位位置。。猴子和和香蕉蕉...用一个个四元元表列列(W,X,Y,Z)来来表示示这个个问题题的状态态，其其中中W－－猴子子的水水平位位置X－当当猴子子在箱箱子顶顶上时时取X=1；否否则取取X=0Y－－箱子子的水水平位位置Z－当当猴子子摘到到香蕉蕉时取取Z=1；；否则则取Z=0图2.4猴猴子和和香蕉蕉问题题2.1状状态空空间法法状状态图图示法法这个问问题中中的操操作(算符符)如如下：：(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)，，就要求求产生生式规规则的的左边边，猴猴子与与箱子子必须须在同同一位位置上上，并并且，，猴子子不是是在箱箱子顶顶上。。这种种强加加于操操作的的适用用性条条件，，叫做做产生生式规规则的的先决决条件件。2.1状状态空空间法法状状态图图示法法这个问问题中中的操操作(算符符)如如下：：(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上上，并并且猴猴子已已在箱箱子顶顶上。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)。。猴子子和和香香蕉蕉问问题题的的状状态态空空间间图图2.2问问题题归归约约法法问问题题归归约约描描述述先把把问问题题分分解解为为子子问问题题和和子子-子子问问题题，，然然后后解解决决较较小小的的问问题题。。对对该该问问题题的的某某个个具具体体子子集集的的解解答答就就意意味味着着对对原原始始问问题题的的一一个个解解答答。。问问题题归归约约表表示示的的组组成成部部分分：：一个个初初始始问问题题描描述述；；一套套把把问问题题变变换换为为子子问问题题的的操操作作符符；；一套套本本原原问问题题描描述述。。问题题归归约约的的实实质质：：从从目目标标(要要解解决决的的问问题题)出出发发逆逆向向推推理理，，建建立立子子问问题题以以及及子子问问题题的的子子问问题题，，直直至至最最后后把把初初始始问问题题归归约约为为一一个个平平凡凡的的本本原原问问题题集集合合。。2.2问问题题归归约约法法问问题题归归约约描描述述１梵梵塔塔难难题题有3个个柱柱子子(1，，2和和3)和和3个个不不同同尺尺寸寸的的圆圆盘盘（（A，，B和和C））。。在在每每个个圆圆盘盘的的中中心心有有一一个个孔孔，，所所以以圆圆盘盘可可以以堆堆叠叠在在柱柱子子上上。。最最初初，，3个个圆圆盘盘都都堆堆在在柱柱子子1上上：：最最大大的的圆圆盘盘C在在底底部部，，最最小小的的圆圆盘盘A在在顶顶部部。。要要求求把把所所有有圆圆盘盘都都移移到到柱柱子子3上上，，每每次次只只许许移移动动一一个个，，而而且且只只能能先先搬搬动动柱柱子子顶顶部部的的圆圆盘盘，，还还不不许许把把尺尺寸寸较较大大的的圆圆盘盘堆堆放放在在尺尺寸寸较较小小的的圆圆盘盘上上。。这这个个问问题题的的初初始始配配置置和和目目标标配配置置如如图图2.6所所示示。。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)所示示。2.2问问题归归约法图2.7梵梵塔问题题解答(a)图2.8梵梵塔问题题解答(b)图2.9梵梵塔问题题解答(c)2.2问问题归归约法梵塔问题题归约图图：子问问题2可可作为本本原问题题考虑，，因为它它的解只只包含一一步移动动。应用用一系列列相似的的推理，，子问题题1和子子问题3也可被被归约为为本原问问题，如如图2.10所所示。这这种图式式结构，，叫做与与或图(AND/ORgraph)。它它能有有效地说说明如何何由问题题归约法法求得问问题的解解答。梵塔问题题归约图图2.2问问题归归约法问问题归约约描述２问题归约约描述问题归约约方法应应用算符符把问题题描述变变换为子子问题描描述，问问题描述述可以用用多种数数据结构构形式，，包括表表列、树树、字符符串、矢矢量、数数组等。。梵塔问问题采用用包含两两个数列列的表列列来描述述,[(113),（（333)]表表示把配配置（113））变换为为配置（（333）。用状态空空间表示示的三元元组合（（S，F，G））来规定定与描述述问题，，有关子子问题可可以当作作状态空空间中的的两个一一定的““脚踏石石”之间间寻找路路径来辨辨别。梵梵塔问题题中的子子问题[（111）=>（122））]，[（122））=>（（322）]，，[（（322）=>（333）]，规定定了最后后的路径径将要通通过“脚脚踏石””状态（（122）和（（322）。2.2问问题归归约法与与或图表表示与图、或或图、与与或图：：一般地，，我们用用一个类类似图的的结构来来表示把把问题归归约为后后继问题题的替换换集合，，这种结结构图叫叫做问题题归约图图，或叫叫与或图图。如下下图所示示:（引入附附加节点点使含有有一个以以上后继继问题的的每个集集合能够够聚集在在它们各各自的父父辈节点点之下。。）子问题替替换集合合结构图图与或图2.2问问题归归约法问问题归约约描述一些关于于与或图图的术语语：终叶节点点：对应于原原问题的的本原节节点。或节点：只要解决决某个问问题就可可解决其其父辈问问题的节节点集合合，如（（M，N，H））。与节点：只有解决决所有子子问题，，才能解解决其父父辈问题题的节点点集合，，如（B,C)和（D,E,F）各各个结点点之间用用一端小小圆弧连连接标记记。2.2问问题归归约法问问题归约约描述与或图：由与节点点及或节节点组成成的结构构图。可解节点点的一般般定义：：(1)终叶节点点是可解解节点(因为它它们与本原原问题相相关连)。(2)如如果某某个非终终叶节点点含有或或后继节点，，那么只只要当其其后继节节点至少有一一个是可可解的时时，此非非终叶节点才才是可解解的。(3)如如果某某个非终终叶节点点含有与与后继节点点，那么么只有当当其后继继节点全部为为可解时时，此非非终叶节节点才是可解解的。图2.15与与或图图例子2.2问问题归归约法2.2.2问题题归约描描述不可解节节点的一一般定义义:(1)没没有后后裔的非非终叶节节点为不不可解节节点。(2)如如果某某个非终终叶节点点含有或或后继节节点，那那么只有有当其全全部后裔裔为不可可解时，，此非终终叶节点点才是不不可解的的。(3)如如果某某个非终终叶节点点含有与与后继节节点，那那么只要要当其后后裔至少少有一个个为不可可解时，，此非终终叶节点点才是不不可解的的。2.2问问题归归约法问问题归约约描述与或图构构成规则则(1)与或或图中的的每个节节点代表表一个要要解决的的单一问问题或问问题集合合。图中中所含起起始节点点对应于于原始问问题。(2)对对应于于本原问问题的节节点，叫叫做终叶叶节点，，它没有有后裔。。(3)对对于把把算符应应用于问问题A的的每种可可能情况况，都把把问题变变换为一一个子问问题集合合；有向向弧线自自A指指向后继继节点表表示所求求得的子子问题集合合，如下下图所示示，把问问题A归归约为3个不同同的子问题题集合N，M，，H(或或节点)。图2.16与与或树树2.2问问题归归约法问问题归约约描述与或图构构成规则则(4)一一般对对于代表表两个或或两个以以上子问问题集合合的每个个节点，，有向弧弧线从此此节点指指向此子子问题集集合中的的各个节节点。由由于只有有当集合合中所有有的项都都有解时时，这个个子问题题的集合合才能获获得解答答，所以以这些子子问题节节点叫做做与节点点。(5)在在特殊殊情况下下，当只只有一个个算符可可应用于于问题A，而且且这个算算符产生生具有一一个以上上子问题题的某个个集合时时，由上上述规则则3和规则则4所产产生的图图可以得得到简化化。因此，代代表子问问题集合合的中间间或节点可以被被略去，，如右图图所示。。图2.16与与或树树2.3谓词逻辑辑法谓谓词演算算（PredicateCalculus）1.语法法和语义义(Syntax&Semantics)谓词逻辑辑的基本本组成部部分：谓谓词符号号、变量量符号、、函数符符号和常常量符号号，并用用圆括号号、方括括号、花花括号和和逗号隔隔开，表表示论域域内的关关系。原子公式式(atomicformulas)由由若干谓谓词符号号和项组组成的谓谓词演算算。原子子公式是是谓词演演算基本本积木块块。例如，要要表示＂＂机器人人(ROBOT)在１１号房间间(r1)内＂＂，如图图2.19所示示，可以以应用原原子公式式:2.3谓词逻辑辑法谓谓词演算算（PredicateCalculus）1.语法法和语义义(Syntax&Semantics)当机器人人ROBOT移移到房间间r2时时，原子子公式可可以表示示为：INROOM(ROBOT,r2)这两个原原子公式式的通用用形式就就是又如,““李的母母亲和他他的父亲亲结婚””这句话话的原子子公式表表示如下：2.3谓词逻辑辑法谓谓词演算算（PredicateCalculus）2.连连词和量量词(Connective&Quantifiers)(1)连连词与与·合取取（conjunction）合合取就是是用连词词∧把几几个公式式连接起起来而构构成的公公式。合合取项是是合取式式的每个个组成部部分。例：LIKE(I，MUSIC)∧∧LIKE(I，PAINTING)(我喜爱爱音乐和和绘画。。)2.3谓词逻辑辑法谓谓词演算算（PredicateCalculus）2.连连词和量量词(Connective&Quantifiers)或·析取取（disjunction）析析取就是是用连词词∨把几几个公式式连接起起来而构构成的公公式。析析取项是是析取式式的每个个组成部部分。例：PLAYS(LILI，，BASKETBALL)∨∨PLAYS(LILI，FOOTBALL)(李力打打篮球或或踢足球球。)2.3谓词逻辑辑法谓谓词演算算（PredicateCalculus）2.连词词和量词词(Connective&Quantifiers)(1)连连词蕴蕴涵"=>"表示"如果-那么"的语句句。用连连词=>连接两两个公式式所构成成的公式式叫做蕴蕴涵。IF=>THEN前项后后项(左式)(右式)例：RUNS(LIUHUA，FASTEST)=>TWINS(LIUHUA，CHAMPION)(如果刘刘华跑得得最快，，那么他他取得冠冠军)非（NOT）表表示否否定，～～、┑均均可表示示否定。。例：～INROOM(ROBOT，，r2)(机器人人不在2号房间间内。)2.3谓词逻辑辑法谓谓词演算算（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)](所有学生都都穿彩色制服服)2.3谓词逻辑法谓谓词演算（（PredicateCalculus）2.连词和量量词(Connective&Quantifiers)(2)量词词存在量词(ExistentialQuantifier)若若一个原原子公式P(x)，至少少有一个变元元X，可使P(X)为T值，则用(x)P(x)表示示。例：(x)INROOM(x,r1)(1号房间内内有个物体)量化变元(QuantifiedVariables)被量化了了的变元x-约束变量。。2.3谓词逻辑法谓谓词公式（（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)求得的的那些公式，，才是合适公公式。2.3谓词逻辑法谓谓词公式（（PredicateFormulas）1.谓词公式式的定义例题："对于所有的的x，如果x是整数，则则x或为正的的或者为负的的。"(x)(I(x)=>(P(x)∨N(x)))I(x)表示示"x是整数数"，P(x)表示"x是正数"，，N(x)表表示"x是负负数"。2.3谓词逻辑法谓谓词公式（（PredicateFormulas）2.合适公式式的性质合适公式的真真值：p36表2-1真真值表2.3谓词逻辑法置置换与合一一（Substitution&Unification）1.置换在谓词逻辑中中，有些推理理规则可应用用于一定的合合适公式和合合适公式集，，以产生新的的合适公式。。一个重要的的推理规则是是假元推理，，这就是由合合适公式W1和W1=>W2产生合合适公式W2的运算。另另一个推理规规则叫做全称称化推理，它它是由合适公公式(x)W(x)产生合适公公式W(A)，其中A为为任意常量符符号。假假元推理：：全称化推理：：综合推理：2.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]2.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}是可合一一的。2.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}2.4语义义网络法语义网络是1968年Quilian在研究人人类联想记忆忆时提出的心心理学模型，，认为记忆是是由概念间的的联系来实现现的。1972年，Simmons首先将语义义网络表示法法用于自然语语言理解系统统。语语义网络的结结构：语义网网络是知识的的一种图解表示，它由节点和和弧线或链线线组成。节点点用于表示实实体、概念和和情况等，弧弧线用于表示示节点间的关关系。组成部部分:1词法部部分：决定表表示词汇表中中允许有哪些些符号，它涉涉及各个节点点和弧线。2结构部部分：叙述符符号排列的约约束条件，指指定各弧线连连接的节点对对。3过程部部分：说明访访问过程，这这些过程能用用来建立和修修正描述，以以及回答相关关问题。4语义部部分：确定与与描述相关的的(联想)意意义的方法即即确定有关节节点的排列及及其占有物和和对应弧线。。2.4语义义网络法二二元语义网网络的表示(RepresentationofTwo-ElementSemanticNetwork)1.表示简单单的事实例1.所有有的燕子都是是鸟2.4语义义网络法二二元语义网网络的表示(RepresentationofTwo-ElementSemanticNetwork)2.表示占有有关系和其它它情况P40例2.小燕燕是一只燕子子，燕子是鸟鸟；巢-1是是小燕的巢，，巢-1是巢巢中的一个。。3.选择语义义基元试图用一组基基元来表示知知识，以便简简化表示，并并可用简单的的知识来表示示更复杂的知知识。2.4语义义网络法例3.我椅子子的颜色是咖咖啡色的；椅椅子包套是皮皮革；椅子是是一种家具；；椅子是座位位的一部分；；椅子的所有有者是X；X是个人，如如下图所示：：2.4语义义网络法多多元语义网网络的表示语义网络是一一种网络结构构。节点之间间以链相连。。多元语义网网络表示的实实质：把多元元关系转化为为一组二元关关系的组合，，或二元关系系的合取。如如果所要表示示的知识是一一元关系，例例如，要表示示李明是一个个人，这在谓谓词逻辑中可可表示为MAN(LIMING)。。用语义网络络，这就可以以表示为:与这样的表示示法相等效的的关系在谓词词逻辑中表示示为ISA(LIMING，MAN)。这说明明语义网络可可以毫无困难难地表示一元元关系。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多元关系系的语义网络络表示2.4语义义网络法语语义网络的推推理过程在语义网络知知识表达方法法中，赋予网网络结构的含含义完全决定定于管理这个个网络的过程程的特性。为了便于以下下的叙述，对对所用符号作作进一步的规规定。区分在在链的头部和和在链的尾部部的节点，把把在链的尾部部的节点称为为值节点。另另外，我们还还规定节点的的槽相当于链链，不过取不不同的名字而而已。在图2.28中砖砖块12(BRICK12)有3个个链，构成两个槽。其其中一个槽只只有一个值，另外一个个槽有两个值值。我们说颜色槽(COLOR)填入红色(RED)，，ISA槽填入入了砖块(BRICK)和玩具(TOY)。。图2.28语义网络络的槽和数值值2.4语义义网络法语语义网络的推推理过程语义网络中的的推理过程主主要有两种:一种是继承承，另一种是是匹配。以下下我们分别介介绍这两种过过程。1.继承在语义网络中中所谓的继承承是把对事物物的描述从概概念节点或类类节点传递到到实例节点。。例如在图2.29上所所示的语义网网络中BRICK是概念念节点，BRICK12是一个实例例节点。BRICK节点点在SHAPE(外形)槽，其中填填入了RECTANGULAR(矩矩形)，说明明砖块的外形形是矩形的。。这个描述可可以通过ISA链传递给给实例节点BRICK12。因此，，虽然BRICK12节节点没有SHAPE槽，，但可以从这这个语义网络络推理出BRICK12的外形是是矩形的。图2.29语义网络络的值继承2.4语义义网络法语语义网络的推推理过程1.继承这种推理过程程，类似于人人的思维过程程。一旦知道道了某种事物物的身份以后后，可以联想想起很多关于于这件事物的的一般描述。。例如，我们通通常认为鲸鱼鱼很大，鸟比比较小，城堡堡很古老，运运动员很健壮壮。这就像我我们用每种事事物的典型情情况来描述各各种事物--鲸鱼、鸟、、城堡和运动动员--那那样。一一共有3种种继承过程：：值继承、"如果需要"继承和"默默认"继承。。2.4语语义网络法法2.4.3语义网络络的推理过过程语义网络中中的推理过过程主要有有两种:一一种是继承承，另一种种是匹配。。以下我们们分别介绍绍这两种过过程。1.继承(1)值值继承除了ISA链以外，，另外还有有一种AKO(是某某种)链也也可被用于于语义网络络中的描述述或特性的的继承。AKO是是A-KIND-OF的缩写写。总总之，ISA和AKO链直直接地表示示类的成员员关系以及及子类和类类之间的关关系，提供供了一种把把知识从某某一层传递递到另一层层的途径。。为为了能利用用语义网络络的继承特特性进行推推理我们还还需要一个个搜索程序序用来在合合适的节点点寻找合适适的槽。2.4语语义网络法法2.4.3语义网络络的推理过过程1.继承(2)““如果需要要”继承在某些情况况下，当我我们不知道道槽值时，，可以利用用已知信息息来计算。。例如，我我们可以根根据体积和和物质的密密度来计算算积木的重重量。进行行上述计算算的程序称称为if-needed(如如果需要)程序。为了储存进进行上述计计算的程序序，我们需需要改进节节点槽值的的结构，允允许槽有几几种类型的的值，而不不只是一个个类型。为为此，每个个槽又可以以有若干个个侧面，以以储存这些些不同类型型的值。这这样，以前前我们讨论论的原始意意义上的值值就放“值值侧面”中中，if-needed程序序，存放在在IF-NEEDED侧面中中。例如在图2.30(a)中，，一个重量量确定程序序存放在BLOCK节点的WEIGHT槽的IF-NEEDED侧面中。。图2.30语义义网络的"如果需要要"继承2.4语语义网络法法2.4.3语义网络络的推理过过程1.继承(3)““缺省”继继承某些情况下下，当我们们对事物所所作的假设设不是十分分有把握时时，最好对对所作的假假设加上““可能”这这样的字眼眼。例如，，我们可以以认为法官官可能是诚诚实的，但但不一定是是；或认为为宝石可能能是很昂贵贵的，但不不一定是。。我们把这种种具有相当程程度的真实性，但又又不能十分分肯定的值值称为“缺省”值值。这种类型型的值被放放入槽的DEFAULT(缺省)侧侧面中.例如，在图图2.31中，网络络所表示的的含义是：从从整体来说说，积木的的颜色很可能是蓝蓝色的，但但在砖块中中，颜色可能是红红的。对BLOCK和BRICK节点来说说，在COLOR槽槽中找到的的侧面都是DEFAULT侧面面，在图中中以括弧加以以标志图2.31语义义网络的"缺省"继继承2.4语语义网络法法2.4.3语义网络络的推理过过程2.匹配至今我们所所讨论的是是类节点和和实例节点点，例如BRICK和BRICK12之间的继继承值。现现在我们转转向讨论更更为困难一一些的问题题。当解决决涉及由几几部分组成成的事物时时，如图2.32中中的玩具房房(TOY-HOUSE)和和玩具房-77(TOY-HOUSE77)，，继承过程程将如何进进行。我们们不仅必须须制定如何何把值从玩玩具房传递递到玩具房房-77的的路径，而而且必须制制定把值从从玩具房部部件传递到到玩具房-77部件件的路径。。例如，很明明显，由于于TOY-HOUSE77是是TOY-HOUSE的一个个实例，所所以它必须须有两个部部件，一一个是砖块块，另一个个是楔块(wedge)。另另外，作为为玩具房的的一个部件件的砖块必必须支撑楔楔块。在图图2.32中，玩具具房-77部件以及及它们之间间的链，都都用虚线画画的节点的的箭头来表表示。因为为这些知识识是通过继继承而间接接知道的，，并不是通通过实际的的节点和链链直接知道道的。因此此，我们说说虚线所表表示的节点点和箭头表表示的链是是虚节点和和虚链。图2.32虚节节点和虚链链图2.32虚节节点和虚链链没有必要从从TOYHOUSE节点把把这些节点点和链复制制到TOY-HOUSE77节点去，，除非我们们需要在这这些复制节节点加上玩玩具房-77所特有有的信息。。例如，如果果我们要表表示玩具房房-77的的砖块的颜颜色是红的的，就必须须为TOY-HOUSE77建立一个个BRICK节点，，并把RED放在这这个BRICK节点点的COLOR槽中中。假设我我们把RED放在作作为玩具房房部件的BRICK节点的COLOR槽中，这这将意味着着所有玩具具房的砖都都是红色的的，而不是是只在由玩玩具房-77所描述述的特定房房子中的砖砖是红色的的。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部件件匹配2.5框框架表示法法心理学的研研究结果表表明，在人人类日常的的思维和理理解活动中中，当分析析和解释遇遇到的新情情况时，要要使用到过过去经验中中积累的知知识。这些些知识规模模巨大而且且以很好的的组织形式式保留在人人们的记忆忆中。例如如:当我们走进进一家从来来没来过的的饭店时，，根据以往往的经验，，可以预见见在这家饭饭店我们将将会看到菜菜单、桌子子、服务员员等等。当我们走进进教室时，，可以预见见在教室里里可以看到到椅子、黑黑板等等。。我们试图用用以往的经经验来分析析解释当前前所遇到的的情况。2.5框框架表示法法当然，我们们无法把过过去的经验验一一都存存在脑子里里，而只能能以一个通通用的数据据结构的形形式存储以以往的经验验。这样的的数据结构构称为框架架。框架提提供了一个个结构，一一种组织。。在这个结结构或组织织中，新的的资料可以以用从过去去的经验中中得到的概概念来分析析和解释。。因此，框框架是一种种结构化表表示法。通常框架采采用语义网网络中的节节点-槽-值表示结结构。所以以框架也可可以定义为为是一组语语义网络的的节点和槽槽，这组节节点和槽可可以描述格格式固定的的事物、行行动和事件件。语义网网络可看做做节点和弧弧线的集合合，也可以以视为框架架的集合。。2.5框框架表示法法2.5.1框架的构构成框架通常由由描述事物物的各个方方面的槽组组成，每个个槽可以拥拥有若干个个侧面，而而每个侧面面又可以拥拥有若干个个值。这些些内容可以以根据具体体问题的具具体需要来来取舍，一一个框架的的一般结构构如下：<框架架名><槽1><侧面11><值111>……<侧面12><值值121>……<槽2><侧面21><值值211>…

………

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

<侧侧面nm><值nm1>…2.5框框架表示法法2.5.1框架的构构成较简单的情情景是用框框架来表示示诸如人和和房子等事事物。例如如，一个人人可以用其其职业、身身高和体重重等项描述述，因而可可以用这些些项目组成成框架的槽槽。当描述述一个具体体的人时，，再用这些些项目的具具体值填入入到相应的的槽中。表表2.3给给出的是描描述John的框架架。对对于大多多数问题，，不能这样样简单地用用一个框架架表示出来来，必须同同时使用许许多框架,组成一个个框架系统统。表2.3简简单单框框架架示示例例JOHN的的描描述述框框架架2.5框框架架表表示示法法一个个框框架架系系统统图2.32所所示示的的就就是是表表示示立立方方体体的的一一个个视视图图的的框框架架。。图图中中，，最最高高层层的的框框架架，，用用isa槽槽说说明明它它是是一一个个立立方方体体，，并并由由region槽槽指指示示出出它它所所拥拥有有的的3个个可可见见面面A、、B、、E。。而而A、、B、、E又又分分别别用用3个个框框架架来来具具体体描描述述。。用用mustbe槽槽指指示示出出它它们们必必须须是是一一个个平平行行四四边边形形。。图2.32一一个个立立体体视视图图的的框框架架表表示示2.5框框架架表表示示法法一个个框框架架系系统统为了了能能从从各各个个不不同同的的角角度度来来描描述述物物体体，，可可以以对对不不同同角角度度的的视视图图分分别别建建立立框框架架，，然然后后再再把把它它们们联联系系起起来来组组成成一一个个框框架架系系统统。。图图2.35所所示示的的就就是是从从3个个不不同同的的角角度度来来研研究究一一个个立立方方体体的的例例子子。。为为了了简简便便起起见见，，图图中中略略去去了了一一些些细细节节，，在在表表示示立立方方体体表表面面的的槽槽中中，，用用实实线线与与可可见见面面连连接接，，用用虚虚线线与与不不可可见见面面连连接接。。图2.35表表示示立立方方体体的的框框架架系系统统2.5框框架架表表示示法法以下下是是另另一一个个框框架架系系统统的的例例子子"今今天天一一次次强强度度为为里里氏氏8.5级级的的强强烈烈地地震震袭袭击击了了下下斯斯洛洛文文尼尼亚亚(LowSlabovia)地地区区，，造造成成25人人死死亡亡和和5亿亿美美元元的的财财产产损损失失。。下下斯斯洛洛文文尼尼亚亚地地区区主主席席说说，，多多年年来来，，靠靠近近萨萨迪迪豪豪金金斯斯断断层层的的重重灾灾区区一一直直是是一一个个危危险险地地区区。。可可以以用用图图2.36中中虚虚线线部部分分所所示示的的EARTHQUAKE13框框架架来来表表示示这这一一新新闻闻。。图2.36表表示灾灾害事件件的框架架系统图中在链链上标明明的地点点(place)、日日期(day)、伤亡亡(fatalities)、损失失(damage)、、震级(magnitude)、、断层(fault)是槽的的名称。。在节点点中填入入相应的的填充值值。这这个个框架可可以发展展成框架架系统，，以描述述更复杂杂更广泛泛的事件件。例如如，向上上移动一一层的话话，可以以把地震震看成是是一种灾灾害事件件(disasterevent)，除除此之外外还可以以有洪水水(flood)、飓飓风(huricane)等等灾害事事件、它它们组成成一个DISASTEREVENT的基本本框架。。如向下下移动一一层，在在每个槽槽中也可可以填入入一个框框架。例例如FATALITIES、、也可以以用一个个框架来来描述。。2.5框框架表表示法显而易见见，这种种框架系系统具有有树状结结构。树树状结构构框架系系统的每每个节点点具有如如下框架架结构形形式：框架名AKOVALUE<值>PROPDEFAULT<表1>SFIF-NEEDED<算术表表达式>CONFLICTADD<表2>其中框架架名用类类名表示示。AKO是一一个槽，，VALUE是是它的侧侧面，通通过填写写<值>的内容容表示出出该框架架属于哪哪一类。。PROP槽用用来记录录该节点点所具有有的特性性，其侧侧面DEFAULT表表示该槽槽的内容容是可以以进行缺缺省继承承的，即即当<表表1>为为非NIL时，，PROP的槽槽值为<表1>，当<表1>为NIL时，，PROP的槽槽值用其其父节点点的PROP槽槽值来代代替。2.5框框架表表示法框框架的推推理框架是一一种复杂杂结构的的语义网网络。因因此语义义网络推推理中的的匹配和和特性继继承在框框架系统统中也可可以实行行。除此此以外，，由于框框架用于于描述具具有固定定格式的的事物、、动作和和事件，，因此可可以在新新的情况况下，推推论出未未被观察察到的事事实。框框架用以以下几种种途径来来帮助实实现这一一点：(1)框框架包包含它所所描述的的情况或或物体的的多方面面的信息息。这些些信息可可以被引引用，就就像已经经直接观观察到这这些信息息一样。。(2)框框架包包含物体体必须具具有的属属性。在在填充框框架的各各个槽时时，要用用到这些些属性。。(3)框框架描描述它们们所代表表的概念念的典型型事例。。如果某某一情况况在很多多方面和和一个框框架相匹匹配，只只有少部部分相互互之间存存在不同同之处。。这些不不同之处处很可能能对应于于当前情情况的重重要方面面，也许许应该对对这些不不同之处处作出解解答。因因此，如如果一个个椅子被被认为应应有4条条腿，而而某一椅椅子只有有3条腿腿，那么么或许这这把椅子子需要修修理。2.5框框架表表示法框框架的推推理用一个框框架来具具体体现现一个特特定情况况的过程程，经常常不是很很顺利的的。但当当这个过过程碰到到障碍时时，经常常不必放放弃原来来的努力力去从头头开始，，而是有有很多办办法可想想的：(1)选选择和和当前情情况相对对应的当当前的框框架片断断，并把把这个框框架片断断和候补补框架相相匹配。。选择最最佳匹配配。如果果当前的的框架，，总的来来说差不不多是可可以接受受的，则则许多已已经做的的，有关关建立子子结构以以填入这这个框架架的工作作将可保保留。(2)尽尽管当当前的框框架和要要描述的的情况之之间有不不相匹配配的地方方，但是是仍然可可以继续续应用这这个框架架。例如如，所研研究的只只有3条条腿的椅椅子，可可能是一一个破椅椅子或是是有另一一个在椅椅子前面面的物体体挡住了了一条腿腿。框架架的某一一部分包包含关于于哪些特特性是允允许不相相匹配的的信息。。同样的的，也有有一般的的启发性性原则，，比如一一个漏失失某项期期望特性性的框架架(可能能由于被被挡住视视线造成成的)比比另一个个多了某某一项不不应有的的特性的的框架更更适合当当前的情情况。举举例来说说，一个个人只有有一条腿腿比说一一个人有有3条腿腿或有尾尾巴更合合乎情理理些。2.5框框架表表示法框框架的推推理(3)查查询框框架之间间专门保保存的链链，以提提出应朝朝哪个方方向进行行试探的的建议。。这种链链的例子子与图2.35所示网网络相似似。例如如，如果果和CHAIR框架匹匹配时，，发现没没有靠背背，并且且太宽，，这时就就建议用用BENCH(条凳)框架；；如果太太高，并并且没有有靠背，，就建议议用STOOL(凳子子)框架架。图2.37相相似网网络2.5框框架表表示法框框架的推推理(4)沿沿着框框架系统统排列的的层次结结构向上上移动(即从狗狗框架→→哺乳动动物框架架→动物物框架)，直到到找到一一个足够够通用，，并不与与已有事事实矛盾盾的框架架。如果果框架足足够具体体，可以以提供所所要求的的知识，，那就采采用这个个框架。。或者建建立一个个新的、、正好在在匹配的的框架下下一层的的框架。。2.6剧剧本(script)表示示剧本是框框架的一一种特殊殊形式，，它用一一组槽来来描述某某些事件件的发生生序列，，就像剧剧本中的的事件序序列一样样，故称称为"剧剧本"。。剧剧本的构构成一个剧本本一般由由以下各各部分组组成：(1)开开场条条件给出在剧剧本中描描述的事事件发生生的前提提条件。。(2)角角色用来表示示在剧本本所描述述的事件件中可能能出现的的有关人人物的一一些槽。。(3)道道具