我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:双彩网 > 语义树 >

人工智能原理与应用 教案doc

归档日期:06-28       文本归类:语义树      文章编辑:爱尚语录

  1.本站不保证该用户上传的文档完整性,不预览、不比对内容而直接下载产生的反悔问题本站不予受理。

  人工智能原理 Principles and Application of Artificial Intelligence 课程简介 本课程主要讲述人工智能的基本概念、基本方法,会用搜索算法、推理方法和机器学习求解简单问题,如证明定理、机器推理、建造简单的专家系统,自然语言分析和理解。 要求 了解人工智能的提出,几种智能观,人工智能重要的研究领域,以及人工智能求解问题的方法与传统的数学方法的不同; 掌握启发式搜索概念,会用搜索方法求解简单问题 掌握归结推理方法,会用归结法证明定理,求解问题。 掌握一种不确定推理方法,会建造带有不确定推理的专家系统。 了解其它的推理方法; 掌握知识的表示方法,会用来表达某一具体的场景; 掌握机器学习概念和学习模型,会用实例学习方法进行学习, 了解数据挖掘的过程,会用关联规则挖掘算法做数据挖掘; 掌握自然语言理解的过程,会用基本的切分和语法分析方法做自然语句分析; 理解神经网络实现智能的另一种观点。掌握BP神经网的工作原理,会用来求解(如识别)问题; 了解遗传算法(GA)概念及如何使用遗传算法 参考资料: 《人工智能原理与应用》,张仰森,高等教育出版社 《人工智能》,蔡自兴 《人工智能原理》,石纯一 黄昌宁 王家钦编著,清华大学出版社 《人工智能》(上下册),陆汝铃编著,科学出版社,1996 《人工智能与知识工程》,田盛丰、黄厚宽,中国铁道出版社,1999 《高级人工智能》,史忠植,科学出版社,1998 《人工智能基础》,高济、朱森良、何钦铭,高等教育出版社,2002 第一章 人工智能概述 1.1 人工智能的起源与发展 计算机所能处理对象的改变:纯粹数值计算→非数值计算(自然语言理解、图象语音识别、专家系统、机器博弈系统等等符号知识处理) 试探性搜索、启发式搜索、不确定性推理方法更符合人类思维过程。也就是说在解决这类问题时,没有算法解或即使有算法解但在当今计算技术不能实现。对这类问题可行的解决方法是搜索、试探,加上经验的启发式知识。这是一种来自专门领域的经验知识,限于特定场合,经常会取得成功但又不能保证必然成功,常能求得有关问题的满意解答。 医生一定能根据病人的症状诊断出是何种疾病吗?我们能用传统的算法设计一个程序进行疾病诊断吗?能用传统的算法设计一个程序能理解自然语言所组成的文档的含义吗? 以上原因促使人工智能学科的诞生。 主要经历了以下几个阶段: 孕育期(1956年以前)——从理论、技术和物质上奠定基础 成长期(1956-1972)——逻辑推理机程序、跳棋程序、通用问题求解(GPS:General Problem Solver)、人工智能程序设计语言LISP/PROLOG 发展期(1972-)——知识工程、专家系统(MYCIN,探矿系统) 学习期 1.2 什么是人工智能 1.什么是人类智能?有何特点?计算机到底能不能有人类智能? 英国数学家Turing于1950提出的著名的Turing实验。 识别、推理、联想、自学习...(人脑的智能很复杂!) 计算机到底能不能有人类智能,至今没有完整的论证(人工智能是一门正在探索和发展的学科,至今还没有完全形成完整的理论体系。目前人工智能与人脑的智能还相差很远) 2.什么是人工智能? 人工智能简称为AI(Artificial Intelligence),是研究如何制造出智能机器或智能系统,来模拟人类智能活动、延伸人类智能的学科。 已实现的人工智能系统: 第一个人工智能专家系统DENDRAL,能根据有机化合物的质谱数据,推断出给有机化合物的分子结构,该系统得到甚至超过化学专家水平。该系统是由Stanford大学的Feigenbaum领导研制成功的。 医疗专家系统MYCIN 探矿专家系统PROSPECTOR 1995年美国智能机器人驾驶汽车以55km/h速度从东部一直开到西部(机器视觉) 1997年国际象棋大师卡斯帕罗夫与IBM深蓝巨型机上的博弈系统对弈 自然语言理解系统 机器翻译系统 机器证明系统(证明了“四色问题”、数学中的定理) 1.3 AI的研究途径、方法、不同学派 1.目标: 近期目标:使机器更聪明 远期目标:探讨研制智能机 2. 方法、途径 仿生学方法:对人脑思维进行生理学模拟,通过微观方法直接模拟人脑和神经系统的结构功能 计算机方法:利用计算机科学的观点,从宏观上模拟人的智能活动 数学方法:建立数学模型,利用算法求解问题 心理学方法:建立心理学模型,利用启发式程序求解问题 3.人工智能研究的各种学派及其理论 功能模拟,符号演绎 模拟人脑的逻辑思维,将问题和知识表示成某种逻辑网络,采用符号推演的方法,实现搜索、推理、学习等功能。这种方法目前还在使用,人工智能研究中的很多成果都是用该方法取得的,如定理证明,自动推理,专家系统、博弈系统等。 采用这种方法的研究者称为心理学派或逻辑学派或符号主义,代表人物是NILSSON,本课程就是讲解这种研究方法。 结构模拟,神经网络计算 根据人脑的生理结构和工作机理,研究和实现计算机智能。因为人脑是由神经细胞组成的神经网络,所以该研究途径就是用人工神经元组成的人工神经网络模型来存储信息和知识,用神经计算(数值计算)的方法实现自学习、联想、识别和推理功能。神经网络具有高度的并行分布性。该研究方法适于实现图象、声音信息识别。 采用这种研究途径称为生理学派或连接主义,代表人物是Newell 行为模拟,控制进化 这种方法模拟人在控制过程中的智能活动和行为特性(自寻优,自适应,自学习),强调“现场AI”(situated AI)即智能系统或智能机器能与环境交互,能对环境进行感知从而表现出智能行为,也就是说智能行为不需要知识从而与“符号主义”相悖。 这种方法的研究者称为行为主义、进化主义或控制论学派。代表人物是MIT的Brooks教授。 人工智能是引起争议最多的学科之一,因而各种研究学派在发展的过程都经历了许多挫折. 通过什么途径有效地实现智能(如符号演绎推理,知识工程,神经网络计算,图搜索技术,不确定推理等). 人工智能的研究范围问题,一般认为包括:知识表示,推理技术,自然语言理解,知识工程,计算机视觉等许多方面.引起争议的原因,第一是由于边界不分明,某些分支与数学有交界(如定理证明,谓词逻辑),或与语言学有交界(如自然语言理解),或与心理学有交界(如认知模型),或与电子学机械学有交界(如计算机视觉,机器人).第二是由于科学的发展,各分支的内容在不断的变化.第三,随着研究工作的深入,一些传统的观念在发生变化,例如在历史上认为数值计算发展到符号演算是AI的一个重要特征,但在近年的研究中,计算机视觉和机器人学的研究中又回到了数值计算的现象,提高了数学在人工智能研究中的地位. 1.4 AI的研究领域 搜索算法:状态空间图、博弈树搜索 推理方法:归结推理、不确定性推理 自然语言理解:不仅能识别文字而且能理解文本含义的机器系统 模式识别(图象与语音识别) 知识工程(知识获取、知识表示、知识数据库、知识运用等一系列知识处理技术,是以知识为中心来组织智能系统) 神经网络技术 专家系统 机器人 1.5 人工智能求解方法的特点 AI研究的是以符号表示的知识而不是数值数据为研究对象; AI中采用的启发式搜索算法(Heuristic Research Algorithm)而不是常规的算法(Algorithm) 控制结构与知识是分离的 允许出现不正确的答案 1.6 人类智能和人工智能 1.人类智能特性 感知能力 思维能力 反应能力 2.人工智能特性 机器感知能力 机器思维能力(知识表示) 机器行为能力 第二章 知识表示.1知识及其表示 1.知识的概念 Feigenbaum认为知识是经过削减、塑造、解释和转换的信息。简单地说,知识是经过加工的信息。 Bernstein说知识是特定领域的描述、关系和过程组成。 Hayes-Roth认为知识是事实、信念和启发式规则。 知识可从(范围,目的,有效性)加以三维描述。其中知识的范围是由具体到一般,知识的目的是由说明到指定,知识的有效性是由确定到不确定。例如“为了证明A→B,只需证明A∧~B是不可满足的”这种知识是一般性、指示性、确定性的。而像“桌子有四条腿”这种知识是具体的、说明性、不确定性。 知识表示是研究用机器表示知识的可行性、有效性的一般方法,是一种数据结构与控制结构的统一体,既考虑知识的存储又考虑知识的使用。知识表示可看成是一组描述事物的约定,以把人类知识表示成机器能处理的数据结构。 2.人工智能系统所关心的知识 一个智能程序高水平的运行需要有关的事实知识、规则知识、控制知识和元知识。 事实:是有关问题环境的一些事物的知识,常以“...是...”的形式出现。如事物的分类、属性、事物间关系、科学事实、客观事实等,在知识库中属于低层的知识。如雪是白色的、鸟有翅膀、张三李四是好朋友。 规则:是有关问题中与事物的行动、动作相联系的因果关系知识,是动态的,常以“如果...那么...”形式出现。特别是启发式规则是属于专家提供的专门经验知识,这种知识虽无严格解释但很有用处。 控制:是有关问题的求解步骤,技巧性知识,告诉怎么做一件事。也包括当有多个动作同时被激活时应选哪一个动作来执行的知识。 元知识:是有关知识的知识,是知识库中的高层知识。包括怎样使用规则、解释规则、校验规则、解释程序结构等知识。 .2 逻辑表示法 对知识通过引入谓词、函数来加以形式描述,获得有关的逻辑公式,进而以机器内部代码表示。 设在一个房间里,有一个机器人ROBOT,一个壁室ALCOVE,一个积木块BOX,两个桌子A和B。机器人可把积木块BOX从一种状态变换成另一种状态。 引入谓词: TABLE(A)表示A是桌子 EMPTYHANDED(ROBOT)表示机器人双手是空的 AT(ROBOT,A)表示机器人在A旁 HOLDS(ROBOT,BOX)表示机器人拿着积木块 ON(BOX,A)表积木块BOX在A上 .3产生式表示法 产生式是一种知识表达方法,具有和Turing机一样的表达能力。 .3.1 事实与规则的表示 事实可看成是断言一个语言变量的值或是多个语言变量间的关系的陈述句,语言变量的值或语言变量间的关系可以是一个词。不一定是数字。如雪是白色的,其中雪是语言变量,其值是白色的。John喜欢Mary,其中John、Mary是两个语言变量,两者的关系值是喜欢。 一般使用三元组(对象,属性,值)或(关系,对象1,对象2)来表示事实,其中对象就是语言变量,若考虑不确定性就成了四元组表示(增加可信度)。这种表示的机器内部实现就是一个表。 如事实“老李年龄是35岁”,便写成(Lee,age,35) 事实“老李、老张是朋友”,可写成(friend,Lee,Zhang) 对于规则是表示事物间的因果关系,以下列形式表示: condition-action condition作为前件或模式,而action称作动作或后件或结论。前件部分常是一些事实Ai的合取,而结论常是某一事实B,如考虑不确定性,需另附可信度度量值。 .3.2 产生式系统的组成和推理 多数较为简单的专家系统(Expert System)都是以产生式表示知识的,相应的系统称作产生式系统。 产生式系统,由知识库和推理机两部分组成。其中知识库由规则库和数据库组成。规则库是产生式规则的集合,数据库是事实的集合。 规则是以产生式表示的。规则集蕴涵着将问题从初始状态转换解状态的那些变换规则,规则库是专家系统的核心。规则可表成与或树形式,基于数据库中的事实对这与或树的求值过程就是推理。 数据库中存放着初始事实、外部数据库输入的事实、中间结果事实和最后结果事实。 推理机是一个程序,控制协调规则库与数据库的运行,包含推理方式和控制策略。 产生式系统的推理方式有正向推理、反向推理和双向推理 正向推理:从已知事实出发,通过规则库求得结论,或称数据驱动方式。推理过程是 规则集中的规则前件与数据库中的事实进行匹配,得匹配的规则集合。 从匹配规则集合中选择一条规则作为使用规则。 执行使用规则的后件。将该使用规则的后件送入数据库中 重复这个过程直至达到目标 具体说如数据库中含有事实A,而规则库中有规则A-B,那么这条规则便是匹配规则,进而将后件B送入数据库中。这样可不断扩大数据库直至包含目标便成功结束。如有多条匹配规则需从中选一条作为使用规则,不同的选择方法直接影响着求解效率,选规则的问题称作控制策略。正向推理会得出一些与目标无直接关系的事实,是有浪费的。 反向推理:从目标(作为假设)出发,反向使用规则,求得已知事实,或称目标驱动方式,推理过程是: 规则集中的规则后件与目标事实进行匹配,得匹配的规则集合; 从匹配的规则集合中选择一条规则作为使用规则; 将使用规则的前件作为子目标; 重复这个过程直至各子目标均为已知事实成功结束; 如果目标明确,使用反向推理方式效率较高。 双向推理:同时使用正向推理又使用反向推理。 .3.3 产生式表示的特点 产生式表示格式固定,形式单一,规则(知识单位)间相互较为独立,没有直接关系使知识库的建立较为容易,处理较为简单的问题是可取的。另外推理方式单纯,也没有复杂计算。特别是知识库与推理机是分离的,这种结构给知识的修改带来方便,无须修改程序,对系统的推理路径也容易作出解释。所以,产生式表示知识常作为构造专家系统的第一选择的知识表示方法。 .4 语义网络表示法 逻辑表示法和产生式表示法常用于表示有关论域中各个不同状态间的关系,然而用于表示一个事物同其各个部分间的分类知识就不方便了。槽(slot)与填槽表示方法便于表示这种分类知识。语义网络和框架表示方法就属于其中的两种。 .4.1 语义网络的结构 语义网络是对知识的有向图表示方法。一个语义网络是由一些以有向图表示的三元组(结点1,弧,结点2)连接而成。 结点表示概念、事物、事件、情况等。 弧是有方向的有标注的。方向体现主次,结点1为主,结点2为辅。弧上的标注表示结点1的属性或结点1和结点2之间的关系。 如事实“雪是白色的”,可表示成: 如规则“如果A那么B”,可表示成: 这样事实与规则的表示是相同的,区别仅是弧上的标注有别。 从逻辑表示法来看,一个语义网络相当于一组二元谓词。因为三元组(结点1,弧,结点2)可写成P(个体1,个体2),其中个体1、个体2对应于结点1、结点2,而弧及其上标注的结点1与结点2的关系由谓词P来体现。 语义网络视作一种知识的单位,人脑的记忆是由存储了大量的语义网络来体现的。而产生式表示法是以一条产生式规则作为知识的单位,而各条产生式规则没有直接的联系。 结点间的关系有isa,a-part-of,is型 (1)ISA链用来表示具体-抽象关系,或说表示一种隶属关系,体现某种层次分类。特点是具体层结点可继承抽象层结点的属性。 (2)a-part-of链用来表示部分-全体关系,或说表示包含关系。特点是part-of关系下各层结点的属性可能是很不相同的。 (3)is链用于表示一个结点是另一个结点的属性 例:苹果的语义网络 .4.2 语义网络表示下的推理 语义网络表示下的推理方法不像逻辑表示法和产生式表示法的推理方法那样明了。语义网络表示法是依匹配和继承来进行推理的。最简单的isa关系下的推理是直接继承,如: 也可以将语义网络引入逻辑含义,表示出∧,∨,~关系,便可以使用归结推理法。 还有人将语义网络中的结点看成有限自动机(DFA),为寻求几个概念间的关系,起动相应的自动机,如有回合点便可求得解答。 .5 框架表示法 .5.1 框架理论 1975年Minsky的论文“A framework for respresenting knowledge”中提出了框架理论。其基本观点是人脑已存储有大量典型情景,当人面临新的情景时,就从记忆中选择一个称为框架的基本知识结构,这个框架是以前记忆的一个知识空框,而其具体内容依新的情景而改变,对这空框的细节加工修改和补充,形成对新情景的认识又记忆于人脑中。框架理论将框架视作的知识单位,将一组有关的框架连接起来便形成框架系统。系统中不同框架可以有共同结点,系统的行为由系统内框架的变化来表现的。推理过程是由框架间的协调来完成的。 框架表示法是一种适应性强、概括性高、结构化良好、推理方式灵活又能把陈述性知识与过程性知识相结合的知识表示方法。 .5.2 框架结构 框架是由若干结点和关系(统称为槽slot)构成的网络。是语义网络一般化形式化的一种结构,同语义网络没有本质区别。将语义网络中结点间弧上的标注也放入槽内就成了框架表示法。 框架是表示某一类情景的结构化的一种数据结构。框架由框架名和一些槽(slot)组成,每个槽有一些值,槽值可以是逻辑的、数字的,可以是程序、条件、默认值或是一个子框架。槽值含有如何使用框架信息、下一步可能发生的信息、预计未实现该如何做的信息等。 框架的一般格式: FRAMEWORK:framework name slot 1 face 11:value ... face 1n:value slot 2 face 21:value ... face 2n:value ... 例: framework: 大学教师 类属:教师 学历:(学士,硕士,博士) 专业:学科专业 职称:(助教,讲师,副教授,教授) 外语: 范围:(英,法,德,...) 默认:英 水平:(优、良、中、差) 默认:良 .5.3 框架表示下的推理 框架表示法没有固定的推理机理。但框架系统的推理和语义网络一样遵循匹配和继承的原则,而且框架中如if-needed、if-added等槽的槽值是附加过程,在推理过程中起重要作用。如确定一个人的年龄,已匹配的知识库中的框架为 槽名 年龄:NIL if-needed:ASK if-added:CHECK 在推理的过程中便启动了if-needed和if-added两个槽的附加过程ASK和CHECK。 4.5.4 框架与产生式表示法的比较 ? production framework 知识表示单位 规则 框架 推理 固定、与知识库独立 可变,与知识库成一体 建立知识库 容易 困难 通用性 低 高 应用 简单问题 复杂问题 用户 初学者 专家 3.1 归结推理方法(确定性推理方法) 3.1.1 谓词、函数、量词 谓词:表示个体对象之间的关系、属性或状态。其表示形式如下: P(x1,x2,x3,...xn) 其中: P是谓词符号,表示x1,x2,x3,...xn个体对象之间的属性、状态或关系。 x1,x2,x3,...xn是谓词的参量(或称项),一般表示个体,它可以是个体常量、个体变量或是个体函数。个体变元的变化范围称为个体域(或论域) 例: P(x):表示x是素数 FRIEND(a,b):表示a和b是朋友 个体函数:表示项之间的关系 有了个体函数之后,谓词的表达能力更强。假如个体函数father(b)表示“个体b的父亲”,则谓词FRIEND(a,father(b))表示“a和b的父亲是朋友”,显然表达能力更强了。 再例: E(x,y):表示x和y相等关系 个体函数square(x):表示个体x的平方 则谓词E(square(a),b)表示什么? 约定:(1)谓词符号有大写字母表示,如P,Q,R,S等;(2)用小写字母x,y,z等作为个体变元符号;(3)用小写字母a,b,c等作为个体常元符号;(4)用小写字母f,g,h表示个体函数符号。 量词 全称量词:“所有”,“一切”,“任一”,“全体”,“凡是”等词称为全称量词,记为x 存在量词:“存在”、“有些”、“至少有一个”、“有的”等词统称为存在量词,记为x 引入量词和连接符(→蕴涵,∧合取,∨析取,否定词~)之后,谓词的表达能力大大扩充了 例1: 谓词M(x):表示x是人,谓词N(x):表示x有名字,则x(M(x)→N(x))表示“凡是人都有名字”。 例2: 谓词G(x):表示x是整数,E(x):表示x是偶数,则x(G(x)∧~E(x))表示“存在不是偶数的整数” 例3:知识“不存在最大的整数”的表示 设:谓词G(x):表示x是整数,D(x,y)表示x大于y。则表示如下: ~x(G(x)∧y(G(y)→D(x,y)))或x(G(x)∧y(G(y)∧D(y,x))) 谓词公式:用谓词、量词(存在量词,全称量词)、联接词(→蕴涵,∧合取,∨析取)连接而成的复杂的符号表达式称为谓词公式。 3.1.2 命题逻辑的归结法 1.概念: 不带参数(肯定也不含量词))的谓词称为命题. 谓词的表达能力更强,命题没有概括能力; 命题: P1:代表“北京是一个城市” P2:代表“上海是一个城市” P3:代表“广州是一个城市” 谓词:CITY(x):代表“x是一个城市”,x的论域为D={北京,上海,广州} 谓词代表变化着的情况,而命题代表固定的情况; P:北京是一个城市; Q:煤球是白的; 则P为永真式,Q为永假式; 而对于以上的谓词CITY(x),当x取值为“北京”时为“真”值,当x取值为“煤球”时为“假”值。 谓词和命题相比的优点是谓词在不同的知识之间建立联系; 例如下面四个知识单元: HUMAN(x):代表x是人; LAWED(x):代表x受法律管制; COMMIT(x):代表x犯法; PUNISHED(x):x受法律制裁; 则 HUMAN(x)→LAWED(x)表示一个高级的知识单元“人人都受法律的管制”。 COMMIT(x)→PUNISHED(x)表示只要x犯罪,x就要受法律制裁。 {(HUMAN(x)→LAWED(x))→(COMMIT(x)→PUNISHED(x))}表示“如果由于某个x是人而受到法律管制,则这个人犯了罪就一定要受到惩罚” 由连接词(→蕴涵,∧合取,∨析取,等价-,否定词~)将命题连接在一起构成命题公式。 A-B,A称为前件,B称为后件,其真值表如下所示: A B A-B 0 0 1 0 1 1 1 0 0 1 1 1 A-B等价于(A-B)∧(B-A) 一些概念: 永真式:真值为T的命题公式称为永真式或重言式或有效的。 永假式:真值为F的命题公式称为永假式或不可满足的。 非永真式:不是永真式的命题公式; 可满足式:不是永假公式的命题公式; 原子公式:不含任何连接词的命题公式称为原子公式或称原子.例如P,Q 文字:原子公式及其否定形式称为文字.例如P,~L 子句:文字的析取称为子句.例如:P∨R∨~Q 互补文字:设L为一个文字,则称L与~L为互补文字。 一些有用的等价关系: ~~A=A 双重否定 A∧A=A 等幂律 A∨A=A A∧B=B∧A 交换律 A∨B=B∨A (A∧B)∧C=A∧(B∧C) 结合律 (A∨B)∨C=A∨(B∨C) A∧(B∨C)=(A∧B)∨(A∧C) 分配律 A∨(B∧C)=(A∨B)∧(A∨C) A∧(A∨B)=A 吸收律 A∨(A∧B)=A ~(A∧B)=~A∨~B 摩根定律 ~(A∨B)=~A∧~B A→B=~A∨B 蕴含表达式 A-B=(A→B)∧(B→A) 等价表达式 A∧T=A A∧F=F A∨T=T A∨F=A A∧~A=F 矛盾律 A∨~A=T 排中律 A→(B→C)=A∧B→C 输出律 (A→B)∧(A→~B)=~A 归谬律 A→B=~B→~A 逆反律 2 命题逻辑中的归结推理方法 若命题逻辑描述的命题A1,A2,...An和B,要证明在A1∧A2∧...∧An成立的条件下有B成立,或说A1∧A2∧...∧An→B。很显然A1∧A2∧...∧An→B等价于证明A1∧A2∧...∧An∧~B是矛盾(永假)式。归结推理的方法就是从A1∧A2∧...∧An∧~B出发使用归结推理规则来寻找矛盾,从而证明A1∧A2∧...∧An→B的成立。这种方法称为反演推理方法。 3 归结式 设有两个子句 C1=P∨C1 C2=~P∨C2 从中消去互补对,所得新子句R(C1,C2)=C1∨C2,称为子句C1,C2的归结式。没有互补对的两子句没有归结式。 归结推理规则就指的是对两子句做归结,也即求归结式。 下面证明归结推理规则是正确的,即C1∧C2=R(C1,C2),也即证明归结式是两子句的逻辑结论,或者说任一使C1,C2为线为真的任一解释,若在I下P为线必为线为真。若在I下P为假,则C1必为线为线),即归结式是子句的逻辑结论。 特别地,当C1=P,C2=~P时,R(C1,C2)=□,记作为空子句。显然C1,C2同时为真是矛盾,或者说空子句□体现了矛盾。 4 命题逻辑的归结推理过程 (1)利用逻辑蕴含式和逻辑等价式逻辑等价式和逻辑蕴含式xy(P(x,y)∧Q(a)∧R(z))就是前束范式。 x(N(x)∧yD(y,x))就不是前束范式。前束范式可分成前束合取范式和前束析取范式。 化成前束合取范式的步骤: step1:去掉多余的量词,即没意义的量词 step2:将同名的约束变元与自由变元改名,使它们不同名。 消去∧,∨,~以外的连接词 A-B.............~A∨B A-B............(~A∨B)∧(~B∨A) step4:将连接词~内移,移到原子公式之前 ~(~A)=A ~(A∧B)=~A∨~B ~(A∨B)=~A∧~B ~xA(x)=x~A(x) ~xA(x)=x~A(x) step5:将量词尽可能向左推,推到前缀所在的位置,用下列公式: xA(x)∨B............x(A(x)∨B),其中B中不含约束变元 B∨xA(x)............x(B∨A(x)),其中B中不含约束变元 xA(x)∨B............x(A(x)∨B),其中B中不含约束变元 B∨xA(x)............x(B∨A(x)),其中B中不含约束变元 同样对上面式子中的∨改为∧可得到另一组关于的∧的替换式。 另外还可用下式进行替换: xA(x)∧xB(x)..................x(A(x)∧B(x)) xA(x)∨xB(x)..................xy(A(x)∨B(y)),采用更名规则 xA(x)∨xB(x)..................x(A(x)∨B(x)) xA(x)∧xB(x)..................xy(A(x)∧B(y)),采用更名规则 step6:使用∧,∨的分配律化成合取范式。 例:将下列谓词公式化成前束合取范式: (4)Skolem(斯克林)标准型:将一个谓词公式中所有存在量词消去之后,便得到该谓词公式的Skolem标准型。 (5)建立谓词公式的子句集 2 将谓词公式化成子句集的步骤: 按上述步骤化成前束合取范式; 化成Skolem标准型,消去存在量词 消取存在量词时,还要进行变元替换。变元替换分两种情况: ①若该存在量词在某些全称量词的辖域内,则用这些全称量词指导变元的一个函数代替该存在量词辖域中的相应约束变元,这样的函数称为Skolem函数; ②若该存在量词不在任何全称量词的辖域内,则用一个常量符号代替该存在量词辖域中相应约束变元,这样的常量符号称为Skolem常量; 消去所有全称量词 消去合取词∧,用逗号代替,以子句为元素组成一个集合S,即是谓词公式的子句集 例1:求谓词公式G=xyz((~P(x,y)∨R(x,y,z))∧(Q(x,z)∨R(x,y,z)))的子句集。 解: 已经是前束范式,并且不含连接词。由于存在量词y,z都在全称量词x的辖域中,所以将y,z分别用Skolem函数f(x)、g(x)代替。 x((~P(x,f(x))∨R(x,f(x),g(x)))∧(Q(x,g(x))∨R(x,f(x),g(x))))已经是合取范式了,所以谓词公式G的子句集是 {~P(x,f(x))∨R(x,f(x),g(x)),Q(x,g(x))∨R(x,f(x),g(x))} 例2:求谓词公式的子句集:x(yP(x,y)→~y(Q(x,y)→R(x,y))) 解:x(yP(x,y)→~y(Q(x,y)→R(x,y))) ==x(yP(x,y)→y~(~Q(x,y)∨R(x,y))) ==x(yP(x,y)→y(Q(x,y)∧~R(x,y))) ==x(yP(x,y)→z(Q(x,z)∧~R(x,z))) ...改名 ==xy(P(x,y)→z(Q(x,z)∧~R(x,z))) ...量词分配率 ==xyz(P(x,y)→(Q(x,z)∧~R(x,z))) ...量词分配率 ==xyz(~P(x,y)∨(Q(x,z)∧~R(x,z))) ==xyz[(~P(x,y)∨Q(x,z))∧(~P(x,y)∨~R(x,z))]...分配律 ==x[(~P(x,f(x))∨Q(x,g(x)))∧(~P(x,f(x))∨~R(x,g(x))]...消取存在量词 从而谓词公式的子句集是 {~P(x,f(x))∨(Q(x,g(x),~P(x,f(x))∨~R(x,g(x))} 例3:设G=xyzuvw(P(x,y,z)∧~Q(u,v,w)),求其子句集 解:xyzuvw(P(x,y,z)∧~Q(u,v,w) ==yzuvw(P(a,y,z)∧~Q(u,v,w))......消去x=a(常数) ==yzvw(P(a,y,z)∧~Q(f(y,z),v,w))......消去u=f(y,z) ==yzv(P(a,y,z)∧~Q(f(y,z),v,g(y,z,v)))......消去w=g(y,z,v),得Skolem标准型 从而G的子句集是 {P(a,y,z),~Q(f(y,z),v,g(y,z,v))} 例4:将机器证明梯形的对角线与上下底构成的内错角相等给出逻辑描述,建立子句集合. 解: 设梯形顶点依次为a,b,c,d,定义谓词: T(x,y,u,v):表示xy为上底,uv为下底的梯形. P(x,y,u,v):表示xyuv E(x,y,z,u,v,w)表示∠xyz=∠uvw,问题的描述和相应的子句集为 xyuv[T(x,y,u,v)→P(x,y,u,v)]...梯形上下底平行 子句:~T(x,y,u,v)∨P(x,y,u,v) xyuv[P(x,y,u,v)→E(x,y,v,u,v,y)]...平行则内错交相等 子句: T(a,b,c,d)...已知 子句:T(a,b,c,d) E(a,b,d,c,d,b)...要证明的结论 子句:~E(a,b,d,c,d,b) 子句集S为 {~T(x,y,u,v)∨P(x,y,u,v),~P(x,y,u,v)∨E(x,y,v,u,v,y),T(a,b,c,d),~E(a,b,d,c,d,b)} 利用后面学到的替换和合一知识之后可给出证明过程。 3.1.4 Herbrand理论: 证明一个谓词公式的不可满足性是困难的,这是因为谓词中个体变量的论域D的任意性,以及解释的个数的无限性。例如: P(x):代表x是偶数。 若x的论域为D={2,4,6,8},则P是永真式,是可满足的; 若x的论域为D={1,3,5,7},则P是永假式,是不可满足的; 若x的论域为D={1,2,5,8},则P的真值与取论域D上的解释有关; 所以如果对一个具体的谓词公式能找到一个比较简单的特殊的论域,使得只要在这个论域上该公式是不可满足的,便能保证该公式在任一论域上也是不可满足的。所要建立的Herbrand域(简称H域)就具有这样的性质。 1 H域 设G是谓词公式,定义在论域D上,令H0是G中所出现的常量的集合。若G中没有常量出现,就任取常量a∈D,而规定H0={a}; Hi=Hi-1∪{所有形如f(t1,...tn)的元素}, 其中f(t1,...,tn)是出现于G中的任一函数符号,而t1...tn是Hi-1的元素,i=1,2,...。 规定H∞为G的H域。不难看出H域是直接依赖于G的最多只有可数个元素。 例1:S={P(a),~P(x)∨P(f(x))},依H域的定义有: H0={a} H1={a}∪{f(a)}={a,f(a)} H2={a,f(a)}∪{f(a),f(f(a))}={a,f(a),f(f(a))} …… H∞={a,f(a),f(f(a)),…} 例2:S={~P(z),P(x)∨~Q(y)} 依定义有 H0={a} a是论域D中的一个常量 H1=H0 H2=H1 …… H∞={a} 例3:S={P(f(x),a,g(y),b)} 依定义有 H0={a,b} H1={a,b}∪{f(a),f(b),g(a),g(b)}={a,b,f(a),f(b),g(a),g(b)} H2={a,b,f(a),f(b),g(a),g(b)}∪{f(a),f(b),f(f(a)),f(f(b)),f(g(a)),f(g(b)),g(a),g(b),g(f(a)),g(f(b)),g(g(a)),g(g(b))} ={a,b,f(a),f(b),g(a),g(b),f(f(a)),f(f(b)),f(g(a)),f(g(b)),g(f(a)),g(f(b)),g(g(a)),g(g(b))} …… H∞=H0∪H1∪H2∪…… 注意:如果在谓词或子句集中出现函数形如f(x,a)仍视为f(x,y)的形式,这时若H0={a,b},则H1中除有f(a,a),f(b,a)外,还出现f(a,b),f(b,b)。 为了讨论在H域上子句集S中各谓词的真值。令集合 A={所有形如P(t1,t2,...,tn)的元素} 称为子句集S(或公式G)的原子集。其中P(t1,t2,...,tn)是出现于S中的任一谓词符号,而t1,t2,...tn是S的H域的任意元素。 上述例1中的原子集为A={P(a),P(f(a)),P(f(f(a))),...} 上述例2中的原子集为A={P(a),Q(a)} 上述例3中的原子集为A={P(a,a,a,a),P(a,a,a,b),...} 例4:S={P(x)∨Q(x),R(f(y))} 依定义有H={a,f(a),f(f(a)),...} 原子集A={P(a),Q(a),R(a),P(f(a)),Q(f(a)),R(f(a)),P(f(f(a))),Q(f(f(a))),R(f(f(a))),...} 由于S中谓词个数是有限的,而H是可数集,必然原子集A也是可数集。 2 H解释 由子句集S建立H域、原子集A,从而讨论S在一般论域D上为真的解释I,就可依赖于在H域上的某个解释I*来实现。也就是子句集S在D上的不可满足问题转化成了在H上的不可满足问题。 下例说明由I寻求I*的过程 例1:S={P(x),Q(y,f(y,a))} 则有H={a,f(a,a),f(a,f(a,a)),f(f(a,a),a),f(f(a,a),f(a,a))...} A={P(a),Q(a,a),P(f(a,a)),Q(a,f(a,a)),Q(f(a,a),a),Q(f(a,a),f(a,a)),...} 设论域D={1,2},解释I作如下设定 a--f(1,1)--f(1,2)--f(2,1)--f(2,2) 2-- 1-------2-------2--------1--- P(1)--P(2)--Q(1,1)--Q(1,2)--Q(2,1)--Q(2,2) T------T------F--------T-------T-------F 于是有 ---x=1,y=1---x=1,y=2---x=2,y=1---x=2,y=2-- SI=P(1)∧Q(1,f(1,2))∧P(1)∧Q(2,f(2,1))∧P(2)∧Q(1,f(1,2))∧P(2)∧Q(2,f(2,2)) =T 可按下列方法选取相应的I*, a→2 f(a,a)→f(2,2)→1 f(a,f(a,a))→f(2,1)→2 f(f(a,a),a)→f(f(2,2),2)→f(1,2)→2 f(f(a,a),f(a,a))→f(1,1)→1 ... P(a)→P(2)→T Q(a,a)→Q(2,2)→F P(f(a,a))→P(1)→T Q(a,f(a,a))→Q(2,1)=T Q(f(a,a),a)→Q(1,2)=T Q(f(a,a),f(a,a))→Q(2,2)=F ... 于是得到相应的H域下的解释I*为 I*={P(a),~Q(a,a),P(f(a,a)),Q(a,f(a,a)),Q(f(a,a),a),~Q(f(a,a),f(a,a)),...} 显然 SI*=T 例2 求S={P(x)∨Q(x),R(f(y))}的H域、原子集A,I*解释。 仍然设D={1,2},解释I设定如下: f(1)--f(2)--P(1)--P(2)--Q(1)--Q(2)--R(1)--R(2) 2------2-----T-----F-----F-----T------F----T 于是由SI=P(1)∨Q(1)∧R(f(1))∧P(1)∨Q(1)∧R(f(2))∧P(2)∨Q(2)∧R(f(1))∧P(2)∨Q(2)∧R(f(2))=T 设a=1,则相应的解释为: I1*={P(a),~Q(a),~R(a),~P(f(a)),Q(f(a)),R(f(a)),...} SI1*=T 定理:设I是S的论域D上的解释,存在对应于I的H解释I*,使得若有SI=T,必有SI*=T 定理:子句集S是不可满足的,当且仅当在所有的S的H解释下为假。 定理:子句集S是不可满足的当且仅当对每个解释I下,至少有S的某个子句的某个基例为假。 3 语义树 讨论S的不可满足性问题,可将S的所有解释展现在一棵二叉树上(这是一个完全二叉树),但要依赖于S的H解释以及S的原子集A。 例:对子句集S={P(x)∨Q(y),~P(a),~Q(b)}画出相应的语义树 因为H={a,b} A={P(a),Q(a),P(b),Q(b)}从A出发可画出语义树(部分) 为了方便常以I(N)表示从根结点到结点N分支上所标记的所有文字的集合。例如I(N32)={P(a),Q(a),~P(b)},I(N42)={P(a),Q(a),P(b),~Q(b)} 例:对子句集S={~P(x)∨Q(x),P(f(y)),~Q(f(y))}画出相应的语义树。 因为H={a,f(a),f(f(a)),...} A={P(a),Q(a),P(f(a)),Q(f(a)),P(f(f(a))),Q(f(f(a))),...},从A出发可画出S的语义树,而且是无限树。 通过对S的完全语义树的观察,便可看到S的所有解释,这棵树的每个直到叶结点的分支都对应于S的一个解释。特别对有限树来说,若N是叶结点,那么I(N)便是S的一个解释。为讨论S的不可满足性,就可通过对语义树每个分支来计算S的真值而实现。 有时并不需要无限延伸某个分支方能确定在相应的解释下S取假值。例如某个分支延伸到结点N时,I(N)已使S的某个子句的某一基例为假,就无需对N再做延伸了。此时就说N是失败结点。 如果S的完全语义树的每个分支上都有一个失败结点,就说它是一个封闭树。即S的不可满足性=S的语义树是封闭语义树。 在上图中如果画出完全语义树的话,则每个分支上都有失败结点,它就是一个封闭树,从而证明S是不可满足的。 例如I(N42)={P(a),Q(a),P(f(a)),~Q(f(a))},它使得子句集S的一个子句~Q(f(y))的一个基例~Q(f(a))为假,从而子句集S为假,所以N42为失败结点。同样的方法可看出每个分支上都存在失败结点。 4 Herbrand定理 定理一:子句集S是不可满足的,当且仅当对应于S的完全语义树都是一棵有限的封闭语义树。 定理二:子句集S是不可满足的,当且仅当存在不可满足的有限基例集(即存在有限个失败结点)。 Herbrand定理给出了一阶逻辑的半可判定算法。其中的“半”字指的是有条件下的判定算法,即仅当被证定理是成立的,使用该算法方可得证。而当被证定理并不成立时,使用该算法得不出任何结果。说是算法,那指的是有限步内是可实现的,因为无论从有限的封闭树观点,还是从不可满足的有限基例集观点都是可判定的,因为这已经是有限的命题逻辑问题了。 使用Herbrand定理来证明定理或子句集S是不可满足的,或是寻找有限的封闭树,或是寻找有限的不可满足的基例集。 一个具体实现证明的方法是,对S的H域中的Hi做出基例集Si,即将Hi中的元素依次代入S中的各子句便构成Si,若Si是不可满足的必有S是不可满足的,或说相应的定理成立。若被证定理成立,必可在有限步内证明某个SN’是不可满足的。 3.1.5 谓词逻辑的归结原理(消解原理) 1 替换与合一 (回顾谓词公式、原子公式、文字、子句、项、个体的概念) 命题逻辑中的归结原理很简单,因为在命题逻辑中不含量词,而谓词逻辑中含有量词和个体变元,这样寻找互补文字对就变得较复杂。例: 子句C1=P(x)∨Q(x),子句C2=~P(a)∨R(y),如直接比较,似乎找不到互补文字,但如果使用替换办法,将C1中的x替换成a,则C1和C2的归结式为R(C1,C2)=Q(a)∨R(y)即可消去互补文字。 从而对谓词逻辑使用归结原理求解问题的步骤是: 求出谓词公式的Skolem标准型--谓词公式的子句集--利用替换和合一--再利用归结原理消去互补对----求解/证明结论。 替换(Substitution):形如{t1/x1,t2/x2,...tn/xn},ti是项,称为替换的分子,xi是互不相同的个体变元,称为替换分母(i=1,2,...n),且ti与xi不相同,xi与ti互不循环出现。ti/xi表示xi用ti替换。若ti都是不含变元的项(基项),该替换称为基替换;没有元素的替换称为空替换,记作ε,他表示不做替换。 例:{a/x,g(y)/y,f(g(b))/z}就是一个替换(但不是基替换),而{y/x,f(x)/y}就不是一个替换,因为出现了x,y的循环替换。 定义:若E是一个谓词公式,θ={t1/x1,t2/x2,...tn/xn}是一个替换,对E施行θ替换之后所得的结果记为Eθ,称为E在θ下的例(instance) 例:设谓词公式G=P(x,y,z),替换θ={a/x,f(b)/y,c/z},则Gθ=P(a,f(b),c) 替换的乘积(复合替换):设θ={t1/x1,...,tn/xn},λ={u1/y1,...,um/ym}是两个替换,则将集合{t1λ/x1,...,tnλ/xn,u1/y1,...,um/ym}中凡符合下列条件的元素删除 (1) tiλ/xi......当tiλ=xi时 (2) ui/yi........当yi∈{x1,x2,...xn} 如此得到的集合仍然是一个替换,该替换称为θ与λ的复合或乘积,记为θ·λ 例: θ={f(y)/x,z/y},λ={a/x,b/y,y/z}, 于是{f(y)λ/x,zλ/y,a/x,b/y,y/z}={f(b)/x,y/y,a/x,b/y,y/z}, 根据替换乘积的定义,删除若干项之后得 θ·λ={f(b)/x,y/z} 替换的复合运算满足结合律,但不满足交换律,即有: (θ·λ) ·u=θ·(λ·u),θ·λ≠λ·θ,λ·ε=λ 例: 若谓词公式E=P(x,f(y),z),置换s1={f(x,y)/z,z/w},s2={a/x,b/y,w/z},求(Es1)s2,E(s1·s2),E(s2·s1) 解: Es1=P(x,f(y),f(x,y)) (Es1)s2=P(a,f(b),f(a,b)) s1·s2={f(a,b)/z,w/w,a/x,b/y,w/z}={f(a,b)/z,a/x,b/y} s2·s1={a/x,b/y,z/z,f(x,y)/z,z/w}={a/x,b/y,z/w} E(s1·s2)=P(a,f(b),f(a,b)) E(s2·s1)=P(a,f(b),z) 可见(Es1)s2=E(s1·s2)≠E(s2·s1) 2 合一置换(替换) 定义1:设S={F1,F2,...,Fn}是一个子句集(F1,F2,...Fn是文字的析取),若存在一个替换θ,可使F1θ=F2θ=...Fnθ,则称θ为S的一个合一(Unifier),并称S为可合一的。一个谓词公式的合一不唯一。 定义2:设δ是谓词公式子句集S的一个合一,如果对S的任何一个合一θ,都存在一个替换λ,使得θ=δ·λ则称δ是子句集的最一般合一,简称MGU(Most General Unifier)。 例:设子句集S={P(u,y,g(y)),P(x,f(u),z)},S有一个最一般合一MGU, δ={u/x,f(u)/y,g(f(u))/z},对S的任一合一,例如θ={a/x,f(a)/y,g(f(a))/z,a/u},存在一个替换λ={a/u},使得θ=δ·λ 求MGU的目的是使子句集中的子句中的文字形式结构完全一致,从而得到消取互补文字的目的。 差异集:设S是一个非空的具有相同谓词名的原子公式集,从S中各公式的左边第一项开始,同时向右比较,直到发现第一个不都相同的项为止,用这些项的差异部分组成一个集合,这个集合就是原子公式子句集的一个差异集。例: S={P(x,y,z),P(x,f(a),h(b))},则S的差异集D1={y,f(a)},D2={z,h(b)} 求子句集S的最一般合一(MGU)的算法,即合一算法(Unification Algorithm): ①置k=0,Sk=S,δk=ε; ②若Sk是单元素集,则算法停止,MGU=δk ③求Sk的差异集Dk; ④若Dk中存在元素xk和tk,其中xk是变元,其中tk是项且xk不在tk中出现,则置Sk+1=Sk·{tk/xk},δk+1=δk·{tk/xk},k=k+1,转步骤(2) ⑤算法停止,S的MGU不存在(若S是可合一的,算法总是在步②停止) 例:求公式集S={P(a,x,f(g(y)),P(z,h(z,u),f(u))}的MGU。 解: k=0;S0=S;δ0=ε;S0不是单元素集,求得差异集D0={a/z},其中z是变元,a是项,且z不在a中出现。k=k+1=1 有δ1=δ0·{a/z}=ε·{a/z}={a/z}, S1=S0·{a/z}={P(a,x,f(g(y)),P(a,h(a,u),f(u))},S1不是单元素集, 求得差异集D1={x,h(a,u)},k=k+1=2;δ2=δ1·{h(a,u)/x}={a/z,h(a,u)/x}, S2=S1·{h(a,u)/x}={P(a,h(a,u),f(g(y)),P(a,h(a,u),f(u))}, S2不是单元素集,求得差异集D2={g(y),u},k=k+1=3 δ3=δ2·{g(y)/u}={a/z,h(a,u)/x}·{g(y)/u}={a/z,h(a,g(y))/x,g(y)/u} S3=S2·{g(y)/u}={P(a,h(a,g(y)),f(g(y)))}是单元素集。 根据求MGU算法,MGU=δ3={a/z,h(a,g(y))/x,g(y)/u} 3 谓词逻辑中的归结式 谓词逻辑下求两个子句的归结式,和命题逻辑一样也是消去互补对,但需考虑变量的合一与置换。设S={C1,C2}C1,C2是子句集中的子句,L1、L2分别是C1,C2中的文字,并且L1和~L2有最一般合一δ,则子句{C1δ-L1δ}∪{C2δ-L2δ}称为C1、C2的归结式。C1,C2称为归结式的亲本子句,L1、L2称为归结文字。 例:S={C1,C2}=S={P(x)∨Q(x),~P(a)∨R(y)},求C1,C2的归结式。 L1=P(x),L2=~P(a), 则L1与L2的MGU δ={a/x}, 则{C1δ-L1δ}∪{C2δ-L2δ}={P(a)∨Q(a)}-{P(a)}∪{~P(a)∨R(y)}-{~P(a)}={Q(a)∨R(y)} 即R(C1,C2)=Q(a)∨R(y).........δ={a/x} 例:C1={P(x,y)~Q(a)},C2={Q(x)∨R(y)}求C1、C2的归结式。 在对子句进行归结之前,可先在子句内部进行化简。如子句C=P(x)∨P(f(y)),令置换δ={f(y)/x},则Cδ=P(f(y))∨~Q(f(y)),Cδ称为C的因子。 R(C1,C2)=R(C1δ,C2)=R(C1,C2δ)=R(C1δ,C2δ) 定理:谓词逻辑中的归结式是它的亲本子句的逻辑结果,即: C1∧C2=(C1δ-{L1δ})∨(C2δ-{L2δ}),这就是谓词逻辑的归结原理. 4 利用归结原理证明/求解 例1:求证:G是A1和A2的逻辑结果 A1: x(P(x)→(Q(x)∧R(x))) A2: x(P(x)∧S(x)) G: x(S(x)∧R(x)) 证:①~P(x)∨Q(x)...从A1变换 ②~P(y)∨R(y)...从A1变换 ③P(a) ④S(a) ⑤~S(z)∨~R(z)...结论的否定 ⑥R(a)......②③归结{a/y} ⑦~R(a)......④⑤归结{a/z} ⑧□......⑥⑦归结 得证. 例2:设已知: (1)能阅读者是识字的; (2)海豚不识字; (3)有些海豚是聪明的; 求证:有些聪明者并不能阅读. 证:定义如下命题: R(x):x能阅读; L(x):x识字; I(x):x是聪明的; D(x):x是海豚; 把已知条件及求证结论翻译成谓词公式为 x(R(x)→L(x))...已知 x(D(x)→~L(x))...已知 x(D(x)∧I(x))...已知 x(I(x)∧~R(x))...求证结论 将已知条件,求证结论的反化成子句集 ①~R(x)∨L(x) ②~D(y)∨~L(y) ③D(a) ④I(a) ⑤~I(z)∨R(z) ⑥~L(a)......2,3归结{a/y} ⑦~R(a)......1,6归结{a/x} ⑧R(a)......4,5归结{a/z} ⑨□......7,8归结 得证. 例3:求解问题,已知: 如果x和y是同班同学,则x的老师也是y的老师; 王先生是小李的老师; 小李和小张是同班同学; 问小张的老师是谁? 解:定义谓词T(x,y):x是y的老师;C(x,y):x与y是同班同学;则已知可表示成如下的谓词公式 xyz((C(x,y)∧T(z,x))→Li是常元 C(Li,Zhang) xT(x,zhang)......(先证明zhang的老师是存在的) 以上谓词公式及结论的反化成子句集如下: ①~C(x,y)∨~T(z,x)∨T(z,y) ②T(wang,Li) ③C(Li,Zhang) ④~T(u,zhang) ⑤~C(Li,y)∨T(wang,y)......1,2归结,{wang/z,Li/x} ⑥~C(Li,zhang)......4,5归结,{wang/u,zhang/y} ⑦□......3,6归结 说明zhang的老师存在. 为了求解用一个重言式代替④ ④~T(u,zhang)∨T(u,zhang)......用重言式代替结论的否定,重言式恒为真 ⑤~C(Li,y)∨T(wang,y)......1,2归结,{wang/z,Li/x} ⑥~C(Li,zhang)∨T(wang,zhang)......4,5归结,{wang/u,zhang/y} ⑦T(wang,zhang)......3,6归结 得结果:张的老师是王先生. 也可用辅助谓词ANS(u) ④~T(u,zhang)∨ANS(u)......用辅助谓词ANS(u) ⑤~C(Li,y)∨T(wang,y)......1,2归结,{wang/z,Li/x} ⑥~C(Li,zhang)∨ANS(wang)......4,5归结,{wang/u,zhang/y} ⑦□∨ANS(wang)......3,6归结 得结果:张的老师是王先生. 3.1.6 归结过程的控制策略 1.删除策略 概念: 设C1,C2是两个子句,若存在替换θ,使得C1θ包含在C2中,则称子句C1类含C2。如: P(x)类含P(a)∨Q(y),取θ={a/x},或者说P(x)把P(a)∨Q(y)归类 P(a,x)∨P(y,b)类含P(a,b),取θ={b/x,a/y} 纯文字:在子句集中无补的文字。如下列子句集 {P(x)∨Q(x,y)∨R(x),~P(a)∨Q(u,v)}中的文字R(x)就是一个纯文字。 在归结的过程中删除以下子句 含有纯文字的子句; 含有永真式的子句; 子句集中被别的子句类含的子句; 删除含有纯文字的子句,是因为在归结过程中纯文字永远不会消去,因而用包含它的子句进行归结不可能得到空子句。删除永真式是因为永真式对子句集的不可满足性不起任何作用。删除被类含的子句是因为被类含的子句是类含它的子句的逻辑蕴含,故它是多余的。如P(a,x)∨P(y,b)类含P(a,b),则可将P(a,b)删除。 例:利用删除策略对下列子句集进行归结 (1)P∨Q...已知 (2)~P∨Q...已知 (3)P∨~Q...已知 (4)~P∨~Q...已知 (5)Q...(1)(2)归结,此时可将子句(1)(2)删除,因它们被子句(5)类含,此时归结只在3,4,5之间进行 (6)~Q...(3)(4)归结 (7)□...(5)(6)归结 例:利用删除策略对下列子句集进行归结 (1)P(x)∨Q(x)∨~R(x)...已知 (2)~Q(a)...已知 (3)~R(a)∨Q(a)...已知 (4)P(y)...已知 (5)~P(z)∨R(z)...已知,子句(4)类含(1),所以将子句(1)删除 (6)~R(a)...(2)(3)归结,此时子句(3)可删除,因为它被(6)类含 (7)~P(a)...(5)(6)归结{a/z},此时子句(5)可删除,因为它被(7)类含 (8)□...(4)(7)归结{a/y} 删除策略是及早删除无用子句,缩小搜索规模.删除策略是完备的,即对不可满足的子句集,使用删除策略进行归结必能导出空子句. 2.语义归结 一种语义归结是把子句S分成两部分,约定每部分内的子句间不允许做归结。还引入了文字次序,约定归结时其中的一个子句的被归结文字只能是该子句中“最大”的文字 例:子句集S={~P∨~Q∨R,P∨R,Q∨R,~R} 先规定S中文字的出现顺序如依次为P,Q,R,再选取S的一个解释如令 I={~P,~Q,~R} 用它将S分成两部分。在解释I下为假的子句放入S1中,在解释I下为线中,于是有: S1={P∨R,Q∨R} S2={~P∨~Q∨R,~R} 规定在Si内部的子句不允许归结,S1与S2子句间的归结必须是S1中的最大文字方可进行。这样所得的归结式仍按解释I放入S1或S2中。 归结过程: (1)~P∨~Q∨R................按顺序排列,属于S2 (2)P∨R................按顺序排列,属于S1 (3)Q∨R................按顺序排列,属于S1 (4)~R................按顺序排列,属于S2 (5)~Q∨R.............(2)和(1)归结,因为选取S1最大文字方向 (6)~P∨R.............(3)和(1)归结,因为选取S1最大文字方向 (7)R.............(2)和(6)归结 (8)□............(7)和(4)归结 明显地减少了归结次数,阻止了(1)与(4)归结(因为它们是S2内部子句),也阻止了(2)(4)归结(因为不是最大文字方向) 另一种语义归结称为支持集策略 对子句集S每次归结时至少要有一个是要证明的目标公式否定的子句或其后裔.这里的要证明的目标公式的否定形式所形成的子句集即为支持集T,很显然S-T是可满足的.所以也可这样理解支持集策略:每次归结时,至少有一个子句来自支持集T或由T导出的归结式. 例:子句集合S={~I(x)∨R(x),I(a),~R(y)∨~L(y),L(a)},其中I(x)∧~R(x)是要证明的结论,其否定形式是子句~I(x)∨R(x).利用支持集策略归结如下: (1)~I(x)∨R(x)..............支持集T (2)I(a) (3)R(y)∨~L(y) (4)L(a) (5)R(a)............1,2归结{a/x} (6)~L(a)...........3,5归结{a/y} (7)□...............(4)(6)归结 支持集策略是完备的. 3.线性归结策略 在归结过程中,除第一次归结可用给定的子句集S中子句(该子句称为顶子句)外,其后各次归结则至少要有一个亲本子句是上次归结的结果.线性归结可用一个归结演绎树加以表示,例如上例中的归结过程: 线.输入归结策略 每次参加归结的两个亲本子句,必须至少有一个子句是初始子句集S中的子句。输入归结策略是不完备的。例如子句集S={P∨Q,~P∨Q,P∨~Q,~P∨~Q}是不可满足的,但用输入归结策略不能导出空子句 5.单元归结策略 每次归结都有一个子句是单元(只含一个文字即原子或其否定)子句或单元的因子时的归结称作单元归结。 单元归结也是不完备的。 3.2不确定性推理概述 3..1 不确定性推理 知识库是人工智能的核心,而知识库中的知识既有规律性的一般原理,又有大量的不完全的专家知识,即知识带有模糊性、随机性、不可靠或不知道不确定因素。世界上几乎没有什么事情是完全确定的。不确定性推理即是通过某种推理得到问题的精确判断。 (1)不确定性问题的代数模型 一个问题的代数模型由论域、运算和公理组成。建立不确定性问题模型必须说明不确定知识的表示、计算、与语义解释。 表示问题:指用什么方法描述不确定性,通常有数值和非数值的语义表示方法。数值表示便于计算,比较,再考虑到定性的非数值描述才能较好的解决不确定性问题。例如对规则A-B(即A真能推导B真)和命题(或称证据、事实)A,分别用f(B,A)来表示不确定性度量。 计算问题:指不确定性的传播和更新,也即获得新的信息的过程。包括: ①已知C(A),A-B,f(B,A),如何计算C(B) ②证据A的原度量值为C1(A),又得C2(A),如何确定C(A) ③如何由C(A1)和C(A2)来计算C(A1∧A2),C(A1∨A2)等。 一般初始命题/规则的不确定性度量常常由有关领域的专家主观确定。 语义问题:是指上述表示和计算的含义是什么?即对它们进行解释,概率方法可以较好地回答这个问题,例如f(B,A)可理解为前提A为真时对结论B为真的一种影响程度,C(A)可理解为A为真的程度。特别关心的是f(B,A)的值是: ①A真则B真,这时f(B,A)=? ②A真则B假,这时f(B,A)=? ③A对B没有影响时,这时f(B,A)=? 对C(A)关心的值是 ①A真时,C(A)=? ②A假时,C(A)=? ③对A一无所知时,C(A)=? (2)不确定推理方法的分类 不确定推理方法在人工智能系统中通常是不够严谨的,但尚能解决某些实际问题,符合人类专家的直觉,在概率上也可给出某种解释。 不确定性推理模型没有一个统一的模型,种类不计其数,其中比较著名的有: Shortliffe在1975年结合医疗专家系统MYCIN建立的确定性理论 Duda在1976年结合探矿专家系统PROSPECTOR建立的主观Bayes推理 Dempster Shafer在1976年提出的证据理论 Zadeh在1978年提出的可能性理论,1983年提出的模糊逻辑和逻辑推理 Nilsson在1986年提出的概率逻辑 Pearl在1986年提出的信任网络 3..2不确定性推理方法 在以产生式作为知识表示的MYCIN系统中,第一次使用了不确定推理方法,给出了可信度作为不确定性的度量。 1.规则的不确定性度量 规则以A-B表示,其中前提A可以是一些命题的合取,引入可信度CF(B,A)作为规则A-B的不确定性度量。其中引入P(B)表示结论B为真的概率,P(BA)表示在规则A-B,证据A为真的作用下结论B为真的概率。则可信度 CF(B,A)表示证据A为真时,相对于P(~B)=1-P(B)来说A对B为真的支持程度(当CF(B,A)≥0),或相对于P(B)来说A对B为真的不支持程度(当CF(B,A)<0)。以上定义保证了-1≤CF(B,A)≤1。 当P(B,A)-P(B)相同时,P(B)小的CF小,P(B)大的CF大。 可以看出规则的可信度CF(B,A)的几个特殊值: 前提A为真,结论B必线,故由上式知CF(B,A)=1; 前提A与结论B无关时,由于P(BA)=P(B),故由上式知CF(B,A)=0; 前提A真结论B必假的情形,由于P(B,A)=0,故由上式知CF(B,A)=-1; 显然CF(B,A)≥0表示前提A真支持B线表示前提A真不支持B真。 CF(B,A)的定义借用了概率,但它本身并不是概率,因为CF(B,A)可取负值(概率=0),另外CF(B,A)+CF(B,~A)不必为1(而P(A)+P(~A)=1),甚至可能为0。 值得注意的是,在实际的应用中CF(B,A)的值是由专家根据经验知识主观确定的,并不是由P(B)和P(B,A)计算出来的。 2.证据的不确定性度量 证据A的不确定性也可以用CF(A)表示,同样规定-1≤CF(A)≤1,几个特殊值规定为: A肯定为线; A肯定为假时,CF(A)=-1; 对证据A一无所知时,CF(A)=0; CF(A)0,则CF(A)表示证据A为真的程度; CF(A)0, 则CF(A)表示证据A为假的程度; 同样要注意的是:初始证据的CF值由专家主观提供,其它证据的CF值由规则的CF值和初始证据的CF值经过推理求得。 3.推理计算 (1)已知CF(A),规则A-B,CF(B,A)求CF(B)。 推理计算:CF(B)=CF(B,A)·max{0,CF(A)} --------------------公式① (2)规定: CF(~A)=-CF(A) ----------------------------------公式② CF(A1∧A2)=min{CF(A1),CF(A2)} ------------------公式③ CF(A1∨A2)=max{CF(A1),CF(A2)} ------------------公式④ (3)由规则A1-B求得CF(B),又使用规则A2-B,如何更新CF(B)。或者说已知CF(A1),CF(A2)以及CF(B,A1)和CF(B,A2)来寻求合成的CF(B)。 计算方法: 由规则A1-B,CF(B,A1),CF(A1),根据(1)求得CF1(B)=CF(B,A1)·max{0,CF(A1)} 由规则A2-B,CF(B,A2),CF(A2),根据(1)求得CF2(B)=CF(B,A2)·max{0,CF(A2)} 则最后更新的CF(B)可由下式求得: ---------------------公式⑤ CF(B)的更新计算,也可以这样理解:已知CF(A),A-B,CF(B,A),而B原来的可信度为CF(B),来求B的可信度更新值CF(BA)。这时上面的计算公式可写成: 当CF(A)=1(证据A肯定为真),根据公式①,CF(B)=CF(B,A)·max{0,CF(A)}=CF(B,A)·max{0,1}=CF(B,A),B原来的可信度为CF(B),根据公式⑤得到最后的B的可信度: ---------------公式⑥ 当CF(A)1(证据A也是不确定的),这时CF(BA)必然比CF(A)=1时的CF(BA)来的小。若CF(A)0,可以CF(B,A)·CF(A)作为对规则A→B的可信度,而CF(BA)的计算仍可用CF=1时的公式⑥。 当CF(A)0时,规则A→B可不使用,像医疗专家系统MYCIN规定证据A的可信度CF(A)=0.2,就认为规则A→B不可使用。 举例:已知一组规则和证据(事实): R1:A1-B1,CF(B1,A1)=0.8 R2:A2-B1,CF(B1,A2)=0.5 R3:B1∧A3-B2,CF(B2,B1∧A3)=0.8 初始证据A1,A2,A3,并且CF(A1)=CF(A2)=CF(A3)=1, 并且初始时对B1,B2一无所知。规则R1,R2,R3作用下求证据B1,B2的可信度更新值CF(B1),CF(B2)。 解:根据规则R1,由公式⑥得:CF(B1A1)=0+0.8*(1-0)=0.8; 根据规则R2,由公式⑥得:CF(B1A1A2)=0.8+0.5*(1-0.8)=0.9 所以CF(B1)的最后更新值为0.9 下面求B2的最后更新值: 根据规则R3。CF(B1∧A3)= min{CF(B1),CF(A3)}=min{0.9,1}=0.9 而规则B1∧A3-B2的前提CF(B1∧A3)≠1,根据公式6的说明求CF(B2,B1∧A3)·CF(B1∧A3)=0.8*0.9=0.72 再根据公式6求得CF(B2B1∧A3)=0+0.72(1-0)=0.72 所以CF(B2)的最后更新值为0.72 3.主观Bayes方法 在PROSPECTOR探矿专家系统中,采用了主观Bayes方法来度量不确定性。引入两个数值(LS,LN)来作度量,LS表现规则A-B成立的充分性,LN表现规则A-B成立的必要性。也就是说LS表现规则A-B,A为真时对B为真的支持程度,LN表现了A不为真(~A)对B为线.对规则的不确定性度量 对规则A-B的不确定性CF(B,A)以(LS,LN)来描述。 ……(公式3.3.1) 分析LS、LN的意义。建立几率函数 ,……(公式3.3.2)表示事实X为真的概率与X为假的概率之比,显然P(X)的越大O(X)也加大,而且: P(X)=0,O(X)=0 P(X)=1,O(X)=∞ 根据公式3.3.1和公式3.3.2可以推导出: O(BA)=LS·O(B)…………………………(公式3.3.3)也即: O(B~A)=LN·O(B)…………………………(公式3.3.4)也即: 由这两个公式,对于规则A-B,LS表现A为真时对B为真的支持程度,LN表现了A为假(~A)时对B为真的支持程度。 几个特殊值: 根据LS、LN的定义可知,LS≥0,LN≥0,而且LS和LN不是独立取值,只能出现: LS1,LN1 或LS1,LN1 或LS=LN=1 但不能两者同时1或同时1 在实际系统中,LS、LN的值是由专家凭经验给出的,而不依照LS、LN的定义来计算。 例如有规则A-B,并且给出 LS=20,LN=1则表示A线则表示~A支持B线.证据的不确定性度量 在主观Bayes推理中就以O(A)或P(A)表示证据A的不确定性,转换公式是: 3.推理计算 (1)当证据A必出现时即P(A)=1,可直接使用 O(BA)=LS·O(B) O(B~A)=LN·O(B) 求得使用规则A-B后,O(B)的更新值O(BA)和O(B~A),若需要以概率表示,再由 计算出P(BA)和P(B~A)。 (2)当A是不确定的即P(A)≠1,需作如下考虑 设证据A是与A有关的所有观察(可以认为A-A),对规则A-B来说Duda在1976给出公式: P(BA)=P(BA)·P(AA)+P(B~A)·P(~AA) 现在是当P(AA)、A-B(LS,LN)以及P(B)已知时,如何更新P(B)或说如何求P(BA) 当P(AA)=1时,证据A必然为真,可推导处: 当P(AA)=0时,证据A必然为假,同样的方法可推导出: 当P(AA)=P(A)时,表示A与A没有关系,根据公式P(BA)=P(BA)·P(AA)+P(B~A)·P(~AA)得 P(BA)=P(BA)·P(A)+P(B~A)·P(~A)=P(BA)+P(B·~A)=P(B)………………概率公式 这样可确定P(AA)为1,0,P(A)时,相应的P(BA)值。其它情况的P(BA)的值可从线必然发生后,看B的概率变化,已知B的先验概率为0.03,而规则 R1:A1-B LS=20 LN=1 R2: A2-B LS =300 LN=1 R3: A3-B LS=75 LN=1 R4: A4-B LS=4 LN=1 解:由规则R1,P(B)=0.03,便得: 即执行规则R1后,证据B为线,计算得: 即执行规则R2后,证据B为线之后证据B的概率的变化可按同样方法计算,读者可自行完成。 (2)证据A必然发生(即为线。使用下列规则R1,R2之后,计算P(B2A)。 R1:A-B1 LS=20 LN=1 R2: B1-B2 LS=300 LN=0.0001 解:在本题中,关键是使用规则R2时,证据B1不是必然为真,即是不确定的,这时需用插值法: ①由于A必然发生,所以根据规则R1有: ②设P(B1A)=1(B1为线.01 于是可作线. 证据理论 Dempster和Shafer提出的证据理论,可用来处理由不知道所引起的不确定性。采用信任函数而不是概率作为不确定性度量,通过对一些事件的概率加以约束来建立信任函数而不必说明精确的难于获得的概率,当这种约束限制为严格的

  “原创力文档”前称为“文档投稿赚钱网”,本网站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有【成交的100%(原创)】

本文链接:http://furymagazine.com/yuyishu/105.html