人工智能技术导论.pptx

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式ABCD,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式ABCD,第二级,第三级,第四级,第五级,人工智能技术导论（第二版),廉师友,编著,ycduan,人工智能技术导论,第1页,参考书,人工智能,马少平、朱小燕编著，清华大学出版社,人工智能及其应用,蔡自兴、徐光祐编著，清华大学出版社,Artificial Intelligence A New Synthesis,(人工智能)Nils J.Nilsson,人工智能技术导论,第2页,第一章 人工智能概述,人工智能概念,人工智能研究途经与方法,人工智能分工领域,人工智能基本技术,人工智能发展概括,人工智能技术导论,第3页,什么是人工智能,人工智能(,Artificial Intelligence,)是指由计算机实现人造智能。作为一门学科，人工智能可定义为：人工智能是一门研究怎样结构智能机器（智能计算机）或智能系统，使它能模拟、延伸、扩展人类智能学科,人工智能是一门交叉边缘学科，与人工智能相关学科有：计算机科学、数学、语言学、神经生理学、神经心理学、脑科学、认知科学、逻辑学、控制论等,人工智能技术导论,第4页,什么是人智能,智能是人脑属性和产物。智能含有主要特征：,A、含有感知能力。经过视觉、听觉、触觉、味觉和嗅觉感知外部世界。,B、含有记忆与思维能力。记忆能存放由感知器官感知到外部信息以及由思维所产生知识。思维用于对记忆信息进行处理。思维可分为逻辑思维和形象思维。,C、含有学习能力及自适应能力。,D、含有行为能力。,发觉规律 应用规律 分析问题 处理问题,图灵测试,汉字屋子问题（约翰希尔勒）,人工智能技术导论,第5页,为何要研究人工智能,现有计算机系统不足。,智能低下、缺乏自学习、自适应、自优化能力。,人类智能不足。,学习能力因人而异、学习速度慢、效率低。,信息化社会迫切要求。,人工智能技术导论,第6页,人工智能目标,近期目标：使现有电子数字计算机能模拟人类部分智能行为。,远期目标：制造智能计算机，使计算机含有看、听、说等感知和交互能力、含有联想、推理、了解、学习等高级思维能力，还要有分析问题、处理问题和创造创造能力。,深蓝（32CPU，200万次/秒，200万个棋局）,人工智能技术导论,第7页,人工智能表现形式,智能软件,智能设备,智能网络,智能计算机,智能机器人,智能体(Agent)(艾真体),人工智能技术导论,第8页,人工智能研究路径与方法,结构模拟（神经计算、生理学派、连接主义）,模拟人脑神经网络结构实现智能。主要特征：,1、经过神经元之间并行协同作用实现信息处理，含有并行性、动态性、全局性。,2、经过神经元间分布式物理联接存放信息。联想记忆、容错性。,3、经过神经元间连接强度动态调整实现自学习和自适应功效。,4、善于模拟人类,形象思维,过程。,人工智能技术导论,第9页,人工智能研究路径与方法,功效模拟（符号主义、心理学派、逻辑学派）,以人脑心理模型为基础，将问题或知识表示成某种逻辑网络，采取符号推演方法，实现搜索、推理和学习等功效。主要特征：,1、立足于逻辑运算和符号操作，适合于模拟人,逻辑思维,过程。,2、知识用显式符号表示，轻易表示人心理模型。,3、现有数字计算机能够方便地实现高速符号处理。,4、能与传统符号数据库进行链接，易于模块化。,5、以知识为基础。,人工智能技术导论,第10页,人工智能研究路径与方法,行为模拟（行为主义、进化主义、控制论学派）,基于感知-行为模型研究路径和方法。,模拟人在控制过程中智能活动和行为特征：自寻优、自适应、自组织、自学习。,强调智能系统与环境交互，认为智能取决于感知和行动,智能行为能够不要知识。,智能只有放在环境中才是真正智能，智能高低表达在对环境适应性上,Brooks，机器虫,人工智能技术导论,第11页,人工智能分支领域,基于脑功效模拟领域划分,1、机器感知（信息输入）。使计算机含有类似于人感知能力，能经过“感知”直接从外界获取信息，是对人感知模拟及延伸。机器视觉、机器听觉。相关学科：模式识别（语音识别、图像识别）。,信息-电信号序列-预处理-提取特征-模式匹配,2、机器联想。基于内容联想，与详细存放位置无关。联想存放技术。,3、机器推理。又称为计算机推理、自动推理，是人工智能关键课题之一。,推理：从一些已知判断（前提）推出一个新判断（结论）思维过程。,演绎推理,、归纳推理、类比推理,确定性推理、,不确定性推理,基于概率逻辑或然推理(随机性)、基于含糊逻辑似然推理(含糊性),串行推理、并行推理,人工智能技术导论,第12页,人工智能分支领域,4、机器学习。使机器自己获取知识。,对人类已经有知识获取、对客观规律发觉、对本身行为修正。,机器学习分为：机械学习、指导学习、解释学习、类比学习、示例学习、发觉学习等。这些属于符号学习。另外还有神经网络学习。,5、机器了解。图形了解（物景分析）、自然语言了解。了解是感知延伸和深化。,6、机器行为（机器人行动规划）。,智能机器人关键技术，反应了机器人智能水平,处理问题依靠规划功效确定行动步骤和动作序列,任务：在一个特定工作区域中自动生成从初始状态到目标状态动作序列、运动路径和轨迹控制程序,人工智能技术导论,第13页,人工智能分支领域,基于研究路径和实现技术领域划分,1、符号智能,以符号知识为基础，经过符号推理进行问题求解,知识工程(知识获取、知识表示、知识管理、知识利用、知识库系统)、符号处理,2、计算智能,以数据为基础，经过数值计算进行问题求解,人工神经网络、进化计算(遗传算法、遗传程序设计、进化规划、进化策略)、含糊技术、人工生命,人工智能技术导论,第14页,人工智能分支领域,基于应用领域领域划分,1、难题求解,难题概念,路径规划、组合优化、天气预报、股市分析、市场预测、机器博弈,NP(Nondeterministic Polynomial)和NPC(Nondeterministic Polynomial Complete)问题,难题求解技术能促进人工智能其它领域发展,2、自动定理证实,自然演绎法、判定法、定例证实器、计算机辅助证实,四色问题(1976.6,K.Appeel)。,3、自动程序设计,超级编译系统,自动程序综合和自动程序验证。,人工智能技术导论,第15页,人工智能分支领域,4、自动翻译。机器翻译。自然语言了解。,一边站着一个人,他想起来了,5、智能控制,1965，KS.FU(傅京孙)提出将启发式推理规则用于学习控制系统,6、智能管理。人工智能与管理科学、系统工程和计算机技术结合。,7、智能决议。人工智能应用于决议支持系统。,8、智能通讯。在通讯各个步骤和层次上实现智能化。如网控、转接、信息转换等。使通讯网随时运行于最正确状态。,9、智能仿真。仿真是在三种类型知识-描述性知识、目标性知识和处理知识基础上产生另一个形式知识-结论性知识。,10、智能CAD。人工智能应用于CAD设计自动化、智能交互、智能图形学、自动数据采集方面。,11、智能CAI。人工智能应用于CAI：自动生成各种问题与练习、自动选择与调整教学内容和进度、自动生成答案、自然语言了解能力、不停改进教学策略。,人工智能技术导论,第16页,人工智能分支领域,基于应用系统领域划分,1、教授系统。基于人类教授知识程序系统。能模拟教授思维方式。,2、知识库系统。,3、智能数据库系统。传统数据库系统+人工智能。,4、智能机器人系统。具备感知、思维、人-机通讯和运动能力。,人工智能技术导论,第17页,人工智能分支领域,基于计算机系统结构领域划分,1、智能操作系统。并行性、分布性和智能性。,2、智能多媒体系统。人工智能与多媒体技术有机结合。,3、智能计算机系统。,4、智能网络系统。含糊和神经网络技术应用于网络业务量预测和控制、资源动态分配、动态路由选择等方面。,人工智能技术导论,第18页,人工智能分支领域,基于实现工具与环境领域划分,1、智能软件工具。人工智能程序设计语言，如表处理语言LISP、逻辑程序设计语言PROLOG、面向对象程序设计语言Smalltalk等。知识表示语言FRL、OPS5。教授系统工具、知识工程工具等。,2、智能硬件平台。直接支持智能系统开发和运行机器硬件。,人工智能技术导论,第19页,人工智能分支领域,基于体系结构领域划分,集中式人工智能（个体智能）,分布式人工智能（群体智能）,个体智能组合或叠加,DPS（分布式问题求解），自顶向下,MAS（多智能体系统），自底向上,人工智能技术导论,第20页,人工智能基本技术,推理技术。推理是智能关键。推理以逻辑为基础。基于谓词逻辑自然演绎推理和归结反演推理。基于非标准逻辑如多值逻辑、模态逻辑、时态逻辑、含糊逻辑、非单调逻辑推理。,搜索技术。人工智能基本技术。许多智能活动过程，都能够看作或抽象为一个“问题求解”过程。“问题求解”就是在问题空间中进行搜索过程。盲目搜索、启发式搜索。神经网络搜索。,知识表示与知识库技术。知识表示是指知识在计算机中表示方式。知识表示要符合知识逻辑结构和物理结构，并适合于计算机存放和处理。知识库由知识组成。知识组织、管理、维护和优化。,人工智能技术导论,第21页,人工智能基本技术,归纳技术。机器自动提取概念、获取知识、发觉规律技术。归纳技术与知识获取和机器学习亲密相关。基于符号处理归纳和基于神经网络归纳。数据库知识发觉（KDD,Knowledge Discovery in Database)和数据挖掘(Data Mining)技术。,联想技术。联想记忆，联想存放。,人工智能技术导论,第22页,人工智能发展概况,孕育期（1956年之前）,1、公元前，Aristotle提出形式逻辑一些主要定律，三段论至今仍是演绎推理基本依据。,2、培根（1561-1626）曾系统地提出了归纳法。提出“知识就是力量”,3、德国数学家Leibniz（1646-1716）提出了万能符号和推理计算思想，为数理逻辑产生和发展奠定了基础。,4、英国逻辑学家Boole（1815-1864）创建了布尔代数，在思维法则一书中首次用符号语言描述了思维活动基本推理法则。,5、英国数学家Turing于1936年提出理想计算机数学模型，即图灵机。Turing测试。,6、1943年，McCulloch 和 Pitts提出M-P神经元模型。,7、1946年，世界上第一台电子计算机诞生。,人工智能技术导论,第23页,人工智能发展概况,人工智能学科产生（1956年）,1956年夏季，McCarthy,Minsky,Lochester,Shannon,More,Samuel,Selfridge,Solomonff,Newell,Simon等十人在Dartmouth大学召开历时两个多月研讨会，讨论机器智能相关问题。由McCarthy提出“人工智能”一词，人工智能从此成为一门学科。,人工智能技术导论,第24页,人工智能发展概况,符号主义AI发展概况,1、形成（1956-1965）（人工智能推理期。结构良好问题。搜索策略和算法）,（1）、1956年，Samuel跳棋程序。1959,1962,（2）、定理证实方面，1956年Newell等逻辑理论机（LT）程序；1958年，王浩工作；1965年，Robinson提出消解原理。,（3）、模式识别方面，1959年Selfridge模式识别程序；1965年Roberts编制了能够分辨积木结构程序。,（4）、问题求解方面。1960年，Newell通用问题求解(GPS)程序。,（5）、1960年，McCarthy研制成功LISP语言。,人工智能技术导论,第25页,人工智能发展概况,人工智能知识期（1965-70年代末）,（1）、教授系统方面。1965年，Feigenbaum教授系统DENDRAL，1968年投入使用。DENDRAL对知识表示、存放、获取和推理技术为以后教授系统建造树立了榜样，对AI发展产生了深刻影响。之后著名教授系统有：医学教授系统MYCIN，地质勘探教授系统PROSPECTOR，计算机配置教授系统R1等。,（2）、1969年，国际人工智能联合会议(IJCAI)召开。1970年，“Artificial Intelligence”杂志创刊。,（3）、1977年，Feigenbaum在第五届国际人工智能会议上，提出了“知识工程”概念。,发展期（20世纪80年代后）,教授系统与知识工程在理论、技术和应用方面都有长足进步和发展。出现了多教授系统、大型教授系统、微教授系统、分布式教授系统等。智能管理信息系统、智能决议支持系统、智能控制系统等。,人工智能技术导论,第26页,人工智能发展概况,连接主义路径发展概况,1、1943年，神经生理学家McCulloch 和Pitts提出M-P神经元模型。1944年，Hebb提出Hebb学习规则。,2、1957年，Rosenblatt提出Perceptron单层神经网络模型。1962年，Widrow提出自适应线性元件Adaline。应用于天气预报、电子线路板分析、人工视觉等。,3、1969年，Minsky和Papert发表Perceptrons，证实了单层人工神经网络无法实现一个简单异或逻辑函数XOR，把神经网络研究带入低谷。,4、在低谷期，Kohonen Grossberg和Anderson等人仍坚持研究，取得了一些有价值结果。,5、20世纪80年代中期以后，神经网络研究复苏，掀起了新一轮研究热潮。1986年，Hopfield网络成功应用于TSP问题。1986年Rumelhart提出BP算法，处理了多层人工神经元网络学习问题。1987年6月，第一届国际神经网络大会（IJCNN）召开，盛况空前。当前，NN与教授系统、知识工程成为AI两个主流方向。NN在智能控制、信号处理、最优化、知识工程等领域都有成功应用。,人工智能技术导论,第27页,当前发展趋势,1、传统以符号处理为中心人工智能与神经网络结合。,神经网络：识别 联想 学习 适应，负责对外界感知和交互,教授系统：判断 推理 搜索，负责高层决议与控制,2、新理论、新技术出现。,Fuzzy,Genetic Algorithm,Chaos,Artificial life,Soft Computing,Computational Intelligence,Rough set,Data Mining,Knowledge discovery in database,Data warehouse,Situated AI,Agent-based distributed AI,等。,人工智能技术导论,第28页,第二章 基于谓词逻辑机器推理,谓词、函词、量词,个体,：研究对象中能够独立存在详细或抽象客体。个体用个体常元或个体变元表示，如x,y,z,a,b,c,等。,谓词,：描述个体性质及个体之间相互关系词。,如P、Q、R，等。,例、命题“2是素数”中，2是个体，“是素数”是谓词。可表示为P(2).,函词,（函数）：一些个体是其它个体函数，描述这种关系词称为函词。,例、命题“小李父亲是医生”可表示为,Doctor(father(Li).,量词,：存在量词“,”；全称量词“”。,例、“任何实数平方都非负”可表示为,x(R(x),N(s(x)。,“存在偶素数”可表示为,x(,E(x)P(x)。,人工智能技术导论,第29页,一些命题表示,凡是人都有名字,x(M(x),N(x),不存在最大整数,x(G(x),y(G(y),D(x,y),x(G(x)y(G(y),D(y,x),对全部自然数，都有X+YX,x y(N(x)N(y)S(x,y,x),一些人对一些食物过敏,x y(M(x)F(y)G(x,y),人工智能技术导论,第30页,谓词公式,项定义,：1、个体常元和个体变元是项；2、设,f,是,n,元函词符号，,t,1,t,2,t,n,是项，则,f,(,t,1,t,2,t,n,)是项。3、只有有限次使用1，2得到符号串才是项。,原子公式,：,P,是,n,元谓词，,t,1,t,2,(,t,n,是项，则,P,(,t,1,t,2,t,n,)称为原子谓词公式(原子公式)(原子)。,谓词公式,：1、原子公式是谓词公式；2、若A、B是谓词公式，,则,A，A,B，A,B，A,B，A,B，,xA，xA,也是谓词公式；3、只有有限次地应用步骤1，2形成符号串才是谓词公式。,辖域,：,xA 和 xA中，x称为量词指导(作用)变元，A称为x辖域。辖域中与该量词指导变元相同变元称为约束变元，其它变元(假如存在话)称为自由变元。,例、,xP(x)；x(H(x)G(x,y)；xA(x)B(x),约束变元更名,：,两个规则,人工智能技术导论,第31页,部分逻辑蕴含式（p59-p60),析取三段论：,A,(A B)B,假言推理（分离规则）：,A,(A B)B,拒取式：,B(A B)A,假言三段论：,(A B)(BC)A C,二难推论,:(A,B),(A C)(BC)C,全称指定规则US(Universal Specification)：,xA(x)A(y)，y是个体域中任一确定元素。,存在指定规则ES(Existential Specification)：,xA(x)A(c)，c是个体域中某一确定元素。,全称推广规则UG(Universal Generalization)：A(y),xA(x)，y是个体域中任一确定元素。,存在推广规则 EG(Universal Generalization)：A(c),xA(x)，c是个体域中某一确定元素。,人工智能技术导论,第32页,自然演绎推理,以谓词公式等价式及推理定律为基础进行推理称为自然演绎推理。例见教材p61。,推理过程是一个符号变换过程，类似于人们使用自然语言进行推理思维过程。,推理与谓词公式含义无关，是一个形式推理。,自然演绎推理在机器上实施比较困难,推理规则太多,应用规则需要很强模式识别能力,中间结论指数递增,人工智能技术导论,第33页,子句集,定义1,原子谓词公式及其否定称为,文字,；若干个文字一个析取式称为一个,子句,；由r个文字组成子句称为,r-文字子句,，1-文字子句称为,单元子句,，不含任何文字子句称为,空子句,，记为,或,NIL,。,定义2,对一个谓词公式G，经过一定步骤得到子句集合S称为G,子句集,。,人工智能技术导论,第34页,子句集,（1）,、利用等价式,A B A B,和 A B (A B)(B A),消去联结词“,”和“”。,（2）,、缩小否定联结词作用范围，使其仅作用于原子公式。可利用以下等价式：,A,A；,(A,B),A B，(A B)A B；,xA(x)x A(x)，xA(x)x A(x),（3）,、重新命名变元名，使不一样量词约束变元有不一样名字。,（4）,、消去存在量词。若存在量词不在全称量词辖域内，则用一个常量符号替换该存在量词辖域中对应约束变元。这么常量称为Skolem常量；若该存在量词在一个或多个全称量词辖域内，则用这些全称量词指导变元一个函数替换该存在量词约束变元。这么函数称为Skolem函数。,比如,x,1,x,2,x,n,yP(x,1,x,2,x,n,y)中y可用Skolem函数f(x,1,x,2,x,n,)替换为x,1,x,2,x,n,P(x,1,x,2,x,n,f(x,1,x,2,x,n,),)。,人工智能技术导论,第35页,子句集,（5）,、把全称量词全部移到公式左边。,（6）,、把全称量词后面公式利用等价关系,A,(B C),(AB)(A C)化为子句合取式，得到公式称为,Skolem标准形,。Skolem标准形普通形式为x,1,x,2,x,n,M，其中M是子句合取式。,（7）,、消去全称量词。,（8）,、对变元更名，使子句间无同名变元。,（9）,、消去合取词,，以子句为元素组成集合称为谓词公式子句集。,例：把以下谓词公式化为子句集。,xyP(x,y)yQ(x,y)R(x,y),人工智能技术导论,第36页,子句集,求解过程,xyP(x,y)yQ(x,y)R(x,y),1),x,yP(x,y),y,Q(x,y),R(x,y),2),x,y,P(x,y),yQ(x,y),R(x,y),3)xyP(x,y),z,Q(x,z,)R(x,z,),4),xP(x,f(x),)Q(x,g(x),)R(x,g(x),),5),P(x,f(x)Q(x,g(x)R(x,g(x),6),P(x,f(x),Q(x,g(x),(,P(x,f(x),R(x,g(x),7)P(x,f(x)Q(x,g(x)(P(,y,f(,y,)R(,y,g(,y,),8),P(x,f(x)Q(x,g(x),，,(P(y,f(y)R(y,g(y),定理1,谓词公式G 不可满足,当且仅当,其子句集S不可满足。子句集S是不可满足是指其全部子句合取式是不可满足。,人工智能技术导论,第37页,命题逻辑中归结原理,要证实在前提P下结论Q成立，即是证实P,Q永真，这只须证实P,Q不可满足。,依据定理1，只须证实P,Q子句集不可满足。因为子句之间是合取关系，只要有一个子句不满足，则整个子句集不可满足。,因为空子句是不可满足，所以假如子句集中包含空子句，则该子句集是不可满足。,若子句集中不包含空子句，则可经过Robinson提出归结原理对子句集进行归结，归结过程确保子句集不可满足性不变。一旦归结出空子句，则证实结束。,所以，归结原理把定理证实化为子句集中归结出空子句过程。,人工智能技术导论,第38页,命题逻辑中归结原理,定义,、设L是一个文字，则称L与,L为,互补文字,。,定义,、设C,1,、C,2,是命题逻辑中两个子句，C,1,中有文字L,1,，C,中有文字L,，且L,1,与L,互补，从C,1,，C,中分别删除L,1,，L,，再将剩下部分,析取,起来，组成新子句C,1,称为C,1,与C,2,归结式,（消解式），C,1,，C,2,称为C,1,亲本子句,。,C,1,=PQ R,C,2,=Q S,C,1,=P R S,定理,、归结式C,1,是其亲本子句C,1,与C,2,逻辑结论。,推论,、设C,1,，C,2,是子句集S两个子句，C,1,是它们归结式，则,（）若用,C,1,代替C,1,和C,2,后得到新子句集S,1,，则由S,1,不可满足性可推出原子句集S不可满足性。即S,1,不可满足,S不可满足,）若把,C,1,加入到S中，得到新子句集S,，则S,与S在不可满足意义上是等价。即S,2,不可满足,S不可满足,人工智能技术导论,第39页,命题逻辑中归结原理,例、用归结原理证实R是P,(P Q)R，(SU)Q，U逻辑结果。,求子句集,P,(PQ)R,(SU)Q,U,R,P,(P Q)R,(S U)Q,U,R,P,P Q R,S Q,U Q,U,R (子句集),归结演绎,P Q R R P Q,P Q P Q,Q U Q U,U U,人工智能技术导论,第40页,替换与合一,问题提出,谓词逻辑和命题逻辑中使用归结原理差异,C,1,=P(x)Q(x),C,2,=P(a)R(y),C,1,=P(a)Q(a),C,2,=P(a)R(y),定义 一个,替换,(Substitution)是形如,t,1,/x,1,t,2,/x,2,t,n,/,x,n,有限集合，其中,t,1,t,2,t,n,是项(替换分子)，,x,1,x,2,x,n,是互不相同个体变元(替换分母)。,t,i,/,x,i,表示用t,i,代换x,i,。t,i,与x,i,不一样，x,i,也不能,循环,出现在t,j,中(j=1,2,n)。,基替换,(t,1,t,2,t,n,均不含变元)、,空替换,例：a/x,g(c)/y,f(g(b)/z ，g(y)/x,f(x)/y,人工智能技术导论,第41页,替换与合一,定义7 设,t,1,/,x,1,t,2,/,x,2,t,n,/,x,n,是一个替换，E是一个表示式，把E中出现全部个体变元,x,i,都用,t,i,替换，记为E,，得到结果称为E在,下,替换实例,(Instance)。,Eg：E=P(x,y,g(z),a,/,x,f(b),/y,c,/z,，,E,=P(a,f(b),g(c),定义,设,t,1,/,x,1,t,2,/,x,2,t,n,/,x,n,，,u,1,/,y,1,u,2,/,y,2,u,m,/,y,m,是两个替换，则将集合,t,1,/,x,1,t,2,/,x,2,t,n,/,x,n,，u,1,/,y,1,u,2,/,y,2,u,m,/,y,m,中符合以下条件两种情形删除：,t,i,/,x,i,，当t,i,x,i,u,i,/,y,i,，当y,i,x,1,x,2,x,n,得到集合仍是一个替换，称为,与,复合,或,乘积,，记为,例:设,=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,人工智能技术导论,第42页,替换与合一,定义,设S=,F,1,F,2,F,n,是一个原子谓词公式集，若存在一个替换，使得F,1,F,2,F,n,，则称为S一个,合一,(Unifier)，并称S为可合一。,一个公式集合一普通不唯一,定义10 设是公式集S一个合一，假如对S任何一个合一，都存在一个替换，使得,，则称为S一个,最普通合一,(Most General Unifier)，简称MGU,设S=P(u,y,g(y),P(x,f(u),z),有=u/x,f(u)/y,g(f(u)/z,对其它某个合一,如=a/x,f(a)/y,g(f(a)/z,a/u，可找到替换=a/u，使得,人工智能技术导论,第43页,替换与合一,定义11 设S是一个非空含有,相同,谓词名原子公式集，从S中各公式左边第一个项开始，同时向右比较，每一组不都相同项差异部分组成集合称为S,差异集,。,公式集S=P(a,x,f(g(y),P(z,h(z,u),f(u)差异集为a,z,x,h(z,u),g(y),u,人工智能技术导论,第44页,替换与合一,设S为一非空有限含有相同谓词名原子谓词公式集，求SMGU算法：,(1)令k=0,S,k,=S,k,=,（表示空替换）,(2)若,S,k,只含有一个谓词公式，则算法停顿，,k,就是要求最普通合一,(3)求,S,k,差异集,D,k,(4)若,D,k,中存在元素,x,k,和,t,k,，其中,x,k,是变元，,t,k,是项且,x,k,不在,t,k,中出现，则置S,k+1,=S,k,t,k,/,x,k,，,k+1,=,k,t,k,/,x,k,，k=k+1，然后转步(2),(5)算法停顿，S最普通合一不存在,人工智能技术导论,第45页,替换与合一,求,S=P(a,x,f(g(y),P(z,h(z,u),f(u)MGU,k=0,S,0,=S,0,=,D,0,=a,z,1,=,0,a/z=a/z,S,1,=S,0,a/z=P(a,x,f(g(y),P(a,h(a,u),f(u),k=1,D,1,=x,h(a,u),2,=,1,h(a,u)/x=a/z h(a,u)/x=a/z,h(a,u)/x,S,2,=S,1,h(a,u)/x=,P(a,h(a,u),f(g(y),P(a,h(a,u),f(u),人工智能技术导论,第46页,替换与合一,S,2,=S,1,h(a,u)/x=,P(a,h(a,u),f(g(y),P(a,h(a,u),f(u),k=2,D,2,=g(y),u,3,=,2,g(y)/u=a/z,h(a,g(y)/x,g(y)/u,S,3,=S,2,g(y)/u=,P(a,h(a,g(y),f(g(y),P(a,h(a,g(y),f(g(y),=P(a,h(a,g(y),f(g(y),k=3,S,3,为单元素集，所以,3,为所求SMGU,说明：MGU可能是不唯一，如D,k,=x,k,y,k,时,人工智能技术导论,第47页,谓词逻辑中归结原理,定义12,设C,1,C,2,是两个没有相同变元子句，L,1,L,2,分别是C,1,C,2,中两个文字，假如L,1,与L,2,有最普通合一，则子句C,12,=(C,1,-L,1,)(C,2,-L,2,)，称作C,1,和C,2,二元归结式,(,二元消解式,)。C,1,和C,2,称为C,12,亲本子句,，L,1,，L,2,称为,消解文字,。,例：C,1,=P(x)Q(x),C,2,=P(a),R(y),C,12,=Q(a),R(y),说明：当子句内部有可合一文字时，应在归结前进行合一，使子句最简,例：C,1,=P(x)P(f(a)Q(x)，则C,1,=P(f(a)Q(x),归结原理：C,1,C,2,(C,1,-L,1,)(C,2,-L,2,),人工智能技术导论,第48页,谓词逻辑中归结原理,归结时注意事项,谓词一致性.名称不一致谓词不能归结,P(x)，R(x),不能归结,常量一致性.含有不一样常量谓词不能归结,P(a,)，,P(b,),不能归结,变量与函数,P(x,x,)，P(x,f(x),),不能归结,P(x,x,)，P(x,f(y),),能归结,不能同时消去两个互补对,P,Q 与,P,Q,不能同时消去,人工智能技术导论,第49页,归结反演,归结反演：应用归结原理证实定理过程,若F为已知前提公式集，Q为结论，用归结反演证实Q为真步骤是：,（1）、否定Q，得到,Q；,（2）、把Q并入到公式集F中，得到F,Q；,（3）、把公式集F,Q化为子句集S；,（4）、应用归结原理对子句集S中子句进行归结，并把每次归结得到归结式都并入S中。如此重复进行，直到出现空子句，就证实了Q为真。,定理5（归结原理,完备性,）、假如子句集S是不可满足，则必存在一个由S推出空子句归结序列。,人工智能技术导论,第50页,归结反演举例,例：自然数都是大于零整数；全部整数不是偶数就是奇数；偶数除以2是整数。求证：全部自然数不是奇数就是其二分之一为整数数。,证实：前提：,F,1,：,x(N(x)GZ(x)I(x),N(x)：x是自然数,F,2,：,x(I(x)E(x),O(x),GZ(x)：x0 I(x)：x是整数,F,3,：,x(E(x)I(h(x),E(x)：x是偶数 O(x)：x是奇数,结论：G：x(N(x)O(x),I(h(x),h(x)：half(x),F,1,、F,2,、,F,3,及,G 化为子句集：,（1）,N(x)GZ(x),（2）,N(y)I(y),（3）I(z)E(z)O(z),（4）,E(u)I(h(u),（5）N(c),（6）,O(c),（7）,I(h(c),归结：,（8）I(c)(2),(5),c/y),（9）,I(c)E(c)(3),(6),c/z),（10）E(c)(8),(9),（11）I(h(c)(4),(10),c/u),（12）(7),(11),人工智能技术导论,第51页,应用归结原理求解,应用归结原理求取问题答案步骤,把已知前提用谓词公式表示出来，并化为子句集S,把待求解问题也用谓词公式表示出来，然后把它否定与,谓词ANS,组成析取式。ANS变元应与问题变元完全一致,把此析取式化为子句集，并把该子句集并入S中得到子句集S,对,S,应用归结原理进行归结,若得到归结式ANS，则答案就在ANS中,人工智能技术导论,第52页,应用归结原理求解,例：设A、B、C三人中有些人从不说真话，也有些人从不说假话，某人向这三人分别提出同一个问题：,谁是说谎者？,A答：“B和C都是说谎者”；B答：“A和C都是说谎者”；C答：“A和B中最少有一个是说谎者”。问：谁是老实人？,解、设T(x)表示x说真话。假如A说是真话，则有：,T(A),T(B)T(C),假如A说是假话，则有：,T(A),T(B)T(C)。,同理，对B和C有：,T(B),T(A)T(C),T(B),T(A)T(C),T(C),T(A)T(B),T(C),T(A)T(B),人工智能技术导论,第53页,应用归结原理求解,化为子句集S：,1)T(A)T(B),2)T(A)T(C),3)T(A)T(B)T(C),4),T(B)T(C),5)T(A)T(B)T(C),6)T(C)T(A),7)T(C)T(B),把,T(x)ANS(x)并入S,8)T(x)ANS(x),9)T(A)ANS(C)(8,6,C/x),10)T(B)ANS(C)(7,8,C/x),11)T(B)ANS(C)(9,1),12)ANS(C)(10,11),所以C是老实人。不论怎样归结，推不出ANS(A),ANS(B),人工智能技术导论,第54页,归结策略,归结反演普通过程。,步1将子句集S置入CLAUSES表；,步2若空子句NIL在CLAUSES中，则归结成功，结束。,步3若CLAUSES表中存在可归结子句对，则归结之，并将归结式并入CLAUSES表，转步；,步4归结失败，退出。,穷举算法（广度优先策略）,第一轮：将原子句集S中子句两两归结，产生归结式集合记为S1，再将S1并入CLAUSES表；,第二轮：将新CLAUSES表，即S,S1中子句与S1中子句两两归结，产生归结式集合记为S2，再将S2并入CLAUSES；,第三轮：将新CLAUSES表即S,S1,S2中子句与S2中子句两两归结，。,如此下去，直到出现空子句。,人工智能技术导论,第55页,归结策略,例1 设有以下子句集，用穷举算法归结以下：,S：（,1）P,Q,（2）,P,Q,（3）,P,Q,（4）,P,Q,S,1,：（5,）,Q (1),(2),（6）,P (1),(3),（7）,Q,Q (1),(4),（8）,P,P (1),(4),（9）,Q,Q (2),(3),（10）,P,P (2),(3),（11）,P (2),(4),（12）Q (3),(4),S,2,：（13,）P,Q (1),(7)（14）,P,Q,(1),(8),人工智能技术导论,第56页,归结策略,（15,）P,Q (1),(9)（16）,P,Q,(1),(10),（17）Q,(1),(11),（18）,P (1),(12),（19）Q (2),(6)（20）,P,Q (2),(7),（21）,P,Q (2),(8)（22）,P,Q (2),(9),（23）,P,Q (2),(10),（24）,P (2),(12),（25）P (3),(5)（26）,P,Q (3),(7),（27）,P,Q (3),(8)（28）,P,Q (3),(9),（29）,P,Q (3),(10)（30）Q (3),(11),（31）,P (4),(5)（32）Q (4),(6),（33）,P,Q (4),(7)（34）,P,Q (4),(8),（35）,P,Q (4),(9)（36）,P,Q (4),(10),（37）Q (5),(7),（38）Q,(5),(9),（39）,(5),(12),人工智能技术导论,第57页,归结策略,定义：设,C,1,，C,2,是两个子句，若存在替换,，使得,C,1,C,2,，则称子句,C,1,类含,C,2,。,P(x)类含P(a),Q(y),P(x)类含P(a),删除策略。在归结过程中可随时删除以下子句：,（1）、含有纯文字子句。,纯文字,是指在子句中无补文字文字。,P(x),Q(x,y),R(x)，,P(a),Q(u,v)，,Q(b,z)，,P(w),解释：永远无法得到空子句,（2）、含有永真式子句；,解释：对子句集不可满足性不起作用,（3）、被子句集中别子句类含子句。,解释：C=P(x)替换后得C=P(a)，D=P(a),Q(y),人工智能技术导论,第58页,归结策略,使用删除策略，例1可简化为：,（,1）P,Q,（7）,P,(2),(4),（2）,P,Q,（8）Q,(3),(4),（3）,P,Q （9）,(5),(8),（4）,P,Q,（5,）,Q (1),(2),（6）,P (1),(3),删除策略特点：,删除策略思想是及早删除无用字句，以防止无效归结，缩小