人工智能-chapter2.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,人们所涉及到的知识是十分广泛的。有的属多数人所熟悉的，有的只是有关专家才掌握的专门领域知识。对于“知识”难以给出明确的定义，只能从不同侧面加以理解。,Feigenbaum认为知识是经过削减、塑造、解释和转换的信息。简单地说，知识是经过加工的信息。Bernstein说知识是由特定领域的描述、关系和过程组成的。Hayes-Roth认为知识是事实、信念和启发式规则。知识表示是研究用机器表示知识的可行性、有效性的一般方法，是一种数据结构与控制结构的统一体，既考虑知识的存储又考虑知识的使用。知识表示可看成是一组描述事物的约定，以把人类知识表示成机器能处理的数据结构。,1,人工智能系统所关心的知识,一个智能程序高水平的运行需要有关的事实知识、规则知识、控制知识和元知识。事实 是有关问题环境的一些事物的知识。如事物的分类、属性、事物间关系、科学事实、客观事实等，事实是静态的为人们共享的可公开获得的公认的知识，在知识库中属低层的知识。如雪是白色的。规则 是有关问题中与事物的行动、动作相联系的因果关系知识，是动态的，常以“如果那么”形式出现。控制 是有关问题的求解步骤、技巧性知识，告诉怎么做一件事。,元知识 是有关知识的知识，是知识库中的高层知识。包括怎样使用规则、解释规则、校验规则、解释程序结构等知识。,2,陈述式知识表示与过程式知识表示,语义网络、框架和剧本等知识表示方法，均是对知识和事实的一种静止的表达方法，我们称这类知识表达方式为陈述式知识表达，它所强调的是事物所涉及的对象是什么，是对事物有关知识的静态描述，是知识的一种显式表达形式。而对于如何使用这些知识，则通过控制策略来决定。和知识的陈述式表示相对应的是知识的过程式表示。所谓过程式知识表示就是将有关某一问题领域的知识，连同如何使用这些知识的方法，均隐式地表达为一个求解问题的过程。它所给出的是事物的一些客观规律，表达的是如何求解问题。知识的描述形式就是程序，所有信息均隐含在程序中，因而难于添加新知识和扩充功能，适用范围较窄。,3,问题求解(problem solving)是个大课题，它涉及归约、推断、决策、规划、常识推理、定理证明和相关过程的核心概念。在分析了人工智能研究中运用的问题求解方法之后，就会发现许多问题求解方法是采用试探搜索方法的。也就是说，这些方法是通过在某个可能的解空间内寻找一个解来求解问题的。这种基于解答空间的问题表示和求解方法就是状态空间法，它是以状态和算符(operator)为基础来表示和求解问题的。,问题求解技术两个主要的方面,(1)问题的表示：如果描述方法不对，对问题求解会带来很大的困难；(2)求解的方法：采用试探搜索方法。,状态空间法概述,2.2 状态空间法,4,问题状态描述,定义,(1)状态(state)：为描述某类不同事物间的差别而引入的一组最少变量q,0,，q,1,，q,n,的有序集合，其矢量形式如下：,式中每一个元素为集合的分量，称作状态变量。,(2)算符（operator）：使问题从一种状态变化为另一种状态的手段称为操作符或算符。操作符可为走步、过程、规则、数学算子、运算符号或逻辑符号等。,(3)问题的状态空间（state space）：是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合，即所有可能的问题初始状态集合S、操作符集合F以及目标状态集合G。可把状态空间记为三元状态(S，F，G)。,5,状态空间法三要点,(1)状态（state）：表示问题解法中每一步问题状况的数据结构；,(2)算符（operator）：把问题从一种状态变换为另一种状态的手段；,(3)状态空间方法：基于解答空间的问题表示和求解方法，它是以状态和算符为基础来表示和求解问题的。,6,状态空间表示详释,我们先用数码难题(puzzle problem)来说明状态空间表示的概念。由15个编有1至15并放在44方格棋盘上的可走动的棋子组成。棋盘上总有一格是空的，以便可能让空格周围的棋子走进空格，这也可以理解为移动空格。图中绘出了两种棋局，即初始棋局和目标棋局，它们对应于该下棋问题的初始状态和目标状态。十五数码难题最直接的求解方法是尝试各种不同的走步，直到偶然得到该目标棋局为止。把初始状态可达到的各状态所组成的空间设想为一幅由各种状态对应的节点组成的图。这种图称为状态图。图中每个节点标有它所代表的棋局。首先把适用的算符用于初始状态，以产生新的状态；然后，再把另一些适用算符用于这些新的状态；这样继续下去，直至产生目标状态为止。,8,11 9 4 15,1 3 12,7 5 8 6,13 2 10 14,11 9 4 15,1 3 12,7 5 8 6,13 2 10 14,11 9 15,1 3 4 12,7 5 8 6,13 2 10 14,11 9 4 15,1 3 12,7 5 8 6,13 2 10 14,11 9 4 15,1 3 8 12,7 5 6,13 2 10 14,算符：右移棋子3,初始状态,目标状态,9,10,11,12,用状态空间法表示为：从某个初始状态开始，每次加一个操作符（或算符），递增地建立起操作符的实验序列，直至达到目标状态为止。,完成某个问题的状态描述的3个基本步骤：,(1)首先，确定该状态的描述方式，特别是初始状态的描述；,(2)然后，确定操作符集合及其对状态描述的作用；,(3)最后，确定目标状态描述的特性。,13,状态图示法,7,5,6,10,有向图,14,路径,：某个节点序列(n,i1,n,i2,n,ik,)当j=2，3，k时，如果对于每一个n,i，j-1,都有一个后继节点n,ij,存在，那么就把这个节点序列叫做从节点n,i1,至节点n,ik,的长度为k的路径。,代价,：用c(n,i,n,j,)来表示从节点n,i,指向节点n,j,的那段弧线的代价。两节点间路径的代价等于连接该路径上各节点的所有弧线代价之和。,显式表示,：各节点及其具有代价的弧线由一张表明确给出。此表可能列出该图中的每一节点、它的后继节点以及连接弧线的代价。,隐式表示,：节点的无限集合s,i,作为起始节点是已知的。后继节点算符也是已知的，它能作用于任一节点以产生该节点的全部后继节点和各连接弧线的代价。,15,图论中的几个术语,节点(node),：图形上的汇合点，用来表示状态、事件和时间关系的汇合，也可用来指示通路的汇合；,弧线(arc),：节点间的连接线；,有向图(directed graph),：图由节点（不一定是有限的节点）的集合构成。象这样一对节点用弧线连接起来，从一个节点指向另一个节点构成的图称为,有向图,。,后继节点(descendant node)与父辈节点(parent node),：如果某条弧线从节点n,i,指向节点n,j,，那么节点n,j,就叫做节点n,i,的后继节点或后裔，而节点n,i,叫做节点n,j,的父辈节点或祖先。一对节点可以互为后裔，此时，这对有向弧线就用一条棱线代替。,当用一个图来表示某个状态空间时，图中各节点标上相应的状态描述，而有向弧线旁边标有操作符（或算符）。,16,对于一类最简单的问题，需要求得某指定节点s（表示初始状态）与另一个节点t（表示目标状态）之间的一条路径（可能具有最小代价）。对于此类问题有两个典型代表,（1）求得节点s与节点集合,t,i,中任意一节点之间的距离；（2）,求得节点集合,s,i,与节点集合,t,i,中任意一节点之间的距离。,s,t1,t2,7,5,6,10,17,图的显式和隐式表示,一个图可由显式说明也可由隐式说明。显然，显式说明对于大型的图是不切实际的，而对于具有无限节点集合的图则是不可能的。此外，引入后继节点算符的概念是方便的。后继节点算符也是已知的，它能作用于任一节点以产生该节点的全部后继节点和各连接弧线的代价(用我们的状态空间术语来说，后继算符是由适用于已知状态描述的算符集合所确定的)。把后继算符应用于s,i,的成员和它们的后继节点以及这些后继节点的后继节点，如此无限制地进行下去，最后使得由和s,i,所规定的隐式图变为显示图。把后继算符应用于节点的过程，就是扩展一个节点的过程。因此，搜索某个状态空间以求得算符序列的一个解答的过程，就对应于使隐式图足够大一部分变为显式以便包含目标的过程。这样的搜索图是状态空间问题求解的主要基础。问题的表示对求解工作量有很大的影响。人们显然希望有较小的状态空间表示。许多似乎很难的问题，当表示适当时就可能具有小而简单的状态空间。,18,状态空间表示举例,根据问题状态，操作（算）符和目标条件选择各种表示，是高效率问题求解所需要的。,首先需要表示问题，然后改进提出的表示。在问题求解过程中，我们能不断取得经验，获得一些简化的表示。如十五数码难题：,（1）60条规则，即左移棋子1，右移棋子1，上移棋子1，下移棋子1.,（2）4条规则，即左移空格，右移空格，上移空格，下移空格。,各种问题都可以用状态空间加以表示，并用状态空间搜索法来求解。,19,产生式系统（Production System）,一个总数据库(global database)：它含有与具体任务有关的信息；随着应用情况的不同，这些数据库可能小得像数字矩阵那样简单，或许大得如检索文件结构那么复杂。,一套规则(set of rules)：它对数据库进行操作运算。每条规则由左右两部分组成，左部鉴别规则的适用性或先决条件，右部描述规则应用时所完成的动作。应用规则来改变数据库，就象应用算符来改变状态一样。,一个控制策略(control system)：它确定应该采用哪一条适用规则，而且当数据库的终止条件满足时，就停止计算。控制策略由控制系统选择和确定。,20,21,产生式系统的例子,22,23,猴子和香蕉问题(monkey and banana problem),用一个四元表列(W,x,Y,z)来表示这个问题的状态，其中W猴子的水平位置x当猴子在箱子顶上时取x=1；否则取x=0Y箱子的水平位置z当猴子摘到香蕉时取z=1；否则取z=0,状态空间方法的例子,24,这个问题中的操作(算符)如下：,(1)goto(U)猴子走到水平位置U，或者用产生式规则表示为,即应用操作goto(U)，能把状态(W，0，Y，z)变换为状态(U，0，Y，z)。,(2)pushbox(V)猴子把箱子推到水平位置V，即有,应当注意的是，要应用算符pushbox(V)，就要求产生式规则的左边，猴子与箱子必须在同一位置上，并且猴子不是在箱子顶上。这种强加于操作的适用性条件，叫做产生式规则的先决条件。,(3)climbbox猴子爬上箱顶，即有,在应用算符climbbox时也必须注意到，猴子和箱子应当在同一位置上，而且猴子不在箱顶上。,4)grasp猴子摘到香蕉，即有,25,把所有适用的操作继续应用于每个状态，我们就能够得到状态空间图,。,26,2.3,问题归约法,先把问题分解为子问题和子-子问题，然后解决较小的问题。对该问题的某个具体子集的解答就意味着对原始问题的一个解答。问题归约表示的组成部分：一个初始问题描述；一套把问题变换为子问题的操作符；一套本原问题描述。问题归约的实质：从目标(要解决的问题)出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个平凡的本原问题集合。,梵塔难题,：,有3个柱子(1，2和3)和3个不同尺寸的圆盘（A，B和C）。在每个圆盘的中心有一个孔，所以圆盘可以堆叠在柱子上。最初，3个圆盘都堆在柱子1上：最大的圆盘C在底部，最小的圆盘A在顶部。要求把所有圆盘都移到柱子3上，每次只许移动一个，而且只能先搬动柱子顶部的圆盘，还不许把尺寸较大的圆盘堆放在尺寸较小的圆盘上。,问题归约描述,27,据说在东方的古国印度土地上，有一座,印度教,的神庙，这庙有一块黄铜板，板上插著三根细细的、镶上宝石的细针，细针像菜叶般粗，而高就像成人由手腕到肘关节的长。当印度教的主神梵天在创造地球这个世界时，就在其中的一根针上从下到上放了半径由大到小的六十四片圆金片环，这就是有名的,梵塔,或称,汉内塔,（Towers of Hanoi）。天神,梵天,要这庙的僧侣，把这些金片全部由一根针移到另外一根指定的针上，一次只能移一片，不管在什么情况下，金片环的大小次序不能变更，小金片环永远只能放在大金片环上面。只要有一天这六十四片的金环能从指定的针上完全转移到另外指定的针上，世界末日就来到，芸芸众生、神庙一切都将消灭，万物尽入,极乐世界,去。,梵,塔难题的起源,28,解题过程：,将原始问题归约为一个较简单问题集合，要把所有圆盘都移至柱子3，我们必须首先把圆盘C移至柱子3；而且在移动圆盘C至柱子3之前，要求柱子3必须是空的。只有在移开圆盘A和B之后，才能移动圆盘C；而且圆盘A和B最好不要移至柱子3。因此，首先应该把圆盘A和B移到柱子2上。然后才能够进行关键的一步，把圆盘C从柱子1移至柱子3，并继续解决难题的其余部分。,29,归约过程,（1）移动圆盘A和B至柱子2的双圆盘难题；,（2）移动圆盘C至柱子3的单圆盘难题；,（3）移动圆盘A和B至柱子3的双圆盘难题。,由上可以看出简化了难题每一个都比原始难题容易，所以问题都会变成易解的本原问题。,30,问题：一圆盘问题要走几步？两圆盘问题要走几步？三个、四个等？,31,问题归约方法是应用算符来把问题描述变换为子问题描述。,可以用状态空间表示的三元组合(S、F、G)来规定与描述问题；对于梵塔问题，子问题（111）(122)，(122)(322)以及(322)(333)规定了最后解答路径将要通过的脚踏石状态（或称作中间状态）(122)和(322)。,问题归约方法可以应用状态、算符和目标这些表示法来描述问题，这并不意味着问题归约法和状态空间法是一样的。,32,与图、或图、与或图,一般地，我们用一个类似图的结构来表示把问题归约为后继问题的替换集合，这种结构图叫做问题归约图，或叫与或图。,与或图表示,例如，设想问题A既可由求解问题B和C，也可由求解问题D、E和F，或者单独求解H来解决。这一关系可由下图的结构表示：,33,关于与或图的术语,终叶节点：对应于原问题的本原节点。,或节点：只要解决某个问题就可解决其父辈问题的节点集合，如（M，N，H）。,与节点：只有解决所有子问题，才能解决其父辈问题的节点集合，如（B,C)和（D,E,F）各个结点之间用一端小圆弧连接标记。,与或图：由与节点及或节点组成的结构图。,可,解节点的一般定义,(1)终叶节点是可解节点(因为它们与本原问题相关连)。,(2)如果某个非终叶节点含有或后继节点，那么只要当其后继节点至少有一个是可解的时，此非终叶节点才是可解的。,(3)如果某个非终叶节点含有与后继节点，那么只有当其后继节点全部为可解时，此非终叶节点才是可解的。,34,不可解节点的一般定义,(1)没有后裔的非终叶节点为不可解节点。,(2)如果某个非终叶节点含有或后继节点，那么只有当其全部后裔为不可解时，此非终叶节点才是不可解的。,(3)如果某个非终叶节点含有与后继节点，那么只要当其后裔至少有一个为不可解时，此非终叶节点才是不可解的。,35,与或图构成规则,(1)与或图中的每个节点代表一个要解决的单一问题或问题集合。图中所含起始节点对应于原始问题。,(2)对应于本原问题的节点，叫做终叶节点，它没有后裔。,(3)对于把算符应用于问题A的每种可能情况，都把问题变换为一个子问题集合；有向弧线自A 指向后继节点表示所求得的子问题集合。,(4)一般对于代表两个或两个以上子问题集合的每个节点，有向弧线从此节点指向此子问题集合中的各个节点。由于只有当集合中所有的项都有解时，这个子问题的集合才能获得解答，所以这些子问题节点叫做与节点。,(5)在特殊情况下，当只有一个算符可应用于问题A，而且这个算符产生具有一个以上子问题的某个集合时，由上述规则3和规则4所产生的图可以得到简化。因此，代表子问题集合的中间或节点可以被略去。,36,设想把三元状态组(S,F,G)规定的状态空间搜索问题归结为比较简单的一些状态空间搜索问题。如果能够识别某个适当的路标状态序列g,1,g,2,.,g,n,那么就能够把初始问题归约为由三元状态(S,F,g,1,),(S,F,g,2,),.,(g,n,F,G)规定的问题集合。解答所有这些问题就等价于解答该初始问题。,问题归约机理,这里将叙述一种问题归约技术，它能够成功地把状态空间搜索问题归约为越来越简单的搜索问题，直至所有问题能够被归约为平凡解为止。,37,关键算符,对于许多状态空间的搜索问题，要推测一个状态空间算符的特性并不是太困难的。也就是说，尽管寻求某个解答中整个算符序列的问题是困难的，但是规定这些算符中的一个却往往是容易的。当应用该算符中的一个被认为是问题求解的决定性步骤时，寻找这样一个算符的可能性就增加了。例如，对我们前面讨论过的梵塔问题，移动圆盘C至柱子3这个算符可被选为问题求解的决定性步骤，我们把这种具有决定性作用的算符叫做关键算符。,38,当某个关键算符被决定时，它可被用来辨别问题归约过程中的路标。假设F中的某个f是由三元状态(S，F，G)表示的问题的关键算符。既然我们认为f必定要应用，所以(S，F，G)表示第一个后裔问题是一个对应于寻找一条通向某一f适用的状态的路径问题。令G,f,表示f适用的所有状态的集合。由此，我们设立了一个由(S，F，G,f,)描述的子问题。一旦这个子问题获得解决，规定一个状态gG,f,我们就能够设立由(g,F,f(g)表示的本原问题，其中，f(g)表示把f应用于g而得到的状态。因为这个问题仅仅由应用关键算符f来解决，所以它是本原的。于是，剩下的(未解决的)是由三元状态(f(g),F,G)描述的问题。当某个状态空间的关键算符能够被规定时，我们就能应用下列问题归约。,39,寻找候选关键算符的一种方法涉及计算某个问题(S，F，G)的差别。粗略地说，问题(S，F，G)的差别就是用S的元对由集合G规定的目标进行测试失败原因的部分表列(如果S的某个元是在G中，那么此问题就获得解决，也就不存在差别)。举例来说，如果目标集合G由某个状态条件集合所规定，而且某个sS满足这些条件中的某些但不是全部条件，那么，差别可由不能被s满足的条件的部分表列组成。如果这些条件能够按其重要性分类，那么我们宁愿选用最重要的不满足条件作为差别。其次，我们把某些状态空间算符或算符集合与每个可能的差别结合起来。这些算符是候选关键算符。只有当应用某个算符是与消去某个差别相关时，此算符才与那个差别结合在一起。,差别,如何计算差别？,40,猴子和香蕉问题,如果F=f,1,f,2,f,3,f,4,是4个算符的集合，G是满足目标条件的状态集合。那么我们的初始问题变为,由于算符集合F在本问题中不发生变化，因此我们可把符号F从表示式中删去，而简单地用(a,0,b,0),G)来表示这个问题。,41,首先，我们计算初始问题的差别。表列(a,0,b,0)不满足目标测试的原因在于其最后一个元素不是1。与归约这个差别相关的关键算符是f,4,=grasp。用f,4,来归约初始问题，得到下列一对子问题,其中，是适用于算符f,4,的状态描述集合(此状态描述在域f,4,内)，而S,1,是 中由求解(a,0,b,0),)而得到的状态。,要求解问题(a,0,b,0),)，我们需要先计算它的差别。由(a,0,b,0)所描述 的状态不在 中，因为：(1)箱子不在c处；(2)猴子不在c处；(3)猴子不在箱子上。,42,把这些说明列出作为这种情况下的差别，我们辨别出下列关键算符：f,2,pushbox(c)f,1,goto(c)f,3,climbbox然后，我们依次应用这些关键算符，以产生各归约问题的替换对。这些关键算符的第一个，用来把问题(a,0,b,0),)归约为一对子问题,其中，S,11,是由求解(1-1)得到的,现在必须先求解(1-1)，所以我们计算它的差别，此差别为：猴子不在b处这个差别给出关键算符:f,1,goto(b),。,这个关键算符又被用来把问题(a,0,b,0),)归结为一对子问题：,43,现在，这对子问题中的第一个问题已是本原问题，它的差别为零，因为(a,0,b,0)是在域f,1,内，f,1,可用来求解此问题。因此，我们可以开始求解第二个子问题(1-12)。由于f,1,(S,111,)=(b,0,b,0),所以问题(1-12)变为：,这个问题也是本原问题，因为(b,0,b,0)在域f,2,内，f,2,可用于求解此问题。把早先产生的问题求解过程继续进行下去，直到最后解答此初始问题为止。,44,2.4,谓词逻辑法,命题逻辑能够把客观世界的各种事实表示为逻辑命题，但是它有较大的局限性，即不适合于表示比较复杂的问题。,谓词逻辑可以表达那些无法用命题逻辑表达的事情，一阶谓词演算是一种形式语言，其根本目的在于把数学中的逻辑论证符号化。,如果采用数学演绎的方式证明一个新语句是从那些已知正确的语句导出的，那么就能够断定这个新语句也是正确的。,旧知识,数学演绎,新知识,45,命题逻辑及其局限性,命题：不带参数的谓词,谓词：带参数的命题,我们可以很容易地把客观世界的各种事实表示为逻辑命题，用命题逻辑把各种命题写成合适公式（WFF），也称“谓词公式”。例如：,晴天:表示为 SUNNY,雨天：表示为 RAINING,雾天：表示为 FOGGY,46,“若为雨天，则非晴天”表示为,RAINING,SUNNY,“张三是工人”表示为,ZHANG SAN IS A WORKER,“毛泽东生于1893年”表示为,MAO ZEDONG IS BORN IN EIGHTEEN NINETY THREE,由上述可知，表示知识的陈述性形式称为,命题,。,47,比起命题来，谓词有更强的表达能力：（1）命题没有概括能力，例如，为了表达：XX是一个城市，则有多少个城市就要用多少个命题来表示。但是，这些命题只要用一个谓词CITY（X）就可以表示，其中X可以是北京、上海、广州,（2）谓词的使用使我们的知识表示方法更深了一层。谓词的表达能力比命题强还因为它把每个知识单元进一步细分了。原来“XX是一个城市”是一个基层知识单元，参数化后，把“城市”这个概念分割出来了，而XX则是另外一个概念，谓词样品CITY（XX）把“城市”和“XX”两个概念连结在一起，而且说明“XX”是“城市”的一个子概念。打个比方，过去是用一个名字来代表化学中的一个分子，而现在则是用它的内部原子结构来表示。,（3）谓词优于一般命题的第二个方面，是因为谓词可以代表变化着的情况，而命题只能代表某种固定的情况。,（4）可以利用谓词在不同的知识之间建立联系。进一步还可以把两个高级的知识单元联成更高级的知识单元。,48,语法和语义(Syntax&Semantics),谓词逻辑的基本组成部分是谓词符号、变量符号、函数符号和常量符号，并用圆括弧、方括弧、花括弧和逗号隔开，以表示论域内的关系。,常量符号：用来表示论域内的物体或实体，可以是实际的物体和人，也可以是概念或具有名字的任何事情。,变量符号：可以不明确涉及是那一个实体。,函数符号：表示论域内的函数。,谓词演算（Predicate Calculus）,49,又如,“李的母亲和他的父亲结婚”这句话的原子公式表示如下：,例,机器人(ROBOT)在1号房间(ROOM1)内;,原子公式是由若干谓词符号和项组成。,50,在谓词演算中，一个合适公式可以通过规定语言的元素在论域内的,关系，实体和函数之间的对应关系来解释。,对每个谓词符号，必须规定定义域内的一个相应关系；,对每个常量符号，必须规定定义域内的一个相应实体；,对每个函数符号，必须规定定义域内的一个函数。,这些规定，确定了谓词演算语言的语义。,对于已定义了的某个解释的一个原子公式，只有当其对应的语句,在定义域内为真时，才具有值 T（真）；而有当其对应的语句在定,义域内为假时，才具有值 F（假）。,51,连词和量词(Connective&Quantifiers),原子公式是谓词演算基本积木块，用连词（与），,（或）和,“=”（蕴涵，或隐含）等符号连接。,多个原子公式的组合构成比较复杂的合适公式。,合取（conjunction）（与）,合取就是用连词把几个公式连接起来而构成的公式。合取项是合取式的,每个组成部分。,例：LIKE(I，MUSIC)LIKE(I，PAINTING)(我喜爱音乐和绘画。),析取（disjunction）（或）,析取就是用连词把几个公式连接起来而构成的公式。析取项是析取式的,每个组成部分。,例：PLAYS(LILI，BASKETBALL)PLAYS(LILI，FOOTBALL),(李力打篮球或踢足球。),52,蕴涵,“=”表示“如果-那么”的语句。用连词=连接两个公式所构成的公式叫做蕴涵。蕴涵的左式叫做前项，右式叫做后项。,IF=THEN,例：RUNS(LIUHUA，FASTEST)=WINS(LIUHUA，CHAMPION)(如果刘华跑得最快，那么他取得冠军),如果后项取值T(不管前项的值为何)，或者前项取值F(不管后项的值为何)，则蕴涵取值T,否则蕴涵取值F。,合取和析取的真值由其组成部分的真值决定。如果每个合取项均取值T，则其合取值为T,否则合取值为 F。如果析取项中至少有一个取T值，则其析取值为T,否则取值F。,53,(2)量词 全称量词(Universal Quantifier)若一个原子公式P(x)，对于所有可能变量x都具有T值，则用(,x)P(x)表示。,例：(,x)ROBOT(x)=COLOR(x,GRAY)(所有的机器人都是灰色的）(,x)Student(x)=Uniform(x,Color)(所有学生都穿彩色制服),存在量词(Existential Quantifier)若一个原子公式P(x)，至少有一个变元X，可使P(X)为T值，则用(,x)P(x)表示。,例：(,x)INROOM(x,r,1,)(1号房间内有个物体),量化变元(Quantified Variables)量化一个合适公式中的某个变量所得到的表达式也是合适公式，如果一个合适公式中某个变量是经过量化的，就把这个变量叫做约束变量，否则就叫它为自由变量。,在合适公式中，我们感兴趣的主要是所有变量都是受约束的。,54,否定,“”（非）用来否定一个公式的真值，也就是说把一个合适公式的取值从T变为F,或从F变为T。,例：INROOM(ROBOT，r2)(机器人不在2号房间内),具有符号的公式叫做否定。一个合适公式的否定也是合适公式,某些文献中也用符号“”可表示否定。,55,谓词公式（Predicate Formulas）,谓词公式的定义,原子谓词公式：用P(x,1,x,2,x,n,)表示一个n元谓词公式其中P为n元谓词，x,1,x,2,x,n,为客体变量或变元。通常把P(x,1,x,2,x,n,)叫做谓词演算的原子公式，或原子谓词公式。,分子谓词公式：可以用连词把原子谓词公式组成复合谓词公式，并把它叫做分子谓词公式。,56,谓词演算中,合适公式(WFF,well-formed formulas)的递归定义：(1)原子谓词公式是合适公式。(2)若A为合适公式，则,A也是一个合适公式。(3)若A和B都是合适公式，则(AB),(AB),(A=B),(AQ,（3）狄.摩根定律 (P,Q)等价于,P,Q；,(P,Q)等价于,P,Q,（4）分配律 P,(Q R)等价于(,P,Q)(,P,R),P,(Q R)等价于(,P,Q),(,P,R),（5）交换律 P,Q 等价于 Q,P;P,Q 等价于 Q,P,58,（6）结合律 （P,Q）R,等价于 P,（Q R）,（P,Q）R,等价于 P,（Q R）,（7）逆否律 P=Q 等价于 Q=P,（8）(x)P(x)等价于(x)P(x)(x)P(x)等价于(x)P(x),（9）(x)P(x),Q(x)等价于(x)P(x),(x)Q(x),（10）(x)P(x)等价于(y)P(y),59,置换,在谓词逻辑中，有些推理规则可应用于一定的合适公式和合适公式集，以产生新的合适公式。一个重要的推理规则是假元推理，这就是由合适公式W,1,和W,1=,W,2,产生合适公式W,2,的运算。另一个推理规则叫做全称化推理，它是由合适公式(x)W(x)产生合适公式W(A)，其中A为任意常量符号。,置换与合一（Substitution&Unification）,假元推理：,全称化推理：,综合推理：,60,置换：用项(A)替换函数表达式中的变量(x)，记为ES，即表示一个表达式E(Expression)用一个置换S(Substitution)而得到的表达式的置换。一个表达式的项可以为变量符号，常量符号或者函数表达式。函数表达式由函数符号和项组成。一个表达式的置换就是在该表达式中用置换项置换变量。,表达式Px,f(y),B的4个置换为,我们用Es来表示一个表达式E用置换s所得到的表达式的置换。于是，我们可得到Px,f(y),B的4个置换的例，如下：,61,性质：,可结合律(LS,1,)S,2,=L(S,1,S,2,),(S,1,S,2,)S,3,=S,1,(S,2,S,3,),置换是可结合的。用s,1,s,2,表示两个置换s,1,和s,2,的合成。L表示一表达式，则有(Ls,1,)s,2,=L(s,1,s,2,)以及(s,1,s,2,)s,3,=s1(s,2,s,3,)即用s,1,和s,2,相继作用于表达式L是同用s,1,s,2,作用于L一样的。一般说来，置换是不可交换的，即 s,1,s,2,s,2,s,1,合一(unification)：,合一：寻找项对变量的置换，以使两表达式一致。可合一：如果一个置换s作用于表达式集E,i,的每个元素，则我们用E,i,s来表示置换例的集。我们称表达式集Ei是可合一的。如果存在一个置换s使得,E,1,s=E,2,s=E,3,s=.,那么称s为Ei的合一者。因为s的作用是使集合成为单一形式。,62,例:表达式集Px,f(y),B,Px,f(B),B的合一者为 s=A/x,B/y;,但是它不是最简单的合一者，最简单的合一者为,g=B/y;,如果s是集合E,i,的任一合一者，又存在某个s，使得,E,i,s=E,i,gs,成立，则称g为E,i,的最通用（最一般）的合一者，记为mgu.,63,合一 算法：,分歧集：设有一非空有限公式集F=F,1,F,2,F,n,，从F中各公式的第一个符号同时向右比较，直到发现第一个彼此不尽相同的符号为止，从F中的各个公式中取出那些以第一个不一致符号开始的最大的子表达式为元素，组成一个集合D，称为的分歧集(Disagreement set),合一算法,设F为非空有限表达式集合，则按下列步骤求其mgu:,置,k=0,F,k,=F,k,=,（,空置换，即不含元素的置换）。,若,F,k,只,含有一个表达式，则算法停止，,k,就是所要求的,mgu,。,找出,F,k,的,分歧集,D,k,。,若,D,k,中存在元素,a,k,和,t,k,，,其中,a,k,是,变元，,t,k,是项目，且,a,k,不在,t,k,中,出现，则置,k+1,=,k,t,k,/a,k,F,k+1,=,F,k,t,k,/a,k,算法停止，,F,的,mgu,不存在。,64,语义网络的特点(1)能把实体的结构、属性与实体间的因果关系显示地和简明地表达出来，与实体相关的事实、特征和关系可以通过相应的节点弧线推导出来。(2)使得概念易于受访和学习。(3)表现问题更加直观，更易于理解，适于知识工程师与领域专家沟通。(4)语义网络结构的语义解释依赖于该结构的推理过程而没有结构的约定，因而达到的推理不能保证象谓词逻辑法那样有效。,(5)节点间的联系可能是线状、树状或网状的，甚至是递归状的结构，使相应的知识存储和检索可能需要比较复杂的过程。,65,2.5语义网络法,语义网络是1968年Quilian在研究人类联想记忆时提出的心理学模型，认为记忆是由概念间的联系来实现的。1972年，Simmons首先将语义网络表示法用于自然语言理解系统。语义网络的结构：语义网络是知识的一种图解表示，它由节点和弧线或链线组成。节点用于表示实体、概念和情况等，弧线用于表示节点间的关系。组成部分(1)词法部分 决定表示词汇表中允许有哪些符号，它涉及各个节点和弧线。(2)结构部分 叙述符号排列的约束条件，指定各弧线连接的节点对。(3)过程部分 说明访问过程，这些过程能用来建立和修正描述，以及回答相关问题。(4)语义部分 确定与描述相关的(联想)意义的方法即确定有关节点的排列及其占有物和对应弧线。,66,二元语义网络的表示(Representation of Two-Element Semantic Network),1.表示简单的事实,所有的燕子都是鸟,2.表示占有关系和其它情况,小燕是一只燕子，燕子是鸟；巢-1是小燕的巢，巢-1是巢中的一个。,67,我椅子的颜色是咖啡色的；椅子包套是皮革；椅子是一种家具；椅子是座位的一部分；椅子的所有者是X；X是个人,。,68,3.选择语义基元,用来表示基本的物体或概念的节点称为概念节点，而表示某一实例的节点称为实例节点。,试图用一组基元来表示知识，以便简化表示，并可用简单的知识来表示更复杂的知识。,69,多元语义网络的表示（Representation of Multi-Element Semantic Network）,1.谓词逻辑与语义网络等效,2.例子,70,语义网络是一种网络结构。节点之间以链相连。多元语义网络表示的实质：把多元关系转化为一组二元关系的组合，或二元关系的合取。如果所要表示的知识是一元关系，例如，要表示李明是一个人，这在谓词逻辑中可表示为MAN(LIMING)。用语义网络，这就可以表示为:,如果我们所要表示的事实是多元关系的，例如，要表达北京大学(BEIJING University,简称BU)和清华大学(TSINGHUA University,简称TU)两校篮球队在北大进行的一场比赛的比分是85比89。若用谓词逻辑可表示为SCORE(BU，TU，(85-89)。这个表示式中包含3项，而语义网络从本质上来说，只能表示二元关系。解决这个矛盾的一种方法是把这个多元关系转化成一组二元关系的组合，或二元关系的合取。具体来说，多元关系R(X1，X2，Xn)总可以转换成R,1,(X,11,，X,12,)R,2,(X,21,，X,22,)R,n,(X,n1,X,n2,)例如，三根线a，b，c组成一个三角形。这可表示成TRIANGLE(a，b，c)。这个三元关系可转换成一组二元关系的合取，即CAT(a,b)CAT(b,c)CAT(c,a)其中，CAT表示串行连接。,71,要在语义网络中进行这种转换需要引入附加节点。对于上述球赛，我们可以建立一个G25节点来表示这场特定的球赛。然后，把有关球赛的信息和这场球赛联系起来。,72,在这里，将要研究如何用语义网络表示谓词逻辑法中的各种连词及量化。,连接词和量化的表示（Representation of Connective and Quantification）,1.合取前已述及，多元关系可以被转换成一组二元关系的合取，从而可以用语义网络的形式表示出来。例如：John gave Mary the book这个事实，可用谓词逻辑表示为GIVE(JOHN,MARY,BOOK)其中包括3项。若用语义网络表示这个事实，就如图所示。其中引入了一个附加的节点G1，表示一个特定的给某人东西的事件。B23表示一件给人的东西。,73,2.析取 在语义网络中，为与合取关系相区别，在析取关系的连接上加注析取界限，并标记DIS。例如要表示ISA(A，B)PART-OF(B，C)，这时语义网络就如图所示,当合取关系嵌套在析取关系之内，如果合取关系不被标注就会引起误解。例如，要表示：John is a programmer or Mary is a lawyer。存在两个特定的职业事件OC1和OC2，它们之间是析取关系。因此可以表示成如图的形式,74,如进一步把John is a programmer以及Mary is a lawye