人工智能2知识表示

1、目录 第一章第一章绪论绪论 第二章第二章知识表示知识表示 第三章搜索技术第三章搜索技术 第四章推理技术第四章推理技术 第五章机器学习第五章机器学习 第六章专家系统第六章专家系统 第七章自动规划系统第七章自动规划系统 第八章第八章 自然语言理解自然语言理解 第九章第九章 智能控制智能控制 第十章第十章 人工智能程序设计人工智能程序设计2.1 知识及其表示概述1. 知识及知识表示知识及知识表示 费根鲍姆：知识是经过归约、塑造、解释和转换的有用信费根鲍姆：知识是经过归约、塑造、解释和转换的有用信息。息。 即知识是经过加工的信息。即知识是经过加工的信息。 伯恩斯坦：知识是由特定领域的描述、关系和过程组

2、成的。伯恩斯坦：知识是由特定领域的描述、关系和过程组成的。 海斯海斯-罗思：知识包括事实、信念和启发式规则等。罗思：知识包括事实、信念和启发式规则等。 知识库的观点：知识是某个论域中所涉及的各有关方面、状知识库的观点：知识是某个论域中所涉及的各有关方面、状态的一种符号表示。态的一种符号表示。 知识可从范围、目的、有效性知识可从范围、目的、有效性3个方面描述：范围是由具体个方面描述：范围是由具体到到一般一般，目的是由说明到，目的是由说明到指定指定，有效性是由确定到，有效性是由确定到不确定不确定。2.1 知识及其表示概述1. 知识及知识表示知识及知识表示 “为了证明为了证明AB，只需证明，只需证明

3、AB是不可满足的是不可满足的” 一般性、指示性、确定性一般性、指示性、确定性 “桌子有四条腿桌子有四条腿” 具体的、说明性、不确定性具体的、说明性、不确定性 知识表示是研究用机器表示知识的可行性、有效性的一知识表示是研究用机器表示知识的可行性、有效性的一般方法，是一种数据结构与控制结构的统一体。既考虑知识般方法，是一种数据结构与控制结构的统一体。既考虑知识的存储又考虑知识的使用。的存储又考虑知识的使用。 知识表示是一组描述事物的约定，以便把人类知识表示知识表示是一组描述事物的约定，以便把人类知识表示成机器能处理的数据结构。成机器能处理的数据结构。2.1 知识及其表示概述2. 人工智能中知识表示

4、人工智能中知识表示 四种知识四种知识 事实知识：有关问题环境的一些事物的知识。如事物的事实知识：有关问题环境的一些事物的知识。如事物的分类、属性、事物间的关系、科学事实、客观事实等。分类、属性、事物间的关系、科学事实、客观事实等。静态静态 规则知识：有关问题中与事物的行动、动作相联系的因规则知识：有关问题中与事物的行动、动作相联系的因果关系知识。果关系知识。动态动态 控制知识：有关问题的求解步骤、技巧性知识。如算法控制知识：有关问题的求解步骤、技巧性知识。如算法 元知识：有关知识的知识，是知识库中的高级知识。如元知识：有关知识的知识，是知识库中的高级知识。如怎样使用规则、解释规则、校验规则、解

5、释程序结构等。怎样使用规则、解释规则、校验规则、解释程序结构等。2.1 知识及其表示概述2. 人工智能中知识表示人工智能中知识表示 陈述性知识表示：是对知识和事实的一种静止的表达方陈述性知识表示：是对知识和事实的一种静止的表达方法，如语义网络、框架和剧本等。是知识的一种显式表达。法，如语义网络、框架和剧本等。是知识的一种显式表达。 过程式知识表示：将有关某一问题领域的知识，连同如过程式知识表示：将有关某一问题领域的知识，连同如何使用这些知识的方法一起隐式地表达为一个求解问题的过何使用这些知识的方法一起隐式地表达为一个求解问题的过程。如程序。程。如程序。2.1 知识及其表示概述3. 知识表示应该

6、注意的问题知识表示应该注意的问题 合适性：所采用的知识表示方法因该恰好适合问题的处理和合适性：所采用的知识表示方法因该恰好适合问题的处理和求解。求解。 高效性：求解算法对所用的知识表示方法应该是高效的高效性：求解算法对所用的知识表示方法应该是高效的，对知识的检索也应该是高效的。，对知识的检索也应该是高效的。 可理解性：易于为用户理解，易于转化为自然语言。可理解性：易于为用户理解，易于转化为自然语言。 无二义性：知识表示的结果应该是唯一的。无二义性：知识表示的结果应该是唯一的。问问题题建建模模机机器器处处理理自然语言自然语言自然语言自然语言知识表示知识表示知识表示知识表示待求解问题待求解问题问题

7、解决方案问题解决方案知识表示的方法知识表示的方法 状态空间法状态空间法 问题归约法问题归约法 谓词逻辑法谓词逻辑法 产生式表示方法产生式表示方法 语义网络法语义网络法 框架表示框架表示 面向对象表示面向对象表示 剧本表示剧本表示2.2 状态空间法问题求解：试探搜索问题求解：试探搜索在可能的解空间内寻找一个解在可能的解空间内寻找一个解 1. 问题求解技术：问题求解技术： 问题的建模与表示问题的建模与表示 知识表示方法知识表示方法 求解方法（算法）求解方法（算法） 试探搜索法试探搜索法2. 状态空间法：基于解答空间的问题表示和求解方法。状态空间法：基于解答空间的问题表示和求解方法。三要点三要点 状

8、态：表示问题解法中每一步问题状况的数据结构。状态：表示问题解法中每一步问题状况的数据结构。 算符：把问题从一种状态变换为另一种状态的手段。算符：把问题从一种状态变换为另一种状态的手段。 状态空间法：以状态与算符为基础来表示问题和求解问题。状态空间法：以状态与算符为基础来表示问题和求解问题。2.2 状态空间法2.2.1 问题状态描述问题状态描述 1. 定义定义 状态状态(state):是为描述某类不同事物间的差别而引入的一组最少是为描述某类不同事物间的差别而引入的一组最少变量变量q0，q1，qn的有序集合，其矢量形式如下：的有序集合，其矢量形式如下：Q=q0,q1,qnT (2.1) 式中每个元

9、素式中每个元素qi(i=0,1，n)为集合的分量，称为状态变量。为集合的分量，称为状态变量。 算符算符(operator)：使问题从一种状态变化为另一种状态的手段：使问题从一种状态变化为另一种状态的手段称为操作符或算符。操作符可为走步、过程、规则、数学算子、称为操作符或算符。操作符可为走步、过程、规则、数学算子、运算符号或逻辑符号等。运算符号或逻辑符号等。2.2 状态空间法2.2.1 问题状态描述问题状态描述 1. 定义定义 问题的状态空间问题的状态空间(state space)：是一个表示该问题全部可能状：是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合，即所有可能的问题初态及

10、其关系的图，它包含三种说明的集合，即所有可能的问题初始状态集合始状态集合S、操作符集合、操作符集合F以及目标状态集合以及目标状态集合G。因此，可把状。因此，可把状态空间记为三元状态态空间记为三元状态(S，F，G)。 2.2 状态空间法2.2.1 问题状态描述问题状态描述 2. 状态空间表示状态空间表示 11 9 4 151 3127 5 8 613 2 10 141 2 3 45 6 7 89 10 11 1213 14 15十五数码难题十五数码难题(a) (a) 初始棋局初始棋局(b) (b) 目标棋局目标棋局2.2 状态空间法2.2.1 问题状态描述问题状态描述 2. 状态空间表示状态空间

11、表示 11 9 4 151 3127 5 8 613 2 10 14十五数码难题部分状态图十五数码难题部分状态图11 9 4 1513 127 5 8 613 2 10 1411 9151 3 4 127 5 8 613 2 10 1411 9 4 151 3 127 5 8 613 2 10 1411 9 4 151 3 8 127 5613 2 10 14119 151 3 4 127 5 8 613 2 10 1411 9 151 3 4 127 5 8 613 2 10 1411 9 41 3 12 157 5 8 613 2 10 142.2 状态空间法2.2.2 状态图示法状态图示

12、法1. 图的基本概念图的基本概念节点节点(node)：图形上的汇合点，用来表示状态、事件和时间：图形上的汇合点，用来表示状态、事件和时间 关系的汇合，也可用来表示通路的汇合。关系的汇合，也可用来表示通路的汇合。 弧线弧线(arc)：节点间的连接线。：节点间的连接线。 有向图有向图(directed graph)：一对节点用弧线连接起来，从一个节：一对节点用弧线连接起来，从一个节点指向另一个节点，这种图叫做有向图。点指向另一个节点，这种图叫做有向图。 后继节点后继节点(descendant graph)与与父辈节点父辈节点(parent node) ：如果：如果某条弧线从节点某条弧线从节点ni指

13、向节点指向节点nj，那么节点，那么节点nj就叫做节点就叫做节点ni的后继节的后继节点，而节点点，而节点ni就叫做节点就叫做节点nj的父辈节点。的父辈节点。2.2 状态空间法2.2.2 状态图示法状态图示法1. 图的基本概念图的基本概念 路径路径(path)：对于某个节点序列：对于某个节点序列(ni1,ni2,nik)，当，当j=2，3，k时，如果对于每一个时，如果对于每一个ni，j-1都有一个后继节点都有一个后继节点nij存在，那么就把这存在，那么就把这个节点序列叫做从节点个节点序列叫做从节点ni1至节点至节点nik的长度为的长度为k的路径。的路径。代价代价(cost) ：是给各弧线指定数值以

14、表示加在相应算符上的：是给各弧线指定数值以表示加在相应算符上的代价，用代价，用c(ni,nj)表示节点表示节点ni指向节点指向节点nj的那段弧线的代价。的那段弧线的代价。显式表示显式表示：各节点及其具有代价的弧线用一张表明确给出。：各节点及其具有代价的弧线用一张表明确给出。 隐式表示隐式表示：节点的无限集合：节点的无限集合si作为起始节点是已知的。后继作为起始节点是已知的。后继节点算符也是已知的，它能作用于任意节点以产生该节点的全部节点算符也是已知的，它能作用于任意节点以产生该节点的全部后继节点和各连接弧线的代价。后继节点和各连接弧线的代价。NoImage2.2 状态空间法2.2.2 状态图示

15、法状态图示法2. 图的显式与隐式表示图的显式与隐式表示 显式说明对于大型的图是不切实际的，而对于具有无限节点集显式说明对于大型的图是不切实际的，而对于具有无限节点集合的图则是不可能的。合的图则是不可能的。2.2 状态空间法2.2.3 状态空间表示举例状态空间表示举例1. 产生式系统（产生式系统（production system） 一个产生式系统由下列一个产生式系统由下列3部分组成：部分组成：一个总数据库一个总数据库(global database)，它含有与具体任务有关的信，它含有与具体任务有关的信息。息。一套规则一套规则，它对数据库进行操作运算。每条规则由左右两部，它对数据库进行操作运算。

16、每条规则由左右两部分组成，左部鉴别规则的适用性或先决条件，右部描述规则应用分组成，左部鉴别规则的适用性或先决条件，右部描述规则应用时所完成的动作。应用规则来改变数据库。时所完成的动作。应用规则来改变数据库。一个控制策略一个控制策略，它确定应该采用哪一条适用规则，而且当数，它确定应该采用哪一条适用规则，而且当数据库的终止条件满足时，就停止计算。据库的终止条件满足时，就停止计算。2.2 状态空间法2.2.3 状态空间表示举例状态空间表示举例2、状态空间表示举例、状态空间表示举例a c b箱子猴子与香蕉的问题：猴子与香蕉的问题：在一个房间内有一在一个房间内有一只猴子、一个箱子只猴子、一个箱子和一束香

17、蕉。香蕉和一束香蕉。香蕉挂在天花板下方，挂在天花板下方，但猴子的高度不足但猴子的高度不足以碰到它。那么猴以碰到它。那么猴子怎样才能摘到香子怎样才能摘到香蕉呢？蕉呢？a c b2.2 状态空间法2.2.3 状态空间表示举例状态空间表示举例2、状态空间表示举例、状态空间表示举例用四元组（用四元组（W，x， Y ，z）表示这个问题状态空间，其中：）表示这个问题状态空间，其中： W 猴子的水平位置猴子的水平位置(a,b,c)； x 当猴子在箱子顶上时取当猴子在箱子顶上时取x=1；否则取；否则取x=0； Y 箱子的水平位置；箱子的水平位置； z 当猴子摘到香蕉时取当猴子摘到香蕉时取z=1；否则取；否则取

18、z=0。 初始状态：初始状态：(a,0,b,0) 目标状态目标状态：(c,1,c,1)2.2 状态空间法2.2.3 状态空间表示举例状态空间表示举例2、状态空间表示举例、状态空间表示举例该问题算符：该问题算符： (1) goto(U)：猴子走到水平位置：猴子走到水平位置U； （W，0， Y ，z） （U，0， Y ，z） (2) pushbox(V)：猴子把箱子推到水平位置：猴子把箱子推到水平位置V； （W，0， W ，z） （V，0， V ，z） (3) climbbox：猴子爬上箱顶；：猴子爬上箱顶； （W，0， W ，z） （W，1， W ，z） (4) grasp：猴子摘到香蕉。：猴子

19、摘到香蕉。 （c，1， c ，0） （c，1， c ，1） 其中，其中，c是香蕉正下方的地板位置。是香蕉正下方的地板位置。 goto(U)pushbox(V)climbboxgrasp2.2 状态空间法2.2.3 状态空间表示举例状态空间表示举例2、状态空间表示举例、状态空间表示举例求解过程求解过程 令初始状态为令初始状态为(a,0,b,0)。这时，。这时，goto(U)是唯一适用的操作，是唯一适用的操作，并导致下一状态并导致下一状态(U，0，b,0)。现在有。现在有3个适用的操作，即个适用的操作，即goto(U)，pushbox(V)和和climbbox(若若U=b)。把所有适用的操作。把所

20、有适用的操作 继继续应用于每个状态，我们就能够得到状态空间图续应用于每个状态，我们就能够得到状态空间图该初始状态变换为目标状态的操作序列为：该初始状态变换为目标状态的操作序列为：goto(b),pushbox(c),climbbox,grasp2.2 状态空间法2.2.3 状态空间表示举例状态空间表示举例2、状态空间表示举例、状态空间表示举例该初始状态变换为目标状态的操作序列为：该初始状态变换为目标状态的操作序列为：goto(b),pushbox(c),climbbox,grasp(a,0,b,0)(U,0,b,0)(V,0,V,0)(b,1,b,0)(c,1,c,0)(U,0,V,0)(c,

21、1,c,1)U=bU=b, climbboxV=c, climbboxgoto(U)goto(U)goto(U)goto(U)pushbox(V)graspU=V2.2 状态空间法习题：习题： 设有设有3个传教士和个传教士和3个野人来到河边，打算乘一只船从右岸个野人来到河边，打算乘一只船从右岸渡到左岸去。该船的负载能力为两人。在任何时候，如果野人渡到左岸去。该船的负载能力为两人。在任何时候，如果野人人数超过传教士人数，那么野人就会把传教士吃掉。他们怎样人数超过传教士人数，那么野人就会把传教士吃掉。他们怎样才能用这条船安全地把所有人都渡过河去？才能用这条船安全地把所有人都渡过河去？2.3 问题归

22、约法2.3.1 问题归约描述问题归约描述 已知问题的描述，通过一系列变换把此问题最终变为一个已知问题的描述，通过一系列变换把此问题最终变为一个子问题集合；这些子问题的解可以直接得到，从而解决了初始子问题集合；这些子问题的解可以直接得到，从而解决了初始问题。问题。该方法也就是从目标该方法也就是从目标(要解决的问题要解决的问题)出发逆向推理，建立出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个子问题以及子问题的子问题，直至最后把初始问题归约为一个平凡的本原问题集合。这就是问题归约的实质。平凡的本原问题集合。这就是问题归约的实质。 问题归约法的组成部分问题归约法的组成部分（1

23、）一个初始问题描述；）一个初始问题描述；（2）一套把问题变换为子问题的操作符；）一套把问题变换为子问题的操作符；（3）一套本原问题描述。）一套本原问题描述。 2.3 问题归约法2.3.1 问题归约描述问题归约描述梵塔难题梵塔难题问题问题 有有3个柱子个柱子(1，2，3)和和3个不同尺寸的圆盘个不同尺寸的圆盘(A，B，C)。在每个圆盘的中心有个孔，所以圆盘可以堆叠在柱子上。最初在每个圆盘的中心有个孔，所以圆盘可以堆叠在柱子上。最初，全部，全部3个圆盘都堆在柱子个圆盘都堆在柱子1上：最大的圆盘上：最大的圆盘C在底部，最小的在底部，最小的圆盘圆盘A在顶部。要求把所有圆盘都移到柱子在顶部。要求把所有圆

24、盘都移到柱子3上，每次只许移动上，每次只许移动一个，而且只能先搬动柱子顶部的圆盘，还不许把尺寸较大的一个，而且只能先搬动柱子顶部的圆盘，还不许把尺寸较大的圆盘堆放在尺寸较小的圆盘上。圆盘堆放在尺寸较小的圆盘上。2.3 问题归约法2.3.1 问题归约描述问题归约描述ABC123ABC123初始配置目标配置如何由初始配置变换为目标配置？2.3 问题归约法2.3.1 问题归约描述问题归约描述移动移动A、B - 2 双圆盘问双圆盘问题：可进一步归约题：可进一步归约(111)=(113)(113)=(123)(123)=(122)移动移动A、B - 3 双圆盘双圆盘问题：可进一步归约问题：可进一步归约(

25、322)=(321)(321)=(331)(331)=(333)移动移动C - 3 单圆盘单圆盘问题：可直接求解问题：可直接求解-本本原问题原问题2.3 问题归约法2.3.1 问题归约描述问题归约描述归约过程归约过程（1）移动圆盘）移动圆盘A和和B至柱子至柱子2的双圆盘难题；的双圆盘难题；（2）移动圆盘）移动圆盘C至柱子至柱子3的单圆盘难题；的单圆盘难题；（3）移动圆盘）移动圆盘A和和B至柱子至柱子3的双圆盘难题。的双圆盘难题。由上可以看出简化了难题每一个都比原始难题容易，所以由上可以看出简化了难题每一个都比原始难题容易，所以问题都会变成易解的本原问题。问题都会变成易解的本原问题。2.3 问题

26、归约法2.3.1 问题归约描述问题归约描述梵塔问题归约图梵塔问题归约图 29问题归约描述：问题归约描述： 采用问题归约法采用问题归约法 描述与求解问题时描述与求解问题时 问题归约表示由三部分组成：问题归约表示由三部分组成：（1）一个一个初始问题描述初始问题描述 如：如：（111），（），（333）（2）一套把问题变换为子问题的操作符一套把问题变换为子问题的操作符问题归约算符问题归约算符 如：移动如：移动A、B - 2 等等（3）一套一套本原问题描述本原问题描述 如：如：（122），（），（322） 本原问题：本原问题：是可直接求解或具有已知解答的问题，出现本原问题是可直接求解或具有已知解答的问

27、题，出现本原问题即可停止搜索。即可停止搜索。问题归约法的实质问题归约法的实质：从目标（要解决的问题）出发：从目标（要解决的问题）出发逆向推理逆向推理，建，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个立子问题以及子问题的子问题，直至最后把初始问题归约为一个本原问题集合。本原问题集合。问题归约的目的问题归约的目的：最终产生具有明显解答的本原问题。：最终产生具有明显解答的本原问题。 2.3 问题归约法2.3 问题归约法2.3.2 与或图表示与或图表示1. 与或图的概念与或图的概念用一个类似图的结构来表示把问题归约为后继问题的替换用一个类似图的结构来表示把问题归约为后继问题的替换集合，画

28、出归约问题图。集合，画出归约问题图。例如，设想问题例如，设想问题A需要由求解问题需要由求解问题B、C和和D来决定，那么可来决定，那么可以用一个与图来表示；同样，一个问题以用一个与图来表示；同样，一个问题A或者由求解问题或者由求解问题B、或、或者由求解问题者由求解问题C来决定，则可以用一个或图来表示。来决定，则可以用一个或图来表示。2.3 问题归约法2.3.2 与或图表示与或图表示2. 与或图的有关术语与或图的有关术语父节点父节点: 是一个初始问题或是可分解为子问题的问题节点；是一个初始问题或是可分解为子问题的问题节点；子节点子节点: 是一个初始问题或是子问题分解的子问题节点；是一个初始问题或是

29、子问题分解的子问题节点；或节点或节点: 只要解决某个问题就可解决其父辈问题的节点集合；只要解决某个问题就可解决其父辈问题的节点集合；与节点与节点: 只有解决所有子问题，才能解决其父辈问题的节点集只有解决所有子问题，才能解决其父辈问题的节点集合；合；弧线弧线: 是父辈节点指向子节点的圆弧连线；是父辈节点指向子节点的圆弧连线；终叶节点终叶节点: 是对应于原问题的本原节点。是对应于原问题的本原节点。 2.3 问题归约法2.3.2 与或图表示与或图表示2. 与或图的有关术语与或图的有关术语ANMHBCDEFG与或图与或图 2.3 问题归约法2.3.2 与或图表示与或图表示3. 与或图的有关定义与或图的

30、有关定义可解节点可解节点 与或图中一个可解节点的一般定义可以归纳如下：与或图中一个可解节点的一般定义可以归纳如下：(1) 终叶节点是可解节点终叶节点是可解节点(因为它们与本原问题相关连因为它们与本原问题相关连)。(2) 如果某个非终叶节点含有或后继节点，那么只有当其后继如果某个非终叶节点含有或后继节点，那么只有当其后继节点至少有一个是可解的时，此非终叶节点才是可解的。节点至少有一个是可解的时，此非终叶节点才是可解的。(3) 如果某个非终叶节点含有与后继节点，那么只要当其后继如果某个非终叶节点含有与后继节点，那么只要当其后继节点全部为可解时，此非终叶节点才是可解的。节点全部为可解时，此非终叶节点

31、才是可解的。2.3 问题归约法2.3.2 与或图表示与或图表示3. 与或图的有关定义与或图的有关定义不可解节点不可解节点 不可解节点的一般定义归纳于下：不可解节点的一般定义归纳于下：(1) 没有后裔的非终叶节点为不可解节点。没有后裔的非终叶节点为不可解节点。(2) 如果某个非终叶节点含有或后继节点，那么只有当其全如果某个非终叶节点含有或后继节点，那么只有当其全部后裔为不可解时，此非终叶节点才是不可解的。部后裔为不可解时，此非终叶节点才是不可解的。(3) 如果某个非终叶节点含有与后继节点，那么只要当其后如果某个非终叶节点含有与后继节点，那么只要当其后裔至少有一个为不可解时，此非终叶节点才是不可解

32、的裔至少有一个为不可解时，此非终叶节点才是不可解的。2.3 问题归约法2.3.2 与或图表示与或图表示4. 与或图构图规则与或图构图规则(1) 与或图中的每个节点代表一个要解决的单一问题或问题集与或图中的每个节点代表一个要解决的单一问题或问题集合。图中所含起始节点对应于原始问题。合。图中所含起始节点对应于原始问题。(2) 对应于本原问题的节点，叫做终叶节点，它没有后裔。对应于本原问题的节点，叫做终叶节点，它没有后裔。(3) 对于把算符应用于问题对于把算符应用于问题A的每种可能情况，都把问题变换为的每种可能情况，都把问题变换为一个子问题集合；有向弧线自一个子问题集合；有向弧线自A指向后继节点，表

33、示所求得指向后继节点，表示所求得的子问题集合。的子问题集合。(4) 一般对于代表两个或两个以上子问题集合的每个节点，有一般对于代表两个或两个以上子问题集合的每个节点，有向弧线从此节点指向此子问题集合中的各个节点。向弧线从此节点指向此子问题集合中的各个节点。(5) 在特殊情况下，当只有一个算符可应用于问题在特殊情况下，当只有一个算符可应用于问题A，而且这个，而且这个算符产生具有一个以上子问题的某个集合时，由上述规则算符产生具有一个以上子问题的某个集合时，由上述规则3和规则和规则4所产生的图可以得到简化。所产生的图可以得到简化。2.3 问题归约法2.3.2 与或图表示与或图表示4. 与或图构图规则

34、与或图构图规则ADEF与或图简化与或图简化 2.4 谓词逻辑法2.4.1 谓词公式谓词公式 P(x1, x2, , xn) n元元谓词公式谓词公式（predicate formulas）其中，其中，P为为n元谓词，元谓词，x1, x2, , xn为客体变量或变元。为客体变量或变元。 原子公式只有当其对应的语句在定义域内为真时，才具有原子公式只有当其对应的语句在定义域内为真时，才具有值值T(真真)；而当其对应的语句在定义域内为假时，该原子公式；而当其对应的语句在定义域内为假时，该原子公式才具有值才具有值F(假假)。 原子公式原子公式2.4 谓词逻辑法 2.4 谓词逻辑法2.4.2 谓词演算谓词演

35、算 1. 语法和语义语法和语义谓词逻辑的基本组成部分是谓词符号、变量符号、函数符号谓词逻辑的基本组成部分是谓词符号、变量符号、函数符号和常量符号，并用圆括弧、方括弧、花括弧和逗号隔开，以和常量符号，并用圆括弧、方括弧、花括弧和逗号隔开，以表示论域内的关系。表示论域内的关系。 原子公式是由若干谓词符号和项组成的谓词公式，是谓词演算的基本积原子公式是由若干谓词符号和项组成的谓词公式，是谓词演算的基本积木块。木块。r1r2INROOM(ROBOT, r1)INROOM(ROBOT, r2)通用形式：通用形式：INROOM(X, Y)MARRIED(mather(LI),father(LI)2.4 谓

36、词逻辑法 2.4 谓词逻辑法 2.4 谓词逻辑法 2.4 谓词逻辑法 2.4 谓词逻辑法2.4.2 谓词演算谓词演算2. 连词和量词连词和量词 量化一个合适公式中的某个变量所得到的表达式也是合适量化一个合适公式中的某个变量所得到的表达式也是合适公式。如果一个合适公式中某个变量是经过量化的，就把这公式。如果一个合适公式中某个变量是经过量化的，就把这个变量叫做约束变量，否则就叫它为自由变量。在合适公式个变量叫做约束变量，否则就叫它为自由变量。在合适公式中，感兴趣的主要是所有变量都是受约束的。这样的合适公中，感兴趣的主要是所有变量都是受约束的。这样的合适公式叫做句子。式叫做句子。2.4 谓词逻辑法2

37、.4.2 谓词演算谓词演算3. 演算演算 真值表真值表PQP=QPTTFTTFFF2.4 谓词逻辑法2.4.2 谓词演算谓词演算3. 演算演算等价关系等价关系 (1) 否定之否定否定之否定(P)等价于等价于P(2) PQ等价于等价于P=Q(3) 摩根定律摩根定律(PQ)等价于等价于PQ(PQ)等价于等价于PQ2.4 谓词逻辑法2.4.2 谓词演算谓词演算3. 演算演算 (4) 分配律分配律P(QR)等价于等价于(PQ)(PR)P(QR)等价于等价于(PQ)(PR)(5) 交换律交换律PQ等价于等价于QPPQ等价于等价于QP(6) 结合律结合律(PQ)R等价于等价于P(QR)(PQ)R等价于等价

38、于P(QR)2.4 谓词逻辑法 2.4 谓词逻辑法2.4.3 置换与合一置换与合一1. 置换置换假元推理：假元推理：由合适公式由合适公式W1和和W1=W2产生合适公式产生合适公式W2的运的运算。算。全称化推理：全称化推理：是由合适公式是由合适公式( x)W(x)产生合适公式产生合适公式W(A)，其，其中中A为任意常量符号。为任意常量符号。 2.4 谓词逻辑法2.4.3 置换与合一置换与合一1. 置换置换 例例2.3 表达式表达式Px, f(y), B的的4个置换为个置换为 s1=z/x, w/y 出现出现x和和y的地方，分别用的地方，分别用z和和w替换替换 s2=A/y s3=q(z)/x,A

39、/y s4=c/x, A/y 用用Es来表示一个表达式来表示一个表达式E用置换用置换s所得的表达式的置换，则：所得的表达式的置换，则： Px, f(y), B s1= Pz, f(w), B Px, f(y), B s2= Pz, f(A), B Px, f(y), B s3= Pq(z), f(A), B Px, f(y), B s4= Pc, f(A), B 2.4 谓词逻辑法2.4.3 置换与合一置换与合一1. 置换置换置换是可结合的，用置换是可结合的，用s1s2表示两个置换表示两个置换s1和和s2的合成。的合成。 (L s1) s2= L (s1s2) (s1 s2) s3= s1 (

40、s2 s3 ) 一般来说，置换是不可交换的，即一般来说，置换是不可交换的，即 s1 s2 s2 s12.4 谓词逻辑法2.4.3 置换与合一置换与合一2. 合一合一 寻找项对变量的置换，以使两表达式一致，叫做寻找项对变量的置换，以使两表达式一致，叫做合一合一(unification)。 如果一个置换如果一个置换s作用于表达式集作用于表达式集Ei的每个元素，则用的每个元素，则用Eis来表示置换例的集。称表达式集来表示置换例的集。称表达式集Ei是是可合一的可合一的。 如果存在一个置换如果存在一个置换s使得：使得：E1s=E2s=E3s=那么称此那么称此s为为Ei的的合一者合一者，因为，因为s的作用

41、是使集合的作用是使集合Ei成为单一形式。称表达成为单一形式。称表达式集式集Ei是可合一的。是可合一的。 例例2.4 表达式集表达式集Px, f(y), B , Px, f(B), B 的合一者为的合一者为 s=A/x, B/y Px, f(y), Bs= Px, f(B), Bs= PA, f(B), B 最简单的合一最简单的合一 g=B/y Eis= Eigs 称称g为最通用（最一般）的合一者，记为最通用（最一般）的合一者，记mgu。2.5 产生式表示法1943年，美国逻辑学家年，美国逻辑学家Post首先提出首先提出1. 产生式的基本形式产生式的基本形式 产生式规则产生式规则 IF P TH

42、EN Q 或或 PQ P称为条件、前项或产生式的左边称为条件、前项或产生式的左边 Q称为操作、结果或产生式的右边称为操作、结果或产生式的右边与蕴涵式与蕴涵式 P=Q区别区别 蕴涵式中蕴涵式中 P、Q要求是谓词公式要求是谓词公式 产生式中产生式中P、Q可以是谓词公式，也可以不是可以是谓词公式，也可以不是2.5 产生式表示法2. 产生式推理产生式推理 产生式规则产生式规则 PQ 若观察到若观察到P，或者知识库中已有，或者知识库中已有P，则可以得到结论，则可以得到结论Q，或执行，或执行操作操作Q。推理的关键问题：推理的关键问题：如何有效解决规则匹配的冲突问题如何有效解决规则匹配的冲突问题2.6 语义

43、网络法语义网络是知识的一种结构化图解表示，它由节点和弧线或语义网络是知识的一种结构化图解表示，它由节点和弧线或链线组成。节点用于表示实体、概念和情况等，弧线用于表示节链线组成。节点用于表示实体、概念和情况等，弧线用于表示节点间的关系。点间的关系。 语义网络表示由下列语义网络表示由下列4个相关部分组成：个相关部分组成： (1) 词法部分词法部分 ：决定表示词汇表中允许有哪些符号，它涉及各：决定表示词汇表中允许有哪些符号，它涉及各个节点和弧线。个节点和弧线。 (2) 结构部分结构部分 ：叙述符号排列的约束条件，指定各弧线连接的：叙述符号排列的约束条件，指定各弧线连接的节点对。节点对。 (3) 过程

44、部分：说明访问过程，这些过程能用来建立和修正描过程部分：说明访问过程，这些过程能用来建立和修正描述，以及回答相关问题。述，以及回答相关问题。 (4) 语义部分：确定与描述相关的语义部分：确定与描述相关的(联想联想)意义的方法即确定有意义的方法即确定有关节点的排列及其占有物和对应弧线。关节点的排列及其占有物和对应弧线。2.6 语义网络法语义网络具有下列特点：语义网络具有下列特点：(1) 能把实体的结构、属性与实体间的因果关系显式地和简能把实体的结构、属性与实体间的因果关系显式地和简明地表达出来，与实体相关的事实、特征和关系可以通过相应明地表达出来，与实体相关的事实、特征和关系可以通过相应的节点弧

45、线推导出来。的节点弧线推导出来。(2) 由于与概念相关的属性和联系被组织在一个相应的节点由于与概念相关的属性和联系被组织在一个相应的节点中，因而使概念易于受访和学习。中，因而使概念易于受访和学习。(3) 表现问题更加直观，更易于理解，适于知识工程师与领表现问题更加直观，更易于理解，适于知识工程师与领域专家沟通。域专家沟通。(4) 语义网络结构的语义解释依赖于该结构的推理过程而没语义网络结构的语义解释依赖于该结构的推理过程而没有结构的约定，因而得到的推理不能保证像谓词逻辑法那样有有结构的约定，因而得到的推理不能保证像谓词逻辑法那样有效。效。(5) 节点间的联系可能是线状、树状或网状的，甚至是递归

46、节点间的联系可能是线状、树状或网状的，甚至是递归状的结构，使相应的知识存储和检索可能需要比较复杂的过程状的结构，使相应的知识存储和检索可能需要比较复杂的过程。2.6 语义网络法2.6.1 二元语义网络的表示二元语义网络的表示 1. 用语义网络表示简单事实用语义网络表示简单事实例例2.5 所有的燕子都是鸟所有的燕子都是鸟 。 小燕子是一只燕子。小燕子是一只燕子。 小燕有一个巢。小燕有一个巢。 小燕从春天到秋天占有一个巢。小燕从春天到秋天占有一个巢。SWALLOWBIRDISAXIAOYANNEST-1NESTISAISAOWNS2.6 语义网络法2.6.1 二元语义网络的表示二元语义网络的表示

47、1. 用语义网络表示简单事实用语义网络表示简单事实用两个节点和一条弧线可以表示一个简单的事实，对于表用两个节点和一条弧线可以表示一个简单的事实，对于表示占有关系的语义网络，是通过允许节点既可以表示一个物体示占有关系的语义网络，是通过允许节点既可以表示一个物体或一组物体，也可以表示情况和动作。每一情况节点可以有一或一组物体，也可以表示情况和动作。每一情况节点可以有一组向外的弧组向外的弧(事例弧事例弧)，称为事例框，用以说明与该事例有关的各，称为事例框，用以说明与该事例有关的各种变量。种变量。在选择节点时，首先要弄清节点是用于表示基本的物在选择节点时，首先要弄清节点是用于表示基本的物体或概念的，或

48、是用于多种目的的。否则，如果语义网络只被体或概念的，或是用于多种目的的。否则，如果语义网络只被用来表示一个特定的物体或概念，那么当有更多的实例时就需用来表示一个特定的物体或概念，那么当有更多的实例时就需要更多的语义网络。要更多的语义网络。2.6 语义网络法2.6.1 二元语义网络的表示二元语义网络的表示 2. 用语义网络表示复杂的事实及其关系用语义网络表示复杂的事实及其关系 选择语义基元就是试图用一组基元来表示知识。这些选择语义基元就是试图用一组基元来表示知识。这些基元描述基本知识，并以图解表示的形式相互联系。基元描述基本知识，并以图解表示的形式相互联系。CHAIRISAFURNITUREMY

49、 CHAIRLEATHERSEATSWALLOWXPERSONISA PARTCOLORISACOVERINGOWNERISA2.6 语义网络法2.6.2 多元语义网络的表示多元语义网络的表示 语义网络是一种网络结构。节点之间以链相连。从本语义网络是一种网络结构。节点之间以链相连。从本质上讲，接点之间的连接是二元关系。语义网络从本质上来说质上讲，接点之间的连接是二元关系。语义网络从本质上来说，只能表示二元关系，如果所要表示的事实是多元关系，则把，只能表示二元关系，如果所要表示的事实是多元关系，则把这个多元关系转化成一组二元关系的组合，或二元关系的合取这个多元关系转化成一组二元关系的组合，或二元

50、关系的合取。具体来说，多元关系。具体来说，多元关系R(X1，X2，Xn)总可以转换成总可以转换成R1 (X11，X12)R2 (X21，X22)Rn (Xn1,Xn2)。要在语义网络中进行。要在语义网络中进行这种转换需要引入附加节点。这种转换需要引入附加节点。 2.6 语义网络法2.6.2 多元语义网络的表示多元语义网络的表示 北京大学（北京大学（BU）和清华大学（）和清华大学（TU）两校篮球队在北大）两校篮球队在北大进行的一场比赛的比分是进行的一场比赛的比分是85比比89。 GAMEG25BU85-89TUISAHOMETEAMVISTINGTEAMSCORE2.6 语义网络法2.6.3 基

51、于语义网络的知识推理基于语义网络的知识推理 继承：把对事物的描述从概念节点或类节点传递到实例节继承：把对事物的描述从概念节点或类节点传递到实例节点。点。 匹配：匹配： 由几个部分组成的的事物间的匹配由几个部分组成的的事物间的匹配2.7 框架表示2.7.1 框架理论及特点框架理论及特点 1. 框架理论概述框架理论概述 1975年年 ，明斯基，明斯基frame理论理论 当遇见一个新事物时，人们在记忆中选择一个合适的框架，当遇见一个新事物时，人们在记忆中选择一个合适的框架，然后根据事物的具体情况对框架进行填充并进行适当修改和补充然后根据事物的具体情况对框架进行填充并进行适当修改和补充，从而形成当前事

52、物的认识。这种数据结构就称为框架。，从而形成当前事物的认识。这种数据结构就称为框架。框架可以定义为是一组语义网络的节点和槽。框架可以定义为是一组语义网络的节点和槽。2. 框架的特点框架的特点 自然性自然性 结构性：结构化的语义网络网络结构性：结构化的语义网络网络 继承性：继承性：2.7 框架表示2.7.2 框架的构成框架的构成 框架通常由描述事物的各个方面的槽组成，每个槽可以拥有框架通常由描述事物的各个方面的槽组成，每个槽可以拥有若干个侧面，而每个侧面又可以拥有若干个值。一个框架的一般若干个侧面，而每个侧面又可以拥有若干个值。一个框架的一般结构如下：结构如下： 框架名框架名槽槽1侧面侧面11值

53、值111侧面侧面12值值121槽槽2侧面侧面21值值211 槽槽n侧面侧面n1值值n11侧面侧面nm值值nm12.7 框架表示2.7.2 框架的构成框架的构成 较简单的情景是用框架来表示诸如人和房子等事物。例如，较简单的情景是用框架来表示诸如人和房子等事物。例如，一个人可以用其职业、身高和体重等项描述，因而可以用这些项一个人可以用其职业、身高和体重等项描述，因而可以用这些项目组成框架的槽。当描述一个具体的人时，再用这些项目的具体目组成框架的槽。当描述一个具体的人时，再用这些项目的具体值填入到相应的槽中。值填入到相应的槽中。2.7 框架表示2.7.2 框架的构成框架的构成 表表2.2给出的是描述

54、给出的是描述John的框架。的框架。框架是一种通用的知识表达形式，对于如何运用框架系统还没有框架是一种通用的知识表达形式，对于如何运用框架系统还没有一种统一的形式一种统一的形式，常常由各种问题的不同需要来决定。，常常由各种问题的不同需要来决定。 JOHNIsa：PERSONProfession：PROGRAMMERHeight：1.8mWeight：79kg2.7 框架表示2.7.3 框架的推理框架的推理 如前所述，框架是一种复杂结构的语义网络。因此语义网络如前所述，框架是一种复杂结构的语义网络。因此语义网络 推理中的匹配和特性继承在框架系统中也可以实行。除此以外，推理中的匹配和特性继承在框架

55、系统中也可以实行。除此以外，由于框架用于描述具有固定格式的事物、动作和事件，因此可以由于框架用于描述具有固定格式的事物、动作和事件，因此可以在新的情况下，推论出未被观察到的事实。框架用以下几种途径在新的情况下，推论出未被观察到的事实。框架用以下几种途径来帮助实现这一点：来帮助实现这一点： (1) 框架包含它所描述的情况或物体的多方面的信息。框架包含它所描述的情况或物体的多方面的信息。 (2) 框架包含物体必须具有的属性。在填充框架的各个槽时，框架包含物体必须具有的属性。在填充框架的各个槽时，要用到这些属性。要用到这些属性。 (3) 框架描述它们所代表的概念的典型事例。框架描述它们所代表的概念的

56、典型事例。 2.7 框架表示2.7.3 框架的推理框架的推理 用一个框架来具体体现一个特定情况的过程，经常不是很顺利用一个框架来具体体现一个特定情况的过程，经常不是很顺利的。但当这个过程碰到障碍时，经常不必放弃原来的努力去从头的。但当这个过程碰到障碍时，经常不必放弃原来的努力去从头开始，而是有很多办法可想的：开始，而是有很多办法可想的： (1) 选择和当前情况相对应的当前的框架片断，并把这个框架选择和当前情况相对应的当前的框架片断，并把这个框架片断和候补框架相匹配。选择最佳匹配。片断和候补框架相匹配。选择最佳匹配。 (2) 尽管当前的框架和要描述的情况之间有不相匹配的地方，尽管当前的框架和要描述的情况之间有不相匹配的地方，但是仍然可以继续应用这个框架。但是仍然可以继续应用这个框架。 (3) 查询框架之间专门保存的链，以提出应朝哪个方向进行试查询框架之间专门保存的链，以提出应朝哪个方向进行试探的建议。探的建议。 (4) 沿着框架系统排列的层次结构向上移动沿着框架系统排列的层次结构向上移动(即从狗框架即从狗框架哺乳哺乳动物框架动物框架