资源描述
第二节第二节 知识表示方法知识表示方法内容提要：内容提要：状态空间法状态空间法 问题归约法问题归约法 谓词逻辑法谓词逻辑法 语义网络法语义网络法 其他方法其他方法前言 在学习本章内容之前，我们先了解一在学习本章内容之前，我们先了解一下有关知识及其表示的概念。下有关知识及其表示的概念。人类的智能活动过程主要是一个获得人类的智能活动过程主要是一个获得并运用知识的过程，知识是智能的基础。并运用知识的过程，知识是智能的基础。为了使计算机具有智能，就必须使它具为了使计算机具有智能，就必须使它具有知识。有知识。那什么是知识呢？那什么是知识呢？知识一般概念知识一般概念 知识是人们在改造客观世界的实践中积累起来的知识是人们在改造客观世界的实践中积累起来的认识认识和和经验经验 认识：认识：包括对事物现象、本质、属性、状态、关系、联系和运动等的认识包括对事物现象、本质、属性、状态、关系、联系和运动等的认识 经验：经验：包括解决问题的包括解决问题的微观方法：微观方法：如步骤、操作、规则、过程、技巧等如步骤、操作、规则、过程、技巧等 宏观方法：宏观方法：如战略、战术、计谋、策略等如战略、战术、计谋、策略等知识的有代表性的定义知识的有代表性的定义 （1 1）Feigenbaum:Feigenbaum:知识是经过剪裁、塑造、解释、选择和转换了的信息知识是经过剪裁、塑造、解释、选择和转换了的信息 （2 2）BernsteinBernstein：知识由特定领域的描述、关系和过程组成知识由特定领域的描述、关系和过程组成 （3 3）Heyes-RothHeyes-Roth：知识知识=事实事实+信念信念+启发式启发式知识、信息、数据及其关系知识、信息、数据及其关系 数据数据是信息的载体，本身无确切含义，其关联构成信息是信息的载体，本身无确切含义，其关联构成信息 信息信息是数据的关联，赋予数据特定的含义，仅可理解为描述性知识是数据的关联，赋予数据特定的含义，仅可理解为描述性知识 知识知识可以是对信息的关联，也可以是对已有知识的再认识可以是对信息的关联，也可以是对已有知识的再认识 常用的关联方式：常用的关联方式：if if then then 什么是知识什么是知识?一般来说，我们把一般来说，我们把一般来说，我们把一般来说，我们把有关信息关联在一起所形成有关信息关联在一起所形成有关信息关联在一起所形成有关信息关联在一起所形成的信息结构称为知识。知识表示就是对知识的的信息结构称为知识。知识表示就是对知识的的信息结构称为知识。知识表示就是对知识的的信息结构称为知识。知识表示就是对知识的一种描述，一种计算机可以接受的用于描述知一种描述，一种计算机可以接受的用于描述知一种描述，一种计算机可以接受的用于描述知一种描述，一种计算机可以接受的用于描述知识的数据结构识的数据结构识的数据结构识的数据结构。知识反映了客观世界中事物之知识反映了客观世界中事物之知识反映了客观世界中事物之知识反映了客观世界中事物之间的关系。间的关系。间的关系。间的关系。例如，例如，例如，例如，雪是白色的、鸟有翅膀等都雪是白色的、鸟有翅膀等都是知识是知识知识的要素知识的要素知识的要素是指构成知识的必需元素。在这里，知识的要素是指构成知识的必需元素。在这里，我们关心的是一个人工智能系统所处理的知识的我们关心的是一个人工智能系统所处理的知识的组成成分。一般而言，人工智能系统的知识包含组成成分。一般而言，人工智能系统的知识包含事实、规则、控制和元知识。事实、规则、控制和元知识。知识的要素知识的要素事实：事物的分类、属性、事物间关系、科学事实、事实：事物的分类、属性、事物间关系、科学事实、客观事实等客观事实等.是有关问题环境的一些事物的知识，常以是有关问题环境的一些事物的知识，常以“是是”形式出现，也是最低层的知识。例如：雪是白色形式出现，也是最低层的知识。例如：雪是白色的，人有四肢。的，人有四肢。规则：事物的行动、动作和联系的因果关系知识。规则：事物的行动、动作和联系的因果关系知识。这种知识是动态的，常以这种知识是动态的，常以“如果如果那么那么”形式出现。例如形式出现。例如启发式规则，如果下雨，则出门带伞。启发式规则，如果下雨，则出门带伞。知识的要素知识的要素控制：当有多个动作同时被激活时，选择哪一个动控制：当有多个动作同时被激活时，选择哪一个动作来执行的知识。是有关问题的求解步骤、规划、求作来执行的知识。是有关问题的求解步骤、规划、求解策略等技巧性知识解策略等技巧性知识.元知识：怎样使用规则、解释规则、校验规则、解元知识：怎样使用规则、解释规则、校验规则、解释程序结构等知识。是有关知识的知识，是知识库中释程序结构等知识。是有关知识的知识，是知识库中的高层知识。元知识与控制知识有时有重叠的高层知识。元知识与控制知识有时有重叠.知识的分类知识的分类根据根据知识表达的内容知识表达的内容，将其简单地分为如下几类：，将其简单地分为如下几类：事实性知识事实性知识知识的一般直接表示，如果事实性知识是批量的、有规律的，则知识的一般直接表示，如果事实性知识是批量的、有规律的，则往往以表格、图册，甚至数据库等形式出现。往往以表格、图册，甚至数据库等形式出现。这种知识描述一般性的事实，如凡是冷血动物都要冬眠，哺乳动物这种知识描述一般性的事实，如凡是冷血动物都要冬眠，哺乳动物都是胎生繁殖后代等。都是胎生繁殖后代等。过程性知识过程性知识表述做某件事的过程。标准程序库也是常见的过程性知识，而且表述做某件事的过程。标准程序库也是常见的过程性知识，而且是系列化、配套的。是系列化、配套的。如电视机维修法，怎样烹制法国大餐等。如电视机维修法，怎样烹制法国大餐等。行为性知识行为性知识不直接给出事实本身，只给出它在某方面的行为。行为性知识经不直接给出事实本身，只给出它在某方面的行为。行为性知识经常表示为某种数学模型，从某种意义上讲，行为性知识描述的是事物常表示为某种数学模型，从某种意义上讲，行为性知识描述的是事物的内涵，而不是外延。如微分方程的内涵，而不是外延。如微分方程知识的分类知识的分类实例性知识实例性知识只给出一些实例。知识藏在实例中。感兴趣的不是实例本身，而是隐藏在大量实例中的规律性知识。类比性知识类比性知识既不给出外延，也不给出内涵，只给出它与其它事物的某些相似之处。类比性知识一般不能完整地刻画事物，但它可以启发人们在不同的领域中做到知识的相似性共享。如比喻，心如刀绞，谜语等元知识元知识有关知识的知识。最重要的元知识是如何使用知识的知识。例如，一个好的专家系统应该知道自己能回答什么问题，不能回答什么问题，这就是关于自己知识的知识。元知识是用于如何从知识库中找到想要的知识。按知识的性质按知识的性质 概念、命题、公理、定理、规则和方法概念、命题、公理、定理、规则和方法按知识的作用域按知识的作用域 常识性知识：常识性知识：通用通识的知识。人们普遍知道的、适应所有领域的知识。通用通识的知识。人们普遍知道的、适应所有领域的知识。领域性知识：领域性知识：面向某个具体专业领域的知识。面向某个具体专业领域的知识。例如：例如：专家经验。专家经验。按知识的层次按知识的层次 表层知识：表层知识：描述客观事物的现象的知识。例如：感性、事实性知识描述客观事物的现象的知识。例如：感性、事实性知识 深层知识：深层知识：描述客观事物本质、内涵等的知识。例如：理论知识描述客观事物本质、内涵等的知识。例如：理论知识按知识的确定性按知识的确定性 确定性知识：确定性知识：可以说明其真值为真或为假的知识可以说明其真值为真或为假的知识 不确定性知识：不确定性知识：包括不精确、模糊、不完备知识包括不精确、模糊、不完备知识 不精确：不精确：知识本身有真假，但由于认识水平限制却不能肯定其真假知识本身有真假，但由于认识水平限制却不能肯定其真假 表示：用可信度、概率等描述表示：用可信度、概率等描述 模糊：模糊：知识本身的边界就是不清楚的。例如：大，小等知识本身的边界就是不清楚的。例如：大，小等 表示：用可能性、隶属度来描述表示：用可能性、隶属度来描述 不完备：不完备：解决问题时不具备解决该问题的全部知识。例如：医生看病解决问题时不具备解决该问题的全部知识。例如：医生看病每种以每种以知识和符号操作知识和符号操作为基础的智能系统，其为基础的智能系统，其问题求解方法都需要某种对解答的搜索。问题求解方法都需要某种对解答的搜索。在搜索过程开始之前，必须先用某种方法或某在搜索过程开始之前，必须先用某种方法或某几种方法的混和来表示问题。几种方法的混和来表示问题。问题求解技术主要涉及两个方面：问题的表示 求解的方法知识表示知识表示方式是学习人工智能的中心内容之一。方式是学习人工智能的中心内容之一。知识表示知识表示知识表示的概念知识表示的概念什么是知识表示什么是知识表示 是对知识的描述，即用一组符号把知识编码成计算机可以接受的某是对知识的描述，即用一组符号把知识编码成计算机可以接受的某种结构。其表示方法不唯一。种结构。其表示方法不唯一。知识表示的要求知识表示的要求 表示能力：表示能力：能否正确、有效地表示问题。包括：能否正确、有效地表示问题。包括：表示范围的广泛性表示范围的广泛性 领域知识表示的高效性领域知识表示的高效性 对非确定性知识表示的支持程度对非确定性知识表示的支持程度 可利用性：可利用性：可利用这些知识进行有效推理。包括：可利用这些知识进行有效推理。包括：对推理的适应性：对推理的适应性：推理是根据已知事实利用知识导出结果的过程推理是根据已知事实利用知识导出结果的过程 对高效算法的支持程度：对高效算法的支持程度：知识表示要有较高的处理效率知识表示要有较高的处理效率 可实现性：可实现性：要便于计算机直接对其进行处理要便于计算机直接对其进行处理 可组织性：可组织性：可以按某种方式把知识组织成某种知识结构可以按某种方式把知识组织成某种知识结构 可维护性：可维护性：便于对知识的增、删、改等操作便于对知识的增、删、改等操作 自然性：自然性：符合人们的日常习惯符合人们的日常习惯 可理解性：可理解性：知识应易读、易懂、易获取等知识应易读、易懂、易获取等 知识表示的一般方法知识表示的一般方法状态空间法状态空间法问题归约法问题归约法谓词逻辑法谓词逻辑法语义网络语义网络另外还有框架表示以及剧本表示另外还有框架表示以及剧本表示,过程表示过程表示,这这里不在一一详述里不在一一详述.在表示和求解比较复杂的问题时在表示和求解比较复杂的问题时,采用单一的表采用单一的表示方法是不够的示方法是不够的,往往采用多种方法的混合表示往往采用多种方法的混合表示.目前这仍是人工智能专家感兴趣的研究方向目前这仍是人工智能专家感兴趣的研究方向.状态空间法状态空间法问题求解(problem solving)是个大课题，它涉及归约、推断、决策、规划、常识推理、定理证明和相关过程的核心概念。在分析了人工智能研究中.运用的问题求解方法之后，就会发现许多问题求解方法是采用试探搜索方法的。也就是说，这些方法是通过在某个可能的解空间内寻找一个解来求解问题的。这种基于解答空间的问题表示和求解方法就是状态空间法，它是以状态和算符(operator)为基础来表示和求解问题的。状态空间法问题求解技术主要涉及两个方面：问题求解技术主要涉及两个方面：问题的表示问题的表示 求解的方法求解的方法 状态空间法状态空间法 状态状态（StateState）算符算符（Operator)Operator)状态空间方法状态空间方法（Method on State Space)Method 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）：把问题从一种状态变换）：把问题从一种状态变换为另一种状态的手段为另一种状态的手段.算算符可为走步、过程、规则、数学算子、运算符号或逻辑符号等。算符算符状态空间方法：基于状态空间方法：基于解答空间的问题表示解答空间的问题表示和求解方法和求解方法，它是以，它是以状态和算符状态和算符为基础来为基础来表示和求解问题的。表示和求解问题的。它包含三种说明的集合,即三元状态（S S，F F，G G）S S 初始状态集合；F F 操作符集合；G G 目标状态集合。对一个问题的状态描述，必须确定对一个问题的状态描述，必须确定3 3件事：件事：(1)(1)该状态描述方式，特别是初始状态描述；该状态描述方式，特别是初始状态描述；(2)(2)操作符集合及其对状态描述的作用；操作符集合及其对状态描述的作用；(3)(3)目标状态描述的特性目标状态描述的特性状态空间表示状态空间表示典型的例子:下棋、迷宫及各种游戏。三数码难题问题描述问题描述:三数码难题三数码难题:有有3 3个编有个编有1-31-3并放在并放在2X22X2方格方格棋盘上可走动的棋子组成棋盘上可走动的棋子组成.棋盘上总有一个棋盘上总有一个空格空格,以便让空格周围的棋子走进来以便让空格周围的棋子走进来.直至直至从初始状态到达目标状态从初始状态到达目标状态.三数码难题八数码难题 初始棋局 目标棋局表示制定操作算符集：*直观方法为每个棋牌制定一套可能的走步：左、上、右、下四种移动。这样就需32个操作算子。*简易方法仅为空格制定这4种走步，因为只有紧靠空格的棋牌才能移动。*空格移动的唯一约束是不能移出棋盘。根据问题状态、操作算符和目标条件选择各种表示，是高效率求解必须的。在问题求解过程中，会不断取得经验，获得一些简化的表示。从初始棋局开始，试探由每一合法走步得到的各种新棋局，然后计算再走一步而得到的下一组棋局。这样继续下去，直至达到目标棋局为止。把初始状态可达到的各状态所组成把初始状态可达到的各状态所组成的空间设想为一幅由各种状态对应的空间设想为一幅由各种状态对应的节点组成的图。这种图称为状态的节点组成的图。这种图称为状态图图。图中每个节点标有它所代表的棋局。首先把适用的算符用于初始状态，以产生新的状态；然后，再把另一些适用算符用于这些新的状态；这样继续下去，直至产生目标状态为止。八数码难题部分状态图十五数码难题(思考)初始状态初始状态目标状态目标状态状态空间的图示形式称为状态空间图。状态空间的图示形式称为状态空间图。有向图(directed graph)(directed graph)图:由节点（不一定是有限的节点）的集合构成。有向图:是指图中的一对节点用弧线连接起来，从一个 节点指向另一个节点。路径 某个节点序列（n ni1i1,n,ni2i2,n,nikik）当j=2,3j=2,3,k k时，如果 对于每一个n nij-1ij-1都有一个后继节点n nijij存在，那么就把这 个节点序列叫做从节点，n ni1i1至至节点n nikik的长度为k k的路 径。状态图示法寻找从一种状态变换为另一种状态的某个算符序列问题就等寻找从一种状态变换为另一种状态的某个算符序列问题就等价于寻求图的某一路径的问题价于寻求图的某一路径的问题.代价:加在各弧线的指定数值，以表示加在相应算符上的代价。两个节点间路径的代价等于连接该路径上各节点的所有弧线的代价之和.图的显示说明:指各节点及其具有代价的弧线可以由一张表明确给出,(可以列出每一个节点,其后继节点以及连接弧线上的代价)图的隐示说明 指各节点及其具有代价的弧线不可以由一张表明确给出.(起始节点后继节点算符已知,把后继算符应用于各节点，以扩展节点）状态图示法状态图示法状态空间表示举例问题描述问题描述在一个房间内有一只猴子在一个房间内有一只猴子(可把这只猴子看做一可把这只猴子看做一个机器人个机器人)、一个箱子和一束香蕉。香蕉挂在天、一个箱子和一束香蕉。香蕉挂在天花板下方，但猴子的高度不足以碰到它。那么花板下方，但猴子的高度不足以碰到它。那么这只猴子怎样才能摘到香蕉呢这只猴子怎样才能摘到香蕉呢?用一个四元表列（用一个四元表列（W W，x x，Y Y，z z）来表示问题）来表示问题状态状态.其中：其中：W-W-猴子的水平位置；猴子的水平位置；x x当猴子在箱子顶上当猴子在箱子顶上时取时取x=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)：它含有与具体任务有关的信息；随着应用情况的不同，这些数据库可能小得像数字矩阵那样简单，或许大得如检索文件结构那么复杂。一套规则一套规则：它对数据库进行操作运算。每条规则由左右两部分组成，左部鉴别规则的适用性或先决条件，右部描述规则应用时所完成的动作。应用规则来改变数据库，就象应用算符来改变状态一样。一个控制策略一个控制策略：它确定应该采用哪一条适用规则，而且当数据库的终止条件满足时，就停止计算。控制策略由控制系统选择和确定。产生式系统产生式系统例:推销员旅行问题从城市A出发,访问每个城市一次且仅一次,返回城市A.总数库:到目前为止访问过的城市表.规则:从一个城市达到另一个城市,规则的要求是必须是合法的数据库.(任一城市出现不能多余一次,只到所有城市出现后,才能出现A)任一个以A为起点的和终点的总数据库都满足终止条件.这种图搜索控制策略将在第三章讨论.推销员旅行问题例2.1 推销员旅行问题（旅行商问题）一个推销员计划出访推销产品。他从一个城市（如A）出发，访问每个城市一次，且最多一次，然后返回城市A。要求寻找最短路线。推销员旅行问题状态描述：目前为止访问过的城市列表（A）初始状态：（A）目标状态：（AA）39推销员旅行问题 图2.4 推销员旅行问题状态空间图算符：下一步走向的城市(a)(b)(c)(d)(e)约束：每个城市只能走过一次，A除外作业（p54）2-3 利用图2.3，用状态空间法规划一个最短的旅行路程：此旅程从城市A开始，访问其他城市不多于一次，并返回A。选择一个状态表示，表示出所求得的状态空间的节点及弧线，标出适当的代价，并指明图中从起始节点到目标节点的最佳路径。问题归约法问题归约法已知问题的描述，通过一系列变换把此问题最终已知问题的描述，通过一系列变换把此问题最终变为一个子问题集合；这些子问题的解可以直接变为一个子问题集合；这些子问题的解可以直接得到，从而解决了初始问题。得到，从而解决了初始问题。该方法也就是从该方法也就是从目标目标(要解决的问题要解决的问题)出发逆向推出发逆向推理，建立子问题以及子问题的子问题，直至最后理，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个平凡的本原问题集合把初始问题归约为一个平凡的本原问题集合。这。这就是问题归约的实质。就是问题归约的实质。问题归约法的组成部分问题归约法的组成部分（1 1）一个初始问题描述；）一个初始问题描述；（2 2）一套把问题变换为子问题的操作符；）一套把问题变换为子问题的操作符；（3 3）一套本原问题描述。）一套本原问题描述。问题规约法图解问题规约法图解梵塔难题梵塔难题有有3 3个个柱柱子子(1(1，2 2，3)3)和和3 3个个不不同同尺尺寸寸的的圆圆盘盘(A(A，B B，C)C)。在在每每个个圆圆盘盘的的中中心心有有个个孔孔，所所以以圆圆盘盘可可以以堆叠在柱子上。堆叠在柱子上。最最初初，全全部部3 3个个圆圆盘盘都都堆堆在在柱柱子子1 1上上：最最大大的的圆圆盘盘C C在底部，最小的圆盘在底部，最小的圆盘A A在顶部。在顶部。要要求求把把所所有有圆圆盘盘都都移移到到柱柱子子3 3上上，每每次次只只许许移移动动一一个个，而而且且只只能能先先搬搬动动柱柱子子顶顶部部的的圆圆盘盘，还还不不许许把把尺寸较大的圆盘堆放在尺寸较小的圆盘上尺寸较大的圆盘堆放在尺寸较小的圆盘上。这个问题的初始配置和目标配置如图所示。这个问题的初始配置和目标配置如图所示。梵塔难题梵塔难题(a)初始状态(b)目标状态分析分析原始问题归约（简化）为三个子问题原始问题归约（简化）为三个子问题1、移动、移动A，B盘至柱子盘至柱子2的双圆盘难题的双圆盘难题2、移动圆盘、移动圆盘C至柱子至柱子3的单圆盘问题的单圆盘问题3、移动、移动A，B盘至柱子盘至柱子3的双圆盘难题的双圆盘难题分析分析可以用状态空间表示的三元组合可以用状态空间表示的三元组合(S、F、G)来规定与描述问题；对于梵塔问题，子问来规定与描述问题；对于梵塔问题，子问题（题（111）(122)，(122)(322)以及以及(322)(333)规定了最后解答路径规定了最后解答路径将要通过的脚踏石状态将要通过的脚踏石状态(122)和和(322)。具体解题过程具体解题过程与或图与或图一般地，我们用一个类似图的结构来表示一般地，我们用一个类似图的结构来表示把问题归约为后继问题的替换集合，这种把问题归约为后继问题的替换集合，这种结构图叫做结构图叫做问题归约图问题归约图，或叫，或叫与或图与或图。与或图表示与或图表示例如，设想问题例如，设想问题A A需要由求解问题需要由求解问题B B、C C和和D D来决定，那么来决定，那么可以用一个与图来表示可以用一个与图来表示 (左图左图)同样，一个问题同样，一个问题A A或者由求解问题或者由求解问题B B、或者由求解问题、或者由求解问题C C来决定，则可以用一个或图来表示来决定，则可以用一个或图来表示(右图右图)与或图表示与或图表示与或图的一些术语与或图的一些术语如果某条弧线从节点a指向节点b，那么节点a叫做节点b的父辈节点；节点b叫做节点a的后继节点或后裔；或节点，只要解决某个问题就可解决其父辈问题的节点集合；与节点，只有解决所有子问题，才能解决其父辈问题的节点集合；弧线，是父辈节点指向子节点的圆弧连线；终叶节点，是对应于原问题的本原节点.举例58与或图构成规则(1)与或图中的每个节点代表一个要解决的单一问题或问题集合。与或图中的每个节点代表一个要解决的单一问题或问题集合。图中所含起始节点对应于原始问题。图中所含起始节点对应于原始问题。(2)对应于本原问题的节点，叫做终叶节点，它没有后裔。对应于本原问题的节点，叫做终叶节点，它没有后裔。(3)对于把算符应用于问题对于把算符应用于问题A的每种可能情况，都把问题变换为的每种可能情况，都把问题变换为一个子问题集合；有向弧线自一个子问题集合；有向弧线自A 指向后继节点表示所求得的子指向后继节点表示所求得的子问题集合。问题集合。(4)一般对于代表两个或两个以上子问题集合的每个节点，有向一般对于代表两个或两个以上子问题集合的每个节点，有向弧线从此节点指向此子问题集合中的各个节点。由于只有当集弧线从此节点指向此子问题集合中的各个节点。由于只有当集合中所有的项都有解时，这个子合中所有的项都有解时，这个子 问题的集合才能获得解答，所问题的集合才能获得解答，所以这些子问题节点叫做与节点。以这些子问题节点叫做与节点。(5)在特殊情况下，当只有一个算符可应用于问题在特殊情况下，当只有一个算符可应用于问题A，而且这个，而且这个算符产生具有一个以上子问题的某个集合时，由上述规则算符产生具有一个以上子问题的某个集合时，由上述规则3和规和规则则4所产生的图可以得到简化。因此，代表子问题集合的中间或所产生的图可以得到简化。因此，代表子问题集合的中间或节点可以被略去。节点可以被略去。59595959作业P54 2-5试用四元数列结构表示四圆盘梵塔问题，并画出求解该问题的与或图。谓词逻辑法知识补充谓词逻辑法知识补充-命题逻辑命题逻辑命题逻辑 逻辑主要研究推理过程，而推理过程必须依靠命题来表达。在命题逻辑中，“命题”被看作最小单位。数理逻辑中最基本、最简单的部分。命题逻辑命题逻辑什么是命题？命题是陈述客观外界发生事情的陈述句。命题是或为真或为假的陈述句。命题是或为真或为假的陈述句。特征：陈述句真假必居其一,且只居其一.命题逻辑命题逻辑例1 下列句子是命题吗？8小于10.8大于10.任一个5的偶数可表示成两个素数的和.答：是命题逻辑例2 下列句子是命题吗？8大于10吗?请勿吸烟.X大于Y.我正在撒谎.悖论答：不是命题逻辑命题逻辑命题的抽象 以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分.命题逻辑命题逻辑联结词和复合命题 上述诸如“没有”、“如果 那么”等连词称为联结词。由联结词和命题连接而成的更加复杂命题称为由联结词和命题连接而成的更加复杂命题称为复合命题；相对地，不能分解为更简单命题的命复合命题；相对地，不能分解为更简单命题的命题称为简单命题。题称为简单命题。复合命题的真假完全由构成它的简单命题的真假所决定。注：简单命题和复合命题的划分是相对的。命题逻辑命题逻辑否定联结词 定义1：设设p为一个命题为一个命题,复合命题复合命题“非非p”称为称为p的否的否定式，记为定式，记为p，“”称为否定联结词.“p”为真当且仅当p为假。例3中,若p代表“期中考试张三考及格了”，则(1)“期中考试,张三没有考及格.”可表示为p.命题逻辑命题逻辑合取联结词 定义2 设设p、q为两个命题，复合命题为两个命题，复合命题“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分”。命题逻辑命题逻辑“相容或相容或”与与“相异或相异或”日常语言中“或”有两种标准用法,例如:(1)张三或者李四考了90分.(2)第一节课上数学课或者上英语课.差异在于：当构成它们的简单命题都真时，前者为真，后者却为假。前者称为“相容或”，后者称为“相异或”。前者(“相容或”)可表示为pq，后者却不能。注意：不能见了或就表示为pq。命题逻辑命题逻辑蕴涵联结词 定义定义4设设p、q为命题为命题,复合命题复合命题“如果如果p,则则q”称为称为p对对q的蕴涵式，记作的蕴涵式，记作pq,其中又称p为此蕴涵式的前件，称q为此蕴涵式的后件，“”称为蕴涵联结词。“p q”假当且仅当p真而q假.pq这样的真值规定有其合理性，也有人为因素。在自然语言中，”如果.“与”“那末.”之间常常是有因果联系的否则就没有意义，但对命题P-Q来说，只要P,Q能够分别确定真值，P-Q即成为命题。此外，自然语言中对“如果.，则.”这样的语句，当前提为假时，结论不管真假，整个 语句的真假无法判断。而在条件命题中，规定为“善意的推定”，即前提为F时，条件命题的真值都取为T.如果雪是黑的，那末太阳从西方出如果雪是黑的，那末太阳从西方出在自然语言中，”如果.“与”“那末.”之间常常是有因果联系的否则就没有意义，但对命题P-Q来说，只要P,Q能够分别确定真值，P-Q即成为命题。此外，自然语言中对“如果.，则.”这样的语句，当前提为假时，结论不管真假，整个 语句的真假无法判断。而在条件命题中，规定为“善意的推定”，即前提为F时，条件命题的真值都取为T.如果雪是黑的，那么太阳从西方出如果雪是黑的，那么太阳从西方出命题逻辑命题逻辑等价联结词 定义定义5设设p、q为命题为命题,复合命题复合命题“p当且仅当当且仅当q”称作称作p、q的等价式的等价式,记作记作pq,“”称作等价联结词。pq真当且仅当p、q同时为真或同时为假.命题逻辑命题逻辑注意 上述五个联结词来源于日常使用的相应词汇,但并不完全一致，在使用时要注意：以上联结词组成的复合命题的真假值一定要根据它们的定义去理解,而不能据日常语言的含义去理解。不能“对号入座”，如见到“或”就表示为“”。有些词也可表示为这五个联结词，如“但是”也可表示为“”。在今后我们主要关心的是命题间的真假值的关系,而不讨论命题的内容.命题逻辑命题逻辑命题符号化例4 将下列命题符号化:(1)铁和氧化合,但铁和氮不化合.(2)如果我下班早,就去商店看看,除非我很累.(3)李四是计算机系的学生,他住在312室或313室.命题逻辑命题逻辑解（解（1）铁和氧化合）铁和氧化合,但铁和氮不化合但铁和氮不化合.p(q)，其中，其中:p代表代表“铁和氧化合铁和氧化合”，q代表代表“铁和氮化合铁和氮化合”。（2）如果我下班早）如果我下班早,就去商店看看就去商店看看,除非我很除非我很累累.(P)q)r，其中，其中:p代表代表“我很累我很累”,q代表代表“我下班早我下班早”,r代表代表“我去商店看看我去商店看看”命题逻辑命题逻辑（3）李四是计算机系的学生）李四是计算机系的学生,他住在他住在312室或室或313室室.p(q r)(q r)，其中：，其中：p代表代表“李四是计算机系学生李四是计算机系学生”,q代表代表“李四住李四住312室室”,r代表代表“李四住李四住313室室”.还可表示为：还可表示为：p(q(r)(q)r)命题逻辑命题逻辑命题公式及其解释命题公式及其解释原子公式原子公式：单个命题变元、单个命题常元称为原子：单个命题变元、单个命题常元称为原子公式。公式。命题公式命题公式：由如下规则生成的公式称为命题公式：由如下规则生成的公式称为命题公式：1.1.单个原子公式是命题公式。单个原子公式是命题公式。2.2.若若A,BA,B是命题公式，则是命题公式，则A,AA,A B,AB,A B,A B,A B B,A,A B B是公式。是公式。3.3.所有命题公式都是有限次应用所有命题公式都是有限次应用1 1、2 2得到的符号串。得到的符号串。命题逻辑命题逻辑命题公式的命题公式的解释解释：给命题公式中的每一个命题变元：给命题公式中的每一个命题变元指定一个真假值，这一组真假值，就是命题公式的指定一个真假值，这一组真假值，就是命题公式的一个解释。用一个解释。用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为恒假的（不可满足的）。为恒假的（不可满足的）。命题逻辑命题逻辑注意：注意：关于五个联结词的约定关于五个联结词的约定：*结合力的强弱顺序：结合力的强弱顺序：，*联结词相同时，从左至右运算。联结词相同时，从左至右运算。解释的个数解释的个数：如果一个公式：如果一个公式G G中有中有n n个不同的原子公式个不同的原子公式（或简称原子），则（或简称原子），则G G有有2 2n n个不同的解释，于是个不同的解释，于是G G在在2 2n n个解释下有个解释下有2 2n n个真值。如果将这些真值和它们的解释个真值。如果将这些真值和它们的解释列成表，就是列成表，就是G G的真值表。的真值表。命题逻辑命题逻辑等价命题公式等价命题公式 如果两个命题公式所含原子公式相同，且在任一解释如果两个命题公式所含原子公式相同，且在任一解释下，两个命题公式的值相同下，两个命题公式的值相同，则称这两个命题公式为等价，则称这两个命题公式为等价命题公式或等价公式。常用的等价公式有：命题公式或等价公式。常用的等价公式有：1.(P Q)=(P Q)(Q P)2.(P Q)=(P Q)3.(P)=P4.交换律：P Q=Q P P Q=Q P7.泛界律：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)(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)=P P Q=T Q=T2.P Q P证P Q P=(P Q)P=P Q P=T Q=T3.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的的逻辑结论逻辑结论。但在命题逻辑中无法准确表。但在命题逻辑中无法准确表达这三个命题的逻辑关系达这三个命题的逻辑关系。为准确表达此类公式，必须引进谓词和量词的概念为准确表达此类公式，必须引进谓词和量词的概念。因为因为(P(P Q)Q)R R 不是恒真不是恒真的。如：的。如：解解释释:I=P/T,Q/T,R/F I=P/T,Q/T,R/F 则公式为假值则公式为假值F.F.就是说解释就是说解释I I 弄假了此公弄假了此公式。式。命题逻辑命题逻辑命题逻辑与谓词逻辑命题逻辑与谓词逻辑命题逻辑虽能够把客观世界的各种实事表命题逻辑虽能够把客观世界的各种实事表示为逻辑命题，但具有很大局限性，即不示为逻辑命题，但具有很大局限性，即不适合表达比较复杂的问题；而谓词逻辑则适合表达比较复杂的问题；而谓词逻辑则允许我们表达那些无法用命题逻辑表达的允许我们表达那些无法用命题逻辑表达的事情事情.谓词逻辑法谓词逻辑法谓词逻辑法谓词逻辑法采用采用谓词合式公式谓词合式公式和和一阶谓一阶谓词演算词演算把要解决的问题变为一个有待证把要解决的问题变为一个有待证明的问题明的问题,然后采用然后采用消除定理消除定理和和消除反演消除反演来来证明一个新语句是从已知的正确语句证明一个新语句是从已知的正确语句导出的导出的,从而证明新语句也是正确的从而证明新语句也是正确的.谓词谓词1.31.3是质数是质数2.2.王二生于武汉市王二生于武汉市3.7=23.7=2 3 3 x x是质数是质数x x生于武汉市生于武汉市x=y x=y z zF(x)F(x)G(x,y)G(x,y)H(x,y,z)H(x,y,z)称称“3 3”、“王二王二”、“武汉市武汉市”、“7 7”、“2 2”、“3 3”为个体为个体;“是质数是质数”、“生于生于”、“=.=.”都是谓词。都是谓词。谓词谓词谓谓词词：用用来来刻刻画画个个体体词词的的性性质质或或个个体体词词之之间间关关系系的的词词例如例如:张三是研究生，李四是研究生张三是研究生，李四是研究生.这两个命题可以用不同的符号这两个命题可以用不同的符号P P、Q Q表示，但是表示，但是P P和和Q Q的的谓语谓语有共同的属性有共同的属性：是研究生。因此引入一个符号表示：是研究生。因此引入一个符号表示“是研究是研究生生”，再引入一个方法表示个体的名称，这样就能把，再引入一个方法表示个体的名称，这样就能把“某某某某是研究生是研究生”这个这个命题的本质属性命题的本质属性刻画出来。刻画出来。对于上面的命题，可以用谓词公式分别表示为对于上面的命题，可以用谓词公式分别表示为GraduateGraduate（张三）、（张三）、GraduateGraduate（李四）。（李四）。其中其中GraduateGraduate是谓词名，是谓词名，张三和李四都是个体，张三和李四都是个体，“GraduateGraduate”刻画了刻画了“张三张三”和和“李四李四”是研究生这一特征。是研究生这一特征。谓词谓词一一般般来来说说，“x x是是A A”类类型型的的命命题题可可以以用用A A（x x）表表达达。对对于于“x x大大于于y y”这这种种两两个个个个体体之之间间关关系系的的命命题题，可可表表达达为为B B（x x，y y），这这里里B B表表示示“大大于于”谓谓词词。我我们们把把A A（x x）称称为为一一元元谓谓词词 B B（x x，y y）称称为为二二元元谓谓词词，M M（a a，b b，c c）称称为为三三元元谓谓词词，依依次次类类推推，通通常把二元以上谓词称作多元谓词。常把二元以上谓词称作多元谓词。语法与语义语法与语义 谓词逻辑的谓词逻辑的基本符号基本符号：谓：谓词符号、变量符号、常词符号、变量符号、常量符号、函数符号、括号和逗号量符号、函数符号、括号和逗号。谓词符号：规定定义域内的一个相应关系。谓词符号：规定定义域内的一个相应关系。变量符号：不明确指定是哪一个实体。变量符号：不明确指定是哪一个实体。常量符号：表示论域内相应的一个实体。常量符号：表示论域内相应的一个实体。函数符号函数符号 ：规定论域内相应的一个函数。：规定论域内相应的一个函数。原子公式原子公式(atomic formulas)(atomic formulas)是由谓词符号和若是由谓词符号和若干项组成的谓词演算。干项组成的谓词演算。语法与语义语法与语义常量符号常量符号是最简单的项，用来表示论域内是最简单的项，用来表示论域内的物体或实体。例如，要表示的物体或实体。例如，要表示“机器人机器人(ROBOT)(ROBOT)在号房间在号房间(r1)(r1)内内”，可以应用原，可以应用原子公式子公式:INROOM(ROBOT,r1)谓词符号常量符号语法与语义语法与语义函数符号函数符号表示论域内的函数，如表示论域内的函数，如“李的母亲和他的李的母亲和他的父亲结婚父亲结婚”这句话的原子公式表示如下：这句话的原子公式表示如下：MARRIED(father(LI),mother(LI)MARRIED(father(LI),mother(LI)MARRIED(father(LI),mother(LI)MARRIED(father(LI),mother(LI)函数符号谓词符号语法与语义语法与语义变量符号变量符号:扩大命题演算的能力，需要使公式中扩大命题演算的能力，需要使公式中的命题带有变量。的命题带有变量。句子句子“所有的机器人都是灰色的所有的机器人都是灰色的”可表示为可表示为我们注意到：这里的我们注意到：这里的x x是被量化的变量是被量化的变量 若某个变量是经过量化的，就把这个变量叫做若某个变量是经过量化的，就把这个变量叫做约束变量约束变量，否则叫做，否则叫做自由变量自由变量。连词和量词连词和量词 连词和量词连词和量词连词连词合取合取（conjunction)用符号将几个公式连接起来而构成的公式，其中的合取项是合取式的每个组成部分。例：我喜爱音乐和绘画。LIKE(ILIKE(I，MUSIC)LIKE(I,LIKE(I,PAINTING)李住在一座黄色的房子里李住在一座黄色的房子里”LIVELIVELIVELIVE（LILILILI，HOUSE-1HOUSE-1HOUSE-1HOUSE-1）COLORCOLORCOLORCOLOR（HOUSE-1HOUSE-1HOUSE-1HOUSE-1，YELLOWYELLOWYELLOWYELLOW）析取析取(disjunction)用连词用连词 把几个公式连接起把几个公式连接起来而构成的公式。析取项是析取式的每个组成部分来而构成的公式。析取项是析取式的每个组成部分.例：李力打篮球或踢足球例：李力打篮球或踢足球.PLAYS(LILI，BASKETBALL)PLAYS(LILI,FOOTBALL)蕴涵（蕴涵（Implication用连词用连词表示表示“如果如果那么那么”的的语句语句.例：如果刘华跑得最快，那么他取得冠军例：如果刘华跑得最快，那么他取得冠军RUNS(LIUHUAFASTEST)(LIUHUA，CHAMPION)例如，例如，例如，例如，“如果该书是何平的，那么它是蓝色的如果该书是何平的，那么它是蓝色的如果该书是何平的，那么它是蓝色的如果该书是何平的，那么它是蓝色的”OWNOWN（HEPINGHEPING，BOOK-1)BOOK-1)COLORCOLOR（BOOK-1BOOK-1，BLUEBLUE）非（Not)用符号表示否定的公式（有时也用表示）例：机器人不在 例：机器人不在2号房间内。INROOM(ROBOT，r2)经连词连接后公式的真值经连词连接后公式的真值合取：各合取项均为真，合取才为真，否合取：各合取项均为真，合取才为真，否则为假。则为假。析取：析取项至少一个为真，析取为真。析取：析取项至少一个为真，析取为真。蕴含：若后项为真，无论前项为真为假；蕴含：若后项为真，无论前项为真为假；或者前项为假，无论后项为真为假，蕴含或者前项为假，无论后项为真为假，蕴含都为真。都为真。非：原式真值相反。非：原式真值相反。量词量词 全称量词全称量词（Universal Quantifiers)若一个原子公式 P(x)，对于所有可能变量对于x都具有T值,则用(x)P(x)表示。例：所有学生都穿彩色制服(x)Student(X)Uniform(x,Color)所有的机器人都是灰色的 (x)Robot(X)COLOR(x,GRAY)量词量词存在量词（存在量词（ExistentialQuantifiers)若一个原子公式若一个原子公式P(x),至少有一个变元至少有一个变元X可使可使P(X)为为T值值,则用则用(x)P(x)表示。表示。例：例：1号房间内有个物体号房间内有个物体(x)INROOM(x,r1)量词的辖域量词的辖域定义定义:量词的辖域量词的辖域是邻接量词之后的最小子是邻接量词之后的最小子公式，故除非辖域是个原子公式，否则应公式，故除非辖域是个原子公式，否则应在该子公式的两端有括号。在该子公式的两端有括号。例：例：(x)P(x)Q(x)x的辖域是的辖域是P(x)(x)P(x,y)Q(x，y)P(y,z)x的辖域是的辖域是P(x，y)Q(x，y)量词的辖域量词的辖域定义：在量词定义：在量词 x，x辖域内变元辖域内变元x的一切出现叫的一切出现叫约束出现，称这样的约束出现，称这样的x为为约束变元。约束变元。变元的非约束出现称为变元的非约束出现称为自由出现自由出现,称这样的变元为称这样的变元为自由变元自由变元。例：例：指出下列谓词公式中的自由变元和约束变元，指出下列谓词公式中的自由变元和约束变元，并指明量词的辖域并指明量词的辖域(x)P(x)R(x)(x)P(x)Q(x)解：表达式中的解：表达式中的 xP(x)R(x)中中x的辖域是的辖域是 P(x)R(x),其中的其中的x是约束出现是约束出现(x)P(x)中中x的辖域是的辖域是 P(x),其中的其中的x是约束出现是约束出现 Q(x)中的中的x是自由变元是自由变元量词的辖域量词的辖域例：指出下列谓词公式中的自由变元和约例：指出下列谓词公式中的自由变元和约束变元束变元,并指明量词的辖域。并指明量词的辖域。(x)P(x，y)(y)R(x，y)解：其中的解：其中的P(x，y)中的中的y是自由变元，是自由变元，x是是约束变元，约束变元，R(x，y)中的中的x，y是约束变元。是约束变元。注：在一个公式中，一个变元既可以约束注：在一个公式中，一个变元既可以约束出现，又可以自由出现。为避免混淆可用出现，又可以自由出现。为避免混淆可用改名规则对变元改名。改名规则对变元改名。注意事项注意事项(1)分析命题中表示分析命题中表示性质性质和和关系关系的谓词，分的谓词，分别符号化为一元和别符号化为一元和n（n 2）元谓词。）元谓词。(2)根据命题的实际意义选用根据命题的实际意义选用全称量词全称量词或或存存在量词。在量词。(3)在不同的个体域中，命题符号化的形式在不同的个体域中，命题符号化的形式可能不一样。如果事先没有给出个体域，可能不一样。如果事先没有给出个体域，都应以都应以全总个体域全总个体域为个体域。为个体域。(4)多个量词同时出现时，不能随意颠倒它多个量词同时出现时，不能随意颠倒它们的顺序，颠倒后会改变原命题的含义。们的顺序，颠倒后会改变原命题的含义。谓词公式谓词公式原子谓词公式 用P（x1，x2，xn）表示一个n元谓词公式 其中P为n元谓词，x1,x2,xn为客体变量或变元。通常把P（x1,x2,xn）叫做谓词演算的原子公式分子谓词公式 用连词把原子谓词公式组成复合谓词公式，并把它叫做分子谓词公式合式公式（WFF,well-formed formulas WFF,well-formed formulas）合式公式的递归定义合式公式的递归定义 合式公式的性质合式公式的性质 合式公式的真值合式公式的真值 等价（等价（Equivalence)Equivalence)合式公式的递归定义合式公式的递归定义 1.1.原子谓词公式是合式公式 2.2.若A A为合式公式，则A A也是一个合式公式。3.3.若A A和B B都是合适公式,则（A AB B）,（A AB B）,（A A B B）也都是合式公式。4.4.若A A是合适公式，x x为A A中的自由变元，则（x x）A A和（x x）A A都是合式公式。5.只有按上述(1)(1)至(4)规则求得的那些公式，才是合式公式合式公式的真值合式公式的真值 真值表:P与 Q是两个合式公式，则由这两个合式公式所组成的复合表达可由下列真值表给出合适公式的性质合适公式的性质合式公式具有强大的形式化表示功能，但由于包合式公式具有强大的形式化表示功能，但由于包括了多种连词和量词以及它们的嵌套应用，会使括了多种连词和量词以及它们的嵌套应用，会使表示形式过于复杂，不利于演绎推理系统的设计表示形式过于复杂，不利于演绎推理系统的设计和高效运作。和高效运作。为此，化简合式公式到某些约定的标准形式是很为此，化简合式公式到某些约定的标准形式是很有意义的，有意义的，合式公式的性质则为化简工作提供了合式公式的性质则为化简工作提供了依据。依据。合式公式的性质 合式公式的性质 量词否定量词否定:量词分配量词分配:约束变量的虚元性（约束变量名的变换不影响合式公式的真值）:谓词逻辑表示方法谓词逻辑表示方法表示步骤：表示步骤：(1)(1)先根据要表示的知识定义谓词先根据要表示的知识定义谓词 (2)(2)再用连词、量词把这些谓词连接起来再用连词、量词把这些谓词连接起来例例1 1 表示知识表示知识“所有教师都有自己的学生所有教师都有自己的学生”。定义谓词：定义谓词：T(x)
展开阅读全文