人工智能课件-第二章(老师版)

人工智能课件——第二章(老师版)第一页，共229页。前言

在学习本章内容之前，我们先了解一下有关知识及其表示的概念。

人类的智能活动过程主要是一个获得并运用知识的过程，知识是智能的基础。为了使计算机具有智能，就必须使它具有知识。那什么是知识呢？第二页，共229页。知识一般概念

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

（1）Feigenbaum:知识是经过剪裁、塑造、解释、选择和转换了的信息

（2）Bernstein：知识由特定领域的描述、关系和过程组成

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

if……then……第三页，共229页。什么是知识?一般来说，我们把有关信息关联在一起所形成的信息结构称为知识。知识表示就是对知识的一种描述，一种计算机可以接受的用于描述知识的数据结构。知识反映了客观世界中事物之间的关系。例如，雪是白色的、鸟有翅膀等都是知识第四页，共229页。知识的要素知识的要素是指构成知识的必需元素。在这里，我们关心的是一个人工智能系统所处理的知识的组成成分。一般而言，人工智能系统的知识包含事实、规则、控制和元知识。第五页，共229页。知识的要素事实：事物的分类、属性、事物间关系、科学事实、客观事实等.是有关问题环境的一些事物的知识，常以“┅是┅”形式出现，也是最低层的知识。例如：雪是白色的，人有四肢。规则：事物的行动、动作和联系的因果关系知识。这种知识是动态的，常以“如果┅那么┅”形式出现。例如启发式规则，如果下雨，则出门带伞。第六页，共229页。知识的要素控制：当有多个动作同时被激活时，选择哪一个动作来执行的知识。是有关问题的求解步骤、规划、求解策略等技巧性知识.元知识：怎样使用规则、解释规则、校验规则、解释程序结构等知识。是有关知识的知识，是知识库中的高层知识。元知识与控制知识有时有重叠.

第七页，共229页。知识的分类

根据知识表达的内容，将其简单地分为如下几类：

事实性知识

知识的一般直接表示，如果事实性知识是批量的、有规律的，则往往以表格、图册，甚至数据库等形式出现。

这种知识描述一般性的事实，如凡是冷血动物都要冬眠，哺乳动物都是胎生繁殖后代等。

过程性知识

表述做某件事的过程。标准程序库也是常见的过程性知识，而且是系列化、配套的。

如电视机维修法，怎样烹制法国大餐等。

行为性知识

不直接给出事实本身，只给出它在某方面的行为。行为性知识经常表示为某种数学模型，从某种意义上讲，行为性知识描述的是事物的内涵，而不是外延。如微分方程

第八页，共229页。知识的分类实例性知识

只给出一些实例。知识藏在实例中。感兴趣的不是实例本身，而是隐藏在大量实例中的规律性知识。

类比性知识

既不给出外延，也不给出内涵，只给出它与其它事物的某些相似之处。类比性知识一般不能完整地刻画事物，但它可以启发人们在不同的领域中做到知识的相似性共享。

如比喻，心如刀绞，谜语等

元知识

有关知识的知识。最重要的元知识是如何使用知识的知识。例如，一个好的专家系统应该知道自己能回答什么问题，不能回答什么问题，这就是关于自己知识的知识。

元知识是用于如何从知识库中找到想要的知识。第九页，共229页。按知识的性质概念、命题、公理、定理、规则和方法按知识的作用域常识性知识：通用通识的知识。人们普遍知道的、适应所有领域的知识。领域性知识：面向某个具体专业领域的知识。例如：专家经验。按知识的层次表层知识：描述客观事物的现象的知识。例如：感性、事实性知识深层知识：描述客观事物本质、内涵等的知识。例如：理论知识按知识的确定性确定性知识：可以说明其真值为真或为假的知识不确定性知识：包括不精确、模糊、不完备知识不精确：知识本身有真假，但由于认识水平限制却不能肯定其真假表示：用可信度、概率等描述模糊：知识本身的边界就是不清楚的。例如：大，小等表示：用可能性、隶属度来描述不完备：解决问题时不具备解决该问题的全部知识。例如：医生看病第十页，共229页。每种以知识和符号操作为基础的智能系统，其问题求解方法都需要某种对解答的搜索。在搜索过程开始之前，必须先用某种方法或某几种方法的混和来表示问题。问题求解技术主要涉及两个方面：问题的表示

求解的方法知识表示方式是学习人工智能的中心内容之一。知识表示第十一页，共229页。知识表示的概念

什么是知识表示是对知识的描述，即用一组符号把知识编码成计算机可以接受的某种结构。其表示方法不唯一。知识表示的要求表示能力：能否正确、有效地表示问题。包括：表示范围的广泛性领域知识表示的高效性对非确定性知识表示的支持程度可利用性：可利用这些知识进行有效推理。包括：对推理的适应性：推理是根据已知事实利用知识导出结果的过程对高效算法的支持程度：知识表示要有较高的处理效率可实现性：要便于计算机直接对其进行处理可组织性：可以按某种方式把知识组织成某种知识结构可维护性：便于对知识的增、删、改等操作自然性：符合人们的日常习惯可理解性：知识应易读、易懂、易获取等第十二页，共229页。知识表示的一般方法状态空间法问题归约法谓词逻辑法语义网络另外还有框架表示以及剧本表示,过程表示,这里不在一一详述.在表示和求解比较复杂的问题时,采用单一的表示方法是不够的,往往采用多种方法的混合表示.目前这仍是人工智能专家感兴趣的研究方向.第十三页，共229页。状态空间法问题求解(problemsolving)是个大课题，它涉及归约、推断、决策、规划、常识推理、定理证明和相关过程的核心概念。在分析了人工智能研究中.运用的问题求解方法之后，就会发现许多问题求解方法是采用试探搜索方法的。也就是说，这些方法是通过在某个可能的解空间内寻找一个解来求解问题的。这种基于解答空间的问题表示和求解方法就是状态空间法，它是以状态和算符(operator)为基础来表示和求解问题的。

第十四页，共229页。

状态空间法问题求解技术主要涉及两个方面：问题的表示求解的方法状态空间法

状态（State）

算符（Operator)

状态空间方法（MethodonStateSpace)第十五页，共229页。状态状态（state）：描述某类不同事物间的差别而引入的一组最少变量q0q1，…，qn的有序集合.矢量形式：矢量形式：Q=[q0,q1,…qn]T

式中每个元素qi为集合的分量，称为状态变量。给定每个分量的一组值就得到一个具体的状态，如Qk=[q０k,

,q1k,…,qnk]第十六页，共229页。算符（operator）：把问题从一种状态变换为另一种状态的手段.算符可为走步、过程、规则、数学算子、运算符号或逻辑符号等。

算符第十七页，共229页。状态空间方法：基于解答空间的问题表示和求解方法，它是以状态和算符为基础来表示和求解问题的。它包含三种说明的集合,即三元状态（S，F，G）

S—

初始状态集合；

F—

操作符集合；

G—目标状态集合。第十八页，共229页。对一个问题的状态描述，必须确定3件事：(1)该状态描述方式，特别是初始状态描述；(2)操作符集合及其对状态描述的作用；(3)目标状态描述的特性第十九页，共229页。状态空间表示典型的例子:下棋、迷宫及各种游戏。

第二十页，共229页。三数码难题问题描述:三数码难题:有3个编有1-3并放在2X2方格棋盘上可走动的棋子组成.棋盘上总有一个空格,以便让空格周围的棋子走进来.直至从初始状态到达目标状态.第二十一页，共229页。三数码难题第二十二页，共229页。八数码难题

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

八数码难题部分状态图第二十五页，共229页。十五数码难题(思考)初始状态目标状态第二十六页，共229页。状态空间的图示形式称为状态空间图。有向图(directedgraph)图:由节点（不一定是有限的节点）的集合构成。有向图:是指图中的一对节点用弧线连接起来，从一个节点指向另一个节点。路径某个节点序列（ni1,ni2,,…,nik）当j=2,3,…k时，如果对于每一个nij-1都有一个后继节点nij存在，那么就把这个节点序列叫做从节点，ni1至至节点nik的长度为k的路径。

状态图示法AB第二十七页，共229页。寻找从一种状态变换为另一种状态的某个算符序列问题就等价于寻求图的某一路径的问题.代价:加在各弧线的指定数值，以表示加在相应算符上的代价。两个节点间路径的代价等于连接该路径上各节点的所有弧线的代价之和.图的显示说明:指各节点及其具有代价的弧线可以由一张表明确给出,(可以列出每一个节点,其后继节点以及连接弧线上的代价)图的隐示说明指各节点及其具有代价的弧线不可以由一张表明确给出.(起始节点后继节点算符已知,把后继算符应用于各节点，以扩展节点）

状态图示法第二十八页，共229页。

状态空间表示举例第二十九页，共229页。问题描述在一个房间内有一只猴子(可把这只猴子看做一个机器人)、一个箱子和一束香蕉。香蕉挂在天花板下方，但猴子的高度不足以碰到它。那么这只猴子怎样才能摘到香蕉呢?第三十页，共229页。用一个四元表列（W，x，Y，z）来表示问题状态.其中：W-猴子的水平位置；x－当猴子在箱子顶上时取x=1；否则取x=0；Y－箱子的水平位置；z-当猴子摘到香蕉时取z=1；否则取z=0。解题过程第三十一页，共229页。操作（算符）：第三十二页，共229页。该初始状态变换为目标状态的操作序列为：{goto(b),pushbox(c),climbbox,grasp}

第三十三页，共229页。U=b=c第三十四页，共229页。状态空间表示举例产生式系统（ProductionSystem）一个总数据库(globaldatabase)：它含有与具体任务有关的信息；随着应用情况的不同，这些数据库可能小得像数字矩阵那样简单，或许大得如检索文件结构那么复杂。

一套规则：它对数据库进行操作运算。每条规则由左右两部分组成，左部鉴别规则的适用性或先决条件，右部描述规则应用时所完成的动作。应用规则来改变数据库，就象应用算符来改变状态一样。一个控制策略：它确定应该采用哪一条适用规则，而且当数据库的终止条件满足时，就停止计算。控制策略由控制系统选择和确定。第三十五页，共229页。产生式系统例:推销员旅行问题从城市A出发,访问每个城市一次且仅一次,返回城市A.总数库:到目前为止访问过的城市表.规则:从一个城市达到另一个城市,规则的要求是必须是合法的数据库.(任一城市出现不能多余一次,只到所有城市出现后,才能出现A)任一个以A为起点的和终点的总数据库都满足终止条件.这种图搜索控制策略将在第三章讨论.第三十六页，共229页。推销员旅行问题例2.1推销员旅行问题（旅行商问题）一个推销员计划出访推销产品。他从一个城市（如A）出发，访问每个城市一次，且最多一次，然后返回城市A。要求寻找最短路线。第三十七页，共229页。推销员旅行问题状态描述：目前为止访问过的城市列表（A…）初始状态：（A）目标状态：（A……A）第三十八页，共229页。39推销员旅行问题图2.4推销员旅行问题状态空间图算符：下一步走向的城市(a)(b)(c)(d)(e)约束：每个城市只能走过一次，A除外第三十九页，共229页。作业（p54）2-3利用图2.3，用状态空间法规划一个最短的旅行路程：此旅程从城市A开始，访问其他城市不多于一次，并返回A。选择一个状态表示，表示出所求得的状态空间的节点及弧线，标出适当的代价，并指明图中从起始节点到目标节点的最佳路径。第四十页，共229页。问题归约法已知问题的描述，通过一系列变换把此问题最终变为一个子问题集合；这些子问题的解可以直接得到，从而解决了初始问题。该方法也就是从目标(要解决的问题)出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个平凡的本原问题集合。这就是问题归约的实质。第四十一页，共229页。问题归约法的组成部分（1）一个初始问题描述；（2）一套把问题变换为子问题的操作符；（3）一套本原问题描述。第四十二页，共229页。问题规约法图解第四十三页，共229页。梵塔难题有3个柱子(1，2，3)和3个不同尺寸的圆盘(A，B，C)。在每个圆盘的中心有个孔，所以圆盘可以堆叠在柱子上。最初，全部3个圆盘都堆在柱子1上：最大的圆盘C在底部，最小的圆盘A在顶部。要求把所有圆盘都移到柱子3上，每次只许移动一个，而且只能先搬动柱子顶部的圆盘，还不许把尺寸较大的圆盘堆放在尺寸较小的圆盘上。这个问题的初始配置和目标配置如图所示。第四十四页，共229页。第四十五页，共229页。梵塔难题(a)初始状态(b)目标状态第四十六页，共229页。分析原始问题归约（简化）为三个子问题 1、移动A，B盘至柱子2的双圆盘难题 2、移动圆盘C至柱子3的单圆盘问题 3、移动A，B盘至柱子3的双圆盘难题第四十七页，共229页。分析可以用状态空间表示的三元组合(S、F、G)来规定与描述问题；对于梵塔问题，子问题［（111）→(122)］，［(122)→(322)］以及［(322)→(333)］规定了最后解答路径将要通过的脚踏石状态(122)和(322)。第四十八页，共229页。具体解题过程第四十九页，共229页。第五十页，共229页。与或图一般地，我们用一个类似图的结构来表示把问题归约为后继问题的替换集合，这种结构图叫做问题归约图，或叫与或图。第五十一页，共229页。

与或图表示例如，设想问题A需要由求解问题B、C和D来决定，那么可以用一个与图来表示(左图)同样，一个问题A或者由求解问题B、或者由求解问题C来决定，则可以用一个或图来表示(右图)第五十二页，共229页。

与或图表示第五十三页，共229页。第五十四页，共229页。

与或图的一些术语如果某条弧线从节点a指向节点b，那么节点a叫做节点b的父辈节点；节点b叫做节点a的后继节点或后裔；或节点，只要解决某个问题就可解决其父辈问题的节点集合；与节点，只有解决所有子问题，才能解决其父辈问题的节点集合；弧线，是父辈节点指向子节点的圆弧连线；终叶节点，是对应于原问题的本原节点.第五十五页，共229页。第五十六页，共229页。举例第五十七页，共229页。58与或图构成规则

(1)与或图中的每个节点代表一个要解决的单一问题或问题集合。图中所含起始节点对应于原始问题。(2)对应于本原问题的节点，叫做终叶节点，它没有后裔。(3)对于把算符应用于问题A的每种可能情况，都把问题变换为一个子问题集合；有向弧线自A指向后继节点表示所求得的子问题集合。(4)一般对于代表两个或两个以上子问题集合的每个节点，有向弧线从此节点指向此子问题集合中的各个节点。由于只有当集合中所有的项都有解时，这个子问题的集合才能获得解答，所以这些子问题节点叫做与节点。(5)在特殊情况下，当只有一个算符可应用于问题A，而且这个算符产生具有一个以上子问题的某个集合时，由上述规则3和规则4所产生的图可以得到简化。因此，代表子问题集合的中间或节点可以被略去。

第五十八页，共229页。59595959作业P542-5试用四元数列结构表示四圆盘梵塔问题，并画出求解该问题的与或图。第五十九页，共229页。第六十页，共229页。谓词逻辑法－知识补充

-命题逻辑命题逻辑逻辑主要研究推理过程，而推理过程必须依靠命题来表达。在命题逻辑中，“命题”被看作最小单位。数理逻辑中最基本、最简单的部分。第六十一页，共229页。命题逻辑什么是命题？命题是陈述客观外界发生事情的陈述句。命题是或为真或为假的陈述句。特征：陈述句真假必居其一,且只居其一.第六十二页，共229页。命题逻辑例1下列句子是命题吗？8小于10.8大于10.任一个>5的偶数可表示成两个素数的和.答：是第六十三页，共229页。命题逻辑例2下列句子是命题吗？8大于10吗?请勿吸烟.X大于Y.我正在撒谎.——悖论答：不是第六十四页，共229页。命题逻辑命题的抽象以p、q、r等表示命题。以1表示真，0表示假。则命题就抽象为：取值为0或1的p等符号。若p取值1，则表示p为真命题；若p取值0，则表示p为假命题；第六十五页，共229页。命题逻辑“复杂命题”例3:由简单命题能构造更加复杂命题(1)期中考试,张三没有考及格.(2)期中考试,张三和李四都考及格了.(3)期中考试,张三和李四中有人考90分.(4)如果张三能考90分,那么李四也能考90分.(5)张三能考90分当且仅当李四也能考90分.第六十六页，共229页。命题逻辑联结词和复合命题上述诸如“没有”、“如果···那么···”等连词称为联结词。由联结词和命题连接而成的更加复杂命题称为复合命题；相对地，不能分解为更简单命题的命题称为简单命题。复合命题的真假完全由构成它的简单命题的真假所决定。注：简单命题和复合命题的划分是相对的。第六十七页，共229页。命题逻辑否定联结词定义1：设p为一个命题,复合命题“非p”称为p的否定式，记为¬p，“¬”称为否定联结词.“¬p”为真当且仅当p为假。

例3中,若p代表“期中考试张三考及格了”，则(1)“期中考试,张三没有考及格.”可表示为¬p.第六十八页，共229页。命题逻辑合取联结词定义2设p、q为两个命题，复合命题“p而且q”称为p、q的合取式，记为p∧q，“∧”称作合取联结词。p∧q真当且仅当p与q同时真.例3的(2)“期中考试,张三和李四都考及格了.”可记为p∧q,其中p代表“张三考及格”,q代表“李四考及格”.第六十九页，共229页。命题逻辑析取联结词定义3设p、q为两个命题，复合命题“p或者q”称为p、q的析取式，记为p∨q，“∨”称作析取联结词。p∨q为真当且仅当p与q中至少有一个为真.例3的(3)“期中考试,张三和李四中有人考90分.”可记为p∨q,其中p代表“张三考90分”,q代表“李四考90分”。第七十页，共229页。命题逻辑“相容或”与“相异或”日常语言中“或”有两种标准用法,例如:(1)张三或者李四考了90分.(2)第一节课上数学课或者上英语课.差异在于：当构成它们的简单命题都真时，前者为真，后者却为假。前者称为“相容或”，后者称为“相异或”。前者(“相容或”)可表示为p∨q，后者却不能。注意：不能见了或就表示为p∨q。第七十一页，共229页。命题逻辑蕴涵联结词定义4设p、q为命题,复合命题“如果p,则q”称为p对q的蕴涵式，记作p→q,其中又称p为此蕴涵式的前件，称q为此蕴涵式的后件，“→”称为蕴涵联结词。“p→q”假当且仅当p真而q假.p→q这样的真值规定有其合理性，也有人为因素。第七十二页，共229页。第七十三页，共229页。第七十四页，共229页。在自然语言中，”如果...“与”“那末...”之间常常是有因果联系的否则就没有意义，但对命题P->Q来说，只要P,Q能够分别确定真值，P->Q即成为命题。此外，自然语言中对“如果...，则...”这样的语句，当前提为假时，结论不管真假，整个

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

语句的真假无法判断。而在条件命题中，规定为“善意的推定”，即前提为F时，条件命题的真值都取为T.如果雪是黑的，那么太阳从西方出第七十七页，共229页。命题逻辑等价联结词定义5设p、q为命题,复合命题“p当且仅当q”称作p、q的等价式,记作p↔q,“↔”称作等价联结词。p↔q真当且仅当p、q同时为真或同时为假.第七十八页，共229页。命题逻辑注意上述五个联结词来源于日常使用的相应词汇,但并不完全一致，在使用时要注意：以上联结词组成的复合命题的真假值一定要根据它们的定义去理解,而不能据日常语言的含义去理解。不能“对号入座”，如见到“或”就表示为“∨”。有些词也可表示为这五个联结词，如“但是”也可表示为“∧”。在今后我们主要关心的是命题间的真假值的关系,而不讨论命题的内容.第七十九页，共229页。命题逻辑命题符号化例4将下列命题符号化:(1)铁和氧化合,但铁和氮不化合.(2)如果我下班早,就去商店看看,除非我很累.(3)李四是计算机系的学生,他住在312室或313室.第八十页，共229页。命题逻辑解（1）铁和氧化合,但铁和氮不化合.p∧(¬q)，其中:p代表“铁和氧化合”，q代表“铁和氮化合”。（2）如果我下班早,就去商店看看,除非我很累.((¬P)∧q)→r，其中:p代表“我很累”,q代表“我下班早”,r代表“我去商店看看”第八十一页，共229页。命题逻辑（3）李四是计算机系的学生,他住在312室或313室.p∧((q∨r)∧(¬(q∧r)))，其中：p代表“李四是计算机系学生”,q代表“李四住312室”,r代表“李四住313室”.还可表示为：p∧((q∧(¬r))∨((¬q)∧r))第八十二页，共229页。命题逻辑命题公式及其解释原子公式：单个命题变元、单个命题常元称为原子公式。命题公式：由如下规则生成的公式称为命题公式：1.单个原子公式是命题公式。2.若A,B是命题公式，则~A,A∧

B,A∨

B,AB,AB是公式。3.所有命题公式都是有限次应用1、2得到的符号串。第八十三页，共229页。命题逻辑命题公式的解释：给命题公式中的每一个命题变元指定一个真假值，这一组真假值，就是命题公式的一个解释。用I表示。例如：公式G=(AB)C

的一个解释是：

I1(G)=A/T,B/F,C/T在解释I1(G)下G为真。永真公式与永假公式：如果公式在它所有的解释I下，其值都为T，则称公式G为恒真的；如果其值都为F，则称公式G为恒假的（不可满足的）。第八十四页，共229页。命题逻辑注意：关于五个联结词的约定：*结合力的强弱顺序：¬，，

，，*联结词相同时，从左至右运算。解释的个数：如果一个公式G中有n个不同的原子公式（或简称原子），则G有2n个不同的解释，于是G在2n个解释下有2n个真值。如果将这些真值和它们的解释列成表，就是G的真值表。第八十五页，共229页。命题逻辑等价命题公式

如果两个命题公式所含原子公式相同，且在任一解释下，两个命题公式的值相同，则称这两个命题公式为等价命题公式或等价公式。常用的等价公式有：1.(PQ)=(PQ)(QP)2.(PQ)=(¬PQ)3.¬(¬P)=P4.交换律：PQ=QP PQ=QP第八十六页，共229页。7.泛界律：PF=P, PT=P PF=F, PT=T

8.互余律：P~P=T, P~P=F9.德•摩根定律：~(PQ)=~P~Q ~(PQ)=~P~Q5.结合律：P(QR)=(PQ)R P(QR)=(PQ)R6.分配律：P(QR)=(PQ)(PR) P(QR)=(PQ)(PR)命题逻辑第八十七页，共229页。证明两个公式等价，可用真值表，也可用基本公式。例如要证明公式

P

Q=~Q~P[证] P

Q=~PQ =~P~(~Q)

=~(~Q)~P=~Q~P命题逻辑第八十八页，共229页。永真蕴涵式

若命题公式GH是恒真的，称其为永真蕴涵式。记为GH，读做“G蕴涵H”，也称“G是H的逻辑结果”。第八十九页，共229页。第九十页，共229页。永真蕴涵式常用的永真蕴涵式：1.PPQ

[证] PPQ=~P(PQ)=~PPQ=TQ=T2.PQP[证] P

Q

P

=~(PQ)P=~P~QP=T~Q=T第九十一页，共229页。3.P(PQ)Q 4.(PQ)~Q~P5.~P(PQ)Q6.(PQ)(QR)(PR)7.(PQ)((QR)(PR))8.((PQ)(RS))(PRQS)9.((PQ)(QR))(PR)第九十二页，共229页。在命题逻辑中有一个三段论法：P:“所有的人都会犯错误”Q:“张三是人”R:“张三会犯错误”

R应该是P和Q的逻辑结论。但在命题逻辑中无法准确表达这三个命题的逻辑关系。为准确表达此类公式，必须引进谓词和量词的概念。因为 (PQ)R不是恒真的。如：解释:I=P/T,Q/T,R/F则公式为假值F.就是说解释I弄假了此公式。命题逻辑第九十三页，共229页。命题逻辑与谓词逻辑命题逻辑虽能够把客观世界的各种实事表示为逻辑命题，但具有很大局限性，即不适合表达比较复杂的问题；而谓词逻辑则允许我们表达那些无法用命题逻辑表达的事情.第九十四页，共229页。谓词逻辑法谓词逻辑法采用谓词合式公式和一阶谓词演算把要解决的问题变为一个有待证明的问题,然后采用消除定理和消除反演来证明一个新语句是从已知的正确语句导出的,从而证明新语句也是正确的.第九十五页，共229页。谓词1.3是质数2.王二生于武汉市3.7=23

x是质数x生于武汉市x=yzF(x)G(x,y)H(x,y,z)称“3”、“王二”、“武汉市”、“7”、“2”、“3”为个体;“是质数”、“生于”、“…=......”都是谓词。第九十六页，共229页。谓词谓词：用来刻画个体词的性质或个体词之间关系的词例如:张三是研究生，李四是研究生.这两个命题可以用不同的符号P、Q表示，但是P和Q的谓语有共同的属性：是研究生。因此引入一个符号表示“是研究生”，再引入一个方法表示个体的名称，这样就能把“某某是研究生”这个命题的本质属性刻画出来。对于上面的命题，可以用谓词公式分别表示为Graduate（张三）、Graduate（李四）。其中Graduate是谓词名，张三和李四都是个体，“Graduate”刻画了“张三”和“李四”是研究生这一特征。第九十七页，共229页。谓词一般来说，“x是A”类型的命题可以用A（x）表达。对于“x大于y”这种两个个体之间关系的命题，可表达为B（x，y），这里B表示“…大于…”谓词。我们把A（x）称为一元谓词B（x，y）称为二元谓词，M（a，b，c）称为三元谓词，依次类推，通常把二元以上谓词称作多元谓词。第九十八页，共229页。

语法与语义谓词逻辑的基本符号：谓词符号、变量符号、常量符号、函数符号、括号和逗号。

谓词符号：规定定义域内的一个相应关系。变量符号：不明确指定是哪一个实体。常量符号：表示论域内相应的一个实体。函数符号：规定论域内相应的一个函数。

原子公式(atomicformulas)是由谓词符号和若干项组成的谓词演算。第九十九页，共229页。语法与语义常量符号是最简单的项，用来表示论域内的物体或实体。例如，要表示“机器人(ROBOT)在１号房间(r1)内”，可以应用原子公式:

INROOM(ROBOT,r1)谓词符号常量符号第一百页，共229页。语法与语义函数符号表示论域内的函数，如“李的母亲和他的父亲结婚”这句话的原子公式表示如下：MARRIED(father(LI),mother(LI))

函数符号谓词符号第一百零一页，共229页。语法与语义变量符号:

扩大命题演算的能力，需要使公式中的命题带有变量。句子“所有的机器人都是灰色的”可表示为我们注意到：这里的x是被量化的变量

若某个变量是经过量化的，就把这个变量叫做约束变量，否则叫做自由变量。第一百零二页，共229页。连词和量词连词和量词连词合取（conjunction)—用符号∧将几个公式连接起来而构成的公式，其中的合取项是合取式的每个组成部分。

例：我喜爱音乐和绘画。LIKE(I，MUSIC)∧LIKE(I,PAINTING)李住在一座黄色的房子里”LIVE（LI，HOUSE-1）∧COLOR（HOUSE-1，YELLOW）第一百零三页，共229页。析取(disjunction)—用连词∨把几个公式连接起来而构成的公式。析取项是析取式的每个组成部分.例：李力打篮球或踢足球.

PLAYS(LILI，BASKETBALL)∨PLAYS(LILI,FOOTBALL)蕴涵（Implication—用连词表示“如果—那么”的语句.例：如果刘华跑得最快，那么他取得冠军RUNS(LIUHUAFASTEST)(LIUHUA，CHAMPION)例如，“如果该书是何平的，那么它是蓝色的”OWN（HEPING，BOOK-1)

COLOR（BOOK-1，BLUE）第一百零四页，共229页。非（Not)

—用符号～表示否定的公式（有时也用┑表示）例：机器人不在例：机器人不在2号房间内。

～

INROOM(ROBOT，r2)第一百零五页，共229页。经连词连接后公式的真值合取：各合取项均为真，合取才为真，否则为假。析取：析取项至少一个为真，析取为真。蕴含：若后项为真，无论前项为真为假；或者前项为假，无论后项为真为假，蕴含都为真。非：原式真值相反。第一百零六页，共229页。

量词

全称量词（UniversalQuantifiers)若一个原子公式P(x)，对于所有可能变量对于x都具有T值,则用(∀x)P(x)表示。例：所有学生都穿彩色制服(∀x)[Student(X)

Uniform(x,Color)]所有的机器人都是灰色的

(∀x)[Robot(X)

COLOR(x,GRAY)]第一百零七页，共229页。量词存在量词（ExistentialQuantifiers)若一个原子公式P(x),至少有一个变元X可使P(X)为T值,则用(∃x)P(x)表示。

例：1号房间内有个物体(∃x)INROOM(x,r1)第一百零八页，共229页。量词的辖域定义:量词的辖域是邻接量词之后的最小子公式，故除非辖域是个原子公式，否则应在该子公式的两端有括号。例：(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)第一百零九页，共229页。量词的辖域定义：在量词x，x辖域内变元x的一切出现叫约束出现，称这样的x为约束变元。变元的非约束出现称为自由出现,称这样的变元为自由变元。例：指出下列谓词公式中的自由变元和约束变元，并指明量词的辖域(x)[P(x)R(x)]→(x)P(x)Q(x)

解：表达式中的x[P(x)R(x)]中x的辖域是P(x)R(x),其中的x是约束出现(x)

P(x)中x的辖域是P(x),其中的x是约束出现

Q(x)中的x是自由变元第一百一十页，共229页。量词的辖域例：指出下列谓词公式中的自由变元和约束变元,并指明量词的辖域。(x)[P(x，y)→(y)R(x，y)]

解：其中的P(x，y)中的y是自由变元，x是约束变元，R(x，y)中的x，y是约束变元。注：在一个公式中，一个变元既可以约束出现，又可以自由出现。为避免混淆可用改名规则对变元改名。第一百一十一页，共229页。注意事项(1)分析命题中表示性质和关系的谓词，分别符号化为一元和n（n

2）元谓词。(2)根据命题的实际意义选用全称量词或存在量词。(3)在不同的个体域中，命题符号化的形式可能不一样。如果事先没有给出个体域，都应以全总个体域为个体域。(4)多个量词同时出现时，不能随意颠倒它们的顺序，颠倒后会改变原命题的含义。第一百一十二页，共229页。

谓词公式原子谓词公式用P（x1，x2，…xn）表示一个n元谓词公式其中P为n元谓词，x1,x2,…xn为客体变量或变元。通常把P（x1,x2,…,xn）叫做谓词演算的原子公式分子谓词公式用连词把原子谓词公式组成复合谓词公式，并把它叫做分子谓词公式第一百一十三页，共229页。

合式公式（WFF,well-formedformulas）

合式公式的递归定义合式公式的性质合式公式的真值等价（Equivalence)

第一百一十四页，共229页。

合式公式的递归定义

1.原子谓词公式是合式公式2.若A为合式公式，则～A也是一个合式公式。3.若A和B都是合适公式,则（A∧B）,（A∨B）,（A

B）也都是合式公式。4.若A是合适公式，x为A中的自由变元，则（∀x）A和（∃x）A都是合式公式。5.只有按上述(1)至(4)规则求得的那些公式，才是合式公式第一百一十五页，共229页。

合式公式的真值

真值表:P与Q是两个合式公式，则由这两个合式公式所组成的复合表达可由下列真值表给出第一百一十六页，共229页。合适公式的性质合式公式具有强大的形式化表示功能，但由于包括了多种连词和量词以及它们的嵌套应用，会使表示形式过于复杂，不利于演绎推理系统的设计和高效运作。为此，化简合式公式到某些约定的标准形式是很有意义的，合式公式的性质则为化简工作提供了依据。第一百一十七页，共229页。合式公式的性质第一百一十八页，共229页。合式公式的性质量词否定:量词分配:约束变量的虚元性（约束变量名的变换不影响合式公式的真值）:第一百一十九页，共229页。谓词逻辑表示方法表示步骤：

(1)先根据要表示的知识定义谓词

(2)再用连词、量词把这些谓词连接起来例1表示知识“所有教师都有自己的学生”。定义谓词：T(x)：表示x是教师。

S(y)：表示y是学生。

TS(x,y)：表示x是y的老师。

表示知识：

(x)(y)(T(x)→TS(x,y)∧S(y))

可读作：对所有x，如果x是一个教师，那么一定存在一个个体y，y的老师是x，且y是一个学生。第一百二十页，共229页。谓词逻辑表示方法例2表示知识“所有的整数不是偶数就是奇数”。定义谓词：I(x)：x是整数，E(x)：x是偶数，O(x)：x是奇数表示知识：(x)(I(x)→E(x)∨O(x))例3表示如下知识：王宏是计算机系的一名学生。王宏和李明是同班同学。凡是计算机系的学生都喜欢编程序。定义谓词：

COMPUTER(x)：表示x是计算机系的学生。

CLASSMATE(x,y)：表示x和y是同班同学。

LIKE(x,y)：表示x喜欢y。表示知识：

COMPUTER(WangHong)CLASSMATE(WangHong,LiMing)(x)(COMPUTER(x)→LIKE(x,programming))第一百二十一页，共229页。谓词逻辑表示的应用

机器人移盒子问题(1/6)分别定义描述状态和动作的谓词描述状态的谓词：

TABLE(x)：x是桌子

EMPTY(y)：y手中是空的

AT(y,z)：y在z处

HOLDS(y,w)：y拿着wON(w,x)：w在x桌面上变元的个体域：

x的个体域是{a,b}y的个体域是{robot}z的个体域是{a,b,c}w的个体域是{box}abc第一百二十二页，共229页。谓词逻辑表示的应用

机器人移盒子问题(2/6)问题的初始状态：

AT(robot,c)EMPTY(robot)ON(box,a)TABLE(a)TABLE(b)问题的目标状态：

AT(robot,c)EMPTY(robot)ON(box,b)TABLE(a)TABLE(b)

机器人行动的目标把问题的初始状态转换为目标状态，而要实现问题状态的转换需要完成一系列的操作abcTABLE(x)：x是桌子

EMPTY(y)：y手中是空的

AT(y,z)：y在z处

HOLDS(y,w)：y拿着wON(w,x)：w在x桌面上第一百二十三页，共229页。谓词逻辑表示的应用

机器人移盒子问题(3/6)描述操作的谓词条件部分：用来说明执行该操作必须具备的先决条件可用谓词公式来表示

动作部分：给出了该操作对问题状态的改变情况通过在执行该操作前的问题状态中删去和增加相应的谓词来实现需要定义的操作：

Goto(x,y)：从x处走到y处。

Pickup(x)：在x处拿起盒子。

Setdown(y)：在x处放下盒子。第一百二十四页，共229页。谓词逻辑表示的应用

机器人移盒子问题(4/6)各操作的条件和动作：

Goto(x，y)

条件：AT(robot，x)

动作：删除表：AT(robot，x)

添加表：AT(robot，y)Pickup(x)

条件：ON(box，x)，TABLE(x)，AT(robot，x)，EMPTY(robot)

动作：删除表：EMPTY(robot)，ON(box，x)

添加表：HOLDS(robot，box)Setdown(x)

条件：AT(robot，x)，TABLE(x)，HOLDS(robot，box)

动作：删除表：HOLDS(robot，box)

添加表：EMPTY(robot)，ON(box，x)

机器人每执行一操作前，都要检查该操作的先决条件是否可以满足。如果满足，就执行相应的操作；否则再检查下一个操作。

第一百二十五页，共229页。谓词逻辑表示的应用

机器人移盒子问题(5/6)这个机器人行动规划问题的求解过程如下：

状态1(初始状态)

AT(robot,c)

开始EMPTY(robot)=========>ON(box,a)TABLE(a)TABLE(b)

状态2AT(robot,a)Goto(c,a)EMPTY(robot)==========>ON(box,a)TABLE(a)TABLE(b)

状态3

AT(robot,a)Pickup(a)HOLDS(robot,box)=========>TABLE(a)TABLE(b)

abc第一百二十六页，共229页。谓词逻辑表示的应用

机器人移盒子问题(6/6)

状态4AT(robot,b)Goto(a,b)HOLDS(robot,box)==========>TABLE(a)TABLE(b)

状态5

AT(robot,b)Setdown(b)EMPTY(robot)==========>ON(box,b)TABLE(a)TABLE(b)

状态6(目标状态)AT(robot,c)Goto(b,c)EMPTY(robot)=========>ON(box,b)TABLE(a)TABLE(b)abc第一百二十七页，共229页。谓词逻辑表示的应用

猴子摘香蕉问题(1/3)描述状态的谓词：

AT(x,y)：x在y处

ONBOX：猴子在箱子上

HB：猴子得到香蕉个体域：

x：{monkey,box,banana}Y：{a,b,c}

问题的初始状态

AT(monkey,a)AT(box,b)¬

ONBOX，¬

HB

问题的目标状态

AT(monkey,c)，AT(box,c)ONBOX，HBabc第一百二十八页，共229页。谓词逻辑表示的应用

猴子摘香蕉问题(2/3)描述操作的谓词

Goto(u,v)：猴子从u处走到v处

Pushbox(v,w)：猴子推着箱子从v处移到w处

Climbbox：猴子爬上箱子

Grasp：猴子摘取香蕉各操作的条件和动作

Goto(u,v)

条件：¬ONBOX，AT(monkey,u)，动作：删除表：AT(monkey,u)

添加表：AT(monkey,v)Pushbox(v,w)

条件：¬

ONBOX，AT(monkey,v)，AT(box,v)

动作：删除表：AT(monkey,v)，AT(box,v)

添加表：AT(monkey,w)，AT(box,w)第一百二十九页，共229页。谓词逻辑表示的应用

猴子摘香蕉问题(3/3)Climbbox

条件：¬

ONBOX，AT(monkey,w)，AT(box,w)

动作：删除表：¬

ONBOX

添加表：ONBOXGrasp

条件：ONBOX，AT(box,c)

动作：删除表：¬

HB

添加表：HB第一百三十页，共229页。谓词逻辑表示的特征主要优点自然：一阶谓词逻辑是一种接近于自然语言的形式语言系统，谓词逻辑表示法接近于人们对问题的直观理解明确：有一种标准的知识解释方法，因此用这种方法表示的知识明确、易于理解精确：谓词逻辑的真值只有“真”与“假”，其表示、推理都是精确的灵活：知识和处理知识的程序是分开的，无须考虑处理知识的细节模块化：知识之间相对独立，这种模块性使得添加、删除、修改知识比较容易进行主要缺点知识表示能力差：只能表示确定性知识，而不能表示非确定性知识、过程性知识和启发式知识知识库管理困难：缺乏知识的组织原则，知识库管理比较困难存在组合爆炸：由于难以表示启发式知识，因此只能盲目地使用推理规则，这样当系统知识量较大时，容易发生组合爆炸系统效率低：它把推理演算与知识含义截然分开，抛弃了表达内容中所含有的语义信息，往往使推理过程冗长，降低了系统效率第一百三十一页，共229页。π的平方是非负的。解:个体：π的平方：以a表示谓词：…是非负的：以Q表示符号化：Q(a)另解个体：π函词（函数符号）：…的平方：以f表示谓词：…是非负的：以Q表示符号化：Q(f(π))进一步练习第一百三十二页，共229页。所有实数的平方都是非负的。解：个体：每一个实数：以x代表函词：…的平方：以f表示谓词：…是非负的：以Q表示量词：所有：以∀表示符号化：(∀x)Q(f(x))x可以代表不同的个体，称为个体变元；相对地π等称为个体常元第一百三十三页，共229页。所有实数的平方都是非负的。另解：个体：每一个数：以z代表谓词：…是一个实数，以R表示函词：…的平方：以f表示谓词：…是非负的：以Q表示量词：所有：以∀表示符号化：(∀z)

[R(z)

Q(f(z))]

个体变元x和z的取值范围不同。个体变元的取值范围称为它的论域（个体域）。第一百三十四页，共229页。人总是要死的。有些人不怕死。如果论域是全人类，用D(x)表示“x是要死的”，用F(x)表示“x是不怕死的”，则人总是要死的。(∀x)D(x)有些人不怕死。(∃x)F(x)如果论域是全总个体域，用M(x)表示“x是人”，则人总是要死的。(∀x)

[M(x)

D(x)]有些人不怕死。(∃x)

[M(x)∧F(x)]M(x)是特性谓词，用以刻画论述对象具有“人”这一特征。特性谓词的使用有以下两条规则：（1）对全称量词，特性谓词作为蕴含式的前件而加入之；（2）对存在量词，特性谓词作为合取项而加入之；人总是要死的。(∀x)

[M(x)∧D(x)]？上述的意义是“所有的x都是人并且都是要死的”因而这样表示不正确。第一百三十五页，共229页。例：凡是有理数皆可写成分数解：x：数Q(x)：x是有理数F(x)：x可写成分数(∀x)

[Q(x)

F(x)]例：教室里有同学在说话。解：x：同学C(x)：x在教室里T(x)：x在说话(∃x)

[C(x)∧T(x)]第一百三十六页，共229页。例：对于任意x,y，都存在唯一的z，使x+y=z。解：(∀x)(∀y)(∃

z)[(x+y=z)∧(∀u)(x+y=uu=z)]注：量词的嵌套“存在唯一”的表示例：有一个整数大于其它每个整数。解：x,y:数Z(x):x是整数

(∃x){Z(x)∧(∀y)[Z(y)

∧~(y=x)

x>y]}第一百三十七页，共229页。例设有下列知识：①刘欢比他父亲出名。②高扬是计算机系的一名学生，但他不喜欢编程。③任何整数或者为正或者为负。

第一百三十八页，共229页。为了用谓词公式表示上述知识，首先需要定义谓词(1)BIGGER(x,y):x比y出名BIGGER(liuhuan,father(liuhuan))(2)COMPUTER(x):x是计算机系的LIKE(x,y):x喜欢yCOMPUTER(gaoyang)∧¬LIKE(gaoyang,programing)(3)I(x)：x是整数，P(x)：x是正数，N(x)：x是负数第一百三十九页，共229页。将下列命题符号化。（1）猫比老鼠跑得快。（2）有的猫比所有老鼠跑得快。（3）并不是所有的猫比老鼠跑得快。（4）不存在跑得同样快的两只猫。解设个体域为全总个体域。令C（x）：x是猫；M（y）：y是老鼠；Q（x，y）：x比y跑得快；L（x，y）：x和y跑得同样快。这4个命题分别符号化为：（1）xy[C（x）∧M（y）Q（x，y）]；（2）x{C（x）∧y[M（y）Q（x，y）]}；（3）{（xy[C（x）∧M（y）Q（x，y）]}；（4）{xy[C（x）∧C（y）∧L（x，y）]}。第一百四十页，共229页。置换例表达式P[x,f(y),B]的4个置换为s1={z/x,w/y}s2={A/y}s3={q(z)/x,A/y}s4={c/x,A/y}于是，我们可得到P[x,f(y),B]的4个置换的例，如下：

P[x,f(y),B]s1=P[z,f(w),B]P[x,f(y),B]s2=P[x,f(A),B]P[x,f(y),B]s3=P[q(z),f(A),B]P[x,f(y),B]s4=P[c,f(A),B]一般说来，置换是可结合的，但置换是不可交换的。第一百四十一页，共229页。合一合一（Unification)合一：寻找项对变量的置换，以使两表达式一致。即设有公式集F={F1，F2，…，Fn}，若存在一个置换s，使得F1s=F2s=…=Fns则称s为公式集F的一个合一。可合一：如果一个置换s作用于表达式集{Ei}的每个元素，则我们用{Ei}s来表示置换例的集。我们称表达式集{Ei}是可合一的。第一百四十二页，共229页。合一例如，设有公式集

F={P(x,y,f(y)),P(a,g(x),z)}

则下式是它的一个合一：

s={a/x,g(a)/y,f(f(a))/z}第一百四十三页，共229页。语义网络法语义网络是奎廉(J.R.Quillian)1968年在研究人类联想记忆时提出的一种心理学模型，认为记忆是由概念间的联系实现的。随后，奎廉又把它用作知识表示。1972年，西蒙在他的自然语言理解系统中也采用了语义网络表示法。1975年，亨德里克(G.G.Hendrix)又对全称量词的表示提出了语义网络分区技术。第一百四十四页，共229页。语义网络的基本概念

什么是语义网络(1/2)什么是语义网络

语义网络是一种用实体及其语义关系来表达知识的有向图。结点代表实体，表示各种事物、概念、情况、属性、状态、事件、动作等；弧代表语义关系，表示它所连结的两个实体之间的语义联系，它必须带有标识。语义基元语义网络中最基本的语义单元称为语义基元，可用三元组表示为：（结点1，弧，结点2）基本网元指一个语义基元对应的有向图例如：若有语义基元（A,R,B），其中，A、B分别表示两个结点，R表示A与B之间的某种语义联系，则它所对应的基本网元如下图所示：

ABR第一百四十五页，共229页。语义网络的基本概念

什么是语义网络(2/2)语义网络的简单例子

例用语义网络表示“鸵鸟是一种鸟”事实的表示：例：“雪的颜色是白的”规则的表示：例：规则R的含义是“如果A则B”鸵鸟鸟是一种雪白颜色ABR第一百四十六页，共229页。语义网络表达能力（1）实例关系：表示类与其实例之间的关系。（2）分类（泛化）关系：是指事物间的类属关系。（3）组装关系：如果下层概念是上层概念的一个方面或者一部分，则称它们的关系是组装关系。（4）属性关系：表示对象的属性及其属性值。（5）集合与成员关系：成员（或元素）与集合之间的关系。（6）逻辑关系（7）方位关系（8）所属关系：“具有”的意思。（9）语句或事件（10）谓词公式第一百四十七页，共229页。语义网络的基本概念

基本的语义关系(1/6)实例关系：ISA体现的是“具体与抽象”的概念，含义为“是一个”，表示一个事物是另一个事物的一个实例。例分类关系：AKO亦称泛化关系，体现的是“子类与超类”的概念，含义为“是一种”，表示一个事物是另一个事物的一种类型。例成员关系：A-Member-of体现的是“个体与集体”的关系，含义为“是一员”，表示一个事物是另一个事物的一个成员。例上述关系的主要特征最主要特征是属性的继承性，处在具体层的结点可以继承抽象层结点的所有属性。如以上例子鸟动物AKO张强共青团员A-Member-of人李刚ISA第一百四十八页，共229页。语义网络的基本概念

基本的语义关系(2/6)属性关系指事物和其属性之间的关系。常用的属性关系有：

Have：含义为“有”，表示一个结点具有另一个结点所描述的属性

Can：含义为“能”、“会”，表示一个结点能做另一个结点的事情例如：“鸟有翅膀”

Age:

含义为“年龄”，表示一个结点是另一个结点