人工智能98415ppt课件

1 第二部分知识表示方法 2 知识是一切智能行为的基础 也是人工智能的重要研究对象 要使计算机具有智能 就必须使它具有知识 而要使计算机具有知识 首先必须解决知识的表示问题 知识表示包括知识表示的概念和知识表示方法 对知识表示方法 又可根据所表示知识的确定化程度 分为确定性知识表示和不确定性知识表示 3 知识与知识表示的概念状态空间法问题规约法谓词逻辑法语义网络法框架表示法 内容提要 4 1 知识与知识表示的概念 知识1 知识的属性2 知识的类型二 知识表示1 知识表示的要求2 知识表示观点3 知识表示的方法 5 知识是人们在改造客观世界的实践中积累起来的认识和经验 通常 人们对客观世界的描述是通过数据和信息来实现的 数据和信息是两个密切相关的概念 数据是信息的载体和表示 信息是数据在特定场合下的含义 或者说信息是数据的语义 一 知识 6 知识是对信息进行智能性加工所形成的对客观世界规律性的认识 把有关信息关联在一起所形成的信息结构称为知识 信息 与 关联 是构成知识的两个要素 信息之间关联的形式可以多种多样 其中最常用的一种形式是 如果 那么 例如 如果他学过人工智能课程 那么他应该知道什么叫知识 7 1 真假性与相对性 1 知识的属性 真假性是指可以通过实践或推理来证明知识为真或为假 相对性是指知识的真与假是相对于某些条件 环境及时间而言的 即知识一般不是无条件的真或无条件的假 而是相对于一定条件的 8 知识的不确定性包括不完备性 不确定性与模糊性 2 不确定性 知识的不完备性是指在解决问题时不具备解决该问题所需要的全部知识 知识的不确定性是指知识所具有的既不能完全被确定为真 又不能完全被确定为假的特性 知识的模糊性是指知识的 边界 不明确的特性 9 矛盾性是指同一个知识集中的不同知识之间相互对立或不一致 即从这些知识出发 会推出不一致的结论 相容性是指同一个知识集中的所有知识之间互相不矛盾 3 矛盾性和相容性 10 可表示性是指知识可以用适当的形式表示出来 例如语言 文字 图形 神经元网络等 可利用性是指知识可以被用来解决各种各样的问题 4 可表示性与可利用性 11 1 按知识的性质 2 知识的类型 概念命题公理定理规则方法 12 常识性知识 是指通用通识的知识 即人们普遍知道的 适应于所有领域的知识 领域性知识 是指面向某个具体专业的专业性知识 这些知识只有该领域的专业人员才能够掌握和运用它 2 按知识的作用范围 13 事实性知识 也称叙述性知识 是用来描述问题或事物的概念 属性 状态 环境及条件等情况的知识 过程性知识 是用来描述问题求解过程所需要的操作 演算或行为等规律性的知识 它指出在问题求解过程中如何使用那些与问题有关的事实性知识 即用来说明在那些叙述性知识成立的时候该怎么办 控制性知识 也称元知识或超知识 是关于如何运用已有知识进行问题求解的知识 因此 也称为关于知识的知识 3 按知识的作用 14 表层知识是指客观事物的现象以及这些现象与结论之间关系的知识 深层知识是指事物本质 因果关系内涵 基本原理之类的知识 例如 理论知识 理性知识等 4 按知识的层次 15 确定性知识 是可以给出其真值为 真 或 假 的知识 这些知识是可以精确表示的知识 不确定性知识 是指具有 不确定 特性的知识 不确定性的概念包含不精确 不完备和模糊 5 按知识的确定性 16 逻辑性知识 是反映人类逻辑思维过程的知识 例如人类的经验性知识 它对应着逻辑思维 形象性知识 是通过事物的形象建立起来的知识 它对应着形象思维 例如 一个人的相貌 要用文字来描述非常困难 但要亲眼见到这个人 就很容易在头脑中形成这个人的概念 6 按知识的结构及表现形式 17 所谓知识表示是对知识的一种描述 即用一些约定的符号把知识编码成一组计算机可以接受的数据结构 所谓知识表示过程就是把知识编码成某种数据结构的过程 同一知识可以有多种不同的表示形式 而不同表示形式所产生的效果又可能不一样 二 知识表示 18 1 表示能力知识表示能力是指能否正确 有效地将问题求解所需要的各种知识表示出来 知识表示能力包括以下三个方面 一是知识表示范围的广泛性 二是领域知识表示的高效性 三是对非确定性知识表示的支持程度 1 知识表示的要求 19 2 可利用性知识的利用是指使用知识进行推理 以求得问题的解 知识的可利用性包括对推理的适应性和对高效算法的支持性 3 可组织性与可维护性知识的组织是指把有关知识按照某种方式组成一种知识结构 知识维护是指在保证知识的一致性与完整性的前提下对知识所进行的增加 删除 修改等操作 20 4 可实现性所谓可实现性是指知识表示要便于在计算机上实现 便于直接由计算机对其进行处理 5 自然性与可理解性自然性是指知识表示形式要符合人们的日常习惯和思维方式 可理解性是指所表示的知识应易读 易懂 易获取 易维护 21 1 陈述性观点陈述性知识表示 Declarativeknowledgerepresentation 是指以陈述的方式把知识用一定的数据结构表示出来 即把知识看作一种特殊的数据 知识表示说明描述的对象是什么 不涉及如何运用知识的问题 2 知识表示观点 22 2 过程性观点过程性知识表示 Proceduralknowledgerepresentation 是指以程序 亦称为过程 的方式把知识表示出来 即把知识寓于程序之中 把知识表示和运用知识结合起来 23 知识表示方法又称为知识表示技术 其表示形式被称为知识表示模式 目前 使用较多的知识表示方法有 状态空间法问题归约法谓词逻辑法语义网络法框架表示法剧本表示法过程表示法面向对象表示法 3 知识表示方法 24 问题的状态描述二 状态图示法三 状态空间表示举例 2 状态空间法 25 对人工智能研究中运用的问题求解方法进行综合分析 可以发现许多问题求解方法是采用试探搜索方法的 是通过在某个可能的解空间内寻找一个解来求解问题的 这种基于解答空间的问题表示和求解方法就是状态空间法 状态空间法是以状态和算符为基础来表示和求解问题的 26 实例 十五数码难题 一 问题的状态描述 如何把初始棋局变换为目标棋局 27 最直接的求解方法 尝试各种不同的走步 直到偶然得到目标棋局为止 即试探搜索 28 对十五数码难题的问题描述和求解过程进行分析 初始状态 初始棋局 11 9 4 15 1 3 0 12 7 5 8 6 13 2 10 14 操作符 走步右移棋子3 下移棋子4 左移棋子12 60条 或者 移动空格 4条 目标状态 目标棋局 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 状态空间法 从某个初始状态开始 每次加一个操作符 递增地建立起操作符的试验序列 直到达到目标状态为止 状态图 初始状态可达到的各状态所对应的节点组成的图 29 问题状态的描述 状态 为描述某类不同事物间的差别而引入的一组最少变量q0 q1 qn的有序集合 其矢量形式如下 Q q0 q1 qn 状态变量 状态集合中的每个元素qi i 0 1 n 具体状态 给定每个分量的一组值 如Qk q0k q1k qnk 操作符 使问题从一种状态变换到另一种状态的手段 也叫算符 算符可以是走步 过程 规则 数学算子 运算符号或逻辑符号等 问题的状态空间 表示该问题全部可能状态及其关系的图 它包含三种说明的集合 即所有可能的问题初始状态集合S 操作符集合F以及目标状态集合G 状态空间可记为三元组 S F G 30 图论中的几个术语 图 有向图 后继节点 后裔 父辈节点 祖先 路径 长度为k的路径 节点nj是从节点ni可达到的路径 代价 两节点间路径的代价 当用一个图来表示某个状态空间时 图中各节点标上相应的状态描述 而有向弧线旁边标上算符 寻找从一种状态变换为另一种状态的某个算符序列问题等价于寻找图的某一路径问题 二 状态图示法 31 图的显式说明 图中的各节点及其具有代价的弧线由一张图或表明确给出 图的隐式说明 图中的节点集合是无限的 但起始节点是已知的 而且引入后继算符的概念是方便的 把后继节点算符作用于任一节点可以产生该节点的全部后继节点和各连接弧线的代价 搜索某个状态空间以求得算符序列的一个解答过程 就是使隐式图足够大的一部分变为显式以便包含目标的过程 这是状态空间问题求解的基础 问题的表示对求解工作量有很大的影响 32 问题的状态表示方法涉及在状态描述中如何应用变量 须用一个包含变量的表达式来描述状态的全部集合 而不仅仅描述一个状态 用常量取代表达式中的变量 就可得到一个具体的状态描述 用来描述一个状态集合的含有变量的表达式 叫做状态描述模式 33 三 状态空间表示举例 实例 猴子摘香蕉问题 acb 34 问题状态的表示 四元组 W x Y z W 猴子的水平位置 W a b c x 当猴子在箱子顶上时取x 1 否则取x 0 Y 箱子的水平位置 Y a b c z 当猴子摘到香蕉时取z 1 否则取z 0 初始状态 a 0 b 0 目标状态 c 1 c 1 35 算符集合 goto b 猴子走到水平位置b a 0 b z goto U b 0 b z pushbox c 猴子把箱子推到水平位置c b 0 b z pushbox V c 0 c z climbbox 猴子爬上箱顶 c 0 c z climbbox c 1 c z grasp 猴子摘到香蕉 c 1 c 0 grasp c 1 c 1 算符的适用性条件 强加于操作的实用性条件 如 应用算符pushbox c 时 要求猴子与箱子必须在同一位置 36 操作序列 goto b pushbox c climbbox grasp 猴子摘香蕉问题的状态空间图 37 练习题 野人和传教士渡河问题 有3个传教士和3个野人来到河边 打算乘一艘小船从右岸渡到左岸去 该船的负载能力为两人 在任何时候 如果野人人数超过传教士人数 那么野人就会把传教士吃掉 他们怎样才能用这条船安全地把所有人都渡过河去 38 3 问题归约法 问题规约的描述二 与或图表示三 问题归约机理 39 问题归约法 有许多问题可以通过一系列变换变为一个子问题集 这些子问题的解可以直接得到 通过解决这些子问题 从而就解决了初始问题 40 实例 梵塔问题 一 问题的归约描述 如何由初始配置变换为目标配置 41 求解思路 把原始问题归约为一个比较简单的问题的集合 要把所有圆盘都移至柱子3 必须先把圆盘C移至柱子3 而且在移动圆盘C至柱子3之前 柱子3必须是空的 只有在移开圆盘A和B之后 才能移动圆盘C 而且圆盘A和B不能在柱子3 因此 应该把A和B移到柱子2上 把圆盘C从柱子1移动到柱子3 并继续解决其余部分的移动问题 移动A B 2 移动C 3 移动A B 3 42 通过以上分析 把原始问题归约为3个子问题 1 移动A B 2双圆盘问题 可进一步归约 2 移动C 3单圆盘问题 可直接求解 本原问题 3 移动A B 3双圆盘问题 可进一步归约 与或图 可以有效说明问题归约法的求解过程 梵塔问题归约图 43 问题归约描述 采用问题归约法描述与求解问题 问题归约表示由三部分组成 1 一个初始问题描述如 111 333 2 一套把问题变换为子问题的操作符 问题归约算符如 移动A B 2等 3 一套本原问题描述如 122 322 本原问题 是可直接求解或具有已知解答的问题 出现本原问题即可停止搜索 问题归约法的实质 从目标 要解决的问题 出发逆向推理 建立子问题以及子问题的子问题 直至最后把初始问题归约为一个本原问题集合 问题归约的目的 最终产生具有明显解答的本原问题 44 二 与或图表示 用问题归约法描述和求解问题的过程可以用与或图来表示 例如 问题A既可由求解问题B和C 也可由求解问题D E和F 或者由单独求解问题G来解决 这一关系可由右图所示的结构图来表示 45 为了使含有一个以上后继问题的每个集合能够聚集在它们各自的父辈节点之下 在上述结构图中引入附加节点 如右图 可以认为问题A被归约为单一子问题N M和H N M和H叫或节点 问题N被归约为子问题B和C的单一集合 要求解N就必须求解所有的子问题 因此 B和C叫做与节点 各个与节点用跨接指向其后继节点的弧线的小段圆弧加以标记 这样形成的结构图就叫与或图 46 关于与或图的几点说明 在与或图中 如果一个节点有后继节点 那么这些后继节点既可全为与节点 也可全为或节点 特殊情况下 可能不出现任何与节点 如在状态空间图中就不存在与节点 即状态空间图是普通图 因此可以说问题归约法是比状态空间法更通用的问题求解方法 通过与或图 在某个问题描述中应用问题归约算符 可以依次产生出一个中间或节点和与节点后继 从而可以用与或图来表示问题归约方法的相关结构 在与或图中 起始节点对应于原始问题描述 叶子节点对应于本原问题描述 47 引入与或图后 问题求解过程就转换为与或图上的搜索过程 搜索的目的是要表明起始节点有解 在与或图中一个可解节点的一般定义可以归纳为 1 叶子节点是可解节点 本原问题 2 如果某个非叶节点含有或后继节点 那么只有当其后继节点至少有一个可解时 该非叶节点才是可解的 3 如果某个非叶节点含有与后继节点 那么只有当其后继节点全部可解时 该非叶节点才是可解的 在上述定义基础上 可以给出解图的定义 解图是那些可解节点的子图 这些节点能够证明其初始节点是可解的 48 当与或图中某些非叶节点完全没有后继节点时 我们就说它是不可解的 这些不可解节点的出现可能意味着图中另外一些节点也是不可解的 不可解节点的一般定义可以归纳为 1 没有后继的非叶节点是不可解节点 2 如果某个非叶节点含有或后继节点 那么只有当其全部后继节点不可解时 该非叶节点才是不可解的 3 如果某个非叶节点含有与后继节点 那么只有当其后继节点至少有一个不可解时 该非叶节点才是不可解的 与状态空间图求解类似 一般很少用显式图来搜索 而是用由初始问题描述和问题归约算符所定义的隐式图来搜索 从而 问题求解过程实际上就是生成与或图的足够部分 以证明初始节点可解 49 综上所述 与或图的构成规则可以概括如下 1 与或图中的每个节点代表一个要解决的单一问题或问题集合 起始节点对应于原始问题 2 对应于本原问题的节点 叫做叶子节点 它没有后继 3 对于把问题归约算符应用于问题A的每种可能情况 都把问题变换为一个子问题的集合 有向弧线由A指向后继节点 表示所求得的子问题集合 如问题A可归约为不同的子问题集合N M和H 只要N M和H有一个可解 则A可解 所以N M和H称为或节点 50 4 对于代表两个或两个以上子问题集合的每个节点 有向弧线从该节点指向该子问题集合中的各个节点 因为只有当集合中的所有项都有解时 该子问题才有解 所以这些子问题节点叫与节点 为了和或节点进行区分 把具有共同父辈的与节点后裔的所有弧线用另外一段小弧线连接起来 5 特殊情况下 当只有一个算符可应用于问题A 而且这个算符产生具有一个以上子问题的某个集合时 由 3 和 4 所产生的图可以得到简化 将代表子问题集合的中间或节点略去 利用上述规则生成的与或图中 每个节点代表一个问题或问题集合 除起始节点外 每个节点只有一个父节点 所以这样的与或图实际是与或树 51 三 问题归约机理 出发点 引入关键算符 对于状态空间的搜索问题 虽然寻求某个解答中的整个算符序列比较困难 但规定这些算符中的一个却往往比较容易 如果某个算符被认为是求解问题的决定性步骤 那么就很容易找到这样一个算符 例如 梵塔难题中 移动C 3 这个算符就是求解问题的决定性步骤 也很容易找到该算符 这种具有决定性作用的算符叫做关键算符 52 关键算符的作用 确定了某个关键算符后 就可以以该关键算符为基础进行问题归约 例如 在三元状态 S F G 表示的问题中 假设F中的某个f是关键算符 那么可以认为 S F G 的第一个后继问题是一个对应于寻找一条通向某一f适用的状态的路径问题 令Gf表示f适用的所有状态的集合 则该后继问题是由 S F Gf 描述的子问题 一旦该子问题得到解决 就可以进一步解决由 g F f g 所表示的子问题 其中g Gf f g 表示把f应用于g而得到的状态 因为该子问题是仅由应用关键算符f就可以解决 所以是本原问题 于是 剩下的就是解决由 f g F G 所描述的子问题 53 关键算符的作用 一旦确定了某个关键算符f 就可以把问题归约为如下三个子问题 1 S F Gf 2 g F f g 3 f g F G 问题 2 是本原问题问题 1 和 3 可以用直接的状态空间搜索技术或进一步的问题归约来求解 寻找子问题的关键算符 进一步归约下去 54 关键算符的作用 对于许多问题 往往无法预先知道哪个算符是关键算符 只能推测某个算符的子集 该子集中的某个算符可能是关键算符 因此 用该子集中的每个算符产生后继子问题 这样就建立起了一个与或图 可见 要应用这种方法 首先必须寻找状态空间搜索问题的候选关键算符集合 如何寻找候选关键算符呢 计算某个问题的差别 55 什么是差别 实例 猴子摘香蕉问题把4个算符的作用结果和使用条件重写如下 f1 W 0 Y z goto U U 0 Y z f2 W 0 W z pushbox V V 0 V z f3 W 0 W z climbbox W 1 W z f4 c 1 c 0 grasp c 1 c 1 初始状态 a 0 b 0 算符集合 F f1 f2 f3 f4 满足目标条件的状态集合 G 56 应用关键算符和差别的归约过程 首先计算初始问题的差别 a 0 b 0 不满足目标测试的原因在于其最后一个元素不是1 与归约这个差别相关的关键算符是f4 grasp 用f4来归约初始问题 得到如下子问题 1 a 0 b 0 F Gf4 2 S1 F f4 S1 本原问题 3 f4 S1 F G 本原问题 其中Gf4是适用于算符f4的状态描述集合 S1 Gf4 57 要求解问题 1 就要先计算其差别 由 a 0 b 0 所描述的状态不在Gf4中 差别如下 箱子不在c处猴子不在c处猴子不在箱子上 f2 pushbox c f1 goto c f3 climbbox 与差别相关的关键算符 用关键算符f2归约问题 1 得到如下子问题 1 1 a 0 b 0 F Gf2 1 2 S11 F f2 S11 本原问题 1 3 f2 S11 F Gf4 Gf2是适用于算符f2的状态描述集合 S11 Gf2 58 现在必须求解问题 1 1 所以仍需要先计算其差别 此差别为 猴子不在b处 f1 goto b 与差别相关的关键算符 用关键算符f1归约问题 1 1 得到如下子问题 1 11 a 0 b 0 F Gf1 差别为0 本原问题 可直接用f1求解 1 12 S111 F f1 S111 本原问题 1 13 f1 S111 F Gf2 Gf1是适用于算符f1的状态描述集合 S111 Gf1 59 现在需要求解问题 1 13 由于f1 S111 b 0 b 0 所以问题 1 13 变为 b 0 b 0 F Gf2 这个问题也是本原问题 可以直接用f2求解 把先前产生的问题求解过程继续下去 直到最后解答此初始问题为止 60 通过该实例分析 可以看出 问题 S F G 的差别就是用S的元对由集合G规定的目标进行测试失败原因的部分表列 如果S的某个元是在G中 那么该问题就获得解决 也就不存在差别 例如 如果目标集合G由某个状态条件集合所规定 而且某个s S满足这些条件中的某些但不是全部条件 那么差别可由不能被s满足的条件的部分表列组成 如果这些条件能够按其重要性分类 那么应该选择最重要的不满足条件作为差别 当把每个可能的差别与某些算符或算符集合结合起来时 这些算符就是候选关键算符 只有当应用某个算符是与消去某个差别相关时 该算符才与该差别结合在一起 61 4 谓词逻辑法 谓词逻辑表示法的逻辑基础1 命题与真值2 论域和谓词3 连接词和量词4 项与合式公式二 谓词逻辑表示方法三 谓词逻辑的应用四 谓词表示的特性 62 谓词逻辑表示法是一种基于数理逻辑的知识表示方式 数理逻辑是一门研究推理的科学 它作为人工智能的基础 在人工智能的发展中占有重要地位 人工智能中用到的逻辑可分为两大类 一类是一阶经典命题逻辑和谓词逻辑 另一类是除经典逻辑以外的那些逻辑 这里所说的谓词逻辑法涉及一阶经典命题逻辑和谓词逻辑 63 一阶谓词逻辑知识表示中所需要的逻辑基础包括 命题 谓词 连词 量词 谓词公式等 逻辑推理所需要的逻辑基础部分放到 逻辑推理 章讨论 一 谓词逻辑表示法的逻辑基础 64 1 命题与真值定义 一个陈述句称为一个断言 凡有真假意义的断言称为命题 命题的意义通常称为真值 它只有真假两种情况 当命题的意义为真时 则称该命题的真值为真 记为T 反之 则称该命题的真值为假 记为F 在命题逻辑中 命题通常用大写的英文字母来表示 一个命题不能同时既为真又为假 例如 天安门城楼在长安街的北边 是一个真值为T的命题 天安门广场在长安街的北边 则是一个真值为F的命题 65 关于命题 一个命题可在一定条件下为真 在另一种条件下为假 例如 命题 北京今天有雨 需要根据当天的实际情况来决定其真值 没有真假意义的感叹句 疑问句等都不是命题 例如 今天好冷啊 和 今天的温度有多少度 都不是命题 命题的优点是简单 明确 其主要缺点是无法描述客观事物的结构及其逻辑特征 也无法表示不同事物间的共性 66 2 论域和谓词论域是由所讨论对象全体构成的非空集合 论域中的元素称为个体 论域也常称为个体域 例如 整数的个体域是由所有整数构成的集合 每个整数都是该个体域中的一个个体 在谓词逻辑中 命题是用谓词来表示的 一个谓词可分为谓词名和个体两部分 其中 个体是命题中的主语 用来表示某个独立存在的事物或者某个抽象的概念 谓词名是命题的谓语 用来表示个体的性质 状态或个体之间的关系等 例如 对于命题 王宏是学生 可用谓词表示为STUDENT Wanghong 其中 Wanghong是个体 代表王宏 STUDENT是谓词名 说明王宏是学生的这一特征 通常 谓词名用大写英文字母表示 个体用小写英文字母表示 67 谓词定义 定义 设D是个体域 P Dn T F 是一个映射 其中Dn x1 x2 xn x1 x2 xn D 则称P是一个n元谓词 n 1 2 记为P x1 x2 xn 其中 x1 x2 xn为个体变元 在谓词中 个体可以是常量 变元或函数 例如 x 6 可用谓词表示为Greater x 6 其中x是变元 再如 王宏的父亲是教师 可用谓词表示为TEACHER father Wanghong 其中father Wanghong 是一个函数 68 函数定义 定义 设D是个体域 f Dn D是一个映射 则称f是D上的一个n元函数 记作 f x1 x2 xn n 1 2 其中X1 X2 Xn是个体变元 谓词和函数从形式上看很相似 容易混淆 但它们是两个完全不同的概念 谓词的真值是真和假 而函数无真值可言 其值是个体域中的某个个体 谓词实现的是从个体域中的个体到T或F的映射 而函数所实现的是同一个体域中从一个个体到另一个个体的映射 在谓词逻辑中 函数本身不能单独使用 它必须嵌入到谓词之中 69 在谓词P x1 x2 xn 中 如果xi i 1 2 n 都是个体常量 变元或函数 称它为一阶谓词 如果某个xi本身又是一个一阶谓词 则称它为二阶谓词 只讨论一阶谓词 70 3 连接词和量词在一阶谓词逻辑中共有5个连接词和2个量词 命题逻辑可看作谓词逻辑的一种特殊形式 一阶谓词逻辑中的5个连接词也都适应于命题逻辑 但2个量词仅适应于谓词逻辑 71 1 连接词连接词是用来连接简单命题 并由简单命题构成复合命题的逻辑运算符号 包括 称为 非 或者 否定 它表示对其后面的命题的否定 使该命题的真值与原来相反 例如 对命题P 若其原来的真值为T 则 P 读作非P 的真值为F 若其原来的真值为F 则 P的真值为T 称为 析取 它表示所连结的两个命题之间具有 或 的关系 称为 合取 它表示所连结的两个命题之间具有 与 的关系 称为 条件 或 蕴含 它表示 若 则 的语义 例如 对命题P和Q 蕴含式P Q表示 P蕴含Q 读作 如果P 则Q 其中P称为条件的前件 Q称为条件的后件 称为 双条件 它表示 当且仅当 的语义 例如 对命题P和Q P Q表示 P当且仅当Q 即读作 P当且仅当Q 72 对以上连接词的定义 可用下表所给出的谓词逻辑真值表来表示 73 2 量词量词是由量词符号和被其量化的变元所组成的表达式 用来对谓词中的个体作出量的规定 在一阶谓词逻辑中引入了2个量词符号 一个是全称量词符号 意思是 所有的 任一个 另一个是存在量词符号 彐 意思是 至少有一个 存在有 例如X是一个全称量词 表示 对论域中的所有个体 读作 对于所有x 彐x是一个存在量词 表示 在论域中存在个体X 读作 存在x 全称量词的定义 命题 x P x 为真 当且仅当对论域中的所有x 都有P x 为真 命题 x P x 为假 当且仅当至少存在一个x0 D 使得P x0 为假 存在量词的定义 命题 彐x P x 为真 当且仅当至少存在一个x0 D 使得P x0 为真 命题 彐x P x 为假 当且仅当对论域中的所有x 都有P x 为假 74 在一阶谓词演算中 合法的表达式称为合式公式 即谓词公式 对合式公式的定义将涉及到 项 的概念 下面分别给出它们的定义 定义 项满足如下规则 1 单独一个个体词是项 2 若t1 t2 tn是项 f是n元函数 则f t1 t2 tn 是项 3 由 1 2 生成的表达式是项 可见 项是把个体常量 个体变量和函数统一起来的概念 定义 原子谓词公式的含义为 若t1 t2 tn是项 P是谓词符号 则称P t1 t2 tn 为原子谓词公式 4 项与合式公式 75 定义 满足如下规则的谓词演算可得到合式公式 1 单个原子谓词公式是合式公式 2 若A是合式公式 则 A也是合式公式 3 若A B都是合式公式 则A B A B A B A B也都是合式公式 4 若A是合式公式 x是项 则 x A和 彐x A也都是合式公式 这个定义是合式公式的形成规则 按照这些规则可以形成任意复杂的合式公式 例如 P x y Q y x A x B x 彐x A x y R x y B y 都是合式公式 在合式公式中 连接词之间的优先级别是 76 当一个谓词公式含有量词时 区分个体变元是否受量词的约束是很重要的 位于量词后面的单个谓词或者用括号括起来的合式公式称为该量词的辖域 辖域内与量词中同名的变元称为约束变元 不受约束的变元称为自由变元 例如 x P x y Q x y R x y 5 自由变元和约束变元 77 谓词逻辑不仅可以用来表示事物的状态 属性 概念等事实性知识 也可以用来表示事物的因果关系 即规则 对事实性知识 通常是用否定 析取或合取符号连接起来的谓词公式表示 对事物间的因果关系 通常用蕴含式表示 例如 对 如果x 则y 可表示为 x y 当用谓词逻辑表示知识时 首先需要根据所表示的知识定义谓词 然后再用连接词或量词把这些谓词连结起来 形成一个谓词公式 二 谓词逻辑表示方法 78 此时 该知识可用谓词表示为 x 彐y PERSON x HASFATHER x y 例1 用谓词逻辑表示知识 每个人都有一个父亲 首先定义谓词 PERSON x 表示x是人 HASFATHER x y 表示x有父亲y 79 首先定义谓词 TEACHER x 表示x是教师 STUDENT y 表示y是学生 TEACHES x y 表示x是y的老师 例2 用谓词逻辑表示知识 所有教师都有自己的学生 此时 该知识可用谓词表示为 x 彐y TEACHER x TEACHES x y STUDENT y 该谓词公式可读作 对所有x 如果x是一个教师 那么一定存在一个个体y x是y的老师 且y是一个学生 80 首先定义谓词 I x x是整数 E x x是偶数 O x x是奇数 此时 该知识可用谓词表示为 x I x E x O x 例3 用谓词逻辑表示知识 所有的整数不是偶数就是奇数 81 首先定义谓词 COMPUTER x 表示x是计算机系的学生 CLASSMATE x y 表示x是y的同班同学 LIKE x y 表示x喜欢y 例4 用谓词逻辑表示如下知识 王宏是计算机系的一名学生 李明是王宏的同班同学 凡是计算机系的学生都喜欢编程序 此时 可用谓词公式把上述知识表示为 COMPUTER Wanghong CLASSMATE Liming Wanghong x COMPUTER x LIKE x programing 82 例 机器人移盒子问题设在一房间里 c处有一个机器人 a和b处各有一张桌子 分别称为a桌和b桌 a桌子上有一盒子 要求机器人从c处出发把盒子从a桌上拿到b桌上 然后再回到c处 请用谓词逻辑来描述机器人的行动过程 前面讨论了一阶谓词逻辑的基础和逻辑知识表示方法 为加深对这些内容的理解 下面举个逻辑表示法的应用例子 A B C 三 谓词逻辑表示的应用 83 在这个例子中 不仅要用谓词公式来描述事物的状态 位置 而且还要用谓词公式表示动作 为此 需要定义如下谓词公式 TABLE x x是桌子EMPTY y y手中是空的AT y z y在z的附近HOLDS y w y拿着wON w x w在x桌面上 其中 x的个体域是 y的个体域是 z的个体域是 w的个体域是 a b robot a b c box 84 问题的初始状态 AT robot c EMPTY robot ON box a TABLE a TABLE b 问题的目标状态 AT robot c EMPTY robot ON box b TABLE a TABLE b 使用规则 85 机器人行动的目标是把问题的初始状态转换为目标状态 而要实现问题状态的转换需要完成一系列的操作 对于每个操作 一般都可分为条件和动作两个部分 条件部分用来说明执行该操作必须具备的先决条件 动作部分给出了该操作对问题状态的改变情况 条件部分可用谓词公式来表示 动作部分则是通过在执行该操作前的问题状态中删去和增加相应的谓词来实现的在本问题中 机器人需要执行以下三个操作 Goto x y 从x处走到y处 Pickup x 在x处拿起盒子 Setdown x 在x处放下盒子 86 这三个操作对应的条件与动作如下 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 87 机器人在执行每一操作之前 都需要检查当前状态是否可以满足该操作的先决条件 如果满足 就执行相应的操作 否则就检查下一个操作所要求的先决条件 作为谓词逻辑知识表示方法的应用 下面给出这个机器人行动规划问题的求解过程 其中 在检查先决条件是否满足时还需要进行变量的置换 88 状态l 初始状态 AT robot c 开始EMPTY robot ON box a TABLE a TABLE b Goto x y 用c代换x a代换y 状态2AT robot a EMPTY robot ON box a TABLE a TABLE b Pickup x 用a代换x 状态3AT robot a HOLDS robot box TABLE a TABLE b Goto x y 用a代换x b代换y 状态4AT robot b HOLDS robot box TABLE a TABLE b Setdown x 用b代换x 状态5AT robot b EMPTY robot ON box b TABLE a TABLE b Goto x y 用b代换x c代换y 状态6 目标状态 AT robot c EMPTY robot ON box b TABLE a TABLE b 89 逻辑知识表示的主要特点是建立在某种形式逻辑的基础上 并利用了逻辑方法研究推理的规律 即条件与结论之间的蕴含关系 逻辑表示法的主要优点包括 1 自然一阶谓词逻辑是一种接近于自然语言的形式语言系统 谓词逻辑表示法接近于人们对问题的直观理解 易于被人们接受 2 明确逻辑表示法对如何由简单陈述句构造复杂陈述句的方法有明确规定 如连接词 量词的用法与含义等 对于用逻辑表示法表示的知识 人们都可以按照一种标准的方法去解释它 因此用这种方法表示的知识明确 易于理解 四 谓词逻辑表示的特性 90 3 精确谓词逻辑是一种二值逻辑 其谓词公式的真值只有 真 与 假 因此可用来表示精确知识 并可保证经演演绎推理所得结论的精确性 4 灵活逻辑表示法把知识和处理知识的程序有效地分开 在使用这种方法表示知识时 无须考虑程序中处理知识的细节 5 模块化在逻辑表示法中 各条知识都是相对独立的 它们之间不直接发生联系 因此添加 删除 修改知识的工作比较容易进行 91 逻辑表示法也存在一些不足 其主要缺点如下 1 知识表示能力差逻辑表示法只能表示确定性知识 而不能表示非确定性知识 如不精确 模糊性知识 实际上 人类的大部分知识都不同程度地具有不确定性 使得它表示知识的范围和能力受到了一定的限制 另外 逻辑表示法还难以表示过程性知识和启发性知识 2 知识库管理困难逻辑表示法缺乏知识的组织原则 利用这种表示法所形成的知识库管理比较困难 3 存在组合爆炸由于逻辑表示法难以表示启发性知识 因此在推理过程中只能盲目地使用推理规则 当系统知识量较大时 容易发生组合爆炸 4 系统效率低逻辑表示法的推理过程是根据形式逻辑进行的 它把推理演算与知识含义截然分开 抛弃了表达内容中所含有的语义信息 往往使推理过程冗长 降低了系统效率 92 设机器人有一只机械手 要处理的世界有一张桌子 桌上可堆放若干相同的方积木块 积木世界的布局如下图所示 练习题 机器人摞积木问题 提示 机械手有4个操作积木的典型动作 从桌面上拣起一块积木 将手中的积木放到桌面上 在积木上再摞上一块积木 从积木上面拣起一块积木 93 5 语义网络法 语义网络的基本概念1 什么是语义网络2 语义的基本关系二 事物和概念的表示三 情景和动作的表示四 逻辑关系的表示五 语义网络的推理过程 94 语义网络是奎廉 J R Qullian 1968年在研究人类联想记忆时提出的一种心理学模型 他认为记忆是由概念间的联系实现的 随后 奎廉又把它用作知识表示 1972年 西蒙在自然语言理解系统中也采用了语义网络表示法 1975年 亨德里克 G G Hendrix 对全称量词的表示提出了语义网络分区技术 目前 语义网络已成为人工智能中应用较多的一种知识表示方法 95 语义网络是一种用实体及其语义关系来表达知识的有向图 其中 结点代表实体 表示各种事物 概念 情况 属性 状态 事件 动作等 弧线代表语义关系 表示它所连结的两个实体之间的语义联系 在语义网络中 每一个结点和弧都必须带有标识 这些标识用来说明它所代表的实体或语义 一 语义网络的基本概念 1 什么是语义网络 96 从结构上看 语义网络一般是由一些最基本的语义单元构成的 这种最基本的语义单元被称为语义基元 一个语义基元可用如下三元组 结点1 弧 结点2 来表示 对该三元组 如果用A B分别表示其中的两个结点 用R表示A与B之间的某种语义联系 则它所对应的基本网元表示为 97 当把多个语义基元用相应的语义联系关联在一起时 就形成了一个语义网络 在语义网络中 弧的方向是有意义的 不能随意调换 例 用语义基元描述 鸵鸟是一种鸟 这一事实 由于 鸵鸟 与 鸟 之间的语义联系为 是一种 因此在此语义网络中 弧被标识为 是一种 如下图 98 语义网络表示和谓词逻辑表示之间有一定的对应表示能力 从逻辑表示来看 一个语义网络相当于一组二元谓词 因为三元组 结点1 弧 结点2 可写成P 个体1 个体2 其中结点1 结点2分别对应个体1 个体2 而孤及其上的标识是由谓词P来体现的 99 从功能上讲 语义网络可以描述任何事物间的任意复杂关系 但是 这种描述是通过把许多基本的语义关系关联到一起来实现的 基本语义关系是构成复杂语义关系的基石 也是语义网络知识表示的基础 但由于基本语义关系的多样性和灵活性 因此又不可能对其进行全面讨论 作为参考 下面给出的仅是一些最常用的基本语义关系 2 基本的语义关系 100 1 类属关系类属关系是指具有共同属性的不同事物间的分类关系 成员关系或实例关系 它体现的是 具体与抽象 个体与集体 的概念 类属关系的一个最主要特征是属性的继承性 处在具体层的结点可以继承抽象层结点的所有属性 常用的类属关系有 A Kind of 含义为 是一种 表示一个事物是另一个事物的一种类型 A Member of 含义为 是一员 表示一个事物是另一个事物的一个成员 is a 含义为 是一个 表示一个事物是另一个事物的一个实例 101 例如 分类关系 鸟是一种动物 可用下图所示的语义网络来表示 它说明鸟是动物的一种类型 并可继承动物的所有属性 实例关系 李刚是人 可用下图所示的语义网络来表示 成员关系 张强是共青团员 可用下图所示的语义网络来表示 在类属关系中 具体层结点除具有抽象层结点的所有属性外 还可以增加一些自己的个性 甚至还能够对抽象层结点的某些属性加以更改 例如 所有的动物都具有能运动 会吃等属性 而鸟类作为动物的一种 除具有动物的这些属性外 还具有会飞 有翅膀等个性 102 2 包含关系包含关系也称为聚类关系 是指具有组织或结构特征的 部分与整体 之间的关系 它和类属关系的最主要区别是包含关系一般不具备属性的继承性 常用的包含关系是 Part of 含义为 是一部分 表示一个事物是另一个事物的一部分 103 例如 大脑是人的一部分 可用下图所示的语义网络来表示 再如 黑板是墙的一部分 可用下图来表示 对于这两个例子 从继承性的角度看 大脑不一定具有人的各种属性 黑板也不具有墙的各种属性 104 3 属性关系属性关系是指事物和其属性之间的关系 常用的属性关系有 Have 含义为 有 表示一个结点具有另一个结点所描述的属性 Can 含义是 能 会 表示一个结点能做另一个结点的事情 例如 鸟有翅膀 可用下图所示的语义网络来表示 鸟 翅膀 Have 属性关系 105 4 时间关系时间关系是指不同事件在其发生时间方面的先后次序关系 常用的时间关系有 before 含义为 在前 表示一个事件在另一个事件之前发生 after 含义为 在后 表示一个事件在另一个事件之后发生 例如 澳门回归在香港回归之后 可用下图所示的语义网络来表示 106 5 位置关系位置关系是指不同事物在位置方面的关系 常用的位置关系有 Located at 含义为 在 表示某一物体所在的位置Located on 含义为 在上 表示某一物体在另一物体之上Located under 含义为 在下 表示某一物体在另一物体之下Located inside 含义为 在内 表示某一物体在另一物体之内Located outside 含义为 在外 表示某一物体在另一物体之外 例如 书在桌子上 可用下图所示的语义网络来表示 107 6 相近关系相近关系是指不同事物在形状 内容等方面相似或接近 常用的相近关系有 Similar to 含义为 相似 表示某一事物与另一事物相似 Near to 含义为 接近 表示某一事物与另一事物接近 例如 猫似虎 可用下图所示的语义网络来表示 猫 虎 Similar to 相似关系 108 7 推论关系推论关系是指从一个概念推出另一个概念的语义关系 例如 由成绩好推出学习努力 可用下图所示的语义网络来表示 109 所谓一元关系是指可以用一元谓词P x 表示的关系 其中 个体X为实体 谓词P说明实体的性质 属性等 一元关系描述的是一些最简单 最直观的事物或概念 常用 是 有 会 能 等语义关系来说明 例如 雪是白的 就是一个一元关系 按道理讲 语义网络描述的是两个结点之间的二元关系 那么如何用它来描述一元关系呢 通常的做法是用结点1表示实体 用结点2表示实体的性质或属性等 用弧表示结点1和结点2之间的语义关系 例如 李刚是人 是一个一元关系 其语义网络如下图所示 李刚 人 is a 实例关系 二 事物和概念的表示 1 用语义网络表示一元关系 110 为了进一步说明一元关系的语义网络表示 下面再给出一个例子 例 用语义网络表示 动物能运动 会吃 在这个例子中 能运动和会吃是动物的两个属性 其表示方法是在 动物 结点上增加它具有的属性 能运动 会吃 如下图 从这些例子可以看出 尽管语义网络描述的是两个结点之间的二元关系 但它同样可以很方便地表示一元关系 111 所谓二元关系是指可用二元谓词P x y 表示的关系 其中 个体x y为实体 谓词P说明两个实体之间的关系 二元关系可以很方便地用语义网络来表示 前面介绍了一些常用二元关系的表示方法 下面主要讨论较复杂关系的表示方法 有些关系看起来比较复杂 但可以较容易地分解成一些相对独立的二元关系或一元关系 对于这类问题 可先给出每个二元关系或一元关系的语义网络表示 然后再把它们关联到一起 得到问题的完整表示 2 用语义网络表示二元关系 112 例 用语义网络表示 动物能运动 会吃 鸟是一种动物 鸟有翅膀 会飞 鱼是一种动物 鱼生活在水中 会游泳 对于这个问题 各种动物的属性按属性关系描述 动物之间的分类关系用类属关系描述 其语义网络如下图所示 113 例 用语义网络表示 王强是理想公司的经理 理想公司在街道口 王强28岁 对于这个问题 其语义网络如下图所示 如果在上图所示的语义网中再增加如下事实 另有一个王强是理想公司经理聘用的职员 职员王强22岁 对于这个问题 为了在同一个语义网络中把两个同名的人都表示出来 需要分别为他们各增设一个结点 王一1 代表经理王强 王一2 代表职员王强 其语义网络为 114 115 例 用语义网络表示以下两个简单事实 李新的自行车是永久牌 蓝色 26型 王红的自行车是金狮牌 红色 24型 这两个事实相互独立 但又有一定联系 不管是李新的自行车 还是王红的自行车 都是一辆特定的自行车 属于具体概念 为使该问题的表示更加一般化和便于扩充 可在语义网络中增加 自行车 这个抽象概念 并用自行车1 自行车2分别代表李新和王红的自行车 其语义网络如下图所示 116 117 所谓多元关系是指可用多元谓词P x1 x2 xn 表示的关系 其中 个体x1 x2 xn为实体 谓词P说明这些实体之间的关系 在现实世界中 往往需要通过某种关系把多种事物联系起来 这就构成了一种多元关系 当用语义网络表示多元关系时 一般采用增加关系结点的办法 3 用语义网络表示多元关系 118 例 用语义网络表示以下事实 北京位于沈阳和武汉之间 这是一种 在