人工智能原理与应用 教案

人工智能原理与应用

PrinciplesandApplicationofArtificialIntelligence课程简介本课程主要讲述人工智能的基本概念、基本方法，会用搜索算法、推理方法和机器学习求解简单问题，如证明定理、机器推理、建造简单的专家系统，自然语言分析和理解。要求了解人工智能的提出，几种智能观，人工智能重要的研究领域，以及人工智能求解问题的方法与传统的数学方法的不同；掌握启发式搜索概念，会用搜索方法求解简单问题掌握归结推理方法，会用归结法证明定理，求解问题。掌握一种不确定推理方法，会建造带有不确定推理的专家系统。了解其它的推理方法；掌握知识的表示方法，会用来表达某一具体的场景；掌握机器学习概念和学习模型，会用实例学习方法进行学习，了解数据挖掘的过程，会用关联规则挖掘算法做数据挖掘；掌握自然语言理解的过程，会用基本的切分和语法分析方法做自然语句分析；理解神经网络实现智能的另一种观点。掌握BP神经网的工作原理，会用来求解（如识别）问题；了解遗传算法（GA）概念及如何使用遗传算法参考资料：《人工智能原理与应用》，张仰森，高等教育出版社《人工智能》，蔡自兴《人工智能原理》，石纯一黄昌宁王家钦编著，清华大学出版社《人工智能》（上下册），陆汝铃编著，科学出版社，1996《人工智能与知识工程》，田盛丰、黄厚宽，中国铁道出版社，1999《高级人工智能》，史忠植，科学出版社，1998《人工智能基础》，高济、朱森良、何钦铭，高等教育出版社，2002第一章人工智能概述1.1人工智能的起源与发展计算机所能处理对象的改变：纯粹数值计算→非数值计算（自然语言理解、图象语音识别、专家系统、机器博弈系统等等符号知识处理）试探性搜索、启发式搜索、不确定性推理方法更符合人类思维过程。也就是说在解决这类问题时，没有算法解或即使有算法解但在当今计算技术不能实现。对这类问题可行的解决方法是搜索、试探，加上经验的启发式知识。这是一种来自专门领域的经验知识，限于特定场合，经常会取得成功但又不能保证必然成功，常能求得有关问题的满意解答。医生一定能根据病人的症状诊断出是何种疾病吗？我们能用传统的算法设计一个程序进行疾病诊断吗？能用传统的算法设计一个程序能理解自然语言所组成的文档的含义吗？以上原因促使人工智能学科的诞生。主要经历了以下几个阶段：孕育期（1956年以前）——从理论、技术和物质上奠定基础成长期（1956－1972）——逻辑推理机程序、跳棋程序、通用问题求解（GPS：GeneralProblemSolver）、人工智能程序设计语言LISP/PROLOG发展期（1972－）——知识工程、专家系统（MYCIN，探矿系统）学习期1.2什么是人工智能1.什么是人类智能？有何特点？计算机到底能不能有人类智能？英国数学家Turing于1950提出的著名的Turing实验。识别、推理、联想、自学习...（人脑的智能很复杂！）计算机到底能不能有人类智能，至今没有完整的论证（人工智能是一门正在探索和发展的学科，至今还没有完全形成完整的理论体系。目前人工智能与人脑的智能还相差很远）2.什么是人工智能？人工智能简称为AI（ArtificialIntelligence）,是研究如何制造出智能机器或智能系统，来模拟人类智能活动、延伸人类智能的学科。已实现的人工智能系统：第一个人工智能专家系统DENDRAL,能根据有机化合物的质谱数据，推断出给有机化合物的分子结构，该系统得到甚至超过化学专家水平。该系统是由Stanford大学的Feigenbaum领导研制成功的。医疗专家系统MYCIN探矿专家系统PROSPECTOR1995年美国智能机器人驾驶汽车以55km/h速度从东部一直开到西部（机器视觉）1997年国际象棋大师卡斯帕罗夫与IBM深蓝巨型机上的博弈系统对弈自然语言理解系统机器翻译系统机器证明系统（证明了“四色问题”、数学中的定理）1.3AI的研究途径、方法、不同学派1．目标：近期目标：使机器更聪明远期目标：探讨研制智能机2.方法、途径仿生学方法：对人脑思维进行生理学模拟，通过微观方法直接模拟人脑和神经系统的结构功能计算机方法：利用计算机科学的观点，从宏观上模拟人的智能活动数学方法：建立数学模型，利用算法求解问题心理学方法：建立心理学模型，利用启发式程序求解问题3．人工智能研究的各种学派及其理论功能模拟，符号演绎模拟人脑的逻辑思维，将问题和知识表示成某种逻辑网络，采用符号推演的方法，实现搜索、推理、学习等功能。这种方法目前还在使用，人工智能研究中的很多成果都是用该方法取得的，如定理证明，自动推理，专家系统、博弈系统等。采用这种方法的研究者称为心理学派或逻辑学派或符号主义，代表人物是NILSSON，本课程就是讲解这种研究方法。结构模拟，神经网络计算根据人脑的生理结构和工作机理，研究和实现计算机智能。因为人脑是由神经细胞组成的神经网络，所以该研究途径就是用人工神经元组成的人工神经网络模型来存储信息和知识，用神经计算（数值计算）的方法实现自学习、联想、识别和推理功能。神经网络具有高度的并行分布性。该研究方法适于实现图象、声音信息识别。采用这种研究途径称为生理学派或连接主义，代表人物是Newell行为模拟，控制进化这种方法模拟人在控制过程中的智能活动和行为特性（自寻优，自适应，自学习），强调“现场AI”（situatedAI）即智能系统或智能机器能与环境交互，能对环境进行感知从而表现出智能行为，也就是说智能行为不需要知识从而与“符号主义”相悖。这种方法的研究者称为行为主义、进化主义或控制论学派。代表人物是MIT的Brooks教授。人工智能是引起争议最多的学科之一,因而各种研究学派在发展的过程都经历了许多挫折.通过什么途径有效地实现智能(如符号演绎推理,知识工程,神经网络计算,图搜索技术,不确定推理等).人工智能的研究范围问题,一般认为包括:知识表示,推理技术,自然语言理解,知识工程,计算机视觉等许多方面.引起争议的原因,第一是由于边界不分明,某些分支与数学有交界(如定理证明,谓词逻辑),或与语言学有交界(如自然语言理解),或与心理学有交界(如认知模型),或与电子学机械学有交界(如计算机视觉,机器人).第二是由于科学的发展,各分支的内容在不断的变化.第三,随着研究工作的深入,一些传统的观念在发生变化,例如在历史上认为数值计算发展到符号演算是AI的一个重要特征,但在近年的研究中,计算机视觉和机器人学的研究中又回到了数值计算的现象,提高了数学在人工智能研究中的地位.1.4AI的研究领域搜索算法：状态空间图、博弈树搜索推理方法：归结推理、不确定性推理自然语言理解：不仅能识别文字而且能理解文本含义的机器系统模式识别（图象与语音识别）知识工程（知识获取、知识表示、知识数据库、知识运用等一系列知识处理技术，是以知识为中心来组织智能系统）神经网络技术专家系统机器人1.5人工智能求解方法的特点AI研究的是以符号表示的知识而不是数值数据为研究对象；AI中采用的启发式搜索算法（HeuristicResearchAlgorithm）而不是常规的算法（Algorithm）控制结构与知识是分离的允许出现不正确的答案1.6人类智能和人工智能1．人类智能特性 感知能力思维能力反应能力2．人工智能特性 机器感知能力机器思维能力（知识表示）机器行为能力第二章知识表示2.1知识及其表示1.知识的概念Feigenbaum认为知识是经过削减、塑造、解释和转换的信息。简单地说，知识是经过加工的信息。Bernstein说知识是特定领域的描述、关系和过程组成。Hayes-Roth认为知识是事实、信念和启发式规则。知识可从（范围，目的，有效性）加以三维描述。其中知识的范围是由具体到一般，知识的目的是由说明到指定，知识的有效性是由确定到不确定。例如“为了证明A→B，只需证明A∧~B是不可满足的”这种知识是一般性、指示性、确定性的。而像“桌子有四条腿”这种知识是具体的、说明性、不确定性。知识表示是研究用机器表示知识的可行性、有效性的一般方法，是一种数据结构与控制结构的统一体，既考虑知识的存储又考虑知识的使用。知识表示可看成是一组描述事物的约定，以把人类知识表示成机器能处理的数据结构。2.人工智能系统所关心的知识一个智能程序高水平的运行需要有关的事实知识、规则知识、控制知识和元知识。事实：是有关问题环境的一些事物的知识，常以“...是...”的形式出现。如事物的分类、属性、事物间关系、科学事实、客观事实等，在知识库中属于低层的知识。如雪是白色的、鸟有翅膀、张三李四是好朋友。规则：是有关问题中与事物的行动、动作相联系的因果关系知识，是动态的，常以“如果...那么...”形式出现。特别是启发式规则是属于专家提供的专门经验知识，这种知识虽无严格解释但很有用处。控制：是有关问题的求解步骤，技巧性知识，告诉怎么做一件事。也包括当有多个动作同时被激活时应选哪一个动作来执行的知识。元知识：是有关知识的知识，是知识库中的高层知识。包括怎样使用规则、解释规则、校验规则、解释程序结构等知识。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上2.3产生式表示法产生式是一种知识表达方法，具有和Turing机一样的表达能力。2.3.1事实与规则的表示事实可看成是断言一个语言变量的值或是多个语言变量间的关系的陈述句，语言变量的值或语言变量间的关系可以是一个词。不一定是数字。如雪是白色的，其中雪是语言变量，其值是白色的。John喜欢Mary，其中John、Mary是两个语言变量，两者的关系值是喜欢。一般使用三元组（对象，属性，值）或（关系，对象1，对象2）来表示事实，其中对象就是语言变量，若考虑不确定性就成了四元组表示（增加可信度）。这种表示的机器内部实现就是一个表。如事实“老李年龄是35岁”，便写成（Lee,age,35）事实“老李、老张是朋友”，可写成（friend,Lee,Zhang）对于规则是表示事物间的因果关系，以下列形式表示：condition->actioncondition作为前件或模式，而action称作动作或后件或结论。前件部分常是一些事实Ai的合取，而结论常是某一事实B，如考虑不确定性，需另附可信度度量值。2.3.2产生式系统的组成和推理多数较为简单的专家系统（ExpertSystem）都是以产生式表示知识的，相应的系统称作产生式系统。产生式系统，由知识库和推理机两部分组成。其中知识库由规则库和数据库组成。规则库是产生式规则的集合，数据库是事实的集合。规则是以产生式表示的。规则集蕴涵着将问题从初始状态转换解状态的那些变换规则，规则库是专家系统的核心。规则可表成与或树形式，基于数据库中的事实对这与或树的求值过程就是推理。数据库中存放着初始事实、外部数据库输入的事实、中间结果事实和最后结果事实。推理机是一个程序，控制协调规则库与数据库的运行，包含推理方式和控制策略。产生式系统的推理方式有正向推理、反向推理和双向推理正向推理：从已知事实出发，通过规则库求得结论，或称数据驱动方式。推理过程是规则集中的规则前件与数据库中的事实进行匹配，得匹配的规则集合。从匹配规则集合中选择一条规则作为使用规则。执行使用规则的后件。将该使用规则的后件送入数据库中重复这个过程直至达到目标具体说如数据库中含有事实A，而规则库中有规则A->B，那么这条规则便是匹配规则，进而将后件B送入数据库中。这样可不断扩大数据库直至包含目标便成功结束。如有多条匹配规则需从中选一条作为使用规则，不同的选择方法直接影响着求解效率，选规则的问题称作控制策略。正向推理会得出一些与目标无直接关系的事实，是有浪费的。反向推理：从目标（作为假设）出发，反向使用规则，求得已知事实，或称目标驱动方式，推理过程是：规则集中的规则后件与目标事实进行匹配，得匹配的规则集合；从匹配的规则集合中选择一条规则作为使用规则；将使用规则的前件作为子目标；重复这个过程直至各子目标均为已知事实成功结束；如果目标明确，使用反向推理方式效率较高。双向推理：同时使用正向推理又使用反向推理。2.3.3产生式表示的特点产生式表示格式固定，形式单一，规则（知识单位）间相互较为独立，没有直接关系使知识库的建立较为容易，处理较为简单的问题是可取的。另外推理方式单纯，也没有复杂计算。特别是知识库与推理机是分离的，这种结构给知识的修改带来方便，无须修改程序，对系统的推理路径也容易作出解释。所以，产生式表示知识常作为构造专家系统的第一选择的知识表示方法。2.4语义网络表示法逻辑表示法和产生式表示法常用于表示有关论域中各个不同状态间的关系，然而用于表示一个事物同其各个部分间的分类知识就不方便了。槽（slot）与填槽表示方法便于表示这种分类知识。语义网络和框架表示方法就属于其中的两种。2.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链用于表示一个结点是另一个结点的属性例：苹果的语义网络2.4.2语义网络表示下的推理语义网络表示下的推理方法不像逻辑表示法和产生式表示法的推理方法那样明了。语义网络表示法是依匹配和继承来进行推理的。最简单的isa关系下的推理是直接继承，如：也可以将语义网络引入逻辑含义，表示出∧，∨，～关系，便可以使用归结推理法。还有人将语义网络中的结点看成有限自动机（DFA），为寻求几个概念间的关系，起动相应的自动机，如有回合点便可求得解答。2.5框架表示法2.5.1框架理论1975年Minsky的论文“Aframeworkforrespresentingknowledge”中提出了框架理论。其基本观点是人脑已存储有大量典型情景，当人面临新的情景时，就从记忆中选择一个称为框架的基本知识结构，这个框架是以前记忆的一个知识空框，而其具体内容依新的情景而改变，对这空框的细节加工修改和补充，形成对新情景的认识又记忆于人脑中。框架理论将框架视作的知识单位，将一组有关的框架连接起来便形成框架系统。系统中不同框架可以有共同结点，系统的行为由系统内框架的变化来表现的。推理过程是由框架间的协调来完成的。框架表示法是一种适应性强、概括性高、结构化良好、推理方式灵活又能把陈述性知识与过程性知识相结合的知识表示方法。2.5.2框架结构框架是由若干结点和关系（统称为槽slot）构成的网络。是语义网络一般化形式化的一种结构，同语义网络没有本质区别。将语义网络中结点间弧上的标注也放入槽内就成了框架表示法。框架是表示某一类情景的结构化的一种数据结构。框架由框架名和一些槽（slot）组成，每个槽有一些值，槽值可以是逻辑的、数字的，可以是程序、条件、默认值或是一个子框架。槽值含有如何使用框架信息、下一步可能发生的信息、预计未实现该如何做的信息等。框架的一般格式：FRAMEWORK：<frameworkname><slot1><face11>:value...<face1n>:value<slot2><face21>:value...<face2n>:value...例：framework:<大学教师>类属：<教师>学历：（学士，硕士，博士）专业：<学科专业>职称：（助教，讲师，副教授，教授）外语：范围：（英，法，德，...）默认：英水平：（优、良、中、差）默认：良2.5.3框架表示下的推理框架表示法没有固定的推理机理。但框架系统的推理和语义网络一样遵循匹配和继承的原则，而且框架中如if-needed、if-added等槽的槽值是附加过程，在推理过程中起重要作用。如确定一个人的年龄，已匹配的知识库中的框架为槽名年龄：NILif-needed:ASKif-added:CHECK在推理的过程中便启动了if-needed和if-added两个槽的附加过程ASK和CHECK。4.5.4框架与产生式表示法的比较

productionframework知识表示单位规则框架推理固定、与知识库独立可变，与知识库成一体建立知识库容易困难通用性低高应用简单问题复杂问题用户初学者专家2.6面向对象的表示法2.7脚本表示法2.8过程表示法2.9状态空间表示法：用来表示问题及其搜索过程的一种方法。1．问题状态空间的构成（1）状态：是描述问题求解过程中不同时刻状况的数据结构。一般用一组变量的有序集合表示：Q＝（q0,q1,q2,…,qn）,其中qi为集合的分量，称为状态变量。当一个分量以确定的值时，就得到一个具体的状态。（2）算符：引起状态中某些分量发生变化，从而使问题由一个状态转变为另一个状态的操作。（3）状态空间：由表示一个问题的全部状态及一切可用算符构成的集合。一般由三部分构成：问题的所有可能的初始状态构成的集合S，算符集合F，目标状态集合G，用一个三元组表示：（S，F，G）状态空间的图示形式称为状态空间图，其中，节点表示状态，有向边表示算符。（4）问题的解：从问题的初始状态集S出发，经过一系列的算符运算，到达目标状态，由初始状态到目标状态所用算符的序列就构成了问题的一个解。2．用状态空间表示问题的步骤（1）定义问题状态的描述形式（2）用所定义的状态描述形式吧问题的所有可能的状态都表示出来，并确定出问题的初始状态集合描述和目标状态集合描述。（3）定义一组算符，使得利用这组算符可把问题由一种状态转变到另一种状态。3．利用状态空间求解问题的过程例：二阶Hanoi塔问题（见P72）解：第一步，定义问题状态的描述形式第二步，用所定义的状态描述形式把问题的所有可能的状态都表示出来，并确定出问题的初始状态集合描述和目标状态集合描述第三步，定义一组算符2.10与/或树表示法1、与或树的概念用一个类似图的结构来表示把问题归约为后继问题的替换集合，画出归约问题图。例如，设想问题A需要由求解问题B、C和D来决定，那么可以用一个与图来表示；同样，一个问题A或者由求解问题B、或者由求解问题C来决定，则可以用一个或树来表示。2、与或树的有关术语父节点是一个初始问题或是可分解为子问题的问题节点；子节点是一个初始问题或是子问题分解的子问题节点；或节点只要解决某个问题就可解决其父辈问题的节点集合；与节点只有解决所有子问题，才能解决其父辈问题的节点集合；弧线是父辈节点指向子节点的圆弧连线；终叶节点是对应于原问题的本原节点。3、与或树的有关定义可解节点与或树中一个可解节点的一般定义可以归纳如下：(1)终叶节点是可解节点(因为它们与本原问题相关连)。(2)如果某个非终叶节点含有或后继节点，那么只有当其后继节点至少有一个是可解的时，此非终叶节点才是可解的。(3)如果某个非终叶节点含有与后继节点，那么只要当其后继节点全部为可解时，此非终叶节点才是可解的。不可解节点不可解节点的一般定义归纳于下：(1)没有后裔的非终叶节点为不可解节点。(2)如果某个非终叶节点含有或后继节点，那么只有当其全部后裔为不可解时，此非终叶节点才是不可解的。(3)如果某个非终叶节点含有与后继节点，那么只要当其后裔至少有一个为不可解时，此非终叶节点才是不可解的。4、与或树构树规则(1)与或树中的每个节点代表一个要解决的单一问题或问题集合。树中所含起始节点对应于原始问题。(2)对应于本原问题的节点，叫做终叶节点，它没有后裔。(3)

对于把算符应用于问题A的每种可能情况，都把问题变换为一个子问题集合；有向弧线自A指向后继节点，表示所求得的子问题集合。(4)一般对于代表两个或两个以上子问题集合的每个节点，有向弧线从此节点指向此子问题集合中的各个节点。(5)在特殊情况下，当只有一个算符可应用于问题A，而且这个算符产生具有一个以上子问题的某个集合时，由上述规则3和规则4所产生的图可以得到简化。第三章推理方法谓词逻辑是一种表达力很强的形式语言，谓词逻辑及其推理方法是人工智能中知识表示方法,机器推理,定理证明的基本方法。另外谓词逻辑中的替换合一技术，也是符号推理中模式匹配的基本技术。本章主要讲解基于谓词逻辑的归结演绎推理。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称为后件，其真值表如下所示：ABA->B001011100111A<->B等价于(A->B)∧(B->A)一些概念：永真式：真值为T的命题公式称为永真式或重言式或有效的。永假式：真值为F的命题公式称为永假式或不可满足的。非永真式：不是永真式的命题公式；可满足式：不是永假公式的命题公式；原子公式:不含任何连接词的命题公式称为原子公式或称原子.例如P,Q文字:原子公式及其否定形式称为文字.例如P,～L子句:文字的析取称为子句.例如:P∨R∨～Q互补文字：设L为一个文字，则称L与～L为互补文字。一些有用的等价关系：～～A<=>A双重否定A∧A<=>A等幂律A∨A<=>AA∧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∧～BA→B<=>～A∨B蕴含表达式A<->B<=>(A→B)∧(B→A)等价表达式A∧T<=>AA∧F<=>FA∨T<=>TA∨F<=>AA∧～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下必有R(C1,C2)也为真。证：设I是使C1，C2为真的任一解释，若在I下P为真，从而～P为假，则C2'必为真，那么R(C1,C2)=C1'∨C2'为真。若在I下P为假，则C1'必为真，那么R(C1,C2)=C1'∨C2'为真。从而证明了C1∧C2=>R(C1,C2)，即归结式是子句的逻辑结论。特别地，当C1=P，C2=～P时，R(C1,C2)=□，记作为空子句。显然C1，C2同时为真是矛盾，或者说空子句□体现了矛盾。4命题逻辑的归结推理过程(1)利用逻辑蕴含式和逻辑等价式将命题公式化成合取范式(子句的析取)(2)子句集：将若干个子句的合取式中的合取词∧换成逗号，形成的集合称为子句集。(3)从子句集S出发，仅只对S的子句间使用归结推理规则（即求归结式），并将所得归结式仍放入S中，进而再对新子句集使用归结推理规则，重复这些步骤直到得到空子句□（说明有矛盾）。便说明S是不可满足的，从而与子句集S对应的定理是成立的。例：证明(P→Q)∧～Q==>～P证：先将已知以及结论的反化成合取范式(～P∨Q)∧～Q∧(～～P)==>(～P∨Q)∧～Q∧P，建立子句集S=｛～P∨Q，～Q，P｝对S作归结(1)～P∨Q(2)～Q(3)P(4)～P..............对(1)(2)求归结式(5)□...............对(3)(4)求归结式得证。例:证明(P→Q)∧(R→～Q)==>(R→～P)证明:将已知以及结论的反化成合取范式==>(～P∨Q)∧(～R∨～Q)∧(～(～R∨～P))==>(～P∨Q)∧(～R∨～Q)∧R∧P化成子句集S=｛～P∨Q，～R∨～Q，R,P｝,对S做归结:(1)～P∨Q(2)～R∨～Q(3)R(4)P(5)～Q...(2)(3)归结(6)Q...(1)(4)归结(7)□...(5)(6)归结3.1.3谓词公式的子句集1合取范式和析取范式（1）合取范式：若谓词公式A有如下形式B1∧B2∧...∧Bn,其中Bi(i=1,2,...n)形如L1∨L2∨...∨Ln，并且L1,L2,...Ln都是文字。例：(P(x)∨～Q(y))∧(～P(x)∨R(x,y))∧(～Q(y)∨～R(x,y))应用逻辑等价式可以将任一谓词公式化成合取范式。（2）析取范式：若谓词公式A有如下形式B1∨B2∨...∨Bn,其中Bi(i=1,2,...n)形如L1∧L2∧...∧Ln，并且L1,L2,...Ln都是文字。例：(P(x)∧～Q(y)∧R(x,y))∨(～P(x)∧R(x,y))应用逻辑等价式和逻辑蕴含式可以将任一谓词公式化成析取范式。（3）前束范式:将所有的量词都放在谓词公式的前面。如xy(P(x,y)∧Q(a)∧R(z))就是前束范式。x(N(x)∧yD(y,x))就不是前束范式。前束范式可分成前束合取范式和前束析取范式。化成前束合取范式的步骤：step1:去掉多余的量词，即没意义的量词step2:将同名的约束变元与自由变元改名，使它们不同名。消去∧，∨，~以外的连接词A->B.............~A∨BA<->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):表示xy||uvE(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.4Herbrand理论：证明一个谓词公式的不可满足性是困难的，这是因为谓词中个体变量的论域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域）就具有这样的性质。1H域设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=H0H2=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也是可数集。2H解释由子句集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--S|I=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→2f(a,a)→f(2,2)→1f(a,f(a,a))→f(2,1)→2f(f(a,a),a)→f(f(2,2),2)→f(1,2)→2f(f(a,a),f(a,a))→f(1,1)→1...P(a)→P(2)→TQ(a,a)→Q(2,2)→FP(f(a,a))→P(1)→TQ(a,f(a,a))→Q(2,1)=TQ(f(a,a),a)→Q(1,2)=TQ(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)),...}显然S|I*=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于是由S|I=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)),...}S|I1*=T定理：设I是S的论域D上的解释，存在对应于I的H解释I*，使得若有S|I=T,必有S|I*=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为失败结点。同样的方法可看出每个分支上都存在失败结点。4Herbrand定理定理一：子句集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(MostGeneralUnifier)。例：设子句集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）的算法，即合一算法（UnificationAlgorithm）:①置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))→T(z,y))T(wang,Li)......wang,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下为真的子句放入S2'中，于是有：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中子句（该子句称为顶子句）外,其后各次归结则至少要有一个亲本子句是上次归结的结果.线性归结可用一个归结演绎树加以表示,例如上例中的归结过程:线性归结策略是完备的4.输入归结策略每次参加归结的两个亲本子句，必须至少有一个子句是初始子句集S中的子句。输入归结策略是不完备的。例如子句集S=｛P∨Q，～P∨Q，P∨～Q，～P∨～Q｝是不可满足的，但用输入归结策略不能导出空子句5.单元归结策略每次归结都有一个子句是单元（只含一个文字即原子或其否定）子句或单元的因子时的归结称作单元归结。单元归结也是不完备的。3.2不确定性推理概述3.2.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推理DempsterShafer在1976年提出的证据理论Zadeh在1978年提出的可能性理论，1983年提出的模糊逻辑和逻辑推理Nilsson在1986年提出的概率逻辑Pearl在1986年提出的信任网络3.2.2不确定性推理方法在以产生式作为知识表示的MYCIN系统中，第一次使用了不确定推理方法，给出了可信度作为不确定性的度量。1.规则的不确定性度量规则以A->B表示，其中前提A可以是一些命题的合取，引入可信度CF(B,A)作为规则A->B的不确定性度量。其中引入P(B)表示结论B为真的概率,P(B|A)表示在规则A->B,证据A为真的作用下结论B为真的概率。则可信度CF（B，A）表示证据A为真时，相对于P（～B）=1-P（B）来说A对B为真的支持程度（当CF（B，A）≥0），或