人工智能及其应用_知识表示

1、第二章 知识表示 本章主要讨论知识表示问题，介绍7种知识表示方法：状态空间法、问题归约法、谓词演算法、语义网络法、框架表示、本体技术、过程表示。掌握状态空间法、问题归约法、谓词演算法、语义网络法的要点及其之间的关系，了解框架表示、本体技术、过程表示。 知识表示的基本概念知识表示的基本概念 v知识表示：研究用机器表示知识的可行性、有效性的一般方法，是一种数据结构与控制结构的统一体，既考虑知识的存储又考虑知识的使用。v知识表示可看成是一组描述事物的约定，以把人类知识表示成机器能处理的数据结构。 人工智能系统所关心的知识人工智能系统所关心的知识v事实事实 有关问题环境的一些事物的知识，常以有关问题环

2、境的一些事物的知识，常以“是是”的形式出现。的形式出现。如事物的分类、属性、事物间关系、科学事实、客观事实等。如雪是白如事物的分类、属性、事物间关系、科学事实、客观事实等。如雪是白色的、鸟有翅膀、张三李四是好朋友、这辆车是张三的。色的、鸟有翅膀、张三李四是好朋友、这辆车是张三的。v规则规则 有关问题中与事物的行动、动作相联系的因果关系知识，是动态有关问题中与事物的行动、动作相联系的因果关系知识，是动态的，常以的，常以“如果如果那么那么”形式出现。形式出现。v控制控制 有关问题的求解步骤、技巧性知识，告诉怎么做一件事。有关问题的求解步骤、技巧性知识，告诉怎么做一件事。v元知识元知识 有关知识的知

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

4、基础来表示和求解问题的。 2.1 状态空间法状态空间法1.问题求解技术两个主要的方面问题求解技术两个主要的方面 (1) 问题的表示：如果描述方法不对，对问题求解会带来很大的困难；(2) 求解的方法：采用试探搜索方法。 2.状态空间法三要点状态空间法三要点 (1)状态（state）(2)算符（operator）(3)状态空间方法2.1 状态空间法状态空间法2.1.1 问题状态描述问题状态描述 1.定义定义 状态状态(state)(state)：为描述某类不同事物间的差别而引入的一组最少变量：为描述某类不同事物间的差别而引入的一组最少变量q q0 0，q q1 1，q qn n的有序集合，其矢量形

5、式如下：的有序集合，其矢量形式如下： Q=qQ=q0,0,q q1,1,q,qn n T T式中每个元素式中每个元素q qi i(i=0,1,n)(i=0,1,n)为集合的分量为集合的分量, ,称为状态变量称为状态变量, ,给定每个分量的一给定每个分量的一组值就得到一个具体的状态组值就得到一个具体的状态, ,如如 Q Qk k=q=q0k,0k,q q1k,1k,q,qnknk T T 式中每个元素式中每个元素q qi i(i=0,1(i=0,1，n)n)为集合的分量，称为状态变量。为集合的分量，称为状态变量。 算符算符：使问题从一种状态变化为另一种状态的手段称为操作符或算符。操：使问题从一种

6、状态变化为另一种状态的手段称为操作符或算符。操作符可为走步、过程、规则、数学算子、运算符号或逻辑符号等。作符可为走步、过程、规则、数学算子、运算符号或逻辑符号等。问题的状态空间问题的状态空间(state space)(state space)：是一个表示该问题全部可能状态及其关系：是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合，即所有可能的问题初始状态集合的图，它包含三种说明的集合，即所有可能的问题初始状态集合S S、操作符、操作符集合集合F F以及目标状态集合以及目标状态集合G G。可把状态空间记为三元状态。可把状态空间记为三元状态(S(S，F F，G)G)。2.1 状态空间

7、法状态空间法v2.状态空间表示详释状态空间表示详释让我们先用数码难题(puzzle problem)来说明状态空间表示的概念。由15个编有1至15并放在44方格棋盘上的可走动的棋子组成。棋盘上总有一格是空的，以便可能让空格周围的棋子走进空格，这也可以理解为移动空格。图中绘出了两种棋局，即初始棋局和目标棋局，它们对应于该下棋问题的初始状态和目标状态。如何把初始棋局变换为目标棋局呢？问题的解答就是某个合适的棋子走步序列，如左移棋子12，下移棋子15，右移棋子4，等等。2.1 状态空间法状态空间法v2.状态空间表示详释状态空间表示详释v状态空间法：从某个初始状态开始，每次加一个操作符，递增的建立起状

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

9、述方式，特别是初始状态描述；v操作符集合及其对状态描述的作用；操作符集合及其对状态描述的作用；v目标状态的特性。目标状态的特性。2.1 状态空间法状态空间法v2.1.2 状态图示法状态图示法 为了对状态空间图有更深入的了解，这里介绍一下图论中的几个术语和了对状态空间图有更深入的了解，这里介绍一下图论中的几个术语和图的正式表示法。图的正式表示法。1.图论中的几个术语图论中的几个术语节点节点(node)：图形上的汇合点，用来表示状态、事件和时间关系的汇合，也图形上的汇合点，用来表示状态、事件和时间关系的汇合，也可用来指示通路的汇合；可用来指示通路的汇合； 弧线弧线(arc)：节点间的连接线；节点间

10、的连接线； 有向图有向图(directed graph)：一对节点用弧线连接起来，从一个节点指向另一个一对节点用弧线连接起来，从一个节点指向另一个节点。节点。 后继节点后继节点(descendant node)与与父辈节点父辈节点(parent node)：如果某条弧线从节：如果某条弧线从节点点ni指向节点指向节点nj，那么节点，那么节点nj就叫做节点就叫做节点ni的后继节点或后裔，而节点的后继节点或后裔，而节点ni叫做叫做节点节点nj的父辈节点或祖先。的父辈节点或祖先。2.1 状态空间法状态空间法v2.1.2 状态图示法状态图示法 1.图论中的几个术语图论中的几个术语路径路径：某个节点序列：

11、某个节点序列(n(ni1i1,n,ni2i2, ,n,nikik) )当当j=2j=2，3 3，k k时，如果对于每一个时，如果对于每一个n ni i，j-1j-1都有一个后继节点都有一个后继节点n nijij存在，那么就把这个节点序列叫做从节点存在，那么就把这个节点序列叫做从节点n ni1i1至节点至节点n nikik的长度为的长度为k k的路径。的路径。v代价代价：用：用c(nc(ni i,n,nj j) )来表示从节点来表示从节点n ni i指向节点指向节点n nj j的那段弧线的代价。两节点间路的那段弧线的代价。两节点间路径的代价等于连接该路径上各节点的所有弧线代价之和。径的代价等于连

12、接该路径上各节点的所有弧线代价之和。 显式表示显式表示：各节点及其具有代价的弧线由一张表明确给出。此表可能列出该：各节点及其具有代价的弧线由一张表明确给出。此表可能列出该图中的每一节点、它的后继节点以及连接弧线的代价。图中的每一节点、它的后继节点以及连接弧线的代价。 隐式表示隐式表示：节点的无限集合：节点的无限集合ssi i 作为起始节点是已知的。后继节点算符作为起始节点是已知的。后继节点算符也也是已知的，它能作用于任一节点以产生该节点的全部后继节点和各连接弧线是已知的，它能作用于任一节点以产生该节点的全部后继节点和各连接弧线的代价。的代价。 2.1 状态空间法状态空间法v2.1.2 状态图示

13、法状态图示法 v2.2.图的显式和隐式表示图的显式和隐式表示 一个图可由显式说明也可由隐式说明。显然，显式说明对于大型一个图可由显式说明也可由隐式说明。显然，显式说明对于大型的图是不切实际的，而对于具有无限节点集合的图则是不可能的。的图是不切实际的，而对于具有无限节点集合的图则是不可能的。此外，引入后继节点算符的概念是方便的。后继节点算符此外，引入后继节点算符的概念是方便的。后继节点算符也是也是已知的，它能作用于任一节点以产生该节点的全部后继节点和各连接已知的，它能作用于任一节点以产生该节点的全部后继节点和各连接弧线的代价把后继算符应用于弧线的代价把后继算符应用于sisi的成员和它们的后继节点

14、以及这些的成员和它们的后继节点以及这些后继节点的后继节点，如此无限制地进行下去，最后使得由后继节点的后继节点，如此无限制地进行下去，最后使得由和和sisi所规定的隐式图变为显示图。所规定的隐式图变为显示图。v 问题的表示对求解工作量有很大的影响。人们显然希望有较小的问题的表示对求解工作量有很大的影响。人们显然希望有较小的状态空间表示。许多似乎很难的问题，当表示适当时就可能具有小而状态空间表示。许多似乎很难的问题，当表示适当时就可能具有小而简单的状态空间。简单的状态空间。 2.1 状态空间法状态空间法v2.1.2 状态图示法状态图示法v根据问题状态、操作符和目标条件选择各种表示，是高效率问题求解

15、必根据问题状态、操作符和目标条件选择各种表示，是高效率问题求解必须的。须的。v各种问题都可以用状态空间加以表示，并用状态空间搜索法来求解。各种问题都可以用状态空间加以表示，并用状态空间搜索法来求解。2.1 状态空间法状态空间法v2.1.2 状态图示法状态图示法 1.产生式系统（Production System） v一个总数据库(global database)：它含有与具体任务有关的信息；随着应用情况的不同，这些数据库可能小得像数字矩阵那样简单，或许大得如检索文件结构那么复杂。v一套规则：它对数据库进行操作运算。每条规则由左右两部分组成，左部鉴别规则的适用性或先决条件，右部描述规则应用时所完

16、成的动作。用规则来改变数据库就象用算符来改变状态一样。v一个控制策略：它确定应该采用哪一条适用规则，而且当数据库的终止条件满足时，就停止计算。控制策略由控制系统选择和确定。推销员旅行问题v总数据库：到目前为止所访问的城市；v规则对应于决策：即下一步走向城市，下一步走向城市，下一步走向城市，一条规则必须能把某个数据库变为一个合法数据库，否则不适应这个数据库；v任一以为起点和终点，并出现所有其它城市的总数据库，都满足终止条件2.1 状态空间法状态空间法v2.1.2 状态图示法状态图示法 2.2.状态空间表示举例状态空间表示举例例例2 2 猴子和香蕉问题猴子和香蕉问题(monkey and bana

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

18、个问题v 的状态，的状态， 其中其中 W W猴子的水平位置猴子的水平位置 X X当猴子在箱子顶上时取当猴子在箱子顶上时取X=1X=1；否则取；否则取X=0X=0 Y Y箱子的水平位置箱子的水平位置 Z Z当猴子摘到香蕉时取当猴子摘到香蕉时取Z=1Z=1；否则取；否则取Z=0 Z=0 图图 2.4 2.4 猴子和香蕉问题猴子和香蕉问题2.1 状态空间法状态空间法v2.1.2 状态图示法状态图示法 这个问题中的操作这个问题中的操作( (算符算符) )如下：如下：(1) goto(U)猴子走到水平位置猴子走到水平位置U U，或者用产生式规则表示为：，或者用产生式规则表示为：v (W，0，Y，z)(U

19、，0，Y，z) (2.3)v 即应用操作即应用操作goto(U)，能把状态，能把状态(W，0，Y，z)变换为状态变换为状态(U，0，Y，z)。v(2) pushbox(V)猴子把箱子推到水平位置猴子把箱子推到水平位置V V，即有，即有 v (W，0，W，z) (V，0，V，z) (2.4) )v应当注意的是，要应用算符应当注意的是，要应用算符pushbox(V)，就要求产生式规则的左边，就要求产生式规则的左边，猴子与箱子必须在同一位置上，并且，猴子不是在箱子顶上。这种强猴子与箱子必须在同一位置上，并且，猴子不是在箱子顶上。这种强加于操作的适用性条件，叫做产生式规则的先决条件。加于操作的适用性条

20、件，叫做产生式规则的先决条件。2.1 状态空间法状态空间法v2.1.2 状态图示法状态图示法 这个问题中的操作这个问题中的操作( (算符算符) )如下：如下：(3) climbbox猴子爬上箱顶，即有猴子爬上箱顶，即有 v (W，0，W，z) (W，1，W，z) (2.5)在应用算符在应用算符climbboxclimbbox时也必须注意到，猴子和箱子应当在同一位置上，时也必须注意到，猴子和箱子应当在同一位置上，而且猴子不在箱顶上而且猴子不在箱顶上 。v(4) grasp(4) grasp猴子摘到香蕉，即有猴子摘到香蕉，即有 v (c,1,c,0) (c,1,c,0) (c,1,c,1) (2.

21、6)(c,1,c,1) (2.6)其中，其中，c c是香蕉正下方的地板位置，在应用算符是香蕉正下方的地板位置，在应用算符graspgrasp时，要求猴子和时，要求猴子和箱子都在位置箱子都在位置c c上，并且猴子已在箱子顶上上，并且猴子已在箱子顶上。2.1 状态空间法状态空间法v 对于规则对于规则(2)(2)，只有当算符，只有当算符pushbox(V)pushbox(V)v 的先决条件，即猴子与箱子在同一位的先决条件，即猴子与箱子在同一位v 置上而且猴子不在箱顶上这些条件得置上而且猴子不在箱顶上这些条件得v 到满足时，算符到满足时，算符pushbox(V)pushbox(V)才是适用才是适用v

22、的。这一操作算符的作用是猴子把箱的。这一操作算符的作用是猴子把箱v 子推到位置子推到位置V V。在这一表示中，目标。在这一表示中，目标v 状态的集合可由任何最后元素为状态的集合可由任何最后元素为1 1的的v 表列来描述。令初始状态为表列来描述。令初始状态为(a,0,b,0) (a,0,b,0) 这时，这时，goto(U)goto(U)是唯一适用的操作，是唯一适用的操作， v 并导致下一状态并导致下一状态(U,0,b,0)(U,0,b,0)。现在有。现在有3 3v 个适用的操作，即个适用的操作，即goto(U)goto(U)， v pushbox(V)pushbox(V)和和climbbox(c

23、limbbox(若若U=b)U=b)。猴猴子子和和香香蕉蕉问问题题的的状状态态空空间间图图 2.2 问题归约法问题归约法 v2.2.1 问题归约描述问题归约描述先把问题分解为子问题和子-子问题，然后解决较小的问题。对该问题的某个具体子集的解答就意味着对原始问题的一个解答。问题归约表示的组成部分：v一个初始问题描述；v一套把问题变换为子问题的操作符；v一套本原问题描述。v问题归约的实质：从目标(要解决的问题)出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个平凡的本原问题集合。2.2 问题归约法问题归约法 v2.2.1 问题归约描述问题归约描述v梵塔难题梵塔难题 有有3 3

24、个柱子个柱子(1(1，2 2和和3)3)和和3 3个不同尺寸的圆盘（个不同尺寸的圆盘（A A，B B和和C C）。在每个圆）。在每个圆盘的中心有一个孔，所以圆盘可以堆叠在柱子上。最初，盘的中心有一个孔，所以圆盘可以堆叠在柱子上。最初，3 3个圆盘都堆个圆盘都堆在柱子在柱子1 1上：最大的圆盘上：最大的圆盘C C在底部，最小的圆盘在底部，最小的圆盘A A在顶部。要求把所有圆在顶部。要求把所有圆盘都移到柱子盘都移到柱子3 3上，每次只许移动一个，而且只能先搬动柱子顶部的圆上，每次只许移动一个，而且只能先搬动柱子顶部的圆盘，还不许把尺寸较大的圆盘堆放在尺寸较小的圆盘上。这个问题的初盘，还不许把尺寸较

25、大的圆盘堆放在尺寸较小的圆盘上。这个问题的初始配置和目标配置如图始配置和目标配置如图2.62.6所示。所示。2.2 问题归约法问题归约法 v解题过程：解题过程：将原始问题归约为一个较简单问题集合，要把所有圆盘都移至柱将原始问题归约为一个较简单问题集合，要把所有圆盘都移至柱子子3 3，我们必须首先把圆盘，我们必须首先把圆盘C C移至柱子移至柱子3 3；而且在移动圆盘；而且在移动圆盘C C至柱子至柱子3 3之前，之前，要求柱子要求柱子3 3必须是空的。只有在移开圆盘必须是空的。只有在移开圆盘A A和和B B之后，才能移动圆盘之后，才能移动圆盘C C；而；而且圆盘且圆盘A A和和B B最好不要移至柱

26、子最好不要移至柱子3 3，否则就不能把圆盘，否则就不能把圆盘C C移至柱子移至柱子3 3。因此，。因此，首先应该把圆盘首先应该把圆盘A A和和B B移到柱子移到柱子2 2上。然后才能够进行关键的一步，把圆上。然后才能够进行关键的一步，把圆盘盘C C从柱子从柱子1 1移至柱子移至柱子3 3，并继续解决难题的其余部分。，并继续解决难题的其余部分。v将原始难题归约（简化）为下列子难题：移动圆盘将原始难题归约（简化）为下列子难题：移动圆盘A A和和B B至柱子至柱子2 2的的双圆盘难题，如图双圆盘难题，如图(a)(a)所示。所示。2.2 问题归约法问题归约法 v 图 2.7 梵塔问题解答(a) 图 2

27、.8 梵塔问题解答(b) 图 2.9 梵塔问题解答(c) 2.2 问题归约法问题归约法 v 梵塔问题归约图：子问题梵塔问题归约图：子问题2 2可作为本原问题考虑，因为它的解只包可作为本原问题考虑，因为它的解只包含一步移动。应用一系列相似的推理，子问题含一步移动。应用一系列相似的推理，子问题1 1和子问题和子问题3 3也可被归约为也可被归约为本原问题，如图本原问题，如图2.102.10所示。这种图式结构，叫做与或图所示。这种图式结构，叫做与或图(AND/OR graph)(AND/OR graph)。它能有效地说明如何由问题归约法求得问题的解答。它能有效地说明如何由问题归约法求得问题的解答。v梵

28、塔问题归约图2.2 问题归约法问题归约法 v2.2.1 问题归约描述问题归约描述v问题归约描述问题归约描述v问题归约方法应用算符把问题描述变换为子问题描述，问题描述可以用问题归约方法应用算符把问题描述变换为子问题描述，问题描述可以用多种数据结构形式，包括表列、树、字符串、矢量、数组等。梵塔问题多种数据结构形式，包括表列、树、字符串、矢量、数组等。梵塔问题采用包含两个数列的表列来描述采用包含两个数列的表列来描述,(113),(113),（333)333)表示把配置（表示把配置（113113）变）变换为配置（换为配置（333333）。）。v用状态空间表示的三元组合（用状态空间表示的三元组合（S S

29、，F F，G G）来规定与描述问题，有关子问）来规定与描述问题，有关子问题可以当作状态空间中的两个一定的题可以当作状态空间中的两个一定的“脚踏石脚踏石”之间寻找路径来辨别。之间寻找路径来辨别。梵塔问题中的子问题梵塔问题中的子问题 （111111）=（122122） ， （122122）=（322322） ， （322322）=（333333） ，规定了最后的路径将要通过，规定了最后的路径将要通过“脚踏石脚踏石”状态状态（122122）和（）和（322322）。）。2.2 问题归约法问题归约法 v2.2.2 与或图表示与或图表示 与图、或图、与或图：与图、或图、与或图：一般地，我们用一个类似图的

30、结构来表示把问题归约为后继问题的替换集合，这种结构图叫做问题归约图，或叫与或图。如下图所示:v（引入附加节点使含有一个以上后继问题的每个集合能够聚集在它们各自的父辈节点之下。）子问题替换集合结构图子问题替换集合结构图 与或图与或图 2.2 问题归约法问题归约法 v2.2.2 问题归约描述问题归约描述一些关于与或图的术语：一些关于与或图的术语：v终叶节点终叶节点：对应于原问题的本原节点。对应于原问题的本原节点。v或节点或节点：只要解决某个问题就可解决其父辈问题的节点集合，如（只要解决某个问题就可解决其父辈问题的节点集合，如（M M，N N，H H）。）。v与节点与节点：只有解决所有子问题，才能解

31、决其父辈问题的节点集合，如只有解决所有子问题，才能解决其父辈问题的节点集合，如（B,C)B,C)和（和（D,E,FD,E,F）各个结点之间用一端小圆弧连接标记。）各个结点之间用一端小圆弧连接标记。 2.2 问题归约法问题归约法 v2.2.2 问题归约描述问题归约描述与或图与或图：由与节点及或节点组成的结构图。由与节点及或节点组成的结构图。v可解节点的一般定义：可解节点的一般定义： (1) 终叶节点是可解节点终叶节点是可解节点( (因为它因为它v们与本原问题相关连们与本原问题相关连) )。v(2) (2) 如果某个非终叶节点含有或后如果某个非终叶节点含有或后v继节点，那么只要当其后继节点继节点，

32、那么只要当其后继节点v至少有一个是可解的时，此非终至少有一个是可解的时，此非终v叶节点才是可解的。叶节点才是可解的。v(3) (3) 如果某个非终叶节点含有与如果某个非终叶节点含有与v后继节点，那么只有当其后继节后继节点，那么只有当其后继节v点全部为可解时，此非终叶节点点全部为可解时，此非终叶节点v才是可解的。才是可解的。图图 2.15 与或图例子与或图例子 2.2 问题归约法问题归约法 v2.2.22.2.2问题归约描述问题归约描述 不可解节点的一般定义不可解节点的一般定义: : (1) (1) 没有后裔的非终叶节点为不可解节点。没有后裔的非终叶节点为不可解节点。 (2) (2) 如果某个非

33、终叶节点含有或后继节点，那么只有当其全部后裔为如果某个非终叶节点含有或后继节点，那么只有当其全部后裔为不可解时，此非终叶节点才是不可解的。不可解时，此非终叶节点才是不可解的。 (3) (3) 如果某个非终叶节点含有与后继节点，那么只要当其后裔至少有如果某个非终叶节点含有与后继节点，那么只要当其后裔至少有一个为不可解时，此非终叶节点才是不可解的。一个为不可解时，此非终叶节点才是不可解的。2.2 问题归约法问题归约法 v2.2.2 问题归约描述问题归约描述与或图构成规则与或图构成规则(1) (1) 与或图中的每个节点代表一个要解决的单一问题或问题集合。图中所含起始与或图中的每个节点代表一个要解决的

34、单一问题或问题集合。图中所含起始节点对应于原始问题。节点对应于原始问题。v(2) (2) 对应于本原问题的节点，叫做终叶节点，它没有后裔。对应于本原问题的节点，叫做终叶节点，它没有后裔。v(3) (3) 对于把算符应用于问题对于把算符应用于问题A A的每种可能情况，都把问题变换为一个子问题集合；的每种可能情况，都把问题变换为一个子问题集合；有向弧线自有向弧线自A A 指向后继节点表示所求得的子指向后继节点表示所求得的子v问题集合，如下图所示，把问题问题集合，如下图所示，把问题A A归约为归约为3 3个不同个不同v的子问题集合的子问题集合N N，M M，H(H(或节点或节点) )。图图 2.16

35、 与或树与或树2.2 问题归约法问题归约法 v2.2.2 问题归约描述问题归约描述与或图构成规则与或图构成规则v(4) (4) 一般对于代表两个或两个以上子问题集合的每个节点，有向弧线从一般对于代表两个或两个以上子问题集合的每个节点，有向弧线从此节点指向此子问题集合中的各个节点。由于只有当集合中所有的项都有解此节点指向此子问题集合中的各个节点。由于只有当集合中所有的项都有解时，这个子问题的集合才能获得解答，所以这些子问题节点叫做与节点。时，这个子问题的集合才能获得解答，所以这些子问题节点叫做与节点。v(5) (5) 在特殊情况下，当只有一个算符可应用于问题在特殊情况下，当只有一个算符可应用于问

36、题A A，而且这个算符产生，而且这个算符产生具有一个以上子问题的某个集合时，由上述规则具有一个以上子问题的某个集合时，由上述规则v3 3和规则和规则4 4所产生的图可以得到简化。所产生的图可以得到简化。v 因此，代表子问题集合的中间或节因此，代表子问题集合的中间或节v点可以被略去，如右图所示。点可以被略去，如右图所示。 图图 2.16 与或树与或树2.3 谓词逻辑法谓词逻辑法 v2.3.1 谓词演算（谓词演算（Predicate Calculus）1.语法和语义语法和语义(Syntax & Semantics)谓词逻辑的基本组成部分：谓词符号、变量符号、函数符号和常量谓词逻辑的基本组成

37、部分：谓词符号、变量符号、函数符号和常量符号，并用圆括号、方括号、花括号和逗号隔开，表示论域内的关系。符号，并用圆括号、方括号、花括号和逗号隔开，表示论域内的关系。v原子公式原子公式(atomic formulas)(atomic formulas)由若干谓词符号和项组成的谓词演算。由若干谓词符号和项组成的谓词演算。原子公式是谓词演算基本积木块。原子公式是谓词演算基本积木块。v例如，要表示机器人例如，要表示机器人(ROBOT)(ROBOT)在号房间在号房间(r1)(r1)内，如图内，如图2.192.19所所示，可以应用原子公式示，可以应用原子公式: :2.3 谓词逻辑法谓词逻辑法 v2.3.1

38、 谓词演算（谓词演算（Predicate Calculus） 1.语法和语义语法和语义(Syntax & Semantics)当机器人当机器人ROBOT移到房间移到房间r2时，原子公式可以表示为：时，原子公式可以表示为：v INROOM (ROBOT, r2)v 这两个原子公式的通用形式就是这两个原子公式的通用形式就是v 又如又如,“李的母亲和他的父亲结婚李的母亲和他的父亲结婚”这句话的原子公式表示这句话的原子公式表示 v 如下：2.3 谓词逻辑法谓词逻辑法 v2.3.1 2.3.1 谓词演算（谓词演算（Predicate CalculusPredicate Calculus）2.2.

39、连词和量词连词和量词(Connective & Quantifiers) (Connective & Quantifiers) v(1) (1) 连词连词与与合取（合取（conjunctionconjunction）合取就是用连词）合取就是用连词把几个公把几个公式连接起来而构成的公式。合取项是合取式的每个组成部分。式连接起来而构成的公式。合取项是合取式的每个组成部分。v例：例：LIKE(ILIKE(I，MUSIC)LIKE(IMUSIC)LIKE(I，PAINTING)PAINTING)v ( (我喜爱音乐和绘画。我喜爱音乐和绘画。) )v2.3 谓词逻辑法谓词逻辑法 v2.3

40、.1 2.3.1 谓词演算（谓词演算（Predicate CalculusPredicate Calculus）2.2.连词和量词连词和量词(Connective & Quantifiers) (Connective & Quantifiers) v或或析取（析取（disjunctiondisjunction） 析取就是用连词析取就是用连词把几个公式连把几个公式连接起来而构成的公式。析取项是析取式的每个组成部分。接起来而构成的公式。析取项是析取式的每个组成部分。 v例：例：PLAYS(LILIPLAYS(LILI，BASKETBALL)PLAYS(LILIBASKETBALL)

41、PLAYS(LILI，FOOTBALL)FOOTBALL)v ( (李力打篮球或踢足球。李力打篮球或踢足球。) ) 2.3 谓词逻辑法谓词逻辑法 v2.3.1 谓词演算（谓词演算（Predicate Calculus）2.连词和量词连词和量词(Connective & Quantifiers) v(1) (1) 连词连词蕴涵蕴涵=表示表示 如果如果- -那么那么 的语句。用连词的语句。用连词=连接两个公式所构连接两个公式所构成的公式叫做蕴涵。成的公式叫做蕴涵。 v IFIF = = THEN THEN v 前项前项 后项后项v ( (左式左式) ) ( (右式右式) )v例：例：RUN

42、S(LIUHUARUNS(LIUHUA，FASTEST) = TWINS(LIUHUAFASTEST) = TWINS(LIUHUA，CHAMPION) CHAMPION) v( (如果刘华跑得最快，那么他取得冠军如果刘华跑得最快，那么他取得冠军) )v非（非（NOTNOT） 表示否定，、表示否定，、均可表示否定。均可表示否定。v例：例：INROOM(ROBOTINROOM(ROBOT，r2)r2)v ( (机器人不在机器人不在2 2号房间内。号房间内。) )2.3 谓词逻辑法谓词逻辑法 v2.3.1 2.3.1 谓词演算（谓词演算（Predicate CalculusPredicate Ca

43、lculus）2.2.连词和量词连词和量词(Connective & Quantifiers)(Connective & Quantifiers) v(2) (2) 量词量词 全称量词全称量词(Universal Quantifier)(Universal Quantifier)若一个原子公式若一个原子公式P(x)P(x)，对于所有可，对于所有可能变量能变量x x都具有都具有T T值，则用值，则用( x)P(x)( x)P(x)表示。表示。v例：例：( x)ROBOT(x) = COLOR(x,GRAY)( x)ROBOT(x) = COLOR(x,GRAY)v ( (所有的机

44、器人都是灰色的）所有的机器人都是灰色的）v( x)Student(x) = Uniform(x,Color) ( x)Student(x) = Uniform(x,Color) v( (所有学生都穿彩色制服所有学生都穿彩色制服) )2.3 谓词逻辑法谓词逻辑法 v2.3.1 2.3.1 谓词演算（谓词演算（Predicate CalculusPredicate Calculus）2.2.连词和量词连词和量词(Connective & Quantifiers)(Connective & Quantifiers) v(2) (2) 量词量词 v存在量词存在量词(Existentia

45、l Quantifier)(Existential Quantifier)若一个原子公式若一个原子公式P(x)P(x)，至少有一个变元，至少有一个变元X X，可使，可使P(X)P(X)为为T T值，则用值，则用( x)P(x)( x)P(x)表示。表示。 v例：例：( x)INROOM(x,r1)( x)INROOM(x,r1)v(1(1号房间内有个物体号房间内有个物体) )v量化变元量化变元(Quantified Variables)(Quantified Variables)被量化了的变元被量化了的变元x-x-约束变量。约束变量。2.3 谓词逻辑法谓词逻辑法 v2.3.2 谓词公式（谓词公

46、式（Predicate Formulas）1.1.谓词公式的定义谓词公式的定义原子谓词公式原子谓词公式：用：用P(x1,x2,P(x1,x2,xn),xn)表示一个表示一个n n元谓词公式，其中元谓词公式，其中P P为为n n元元谓词，谓词，x1,x2,x1,x2,xnxn为客体变量或变元。通常把为客体变量或变元。通常把P(x1,x2,P(x1,x2,xn),xn)叫做谓词演算叫做谓词演算的原子公式，或原子谓词公式。的原子公式，或原子谓词公式。 分子谓词公式分子谓词公式：可以用连词把原子谓词公式组成复合谓词公式，并把它：可以用连词把原子谓词公式组成复合谓词公式，并把它叫做分子谓词公式。叫做分子

47、谓词公式。合适公式合适公式(WFF,well-formed formulas)(WFF,well-formed formulas)的递归定义：的递归定义：(1) (1) 原子谓词公式是合适公式。原子谓词公式是合适公式。(2) (2) 若若A A为合适公式，则为合适公式，则A A也是一个合适公式。也是一个合适公式。(3) (3) 若若A A和和B B都是合适公式，则都是合适公式，则(AB),(AB),(A=B), (AB)(AB),(AB),(A=B), (AB)也都是也都是合适公式。合适公式。(4) (4) 若若A A是合适公式，是合适公式，x x为为A A中的自由变元，则中的自由变元，则(

48、x)A,( x)A( x)A,( x)A都是合适公都是合适公式。式。(5) (5) 只有按上述规则只有按上述规则(1)(1)至至(4)(4)求得的那些公式，才是合适公式。求得的那些公式，才是合适公式。2.3 谓词逻辑法谓词逻辑法 v2.3.2 谓词公式（谓词公式（Predicate Formulas）1.谓词公式的定义谓词公式的定义v例题：v对于所有的x，如果x是整数，则x或为正的或者为负的。v( x)(I(x)=(P(x)N(x)vI(x)表示x是整数，P(x)表示x是正数，N(x)表示x是负数。2.3 谓词逻辑法谓词逻辑法 v2.3.2 谓词公式（谓词公式（Predicate Formul

49、as）2.合适公式的性质合适公式的性质合适公式的真值：p36v表2-1 真值表2.3 谓词逻辑法谓词逻辑法 v2.3.3 置换与合一（置换与合一（Substitution & Unification）1.1.置换置换在谓词逻辑中，有些推理规则可应用于一定的合适公式和合适公在谓词逻辑中，有些推理规则可应用于一定的合适公式和合适公式集，以产生新的合适公式。一个重要的推理规则是假元推理，这就式集，以产生新的合适公式。一个重要的推理规则是假元推理，这就是由合适公式是由合适公式W1W1和和W1=W2W1=W2产生合适公式产生合适公式W2W2的运算。另一个推理规则叫的运算。另一个推理规则叫做全称化

50、推理，它是由合适公式做全称化推理，它是由合适公式( x)W(x)( x)W(x)产生合适公式产生合适公式W(A)W(A)，其中，其中A A为任意常量符号。为任意常量符号。假元推理：假元推理：vv 全称化推理：全称化推理：vv 综合推理：综合推理： v2.3 谓词逻辑法谓词逻辑法 v2.3.3 置换与合一（置换与合一（Substitution & Unification）1.1.置换置换置换：用项置换：用项(A)(A)替换函数表达式中的变量替换函数表达式中的变量(x)(x)，记为，记为ESES，即表示一，即表示一个表达式个表达式E(Expression)E(Expression)用一个置

51、换用一个置换S(Substitution)S(Substitution)而得到的表达式而得到的表达式的置换。的置换。例例1 1表达式表达式Px,f(y),BPx,f(y),B的的4 4个置换为个置换为 s1=z/x,w/ys1=z/x,w/ys2=A/ys2=A/y s3=q(z)/x,A/y s3=q(z)/x,A/y s4=c/x,A/y s4=c/x,A/yv我们用我们用EsEs来表示一个表达式来表示一个表达式E E用置换用置换s s所得到的表达式的置换。于是，所得到的表达式的置换。于是，我们可得到我们可得到Px,f(y),BPx,f(y),B的的4 4个置换的例，如下：个置换的例，如下

52、：Px,f(y),Bs1=Pz,f(w),BPx,f(y),Bs1=Pz,f(w),BPx,f(y),Bs2=Px,f(A),BPx,f(y),Bs2=Px,f(A),B Px,f(y),Bs3=Pq(z),f(A),B Px,f(y),Bs3=Pq(z),f(A),BPx,f(y),Bs4=Pc,f(A),BPx,f(y),Bs4=Pc,f(A),B2.3 谓词逻辑法谓词逻辑法 v2.3.3 2.3.3 置换与合一（置换与合一（Substitution & UnificationSubstitution & Unification）2.2.性质性质 v可结合律可结合律 (LS

53、1)S2=L(S1S2) (L(LS1)S2=L(S1S2) (L表示一表达式表示一表达式) )v (S1S2)S3=S1(S2S3) (S1S2)S3=S1(S2S3) v置换是可结合的。用置换是可结合的。用s1s2s1s2表示两个置换表示两个置换s1s1和和s2s2的合成。的合成。L L表示一表达表示一表达式，则有式，则有(Ls1)s2=L(s1s2)(Ls1)s2=L(s1s2)v以及以及(s1s2)s3=s1(s2s3)(s1s2)s3=s1(s2s3)即用即用s1s1和和s2s2相继作用于表达式相继作用于表达式L L是同用是同用s1s2s1s2作用于作用于L L一样的。一样的。一般说

54、来，置换是不可交换的，即一般说来，置换是不可交换的，即v s1s2s2s1s1s2s2s1v3.3.合一合一 (unification)P38(unification)P38v合一：寻找项对变量的置换，以使两表达式一致。合一：寻找项对变量的置换，以使两表达式一致。可合一：如果一个置换可合一：如果一个置换s s作用于表达式集作用于表达式集EiEi的每个元素，则我的每个元素，则我们用们用EisEis来表示置换例的集。我们称表达式集来表示置换例的集。我们称表达式集EiEi是可合一的。是可合一的。2.3 谓词逻辑法谓词逻辑法v2.3.3 2.3.3 置换与合一（置换与合一（Substitution &

55、amp; UnificationSubstitution & Unification）例:表达式集Px,f(y),B, Px,f(B),B的合一者为:s=A/x,B/y 因为Px,f(y),Bs= Px,f(B),B=PA,f(B),B 即s使表达式成为单一形式: PA,f(B),B,但最简单的合一者为: s=B/Y 2.4 语义网络法语义网络法v语义网络是语义网络是19681968年年QuilianQuilian在研究人类联想记忆时提出的心理学模型，认为在研究人类联想记忆时提出的心理学模型，认为记忆是由概念间的联系来实现的。记忆是由概念间的联系来实现的。19721972年，年，Sim

56、monsSimmons首先将语义网络表示法用于首先将语义网络表示法用于自然语言理解系统。自然语言理解系统。语义网络的结构：语义网络是知识的一种语义网络的结构：语义网络是知识的一种图解表示图解表示，它由节点和弧线或链，它由节点和弧线或链线组成。节点用于表示实体、概念和情况等，弧线用于表示节点间的关系。组线组成。节点用于表示实体、概念和情况等，弧线用于表示节点间的关系。组成部分成部分: :v1 1 词法部分：决定表示词汇表中允许有哪些符号，它涉及各个节点和弧线。词法部分：决定表示词汇表中允许有哪些符号，它涉及各个节点和弧线。v2 2 结构部分：叙述符号排列的约束条件，指定各弧线连接的节点对。结构部

57、分：叙述符号排列的约束条件，指定各弧线连接的节点对。v3 3 过程部分：说明访问过程，这些过程能用来建立和修正描述，以及回答过程部分：说明访问过程，这些过程能用来建立和修正描述，以及回答相关问题。相关问题。 v4 4 语义部分：确定与描述相关的语义部分：确定与描述相关的( (联想联想) )意义的方法即确定有关节点的排列意义的方法即确定有关节点的排列及其占有物和对应弧线。及其占有物和对应弧线。2.4 语义网络法语义网络法v2.4.1 二元语义网络的表示二元语义网络的表示 (Representation of Two-Element Semantic Network)1.表示简单的事实表示简单的事

58、实 例例1. 所有的燕子都是鸟所有的燕子都是鸟 2.4 语义网络法语义网络法v2.4.1 二元语义网络的表示二元语义网络的表示 (Representation of Two-Element Semantic Network)2.2.表示占有关系和其它情况表示占有关系和其它情况 P40P40v 例2. 小燕是一只燕子，燕子是鸟；巢-1是小燕的巢，巢-1是巢中的一个。 3.3.选择语义基元选择语义基元 试图用一组基元来表示知识，以便简化表示，并可用简单的知识来表示更复杂的知识。 2.4 语义网络法语义网络法例3.我椅子的颜色是咖啡色的；椅子包套是皮革；椅子是一种家具；椅子是座位的一部分；椅子的所有

59、者是X；X是个人，如下图所示：2.4 语义网络法语义网络法2.4.2 多元语义网络的表示多元语义网络的表示 语义网络是一种网络结构。节点之间以链相连。多元语义网络表示的实质：把多元关系转化为一组二元关系的组合，或二元关系的合取。如果所要表示的知识是一元关系，例如，要表示李明是一个人，这在谓词逻辑中可表示为MAN(LIMING)。用语义网络，这就可以表示为:与这样的表示法相等效的关系在谓词逻辑中表示为ISA(LIMING，MAN)。这说明语义网络可以毫无困难地表示一元关系。 2.4 语义网络法语义网络法 例如：要表达北京大学例如：要表达北京大学(BEIJING University,(BEIJI

60、NG University,简称简称BU)BU)和清华大学和清华大学(TSINGHUA(TSINGHUA University, University,简称简称TU)TU)两校篮球队在北大进行的一场比赛的比分是两校篮球队在北大进行的一场比赛的比分是8585比比8989。 若用谓词逻辑可表示为若用谓词逻辑可表示为SCORE(BUSCORE(BU，TUTU，(85-89)(85-89)。这个表示式中包含。这个表示式中包含3 3项，而项，而语义网络从本质上来说，只能表示二元关系。解决这个矛盾的一种方法是把这个多语义网络从本质上来说，只能表示二元关系。解决这个矛盾的一种方法是把这个多元关系转化成一组二元关系的组合，或二元关系的合取。元关系转化成一组二元关系的组合，或二元关系的合取。 具体来说，多元关系具体来说，多元关系R(