人工智能原理ch2 知识表示ppt课件.ppt

2022/12/13,1,人工智能原理,第二讲知识表示 之Introduction,主讲：王祖喜 华中科技大学图像所,2022/12/13,2,本章主要讨论了知识表示问题，介绍了几种知识表示方法：如状态空间法、问题归约法、谓词演算法、语义网络法、框架表示、面向对象表示、剧本表示、过程表示等。,2022/12/13,3,知识是智能的基础。为了使计算机具有智能，使它能模拟人类的智能 行为，就必须使它具有知识。但知识是需要用适当的模式表示出来才能存储到计算机中去的，因此关于知识的表示问题就成为人工智能中的一个重要的研究课题。,知识定义、分类及表示,2022/12/13,4,1. 关于知识的定义,信息(information)信息是伴随着宇宙的形成而产生的，它普遍存在于自然界、人类社会及思维活动中。但怎样给信息下一个定义呢？由于各学派研究的内容、方法不尽相同，对信息产生了各种各样的看法，信息作为一门新兴学科，由于它涉及的领域广，内容丰富，至今还没有一个统一的，为大家所公认的定义。,2022/12/13,5,总结归纳一下，信息的定义包括以下几个要点：(1) 信息是客观存在的。控制论的奠基人维纳有一句名言“信息就是信息，不是物质，也不是能量”，讲的是信息的客观永恒性；(2) 信息是物质世界普遍存在的东西，一切物质都无时无刻不在发出信息，一切信息都是物质产生的。(3) 信息是客观世界中各种事物变化和特征的反映。任何事物都在不停地运动和变化着，呈现出不同的状态和特征，伴随着的信息也总是在不断地生长和传递着。,2022/12/13,6,(4) 信息是客观事物之间全面相互作用、全面相互联系的表征。客观世界中各种事物在一定条件下相互作用、全面联系，引起事物的物质结构和量度的变化，是由信息来表现的。(5) 信息都是要经过传递的。只有传递才能反映事物的存在方式和运动状态，任何信息只有经过传递才能被人们接受和利用。(6) 人们获得了信息，经过加工和有序化过程，实际上就是获得了知识。,2022/12/13,7,知识(knowledge) 知识是人们在长期的生活及社会实践中积累起来的对客观世界的认识与经验，人们把实践中获得的信息关联在一起，就获得了知识。如：把“大雁向南飞”与“冬天就要来临了“这两个信息关联在一起，得到了如下一条知识：“如果大雁向南飞，则冬天就要来临了。”,2022/12/13,8,知识反映了客观世界中事物间的关系，不同事物或者相同事物间的不同关系形成了不同的知识。如：“雪是白色的” 是一条知识，它反映了雪与颜色之间的关系。在人工智能中，这种知识称为“facts”。,2022/12/13,9,而 “如果头疼且流鼻涕，则可能是患了感冒“，反映了头疼流鼻涕与感冒之间的一种因果关系。在人工智能中，这种知识，即用“如果则”关联起来的知识称为“rules”。,2022/12/13,10,人们所涉及到的知识是十分广泛的。有的属多数人所熟悉的，有的只是有关专家才掌握的专门领域知识。对于“知识”难以给出明确的定义，只能从不同侧面加以理解。Feigenbaum认为知识是经过削减、塑造、解释和转换的信息。简单地说，知识是经过加工的信息。Bernstein说知识是由特定领域的描述、关系和过程组成的。Hayes-Roth认为知识是事实、信念和启发式规则。,2022/12/13,11,从知识库观点看，知识是某论域中所涉及的各有关方面、状态的一种符号表示。知识可从(范围，目的，有效性)加以三维描述。其中知识的范围是由具体到一般知识的目的是由说明到指定知识的有效性是由确定到不确定。例如“为了证明AB，只需证明AB是不可满足的”这种知识是一般性、指示性、确定性的。而像桌子有四条腿这种知识是具体的、说明性、不确定性的。,2022/12/13,12,2. 知识的特性,(1) 相对正确性 (Relatively Correct)知识是人们对客观世界认识的结晶，并且受到长期检验。因此在一定条件和环境下，知识一般是正确的，可信任的。这里的一定条件和环境是必不可少的，是知识正确性的前提。,2022/12/13,13,(2) 不确定性 (Uncertainty)知识并不总是只有“真”与“假”这两种状态，而是在“真假”之间存在很多中间状态，知识的这一特性称为不确定性。知识不确定性的原因很多。概括起来有以下几种：由随机性引起的不确定性由模糊性引起的不确定性由不完全性引起的不确定性由经验引起的不确定性,2022/12/13,14,(3) 可表示性与可利用性 (Representation and Utility)知识是可用适当形式表示出来的，如：语言、文字、图形、神经网络等，所以它才得以被存储并被传播；知识当然也可被利用，我们时时都在利用它解决各种问题。,2022/12/13,15,按知识的作用范围分：常识性知识，领域性知识。常识性知识人们普遍知道的知识，适用于所有领域；领域性知识面向某个具体领域的知识，是专业性知识，专家系统主要是以领域性知识为基础建立起来的。,3. 知识的分类,按知识的作用及表示分：事实性知识，过程性知识，控制性知识事实性知识（陈述性知识）用于表示描述领域内有关概念、事实、事物的属性及状态等；事实性知识一般采用直接表达的形式，如用谓词公式表示等。过程性知识主要指领域知识，用于指出如何处理与问题相关的信息以求得问题的解，由领域内的规则、定律、定理及经验构成；其表示方法既可以是一组产生式规则，也可以是语义网络等。,2022/12/13,17,控制性知识又称深层知识或元知识，是关于如何运用已有的知识进行问题求解的知识，又称“关于知识的知识”。例如问题求解中的推理策略（正向推理及逆向推理)；信息传播策略 (如不确定性的传递算法)；搜索策略(广度优先、深度优先、启发式搜索等)；求解策略(求第一个解、全部解、严格解、最优解等)。,2022/12/13,18,按知识的确定性来分：确定性知识，不确定知识确定性知识可以指出其值为“真”或“假”的知识，是精确性知识；不确定性知识指具有“不确定”特性的知识，它是对不精确、不完全及模糊性知识的总称。,2022/12/13,19,按知识的结构及表现形式：逻辑性知识，形象性知识逻辑性知识反映人类逻辑思维过程的知识，如人类的经验性知识。这种知识一般都具有因果关系及难以精确描述的特点，它们通常是基于专家的经验，以及对一些事物的直观感觉。在下面讨论的知识表示方法中，一阶谓词逻辑表示法，产生式表示法都是用来表示这种知识的；,2022/12/13,20,形象性知识在人类的思维中，还有一种是形象思维，通过事物的形象（如：一棵树，看过之后在脑子里建立起的概念）建立起来的知识，成为形象性知识。 目前人们正在研究利用神经元网络连接机制来表示这种知识。,2022/12/13,21,从抽象、整体的观点来分：零级知识，一级知识，二级知识 零级知识指问题领域内的事实、定律、定理、方程等常识性知识和原理性知识；一级知识具有经验性和启发性的知识；二级知识如何运用上述两级知识的知识，即元知识。,2022/12/13,22,4. 知识的表示,(1) 定义所谓知识的表示实际上是对知识的一种描述，或者说一种约定，一种计算机可以接受的用于描述知识的数据结构。对知识的表示过程就是把知识编码成某种数据结构的过程。知识表示是研究用机器表示知识的可行性、有效性的一般方法，是一种数据结构与控制结构的统一体，既考虑知识的存储又考虑知识的使用。知识表示可看成是一组描述事物的约定，以把人类知识表示成机器能处理的数据结构。,2022/12/13,23,(2) 分类 粗略地分为两类： 符号表示法：用各种包含具体涵义的符号，以各种不同的方式和次序组织起来表示知识的一类方法，主要用来表示逻辑性知识。本课程所要讨论的各种知识表示方法多属于这一类。连接机制表示法：是用神经网络技术表示知识的一种方法，它把各种物理对象以不同的方式和次序连接起来，并在其间相互传递及加工各种包含具体意义的信息，以此来表示相关的概念及知识。它特别适合于表示各种形象性知识。这部分内容可参看人工神经网。,2022/12/13,24,(3) 对表示的要求充分性：能够将问题求解所需的知识正确有效的表达出来；可理解性：所表达知识简单、明了、易于理解；可利用性：能够有效地利用所表达的知识；可扩充性：能够方便、灵活的对所表达的知识进行维护和扩充；,2022/12/13,25,(4) 常用表示方法. 一阶谓词逻辑表示法采用一阶谓词逻辑表示知识 属叙述性知识表示有严格的数学基础. 产生式规则表示法将知识表示成“if then”的形式；表示方法自然、简洁；III.语义网络表示法采用结点和结点间的弧表示对象、概念及其相互关系。,2022/12/13,26,. 框架表示法将知识表示为层状结构，一个对象或概念的所有信息均属于该层次的结构中；该层次结构还可以表示对象间的关系；该层次结构由一系列的“槽”和相关于“槽”的一系列“侧面”组成；. 其它表示法状态空间法；与或图PETRI网概念图,2022/12/13,27,陈述式知识表示与过程式知识表示,陈述式知识表达 语义网络、框架和剧本等知识表示方法，均是对知识和事实的一种静止的表达方法，我们称这类知识表达方式为陈述式知识表达，它所强调的是事物所涉及的对象是什么，是对事物有关知识的静态描述，是知识的一种显式表达形式。而对于如何使用这些知识，则通过控制策略来决定。,2022/12/13,28,过程式知识表示 和知识的陈述式表示相对应的是知识的过程式表示。所谓过程式表示就是将有关某一问题领域的知识，连同如何使用这些知识的方法，均隐式地表达为一个求解问题的过程。它所给出的是事物的一些客观规律，表达的是如何求解问题。知识的描述形式就是程序，所有信息均隐含在程序中，因而难于添加新知识和扩充功能，适用范围较窄。,2022/12/13,29,人工智能系统所关心的知识,一个智能程序高水平的运行需要有关的事实知识、规则知识、控制知识和元知识。事实 是有关问题环境的一些事物的知识，常以“是”的形式出现。如事物的分类、属性、事物间关系、科学事实、客观事实等，事实是静态的为人们共享的可公开获得的公认的知识，在知识库中属低层的知识。如雪是白色的、鸟有翅膀、张三李四是好朋友、这辆车是张三的。,2022/12/13,30,规则 是有关问题中与事物的行动、动作相联系的因果关系知识，是动态的，常以如果那么形式出现。特别是启发式规则是属专家提供的专门经验知识，这种知识虽无严格解释但很有用处。控制 是有关问题的求解步骤、技巧性知识，告诉怎么做一件事。也包括当有多个动作同时被激活时应选哪一个动作来执行的知识。,2022/12/13,31,元知识 是有关知识的知识，是知识库中的高层知识。包括怎样使用规则、解释规则、校验规则、解释程序结构等知识。元知识与控制知识是有重迭的，对一个大的程序来说，以元知识或说元规则形式体现控制知识更为方便，因为元知识存于知识库中，而控制知识常与程序结合在一起出现，从而不容易修改。,2022/12/13,32,人工智能学科体系,人工智能学科体系的层次人工智能理论基础数学基础:数理逻辑，计算的数学理论，离散数学,模糊数学思维科学理论:认知心理学,逻辑或抽象思维学,形象或直感思维学 计算机工程技术:硬件,软件技术人工智能原理知识的表达,知识的处理,知识的获取与学习,利用知识求解问题.,2022/12/13,33,人工智能工程系统专家咨询系统,专家系统开发工具与环境,自然语言理解系统,图像理解与识别系统,智能机器人系统,2022/12/13,34,知识的表示方法,知识的表示方法概括有以下几种： 谓词逻辑法 状态空间法问题归约法语义网络法 框架表示法 面向对象表示 剧本(script)表示 过程(procedure)表示,2022/12/13,35,人工智能原理,第二讲知识表示 之谓词逻辑/产生式表示,主讲：王祖喜 华中科技大学图像所,2022/12/13,36,知识的表示方法,谓词逻辑法 状态空间法问题归约法语义网络法 框架表示法 面向对象表示 剧本(script)表示 过程(procedure)表示 小结,2022/12/13,37,数理逻辑,数理逻辑：用数学方法来研究推理的形式结构和推理规律的数学学科与数学其它分支、计算机科学、AI、语言学有密切的联系数理逻辑的内容逻辑演算命题逻辑、谓词逻辑 证明论 公理集合论 递归论 模型论,2022/12/13,38,提纲命题逻辑一阶谓词逻辑,2022/12/13,39,用形式逻辑（尤其是一阶谓词逻辑）表示知识是AI 研究中提出使用的一种普遍方法。命题逻辑和谓词逻辑是最先应用于人工智能的两种逻辑，谓词逻辑是在命题逻辑基础上发展起来的，命题逻辑可以看作是谓词逻辑的一种特殊形式。,2022/12/13,40,一、命题逻辑,命题定义：能够判断真假的陈述句真值真：正确的判断;真值1,T假：错误的判断;真值0,F例子：2是素数雪是黑色的3能够被2整除地球以外的星球上也有人,2022/12/13,41,一些不是命题的句子,X+Y5 X,Y未知，真假不定这朵花多美呀！ 感叹句明天下午有会吗？ 疑问句请你把门关上！ 祈使句,2022/12/13,42,判断是否为命题的方法,陈述句真值确定真值是确定的可以不知道,2022/12/13,43,原子命题与命题符号化,原子命题（简单命题）不能够再分解的命题命题符号化使用小写的字母表示命题放在命题的前面p,q,r, pi,qi,rip:2是素数 真命题q:雪是黑的 假命题,2022/12/13,44,命题常量和命题变量,命题常量：其真值是确定的简单命题命题变量（命题变元）定义：真值不确定的简单陈述句表示：也用小写字母表示：p,q,r, pi,qi,ri性质：命题变量不是命题例子：X+y5,2022/12/13,45,复合命题,定义：由简单命题用联结词联结而成的命题例子3不是偶数2是素数和偶数林芳学过英语或日语如果角A和角B是对顶角，则角A和角B相等,2022/12/13,46,否定、合取联结词,定义1：设p为任一命题，复合命题“非p”称为p的否定式，记做p。为否定联结词， p为真当且仅当p为假。p:3是偶数、p:3不是偶数定义2：设p,q为二命题，复合命题“p并且q”称作p和q的合取式，记做pq， 为合取联结词，pq为真当且仅当p，q同时为真p:李平聪明q:李平用功pq：李平不但聪明，而且用功p q：李平聪明,但不用功,2022/12/13,47,析取联结词,定义3：设p,q为二命题，复合命题“p或q”称作p和q的析取式，记做p q， 为析取联结词， pq为真当且仅当p和q中至少有一个为真p:李平聪明q:李平用功pq：李平聪明或者用功pq：李平聪明或者不用功,2022/12/13,48,蕴涵联结词,定义4：设p,q为二命题，复合命题“如果p，则q”称作p和q的蕴涵式，记做pq， 为蕴涵联结词， pq为假当且仅当p为真，q为假如果pq为真，记做p q，称为定理与自然语言不一样，蕴涵式的前件和后件可以没有内在联系 例：如224，则太阳从西边出来蕴涵式的真值表,2022/12/13,49,蕴涵联结词,将下列命题符号化只要不下雨，我就骑自行车上班只有不下雨，我才骑自行车上班p:下雨q:骑自行车上班pq qp,2022/12/13,50,等价联结词,定义5：设p,q为二命题，复合命题“p当且仅当q”称作p和q的等价式，记做p q， 为等价联结词， p q为假当且仅当p与q的真值不相同与自然语言不一样，等价式的2个命题可以没有内在联系例如：224，当且仅当太阳从西边出来蕴涵式的真值表,2022/12/13,51,逻辑联结词的优先级,2022/12/13,52,命题符号化的例子,分析出简单命题，将之符号化用联结词将简单命题联结起来，形成复合命题的符号化例子：1：小王是游泳冠军或是百米赛跑冠军2：如果我上街，我就去书店看看，除非我很累1：pq,其中：q:小王是游泳冠军；q:小王是百米赛跑冠军2：r (pq),其中p:我上街,q:我去书店看看, r:我很累,2022/12/13,53,命题公式及分类,复合命题：p,pq, pq,pq,p q如果p,q为命题常量，这些复合命题为命题如果p,q为命题变量，这些复合命题为命题公式命题公式：由命题常量、命题变量、逻辑联结词、括号等构成的有效字符串,2022/12/13,54,命题公式及分类,定义6：1. 单个命题常项或变项p,q,r,pi,qi,ri ,0,1是合式公式2. 如果A是合式公式，则（A）为合式公式3. 如果A,B是合式公式，则（AB）,（A B） ,（AB） , （A B）也是合式公式4. 只有有限次地应用13组成的符号串才是合式公式命题逻辑下的合式公式：命题公式，公式例子：q qvr,2022/12/13,55,公式的层次,定义7若A为单个命题（常项或变项）p,q,r,pi,qi, ri, ,0,1，则称A为0层公式称A是n+1 (n=0)层公式是指A符合下列情况之一：A B,B为n层公式A BC, 其中B，C分别为i,j层公式，且n= max(i,j)A BC, 其中B,C的层次同2A B C, 其中B,C的层次同2A B C, 其中B,C的层次同2,2022/12/13,56,命题公式的赋值或解释,命题公式中命题常项和变项，不是命题，只有对命题公式中的所有命题变项进行赋值，公式的真值才能够确定下来，才能够变成命题定义8：设A为一个命题公式，p1,p2,pn为出现在A中的所有命题变项，给指定一组真值，称为对A的一个赋值或解释。如果指定的一组值使A的值为真，则称这组值为成真赋值，如果指定的一组值使A的值为假，则称这组值为成假赋值。,2022/12/13,57,公式的真值表,真值表：含有n个变项的公式，其赋值有2n个，将每一个赋值及公式在此赋值下的真值构成的表例子: (p(pq) q,2022/12/13,58,公式的性质,定义9设A为一个命题公式若A在它的各种赋值下取值均为真，则称A为重言式或永真式（真值表最后一列全为1）若A在它的各种赋值下取值均为假，则称A为矛盾式或永假式（真值表最后一列全为0）若A至少存在一组赋值是成真赋值，则称A为可满足式（真值表最后一列有1）,2022/12/13,59,等值演算,判断公式性质的办法真值表等值演算将之演算成简单形式，判断其性质定义10设A,B为2个命题公式，若等价式A B是重言式，则称A与B是等值的，记做A B ：不是逻辑联结词，一个等值的记号，不能够用（数值上的相等）代替等值本质上是指：公式A和B在任何解释下都相等,2022/12/13,60,逻辑等值式,2022/12/13,61,逻辑等值式,2022/12/13,62,逻辑等值式,2022/12/13,63,等值演算,利用等值式，将一个公式变换成另外一种形式的过程例子,2022/12/13,64,等值演算,2022/12/13,65,等值演算,2022/12/13,66,简单析取式及简单合取式,简单析取式和简单合取式定义10：仅由有限个命题变项或其否定构成的析取式称为，简单析取式；仅由有限个命题变项或其否定构成的合取式称为，简单合取式例子：简单析取式：p, q, pq, pq, pqr简单合取式：p, q, pq, pq, pqr,2022/12/13,67,合取范式,定义11：仅有有限个简单析取式构成的合取式称为合取范式A=A1A2An其中A1，A2，An为简单析取式例子：A=(pqr)(pq)(qq)任何公式都有与其对应的合取范式,2022/12/13,68,化成合取范式的步骤,1. 消去对，来说冗余的联结词2. 否定联结词的消除或内移3. 利用分配率,2022/12/13,69,合取范式,原子：命题常项或变项文字：原子或原子的否定 子句：文字的析取合取范式：子句的合取子句集：合取范式的集合表示每一个合取项作为集合的元素元素之间的关系为合取,2022/12/13,70,命题逻辑的问题,命题作为命题演算的基本单位，不再分解无法研究命题内部的结构和命题之间的联系 例子：苏格拉底三段论p:凡人都是要死的q:苏格拉底是人r:苏格拉底是要死的命题符号化： (pq)r 真值不定！,2022/12/13,71,将命题进一步分解成：个体词，谓词和量词等研究它们的形式结构和逻辑关系，总结出正确地推理形式和规则一阶谓词逻辑,解决办法,2022/12/13,72,二、一阶谓词逻辑,简单命题的分解：个体词和谓词个体词指可以独立存在的客体可以表示具体的事物：李明，玫瑰花，自然数可以表示抽象的概念：思想谓词用于刻画个体词的性质或个体词之间的关系的词 2是有理数，是有理数 小李比小王高， 比高,2022/12/13,73,个体常项、个体变项,个体常项定义：表示具体或特定的词表示：小写的英文字母a,b,c,表示个体确定下来个体变项定义：泛指的个体的词表示：小写的英文字母x,y,z,表示个体没有确定下来,2022/12/13,74,个体域,个体域个体变项的取值范围可以是一个有限的集合a,b,c也可以是一个无限的集合：全体自然数，全体实数全总个体域：宇宙间的一切事物组成的个体域,2022/12/13,75,谓词常项、谓词变项,谓词常项定义：表示具体性质或关系的词表示：大写英文字母F,G,H,谓词变项定义：表示抽象或泛指的性质或关系的词表示：大写英文字母F,G,H, F(x): x很高，x是无理数,; L(x,y):x比y学习好, x比y大,;,2022/12/13,76,谓词的元数,谓词的元数：谓词中包含的个体词的个数n元谓词：包含有n个个体词的谓词F(x)一元谓词L(x,y)二元谓词有时n元谓词：包含有n个个体变项的谓词F(a): 0元谓词L(x,a):1元谓词,2022/12/13,77,谓词符号化的例子,2是素数且是偶数F(x): x是素数;G(x)：x是偶数a:2F(a)G(a)如果2大于3，则2大于4L(x,y): x大于ya:2; b:3 ; c:4L(a,b)L(b,c),2022/12/13,78,全称量词和存在量词,谓词符号化下面的句子所有的人都是要死的有的人活到100岁以上量词：表示数量的词全称量词对应于日常语言中的“一切”，“任意的”，“所有的”表示： xF(x）,2022/12/13,79,全称量词和存在量词,存在量词对应于日常语言中的“存在着”，“有一个”，“至少一个”等词表示： xF(x),2022/12/13,80,谓词符号化的例子,所有的人都是要死的定义谓词：F(x），x是要死的个体域为全体人类时： xF(x）全总个体域(没有申明个体域)： x(M(x) F(x)特性谓词：M(x)有的人活到100岁以上定义谓词：G(x）x活到100岁以上个体域为全体人类时： xG(x）全总个体域(没有申明个体域)： x(M(x)G(x),2022/12/13,81,量词使用的注意事项,不同的个体域，符号化的形式可能不一样如果没有给出个体域，都应以全总个体域为个体域引入特性谓词后，使用全称量词和存在量词符号化的形式不一样个体词和谓词的涵义确定之后，n元谓词转化成命题至少要n个量词,2022/12/13,82,量词使用的注意事项,当个体域为有限集时，D=a1,a2,an,由量词的意义可以看出，对于任意的谓词F(x)，都有 xF(x) F(a1)F(a2)F(an) xF(x) F(a1)F(a2)F(an)多个量词同时出现，不能够随意颠倒它们的次序 x yH(x, y) x yH(x, y),2022/12/13,83,一阶谓词逻辑中的命题符号化,凡是有理数都可以表示成分数不用引入特性谓词的情况 xF(x)引入特性谓词的情况 x(R(x) F(x),2022/12/13,84,一阶谓词逻辑中的命题符号化,没有不犯错误的人没有指定个体域，以全总个体域作为个体域谓词：M(x) x是人；F(x): x犯错误 x(M(x)F(x)在北京工作的人未必是北京人F(x): x在北京工作； G(x): x是北京人 x(F(x)G(x),2022/12/13,85,谓词公式的字母表,定义11 字母表个体常项: a,b,c, ai,bi,ci, i=1个体变项:x,y,z, xi,yi,zi, i=1函数符号:f,g,h, fi,gi,hi, i=1谓词符号:F,G,H, Fi,Gi,Hi, i=1量词符号: , 联结词符： , , , , 逗号和括号： （，），,2022/12/13,86,项的递归定义,定义121. 个体常项和变项是项2. 若(x1,x2,xn)是任意的n元函数，x1,x2,xn是项，则(x1,x2,xn)是项3. 只有有限次地使用1，2生成的符号才是项a,b,x,y, f(x,y), f(x,g(a,b,z),2022/12/13,87,合式公式（谓词公式）,原子公式定义13：设R(x1,x2,.,xn)是任意的n元谓词，t1,t2,tn为项，则R(t1,t2,tn)称为原子公式合式公式，定义14：1. 原子公式是合式公式2. 如果A是合式公式，则（A）为合式公式3. 如果A,B是合式公式，则（AB）,（A B） , （AB） , （A B）也是合式公式4. 如果A是合式公式，则 xA， xA也是合式公式5. 只有有限次地应用14组成的符号串才是合式公式（谓词公式）,2022/12/13,88,指导变项、辖域,定义15：在合式公式 xA和 xA中，称x为指导变项，称A为相应量词的辖域。在辖域中，x的所有出现称为约束出现（即x受相应量词指导变项的约束），A中不是约束出现的其它变项称为自由出现。通常用A(x)表示x是自由出现的任意公式例子 x(F(x) yH(x,y) xF(x)G(x,y) x y(R(x,y)L(y,z) xH(x,y),2022/12/13,89,闭式,定义16：设A为任一公式，若A中无自由出现的个体变项，则称A是封闭的合式公式，简称闭式。例子：,2022/12/13,90,换名规则和代替规则,为了避免出现某个变项既是自由出现的又是约束出现的，使用以下2种办法换名规则：将量词辖域种出现的某个约束出现的个体变项及对应的指导变项，改成另外一个辖域中未曾出现过的个体变项符号，公式其它部分不变 xF(x)G(x,y) zF(z)G(x,y)代替规则：对某个自由出现的个体变项用与原公式中的所有个体变项符号不同的变项符号来代替，且处处代替 xF(x)G(x,y) xF(x)G(z,y),2022/12/13,91,公式的解释,公式的解释：一阶谓词公式中含有：个体常项，个体变项（自由出现或约束出现的），函数变项，谓词变项等。对各种变项指定特殊的常项来代替，就构成公式的一个解释。解释，定义17一个解释I由下面的4个部分构成1. 非空个体域D2. D上的一部分特定的元素3. D上的一些特定的函数4. D上的一些特定的谓词,2022/12/13,92,解释的例子,解释DI=2,3DI上的特定元素函数：f(2)=3,f(3)=2谓词：F(2)=0;f(3)=1 G(x,y)为G(i,j)=1, i,j=2,3; L(x,y)为L(2,2)=L(3,3)=1 L(3,2)=L(2,3)=0;,2022/12/13,93,公式的解释,2022/12/13,94,公式的性质,定义18设A为一个公式(谓词公式)若A在它的任何解释下取值均为真，则称A为逻辑有效式或永真式若A在它的任何解释下取值均为假，则称A为矛盾式或永假式若A至少存在一组解释是成真赋值，则称A为可满足式,2022/12/13,95,代换实例,定义19：设A0是含命题变项p1,p2,pn的命题公式，A1,A2,An是n个谓词公式，用Ai(i=1n)处处代替pi，所得到的公式称为A0的代换实例例子命题公式：pq A1 xF(x) A2 G(x,y)代换实例： ( xF(x)G(x,y),2022/12/13,96,代换实例的一个结论,命题公式的重言式的代换实例在谓词逻辑中，仍然是重言式；命题公式的矛盾式的代换实例在谓词逻辑中，仍然是矛盾式；例子：,2022/12/13,97,一阶逻辑等值式,定义20：设A,B是一阶逻辑中的任意2公式，若A B是逻辑有效式，则称A与B是等值的，记做A B，称A B为等值式命题逻辑中的24条等值式的代换实例也是逻辑等值式,2022/12/13,98,谓词逻辑中的逻辑等值式1,定理1：量词否定等值式,2022/12/13,99,谓词逻辑中的逻辑等值式2,定理2：量词的辖域收缩和扩张等值式,2022/12/13,100,谓词逻辑中的逻辑等值式3,定理3：量词分配等值式,2022/12/13,101,谓词逻辑中的逻辑等值式4,定理4量词的性质相同，可以交换位置量词的性质不同，不可交换位置,2022/12/13,102,前束范式,定义21：设A为一谓词公式，如果A具有如下形式： Q1x1Q2x2QkxkB 则称A是前束范式。其中每一个Qi为 或 B为不含量词的谓词公式（母式）例如： x y(F(x,y)G(x,y) 前束范式 x(F(x) y(G(y)H(x) 非前束范式,2022/12/13,103,前束范式例题,求下列公式的前束范式,2022/12/13,104,谓词公式的合取范式和子句集,对任一公式量词辖域扩张和收缩定理，得到前束范式对于母式，等值演算得到合取范式合取项的集合，构成了该公式的子句集S母式原子：谓词文字：谓词或谓词的否定子句：文字的析取合取范式：子句的合取子句集：合取范式的集合形式，元素之间的关系为合取关系,2022/12/13,105,人工智能原理,第二讲知识表示 之状态空间表示,主讲：王祖喜 华中科技大学图像所,2022/12/13,106,知识的表示方法,谓词逻辑法 状态空间法问题归约法语义网络法 框架表示法 面向对象表示 剧本(script)表示 过程(procedure)表示 小结,2022/12/13,107,状态空间法,问题求解(problem solving)是个大课题，它涉及归约、推断、决策、规划、常识推理、定理证明和相关过程的核心概念。在分析了人工智能研究中运用的问题求解方法之后，就会发现许多问题求解方法是采用试探搜索方法的。也就是说，这些方法是通过在某个可能的解空间内寻找一个解来求解问题的。这种基于解答空间的问题表示和求解方法就是状态空间法，它是以状态和算符(operator)为基础来表示和求解问题的。,2022/12/13,108,问题求解技术两个主要的方面问题的表示：如果描述方法不对，对问题求解会带来很大的困难求解的方法：采用试探搜索方法。,2022/12/13,109,状态空间法三要点状态（state）：表示问题解法中每一步问题状况的数据结构；算符（operator）：把问题从一种状态变换为另一种状态的手段；状态空间方法：基于解答空间的问题表示和求解方法，它是以状态和算符为基础来表示和求解问题的。,2022/12/13,110,1.问题状态描述,要完成某个问题的状态描述，必须确定三件事： 该状态描述方式，特别是初始状态描述； 操作符集合及其对状态描述的作用； 目标状态描述的特性。,2022/12/13,111,定义 :状态(state)：为描述某类不同事物间的差别而引入的一组最少变量q0，q1，qn的有序集合，其矢量形式如下： 式中每个元素qi(i=0,1，n)为集合的分量，称为状态变量。,2022/12/13,112,给定每个变量的一组值就得到一个具体的状态，如 Qk=q0k，q1k，. ，qnkT 它只是问题所有可能状态的罗列，还必须描述这些状态之间的可能变化。所谓操作，或称为算子是引起状态中的某分量发生改变，从而使问题由一个具体状态A变化为另一具体状态B的作用。,2022/12/13,113,算符：使问题从一种状态变化为另一种状态的手段称为操作符或算符。操作符可为走步、过程、规则、数学算子、运算符号或逻辑符号等。问题的状态空间(state space)：是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合，即所有可能的问题初始状态集合S(初始状态S0S)、操作符集合F以及目标状态集合G(GS)。可把状态空间记为三元状态(S，F，G)。状态空间可用有向图来表示,2022/12/13,114,状态空间的一个解 使一个有限的操作算子序列，它使初始状态转化为目标状态：S0-f1-S1-f2-.fk-G,2022/12/13,115,状态空间表示详释,让我们先用数码难题(puzzle problem)来说明状态空间表示的概念。由15个编有1至15并放在44方格棋盘上的可走动的棋子组成。棋盘上总有一格是空的，以便可能让空格周围的棋子走进空格，这也可以理解为移动空格。图中绘出了两种棋局，即初始棋局和目标棋局，它们对应于该下棋问题的初始状态和目标状态。如何把初始棋局变换为目标棋局呢？问题的解答就是某个合适的棋子走步序列，如左移棋子12，下移棋子15，右移棋子4，等等。,2022/12/13,116,（a）初始棋局 （b）目标棋局 十五数码难题,2022/12/13,117,总状态为16!20922789888000由于棋盘的对称性，实际状态数减半上、下、左、右移动四种操作,2022/12/13,118,十五数码难题最直接的求解方法是尝试各种不同的走步，直到偶然得到该目标棋局为止。这种尝试本质上涉及某种试探搜索。从初始棋局开始，试探(对于一般问题实际上是由计算机进行计算和执行的)由每一合法走步得到的各种新棋局，然后计算再走一步而得到的下一组棋局。这样继续下去，直至达到目标棋局为止。把初始状态可达到的各状态所组成的空间设想为一幅由各种状态对应的节点组成的图。这种图称为状态图。图中每个节点标有它所代表的棋局。首先把适用的算符用于初始状态，以产生新的状态；然后，再把另一些适用算符用于这些新的状态；这样继续下去，直至产生目标状态为止。,2022/12/13,119,部分状态图：,2022/12/13,120,我们一般用状态空间法这一术语来表示下述方法：从某个初始状态开始，每次加一个操作符，递增地建立起操作符的试验序列，直到目标状态为止。寻找状态空间的全部过程包括从旧的状态描述产生新的状态描述，以及此后检验这些新的状态描述，看其是否描述了该目标。这种检验往往只是查看某个状态是否与给定的 目标状态描述相匹配。,2022/12/13,121,2.状态图示法,图论中的几个术语节点(node)：图形上的汇合点，用来表示状态、事件和时 间关系的汇合，也可用来指示通路的汇合；弧线(arc)：节点间的连接线；有向图(directed graph)：一对节点用弧线连接起来，从一个节点指向另一个节点。,2022/12/13,122,后继节点(descendant node)与父辈节点(parent node)：如果某条弧线从节点ni指向节点nj，那么节点nj就叫做节点ni的后继节点或后裔，而节点ni叫做节点nj的父辈节点或祖先。路径：某个节点序列(ni1,ni2,nik)当j=2，3，k时，如果对于每一个ni,j-1都有一个后继节点nij存在，那么就把这个节点序列叫做从节点ni1至节点nik的长度为k的路径。代价：用c(ni,nj)来表示从节点ni指向节点nj的那段弧线的代价。,2022/12/13,123,如果从节点ni至节点nj存在有一条路径，那么就称节点nj 是从节点ni可达到的节点。两节点间路径的代价等于连接该路径上各节点的所有弧线代价之和。最小者称为最小代价的路径。,2022/12/13,124,显式表示：各节点及其具有代价的弧线由一张表明确给出。此表可能列出该图中的每一节点、它的后继节点以及连接弧线的代价。隐式表示：节点的无限集合si作为起始节点是已知的。后继节点算符也是已知的，它能作用于任一节点以产生该节点的全部后继节点和各连接弧线的代价。,2022/12/13,125,图的显式和隐式表示,一个图可由显式说明也可由隐式说明。显然，显式说明对于大型的图是不切实际的，而对于具有无限节点集合的图则是不可能的。此外，引入后继节点算符的概念是方便的。后继节点算符也