第2章 知识表示方法人工智能

1、Artificial Intelligence (AI)人工智能人工智能主讲：何春梅Email：xiaoxiao_第二章：知识表示方法第二章：知识表示方法预备知识预备知识v人类的智能活动过程主要是一个获得并运用知识人类的智能活动过程主要是一个获得并运用知识的过程的过程v按照符号主义的观点，按照符号主义的观点，知识是一切智能行为的基知识是一切智能行为的基础础，要使计算机具有智能，首先必须使它拥有知，要使计算机具有智能，首先必须使它拥有知识识知识表示方法知识的概念知识的概念知识是人们在改造客观世界的知识是人们在改造客观世界的实践中积累起来的实践中积累起来的认识认识和和经验经验认识：认识：包括对事物

2、现象、本质、属性、状态、联系等包括对事物现象、本质、属性、状态、联系等的认识的认识经验：经验：包括包括解决问题的微观方法和宏观方法解决问题的微观方法和宏观方法p微观方法：微观方法：如步骤、操作、规则、过程、技巧等如步骤、操作、规则、过程、技巧等p宏观方法：宏观方法：如战略、战术、计谋、策略等如战略、战术、计谋、策略等eg：“if 大雁向南飞，大雁向南飞，then 冬天就要来临了。冬天就要来临了。”这样一条知识就是这样一条知识就是人们经过长期的观察，将人们经过长期的观察，将“大雁向南飞大雁向南飞”与与“冬天来临冬天来临”这两条信息这两条信息关联在一起。关联在一起。“雪是白色的雪是白色的”反映雪与

3、颜色的一种关系。反映雪与颜色的一种关系。知识的概念知识的概念 数据：数据：是信息的载体，本身无确切含义。如：是信息的载体，本身无确切含义。如：水的温度是水的温度是100，木头的长度是，木头的长度是2米，大楼的高度是米，大楼的高度是100层层 信息：信息：是数据的关联，赋予数据特定的含义，仅可理解为描是数据的关联，赋予数据特定的含义，仅可理解为描述性知识。数据是没有联系的，孤立的，述性知识。数据是没有联系的，孤立的，只有当数据用来描只有当数据用来描述一个客观事物和客观事物的关系，形成有逻辑的数据流，述一个客观事物和客观事物的关系，形成有逻辑的数据流，他们才能被称为信息他们才能被称为信息。 知识：

4、知识：是对信息的关联，或对已有知识的再认识。是对信息的关联，或对已有知识的再认识。 如：西安如：西安7月月1日气温为日气温为30度，度，12月月1日气温为日气温为3度。度。 当对这类信息进行归纳和对比就会发现西安每年当对这类信息进行归纳和对比就会发现西安每年7月气温比月气温比较高，较高，12月气温比较低，形成了新知识。月气温比较低，形成了新知识。知识的划分知识的划分按知识的性质：按知识的性质：概念、命题、公理、定理、规则和方法概念、命题、公理、定理、规则和方法按知识的作用域：按知识的作用域：常识性知识，领域性知识常识性知识，领域性知识按知识的等级：按知识的等级：p零级知识：零级知识：事实性知识

5、。用于描述事物的概念、定义、属性等；事实性知识。用于描述事物的概念、定义、属性等； 或用于描述问题的状态、环境、条件等。或用于描述问题的状态、环境、条件等。p一级知识：一级知识：过程性知识。用于问题求解过程的操作、演算和行过程性知识。用于问题求解过程的操作、演算和行为的知识。为的知识。表示方式：产生式、谓词、语义网络等。表示方式：产生式、谓词、语义网络等。p二级知识：二级知识：控制性知识，元知识或超知识。是关于如何使用过控制性知识，元知识或超知识。是关于如何使用过程性知识的知识。程性知识的知识。例如：推理策略、搜索策略、不确定性的传例如：推理策略、搜索策略、不确定性的传播策略。播策略。 知识的

6、划分知识的划分按知识的层次：按知识的层次：p表层知识：表层知识：描述客观事物的现象的知识。例如：感性、事实性描述客观事物的现象的知识。例如：感性、事实性知识知识p深层知识：深层知识：描述客观事物本质、内涵等的知识。例如：理论知描述客观事物本质、内涵等的知识。例如：理论知识识按知识的确定性：按知识的确定性：p确定性知识：确定性知识：可以说明其真值为真或为假的知识可以说明其真值为真或为假的知识p不确定性知识：不确定性知识：包括不精确、模糊、不完备知识包括不精确、模糊、不完备知识l不精确：不精确：知识本身有真假，但由于认识水平限制却不能肯定知知识本身有真假，但由于认识水平限制却不能肯定知识的真假。识

7、的真假。表示：用可信度、概率等描述表示：用可信度、概率等描述l模糊：模糊：知识本身的边界就是不清楚的。知识本身的边界就是不清楚的。例如：大，小等。表示：例如：大，小等。表示：用可能性、隶属度来描述用可能性、隶属度来描述l不完备：不完备：解决问题时不具备解决该问题的全部知识。解决问题时不具备解决该问题的全部知识。例如：医例如：医生看病生看病知识的划分知识的划分按人类的思维及认识方法：按人类的思维及认识方法：p逻辑性知识：逻辑性知识：是反映人类逻辑思维过程的知识，一般具有因果是反映人类逻辑思维过程的知识，一般具有因果关系或难以精确描述的特点，是人类的经验性知识和直观感觉；关系或难以精确描述的特点，

8、是人类的经验性知识和直观感觉；如：人的为人处事的经验与风格如：人的为人处事的经验与风格p形象性知识：形象性知识：通过事物的形象建立起来的知识。通过事物的形象建立起来的知识。如如: :什么是人？什么是人？按知识的获取方式：按知识的获取方式：p显性知识：显性知识：指可通过文字、语言、图形、声音等形式编码记录指可通过文字、语言、图形、声音等形式编码记录和传播的知识；和传播的知识；如：教材、音视频光盘。如：教材、音视频光盘。p隐性知识：隐性知识：指人们长期实践中积累获得的知识，不易用显性知指人们长期实践中积累获得的知识，不易用显性知识表达的知识。识表达的知识。如：每个人都有不同的审美观。如：每个人都有

9、不同的审美观。人工智能系统中的知识人工智能系统中的知识v 一个智能程序高水平的运行需要有关的一个智能程序高水平的运行需要有关的事实知识、规则知事实知识、规则知识、控制知识和元知识。识、控制知识和元知识。v 事实知识：事实知识：是有关问题环境的一些事物的知识，常以是有关问题环境的一些事物的知识，常以“是是”的形式出现。的形式出现。 如事物的分类、属性、事物间关系、科学事实、客观事实等如事物的分类、属性、事物间关系、科学事实、客观事实等 事实是静态的为人们共享的可公开获得的公认的知识，事实是静态的为人们共享的可公开获得的公认的知识，在知在知识库中属低层的知识。识库中属低层的知识。 如：雪是白色的、

10、鸟有翅膀、张三李四是好朋友、这辆车是如：雪是白色的、鸟有翅膀、张三李四是好朋友、这辆车是张三的张三的v 规则知识：规则知识：是有关问题中与事物的行动、动作相联系的因是有关问题中与事物的行动、动作相联系的因果关系知识，是动态的，常以果关系知识，是动态的，常以“如果如果那么那么” 形式出现。形式出现。人工智能系统中的知识人工智能系统中的知识v 控制知识：控制知识：是有关问题的求解步骤、技巧的知识，告诉人是有关问题的求解步骤、技巧的知识，告诉人们怎么做一件事，也包括当有多个动作同时被激活时应选们怎么做一件事，也包括当有多个动作同时被激活时应选哪一个动作来执行的知识。哪一个动作来执行的知识。控制知识常

11、与程序结合在一起控制知识常与程序结合在一起出现，如一个问题求解的算法可以看做是一种知识表示。出现，如一个问题求解的算法可以看做是一种知识表示。v 元知识：元知识：是有关知识的知识，是是有关知识的知识，是知识库中的高层知识知识库中的高层知识。 包括怎样使用规则、解释规则、校验规则、解释程序结构等包括怎样使用规则、解释规则、校验规则、解释程序结构等知识。知识。 元知识与控制知识是有重迭的元知识与控制知识是有重迭的，对一个大的程序来说，以元，对一个大的程序来说，以元知识或说元规则形式体现控制知识更为方便，因为知识或说元规则形式体现控制知识更为方便，因为元知识存元知识存于知识库中，而控制知识常与程序结

12、合在一起出现，从而不于知识库中，而控制知识常与程序结合在一起出现，从而不容易修改容易修改。 知识表示知识表示v 知识表示：知识表示：是研究用机器表示知识的可行性、有效性的一是研究用机器表示知识的可行性、有效性的一般方法，是一种般方法，是一种数据结构数据结构与与控制结构控制结构的统一体，既考虑知的统一体，既考虑知识的识的存储存储又考虑知识的又考虑知识的使用使用。v 知识表示的要求：知识表示的要求：p 表示能力：表示能力：能否能否正确正确、有效有效地表示问题。包括：表范围的广泛性、地表示问题。包括：表范围的广泛性、领域知识表示的高效性、对非确定性知识表示的支持程度。领域知识表示的高效性、对非确定性

13、知识表示的支持程度。p 可利用性：可利用性：可利用这些知识可利用这些知识进行有效推理进行有效推理。包括：对推理的适应。包括：对推理的适应性，对高效算法的支持程度。性，对高效算法的支持程度。p 可实现性：可实现性：要便于计算机直接对其进行处理要便于计算机直接对其进行处理 p 可组织性：可组织性：可以按某种方式把知识组织成可以按某种方式把知识组织成某种知识结构某种知识结构p 可维护性：可维护性：便于对知识的增、删、改等操作便于对知识的增、删、改等操作p 自然性：自然性：符合人们的日常习惯符合人们的日常习惯p 可理解性：可理解性：知识应易读、易懂、易获取等知识应易读、易懂、易获取等 内容提要1.1.

14、状态空间法状态空间法2.2.问题归约法问题归约法3.3.谓词逻辑法谓词逻辑法4.4.语义网络法语义网络法5.5.其他方法其他方法内容提要1.1.状态空间法状态空间法2.2.问题归约法问题归约法3.3.谓词逻辑法谓词逻辑法4.4.语义网络法语义网络法5.5.其他方法其他方法状态空间法v人工智能虽有多个研究领域，且每个研究领域又人工智能虽有多个研究领域，且每个研究领域又各有自己的规律和特点，但都可抽象为一个各有自己的规律和特点，但都可抽象为一个“问问题求解题求解”的过程。问题求解过程实际上是一个的过程。问题求解过程实际上是一个搜搜索索过程。过程。v 问题求解技术主要是两个方面：问题求解技术主要是两

15、个方面： 问题的表示问题的表示 求解的方法求解的方法v 状态空间法状态空间法（State Space Representation）：）：状态空间法是用来表示问题及其搜索过程的一种方法。它是人状态空间法是用来表示问题及其搜索过程的一种方法。它是人工智能中最基本的形式化方法，用工智能中最基本的形式化方法，用“状态（状态（state）”和和“算符算符（operator）”来表示问题。来表示问题。状态空间法v 状态空间法的三要素状态空间法的三要素p(1) 状态（状态（state）：）：描述某类不同事物间的差别而引入的一描述某类不同事物间的差别而引入的一组最少变量组最少变量 q0，q1，qn的有序集合

16、，是表示问题解法中的有序集合，是表示问题解法中每一步问题状况的数据结构。有序集合中每个元素每一步问题状况的数据结构。有序集合中每个元素qi（i= 0,1,.,n）为集合的分量，称为）为集合的分量，称为状态变量状态变量。给定每个分量的一。给定每个分量的一组值就得到一个具体的状态。组值就得到一个具体的状态。p (2) 算符（算符（operator）：）：使问题从一种状态变化为另一种状使问题从一种状态变化为另一种状态的手段称为操作符或算符。态的手段称为操作符或算符。p (3) 状态空间方法：状态空间方法：是是一个表示该问题全部可能状态及其关一个表示该问题全部可能状态及其关系的图系的图，它包含三种说明

17、的集合，即三元状态（，它包含三种说明的集合，即三元状态（S，F，G）。）。S：所有可能的问题初始状态集合；：所有可能的问题初始状态集合；F：操作符集合；：操作符集合；G：目：目标状态集合。标状态集合。状态空间法v 状态空间法举例：状态空间法举例：下棋、迷宫及各种游戏。下棋、迷宫及各种游戏。十五数码难题十五数码难题(15 puzzle)(15 puzzle)：由由1515个编有个编有1 1至至1515并放在并放在4 44 4方格棋盘上的可走动的棋子组成。方格棋盘上的可走动的棋子组成。119415131275861321014123456789101112131415初始棋局初始棋局目标棋局目标棋

18、局十五数码难题十五数码难题11119 94 415151 13 312127 75 58 86 613132 21010141411119 915151 13 34 412127 75 58 86 613132 21010141411119 94 415151 13 312127 75 58 86 613132 21010141411119 94 415151 13 38 812127 75 56 613132 21010141411119 94 415151 13 312127 75 58 86 613132 2101014141 12 23 34 45 56 67 78 89 910101

19、1111212131314141515初始状态初始状态目标状态目标状态如何把初试棋局如何把初试棋局变成目标棋局？变成目标棋局？首先把适用的算符首先把适用的算符用于初始状态，以产用于初始状态，以产生新的状态生新的状态再把另一些适用算符再把另一些适用算符用于这些新的状态；用于这些新的状态；这样继续下去，直至这样继续下去，直至产生目标状态为止产生目标状态为止状态空间法v 问题的表示对求解工作有很大影响。人们问题的表示对求解工作有很大影响。人们希望有较小的状希望有较小的状态空间表示态空间表示。v 例如，对于十五数码问题：例如，对于十五数码问题：可以规定可以规定15460条规则条规则p “上移棋子上移棋

20、子1，下移棋子，下移棋子1，左移棋子，左移棋子1，右移棋子，右移棋子1”p “上移棋子上移棋子2，下移棋子，下移棋子2，左移棋子，左移棋子2，右移棋子，右移棋子2 ”p .如果用如果用“上下左右移动空格上下左右移动空格”，则只需，则只需4条规则。所以，条规则。所以，移动空格是一种较好的表示。移动空格是一种较好的表示。状态空间法v 状态空间法举例：状态空间法举例：旅行商问题旅行商问题旅行商问题旅行商问题(Traveling Salesman Problem(Traveling Salesman Problem，TSP)TSP)：假定起始假定起始城市为城市为A状态空间法旅行商问题旅行商问题(Tra

21、veling Salesman Problem(Traveling Salesman Problem，TSP)TSP)：算符的代价算符的代价状态空间法v 状态图示法：状态图示法：状态空间的图示形式称为状态空间的图示形式称为状态空间图状态空间图。状态。状态图中有几个术语。图中有几个术语。 节点节点(Node)：图形上的汇合点，用来表示图形上的汇合点，用来表示状态状态、事件事件和和时间时间关系的汇合关系的汇合。 弧线弧线(Arc)：节点间的连接线，表示节点间的连接线，表示算符算符； 有向图有向图(Directed Graph)：一对节点用弧线连接起来，从一一对节点用弧线连接起来，从一个节点指向另一

22、个节点。个节点指向另一个节点。 后继节点后继节点(Descendant node)与父辈节点与父辈节点(Parent node)：如果如果某条弧线从节点某条弧线从节点ni指向节点指向节点nj，那么节点，那么节点nj就叫做节点就叫做节点ni的的后后继节点或后裔继节点或后裔，而节点，而节点ni叫做节点叫做节点nj的的父辈节点或祖先父辈节点或祖先。状态空间法v 状态图示法：状态图示法：状态空间的图示形式称为状态空间的图示形式称为状态空间图状态空间图。状态。状态图中有几个术语。图中有几个术语。 路径路径(Path)：某个节点序列某个节点序列(ni1,ni2,nik)当当j=2,3,k时，如时，如果对于

23、每一个果对于每一个ni,j-1都有一个后继节点都有一个后继节点nij存在，那么就把这个存在，那么就把这个节点序列叫做从节点节点序列叫做从节点ni1至节点至节点nik的长度为的长度为k的路径。的路径。 代价代价(Cost)：用用c(ni,nj)来表示从节点来表示从节点ni指向节点指向节点nj的的 那段弧那段弧线的代价。线的代价。两节点间路径的代价两节点间路径的代价等于连接该路径上各节点的等于连接该路径上各节点的所有弧线代价之和。所有弧线代价之和。 图的显示说明图的显示说明/隐示说明：隐示说明：指各节点及其具有代价的弧线可指各节点及其具有代价的弧线可以以/不可以由一张表明确给出。不可以由一张表明确

24、给出。显然，显示说明对于大型的显然，显示说明对于大型的图是不切实际的，而对于具有无限节点集合的图则是不可能图是不切实际的，而对于具有无限节点集合的图则是不可能的。的。状态空间法v 各种问题都可用状态空间加以表示，并用各种问题都可用状态空间加以表示，并用状态空间搜索法状态空间搜索法来求解。下面简单介绍一种来求解。下面简单介绍一种产生式系统（产生式系统（production system）描述的搜索算法。）描述的搜索算法。v 产生式系统（产生式系统（production systemproduction system）由三部分组成：）由三部分组成：一个总数据库：一个总数据库：0 0级知识。它含有与

25、具体任务有关的信级知识。它含有与具体任务有关的信息。息。一套规则：一套规则：1 1级知识。它对数据库进行操作运算。级知识。它对数据库进行操作运算。一个控制策略（程序）：一个控制策略（程序）：2 2级知识。它确定应该采用哪级知识。它确定应该采用哪一条适用规则，而且当数据库的终止条件满足时，就一条适用规则，而且当数据库的终止条件满足时，就停止计算。控制策略由控制系统选择和确定。停止计算。控制策略由控制系统选择和确定。 状态空间法v 状态空间法举例：状态空间法举例：猴子和香蕉问题：猴子和香蕉问题：在一个房间内有一只猴子、一个箱在一个房间内有一只猴子、一个箱子和一束香蕉。香蕉挂在天花板下方，但猴子的高

26、度子和一束香蕉。香蕉挂在天花板下方，但猴子的高度不足以碰到它。那么这只猴子怎样才能摘到香蕉呢不足以碰到它。那么这只猴子怎样才能摘到香蕉呢? ?猴子和香蕉问题v 解题过程解题过程 用一个四元表列（用一个四元表列（W，x，Y，z）来表示这个问题状态）来表示这个问题状态p W：猴子的水平位置；：猴子的水平位置；p x： 当猴子在箱子顶上时取当猴子在箱子顶上时取1；否则取；否则取0；p Y： 箱子的水平位置；箱子的水平位置；p z： 当猴子摘到香蕉时取当猴子摘到香蕉时取1；否则取；否则取0。p 初始状态为初始状态为(a,0,b,0) ，目标状态为，目标状态为(c,1,c,1) 这个问题的操作（算符）如

27、下：这个问题的操作（算符）如下：pgoto（U）表示猴子走到水平位置）表示猴子走到水平位置Uppushbox（V）猴子把箱子推到水平位置）猴子把箱子推到水平位置Vpclimbbox猴子爬上箱顶猴子爬上箱顶pgrasp猴子摘到香蕉猴子摘到香蕉猴子和香蕉问题v 解题过程解题过程该初始状态变换为目标该初始状态变换为目标状态的操作序列为：状态的操作序列为：pStep1: goto(b)pStep2: pushbox(c)pStep3: climbboxpStep4: grasp猴子和香蕉问题v 状态空间图状态空间图(b，1，b，0)（U，0，b，0）（V，0，V，0）（c，1，c，0）（U，0，V，0

28、）（c，1，c，1）（a，0，b，0）目标状态目标状态goto（U）goto（U）U=b，climbboxgoto（U）U=bpushbox（V）goto（U）U=VV=c，climbboxgrasp内容提要1.1.状态空间法状态空间法2.2.问题归约法问题归约法3.3.谓词逻辑法谓词逻辑法4.4.语义网络法语义网络法5.5.其他方法其他方法问题归约法v 问题归约（问题归约（Problem Reduction） 是另外一种是另外一种基于状态空间基于状态空间的问题描述与求解方法的问题描述与求解方法 已知问题的描述，通过一系列已知问题的描述，通过一系列变换变换把此问题变为一个把此问题变为一个子问题

29、子问题集合集合 这些子问题的解可以这些子问题的解可以直接得到（本原问题）直接得到（本原问题），从而解决了初，从而解决了初始问题始问题问题归约法v 问题归约法的组成部分问题归约法的组成部分一个初始问题描述；一个初始问题描述；一套把问题变换为子问题的一套把问题变换为子问题的操作符操作符；一套一套本原问题本原问题描述。描述。( (本原问题本原问题: :不能再分解或变换且不能再分解或变换且直接可解的子问题直接可解的子问题) )v 问题归约的实质：问题归约的实质：从目标（要解决的问题）出发从目标（要解决的问题）出发逆向推理逆向推理，建立子问题，建立子问题以及子问题的子问题，直到最后把初始问题归约为以及子

30、问题的子问题，直到最后把初始问题归约为一一个本原问题集合个本原问题集合。问题归约法v 问题归约法举例：问题归约法举例：汉诺塔问题（汉诺塔问题（ Hanoi ） p 从从1移到移到3p 每次移动一个盘子每次移动一个盘子p 大盘在下小盘在上大盘在下小盘在上123CBA初始状态（初始状态（111）目标状态（目标状态（333）CBA汉诺塔问题v 原始问题可以归约为下列原始问题可以归约为下列3 3个子问题：个子问题：子问题子问题1 1：子问题子问题2 2：子问题子问题3 3：汉诺塔问题v 归约过程（归约过程（3 3个圆盘）个圆盘）汉诺塔问题v 汉诺塔问题归约图汉诺塔问题归约图本原问题本原问题本原问题本原

31、问题与或图与或图CBA问题归约法v 与或图表示：与或图表示：用一个类似于图的结构来表示把问题归约为用一个类似于图的结构来表示把问题归约为后继问题的替换集合。后继问题的替换集合。与图：与图：把一个复杂问题把一个复杂问题分解为若干个较为简单的分解为若干个较为简单的子问题，形成子问题，形成“与与”树。树。或图：或图：把原问题变换为把原问题变换为若干个较为容易求解的新若干个较为容易求解的新问题，形成问题，形成“或或”树。树。问题归约法v 与或图表示：与或图表示：BCDEFGAHMBCDEFGAN子问题替代集合结构图子问题替代集合结构图与或图与或图问题归约法v 一些关于与或图的术语一些关于与或图的术语起

32、始节点起始节点对应于原对应于原始问题描始问题描述述终叶节点对应于本原问题终叶节点对应于本原问题问题归约法v 与或图的构成规则与或图的构成规则 1 1）与或图中的每个节点代表一）与或图中的每个节点代表一个要解决的单一问题或问题集合。个要解决的单一问题或问题集合。图中所含起始节点对应于原始问图中所含起始节点对应于原始问题题A A。 2 2）对应于本原问题的节点称为）对应于本原问题的节点称为终叶节点，它没有后继节点。终叶节点，它没有后继节点。 3 3）对于把算符应用于问题）对于把算符应用于问题A A的每的每种可能情况，都把问题变换为一种可能情况，都把问题变换为一个子问题集合；有向弧线自个子问题集合；

33、有向弧线自A A指指向后继节点表示所求得的子问题向后继节点表示所求得的子问题集合。集合。HMBCDEFGAN37问题归约法v 与或图的构成规则与或图的构成规则 4 4）一般对于代表两个或两个以上）一般对于代表两个或两个以上子问题集合的每个节点，有向弧子问题集合的每个节点，有向弧线从此节点指向次子问题集合中线从此节点指向次子问题集合中的各个节点。由于只有当集合中的各个节点。由于只有当集合中所有项都有解时，这个子问题的所有项都有解时，这个子问题的集合才能获得解答，所以这些子集合才能获得解答，所以这些子问题节点叫做与节点。问题节点叫做与节点。 5 5）特殊情况下，当只有一个算符）特殊情况下，当只有一

34、个算符可应用于问题可应用于问题A A，而且这个算符产，而且这个算符产生具有一个以上子问题的某个集生具有一个以上子问题的某个集合时，由上述规则合时，由上述规则3 3）和规则）和规则4 4）所产生的图可以得到简化。所产生的图可以得到简化。MDEFAADEF简化简化问题归约法v与或图的搜索：与或图的搜索：目的在于表明起始节点是有解的。目的在于表明起始节点是有解的。v可解节点可解节点终叶节点是可解节点（对应于本原问题）。终叶节点是可解节点（对应于本原问题）。如果某个非终叶节点含有如果某个非终叶节点含有或后继节点或后继节点，那么只要当其后，那么只要当其后继节点至少有一个是可解的时，此非终叶节点才是可解继

35、节点至少有一个是可解的时，此非终叶节点才是可解的。的。如果某个非终叶节点含有如果某个非终叶节点含有与后继节点与后继节点，那么只有当其后，那么只有当其后继节点全部为可解时，此非终叶节点才是可解的。继节点全部为可解时，此非终叶节点才是可解的。问题归约法v不可解节点不可解节点没有后裔的非终叶节点为不可解节点。没有后裔的非终叶节点为不可解节点。 如果某个非终叶节点含有如果某个非终叶节点含有或后继节点或后继节点，那么只有当其，那么只有当其全全部后裔为不可解时部后裔为不可解时，此非终叶节点才是不可解的。，此非终叶节点才是不可解的。 如果某个非终叶节点含有如果某个非终叶节点含有与后继节点与后继节点，那么只要

36、当其，那么只要当其后后裔至少有一个为不可解时裔至少有一个为不可解时，此非终叶节点才是不可解的。，此非终叶节点才是不可解的。v解树解树由可解节点所构成，并且由这些可解节点可推出初始节由可解节点所构成，并且由这些可解节点可推出初始节点为可解节点的子树称为解树。点为可解节点的子树称为解树。解树中一定包含初始节点，它对应于原始问题。解树中一定包含初始节点，它对应于原始问题。问题归约法ttttttttt有解节点有解节点无解节点无解节点终叶节点终叶节点与或图例子与或图例子原始问题原始问题有一有一个以上的解个以上的解原始问题原始问题有有解解内容提要1.1.状态空间法状态空间法2.2.问题归约法问题归约法3.

37、3.谓词逻辑法谓词逻辑法4.4.语义网络法语义网络法5.5.其他方法其他方法谓词逻辑法v命题逻辑与谓词逻辑命题逻辑与谓词逻辑v命题命题v命题逻辑的局限性命题逻辑的局限性v谓词谓词谓词逻辑法v命题逻辑与谓词逻辑命题逻辑与谓词逻辑命题逻辑与谓词逻辑是最先用于人工智能的两种逻辑，命题逻辑与谓词逻辑是最先用于人工智能的两种逻辑，对于知识的形式化表示，特别是定理的证明发挥了重对于知识的形式化表示，特别是定理的证明发挥了重要作用要作用虽然命题逻辑能把客观世界的各种事实表示为逻辑命虽然命题逻辑能把客观世界的各种事实表示为逻辑命题，但它具有较大局限性。命题逻辑只能进行命题间题，但它具有较大局限性。命题逻辑只能

38、进行命题间关系关系的推理，无法解决与的推理，无法解决与命题结构命题结构和和成分成分有关的推理有关的推理问题，问题，不适合表示较复杂的问题不适合表示较复杂的问题。谓词逻辑是在命题逻辑的基础上发展而来的，命题逻谓词逻辑是在命题逻辑的基础上发展而来的，命题逻辑可看作是谓词逻辑的一种特殊形式。辑可看作是谓词逻辑的一种特殊形式。谓词逻辑法v命题命题命题是具有真假意义的语句。命题是具有真假意义的语句。命题代表人们进行思维时的一种判断，若命题的意义命题代表人们进行思维时的一种判断，若命题的意义为真，称它的真值为为真，称它的真值为“真真”，记作，记作“T”；若命题的意；若命题的意义为假，称它的真值为义为假，称

39、它的真值为“假假”，记作，记作“F”。例如：。例如：p“西安是陕西省省会西安是陕西省省会”“”“10大于大于6”是真值为是真值为“T”的命题；的命题；p“月亮是方的月亮是方的”“”“煤炭是白的煤炭是白的”是真值为是真值为“F”的命题；的命题；一个命题不能同时即为真又为假，但可以在一定条件一个命题不能同时即为真又为假，但可以在一定条件下为真，在另一种条件下为假。例如：下为真，在另一种条件下为假。例如：p“1+1=10”1+1=10”在二进制情况下为真，十进制情况下为假。在二进制情况下为真，十进制情况下为假。谓词逻辑法v命题命题无真假意义的语句，如感叹句、疑问句等，不是命题。无真假意义的语句，如感

40、叹句、疑问句等，不是命题。通常用大写英文字母表示一个命题，例如：通常用大写英文字母表示一个命题，例如： p P P：西安是座古老的城市：西安是座古老的城市v命题逻辑的局限性？命题逻辑的局限性？客观事物的结构及逻辑特征？客观事物的结构及逻辑特征？不同事物间的共同特征？不同事物间的共同特征？谓词逻辑法v命题逻辑的局限性？命题逻辑的局限性？命题这种表示方法无法反映它所描述的客观事物的结命题这种表示方法无法反映它所描述的客观事物的结构及逻辑特征，也不能表述不同事物间的共同特征。构及逻辑特征，也不能表述不同事物间的共同特征。例如：例如：用字母用字母P P表示表示“小张是老张的儿子小张是老张的儿子”这一命

41、题，这一命题，则无法表述出老张与小张是父子关系。则无法表述出老张与小张是父子关系。例如：例如：“张三是学生张三是学生”，“李四是学生李四是学生”这两个命题，这两个命题，用命题逻辑表示时，无法把两者的共同特征用命题逻辑表示时，无法把两者的共同特征“都是学都是学生生”形式的表示出来。形式的表示出来。可否用可否用 Student（“张三张三”），）， Student（“李四李四”）表示上述命题？表示上述命题？谓词逻辑谓词逻辑谓词逻辑法v谓词谓词在谓词逻辑中，命题是用形如在谓词逻辑中，命题是用形如P(x1,x2,xn)的谓词来表的谓词来表述的。一个谓词可分为述的。一个谓词可分为谓词名谓词名与与个体个体

42、两个部分。两个部分。个体：个体： 是命题的主语，表示独立存在的事物或某个抽是命题的主语，表示独立存在的事物或某个抽象的概念象的概念p “x1,x2,xn”是个体，一般用小写字母表示是个体，一般用小写字母表示p 个体可以是个体常量、变元或函数个体可以是个体常量、变元或函数谓词名：谓词名：表示个体的性质、状态或个体之间的关系表示个体的性质、状态或个体之间的关系p “P”是谓词名，一般用大写字母表示是谓词名，一般用大写字母表示p 称称P 是一个是一个n元谓词。元谓词。谓词逻辑法v谓词谓词命题命题“张三是学生张三是学生” ，用谓词可表示为：，用谓词可表示为：Student（“张张三三”）。其中，）。其

43、中， Student是谓词名，是谓词名，“张三张三”是个体，是个体， Student刻画了刻画了“张三张三”是学生这一特征。是学生这一特征。在谓词中，个体可以是常量、变元或函数。在谓词中，个体可以是常量、变元或函数。例如例如：命题：命题“x10”可表示为可表示为more（x,10），其中），其中x是变元。是变元。又如命题又如命题“小张的父亲是老师小张的父亲是老师”，可表示为，可表示为Teacher（father（Zhang），其中），其中 father（Zhang）是函数。）是函数。当谓词的变元都用特定的个体取代时，谓词就具有一个确当谓词的变元都用特定的个体取代时，谓词就具有一个确定的真值定的

44、真值“T”或或 “F” 。谓词逻辑法v谓词谓词在在n元谓词元谓词 P(x1,x2,xn)中，若每个个体均为常量、变中，若每个个体均为常量、变元或函数，则称它为元或函数，则称它为一阶谓词一阶谓词。如果某个个体本身又是一个一阶谓词，则称它为如果某个个体本身又是一个一阶谓词，则称它为二阶二阶谓词谓词，如此类推。，如此类推。个体变元的取值范围称为个体变元的取值范围称为个体域个体域。个体域可以是有限。个体域可以是有限的，也可以是无限的。例如用的，也可以是无限的。例如用I(x)表示表示“x是整数是整数”，则个体域为所有整数，是无限的。则个体域为所有整数，是无限的。谓词与函数不同谓词与函数不同，谓词的真值是

45、，谓词的真值是 “T”或或 “F”，而函数，而函数的值是个体域中的一个个体，无真值可言。的值是个体域中的一个个体，无真值可言。谓词逻辑法v谓词演算谓词演算谓词逻辑语言的语法和语义谓词逻辑语言的语法和语义p谓词逻辑语言的基本符号：谓词逻辑语言的基本符号：- 谓词符号谓词符号- 变量符号变量符号- 函数符号函数符号- 常量符号常量符号- 括号和逗号括号和逗号谓词逻辑法v谓词演算谓词演算谓词逻辑语言的语法和语义谓词逻辑语言的语法和语义p原子公式：原子公式：原子公式由若干谓词符号和项组成原子公式由若干谓词符号和项组成. .谓词符号谓词符号规定定义域内的一个相应关系规定定义域内的一个相应关系. .常量符

46、号常量符号是最简单的项，表示论域内的物体或实体是最简单的项，表示论域内的物体或实体. .变量符号变量符号也是项，不明确涉及是哪一个实体也是项，不明确涉及是哪一个实体. .函数符号函数符号表示论域内的函数，是从论域内的一个实体表示论域内的函数，是从论域内的一个实体到另外一个实体的映射到另外一个实体的映射. .例如：原子公式例如：原子公式 Married father(LI) , Married father(LI) , mother(LI) mother(LI) 表示表示“李（李（LILI）的父亲和他的母亲结婚）的父亲和他的母亲结婚”谓词逻辑法连词和量词连词和量词p连词连词合取：合取：符号符号“

47、 ” ”， 表示所连结的两个命题之间表示所连结的两个命题之间具有具有“与与”的关系。的关系。析取：析取： 符号符号“ ”“ ”，表示所连结的两个命题之间，表示所连结的两个命题之间具有具有“或或”的关系。的关系。蕴涵：蕴涵：符号符号“ ”“ ”，表示，表示“若若则则”的语义。的语义。PQPQ读作读作“如果如果P P，则，则Q”Q”其中其中P P称为条件的前件，称为条件的前件，Q Q称称为条件的后件。为条件的后件。非：非：符号符号“ ” ”，表示对其后面的命题的否定。，表示对其后面的命题的否定。双条件：双条件：符号符号“ ” ”，表示，表示“当且仅当当且仅当”的语义。的语义。 P PQ Q读作读作

48、“P P当且仅当当且仅当Q”Q”。谓词逻辑法连词和量词连词和量词p量词量词全称量词：全称量词：符号符号“ ”，意思是意思是“所有的所有的”、“任一个任一个”。 x x读作读作“对一切对一切x”,x”,或或“对每一对每一x”x”，或，或“对任一对任一x”x”。命题命题( ( x)P(x)x)P(x)为真，当且仅当对论域中的所为真，当且仅当对论域中的所有有x x，都有，都有P(x)P(x)为真。为真。命题命题( ( x)P(x)x)P(x)为假，当且仅当至少存在论域为假，当且仅当至少存在论域中的一个中的一个x x，使得，使得P(x)P(x)为假。为假。谓词逻辑法连词和量词连词和量词p量词量词存在量

49、词：存在量词：符号符号“ ”，意思是意思是“至少有至少有”、“存在存在” ” 。 x x读作读作“存在一个存在一个x”,x”,或或“对某些对某些x”x”，或，或“至少有一至少有一x”x”。命题命题( ( x)P(x)x)P(x)为真，当且仅当至少存在论域为真，当且仅当至少存在论域中的一个中的一个x x，使得，使得P(x)P(x)为真。为真。命题命题( ( x)P(x) x)P(x)为假，当且仅当对论域中的所为假，当且仅当对论域中的所有有x x，都有，都有P(x)P(x)为假为假 。谓词逻辑法v谓词公式谓词公式原子谓词公式：原子谓词公式：p是由谓词符号和若干项组成的谓词演算。是由谓词符号和若干项

50、组成的谓词演算。p若若t1,t2,tn是项，是项，P是谓词，则称是谓词，则称P(t1,t2,tn)为原子谓词公式。为原子谓词公式。分子谓词公式：分子谓词公式：p可以用连词把原子谓词公式组成复合谓词公式，并把它叫做分可以用连词把原子谓词公式组成复合谓词公式，并把它叫做分子谓词公式。子谓词公式。谓词逻辑法v谓词公式谓词公式合式公式（合式公式（WFF，Well-formed Formulas）：）：通常把通常把合合式公式式公式叫做叫做谓词公式谓词公式，递归定义如下：，递归定义如下：p(1) 原子谓词公式是合式公式原子谓词公式是合式公式p(2) 若若A为合式公式，则为合式公式，则 A也是一个合式公式也

51、是一个合式公式p(3) 若若A,B是合式公式，则是合式公式，则AB，AB，AB，AB也都是合式公式也都是合式公式p(4) 若若A是合式公式，是合式公式，x为为A中的自由变元，则中的自由变元，则 ( x)A和和( x)A都是合式公式都是合式公式p(5) 只有按上述规则只有按上述规则(1)至至(4)求得的那些公式，才是合式求得的那些公式，才是合式公式。公式。谓词逻辑法v谓词公式谓词公式用谓词公式表示知识时，需要首先用谓词公式表示知识时，需要首先定义谓词定义谓词，然后再，然后再用用连接词连接词把有关的谓词连接起来，形成一个谓词公式把有关的谓词连接起来，形成一个谓词公式表达一个完整的意义。表达一个完整

52、的意义。 例例1：设有下列知识设有下列知识 刘欢比他父亲出名。刘欢比他父亲出名。 高扬是计算机系的一名学生，但他不喜欢编程高扬是计算机系的一名学生，但他不喜欢编程 。 任何整数或者为正或者为负。任何整数或者为正或者为负。为了用谓词公式表示上述知识，首先需要定义谓词：为了用谓词公式表示上述知识，首先需要定义谓词： FAMOUS (x, y) : x比比y出名出名 COMPUTER ( x ) : x 是计算机系的是计算机系的 LIKE (x, y ) : x 喜欢喜欢 y谓词逻辑法 I(x)表示表示“x是整数是整数” P(x)表示表示“x是正数是正数” N(x)表示表示“x是负数是负数” 此时可

53、用谓词公式把上述知识表示为此时可用谓词公式把上述知识表示为: 刘欢比他父亲出名刘欢比他父亲出名: FAMOUS ( liuhuan, father ( liuhuan ) 高扬是计算机系的一名学生，但他不喜欢编程高扬是计算机系的一名学生，但他不喜欢编程 : COMPUTER(gaoyang)LIKE(gaoyang, programing) 任何整数或者为正或者为负任何整数或者为正或者为负: ( x)(I(x) (P(x) N(x)谓词逻辑法v谓词公式谓词公式例例2：用谓词逻辑描述右图中的房子的概念用谓词逻辑描述右图中的房子的概念p个体个体 ：A , Bp谓词谓词 ：SUPPORT( x,y

54、)：表示：表示 x 被被 y支撑着支撑着 WEDGE ( x )：表示：表示 x 是楔形块是楔形块 BRICK( y )：表示：表示 y 是长方块是长方块 p其中其中 x , y是个体变元，它们的个体域是个体变元，它们的个体域A,Bp房子的概念可以表示成一组合式谓词公式的合取式：房子的概念可以表示成一组合式谓词公式的合取式： SUPPORT(A,B) WEDGE( A ) BRICK( B )谓词逻辑法v合式公式的性质合式公式的性质若若P、Q是两个合式公式，则由这两个合式公式所组成是两个合式公式，则由这两个合式公式所组成的复合表达式可由下列真值表给出。的复合表达式可由下列真值表给出。PQPPQ

55、PQPQPQTTFTTTTTFFTFFFFTTTFTFFFTFFTT谓词逻辑法v合式公式的性质合式公式的性质如果两个合式公式，无论如何解释，其真值表都是相如果两个合式公式，无论如何解释，其真值表都是相同的，那么我们就称此两合式公式是同的，那么我们就称此两合式公式是等价的等价的。应用上述真值表可以确立下列等价关系：应用上述真值表可以确立下列等价关系：p（1）否定之否定：）否定之否定： ( P ) = Pp（2）( P Q ) = ( P Q ) 或者或者 ( P Q ) = ( P Q ）p（3）狄）狄 摩根定律：摩根定律： ( P Q ) = P Q ( P Q ) = P Q谓词逻辑法p（4

56、）分配律：）分配律： P ( Q R ) = ( P Q ) ( P R ) P ( Q R ) = ( P Q ) ( P R )p（5）交换律：）交换律： P Q = Q P P Q = Q Pp（6）结合律：）结合律： P ( Q R ) = ( P Q ) R P ( Q R ) = ( P Q ) Rp（7）逆否率：）逆否率： ( P Q ) = ( Q P ) 谓词逻辑法p（8）泛界律：）泛界律： P F = P , P T = P P F = F , P T = T p（9）互余律：）互余律： P P = T, P P = F此外还可以确立下列等价关系：此外还可以确立下列等价关系

57、：p ( x) P(x) = ( x) P(x) p ( x) P(x) = ( x) P(x) p ( x) P(x) Q(x) = ( x) P(x) ( x) Q(x)p ( x) P(x) Q(x) = ( x) P(x) ( x) Q(x) p ( x) P(x) = ( y) P(y) p ( x) P(x) = ( y) P(y) 谓词逻辑法v置换与合一置换与合一置换置换p 推理规则：推理规则：用合式公式的集合产生新的合式公式用合式公式的集合产生新的合式公式 假元推理：假元推理： 全称化推理：全称化推理： 综合推理：综合推理：由合式公式由合式公式W1和和W1 W2产生合式公式产生

58、合式公式W2 W(A)( x) W(x) 任意常量任意常量A W2(A) W1(A)( x) W1(x) W2(x)寻找寻找A对对x的的置置换换，使，使W1(A)与与W1(x)一致一致谓词逻辑法v置换与合一置换与合一置换（置换（SubstitutionSubstitution）p置换的定义：置换的定义：置换是用置换是用变元、常量、函数变元、常量、函数来替换来替换变变元元，使该变元不在公式中出现使该变元不在公式中出现。p置换是形如置换是形如 t1/x1, t2/x2, ， tn/xn的有限集合。的有限集合。 t1，t2， ， tn是项是项 x1，x2， ， xn是互不相同的变元是互不相同的变元

59、ti/xi表示用表示用ti项替换变元项替换变元xi，不允许，不允许ti和和xi相同，也相同，也不允许变元不允许变元xi循环地出现在另一个循环地出现在另一个tj中中谓词逻辑法v置换与合一置换与合一置换（置换（SubstitutionSubstitution）p例例2.2（P37），表达式），表达式 Px, 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所得到的表达式的置所得到的表达式的置换。于是，换。于是，Px, f(y), B的的4个置换如下：

60、个置换如下： Px, f(y), B s1 = Pz, f(w), B Px, f(y), B s2 = Px, f(A), B Px, f(y), B s3 = Pq(z), f(A), B Px, f(y), B s4 = Pc, f(A), B 谓词逻辑法v置换与合一置换与合一置换（置换（SubstitutionSubstitution）p置换是可结合的置换是可结合的用用s1s2表示两个置换表示两个置换s1和和s2的的合成合成，L表示一个表达表示一个表达式，则有式，则有 （Ls1）s2 = L（s1s2 ） 即用即用s1和和s2相继作用于表达式相继作用于表达式L是与用是与用s1s2作用于