《人工智能及其应用》第02章

文学志南京信息工程大学计软学院2010年2月第2章知识表示方法文学志南京信息工程大学计软学院2010年2月2.1知识表示基本概念2.2状态空间法2.3问题归约法2.4谓词逻辑法文学志南京信息工程大学计软学院2010年2月2.1知识表示基本概念文学志南京信息工程大学计软学院2010年2月2.1.1知识什么是知识知识是人们在改造客观世界的实践中积累起来的认识和经验数据是指人们为了描述客观世界中的具体事物而引入的一些数字、字符、文字等符号或这些符号的组合。信息是指由不同数据所组成的一种有意义的结构。知识是对信息进行智能性加工所形成的、对客观世界规律性的认识。知识与信息“信息”与“关联”是构成知识的两个关键要素。文学志南京信息工程大学计软学院2010年2月2.1.1知识知识的类型按知识的性质可分为概念、命题、公理、规则、方法等按知识的适应范围常识性知识：通用通识的知识领域性知识：面向某个具体专业的专业性知识。按知识的作用效果事实性知识：也称叙述性知识，用来描述问题或事物的概念、属性、状态、环境及条件等情况的知识。过程性知识：用来描述问题求解过程所需要的操作、演算或行为等规律性的知识。控制性知识：也称元知识或超知识，是关于如何运用已有知识进行问题求解的知识。文学志南京信息工程大学计软学院2010年2月2.1.2知识表示知识表示概念及其要求概念知识表示就是对知识的描述，即用一些约定的符号把知识编码成一组可以被计算机接收，并便于系统使用的数据结构。要求表示能力：指能否正确、有效地将问题求解所需要的各种知识表示出来。可利用性：指通过使用知识进行推理，可求得问题的解可组织性与可维护性o可组织性：指把有关知识按照某种方式组成一种知识结构。o可维护性：在保证知识的一致性与完整性的前提下，对知识所进行的增加、删除、修改等操作。可实现性：是指知识表示要便于在计算机上实现，便于直接由计算机对其进行处理。自然性与可理解性o自然性：指知识表示形式要符合人们的日常习惯和思维形式o可理解性：指所表示的知识应易读、易懂、易获取、易维护文学志南京信息工程大学计软学院2010年2月2.1.2知识表示知识表示观点陈述性观点陈述性知识表示（declarationknowledgerepresentation）是指以陈述的方式把知识用一定的数据结构表示出来。特点：把知识的表示和运用分开处理。过程性观点过程性知识表示（proceduralknowledgerepresentation）是指以程序（也称为过程）的方式把知识表示出来特点：把知识的表示和运用结合起来。两种知识表示观点的结合知识表示方法文学志南京信息工程大学计软学院2010年2月2.1.2知识表示知识表示方法又称为知识表示技术，其表示形式被称为知识表示模式。陈述性知识表示方法一阶谓词逻辑表示法产生式表示法结构化表示法过程性知识表示方法状态空间表示法问题规约法文学志南京信息工程大学计软学院2010年2月2.2状态空间法文学志南京信息工程大学计软学院2010年2月2.2.1问题状态描述状态的基本概念状态(state)是为描述某类不同事物间的差别而引入的一组最少变量q0，q1，…，qn的有序集合，其矢量形式如下：Q=［q0,q1,…,qn］T(2.1)式中每个元素qi(i=0,1，…，n)为集合的分量，称为状态变量。给定每个分量的一组值就得到一个具体的状态，如Qk=［q0k,q1k,…，qnk］T(2.2)算符使问题从一种状态变化为另一种状态的手段称为操作符或算符。操作符可为走步、过程、规则、数学算子、运算符号或逻辑符号等。问题的状态空间(statespace)是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合，即所有可能的问题初始状态集合S、操作符集合F以及目标状态集合G。因此，可把状态空间记为三元状态(S，F，G)。状态空间的表示法对一个问题的状态描述，必须确定3件事：(1)该状态描述方式，特别是初始状态描述；(2)操作符集合及其对状态描述的作用；(3)目标状态描述的特性。文学志南京信息工程大学计软学院2010年2月2.2.2状态图示法基本概念图由节点(不一定是有限的节点)的集合构成。有向图一对节点用弧线连接起来，从一个节点指向另一个节点。路径某个节点序列(ni1,ni2,…,nik)当j=2，3，…，k时，如果对于每一个ni,j-1都有一个后继节点nij存在，那么就把这个节点序列叫做从节点ni1至节点nik的长度为k的路径。代价(cost)是给各弧线指定数值以表示加在相应算符上的代价。图的显式说明是指各节点及其具有代价的弧线由一张表明确给出。图的隐式说明是指各节点及其具有代价的弧线不能由一张表明确给出。文学志南京信息工程大学计软学院2010年2月2.3问题归约法文学志南京信息工程大学计软学院2010年2月2.3.1问题归约描述问题归约法的概念已知问题的描述，通过一系列变换把此问题最终变为一个子问题集合；这些子问题的解可以直接得到，从而解决了初始问题。该方法也就是从目标(要解决的问题)出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个平凡的本原问题集合。这就是问题归约的实质。问题归约法的组成部分（1）一个初始问题描述；（2）一套把问题变换为子问题的操作符；（3）一套本原问题描述。示例：梵塔难题问题有3个柱子(1，2，3)和3个不同尺寸的圆盘(A，B，C)。在每个圆盘的中心有个孔，所有圆盘可以堆叠在柱子上。最初，全部3个圆盘都堆在柱子1上：最大的圆盘C在底部，最小的圆盘A在顶部。要求把所有圆盘都移到柱子3上，每次只许移动一个，而且只能先搬动柱子顶部的圆盘，还不许把尺寸较大的圆盘堆放在尺寸较小的圆盘上。文学志南京信息工程大学计软学院2010年2月归约过程（1）移动圆盘A和B至柱子2的双圆盘难题；（2）移动圆盘C至柱子3的单圆盘难题；（3）移动圆盘A和B至柱子3的双圆盘难题。由上可以看出简化了难题每一个都比原始难题容易，所以问题都会变成易解的本原问题。文学志南京信息工程大学计软学院2010年2月2.3.2与或图表示（1）与或图的概念用一个类似图的结构来表示把问题归约为后继问题的替换集合，画出归约问题图。例如，设想问题A需要由求解问题B、C和D来决定，那么可以用一个与图来表示；同样，一个问题A或者由求解问题B、或者由求解问题C来决定，则可以用一个或图来表示。与或图的有关术语父节点：是一个初始问题或是可分解为子问题的问题节点。子节点：是一个初始问题或是子问题分解的子问题节点。或节点：只要解决某个问题就可解决其父辈问题的节点集合。与节点：只有解决所有子问题，才能解决其父辈问题的节点集合。弧线：是父辈节点指向子节点的圆弧连线。终叶节点：是对应于原问题的本原节点。文学志南京信息工程大学计软学院2010年2月2.3.2与或图表示（2）与或图的有关定义可解节点：与或图中一个可解节点的一般定义可以归纳如下(1)终叶节点是可解节点(因为它们与本原问题相关连)。(2)如果某个非终叶节点含有或后继节点，那么只有当其后继节点至少有一个是可解的时，此非终叶节点才是可解的。(3)如果某个非终叶节点含有与后继节点，那么只要当其后继节点全部为可解时，此非终叶节点才是可解的。不可解节点：不可解节点的一般定义归纳于下(1)没有后裔的非终叶节点为不可解节点。(2)如果某个非终叶节点含有或后继节点，那么只有当其全部后裔为不可解时，此非终叶节点才是不可解的。(3)如果某个非终叶节点含有与后继节点，那么只要当其后裔至少有一个为不可解时，此非终叶节点才是不可解的。文学志南京信息工程大学计软学院2010年2月2.3.2与或图表示（3）与或图构图规则(1)与或图中的每个节点代表一个要解决的单一问题或问题集合。图中所含起始节点对应于原始问题。(2)对应于本原问题的节点，叫做终叶节点，它没有后裔。(3)对于把算符应用于问题A的每种可能情况，都把问题变换为一个子问题集合；有向弧线自A指向后继节点，表示所求得的子问题集合。(4)一般对于代表两个或两个以上子问题集合的每个节点，有向弧线从此节点指向此子问题集合中的各个节点。(5)在特殊情况下，当只有一个算符可应用于问题A，而且这个算符产生具有一个以上子问题的某个集合时，由上述规则3和规则4所产生的图可以得到简化。文学志南京信息工程大学计软学院2010年2月2.4谓词逻辑法(3_23网工)文学志南京信息工程大学计软学院2010年2月2.4.1谓词演算语法和语义谓词逻辑的基本组成部分是谓词符号、变量符号、函数符号和常量符号，并用圆括弧、方括弧、花括弧和逗号隔开，以表示论域内的关系。原子公式是由若干谓词符号和项组成，只有当其对应的语句在定义域内为真时，才具有值T(真)；而当其对应的语句在定义域内为假时，该原子公式才具有值F(假)。连词和量词连词有∧(与)、∨(或)，全称量词(∀x)，存在量词(∃x)。原子公式是谓词演算的基本积木块，运用连词能够组合多个原子公式以构成比较复杂的合式公式。文学志南京信息工程大学计软学院2010年2月2.4.1谓词演算几个有关定义用连词∧把几个公式连接起来而构成的公式叫做合取，而此合取式的每个组成部分叫做合取项。一些合式公式所构成的任一合取也是一个合式公式。用连词∨把几个公式连接起来所构成的公式叫做析取，而此析取式的每一组成部分叫做析取项。由一些合式公式所构成的任一析取也是一个析取公式。用连词→连接两个公式所构成的公式叫做蕴涵。蕴涵的左式叫做前项，右式叫做后项。如果前项和后项都是合式公式，那么蕴涵也是合式公式。前面具有符号～的公式叫做否定。一个合式公式的否定也是合式公式。量化一个合式公式中的某个变量所得到的表达式也是合式公式。如果一个合式公式中某个变量是经过量化的，就把这个变量叫做约束变量，否则就叫它为自由变量。在合式公式中，感兴趣的主要是所有变量都是受约束的。这样的合式公式叫做句子。文学志南京信息工程大学计软学院2010年2月2.4.2谓词公式谓词合式公式的定义在谓词演算中合式公式的递归定义如下：(1)原子谓词公式是合式公式。(2)若A为合式公式，则～A也是一个合式公式。(3)若A和B都是合式公式，则(A∧B)，(A∨B)，(A→B)和(A←→B)也都是合式公式。(4)若A是合式公式，x为A中的自由变元，则(∀x)A和(∃x)A都是合式公式。(5)只有按上述规则(1)至(4)求得的那些公式，才是合式公式。举例：试把下列命题表示为谓词公式：任何整数或者为正或者为负。提问：指出此例题谓词公式中的量词、连词及蕴涵符号。文学志南京信息工程大学计软学院2010年2月3_25第3、4节软工例1所有的整数不是偶数就是奇数I(x):x是整数。E(x):x是偶数。O(x):x是奇数。（∀x）（I(x)→E(x)∨O(x)）例2王宏是计算机系的一名学生。王宏和李明是同班同学。凡是计算机系的学生都喜欢编程序。COMPUTER(x):表示x是计算机系的学生。CLASSMATE(x,y):表示x和y是同班同学。LIKE(x,z):表示x喜欢z。COMPUTER(wanghong)CLASSMATE(wanghong,liming)(∀x)(COMPUTER(x)→LIKE(x,programing))文学志南京信息工程大学计软学院2010年2月2.4.2谓词公式合式公式的性质(1)否定之否定～(～P)等价于P(2)P∨Q等价于～P→Q(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∧PP∨Q等价于Q∨P(6)结合律(P∧Q)∧R等价于P∧(Q∧R)(P∨Q)∨R等价于P∨(Q∨R)文学志南京信息工程大学计软学院2010年2月2.4.2谓词公式合式公式的性质(7)逆否律P→Q等价于～Q→～P此外，还可建立下列等价关系：(8)～(∃x)P(x)等价于(∀x)［～P(x)］～(∀x)P(x)等价于(∃x)［～P(x)］(9)(∀x)［P(x)∧Q