华南理工大学《人工智能》复习资料
- 格式:doc
- 大小:3.29 MB
- 文档页数:17
第一章绪论●人工智能的诞生:1965年夏季,在达特茅斯大学●人工智能的学派:符号主义,联结主义,行为主义第二章知识表示方法●知识的特性:1.相对正确性;2.不确定性;3.可表示性;4.可利用性●★用谓词公式表示知识的步骤:1.定义谓词及个体,确定每个谓词及个体的确切含义。
2.根据所要表达的事物或概念,为每个谓词中的变元赋以特定的值。
3.根据所要表达的知识的语义,用适当的联接符号将各个谓词联接起来,形成谓词公式。
●★★机器人搬弄积木块问题表示P19●★一阶谓词逻辑表示法的特点:1.自然性;2.适宜于精确性知识的表示;3.易实现;4.与谓词逻辑表示法相对应的推理方法。
●产生式系统的组成:1.规则库;2.综合数据库;3.推理机●★产生式系统的推理方式:1.正向推理:①规则库中的规则与综合数据库中的事实进行匹配,得到匹配的规则集合;②使用冲突解决算法,从匹配规则集合中选择一条规则作为启用规则;③执行启动规则的后件。
将该启用规则的后件送入综合数据库或对综合数据库进行必要的修改。
重复这个过程直至达到目标。
2.反向推理:①规则库中的规划后件与目标事实进行匹配,得到匹配的规则集合;②使用冲突解决算法,从匹配规则集合中选择一条规则作为启用规则;③将启用规则的前件作为子目标。
重复这个过程直至各子目标均为已知事实,则反向推理的过程成功结束。
●★★语义网络表示知识举例:P36 例2.5、2.6、2.7;P71 作业18●框架的定义及组成:一个框架由若干个“槽”组成,每个“槽”又可划分为若干个“侧面”。
一个槽用于描述所论及对象的某一方面的属性,一个侧面用于描述相应属性的一个方面。
框架名<槽名><侧面><值>●脚本表示法:美国耶鲁大学的R.C.Schank及其同事们根据概念从属理论提出了一种知识表示方法——脚本表示法。
●问题状态空间的构成:1.状态;(2).算符;3.状态空间。
●★用状态空间表示问题的步骤1.定义状态的描述形式;2.用所定义的状态描述形式把问题的所有可能的状态都表示出来,并确定出问题的初始状态集合描述和目标状态集合描述;3.定义一组算符。
一、填空题(40分)1.人工智能的主要学派:(1)符号主义:又称逻辑主义、心理学派或计算机学派,其原理主要是为物理符号系统假设和有限合理性原理。
(2)连接主义:又称仿生学派或生理学派,其原理主要是为神经网络及神经网络间的连接机制与学习算法。
(3)行为主义:又称进化主义或控制论学派,其原理为控制论及感知-动作型控制系统。
2.人工智能三个基本问题:知识获取、知识推理、知识利用。
3.常用的知识表示方法包括:状态空间法、问题归纳法、谓词演算法、语义网络法、框架表示法、本体表示法、过程表示法和神经网络表示法。
4.机器学习分为:监督学习、无监督学习、强化学习。
5.遗传算法基本操作分为:选择、交叉和变异。
6.产生式系统的构成分为:规则库、综合数据库和推理机。
7.问题状态空间包含的三种说明集合分别为:初始状态集(S)、操作符集合(F)、以及目标状态集合(G)。
8.可信度方法中,不精确推理规则的一般形式为:IF E THEN H (CF(H,E)),其中(CF(H,E))是该规则的可信度,称为可信度因子或规则强度。
(1)当证据E的可信度CF(E)的取值范围与CF(H,E)相同,即-1 ≤ CF(E)≤ 1;(2)当证据以某种程度为真时,CF(E) > 0(3)当证据肯定为真时,CF(E) = 1(4)当证据以某种程度为假时,CF(E) < 0(5)当证据肯定为假时,CF(E) = -1(6)当证据一无所知时,CF(E) = 09.用产生式方法表示张和李是同学关系:(classmate,Zhang,Li)10.模糊集合表示,例如有一组数据:85,90,82,70,98,模糊集合表示为:11.自然语言理解过程的层次有:语音分析、句词分析、语义分析。
12.人工生命研究实例有:人工脑、计算机病毒、计算机进程、细胞自动机、人工核苷酸。
13.计算智能涉及神经计算、模糊计算、进化计算、粒群计算、自然计算、免疫计算和人工生命等研究领域。
人工智能:Artificial Intelligence,简称AI,主要研究如何使用人工的方法和技术,使用各种自动化机器或智能化机器模仿、延伸和扩展人的智能,实现某些机器的智能行为。
传统划分①符号主义学派②联结主义学派③行为主义学派现代1.符号智能流派2.计算智能流派3.群体智能流派人工智能的基本技术:1知识表示技术2知识推理、计算和搜索技术3系统实现技术。
符号智能的表示是知识的表示,运算是基于知识表示的推理或符号操作,采用搜索方法进行问题求解,一般在问题空间上进行,计算智能的表示是对象表示,运算时给予对象的表示的操作或计算,采用搜索方法进行问题求解,一般是在解空间上进行。
人工智能的研究领域:定理证明、专家系统、模式识别、机器学习、计算智能、自然语言处理、组合调度问题。
应用领域:难题求解、自动定理证明、自动翻译、智能管理、智能通信、智能仿真等。
人工智能的主要研究途径与方法:1功能模拟。
符号推演2结构模拟。
神经计算3行为模拟。
控制进化人工智能的研究目标及其意义:1目标:远期目标是要制造智能机器,即探索智能的基本机理,最终制造出和人有相似或相近智力和行为能力的综合智能系统;近期目标是实现机器智能,即研究如何使用现有的计算机具备更高的智能,在一定领域或在一定程度上去完成需要人的复杂脑力劳动才能完成的工作。
2意义:普遍的计算机智能低下,无法满足社会需求;研究AI是当前信息化社会的迫切需求;智能化是自动化发展的必然趋势;研究AI,对人类自身的智能的奥秘也提供有益的帮助。
人工智能的基本内容:1从人工智能的定义出发包括(感知与交流的模拟,记忆,联想,计算,思维的模拟,输出效率或行为模拟2从知识工程的角度出发包括(知识的获取,知识的处理以及知识的运用)人工智能诞生1956年夏,达特莫斯大学的研究会,麦卡锡提议正式采用了“AI”术语。
发展:推理期,知识期,学习期AI的现状与发展趋势:1多种途径齐头并进,多种方法协作互补2新思想、新技术不断涌现,新领域新方向不断开拓3理论研究更加深入,应用研究愈加广泛4研究队伍日益壮大,社会影响越来越大。
人工智能第一章1、智能(intelligence )人的智能是他们理解和学习事物的能力,或者说,智能是思考和理解能力而不是本能做事能力。
2、人工智能(学科)人工智能研究者们认为:人工智能(学科)是计算机科学中涉及研究、设计和应用智能机器的一个分支。
它的近期主要目标在于研究用机器来模仿和执行人脑的某些智力功能,并开发相关理论和技术。
3、人工智能(能力)人工智能(能力)是智能机器所执行的通常与人类智能有关的智能行为,这些智能行为涉及学习、感知、思考、理解、识别、判断、推理、证明、通信、设计、规划、行动和问题求解等活动。
4、人工智能:就是用人工的方法在机器上实现的智能,或者说,是人们使用机器模拟人类的智能。
5、人工智能的主要学派:符号主义:又称逻辑主义、心理学派或计算机学派,其原理主要为物理符号系统(即符号操作系统)假设和有限合理性原理。
代表人物有纽厄尔、肖、西蒙和尼尔逊等。
连接主义:又称仿生学派或生理学派,其原理主要为神经网络及神经网络间的连接机制与学习算法。
行为主义:又称进化主义或控制论学派,其原理为控制论及感知—动作模式控制系统。
6、人类认知活动具有不同的层次,它可以与计算机的层次相比较,见图人类 计算机认知活动的最高层级是思维策略,中间一层是初级信息处理,最低层级是生理过程,即中枢神经系统、神经元和大脑的活动,与此相对应的是计算机程序、语言和硬件。
研究认知过程的主要任务是探求高层次思维决策与初级信息处理的关系,并用计算机程序来模拟人的思维策略水平,而用计算机语言模拟人的初级信息处理过程。
7、人工智能研究目标为:1、更好的理解人类智能,通过编写程序来模仿和检验的关人类智能的理论。
2、创造有用和程序,该程序能够执行一般需要人类专家才能实现的任务。
一般来说,人工智能的研究目标又可分为近期研究目标和远期研究目标两种。
两者具有不可分割的关系,一方面,近期目标的实现为远期目标研究做好理论和技术准备,打下了必要的基础,并增强人们实现远期目标的信心。
人工智能原理期末考试复习1. 什么是人工智能?发展经历了几个阶段?人工智能指的是能够感知或推断信息,并将其作为知识而拥有,以应用于环境或语境中适合的行为;机器的智能称为人工智能,通常在运用程序、间或适当硬件的计算机系统中得以实现.2. 人工智能研究的内容有哪些?机器学习、知识表示方法、搜索求解策略、进化算法及其应用、确定性及不确定性推理方法、群体智能算法及其应用。
3. 人工智能有哪些研究领域?安全防范、医疗诊断、语音识别、工业制造、计算机游戏、机器翻译。
4. 什么是知识?有哪些特性?有几种分类方法?知识是人们在长期的生活及社会实践中、在科学研究及实验中积累起来的对客观世界的认识与经验。
相对正确性、不确定性、可表示性与可利用性。
分类方法:(1)按知识的作用范围分为∶常识性知识和领域性知识﹔(2)按知识的作用及表示分为∶事实性知识、规则性知识、控制性知识和元知识;(3 )按知识的确定性分为:确定知识和不确定知识;(4) 按人类思维及认识方法分为:逻辑性知识和形象性知识。
5. 什么是知识表示、命题、谓词,一阶谓词逻辑、产生式、框架、语义网络?知识表示就是将人类知识形式化或者模型化;命题是一个非真即假的陈述句;谓词的一般形式: ),...,,(21n x x x P );n x x x ,...,,21是个体,某个独立存在的事物或者某个抽象的概念, P 是谓词名,用来刻画个体的性质、状态或个体间的关系。
一阶谓词逻辑表示:谓词不但可表示一些简单的事实,而且可以表示带有变量的“知识”,有时称为“事实的函数”。
进而可用谓词演算中的逻辑联接词“与()”、“或(v)"、“非(┐)”和“蕴含(→)”等来组合已有知识,从而表示出更复杂的知识。
产生式通常用于表示事实、规则以及它们的不确定性度量,适合于表示事实性知识和规则性知识。
框架是一种描述所论对象(一个事物、事件或概念)属性的数据结构。
语义网络:从图论的观点看,它其实就是“一个带标识的有向图”,由结点和弧(也称“边”)所组成。
人工智能复习资料1.3什么是人工智能?它研究的目标是什么?从能力的角度:人工智能是指用人工的方法在机器(计算机)上实现的智能。
从学科的角度:人工智能是一门研究如何构造智能机器或智能系统,去模拟、延伸和扩展人类智能的学科。
目标:1)对智能行为有效解释的理论分析。
2)解释人类智能。
3)构造具有智能的人工制品。
1.8人工智能有哪些主要研究和应用领域?其中哪些是新的研究热点?机器思维、机器学习、机器感知、机器行为计算智能、分布智能、智能系统、人工心理与人工情感人工智能的典型应用:智能机器人、智能检索、智能游戏问题求解(下棋程序),逻辑推理与定理证明(四色定理证明),自然语言理解,自动程序设计,专家系统,机器学习,神经网络,机器人学(星际探索机器人),模式识别(手写识别,汽车牌照识别,指纹识别),机器视觉(机器装配,卫星图像处理),智能控制,智能检索,智能调度与指挥(汽车运输高度,列车编组指挥),系统与语言工具新的研究热点:分布式人工智能与Agent,计算智能与进化计算,数据挖掘与知识发现(超市市场商品数据分析),人工生命1.9人工智能有未来发展有哪些值得思考和关注的重要问题?1.多学科交叉研究2.分布智能与社会智能研究3.集成智能研究4.智能网络研究5.认知计算与情感计算研究6.智能系统与智能服务2.2什么是知识表示?知识表示有哪些要求?知识表示是对知识的描述,即用一组符号把知识编码成计算机可以接受的某种结构。
要求:1)表示能力。
2)可利用性。
3)可组织性与可维护性。
4)可理解性与可实现性。
2.4什么是推理?它有哪些分类方法?推理是由具体事例归纳出一般规律,或者根据已有知识推出新的结论的思维过程。
分类方法:按推理的逻辑基础:演绎推理和归纳推理按知识的确定性:确定性推理和不确定性推理按推理的控制策略:推理策略和搜索理策略2.5推理中的控制策略包括哪几个方面的内容?主要解决哪些问题?推理的控制策略是指如何使用领域知识使推理过程尽快达到目标的策略解决推理方向控制策略、求解策略、限制策略、冲突消解策略等2.6什么是命题?什么是命题的真值?断言:一个陈述句称为一个断言.命题:具有真假意义的断言称为命题.命题的意义通常称为真值,它只有真、假两种情况。
第一章1.人工智能的定义(能力)?人工智能的研究目标?人工智能(学科)是计算机科学中涉及研究、设计和应用智能机器的一个分支。
近期目标:实现机器智能——理论和技术基础远期目标:制造智能机器——发展方向2.人工智能的起源与发展过程;典型人物、事件(1)古希腊,亚里士多德,形式逻辑的基本规律(2)英国,培根,归纳法(3)德国,莱布尼茨,数理逻辑(4)英国,布尔,布尔代数(5)奥地利,哥德尔,一阶谓词完备性(6)英国,图灵,图灵机(7)美国,Mauchly,ENIAC(8)美国,McCulloch,神经网络模型(9)美国,香农,信息论1956年,麦卡锡,人工智能之父,50年代开始符号处理,70年代理论走向实践,Nilson A*算法,1977年,专家系统广泛应用,80年代达到顶峰,90年代趋向小型化、并行化、网络化、智能化。
3.人工智能的主要学派及观点符号主义,认为人工智能源于数理逻辑。
联结主义,认为人工智能源于仿生学。
行为主义,认为人工智能源于控制论。
4.人工智能所研究的范围与应用领域智能感知:模式识别、自然语言理解智能推理:问题求解、逻辑推理与定理证明、专家系统、自动程序设计智能学习:机器学习、神经网络、计算智能与进化计算智能行动:机器人学、智能控制、智能检索、智能调度与指挥、分布式人工智能与Agent、数据挖掘与知识发现、人工生命、机器视觉5.人工智能的基本技术推理技术、搜索技术、知识表示与知识库技术、归纳技术、联想技术第二章1.概念:知识及形式化描述、同构变换、同态变换把有关信息关联在一起所形成的信息结构称为知识。
同构变换可使问题更明确,便于求解,同构问题的解答等价于原始问题的解答。
同态变换可使问题更加简化,易于求解。
原始问题有解,则同态问题有解,同态问题无解,则原始问题无解,它们之间是蕴含关系。
2.知识、信息和数据的区别数据是记录信息的符号,是信息的载体和表示;信息是对数据的解释,是数据在不同场合下的具体含义;只有将有关的信息关联到一起才能使用,才称之为知识。
华南理工大学人工智能期末考试卷题整理二、简答题1.什么是人工智能,哪些阶段答:人工智能研究的是如何运用知识,以便像人类一样完成富有智能的工作,就人工智能的本质而言,可以认为人工智能是一门研究如何制造出人造的智能机器或智能系统,来模拟人类智能活动的能力,以延伸人们智能的科学。
人工智能发展阶段(1)萌芽期(1956年以前)(3)形成时期(1956-1961年)(3)发展时期(1961年以后)2.不确定性推理的“不确定性”在?答:在不确定推理中,规则前件(证据)、后件(结论)以及规则本身在某种程度上都是不确定的。
(1)证据的不确定性:歧义性、不完全性、不精确性模糊性、可信性、随机性和不一致性(2)规则的不确定性:证据的组合的不确定性、规则自身的不确定性规则、结论的不确定性;(3)推理的不确定性;3.列两种知识表示方法和优缺点。
(1)脚本知识表示方法:脚本结构比起语义网络、框架机构等通用结构来要呆板得多,知识表达范围也很窄,因此不适用于表达各种知识。
但对于表达事先构思好的特定知识非常有效。
(2)过程性知识表示方法:过程性知识表示的最主要特点是效率高。
过程性知识表示的主要缺点就是不易修改和添加知识。
4.画机器学习基本构成,分环节作用(1)环境:环境是以某种形式表达的外界信息集合,它代表外界信息来源;(2)知识库:知识库在初始阶段要有相当的初始知识,并且在学习过程中不断修正和增加新的知识:(3)学习环节:在机器学习的整个系统结构中,学习部分是核心模块,是和外部交互的接口;(4)执行环节:执行部分是根据知识库执行一系列任务,同时把执行结果过执行过程中获得的信息反馈给学习部分,完成对新知识库的评价,指导进一步的工作。
5.说常规与高级搜索的区别常规搜索可以找到最优解,但是.即便是A*算法,一般情况下,其算法复杂性仍然是指数时间级的,因此,当问题的规模大到一定程度后,常规搜索就显得无能为力了,而高级搜索放弃每次必然找到最优解的目标,换取算法时间复杂度的降低,适合于求解大规模的优化问题。
人工智能概论简答题人工智能(Artificial Intelligence,AI)是一门理论、方法和技术体系,目的是通过计算机等工具和设备模拟或超越人类智能的各种表现形式,包括感知、推理、学习、创造、沟通、协作等。
它是各类智能应用系统的基础,以及人类自身智慧发展的关键所在,因此备受社会各界关注和研究。
1. 人工智能的来源和历史人工智能源于人类对自身智能本质的思考和模拟,最早的想法可追溯至古希腊哲学家亚里士多德的“逻辑学”和瑞士学者拉曼努金的“机械思维”。
但是,直到20世纪50年代,人工智能的研究才真正开始起步,主要得益于计算机技术的迅速发展和数学、逻辑、语言等学科理论的提升。
此后,不断涌现出机器学习、深度学习、自然语言处理、计算机视觉、智能机器人等人工智能相关的领域和技术。
2. 人工智能的基本理论和方法人工智能的基本理论和方法包括知识表示与推理、机器学习、自然语言处理、计算机视觉、智能控制等方面。
其中,知识表示与推理是实现智能判断和推导的基础,机器学习是实现自我学习和优化的核心手段,自然语言处理是实现人机交互和信息处理的前沿领域,计算机视觉是实现机器感知和识别的重要手段,智能控制是实现智能行为和决策的关键要素。
3. 人工智能的应用领域和前景人工智能的应用领域涵盖了各个社会领域和行业,例如智能交通、智能医疗、智能金融、智能制造、智能家居、智能城市等。
随着人工智能技术的不断发展和完善,未来人们可能会看到更多的智能产品和服务,包括自动驾驶汽车、智能家庭助手、智能医疗设备、智能教育机器人等。
同时,人工智能也带来了一系列挑战和问题,例如数据安全、隐私保护、道德风险等,需要人们共同解决和管理。
4. 未来人工智能的发展方向和趋势未来人工智能的发展方向和趋势可能包括以下几个方面:(1)普适性:人工智能将更多地服务于人类的生产和生活,涉及的应用场景将更为普适和广泛。
(2)多样化:人工智能技术将呈现出越来越多的多样化和细分化,以适应各个应用领域和场景的需求。
华南理工大学《人工智能》复习资料Ch 2.【状态空间表示】S F G<>,,S:初始状态的集合F:操作的集合G:目标状态的集合例如:507{}{}{}Q a b c Q Q<>,,,,,【状态空间图】【状态空间图搜索使用的数据结构】OPEN表:已生成但没考察的节点(待考察节点)CLOSED表:考察过的节点及节点间关系(搜索树)【广度/深度优先搜索特点】广度优先:完备的(一定能找到最优解),搜索效率低,OPEN表为队列结构深度优先:不能保证找到最优解,OPEN表为堆栈结构有界深度优先搜索:即使能求出解,也不一定是最优可变界深度优先搜索算法:深度可变,每次深度超过阈值的点,都被当作待考察点(在CLOSED表中)【启发式搜索算法分类】按选择范围分类:全局择优搜索:考虑所有待考察节点局部择优搜索:只考虑当前节点的子节点【A*算法】f(x)=g(x)+h(x)g(x)为当前点的代价h(x)为距离目标的距离A*对A算法的改进:对h(x)作限制,使其总是小于实际最小距离h(x)≤ h* (x),具有完备性【与或图】Q与Q1,Q2与等价(即Q可以分解为Q1+Q2)Q1与{Q1i},{Q1i’}或等价(即Q1可以转换为{Q1i}或{Q1i’})【与或图中的概念】本原问题:直接可解的问题。
终止节点:本原问题对应的节点端节点:无子节点的节点与节点:子节点为与关系或节点:子节点为或关系【与或图的广度/深度搜索】Step1:S0放入OPEN表Step2:OPEN表第一个点(记为N)取出放入CLOSED表,冠以编号n。
Step3:若n可扩展:(1)扩展N,其子节点放入OPEN表(深度:尾部,广度:首部)(2)考查这些节点是否终止节点。
若是,放入CLOSED表,标为可解节点,并对先辈点标示。
若S0被标可解,得解。
(3)从OPEN表删除具有可解先辈的节点。
转Step2。
Step4:若N不可扩展:(1)标示N为不可解。
(2)标示先辈节。
若S0被标不可解,失败。
(3)从OPEN表删除具有不可解先辈的节点。
转Step2。
【与或图启发式搜索】由下往上更新函数值,函数值=子节点价值+子节点与父节点距离。
例子见PP3 Ch3.P117-120【博弈树】与结点:对手(MIN)力图干扰MAX的选择。
因此站在我方(MAX)的立场,由MIN出棋的结点具有与结点的性质。
或结点:我方(MAX)力图通往取胜。
MAX出棋的结点具有或结点的性质。
【α剪枝,β剪枝】α剪枝:对MIN节点,若其倒推上确界β不大于MIN的父节点倒推下确界α,即α≥β,则不必扩展该MIN节点其余子节点β剪枝:对MAX节点,若其倒推下确界α不小于MAX的父节点倒推上确界β,即α≥β,则不必扩展该MAX节点其余子节点Ch 3.【离散数学相关定义】命题(proposition):具有真假意义的语句谓词(predicate):刻画个体的性质、状态或个体间的关系,例如P(x,y): x是y的父亲个体域:个体变元的变化范围。
(如P(x,y)中,x,y是变元) 全总个体域:包揽一切事物的集合函数:个体之间的对应关系,例如father(x): 值为x的父亲项:个体常元和变元都是项。
若t1,t2,…,tn是项,则f(t1,t2,…,tn )是项原子公式:若t1,t2,…,tn为项,P(t1,t2,…,tn)称为原子谓词公式,简称原子或原子公式谓词公式:原子公式是谓词公式。
若A、B是谓词公式,则¬ A,A∪B等都是谓词公式辖域:紧接于量词之后被量词作用的谓词公式指导变量:量词后的变量约束变量:量词辖域中,与该量词的指导变元相同的变量自由变量:除了约束变量之外的变量一阶谓词:仅个体变元被量化的谓词二阶谓词:个体变元、函数符号、谓词符号被量化从谓词公式得到命题:(1)把谓词中的个体变元代入个体常元(2)把谓词中的个体变元全部量化如P(x)表示"x是素数", 则∀x P(x),P(a)都是命题合取范式:B1 ∧ B2 ∧…∧B n,如(()())(()())(()())P x Q x Q y R y P z S z∨∧⌝∨∧⌝∨8析取范式:B1 ∨B2 ∨…∨B n,如(()())(D y L a y P x C z P u L u v⌝∧∨⌝∧∨⌝∧⌝,(()())())(,))谓词公式永真性:P对个体域D全部成立,则P在D上永真。
P在全总个体集成立,则P永真谓词公式可满足性:P对个体域D至少有一个个体成立,则P在D上可满足。
【常用逻辑等价式】【常用推理定律】【子句集】文字:原子谓词公式及其否定子句:任何文字的析取【子句集特点】1.没有蕴含词、等值词2.“¬”作用原子谓词3.没有量词( ∀、∃ )4.合取范式5.元素之间变元不同6.集合形式【由谓词公式得到子句集】(对应子句集特点的序号)1.根据蕴含等价式消去蕴含关系2.根据量词转换律、双重否定律、摩根定律转换3.存在量词:受∀x约束,则定义f(x)替换y (Skolem函数)不受∀x约束,常量代替y (Skolem常量) 全称量词:直接消去4.根据分配率合取5.各个合取子句变量改名6.把合取符号替换为逗号,组成集合【Skolem标准型】消去存在量词,把全称量词移到最左,右式为合取,如∀x [P(x,f(x)) ∧¬ R(x,g(x)) ]Skolem标准型与原公式一般并不等价【命题逻辑中的归结原理定义】逻辑结论与前提:G是F1、F2 、…、F n的逻辑结论,当且仅当对每个解释I,如果F1、F2 、…、F n都为真,则G也为真。
F1、F2 、…、F n为G的前提。
互补文字:L与¬L归结式:C1包含L1,C2包含L2,L1与L2互补。
把L1和L2删除,并把剩余部分析取,得到C12亲本子句:上例中C1与C2消解基:上例中L1与L2例如:【归结原理定理】1.谓词公式A不可满足当且仅当其子句集S不可满足。
2.G是公式F1、F2、…、F n的逻辑结论,当且仅当F1 ∧F2 ∧…∧F n => G3.G是公式F1、F2、…、F n的逻辑结论,当且仅当F1 ∧F2 ∧…∧F n ∧ ¬ G不可满足4.归结式是其亲本子句的逻辑结果5.子句集S的C1,C2替换为C12得到S1,则S1不满足=>S不满足6.子句集S添加C12得到S2,则S2不满足=>S不满足【归结反演法】否定目标公式G,¬ G加入到F1 ∧F2 ∧…∧F n中,得到子句集S。
对S进行归结,并把归结结果并入S,直到得到空子句,原问题得证。
【替换定义】替换:{t1/x1, t2/x2, …, tn/xn}替换的分子:t1, t2, …, tn是项替换的分母:x1, x2, …, xn是互不相同的个体变元(ti,,xi不同,xi不循环出现在tj中,如{f(x)/y,g(y)/x}不是替换) 基替换:t1, t2, …, tn是不含变元的项(称为基项)空替换:没有元素的替换,记作ε表达式:项、原子公式、文字、子句的统称基表达式:没有变元的表达式例/特例:对公式E实施替换θ,记为Eθ,所得结果称为E在θ下的例复合/乘积:θ={t1/x1, t2/x2, …, tm/xm},λ={u1/y1, u2/y2, …, un/yn},删除{t1λ/x1,t2λ/x2,…,tmλ/xm ,u1/y1,u2/y2,…,un/yn}中:(1)tiλ/xi 当tiλ=xi(2)ui/yi 当yi∈{x1,…, xn}得到θ与λ的复合或乘积,记为θ•λ例如:θ= {a/x, f(u)/y ,y/z},λ={b/u,z/y,g(x)/z}从{a/x,f(b)/y ,z/z,b/u,z/y,g(x)/z},删去:z/z,z/y,g(x)/z得到:θ·λ= {a/x,f(b)/y ,b/u}【合一定义】合一:F1λ=F2λ=…=Fnλ则λ为F的合一,F为可合一的(一个公式的合一一般不唯一)最一般合一:σ为F的一个合一,如果对F任何合一θ都存在λ使得θ=σ•λ,则σ为F的最一般合一,极为MGU(一个公式集的MGU不唯一)差异集:S是具有相同谓词名的原子公式集,从各公式左边开始,同时向右比较,直到发现第一个不都相同的项为止,用这些项的差异部分组成的集合【合一算法】Step1:置k=0,Fk=F,σk =ε;Step2:若Fk只含有一个谓词公式,则算法停止,σk就是最一般合一;Step3:求Fk的差异集Dk;Step4:若Dk中存在元素xk和tk ,其中xk是变元,tk 是项且xk不在tk中出现,则置Sk +1=Fk{tk/ xk} ,σk+1= σk •{tk/ xk} ,k=k+1然后转Step2;Step5:算法停止,F的最一般合一不存在。
对任一非空有限可合一的公式集,一定存在最一般合一,而且用合一算法一定能找到最一般合一【合一算法例子】求公式集F={Q(a,x,f(g(y))),Q(z,h(z,u),f(u))}的最一般合一解:解k=0;F0=F,σ0=ε,D0={a,z}RSPC∨∨⌝=12σ1=σ0·{a/z}= {a/z}F1= F0{a/z}= {Q(a,x,f(g(y))),Q(a,h(a,u),f(u))}k=1;D1={x, h(a,u)}σ2= σ1·{h(a,u) /x}={a/z,h(a,u) /x}F2= F1{a/z, h(a,u) /x}= {P(a, h(a,u) ,f(g(y))),P(a,h(a,u),f(u))}k=2;D2={g(y),u}σ3={a/z ,h(a, g(y)) /x ,g(y)/u}F3= F2{g(y)/u}= {P(a,h(a,g(y)),f(g(y)))}S3单元素集,σ3为MGU。
【谓词逻辑中的归结原理定义】二元归结式(二元消解式):(C1σ-{L1σ})∪(C2σ-{L2σ}),其中:亲本子句:C1,C2为无相同变元的子句消解文字:L1,L2σ为L1和¬L2的最一般合一因子:C σ。
其中σ为C的子句文字的最一般合一单因子:C σ为单元句子【归结式】子句的C1,C2归结式,是下列二元归结式之一:(1)C1和C2的二元归结式;(2)C1和C2的因子的二元归结式;(3)C1因子和C2的二元归结式;(4)C1的因子和C2的因子的二元归结式。
归结注意事项:(1) 两个子句不能含有相同的变元(2) 归结的子句内部含有可合一的文字,则需进行简化【谓词逻辑的消解原理/归结原理】谓词逻辑中的消解(归结)式是它的亲本子句的逻辑结果:C1 C2=>(C1σ -{L1σ})∪(C2σ-{L2σ})【谓词逻辑的定理】如果子句集S是不可满足的,那么必存在一个由S推出空子句的消解序列。