人工智能技术导论

1、人工智能技术导论第1页，共187页，2022年，5月20日，10点57分，星期日参考书人工智能马少平、朱小燕编著，清华大学出版社人工智能及其应用蔡自兴、徐光祐编著，清华大学出版社 Artificial Intelligence A New Synthesis(人工智能) Nils J.Nilsson 第2页，共187页，2022年，5月20日，10点57分，星期日第一章 人工智能概述人工智能的概念人工智能的研究途经与方法人工智能的分工领域人工智能的基本技术人工智能的发展概括第3页，共187页，2022年，5月20日，10点57分，星期日什么是人工智能人工智能(Artificial Intell

2、igence)是指由计算机实现的人造智能。作为一门学科，人工智能可定义为：人工智能是一门研究如何构造智能机器（智能计算机）或智能系统，使它能模拟、延伸、扩展人类智能的学科人工智能是一门交叉边缘学科，与人工智能有关的学科有：计算机科学、数学、语言学、神经生理学、神经心理学、脑科学、认知科学、逻辑学、控制论等第4页，共187页，2022年，5月20日，10点57分，星期日什么是人的智能智能是人脑的属性和产物。智能具有的主要特征：A、具有感知能力。通过视觉、听觉、触觉、味觉和嗅觉感知外部世界。B、具有记忆与思维能力。记忆能存储由感知器官感知到的外部信息以及由思维所产生的知识。思维用于对记忆的信息进行

3、处理。思维可分为逻辑思维和形象思维。C、具有学习能力及自适应能力。D、具有行为能力。发现规律 应用规律 分析问题 解决问题图灵测试中文屋子问题（约翰希尔勒）第5页，共187页，2022年，5月20日，10点57分，星期日为什么要研究人工智能现有计算机系统的局限性。 智能低下、缺乏自学习、自适应、自优化能力。人类智能的局限性。 学习能力因人而异、学习速度慢、效率低。信息化社会的迫切要求。第6页，共187页，2022年，5月20日，10点57分，星期日人工智能的目标近期目标：使现有的电子数字计算机能模拟人类的部分智能行为。远期目标：制造智能计算机，使计算机具有看、听、说等感知和交互能力、具有联想、

4、推理、理解、学习等高级思维能力，还要有分析问题、解决问题和发明创造的能力。深蓝（32CPU，200万次/秒，200万个棋局）第7页，共187页，2022年，5月20日，10点57分，星期日人工智能的表现形式智能软件智能设备智能网络智能计算机智能机器人智能体(Agent) (艾真体)第8页，共187页，2022年，5月20日，10点57分，星期日人工智能的研究途径与方法结构模拟（神经计算、生理学派、连接主义） 模拟人脑的神经网络结构实现智能。主要特征：1、通过神经元之间的并行协同作用实现信息处理，具有并行性、动态性、全局性。2、通过神经元间分布式的物理联接存储信息。联想记忆、容错性。3、通过神经

5、元间连接强度的动态调整实现自学习和自适应功能。4、善于模拟人类的形象思维过程。第9页，共187页，2022年，5月20日，10点57分，星期日人工智能的研究途径与方法功能模拟（符号主义、心理学派、逻辑学派） 以人脑的心理模型为基础，将问题或知识表示成某种逻辑网络，采用符号推演的方法，实现搜索、推理和学习等功能。主要特征：1、立足于逻辑运算和符号操作，适合于模拟人的逻辑思维过程。2、知识用显式的符号表示，容易表达人的心理模型。3、现有的数字计算机可以方便地实现高速的符号处理。4、能与传统的符号数据库进行链接，易于模块化。5、以知识为基础。第10页，共187页，2022年，5月20日，10点57分

6、，星期日人工智能的研究途径与方法行为模拟（行为主义、进化主义、控制论学派）基于感知-行为模型的研究途径和方法。模拟人在控制过程中的智能活动和行为特征：自寻优、自适应、自组织、自学习。强调智能系统与环境的交互，认为智能取决于感知和行动,智能行为可以不要知识。智能只有放在环境中才是真正的智能，智能的高低体现在对环境的适应性上Brooks，机器虫第11页，共187页，2022年，5月20日，10点57分，星期日人工智能的分支领域基于脑功能模拟的领域划分1、机器感知（信息输入）。使计算机具有类似于人的感知能力，能通过“感知”直接从外界获取信息，是对人的感知的模拟及延伸。机器视觉、机器听觉。相关学科：模

7、式识别（语音识别、图像识别）。 信息-电信号序列-预处理-提取特征-模式匹配2、机器联想。基于内容的联想，与具体存储位置无关。联想存储技术。3、机器推理。又称为计算机推理、自动推理，是人工智能的核心课题之一。推理：从一些已知判断（前提）推出一个新判断（结论）的思维过程。演绎推理、归纳推理、类比推理确定性推理、不确定性推理基于概率逻辑的或然推理(随机性)、基于模糊逻辑的似然推理(模糊性)串行推理、并行推理第12页，共187页，2022年，5月20日，10点57分，星期日人工智能的分支领域4、机器学习。使机器自己获取知识。对人类已有知识的获取、对客观规律的发现、对自身行为的修正。机器学习分为：机械

8、学习、指导学习、解释学习、类比学习、示例学习、发现学习等。这些属于符号学习。另外还有神经网络学习。5、机器理解。图形理解（物景分析）、自然语言理解。理解是感知的延伸和深化。6、机器行为（机器人行动规划）。智能机器人的核心技术，反映了机器人的智能水平解决问题依靠规划功能确定行动步骤和动作序列任务：在一个特定的工作区域中自动生成从初始状态到目标状态的动作序列、运动路径和轨迹的控制程序第13页，共187页，2022年，5月20日，10点57分，星期日人工智能的分支领域基于研究途径和实现技术的领域划分1、符号智能以符号知识为基础，通过符号推理进行问题求解知识工程(知识获取、知识表示、知识管理、知识运用

9、、知识库系统)、符号处理2、计算智能以数据为基础，通过数值计算进行问题求解人工神经网络、进化计算(遗传算法、遗传程序设计、进化规划、进化策略)、模糊技术、人工生命第14页，共187页，2022年，5月20日，10点57分，星期日人工智能的分支领域基于应用领域的领域划分1、难题求解难题的概念路径规划、组合优化、天气预报、股市分析、市场预测、机器博弈NP (Nondeterministic Polynomial) 和NPC (Nondeterministic Polynomial Complete)问题难题求解技术能促进人工智能其他领域的发展2、自动定理证明自然演绎法、判定法、定例证明器、计算机辅

10、助证明四色问题(1976.6,K.Appeel)。3、自动程序设计超级编译系统自动程序综合和自动程序验证。第15页，共187页，2022年，5月20日，10点57分，星期日人工智能的分支领域4、自动翻译。机器翻译。自然语言理解。一边站着一个人他想起来了5、智能控制1965，KS.FU (傅京孙)提出将启发式推理规则用于学习控制系统6、智能管理。人工智能与管理科学、系统工程和计算机技术的结合。7、智能决策。人工智能应用于决策支持系统。8、智能通讯。在通讯的各个环节和层次上实现智能化。如网控、转接、信息转换等。使通讯网随时运行于最佳状态。9、智能仿真。仿真是在三种类型知识-描述性知识、目的性知识和

11、处理知识的基础上产生另一种形式的知识-结论性知识。10、智能CAD。人工智能应用于CAD的设计自动化、智能交互、智能图形学、自动数据采集方面。11、智能CAI。人工智能应用于CAI： 自动生成各种问题与练习、自动选择与调整教学内容和进度、自动生成答案、自然语言理解能力、不断改善教学策略。第16页，共187页，2022年，5月20日，10点57分，星期日人工智能的分支领域基于应用系统的领域划分1、专家系统。基于人类专家知识的程序系统。能模拟专家的思维方式。2、知识库系统。3、智能数据库系统。传统数据库系统+人工智能。4、智能机器人系统。具备感知、思维、人-机通讯和运动能力。第17页，共187页，

12、2022年，5月20日，10点57分，星期日人工智能的分支领域基于计算机系统结构的领域划分1、智能操作系统。并行性、分布性和智能性。2、智能多媒体系统。人工智能与多媒体技术的有机结合。3、智能计算机系统。4、智能网络系统。模糊和神经网络技术应用于网络的业务量预测和控制、资源动态分配、动态路由选择等方面。第18页，共187页，2022年，5月20日，10点57分，星期日人工智能的分支领域基于实现工具与环境的领域划分1、智能软件工具。人工智能程序设计语言，如表处理语言LISP、逻辑程序设计语言PROLOG、面向对象程序设计语言Smalltalk等。知识表示语言FRL、OPS5。专家系统工具、知识工

13、程工具等。2、智能硬件平台。直接支持智能系统开发和运行的机器硬件。第19页，共187页，2022年，5月20日，10点57分，星期日人工智能的分支领域基于体系结构的领域划分集中式人工智能（个体智能）分布式人工智能（群体智能）个体智能的组合或叠加DPS（分布式问题求解），自顶向下MAS（多智能体系统），自底向上第20页，共187页，2022年，5月20日，10点57分，星期日人工智能的基本技术推理技术。推理是智能的核心。推理以逻辑为基础。基于谓词逻辑的自然演绎推理和归结反演推理。基于非标准逻辑如多值逻辑、模态逻辑、时态逻辑、模糊逻辑、非单调逻辑的推理。搜索技术。人工智能的基本技术。许多智能活动的

14、过程，都可以看作或抽象为一个“问题求解”过程。“问题求解”就是在问题空间中进行搜索的过程。盲目搜索、启发式搜索。神经网络搜索。知识表示与知识库技术。知识表示是指知识在计算机中的表示方式。知识表示要符合知识的逻辑结构和物理结构，并适合于计算机存储和处理。知识库由知识构成。知识的组织、管理、维护和优化。第21页，共187页，2022年，5月20日，10点57分，星期日人工智能的基本技术归纳技术。机器自动提取概念、获取知识、发现规律的技术。归纳技术与知识获取和机器学习密切相关。基于符号处理的归纳和基于神经网络的归纳。数据库知识发现（KDD, Knowledge Discovery in Databa

15、se) 和数据挖掘(Data Mining)技术。联想技术。联想记忆，联想存储。第22页，共187页，2022年，5月20日，10点57分，星期日人工智能的发展概况孕育期（1956年之前）1、公元前，Aristotle提出形式逻辑的一些主要定律，三段论至今仍是演绎推理的基本依据。2、培根（1561-1626）曾系统地提出了归纳法。提出“知识就是力量”3、德国数学家Leibniz（1646-1716）提出了万能符号和推理计算的思想，为数理逻辑的产生和发展奠定了基础。4、英国逻辑学家Boole（1815-1864）创立了布尔代数，在思维法则一书中首次用符号语言描述了思维活动的基本推理法则。5、英国

16、数学家Turing于1936年提出理想计算机的数学模型，即图灵机。Turing测试。6、1943年，McCulloch 和 Pitts提出M-P神经元模型。7、1946年，世界上第一台电子计算机诞生。第23页，共187页，2022年，5月20日，10点57分，星期日人工智能的发展概况人工智能学科的产生（1956年） 1956年夏季，McCarthy, Minsky, Lochester, Shannon, More, Samuel, Selfridge, Solomonff, Newell, Simon等十人在Dartmouth大学召开历时两个多月的研讨会，讨论机器智能的有关问题。由McCar

17、thy提出“人工智能”一词，人工智能从此成为一门学科。第24页，共187页，2022年，5月20日，10点57分，星期日人工智能的发展概况符号主义AI发展概况1、形成（1956-1965）（人工智能的推理期。结构良好问题。搜索策略和算法）（1）、1956年，Samuel的跳棋程序。1959,1962（2）、定理证明方面，1956年Newell等的逻辑理论机（LT）程序；1958年，王浩的工作；1965年，Robinson提出的消解原理。（3）、模式识别方面，1959年Selfridge的模式识别程序；1965年Roberts编制了可以分辨积木构造的程序。（4）、问题求解方面。1960年，New

18、ell的通用问题求解(GPS)程序。（5）、1960年，McCarthy研制成功LISP语言。第25页，共187页，2022年，5月20日，10点57分，星期日人工智能的发展概况人工智能的知识期（1965-70年代末）（1）、专家系统方面。1965年，Feigenbaum的专家系统DENDRAL，1968年投入使用。DENDRAL对知识表示、存储、获取和推理的技术为以后的专家系统的建造树立了榜样，对AI的发展产生了深刻的影响。之后著名的专家系统有：医学专家系统MYCIN，地质勘探专家系统PROSPECTOR，计算机配置专家系统R1等。（2）、1969年，国际人工智能联合会议(IJCAI)召开。

19、1970年，“Artificial Intelligence”杂志创刊。（3）、1977年，Feigenbaum在第五届国际人工智能会议上，提出了“知识工程”的概念。发展期（20世纪80年代后） 专家系统与知识工程在理论、技术和应用方面都有长足的进步和发展。出现了多专家系统、大型专家系统、微专家系统、分布式专家系统等。智能管理信息系统、智能决策支持系统、智能控制系统等。第26页，共187页，2022年，5月20日，10点57分，星期日人工智能的发展概况连接主义途径发展概况1、1943年，神经生理学家McCulloch 和Pitts提出M-P神经元模型。1944年，Hebb提出Hebb学习规则。

20、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提出B

21、P算法，解决了多层人工神经元网络的学习问题。1987年6月，第一届国际神经网络大会（IJCNN）召开，盛况空前。目前，NN与专家系统、知识工程成为AI的两个主流方向。NN在智能控制、信号处理、最优化、知识工程等领域都有成功应用。第27页，共187页，2022年，5月20日，10点57分，星期日当前发展趋势1、传统以符号处理为中心的人工智能与神经网络的结合。神经网络：识别 联想 学习 适应，负责对外界的感知和交互专家系统：判断 推理 搜索，负责高层的决策与控制2、新理论、新技术的出现。Fuzzy, Genetic Algorithm, Chaos, Artificial life, Soft C

22、omputing, Computational Intelligence, Rough set, Data Mining, Knowledge discovery in database, Data warehouse, Situated AI, Agent-based distributed AI 等。第28页，共187页，2022年，5月20日，10点57分，星期日第二章 基于谓词逻辑的机器推理谓词、函词、量词个体：研究对象中可以独立存在的具体的或抽象的客体。个体用个体常元或个体变元表示，如x,y,z,a,b,c,等。谓词：描述个体性质及个体之间相互关系的词。 如P、Q、R，等。例、命题“

23、2是素数”中，2是个体，“是素数”是谓词。可表示为P(2).函词（函数）：某些个体是其它个体的函数，描述这种关系的词称为函词。例、命题“小李的父亲是医生”可表示为Doctor(father(Li).量词：存在量词“ ”；全称量词“ ”。例、“任何实数的平方都非负”可表示为 x(R(x) N(s(x)。 “存在偶素数”可表示为 x(E(x) P(x)。第29页，共187页，2022年，5月20日，10点57分，星期日一些命题的表示凡是人都有名字 x(M(x) N(x)不存在最大的整数x(G(x) y(G(y) D(x,y) x(G(x) y(G(y) D(y,x)对所有的自然数，均有X+YXx

24、y(N(x) N(y) S(x,y,x)某些人对某些食物过敏 x y(M(x) F(y) G(x,y)第30页，共187页，2022年，5月20日，10点57分，星期日谓词公式项的定义：1、个体常元和个体变元是项；2、设f是n元函词符号， t1, t2 , , tn是项，则f(t1, t2 , , tn)是项。3、只有有限次使用1，2得到的符号串才是项。原子公式：P是n元谓词， t1, t2 , ,( tn是项，则P(t1, t2 , , tn)称为原子谓词公式(原子公式)(原子)。谓词公式：1、原子公式是谓词公式；2、若A、B是谓词公式，则 A，A B，A B，A B，A B， xA， xA

25、也是谓词公式；3、只有有限次地应用步骤1，2形成的符号串才是谓词公式。辖域： xA 和 xA中，x称为量词的指导(作用)变元，A称为x的辖域。辖域中与该量词的指导变元相同的变元称为约束变元，其它变元(如果存在的话)称为自由变元。例、xP(x)； x(H(x) G(x,y)； xA(x) B(x)约束变元的改名 ：两个规则第31页，共187页，2022年，5月20日，10点57分，星期日部分逻辑蕴含式（p59-p60)析取三段论： A (A B) B假言推理（分离规则）： A (A B) B拒取式： B (A B) A假言三段论： (A B) (BC) A C二难推论: (A B) (A C)

26、(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页，共187页，2022年，5月20日，10点57分，星期日自然演绎推理以谓词公式的等价式

27、及推理定律为基础进行的推理称为自然演绎推理。例见教材p61。推理过程是一个符号变换过程，类似于人们使用自然语言进行推理的思维过程。推理与谓词公式的含义无关，是一种形式推理。自然演绎推理在机器上实施比较困难推理规则太多应用规则需要很强的模式识别能力中间结论的指数递增第33页，共187页，2022年，5月20日，10点57分，星期日子句集定义1 原子谓词公式及其否定称为文字；若干个文字的一个析取式称为一个子句；由r个文字组成的子句称为r-文字子句，1-文字子句称为单元子句，不含任何文字的子句称为空子句，记为或NIL。定义2 对一个谓词公式G，通过一定的步骤得到的子句集合S称为G的子句集。第34页，

28、共187页，2022年，5月20日，10点57分，星期日子句集（1）、利用等价式A B A B和 A B (A B) (B A)消去联结词“ ” 和 “ ”。 （2）、缩小否定联结词的作用范围，使其仅作用于原子公式。可利用下列等价式： A A； (AB) A B， (A B) A B；xA(x) x A(x)， xA(x) x A(x)（3）、重新命名变元名，使不同量词约束的变元有不同的名字。（4）、消去存在量词。若存在量词不在全称量词的辖域内，则用一个常量符号替换该存在量词辖域中的相应约束变元。这样的常量称为Skolem常量；若该存在量词在一个或多个全称量词的辖域内，则用这些全称量词指导变元

29、的一个函数替换该存在量词约束的变元。这样的函数称为Skolem函数。例如x1 x2 xnyP(x1,x2, xn,y)中y可用Skolem函数f(x1,x2, xn)替换为x1 x2 xnP(x1,x2, xn,f(x1,x2, xn)。第35页，共187页，2022年，5月20日，10点57分，星期日子句集（5）、把全称量词全部移到公式的左边。（6）、把全称量词后面的公式利用等价关系A(B C) (AB) (A C)化为子句的合取式，得到的公式称为Skolem标准形。Skolem标准形的一般形式为x1 x2 xnM，其中M是子句的合取式。（7）、消去全称量词。（8）、对变元更名，使子句间无同

30、名变元。（9）、消去合取词 ，以子句为元素组成的集合称为谓词公式的子句集。例：把如下谓词公式化为子句集。 xyP(x,y) yQ(x,y)R(x,y)第36页，共187页，2022年，5月20日，10点57分，星期日子句集求解过程 xyP(x,y) yQ(x,y)R(x,y)1) xyP(x,y) yQ(x,y) R(x,y)2) xyP(x,y) yQ(x,y) R(x,y)3) xyP(x,y) zQ(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

31、,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页，共187页，2022年，5月20日，10点57分，星期日命题逻辑中的归结原理要证明在前提P下结论Q成立，即是证明P Q永真，这只须证明P Q不可满足。根据定理1，只须证明P Q的子句集不可满足。由于子句之间是合取关系，只要有一个子句不满足，则整个子句集不可满足。由于空子句是不可满足的，所以如果

32、子句集中包含空子句，则该子句集是不可满足的。若子句集中不包含空子句，则可通过Robinson提出的归结原理对子句集进行归结，归结过程保证子句集的不可满足性不变。一旦归结出空子句，则证明结束。因此，归结原理把定理的证明化为子句集中归结出空子句的过程。第38页，共187页，2022年，5月20日，10点57分，星期日命题逻辑中的归结原理定义、设L是一个文字，则称L与L为互补文字。定义、设C1、C2是命题逻辑中的两个子句， C1 中有文字L1 ， C 中有文字L，且L1与L互补， 从C1，C中分别删除L1 ， L，再将剩余部分析取起来，构成的新子句C1称为C1与C2的归结式（消解式）， C1，C2称

33、为C1的亲本子句。C1 = PQ R, C2 = Q S, C1 = P R S定理、归结式C1是其亲本子句C1与C2的逻辑结论。推论、设C1，C2是子句集S的两个子句， C1是它们的归结式，则（）若用C1代替C1和C2后得到新子句集S1，则由S1的不可满足性可推出原子句集S的不可满足性。即S1不可满足S不可满足）若把C1加入到S中，得到新子句集S，则S与S在不可满足意义上是等价的。即S2不可满足 S不可满足第39页，共187页，2022年，5月20日，10点57分，星期日命题逻辑中的归结原理例、用归结原理证明R是P, (P Q) R， (SU) Q，U的逻辑结果。求子句集P, (PQ)R,

34、(SU) Q, U, RP, (P Q) R, ( S U) Q, U, RP, P Q R, S Q , U Q, U, R (子句集)归结演绎P Q R R P Q P Q P QQ U Q U U U 第40页，共187页，2022年，5月20日，10点57分，星期日替换与合一问题的提出谓词逻辑和命题逻辑中使用归结原理的差别C1 = P (x) Q (x) , C2 = P (a) R (y)C1 = P (a) Q (a) , C2 = P (a) R (y)定义 一个替换(Substitution)是形如t1/x1 , t2/x2 , tn/ xn 的有限集合，其中t1 , t2 ,

35、tn 是项(替换的分子)， x1, x2 ,xn是互不相同的个体变元(替换的分母)。ti / xi表示用ti代换xi 。 ti与xi不同，xi也不能循环出现在tj中(j=1,2,n)。基替换(t1 , t2 ,tn 均不含变元)、空替换例：a/x, g(c)/y, f(g(b)/z ，g(y)/x, f(x)/y第41页，共187页，2022年，5月20日，10点57分，星期日替换与合一定义7 设t1 / x1, t2 / x2 ,tn / xn 是一个替换，E是一个表达式，把E中出现的所有个体变元xi都用ti 替换，记为E ，得到的结果称为E在下的替换实例(Instance)。Eg：E=P(

36、x,y,g(z), a / x, f(b) /y ,c /z ，E= P(a,f(b),g(c)定义 设t1 / x1, t2 / x2 ,tn / xn ， u1 / y1, u2 / y2 ,um / ym 是两个替换，则将集合t1 / x1, t2 / x2 ,tn / xn，u1 / y1, u2 / y2 ,um / ym 中符合下列条件的两种情形删除： ti / xi ，当ti xi ui / yi ，当yi x1, x2 , xn 得到的集合仍是一个替换，称为与的复合或乘积，记为 例: 设 =f(y)/x,z/y =a/x,b/y,y/z =f(b)/x,y/y,a/x,b/y,

37、y/z=f(b)/x,y/z第42页，共187页，2022年，5月20日，10点57分，星期日替换与合一定义 设S= F1, F2 , Fn 是一个原子谓词公式集，若存在一个替换，使得F1 F2 Fn ，则称为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)

38、/z,a/u，可找到替换=a/u，使得 第43页，共187页，2022年，5月20日，10点57分，星期日替换与合一定义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页，共187页，2022年，5月20日，10点57分，星期日替换与合一设S为一非空有限具有相同谓词名的原子谓词公式集，求S的MGU的算法：(1) 令k=0, Sk=S, k= （ 表示空替换）(2)

39、若Sk只含有一个谓词公式，则算法停止， k就是要求的最一般合一(3) 求Sk的差异集Dk(4) 若Dk中存在元素 xk 和 tk ，其中xk是变元， tk是项且xk不在tk中出现，则置Sk+1 = Sktk /xk ， k+1 = ktk /xk ，k=k+1，然后转步(2) (5) 算法停止，S的最一般合一不存在第45页，共187页，2022年，5月20日，10点57分，星期日替换与合一求S=P(a,x,f(g(y) , P(z,h(z,u),f(u)的MGUk=0S0=S, 0= , D0=a,z1= 0a/z=a/zS1=S0a/z =P(a,x,f(g(y) , P(a,h(a,u),

40、f(u)k=1D1=x,h(a,u)2= 1h(a,u)/x=a/z h(a,u)/x=a/z, h(a,u)/xS2=S1h(a,u)/x= P(a,h(a,u),f(g(y) , P(a,h(a,u),f(u)第46页，共187页，2022年，5月20日，10点57分，星期日替换与合一S2=S1h(a,u)/x= P(a,h(a,u),f(g(y) , P(a,h(a,u),f(u)k=2D2=g(y),u3= 2g(y)/u=a/z, h(a, g(y)/x, g(y)/uS3=S2g(y)/u=P(a,h(a,g(y),f(g(y), P(a,h(a,g(y),f(g(y) = P(a

41、,h(a,g(y),f(g(y)k=3S3为单元素集，所以3为所求的S的MGU说明：MGU可能是不唯一的，如Dk=xk,yk时第47页，共187页，2022年，5月20日，10点57分，星期日谓词逻辑中的归结原理定义12 设C1,C2是两个没有相同变元的子句，L1,L2分别是C1,C2中的两个文字，如果L1与L2有最一般合一 ，则子句C12=(C1-L1) (C2-L2)，称作C1和C2的二元归结式(二元消解式)。 C1和C2称为C12的亲本子句， L1，L2称为消解文字。例：C1=P(x)Q(x) , C2= P(a)R(y), C12=Q(a)R(y)说明：当子句内部有可合一的文字时，应在

42、归结前进行合一，使子句最简例：C1=P(x) P(f(a)Q(x)，则C1=P(f(a)Q(x)归结原理：C1 C2 (C1-L1) (C2-L2)第48页，共187页，2022年，5月20日，10点57分，星期日谓词逻辑中的归结原理归结时的注意事项谓词的一致性. 名称不一致的谓词不能归结 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页，共187页，2022年，5月

43、20日，10点57分，星期日归结反演归结反演：应用归结原理证明定理的过程若F为已知前提的公式集，Q为结论，用归结反演证明Q为真的步骤是：（1）、否定Q，得到Q；（2）、把Q并入到公式集F中，得到F, Q；（3）、把公式集F, Q化为子句集S；（4）、应用归结原理对子句集S中的子句进行归结，并把每次归结得到的归结式都并入S中。如此反复进行，直到出现空子句，就证明了Q为真。定理5（归结原理的完备性）、如果子句集S是不可满足的，则必存在一个由S推出空子句的归结序列。第50页，共187页，2022年，5月20日，10点57分，星期日归结反演举例例：自然数都是大于零的整数；所有整数不是偶数就是奇数；偶数

44、除以2是整数。求证：所有自然数不是奇数就是其一半为整数的数。证明：前提： F1 ：x(N(x) GZ(x) I(x) N(x)：x是自然数 F2 ：x(I(x) E(x) O(x) GZ(x)：x0 I(x)：x是整数 F3 ：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) F1、 F2、 F3 及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)

45、 ( (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页，共187页，2022年，5月20日，10点57分，星期日应用归结原理求解应用归结原理求取问题答案的步骤把已知前提用谓词公式表示出来，并化为子句集S把待求解问题也用谓词公式表示出来，然后把它的否定与谓词ANS构成析取式。ANS的变元应与问题的变元完全一致把此析取式化为子句集，并把该子句集并入S中得到子句集S对S应用归结原理进行归结若得到归结式A

46、NS，则答案就在ANS中第52页，共187页，2022年，5月20日，10点57分，星期日应用归结原理求解例：设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(

47、B )第53页，共187页，2022年，5月20日，10点57分，星期日应用归结原理求解化为子句集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)并入S8) 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

48、), ANS(B)第54页，共187页，2022年，5月20日，10点57分，星期日归结策略 归结反演的一般过程。步1将子句集S置入CLAUSES表；步2若空子句NIL在CLAUSES中，则归结成功，结束。步3若CLAUSES表中存在可归结的子句对，则归结之，并将归结式并入CLAUSES表，转步；步4归结失败，退出。穷举算法（广度优先策略）第一轮：将原子句集S中的子句两两归结，产生的归结式集合记为S1，再将S1并入CLAUSES表；第二轮：将新的CLAUSES表，即S S1中的子句与S1中的子句两两归结，产生的归结式集合记为S2，再将S2并入CLAUSES；第三轮：将新的CLAUSES表即S

49、S1 S2中的子句与S2中的子句两两归结，。如此下去，直到出现空子句。第55页，共187页，2022年，5月20日，10点57分，星期日归结策略例1 设有如下的子句集，用穷举算法归结如下：S： （1） PQ （2） PQ （3） P Q （4） P QS1： （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)S2：（13） P Q (1), (7) （14） P Q (1), (8)第5

50、6页，共187页，2022年，5月20日，10点57分，星期日归结策略 （15） P Q (1), (9) （16） P Q (1), (10) （17） Q (1), (11) （18） P (1), (12) （19） Q (2), (6) （20） PQ (2), (7) （21） PQ (2), (8) （22） PQ (2), (9) （23） PQ (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) （3

51、0） 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页，共187页，2022年，5月20日，10点57分，星期日归结策略定义：设C1，C2是两个子句，若存在替换，使得C1 C2 ，则称子句C1类含C2 。 P(x)类含P(a) Q(y) P(x)类含P(a)删除策略。在归结过程中可随时删除以下子句：（1）、含有纯

52、文字的子句。纯文字是指在子句中无补文字的文字。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页，共187页，2022年，5月20日，10点57分，星期日归结策略使用删除策略，例1可简化为： （1） PQ （7） P (2), (4) （2） PQ （8） Q (3), (4) （3） P Q （ 9） (5), (8) （4） P Q （5） Q (1), (2) （

53、6） P (1), (3)删除策略的特点：删除策略的思想是及早删除无用字句，以避免无效归结，缩小搜索空间。删除策略是完备的。一个归结策略是完备的，是指对于不可满足的子句集，使用该策略进行归结，最终必导出空子句。第59页，共187页，2022年，5月20日，10点57分，星期日归结策略支持集策略支持集：目标公式的否定的子句集支持集策略：每次归结时，两个亲本子句中至少要有一个是目标公式否定的子句或其后裔。支持集策略的特点：支持集策略实际是一种目标制导的反向推理。支持集策略是完备的。线性归结策略在归结过程中，除第一次归结可都用初始子句集S中的子句外，其它的各次归结至少要有一个亲本子句是前次归结的结果

54、。线性归结策略的特点：完备、高效、与别的策略兼容。第60页，共187页，2022年，5月20日，10点57分，星期日归结策略归结策略的类型简化性策略思想：尽量简化子句和子句集，以减少和避免无效归结。缺点：额外开销 (eg:检验、真值计算)限制性策略思想：缩小搜索范围，提高搜索效率有序性策略思想：给子句安排一定的顺序，一边尽快推出空子句归结反演的一般算法步1将子句集S置入CLAUSES表；步2若空子句NIL在CLAUSES中，则归结成功，结束。步3按某种策略在CLAUSES表中寻找可归结的子句对，若存在则归结之，并将归结式并入CLAUSES表，转步；步4归结失败，退出。第61页，共187页，20

55、22年，5月20日，10点57分，星期日第四章 图搜索技术搜索：根据问题的实际情况不断寻找可利用的知识，从而构造一条代价较少的推理路线，使问题得到圆满解决的过程。应用：结构不良问题，无成熟算法；或有算法 ，但问题复杂，如博弈图：由节点和有向边组成的网络图的分类：或图(状态图、直接图)与或图第62页，共187页，2022年，5月20日，10点57分，星期日状态图状态图的概念迷宫问题八数码难题/华容道问题以上问题的本质：在某个有向图中寻找目标或路径，该有向图称为状态空间图或状态图。状态是描述问题求解过程中任一时刻的状况。引起状态中某些分量发生变化，从而使问题从一个状态变为另一个状态的操作、规则、变

56、换称为算符。问题求解就是寻找一个从初始状态到目标状态的算符序列的过程。问题求解过程可描述为一个有向图，其中的节点代表状态，边表示状态转换之间的算符。2 31 8 47 6 51 2 38 47 6 5第63页，共187页，2022年，5月20日，10点57分，星期日状态图搜索搜索树：搜索过程中经过的节点和边按原图的连接关系构成一个树型的有向图，称为搜索树。搜索方式树式搜索：记录搜索过程中所经过的所有节点和边线式搜索：记录当前认为是所找路径上的节点和边不可回溯 (随机碰撞式搜索)可回溯 (穷举式搜索)两种方式下路径的获得树式搜索：反向求解线式搜索：搜索线本身第64页，共187页，2022年，5月

57、20日，10点57分，星期日状态图搜索搜索策略盲目搜索(无向导) ：按预定的控制策略进行搜索，在搜索过程中获得的中间信息不用来改进控制策略。启发式搜索(有向导) ：在搜索过程中加入了与问题有关的启发性信息，用以指导搜索朝着最有希望的方向前进，加速问题的求解过程并找到最优解。按搜索范围的扩展顺序不同广度优先搜索深度优先搜索第65页，共187页，2022年，5月20日，10点57分，星期日搜索算法CLOSED表和OPEN表树式搜索算法步1 把初始节点放入OPEN表；步2 检查OPEN表，若为空，则问题无解，退出；步3 移出OPEN表中第一个节点N并放入CLOSED表中，并编号为n;步4 考察节点N

58、是否为目标节点，若是，则搜索成功，退出；步5 若N不可扩展，则转步2；步6 扩展节点N，生成所有子节点，对这组子节点作如下处理：（1）、如果有节点N的先辈节点，则删除；（2）、如果有已存在于OPEN表的节点，也删除；但删除之前要比较其返回初始节点的新路径与原路径，如果新路径“短”，则修改这些节点在OPEN表中的原指向父节点的指针，使其指向新的父节点。（3）、如果有已存在于CLOSED表中的节点，则作与（2）同样的处理，并且再将其移出CLOSED表，放入OPEN表重新扩展；（4）、对其余子节点，配上指向父节点n的指针后放入OPEN表，对OPEN表按某种搜索策略排序后转步2。第66页，共187页，

59、2022年，5月20日，10点57分，星期日搜索算法不回溯的线式搜索步1 把初始节点S0放入CLOSED表中；步2 令N= S0 ；步3 若N是目标节点，则搜索成功，结束;步4 若N不可扩展，则搜索失败，退出。步5 扩展N，选取一个未在CLOSED表中出现的子节点N1放入CLOSED表中，令N=N1，转步3。可回溯的线式搜索步1 把初始节点S0放入CLOSED表中；步2 令N= S0 ；步3 若N是目标节点，则搜索成功，结束;步4 若N不可扩展，则移出CLOSED表的末端节点Ne ，若Ne = S0 ，则搜索失败，退出。否则，以CLOSED表新的末端节点Ne作为N,即令N= Ne ，转步4步5

60、 扩展N，选取一个未在CLOSED表中出现的子节点N1放入CLOSED表中，令N=N1，转步3。第67页，共187页，2022年，5月20日，10点57分，星期日穷举式搜索广度优先搜索：优先在同一级节点中考察，只有当同一级节点扩展完以后，才扩展下一级节点。广度优先搜索算法：步1 把初始节点S0放入OPEN表中；步2 若OPEN表为空，则搜索失败，退出；步3 取OPEN表中前面第一个节点N放入CLOSED表中；步4 若目标节点Sg =N，则搜索成功，结束;步5 若N不可扩展，则转步2。步6 扩展N，将其所有子节点配上指向N的指针依次放入OPEN表的尾部，转步2。 (OPEN表为一个队列)例、解八