人工智能课件之知识表示方法.pptx

《人工智能课件之知识表示方法.pptx》由会员分享，可在线阅读，更多相关《人工智能课件之知识表示方法.pptx（230页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二节第二节 知识表示方法知识表示方法内容提要：内容提要：状态空间法状态空间法 问题归约法问题归约法 谓词逻辑法谓词逻辑法 语义网络法语义网络法 其他方法其他方法培训专用前言 在学习本章内容之前，我们先了解一在学习本章内容之前，我们先了解一下有关知识及其表示的概念。下有关知识及其表示的概念。人类的智能活动过程主要是一个获得人类的智能活动过程主要是一个获得并运用知识的过程，知识是智能的基础。并运用知识的过程，知识是智能的基础。为了使计算机具有智能，就必须使它具为了使计算机具有智能，就必须使它具有知识。有知识。那什么是知识呢？那什么是知识呢？培训专用知识一般概念知识一般概念 知识是人们在改造客观世

2、界的实践中积累起来的知识是人们在改造客观世界的实践中积累起来的认识认识和和经验经验 认识：认识：包括对事物现象、本质、属性、状态、关系、联系和运动等的认识包括对事物现象、本质、属性、状态、关系、联系和运动等的认识 经验：经验：包括解决问题的包括解决问题的微观方法：微观方法：如步骤、操作、规则、过程、技巧等如步骤、操作、规则、过程、技巧等 宏观方法：宏观方法：如战略、战术、计谋、策略等如战略、战术、计谋、策略等知识的有代表性的定义知识的有代表性的定义 （1 1）Feigenbaum:Feigenbaum:知识是经过剪裁、塑造、解释、选择和转换了的信息知识是经过剪裁、塑造、解释、选择和转换了的信息

3、 （2 2）BernsteinBernstein：知识由特定领域的描述、关系和过程组成知识由特定领域的描述、关系和过程组成 （3 3）Heyes-RothHeyes-Roth：知识知识=事实事实+信念信念+启发式启发式知识、信息、数据及其关系知识、信息、数据及其关系 数据数据是信息的载体，本身无确切含义，其关联构成信息是信息的载体，本身无确切含义，其关联构成信息 信息信息是数据的关联，赋予数据特定的含义，仅可理解为描述性知识是数据的关联，赋予数据特定的含义，仅可理解为描述性知识 知识知识可以是对信息的关联，也可以是对已有知识的再认识可以是对信息的关联，也可以是对已有知识的再认识 常用的关联方式

4、：常用的关联方式：if then if then 培训专用什么是知识什么是知识?一般来说，我们把一般来说，我们把有关信息关联在一起所形成的信有关信息关联在一起所形成的信有关信息关联在一起所形成的信有关信息关联在一起所形成的信息结构称为知识。知识表示就是对知识的一种描述，息结构称为知识。知识表示就是对知识的一种描述，息结构称为知识。知识表示就是对知识的一种描述，息结构称为知识。知识表示就是对知识的一种描述，一种计算机可以接受的用于描述知识的数据结构一种计算机可以接受的用于描述知识的数据结构一种计算机可以接受的用于描述知识的数据结构一种计算机可以接受的用于描述知识的数据结构。知知识反映了客观世界中

5、事物之间的关系。识反映了客观世界中事物之间的关系。例如，例如，例如，例如，雪雪是白色的、鸟有翅膀等都是知识是白色的、鸟有翅膀等都是知识培训专用知识的要素知识的要素知识的要素是指构成知识的必需元素。在这里，我们知识的要素是指构成知识的必需元素。在这里，我们关心的是一个人工智能系统所处理的知识的组成成分。关心的是一个人工智能系统所处理的知识的组成成分。一般而言，人工智能系统的知识包含事实、规则、控一般而言，人工智能系统的知识包含事实、规则、控制和元知识。制和元知识。培训专用知识的要素知识的要素事实：事物的分类、属性、事物间关系、科学事实、事实：事物的分类、属性、事物间关系、科学事实、客观事实等客观

6、事实等.是有关问题环境的一些事物的知识，常以是有关问题环境的一些事物的知识，常以“是是”形式出现，也是最低层的知识。例如：雪是白色形式出现，也是最低层的知识。例如：雪是白色的，人有四肢。的，人有四肢。规则：事物的行动、动作和联系的因果关系知识。规则：事物的行动、动作和联系的因果关系知识。这种知识是动态的，常以这种知识是动态的，常以“如果如果那么那么”形式出现。例如形式出现。例如启发式规则，如果下雨，则出门带伞。启发式规则，如果下雨，则出门带伞。培训专用知识的要素知识的要素控制：当有多个动作同时被激活时，选择哪一个动控制：当有多个动作同时被激活时，选择哪一个动作来执行的知识。是有关问题的求解步骤

7、、规划、求作来执行的知识。是有关问题的求解步骤、规划、求解策略等技巧性知识解策略等技巧性知识.元知识：怎样使用规则、解释规则、校验规则、解元知识：怎样使用规则、解释规则、校验规则、解释程序结构等知识。是有关知识的知识，是知识库中释程序结构等知识。是有关知识的知识，是知识库中的高层知识。元知识与控制知识有时有重叠的高层知识。元知识与控制知识有时有重叠.培训专用知识的分类知识的分类根据根据知识表达的内容知识表达的内容，将其简单地分为如下几类：，将其简单地分为如下几类：事实性知识事实性知识知识的一般直接表示，如果事实性知识是批量的、有规律的，则往往以表格、知识的一般直接表示，如果事实性知识是批量的、

8、有规律的，则往往以表格、图册，甚至数据库等形式出现。图册，甚至数据库等形式出现。这种知识描述一般性的事实，如凡是冷血动物都要冬眠，哺乳动物都是胎生繁这种知识描述一般性的事实，如凡是冷血动物都要冬眠，哺乳动物都是胎生繁殖后代等。殖后代等。过程性知识过程性知识表述做某件事的过程。标准程序库也是常见的过程性知识，而且是系列表述做某件事的过程。标准程序库也是常见的过程性知识，而且是系列化、配套的。化、配套的。如电视机维修法，怎样烹制法国大餐等。如电视机维修法，怎样烹制法国大餐等。行为性知识行为性知识不直接给出事实本身，只给出它在某方面的行为。行为性知识经常表示为某种数不直接给出事实本身，只给出它在某方

9、面的行为。行为性知识经常表示为某种数学模型，从某种意义上讲，行为性知识描述的是事物的内涵，而不是外延。如微分方学模型，从某种意义上讲，行为性知识描述的是事物的内涵，而不是外延。如微分方程程培训专用知识的分类知识的分类实例性知识实例性知识只给出一些实例。知识藏在实例中。感兴趣的不是实例本身，而是隐藏在大量实例中的规律性知识。类比性知识类比性知识既不给出外延，也不给出内涵，只给出它与其它事物的某些相似之处。类比性知识一般不能完整地刻画事物，但它可以启发人们在不同的领域中做到知识的相似性共享。如比喻，心如刀绞，谜语等元知识元知识有关知识的知识。最重要的元知识是如何使用知识的知识。例如，一个好的专家系

10、统应该知道自己能回答什么问题，不能回答什么问题，这就是关于自己知识的知识。元知识是用于如何从知识库中找到想要的知识。培训专用按知识的性质按知识的性质 概念、命题、公理、定理、规则和方法概念、命题、公理、定理、规则和方法按知识的作用域按知识的作用域 常识性知识：常识性知识：通用通识的知识。人们普遍知道的、适应所有领域的知识。通用通识的知识。人们普遍知道的、适应所有领域的知识。领域性知识：领域性知识：面向某个具体专业领域的知识。面向某个具体专业领域的知识。例如：例如：专家经验。专家经验。按知识的层次按知识的层次 表层知识：表层知识：描述客观事物的现象的知识。例如：感性、事实性知识描述客观事物的现象

11、的知识。例如：感性、事实性知识 深层知识：深层知识：描述客观事物本质、内涵等的知识。例如：理论知识描述客观事物本质、内涵等的知识。例如：理论知识按知识的确定性按知识的确定性 确定性知识：确定性知识：可以说明其真值为真或为假的知识可以说明其真值为真或为假的知识 不确定性知识：不确定性知识：包括不精确、模糊、不完备知识包括不精确、模糊、不完备知识 不精确：不精确：知识本身有真假，但由于认识水平限制却不能肯定其真假知识本身有真假，但由于认识水平限制却不能肯定其真假 表示：用可信度、概率等描述表示：用可信度、概率等描述 模糊：模糊：知识本身的边界就是不清楚的。例如：大，小等知识本身的边界就是不清楚的。

12、例如：大，小等 表示：用可能性、隶属度来描述表示：用可能性、隶属度来描述 不完备：不完备：解决问题时不具备解决该问题的全部知识。例如：医生看病解决问题时不具备解决该问题的全部知识。例如：医生看病培训专用每种以每种以知识和符号操作知识和符号操作为基础的智能系统，其问题为基础的智能系统，其问题求解方法都需要某种对解答的搜索。求解方法都需要某种对解答的搜索。在搜索过程开始之前，必须先用某种方法或某几在搜索过程开始之前，必须先用某种方法或某几种方法的混和来表示问题。种方法的混和来表示问题。问题求解技术主要涉及两个方面：问题的表示 求解的方法知识表示知识表示方式是学习人工智能的中心内容之一。方式是学习人

13、工智能的中心内容之一。知识表示知识表示培训专用知识表示的概念知识表示的概念什么是知识表示什么是知识表示 是对知识的描述，即用一组符号把知识编码成计算机可以接受的某种结构。其是对知识的描述，即用一组符号把知识编码成计算机可以接受的某种结构。其表示方法不唯一。表示方法不唯一。知识表示的要求知识表示的要求 表示能力：表示能力：能否正确、有效地表示问题。包括：能否正确、有效地表示问题。包括：表示范围的广泛性表示范围的广泛性 领域知识表示的高效性领域知识表示的高效性 对非确定性知识表示的支持程度对非确定性知识表示的支持程度 可利用性：可利用性：可利用这些知识进行有效推理。包括：可利用这些知识进行有效推理

14、。包括：对推理的适应性：对推理的适应性：推理是根据已知事实利用知识导出结果的过程推理是根据已知事实利用知识导出结果的过程 对高效算法的支持程度：对高效算法的支持程度：知识表示要有较高的处理效率知识表示要有较高的处理效率 可实现性：可实现性：要便于计算机直接对其进行处理要便于计算机直接对其进行处理 可组织性：可组织性：可以按某种方式把知识组织成某种知识结构可以按某种方式把知识组织成某种知识结构 可维护性：可维护性：便于对知识的增、删、改等操作便于对知识的增、删、改等操作 自然性：自然性：符合人们的日常习惯符合人们的日常习惯 可理解性：可理解性：知识应易读、易懂、易获取等知识应易读、易懂、易获取等

15、 培训专用知识表示的一般方法知识表示的一般方法状态空间法状态空间法问题归约法问题归约法谓词逻辑法谓词逻辑法语义网络语义网络另外还有框架表示以及剧本表示另外还有框架表示以及剧本表示,过程表示过程表示,这里这里不在一一详述不在一一详述.在表示和求解比较复杂的问题时在表示和求解比较复杂的问题时,采用单一的表示方法采用单一的表示方法是不够的是不够的,往往采用多种方法的混合表示往往采用多种方法的混合表示.目前这仍是人目前这仍是人工智能专家感兴趣的研究方向工智能专家感兴趣的研究方向.培训专用状态空间法状态空间法问题求解(problem solving)是个大课题，它涉及归约、推断、决策、规划、常识推理、定

16、理证明和相关过程的核心概念。在分析了人工智能研究中.运用的问题求解方法之后，就会发现许多问题求解方法是采用试探搜索方法的。也就是说，这些方法是通过在某个可能的解空间内寻找一个解来求解问题的。这种基于解答空间的问题表示和求解方法就是状态空间法，它是以状态和算符(operator)为基础来表示和求解问题的。培训专用状态空间法问题求解技术主要涉及两个方面：问题求解技术主要涉及两个方面：问题的表示问题的表示 求解的方法求解的方法 状态空间法状态空间法 状态状态（StateState）算符算符（Operator)Operator)状态空间方法状态空间方法（Method on State Space)Me

17、thod on State Space)培训专用状态状态状态（状态（statestate）：）：描述某类不同事物间的差别而引入的一组最少变量 q q0 0 q q1 1，q qn n的有序集合.矢量形式：矢量形式：Q=q q0 0,q q1 1,q qn n T T 式中每个元素q qi i为集合的分量，称为状态变量。给定每个分量的一组值就得到一个具体的状态，如 Q Qk k=q qk k,q q1k,q qnk 培训专用算符（算符（operatoroperator）：把问题从一种状态变换）：把问题从一种状态变换为另一种状态的手段为另一种状态的手段.算算符可为走步、过程、规则、数学算子、运算符

18、号或逻辑符号等。算符算符培训专用状态空间方法：基于状态空间方法：基于解答空间的问题表示和求解答空间的问题表示和求解方法解方法，它是以，它是以状态和算符状态和算符为基础来表示和求为基础来表示和求解问题的。解问题的。它包含三种说明的集合,即三元状态（S S，F F，G G）S S 初始状态集合；F F 操作符集合；G G 目标状态集合。培训专用对一个问题的状态描述，必须确定对一个问题的状态描述，必须确定3 3件事：件事：(1)(1)该状态描述方式，特别是初始状态描述；该状态描述方式，特别是初始状态描述；(2)(2)操作符集合及其对状态描述的作用；操作符集合及其对状态描述的作用；(3)(3)目标状态

19、描述的特性目标状态描述的特性培训专用状态空间表示状态空间表示典型的例子:下棋、迷宫及各种游戏。培训专用三数码难题问题描述问题描述:三数码难题三数码难题:有有3 3个编有个编有1-31-3并放在并放在2X22X2方格棋方格棋盘上可走动的棋子组成盘上可走动的棋子组成.棋盘上总有一个空棋盘上总有一个空格格,以便让空格周围的棋子走进来以便让空格周围的棋子走进来.直至从初直至从初始状态到达目标状态始状态到达目标状态.培训专用三数码难题培训专用八数码难题 初始棋局 目标棋局培训专用表示制定操作算符集：*直观方法为每个棋牌制定一套可能的走步：左、上、右、下四种移动。这样就需32个操作算子。*简易方法仅为空格

20、制定这4种走步，因为只有紧靠空格的棋牌才能移动。*空格移动的唯一约束是不能移出棋盘。根据问题状态、操作算符和目标条件选择各种表示，是高效率求解必须的。在问题求解过程中，会不断取得经验，获得一些简化的表示。培训专用从初始棋局开始，试探由每一合法走步得到的各种新棋局，然后计算再走一步而得到的下一组棋局。这样继续下去，直至达到目标棋局为止。把初始状态可达到的各状态所组成的空把初始状态可达到的各状态所组成的空间设想为一幅由各种状态对应的节点组间设想为一幅由各种状态对应的节点组成的图。这种图称为状态图成的图。这种图称为状态图。图中每个节点标有它所代表的棋局。首先把适用的算符用于初始状态，以产生新的状态；

21、然后，再把另一些适用算符用于这些新的状态；这样继续下去，直至产生目标状态为止。八数码难题部分状态图培训专用十五数码难题(思考)初始状态初始状态目标状态目标状态培训专用状态空间的图示形式称为状态空间图。状态空间的图示形式称为状态空间图。有向图(directed graph)(directed graph)图:由节点（不一定是有限的节点）的集合构成。有向图:是指图中的一对节点用弧线连接起来，从一个 节点指向另一个节点。路径 某个节点序列（n ni1i1,n,ni2i2,n,nikik）当j=2,3j=2,3,k k时，如果 对于每一个n nij-1ij-1都有一个后继节点n nijij存在，那么就

22、把这 个节点序列叫做从节点，n ni1i1至至节点n nikik的长度为k k的路 径。状态图示法培训专用寻找从一种状态变换为另一种状态的某个算符序列问题就等价于寻寻找从一种状态变换为另一种状态的某个算符序列问题就等价于寻求图的某一路径的问题求图的某一路径的问题.代价:加在各弧线的指定数值，以表示加在相应算符上的代价。两个节点间路径的代价等于连接该路径上各节点的所有弧线的代价之和.图的显示说明:指各节点及其具有代价的弧线可以由一张表明确给出,(可以列出每一个节点,其后继节点以及连接弧线上的代价)图的隐示说明 指各节点及其具有代价的弧线不可以由一张表明确给出.(起始节点后继节点算符已知,把后继算

23、符应用于各节点，以扩展节点）状态图示法状态图示法培训专用状态空间表示举例培训专用问题描述问题描述在一个房间内有一只猴子在一个房间内有一只猴子(可把这只猴子看做一个机可把这只猴子看做一个机器人器人)、一个箱子和一束香蕉。香蕉挂在天花板下、一个箱子和一束香蕉。香蕉挂在天花板下方，但猴子的高度不足以碰到它。那么这只猴子方，但猴子的高度不足以碰到它。那么这只猴子怎样才能摘到香蕉呢怎样才能摘到香蕉呢?培训专用用一个四元表列（用一个四元表列（W W，x x，Y Y，z z）来表示问题）来表示问题状态状态.其中：其中：W-W-猴子的水平位置；猴子的水平位置；x x当猴子在箱子顶上时当猴子在箱子顶上时取取x=

24、1x=1；否则取；否则取x=0 x=0；Y Y箱子的水平位置；箱子的水平位置；z-z-当猴子当猴子摘到香蕉时取摘到香蕉时取z=1z=1；否则取；否则取z=0z=0。解题过程培训专用操作（算符）：操作（算符）：培训专用该初始状态变换为目标状态的操作序列为：该初始状态变换为目标状态的操作序列为：goto(b),pushbox(c),climbbox,grasp goto(b),pushbox(c),climbbox,grasp 培训专用U=b=c培训专用状态空间表示举例产生式系统（产生式系统（ProductionSystem）一个总数据库一个总数据库(global database)：它含有与具体

25、任务有关的信息；随着应用情况的不同，这些数据库可能小得像数字矩阵那样简单，或许大得如检索文件结构那么复杂。一套规则一套规则：它对数据库进行操作运算。每条规则由左右两部分组成，左部鉴别规则的适用性或先决条件，右部描述规则应用时所完成的动作。应用规则来改变数据库，就象应用算符来改变状态一样。一个控制策略一个控制策略：它确定应该采用哪一条适用规则，而且当数据库的终止条件满足时，就停止计算。控制策略由控制系统选择和确定。培训专用产生式系统产生式系统例:推销员旅行问题从城市A出发,访问每个城市一次且仅一次,返回城市A.总数库:到目前为止访问过的城市表.规则:从一个城市达到另一个城市,规则的要求是必须是合

26、法的数据库.(任一城市出现不能多余一次,只到所有城市出现后,才能出现A)任一个以A为起点的和终点的总数据库都满足终止条件.这种图搜索控制策略将在第三章讨论.培训专用推销员旅行问题例2.1 推销员旅行问题（旅行商问题）一个推销员计划出访推销产品。他从一个城市（如A）出发，访问每个城市一次，且最多一次，然后返回城市A。要求寻找最短路线。培训专用推销员旅行问题状态描述：目前为止访问过的城市列表（A）初始状态：（A）目标状态：（AA）培训专用39推销员旅行问题 图2.4 推销员旅行问题状态空间图算符：下一步走向的城市(a)(b)(c)(d)(e)约束：每个城市只能走过一次，A除外培训专用作业（p54）

27、2-3 利用图2.3，用状态空间法规划一个最短的旅行路程：此旅程从城市A开始，访问其他城市不多于一次，并返回A。选择一个状态表示，表示出所求得的状态空间的节点及弧线，标出适当的代价，并指明图中从起始节点到目标节点的最佳路径。培训专用问题归约法问题归约法已知问题的描述，通过一系列变换把此问题最终变已知问题的描述，通过一系列变换把此问题最终变为一个子问题集合；这些子问题的解可以直接得到，为一个子问题集合；这些子问题的解可以直接得到，从而解决了初始问题。从而解决了初始问题。该方法也就是从该方法也就是从目标目标(要解决的问题要解决的问题)出发逆向推理，建出发逆向推理，建立子问题以及子问题的子问题，直至

28、最后把初始问题归立子问题以及子问题的子问题，直至最后把初始问题归约为一个平凡的本原问题集合约为一个平凡的本原问题集合。这就是问题归约的实质。这就是问题归约的实质。培训专用问题归约法的组成部分问题归约法的组成部分（1 1）一个初始问题描述；）一个初始问题描述；（2 2）一套把问题变换为子问题的操作符；）一套把问题变换为子问题的操作符；（3 3）一套本原问题描述。）一套本原问题描述。培训专用问题规约法图解问题规约法图解培训专用梵塔难题梵塔难题有有3 3个个柱柱子子(1(1，2 2，3)3)和和3 3个个不不同同尺尺寸寸的的圆圆盘盘(A(A，B B，C)C)。在在每每个个圆圆盘盘的的中中心心有有个个

29、孔孔，所所以以圆圆盘盘可可以以堆堆叠叠在在柱柱子子上。上。最最初初，全全部部3 3个个圆圆盘盘都都堆堆在在柱柱子子1 1上上：最最大大的的圆圆盘盘C C在在底底部，最小的圆盘部，最小的圆盘A A在顶部。在顶部。要要求求把把所所有有圆圆盘盘都都移移到到柱柱子子3 3上上，每每次次只只许许移移动动一一个个，而而且且只只能能先先搬搬动动柱柱子子顶顶部部的的圆圆盘盘，还还不不许许把把尺尺寸寸较较大的圆盘堆放在尺寸较小的圆盘上大的圆盘堆放在尺寸较小的圆盘上。这个问题的初始配置和目标配置如图所示。这个问题的初始配置和目标配置如图所示。培训专用培训专用梵塔难题梵塔难题(a)初始状态(b)目标状态培训专用分析

30、分析原始问题归约（简化）为三个子问题原始问题归约（简化）为三个子问题1、移动、移动A，B盘至柱子盘至柱子2的双圆盘难题的双圆盘难题2、移动圆盘、移动圆盘C至柱子至柱子3的单圆盘问题的单圆盘问题3、移动、移动A，B盘至柱子盘至柱子3的双圆盘难题的双圆盘难题培训专用分析分析可以用状态空间表示的三元组合可以用状态空间表示的三元组合(S、F、G)来规定与描述问题；对于梵塔问题，子问来规定与描述问题；对于梵塔问题，子问题（题（111）(122)，(122)(322)以及以及(322)(333)规定了最后解答路径规定了最后解答路径将要通过的脚踏石状态将要通过的脚踏石状态(122)和和(322)。培训专用具

31、体解题过程具体解题过程培训专用培训专用与或图与或图一般地，我们用一个类似图的结构来表示把一般地，我们用一个类似图的结构来表示把问题归约为后继问题的替换集合，这种结构问题归约为后继问题的替换集合，这种结构图叫做图叫做问题归约图问题归约图，或叫与或图。，或叫与或图。培训专用与或图表示与或图表示例如，设想问题例如，设想问题A A需要由求解问题需要由求解问题B B、C C和和D D来决定，那么可以用来决定，那么可以用一个与图来表示一个与图来表示 (左图左图)同样，一个问题同样，一个问题A A或者由求解问题或者由求解问题B B、或者由求解问题、或者由求解问题C C来决定，来决定，则可以用一个或图来表示则

32、可以用一个或图来表示(右图右图)培训专用与或图表示与或图表示培训专用培训专用与或图的一些术语与或图的一些术语如果某条弧线从节点a指向节点b，那么节点a叫做节点b的父辈节点；节点b叫做节点a的后继节点或后裔；或节点，只要解决某个问题就可解决其父辈问题的节点集合；与节点，只有解决所有子问题，才能解决其父辈问题的节点集合；弧线，是父辈节点指向子节点的圆弧连线；终叶节点，是对应于原问题的本原节点.培训专用培训专用举例培训专用58与或图构成规则(1)与或图中的每个节点代表一个要解决的单一问题或问题集合。与或图中的每个节点代表一个要解决的单一问题或问题集合。图中所含起始节点对应于原始问题。图中所含起始节点

33、对应于原始问题。(2)对应于本原问题的节点，叫做终叶节点，它没有后裔。对应于本原问题的节点，叫做终叶节点，它没有后裔。(3)对于把算符应用于问题对于把算符应用于问题A的每种可能情况，都把问题变换为一个子问的每种可能情况，都把问题变换为一个子问题集合；有向弧线自题集合；有向弧线自A 指向后继节点表示所求得的子问题集合。指向后继节点表示所求得的子问题集合。(4)一般对于代表两个或两个以上子问题集合的每个节点，有向弧线一般对于代表两个或两个以上子问题集合的每个节点，有向弧线从此节点指向此子问题集合中的各个节点。由于只有当集合中所有的从此节点指向此子问题集合中的各个节点。由于只有当集合中所有的项都有解

34、时，这个子项都有解时，这个子 问题的集合才能获得解答，所以这些子问题节问题的集合才能获得解答，所以这些子问题节点叫做与节点。点叫做与节点。(5)在特殊情况下，当只有一个算符可应用于问题在特殊情况下，当只有一个算符可应用于问题A，而且这个算符产生具，而且这个算符产生具有一个以上子问题的某个集合时，由上述规则有一个以上子问题的某个集合时，由上述规则3和规则和规则4所产生的图可以得所产生的图可以得到简化。因此，代表子问题集合的中间或节点可以被略去。到简化。因此，代表子问题集合的中间或节点可以被略去。培训专用59595959作业P54 2-5试用四元数列结构表示四圆盘梵塔问题，并画出求解该问题的与或图

35、。培训专用培训专用谓词逻辑法知识补充谓词逻辑法知识补充-命题逻辑命题逻辑命题逻辑 逻辑主要研究推理过程，而推理过程必须依靠命题来表达。在命题逻辑中，“命题”被看作最小单位。数理逻辑中最基本、最简单的部分。培训专用命题逻辑命题逻辑什么是命题？命题是陈述客观外界发生事情的陈述句。命题是或为真或为假的陈述句。命题是或为真或为假的陈述句。特征：陈述句真假必居其一,且只居其一.培训专用命题逻辑命题逻辑例1 下列句子是命题吗？8小于10.8大于10.任一个5的偶数可表示成两个素数的和.答：是培训专用命题逻辑例2 下列句子是命题吗？8大于10吗?请勿吸烟.X大于Y.我正在撒谎.悖论答：不是培训专用命题逻辑命

36、题逻辑命题的抽象 以p、q、r等表示命题。以1表示真，0表示假。则命题就抽象为：取值为取值为0或或1的的p等符号等符号。若p取值1，则表示p为真命题；若p取值0，则表示p为假命题；培训专用命题逻辑命题逻辑“复杂命题”例3:由简单命题能构造更加复杂命题(1)期中考试,张三没有考及格.(2)期中考试,张三和李四都考及格了.(3)期中考试,张三和李四中有人考90分.(4)如果张三能考90分,那么李四也能考90分.(5)张三能考90分当且仅当李四也能考90分.培训专用命题逻辑命题逻辑联结词和复合命题 上述诸如“没有”、“如果 那么”等连词称为联结词。由联结词和命题连接而成的更加复杂命题称为复合由联结词

37、和命题连接而成的更加复杂命题称为复合命题；相对地，不能分解为更简单命题的命题称为简命题；相对地，不能分解为更简单命题的命题称为简单命题。单命题。复合命题的真假完全由构成它的简单命题的真假所决定。注：简单命题和复合命题的划分是相对的。培训专用命题逻辑命题逻辑否定联结词 定义1：设设p为一个命题为一个命题,复合命题复合命题“非非p”称为称为p的否定式，记为的否定式，记为p，“”称为否定联结词.“p”为真当且仅当p为假。例3中,若p代表“期中考试张三考及格了”，则(1)“期中考试,张三没有考及格.”可表示为p.培训专用命题逻辑命题逻辑合取联结词 定义2 设设p、q为两个命题，复合命题为两个命题，复合

38、命题“p而且而且q”称为称为p、q的合取的合取式，记为式，记为p q，“”称作合取联结词。pq真当且仅当p与q同时真.例3的(2)“期中考试,张三和李四都考及格了.”可记为pq,其中p代表“张三考及格”,q代表“李四考及格”.培训专用命题逻辑命题逻辑析取联结词 定义定义3设设p、q为两个命题，复合命题为两个命题，复合命题“p或者或者q”称为称为p、q的析取式，的析取式，记为记为p q，“”称作析取联结词称作析取联结词。p q为真当且仅当p与q中至少有一个为真.例3的(3)“期中考试,张三和李四中有人考90分.”可记为p q,其中p代表“张三考90分”,q代表“李四考90分”。培训专用命题逻辑命

39、题逻辑“相容或相容或”与与“相异或相异或”日常语言中“或”有两种标准用法,例如:(1)张三或者李四考了90分.(2)第一节课上数学课或者上英语课.差异在于：当构成它们的简单命题都真时，前者为真，后者却为假。前者称为“相容或”，后者称为“相异或”。前者(“相容或”)可表示为pq，后者却不能。注意：不能见了或就表示为pq。培训专用命题逻辑命题逻辑蕴涵联结词 定义定义4设设p、q为命题为命题,复合命题复合命题“如果如果p,则则q”称为称为p对对q的蕴涵的蕴涵式，记作式，记作pq,其中又称p为此蕴涵式的前件，称q为此蕴涵式的后件，“”称为蕴涵联结词。“p q”假当且仅当p真而q假.pq这样的真值规定有

40、其合理性，也有人为因素。培训专用培训专用培训专用在自然语言中，”如果.“与”“那末.”之间常常是有因果联系的否则就没有意义，但对命题P-Q来说，只要P,Q能够分别确定真值，P-Q即成为命题。此外，自然语言中对“如果.，则.”这样的语句，当前提为假时，结论不管真假，整个 语句的真假无法判断。而在条件命题中，规定为“善意的推定”，即前提为F时，条件命题的真值都取为T.如果雪是黑的，那末太阳从西方出如果雪是黑的，那末太阳从西方出培训专用培训专用在自然语言中，”如果.“与”“那末.”之间常常是有因果联系的否则就没有意义，但对命题P-Q来说，只要P,Q能够分别确定真值，P-Q即成为命题。此外，自然语言中

41、对“如果.，则.”这样的语句，当前提为假时，结论不管真假，整个 语句的真假无法判断。而在条件命题中，规定为“善意的推定”，即前提为F时，条件命题的真值都取为T.如果雪是黑的，那么太阳从西方出如果雪是黑的，那么太阳从西方出培训专用命题逻辑命题逻辑等价联结词 定义定义5设设p、q为命题为命题,复合命题复合命题“p当且仅当当且仅当q”称称作作p、q的等价式的等价式,记作记作pq,“”称作等价联结词。pq真当且仅当p、q同时为真或同时为假.培训专用命题逻辑命题逻辑注意 上述五个联结词来源于日常使用的相应词汇,但并不完全一致，在使用时要注意：以上联结词组成的复合命题的真假值一定要根据它们的定义去理解,而

42、不能据日常语言的含义去理解。不能“对号入座”，如见到“或”就表示为“”。有些词也可表示为这五个联结词，如“但是”也可表示为“”。在今后我们主要关心的是命题间的真假值的关系,而不讨论命题的内容.培训专用命题逻辑命题逻辑命题符号化例4 将下列命题符号化:(1)铁和氧化合,但铁和氮不化合.(2)如果我下班早,就去商店看看,除非我很累.(3)李四是计算机系的学生,他住在312室或313室.培训专用命题逻辑命题逻辑解（解（1）铁和氧化合）铁和氧化合,但铁和氮不化合但铁和氮不化合.p(q)，其中，其中:p代表代表“铁和氧化合铁和氧化合”，q代表代表“铁和氮化合铁和氮化合”。（2）如果我下班早）如果我下班早

43、,就去商店看看就去商店看看,除非我很累除非我很累.(P)q)r，其中，其中:p代表代表“我很累我很累”,q代表代表“我下班早我下班早”,r代表代表“我去商店看看我去商店看看”培训专用命题逻辑命题逻辑（3）李四是计算机系的学生）李四是计算机系的学生,他住在他住在312室或室或313室室.p(q r)(q r)，其中：，其中：p代表代表“李四是计算机系学生李四是计算机系学生”,q代表代表“李四住李四住312室室”,r代表代表“李四住李四住313室室”.还可表示为：还可表示为：p(q(r)(q)r)培训专用命题逻辑命题逻辑命题公式及其解释命题公式及其解释原子公式原子公式：单个命题变元、单个命题常元称

44、为原子公式。：单个命题变元、单个命题常元称为原子公式。命题公式命题公式：由如下规则生成的公式称为命题公式：由如下规则生成的公式称为命题公式：1.1.单个原子公式是命题公式。单个原子公式是命题公式。2.2.若若A,BA,B是命题公式，则是命题公式，则A,AA,A B,AB,A B,A B,A B,A B,A B B是公式。是公式。3.3.所有命题公式都是有限次应用所有命题公式都是有限次应用1 1、2 2得到的符号串。得到的符号串。培训专用命题逻辑命题逻辑命题公式的命题公式的解释解释：给命题公式中的每一个命题变元指：给命题公式中的每一个命题变元指定一个真假值，这一组真假值，就是命题公式的一个定一个

45、真假值，这一组真假值，就是命题公式的一个解释。用解释。用I I表示。表示。例如：公式例如：公式G=(G=(A A B)B)C C 的一个解释是：的一个解释是：I I1 1(G)=A/T,B/F,C/T(G)=A/T,B/F,C/T 在解释在解释I I1 1(G)(G)下下G G为真。为真。永真公式与永假公式永真公式与永假公式：如果公式在它所有的解释：如果公式在它所有的解释I I下，下，其值都为其值都为T T，则称公式，则称公式G G为恒真的；如果其值都为为恒真的；如果其值都为F F，则，则称公式称公式G G为恒假的（不可满足的）。为恒假的（不可满足的）。培训专用命题逻辑命题逻辑注意：注意：关于

46、五个联结词的约定关于五个联结词的约定：*结合力的强弱顺序：结合力的强弱顺序：，*联结词相同时，从左至右运算。联结词相同时，从左至右运算。解释的个数解释的个数：如果一个公式：如果一个公式G G中有中有n n个不同的原子公式（或个不同的原子公式（或简称原子），则简称原子），则G G有有2 2n n个不同的解释，于是个不同的解释，于是G G在在2 2n n个解释下个解释下有有2 2n n个真值。如果将这些真值和它们的解释列成表，就是个真值。如果将这些真值和它们的解释列成表，就是G G的真值表。的真值表。培训专用命题逻辑命题逻辑等价命题公式等价命题公式 如果两个命题公式所含原子公式相同，且在任一解释下

47、，如果两个命题公式所含原子公式相同，且在任一解释下，两个命题公式的值相同两个命题公式的值相同，则称这两个命题公式为等价命题公，则称这两个命题公式为等价命题公式或等价公式。常用的等价公式有：式或等价公式。常用的等价公式有：1.(P Q)=(P Q)(Q P)2.(P Q)=(P Q)3.(P)=P4.交换律：P Q=Q P P Q=Q P培训专用7.泛界律：P F=P,P T=P P F=F,P T=T 8.互余律：P P=T,P P=F9.德 摩根定律：(P Q)=P Q (P Q)=P Q5.结合律：P(Q R)=(P Q)R P (Q R)=(P Q)R6.分配律：P(Q R)=(P Q)

48、(P R)P (Q R)=(P Q)(P R)命题逻辑命题逻辑培训专用证明两个公式等价，可用真值表，也可用基本公式。证明两个公式等价，可用真值表，也可用基本公式。例如例如 要证明公式要证明公式 P Q=Q P证 P Q=P Q=P (Q)=(Q)P=Q P命题逻辑命题逻辑培训专用永真蕴涵式永真蕴涵式 若命题公式若命题公式G G H H是恒真的是恒真的，称其为永真蕴涵式。记为，称其为永真蕴涵式。记为G GH H，读做，读做“G G蕴涵蕴涵H”H”，也称，也称“G G是是H H的逻辑结果的逻辑结果”。培训专用培训专用永真蕴涵式永真蕴涵式常用的永真蕴涵式：1.P P Q 证P P Q=P (P Q)

49、=P P Q=T Q=T2.P Q P证P Q P=(P Q)P=P Q P=T Q=T培训专用3.P (P Q)Q4.(P Q)Q P5.P(P Q)Q6.(P Q)(Q R)(P R)7.(P Q)(Q R)(P R)8.(P Q)(R S)(P R Q S)9.(P Q)(Q R)(P R)培训专用在命题逻辑中有一个三段论法：在命题逻辑中有一个三段论法：P:“P:“所有的人都会犯错误所有的人都会犯错误”Q:“Q:“张三是人张三是人”R:“R:“张三会犯错误张三会犯错误”R R应该是应该是P P和和Q Q的的逻辑结论逻辑结论。但在命题逻辑中无法准确表达这。但在命题逻辑中无法准确表达这三个命

50、题的逻辑关系三个命题的逻辑关系。为准确表达此类公式，必须引进谓词和量词的概念为准确表达此类公式，必须引进谓词和量词的概念。因为因为(P(P Q)Q)R R 不是恒真不是恒真的。如：解释的。如：解释:I=P/T,Q/T,R/F I=P/T,Q/T,R/F 则公式为假值则公式为假值F.F.就是说解释就是说解释I I 弄假了此公式。弄假了此公式。命题逻辑命题逻辑培训专用命题逻辑与谓词逻辑命题逻辑与谓词逻辑命题逻辑虽能够把客观世界的各种实事表示命题逻辑虽能够把客观世界的各种实事表示为逻辑命题，但具有很大局限性，即不适为逻辑命题，但具有很大局限性，即不适合表达比较复杂的问题；而谓词逻辑则允合表达比较复杂