1、主 讲：谢 榕 武汉大学国际软件学院1.1.学习目的和意义学习目的和意义 对自动化自动化、智能化智能化的追求是我们的永久 目标，使计算机具有智能、能够模仿人 的思维和行为，成为人们的理想和追求。u人工智能是一门具有实用价值实用价值的跨学科的科目。具有不同背景和专业的人们，正在从这个年轻的领域内发现某些新思想新思想和新方法新方法。u人工智能也是一门非常有趣的学科，我们不仅将学习人工智能基本原理基本原理, 而且将学习人工智能实实现技术现技术及其应用应用, 并了解国内外研究领域的最新最新进展进展和研究方向研究方向。2.2.人工智能的研究与应用领域人工智能的研究与应用领域 问题求解问题求解 自然语言理
2、解自然语言理解 自动定理证明自动定理证明 专家系统专家系统 智能控制及智能系统智能控制及智能系统 模式识别模式识别 机器人学机器人学 数据挖掘与知识发现数据挖掘与知识发现 人工生命人工生命3.3.本课程主要内容概要本课程主要内容概要u 探讨人工智能研究领域的探讨人工智能研究领域的发展状况发展状况及其主要及其主要应用领域应用领域u人工智能人工智能程序设计语言程序设计语言u 传统人工智能理论与方法传统人工智能理论与方法p 知识表示方法知识表示方法p 搜索推理技术搜索推理技术u 人工智能的新研究领域人工智能的新研究领域p 神经计算神经计算p 模糊计算模糊计算p 进化计算进化计算p 人工生命人工生命u
3、人工智能的主要应用人工智能的主要应用p 专家系统与知识发现专家系统与知识发现p 自动规划自动规划u人工智能人工智能最新进展最新进展与与研究方向研究方向第二章第二章 知识表示方法知识表示方法内容提要：知识与知识表示 状态空间表示问题归约表示 谓词逻辑表示语义网络表示 框架表示本体技术（New）2.1 知识与知识表示知识与知识表示u什么是知识？什么是知识？u知识的分类知识的分类u什么是知识表示？什么是知识表示？u知识表示方法知识表示方法什么是知识？什么是知识？u什么是知识？u知识是人类进行一切智能活动的基础。u知识是人们对于可重复信息之间联系的认识，是信息经过加工整理、解释、挑选和改造而形成的。所
4、以知识是人们对信息和信息之间联系的认识和人们利用这些认识解决实际问题的方法和策略。u培根：知识就是力量知识就是力量数据数据 信息信息 知识知识知 识信 息数 据概念概念例如：1313亿亿中国人口数已经达到中国人口数已经达到 13 13 亿亿中国是世界上人口最多的国家中国是世界上人口最多的国家“为了中国的可持续发展，我们必须继续坚持计划生育政策为了中国的可持续发展，我们必须继续坚持计划生育政策”是决策决策。p “1313亿亿” 是数据。p “中国人口数已经达到中国人口数已经达到 13 13 亿亿”是信息。p “中国是世界上人口最多的国家中国是世界上人口最多的国家”是知识。2.2.人工智能系统所关
5、心的知识人工智能系统所关心的知识u要使计算机系统具有智能，至少应使运行的系统拥有以下4个方面的知识。p 事实知识事实知识p 规则知识规则知识p 控制知识控制知识p 元知识元知识2.2.人工智能系统所关心的知识人工智能系统所关心的知识u事实知识事实知识 事实知识是有关问题环境的一些事物的知识，常以“是是”的形式出现。 如事物的分类、属性、事物间关系、科学事实、客观事实等。 事实是静态的、为人们共享的、可公开获得的、公认的知识，在知识库中属低层的知识。例如，雪是白色的、鸟有翅膀、张三李四是好朋友等。2.2.人工智能系统所关心的知识人工智能系统所关心的知识u规则知识规则知识 规则知识是有关问题中与事
6、物的行动、动作相联系的因果关系知识。 它是动态的，常以“如果如果那么那么”形式出现。 特别是启发式规则是属专家提供的专门经验知识，这种知识虽无严格解释但很有用处。例如，如果下雨，则出门带伞。2.2.人工智能系统所关心的知识人工智能系统所关心的知识u控制知识控制知识 控制知识是有关问题的求解步骤、技巧性知识，告诉怎么做一件事。 也包括当有多个动作同时被激活时应选哪一个动作来执行的知识。例如，从北京到上海，是乘飞机还是坐火车的问题，乘飞机较快、较贵；坐火车较慢、较便宜。2.2.人工智能系统所关心的知识人工智能系统所关心的知识u元知识元知识 元知识是有关知识的知识，是知识库中的高层知识。 包括怎样使
7、用规则、解释规则、校验规则、解释程序结构等知识。 元知识与控制知识是有重迭的，对一个大的程序来说，以元知识或说元规则形式体现控制知识更为方便，因为元知识存于知识库中，而控制知识常与程序结合在一起出现，从而不容易修改。例如，知识目录等。事实知识控制知识规则知识元知识人工智能系统人工智能系统2.2.人工智能系统所关心的知识人工智能系统所关心的知识 什么是知识表示？什么是知识表示？u人类拥有的知识如何才能被计算机系统所接受并用于实际问题的求解？必须以合适的方式将面向将面向人的知识转化为计算机系统所能接受的形式人的知识转化为计算机系统所能接受的形式，即知识表示研究的内容。u知识表示是指将知识符号化，并
8、输入计算机的过程和方法。p用给定的结构，按一定的原则、组织方式表示知识。p解释所表示知识的含义。u理想的知识表示方法是模拟人脑的知识存储结构，但目前还难以做到。合理的知识表示能使得问题求解变得容易，并具有较高的求解效率。人工智能中几种知识表示方法人工智能中几种知识表示方法u状态空间法u问题归约法u谓词逻辑法u语义网络法u本体技术u框架表示u剧本表示u过程表示u面向对象法2.2 2.2 状态空间表示状态空间表示1. 问题求解2. 问题状态描述3. 状态图示法例1：猴子和香蕉问题例2：推销员旅行间题1.1.问题求解问题求解u问题求解问题求解(problem solving)涉及归约、推断、决策、规
9、划、常识推理、定理证明和相关过程的核心概念。u在计算机程序上的应用：自然语言处理、情报检索、自动程序设计、机器人学、景物分析、博弈、专家系统和数学定理证明等。u典型问题包括：p 求解智力测验难题p 求证逻辑或数学定理p 求解最短路径p 求解能够取胜的博弈走步序列p 求解符号积分问题的变换序列1.1.问题求解问题求解u问题求解与人工智能问题求解与人工智能许多问题求解方法是采用试探搜索方法试探搜索方法的。这些方法是通过在某个可能的解空间内寻找一个解来求解问题的。1. 1. 问题求解问题求解u什么是状态空间法状态空间法？状态空间法状态空间法是基于解答空间的问题表示和求解方法，它是以状态状态(stat
10、us)和算符算符(operator)为基础来表示和求解问题的。u问题求解技术两个主要的方面 p问题的表示:如果描述方法不对，对问题求解会带来很大的困难；p求解的方法:采用试探搜索方法。2. 2. 问题状态描述问题状态描述u状态空间法三要点 p 状态状态（state）p 算符算符（operator）p 状态空间状态空间（state space）定义定义u状态状态(state)p描述某类不同事物间的差别而引入的一组最少变量q0， q1 ， qn的有序集合。p矢量形式如下： Q =q0, q1, , ,qnT式中每个元素qi(i=0,1，n)为集合的分量，称为状态变量。给定每个分量的一组值就得到一个
11、具体的状态，如 qk =q0k, q1k, ,qnkT定义定义u算符算符（operator）p使问题从一种状态变化为另一种状态的手段称为操作符或算符。p操作符可为走步走步、过程过程、规则规则、数学算子数学算子、运算符号或逻辑符号运算符号或逻辑符号等。定义定义u问题的状态空间问题的状态空间(state space)p表示该问题全部可能状态及其关系的图p包含三种说明的集合，即 所有可能的问题的初始状态集合初始状态集合S 操作符集合操作符集合F 目标状态集合目标状态集合G。可把状态空间记为三元状态(S，F，G)。例：三数码难题（例：三数码难题（3 Puzzle Problem3 Puzzle Pro
12、blem）状态空间Q=(S，F，G)，其中初始状态集合S= 操作符集合F=上移2、左移1，下移3，右移2，上移1目标状态集合G= 五子棋跳棋国际象棋应用实例应用实例中国象棋u对一个问题的状态描述，必须确定 3 件事：p 状态描述方式，特别是初始状态描述初始状态描述p 操作符集合及其对状态描述的作用操作符集合及其对状态描述的作用p 目标状态描述目标状态描述的特性2.2.问题状态描述问题状态描述u用十五数码难题(15 puzzle problem)来说明状态空间表示的概念。u十五数码难题十五数码难题：由15个编有1至15并放在44方格棋盘上的可走动的棋子组成。棋盘上总有一格是空的，以便可能让空格周
13、围的棋子走进空格，这也可以理解为移动空格。初始棋局目标棋局3.3.状态空间表示详释状态空间表示详释如何把初始棋局变换为目标棋局呢？u首先把适用的算符用于初始状态，以产生新的状态；然后，再把另一些适用算符用于这些新的状态；这样继续下去，直至产生目标状态为止。算符：棋子算符：棋子3 3右移右移或空格左移或空格左移中间棋局中间棋局初始棋局初始棋局解题过程解题过程目标棋局目标棋局u把初始状态可达到的各状态所组成的空间设想为一幅由各种状态对应的节点组成的图。这种图称为状态图状态图。图：十五数码难题部分状态图中间状态初始状态解题过程解题过程u对于某些最优化问题，仅仅找到到达目标的任一路径是不够的，还必须找
14、到按某个准则实现最优化的路径实现最优化的路径（例如，下棋走步最少）。初始状态解题过程解题过程图：十五数码难题部分状态图3. 3. 状态图示法状态图示法1. 图论中的几个术语p节点(node)p弧线(arc)p有向图(directed graph)p后继节点(descendant node)与父辈节点(parent node)p路径(route)p代价（cost）p显式表示p隐式表示图论中的几个术语图论中的几个术语u节点节点(node)图形上的汇合点，用来表示状态、事件和时间关系的汇合，也可用来指示通路的汇合。u弧线弧线(arc)节点间的连接线。u有向图有向图(directed graph)一对
15、节点用弧线连接起来，从一个节点指向另一个节点。图论中的几个术语图论中的几个术语u后继节点后继节点(descendant node)与父辈节点父辈节点(parent node)如果某条弧线从节点ni指向节点nj ，那么节点nj就叫做节点ni的后继节点或后裔，而节点ni叫做节点nj的父辈节点或祖先。ninju路径路径(route)某个节点序列(ni1, ni2, nik)当j=2，3，k时，如果对于每一个ni ，j-1都有一个后继节点ni j存在，那么就把这个节点序列叫做从节点ni1至节点nik的长度为k的路径。ni1nikni2图论中的几个术语图论中的几个术语u代价代价（cost）用c(ni,
16、nj)来表示从节点ni指向节点nj的那段弧线的代价。两节点间路径的代价等于连接该路径上各节点的所有弧线代价之和。ninj图论中的几个术语图论中的几个术语u显式表示显式表示各节点及其具有代价的弧线由一张表明确给出。此表可能列出该图中的每一节点、它的后继节点以及连接弧线的代价。u隐式表示隐式表示节点的无限集合si作为起始节点是已知的。后继节点算符也是已知的，它能作用于任一节点以产生该节点的全部后继节点和各连接弧线的代价。u产生式系统由下列3部分组成：p 一个总数据库一个总数据库(global database)：它含有与具体任务有关的信息p 一套规则一套规则：它对数据库进行操作运算。每条规则由左右
17、两部分组成，左部鉴别规则的适用性或先决条件，右部描述规则应用时所完成的动作。规则的基本形式是“如果那么”，即“ifthen”。我们把这种规则称之为产生式规则。应用规则来改变数据库，就象应用算符来改变状态一样。p 一个控制策略一个控制策略：它确定应该采用哪一条适用规则，而且当数据库的终止条件满足时，就停止计算。控制策略由控制系统选择和确定。产生式系统的方法产生式系统的方法例例1 1：猴子和香蕉问题：猴子和香蕉问题u猴子和香蕉问题猴子和香蕉问题（monkey and banana problem ）：在一个房间内有一只猴子（可把这只猴子看做一个智能机器猴）、一个箱子和一束香蕉。香蕉挂在天花板下方，
18、但猴子的高度不足以碰到它。这只猴子怎样才能摘到香蕉呢？这只猴子怎样才能摘到香蕉呢？解题过程解题过程用一个四元表列(W,x,Y,z)来表示这个问题的状态，其中:W猴子的水平位置x当猴子在箱子顶上时取x=1；否则取x=0Y箱子的水平位置z当猴子摘到香蕉时取z=1；否则取z=0解题过程解题过程u 该问题的操作（算符）：1.goto（U）表示猴子走到水平位置U或者用产生式规则表示为:（W，0，Y，z）goto（U）（U，0，Y，z）2.pushbox（V）猴子把箱子推到水平位置V，即有:（W，0，W，z）pushbox（V）（V，0，V，z）3.climbbox猴子爬上箱顶，即有：（W，0，W，z）c
19、limbbox（W，1，W，z）4.grasp猴子摘到香蕉，即有：（c，1，c，0）grasp （c，1，c，1）u 该初始状态变换为目标状态的操作序列为：goto(b), pushbox(c), climbbox, grasp四元表列(W,x,Y,z)： W猴子的水平位置 x当猴子在箱子顶上时 取x=1；否则取x=0 Y箱子的水平位置 z当猴子摘到香蕉时取 z=1；否则取z=0图：猴子和香蕉问题的状态空间图猴子和香蕉问题的演示过程猴子和香蕉问题的演示过程例例2 2：推销员旅行问题：推销员旅行问题 推销员旅行问题推销员旅行问题：一个推销员计划出访推销产品。他从一个城市（如A）出发，访问每个城市
20、一次，且最多一次，然后返回城市A。要求寻找最短路线。u总数据库总数据库是到目前为止所访问过的城市表。初始数据库被描述为表(A)。不允许目录表中任一城市出现多于一次，只有城市A例外，但也只有当所有其它城市均已出现之后，才能再次出现A。u规则规则对应于决策：(a)下一步走向城市A；(b)下一步走向城市B；(e)下一步走向城市E。一条规则除非能把某个数据库变为一合法数据库，否则就不适用于这个数据库。图：推销员旅行问题状态空间图u控制策略控制策略任一以A为起点和终点，并出现所有其它城市的总数据库，都满足终止条件终止条件。提出条件：必须是具有最短距离最短距离的旅程。2.3 2.3 问题归约法问题归约法1
21、. 问题归约描述2. 问题归约表示3. 例：梵塔难题1.1.问题归约描述问题归约描述u问题归约法(problem reduction)是另一种问题描述与求解方法。u先把问题分解为子问题和子-子问题，然后解决较小的问题。对该问题的某个具体子集的解答就意味着对原始问题的一个解答。1.1.问题归约描述问题归约描述u问题归约表示的组成部分：p 一个初始问题描述p 一套把问题变换为子问题的操作符p 一套本原问题描述u问题归约的实质：从目标(要解决的问题)出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个平凡的本原问题集合。2.2.问题归约表示问题归约表示( (与或图表示）与或图表示
22、）u与或图与或图一般地，用一个类似图的结构来表示把问题归约为后继问题的替换集合，这种结构图叫做问题归问题归约图约图，或叫与或图与或图。一些关于与或图的术语：u与或图与或图：由与节点及或节点组成的结构图。u或节点或节点：只要解决某个子问题就可解决其父辈问题的节点集合，如（N，M，H）。u与节点与节点：只有解决所有子问题，才能解决其父辈问题的节点集合，如（B,C)和（D,E,F）各个结点之间用一小圆弧连接标记。u终叶节点终叶节点：对应于原问题的本原节点。或节点或节点与节点与节点终叶节点终叶节点u可解节点可解节点p 终叶节点终叶节点是可解节点(因为它们与本原问题相关连)。p 如果某个非终叶节点含有或
23、后继节点或后继节点，那么只要当其后继节点至少有一个是可解的时，此非终叶节点才是可解的。p 如果某个非终叶节点含有与后继节点与后继节点，那么只有当其后继节点全部为可解时，此非终叶节点才是可解的。终叶节点终叶节点可解节点可解节点可解节点可解节点u不可解节点不可解节点p 没有后裔的非终叶节点非终叶节点为不可解节点。p 如果某个非终叶节点含有或后继节点或后继节点，那么只有当其全部后裔为不可解时，此非终叶节点才是不可解的。p 如果某个非终叶节点含有与后继节点与后继节点，那么只要当其后裔至少有一个为不可解时，此非终叶节点才是不可解的。不可解节点不可解节点不可解节点不可解节点不可解节点不可解节点与或图的构成
24、规则与或图的构成规则u规则规则1 1: 与或图中的每个节点代表一个要解决的单一问题或问题集合。图中所含起始节点起始节点对应于原始问题。u规则规则2 2: 对应于本原问题的节点，叫做终叶节点终叶节点，它没有后裔。u规则规则3 3: 对于把算符应用于问题A的每种可能情况，都把问题变换为一个子问题集合；有向弧线自A指向后继节点表示所求得的子问题集合。起始节点起始节点终叶节点终叶节点有向弧线有向弧线u规则规则4: 一般对于代表两个或两个以上子问题集合的每个节点，有向弧线从此节点指向此子问题集合中的各个节点。由于只有当集合中所有的项都有解时，这个子问题的集合才能获得解答。u规则规则5: 在特殊情况下，当
25、只有一个算符可应用于问题A，而且这个算符产生具有一个以上子问题的某个集合时，由上述规则3和规则4所产生的图可以得到简化。因此，代表子问题集合的中间或节点可以被略去，如下图所示。规则规则4规则规则5u梵塔难题梵塔难题（Tower of Hanoi puzzle）有3个柱子(1，2和3)和3个不同尺寸的圆盘（A，B和C）。在每个圆盘的中心有一个孔，所以圆盘可以堆叠在柱子上。最初，3个圆盘都堆在柱子1上：最大的圆盘C在底部，最小的圆盘A在顶部。要求把所有圆盘都移到柱子3上，每次只许移动一个，而且只能先搬动柱子顶部的圆盘，还不许把尺寸较大的圆盘堆放在尺寸较小的圆盘上。3.3.例：梵塔难题例：梵塔难题美
26、_课程_汉诺塔算法演示.flv解题要点解题要点u将原始问题归约为一个较简单问题集合。u要把所有圆盘都移至柱子3，我们必须首先把圆盘C移至柱子3，而且在移动圆盘C至柱子3之前，要求柱子3必须是空的。u只有在移开圆盘A和B之后，才能移动圆盘C，而且圆盘A和B最好不要移至柱子3,否则就不能把圆盘C移至柱子3。因此，首先应该把圆盘A和B移到柱子2上。u然后才能够进行关键的一步，把圆盘C从柱子1移至柱子3，并继续解决难题的其余部分。将原始难题归约（简化）为下列子难题：u移动圆盘A和B移至柱子2的双圆盘难题。u移动圆盘C移至柱子3的单圆盘难题。u移动圆盘A和B移至柱子3的双圆盘难题。X X XCBA梵塔问
27、题归约图：u子问题2可作为本原问题考虑。子问题1和子问题3也可被归约为本原问题。u与或图与或图(AND/OR graph)能有效地说明如何由问题归约法求得问题的解答。多圆盘梵塔难题演示多圆盘梵塔难题演示http:/ 2.4 谓词逻辑法谓词逻辑法1.命题逻辑 vs.谓词逻辑2.谓词演算3.谓词公式4.置换与合一5.例：机器人行为规划1.1.命题逻辑命题逻辑 vs.vs.谓词逻辑谓词逻辑u我们能够很容易地把客观世界的各种事实表示为逻辑命题逻辑命题。u命题，是数理逻辑中最基本的概念，实际上就是一个意义明确，能分辨真假的陈述句。例如：中国是世界上人口最多的国家中国是世界上人口最多的国家。u最基本的命题
28、逻辑的知识表达是给一个对象命名或陈述一个事实。1.1.命题逻辑命题逻辑 vs.vs.谓词逻辑谓词逻辑u但命题逻辑有一定的局限性。u例1:“李明是软件工程班级学生，王华也是软件工程班李明是软件工程班级学生，王华也是软件工程班级学生级学生”。无法得出李明和王华相似性的结论。u例2：“所有的人都要学习所有的人都要学习”，如果不对问题进行量化，我们就必须一个一个地写出已经知道的人都需要学习的独立命题。u谓词逻辑(predicate logic)允许我们表达那些无法用命题逻辑性应地加以表达的命题。u在谓词逻辑中，我们能够表达客观世界事实为由合适公合适公式（式（WFFWFF）写成的命题。u谓词逻辑可作为知
29、识的一种表示方法。2.2.谓词演算谓词演算u谓词逻辑的基本组成部分：谓词符号、变量符号、函数符号、常量符号、括号和逗号u原子公式原子公式(atomic formulas)由若干谓词符号和项组成的谓词演算。原子公式是谓词演算基本积木块。u运用连词和量词能够组合成多个原子公式以构成比较复杂的合式公式合式公式。原子公式原子公式u例1，要表示机器人机器人(ROBOT)(ROBOT)在号房间在号房间(r1)(r1)内内，可以应用原子公式:当机器人机器人ROBOTROBOT移到房间移到房间r2r2时，原子公式可以表示为：这两个原子公式的通用形式就是原子公式原子公式u例2,“李的母亲和他的父亲结婚李的母亲和
30、他的父亲结婚”这句话的原子公式表示如下：连词连词u与与合取合取（conjunction）p用连词把几个公式连接起来而构成的公式。p合取项是合取式的每个组成部分。p例：我喜爱音乐和绘画我喜爱音乐和绘画LIKE(I，MUSIC)LIKE(I，PAINTING)u或或析取析取（disjunction）p用连词把几个公式连接起来而构成的公式。p析取项是析取式的每个组成部分。 p例：李力打篮球或踢足球李力打篮球或踢足球PLAYS(LILI，BASKETBALL)PLAYS(LILI，FOOTBALL)连词连词u蕴涵蕴涵（Implication） p用连词=连接两个公式所构成的公式，表示“如果-那么”语句
31、。p蕴涵的左式叫做前项，右式叫做后项。p例：如果刘翔跑得最快，那么他取得冠军如果刘翔跑得最快，那么他取得冠军RUNS(LIUXIANG，FASTEST) = WINS(LIUXIANG，CHAMPION)u非非（NOT）p用来否定一个公式的真值，可用、表示。p例：机器人不在机器人不在2 2号房间内号房间内INROOM(ROBOT，r2）量词量词u全称量词全称量词(Universal Quantifier)p若一个原子公式P(x)，对于所有可能变量x都具有T值，则用(x)P(x)表示。p例：所有的机器人都是灰色的所有的机器人都是灰色的（x)ROBOT(x) = COLOR(x,GRAY)p例：所
32、有学生都穿彩色制服所有学生都穿彩色制服（x)Student(x) = Uniform(x,Color)u存在量词存在量词(Existential Quantifier)p若一个原子公式P(x)，至少有一个变元X，可使P(X)为T值，则用( x)P(x)表示。p例：1 1号房间内有个物体号房间内有个物体(x)INROOM(x,r1)3.3.谓词公式谓词公式谓词公式的定义u原子谓词公式原子谓词公式用P(x1,x2,xn)表示一个n元谓词公式，其中P为n元谓词，x1,x2,xn为客体变量或变元。通常把P(x1,x2,xn)叫做谓词演算的原子公式，或原子谓词公式。u分子谓词公式分子谓词公式可以用连词把
33、原子谓词公式组成复合谓词公式，并把它叫做分子谓词公式。u合式公式合式公式(WFF,well-formed formulas)的递归定义(1)原子谓词公式是合式公式。(2)若A为合式公式，则A也是一个合式公式。(3)若A和B都是合式公式，则(AB),(AB),(A=B)也都是合式公式。(4)若A是合式公式，x为A中的自由变元，则(x)A,(x)A都是合式公式。p只有按上述规则(1)至(4)求得的那些公式，才是合式公式。谓词公式谓词公式例如：“对于所有的对于所有的x x，如果，如果x x是整数，则是整数，则x x或为正的或者为负的。或为正的或者为负的。”(x)(I(x)=(p(x)N(x)，其中I
34、(x)表示“x是整数”,P(x)表示“x是正数”，N(x)表示“x是负数”谓词公式谓词公式u合式公式的性质合式公式的真值表：谓词公式谓词公式u等价关系(Equivalence)如果两个合式公式，无论如何解释，其真值表都是相同的,那么我们就称此两个合式公式是等价等价的的。u等价关系等价关系(Equivalence)(Equivalence)p 否定之否定 (P) 等价于 Pp PQ 等价于 P=Qp 狄.摩根定律(PQ) 等价于 PQ(PQ) 等价于 PQp 分配律P(QR) 等价于 (PQ)(PR)P(QR) 等价于 (PQ)(PR)u交换律PQ 等价于 QPPQ 等价于 QPu结合律(PQ)
35、R 等价于 P(QR)(PQ)R 等价于 P(QR)u逆否律P = Q 等价于 Q = Pu其它等价关系(x)P(x) 等价于（x)P(x)(x)P(x) 等价于（x)P(x)（x）P(x)Q(x) 等价于（x）P(x)(x)Q(x）（x）P(x)Q(x) 等价于（x）P(x)（x）Q(x) （x)P(x) 等价于（y)P(y) （x)P(x) 等价于（y)P(y) 下面举个用谓词演算来表示的英文句子的实例：For every set x, there is a set y, such that the cardinality of y is greater than the cardinal
36、ity of x.4.4.置换与合一置换与合一u置换置换p 假元推理假元推理，是由合式公式W1和W1W2产生合式公式W2的运算。p 全称化推理全称化推理，是由合式公式(x)W(x)产生合式公式W(A)，其中A为任意常量符号。u举例：表达式Px，f(y)，B的一个置换为s1=z/x，w/y，则Px，f(y)，Bs1 = Pz，f(w)，B一个表达式的置换就是在该表达式中用置换项置换变量。4.4.置换与合一置换与合一u合一合一p 寻找项对变量的置换，以使两表达式一致，叫做合一。如果一个置换s作用于表达式集Ei的每个元素，则用Eis来表示置换例的集。称表达式集Ei是可合一的。如果存在一个置换s使得：
37、E1s=E2s=E3s=那么称此s为Ei的合一者，因为s的作用是使集合Ei成为单一形式。u 举例：表达式Px，f(y)，B和表达式Px，f(B)，B的合一者p 表达式Px，f(y)，B的一个置换为s=A/x，B/y，则 Px，f(y)，Bs = PA，f(B)，Bp 表达式Px，f(B)，B的一个置换为s=A/x，B/y，则：Px，f(B)，Bs = PA，f(B)，B , s为二者的合一者。5.5.例：机器人行为规划例：机器人行为规划u设有个含有凹室(alcove)的房间里有两张桌子A和B、一个机器人(robot)和一个箱子(box)。为了让机器人从凹室出发，将在桌子A上的箱子移到桌子B上，
38、然后同到凹室。解题过程解题过程u本问题涉及的常量定义为：机器人：robot积木块：box凹室：alcove桌子：A桌子：B解题过程解题过程Step1Step1:定义与问题有关的谓词： Table(x) x是桌子 Empty(y) y手中是空的 At(y，z) y在z附近 Holds(y，w) y手中拿着w On(w,x) w在x之上这些谓词表达了事物之间的关系，其中，变量x,y,z,w的客体域分别为A,B，robot，A，B，a1cove，box。解题过程解题过程Step2Step2:根据问题的描述，将问题的初始状态和目标状态分别用谓词公式表示出来p初始状态为：At（robot，a1cove）
39、 Empty(robot) 0n(box，A) Table(A) Table(B)p目标状态为下列语句的合取:At(robot，a1cove) Empty(robot) on(box，B) Table(A) Table(B)解题过程解题过程Step3Step3:定义操作、条件和行为u如何从初始状态转移到目标状态，机器人要通道一系列的操作才能实现。Go-to-A(x)表示机器人从x处走到A处Pick-up-box(x)表示机器人从x处拿起箱子Set-down-box(x)表示机器人在x处放下箱子u在机器人行动规则中，通常需要为每一个操作定义条件和行动。例如：Pick-up-box(A)条件：on
40、(箱子，A)At(机器人，A)Empty(机器人)行动：删除Empty(机器人)增加Holds(机器人，箱子)u如何从初始状态转移到目标状态，机器人要通道一系列的操作才能实现。机器人行动规划的问题求解过程为：u 初始状态At(机器人，Alcove)Empty(机器人)on(箱子，A)Table(A)Table(B)u = 从 Go-to-A(x)At(机器人，A)Empty(机器人)0n(箱子，A)Table(A)Table(B)u =Pick-up-box(x)At(机器人，A)Ho1ds(机器人，箱子)Table(A)Table(B)u =Go-to-B(x)At(机器人，B)Ho1ds(
41、机器人，箱子)Table(A)Table(B)u =Set-down-box(x)At(机器人，A)Empty(机器人)on(箱子，B)Table(A)Table(B)u =Go-to-A1cove(x)At(机器人，Alcove)Empty(机器人)0n(箱子，B)Table(A)Table(B)谓词逻辑表示法的应用谓词逻辑表示法的应用u尽管谓词逻辑还有不尽入意之处，但确是一种应用较早，较广泛，也是较成功的知识表示方法，它比较适用于用定理证明方法求解问题定理证明方法求解问题的系统。例如，pGreen(1969)研制的自动问答系统，用逻辑方法表达知识，以定理证明方式推理，它是进行化学等方面的问
42、题解答的通用系统。pFikes(1971)研制的机器人行动规划系统，在问题求解中采用了演绎推理方法，规划决策采用了“目标-手段”分析法。pFilman(1976)研制了机器博弈系统。pKoWalski(1979)研制了问题求解系统。2.5 2.5 语义网络法语义网络法1.语义网络的概念及其结构2.语义网络法的表示3.语义网络表示下的推理4.语义网络表示法举例l Google翻译工具l MS Word拼写与语法检查功能语法语法 vs.vs.语义语义l 一种语言是合法句子合法句子的集合。l什么样的句子是合法的呢？ 语法和语义。 语法：和文法结构有关 语义：和按照这个结构所组合的单词符号的意义有关
43、e.g.雪是白的。 - 语法正确,语义正确雪是红的。- 语法正确,语义错误2.5 2.5 语义网络法语义网络法u语义网络最初被提出是为了表达词汇之间的语义关系。后来，人们很快地发现语义网络在逻辑推理方面的潜在能力，从而使语义网络成为人工智能的一种知识表示方法获得迅速发展。u“语义”一词主要是指语言结构(如词、短语、句子、段落等)及其意义上的联系。u客观世界中的事物相互间除了具有因果关系、类属关系等表面上的一些关系外，各事物、各概念之间还存在着含义上的联系或者语义上的联系。图：狗的身体构成图：生物分类2.5 2.5 语义网络法语义网络法u1968年J.R.Quillian在研究人类联想记忆时提出
44、语义网语义网络络这一心理学模型。他认为，记忆是由概念间的联系实现的。u1972年，Simon首先将语义网络表示法用于自然语言理自然语言理解系统解系统。 随后在他设计的可教式语言理解器可教式语言理解器（Teachable Language Comprehenden, TCL）中将这种心理学模型（语义网络）用于知识表示。1.1.语义网络的概念及结构语义网络的概念及结构u语义网络就是为了描述概念概念、事物事物、属性属性、情况情况、动作动作、状态状态等以及它们之间的语义联系语义联系而引入的。u语义网络是知识的一种图解表示。p 它由节点节点和弧线弧线组成。p 节点节点用于表示实体、概念和情况等。p 弧线
45、弧线用于表示节点间的关系。p 弧上的标注标注表示被连接的两个节点间的某种语义联系或语义关系。BRAu语义网络表示知识的步骤u语义网络中常用的语义联系u二元语义网络的表示u多元语义网络的表示2.2.语义网络法的表示语义网络法的表示uStep1Step1: 确定问题中的所有对象所有对象以及各对象的属性各对象的属性uStep2Step2: 确定所讨论对象间的关系对象间的关系uStep3Step3: 将各对象作为语义网络的一个节点，各对象间的关系作为网络中的各节点间的弧，连接形成语义网络形成语义网络。节点可代表一个事物或一个具体概念，也可代表某种情况、事件或某一动作。当节点表示某种事件或某一动作，可以
46、从该节点引出一组向外的弧，用于指出事件的因果或动作的主体及客体。语义网络表示知识的步骤语义网络表示知识的步骤u语义联系反映了节点间的语义关系。u常用的语义联系：p实例联系p泛化联系p聚集联系p属性联系p语义网络中常用的语义联系语义网络中常用的语义联系语义网络中常用的语义联系语义网络中常用的语义联系u实例联系实例联系 用于表示实例节点与所属类节点之间的联系，常用语言“是一个”描述，可表示为“ISA”或“is-a”。u泛化联系泛化联系 用于表示一种类节点与更抽象类节点之间的联系，常用语言“是一种”描述，可表示为“a-kind-ofa-kind-of”或AKOAKO。 AKO是一种偏序联系，通过AK
47、O可以将问题中的所有节点组织成一个AKO层次网络。语义网络中常用的语义联系语义网络中常用的语义联系u聚集联系聚集联系 用于表示某一个体与其组成成分之间的联系，通常用PART-OFPART-OF表示。 聚集联系基于概念的分解性，将高层概念分解为若干低层概念的集合。语义网络中常用的语义联系语义网络中常用的语义联系u属性联系属性联系用于表示个体、属性及其取值之间的联系，通常用有向弧表示属性，用这些弧所指向的节点表示各自的值。语义网络中常用的语义联系语义网络中常用的语义联系u其它联系其它联系在客观世界中，事物间的联系是多种多样的、千变万化的。在使用语义网络进行知识表示时，可根据需要对事物间的各种联系进
48、行定义。语义网络中常用的语义联系语义网络中常用的语义联系二元语义网络的表示二元语义网络的表示u1.表示简单的事实两节点以“是一个”（ISA）链相连。例1：所有的燕子都是鸟 二元语义网络的表示二元语义网络的表示u2.表示占有关系和其它情况例2：小燕是一只燕子，燕子是鸟；巢-1是小燕的巢，巢-1是巢中的一个。二元语义网络的表示二元语义网络的表示u3.选择语义基元试图用一组基元来表示知识，以便简化表示，并可用简单的知识来表示更复杂的知识。例例3 3：我椅子的颜色是咖啡色的；椅子包套是皮革；椅子是一种家具；椅子是座位的一部分；椅子的所有者是X；X是个人。多元语义网络的表示多元语义网络的表示u语义网络是
49、一种网络结构。从本质上讲，结点之间的连接是二元关系。u例如，TRIANGLE(a,b,c)表示一个三角形由三条边a,b,c构成，可表述为,cat(a,b)cat(b,c) cat(c,a)其中，cat表示将两条边串接起来。u如果要表示的事实是多元关系多元关系，必须将多元关系转化为二元关系。u把多元关系转化成一组二元关系的组合，即二元关系的二元关系的合取合取。具体地，多元关系R(X1, X2,Xn)可以转换成R1(X11, X12)R2(X21, X22)Rn(Xn1, Xn2)3.3.语义网络表示下的推理语义网络表示下的推理u语义网络的推理过程主要有两种。p继承p匹配3.3.语义网络表示下的推
50、理语义网络表示下的推理u1. 继承在语义网络中，所谓的继承是把对事物的描述从概念节点或类节点传递到实例节点。u一共有3种继承过程。p 值继承p “如果需要”继承p “缺省”继承值继承值继承u值继承最简单的值继承是ISA关系下的直接继承。 ISAISA是IS-A的缩写，表示“是一种”关系。uAKOAKO(a kind of)弧也用于语义网络中的描述特性的继承。AKO是A-KIND-OF的缩写，表示“是某种”关系。图：语义网络的值继承uISA和AKO链直接地表示类的成员关系以及子类和类之间的关系，提供了一种把知识从某一层传递到另一层的途径。“如果需要如果需要”继承继承u当不知道某个值时，可以利用已
