人工智能 上海交通大学计算机系 卢 宏 涛 2003年9月

教 材 《人工智能技术导论》 廉师友编著，西安电子科技大学出版社

参考书 《人工智能原理·方法·应用》，王永庆编，西安交大出版社 《人工智能基础》，邵军力等编著，电子工业出版社

第一章 人工智能概述 1.1 人工智能的概念 1.1.1 什么是人工智能 第一章 人工智能概述 1.1 人工智能的概念 1.1.1 什么是人工智能 （1）人工智能（Artificial Intelligence)是指由计算机实现的人造智能。人工智能就是用人工的方法在机器（计算机）上实现的智能。作为一门学科，人工智能可定义为：人工智能是一门研究如何构造智能机器（智能计算机）或智能系统，使它能模拟、延伸、扩展人类智能的学科。 （2）人工智能是一门交叉边缘学科，与人工智能有关的学科有：计算机科学、数学、哲学、语言学、神经生理学、神经心理学、脑科学、认知科学、逻辑学、控制论等 恢复高考以后第二届 硕士毕业后留校工作 专门开展基于角度格栅的二维位置研究 日本东京大学、东京理工大学和东北大学的合作研究计划

第一章 人工智能概述 （3）什么是人的智能？智能是人脑的属性和产物。智能具有的主要特征： 第一章 人工智能概述 （3）什么是人的智能？智能是人脑的属性和产物。智能具有的主要特征： A、具有感知能力。通过视觉、听觉、触觉、味觉和嗅觉感知外部世界。 B、具有记忆与思维能力。记忆能存储由感知器官感知到的外部信息以及有思维所产生的知识。思维用于对记忆的信息进行处理。思维可分为逻辑思维和形象思维。 C、具有学习能力及自适应能力。 D、具有行为能力。

第一章 人工智能概述 1.1.2 为什么要研究人工智能 1、现有计算机系统的局限性。智能低下、缺乏自学习、自适应能力。 第一章 人工智能概述 1.1.2 为什么要研究人工智能 1、现有计算机系统的局限性。智能低下、缺乏自学习、自适应能力。 2、人类智能的局限性。学习能力因人而异、学习速度慢、效率低。 3、信息化社会的迫切要求。 1.1.3 人工智能的目标 近期目标：使现有的电子数字计算机能模拟人类的部分智能行为。 远期目标：够造智能计算机，使计算机具有看、听、说等感知和交互能、具有联想、推理、理解、学习等高级思维能力，还要有分析问题、解决问题和发明创造的能力。

第一章 人工智能概述 1.2 人工智能的研究途径与方法 1.2.1 结构模拟（神经计算、生理学派、连接主义） 第一章 人工智能概述 1.2 人工智能的研究途径与方法 1.2.1 结构模拟（神经计算、生理学派、连接主义） 模拟人脑的神经网络结构实现智能。主要特征： 1、通过神经元之间的并行协同作用实现信息处理，具有并行性、动态性、全局性。 2、通过神经元间分布式的物理联接存储信息。联想记忆、容错性。 3、通过神经元间连接强度的动态调整实现自学习和自适应功能。 4、善于模拟人类的形象思维过程。

第一章 人工智能概述 1.2.2 功能模拟（符号主义、心理学派、逻辑学派） 第一章 人工智能概述 1.2.2 功能模拟（符号主义、心理学派、逻辑学派） 以人脑的心理模型为基础，将问题或知识表示成某种逻辑网络，采用符号推演的方法，实现搜索、推理和学习等功能。主要特征： 1、立足于逻辑运算和符号操作，适合于模拟人的逻辑思维过程。 2、知识用显式的符号表示，容易表达人的心理模型。 3、现有的数字计算机可以方便地实现高速的符号处理。 4、能与传统的符号数据库进行链接，易于模块化。 5、以知识为基础。

第一章 人工智能概述 1.2.3 行为模拟（行为主义、进化主义、控制论学派） 第一章 人工智能概述 1.2.3 行为模拟（行为主义、进化主义、控制论学派） 基于感知-行为模型的研究途径和方法。强调智能系统与环境的交互，认为智能取决于感知和行动。智能行为可以不要知识。

第一章 人工智能概述 1.3 人工智能的分支领域 1.3.1 基于脑功能模拟的领域划分 第一章 人工智能概述 1.3 人工智能的分支领域 1.3.1 基于脑功能模拟的领域划分 1、机器感知（信息输入）。使计算机具有类似于人的感知能力，能通过“感知”直接从外界获取信息。机器视觉、机器听觉。相关学科：模式识别、语音识别。 2、机器联想。基于内容的联想，与具体存储位置无关。联想存储技术。 3、机器推理。又称为计算机推理、自动推理，是人工智能的核心课题之一。自然演绎推理、归结演绎推理、基于非经典逻辑的推理。 4、机器学习。使机器自己获取知识。对书本知识的学习、对客观规律的发现、对自身行为的修正。机器学习分为：机械学习、指导学习、解释学习、类比学习、示例学习、发现学习等。这些属于符号学习。另外还有神经网络学习。

第一章 人工智能概述 1.3.2 基于实现技术的领域划分 5、机器理解。图形理解（物景分析）、自然语言理解。理解是感知的延伸和深化。 第一章 人工智能概述 5、机器理解。图形理解（物景分析）、自然语言理解。理解是感知的延伸和深化。 6、机器行为（信息输出）。计算机的表达能力及类似于人四肢的功能，能走路、取物、操作等。机器人行动规划 1.3.2 基于实现技术的领域划分 1。知识工程与符号处理技术。 2。神经网络技术

第一章 人工智能概述 1.3.3 基于应用领域的领域划分 第一章 人工智能概述 1.3.3 基于应用领域的领域划分 1、难题求解。路径规划、组合优化、博弈等难题求解。NP(Nondeterministic Polynomial) 和NPC问题。难题求解技术能促进人工智能其他领域的发展。 2、自动定理证明。机器定理证明。吴文俊，四色问题。 3、自动程序设计。自动程序综合和自动程序验证。 4、自动翻译。机器翻译。自然语言理解。 5、智能控制。自动控制与人工智能的结合。专家智能控制、模糊控制、神经控制。 6、智能管理。人工智能与管理科学、系统工程和计算机技术的结合。 7、智能决策。人工智能应用于决策支持系统。 8、智能通讯。在通讯的各个环节和层次上实现智能化。如网控、转接、信息转换等。使通讯网随时运行于最佳状态。

第一章 人工智能概述 9、智能仿真。仿真是在三种类型知识-描述性知识、目的性知识和处理知识的基础上产生另一种形式的知识-结论性知识。 第一章 人工智能概述 9、智能仿真。仿真是在三种类型知识-描述性知识、目的性知识和处理知识的基础上产生另一种形式的知识-结论性知识。 10、智能CAD。人工智能应用于CAD的设计自动化、智能交互、智能图形学、自动数据采集方面。 11、智能CAI。人工智能应用于CAI： 自动生成各种问题与练习、自动选择与调整教学内容和进度、自动生成答案、自然语言理解能力、不断改善教学策略。 12、机器人学。智能机器人。是人工智能的实验场。

第一章 人工智能概述 1.3.4 基于应用系统的领域划分 1.3.5 基于计算机系统结构的领域划分 第一章 人工智能概述 1.3.4 基于应用系统的领域划分 1、专家系统。基于人类专家知识的程序系统。能模拟专家的思维方式。 2、知识库系统。 3、智能数据库系统。传统数据库系统+人工智能。 4、智能机器人系统。具备感知、思维、人-机通讯和运动能力。 1.3.5 基于计算机系统结构的领域划分 1、智能操作系统。并行性、分布性和智能性。 2、智能多媒体系统。人工智能与多媒体技术的有机结合。 3、智能计算机系统。 4、智能网络系统。模糊和神经网络技术应用于网络的业务量预测和控制、资源动态分配、动态路由选择等方面。

第一章 人工智能概述 1.3.6 基于实现工具与环境的领域划分 第一章 人工智能概述 1.3.6 基于实现工具与环境的领域划分 1、智能软件工具。人工智能程序设计语言，如表处理语言LISP、逻辑程序设计语言PROLOG、面向对象程序设计语言Smalltalk等。知识表示语言FRL、OPS5。专家系统工具、知识工程工具等。 2、智能硬件平台。直接支持智能系统开发和运行的机器硬件。

第一章 人工智能概述 1.4 人工智能的基本技术 1.4.1 推理技术。推理是智能的核心。推理以逻辑为基础。基于谓词逻辑的自然演绎推理和归结反演推理。基于非标准逻辑如多值逻辑、模态逻辑、时态逻辑、模糊逻辑、非单调逻辑的推理。 1.4.2 搜索技术。许多智能活动的过程，都可以看作或抽象为一个“问题求解”过程。“问题求解”就是在问题空间中进行搜索的过程。盲目搜索、启发式搜索。神经网络搜索。 1.4.3 知识表示与知识库技术。知识表示是指知识在计算机中的表示方式。知识表示要符合知识的逻辑结构和物理结构，并适合于计算机存储和处理。知识库由知识构成。知识的组织、管理、维护和优化。

第一章 人工智能概述 1.4.4 归纳技术。机器自动提取概念、获取知识、发现规律的技术。归纳技术与知识获取和机器学习密切相关。基于符号处理的归纳和基于神经网络的归纳。数据库知识发现（KDD, Knowledge Discovery in Database) 和数据挖掘(Data Mining)技术。 1.4.5 联想技术。联想记忆，联想存储。

第一章 人工智能概述 1.5 人工智能的发展概况 孕育期（1956年之前） 第一章 人工智能概述 1.5 人工智能的发展概况 孕育期（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年，世界上第一台电子计算机诞生。

第一章 人工智能概述 1.5.1 人工智能学科的产生（1956年） 第一章 人工智能概述 1.5.1 人工智能学科的产生（1956年） 1956年夏季，McCarthy, Minsky, Lochester, Shannon, More, Samuel, Selfridge, Solomonff, Newell, Simon等十人在Dartmouth大学召开历时两个多月的研讨会，讨论机器智能的有关问题。由McCarthy提出“人工智能”一词，人工智能从此成为一门学科。 1.5.2 符号主义AI发展概况 1、形成（1956-1965）（人工智能的推理期。结构良好问题。搜索策略和算法） （1）、1965年，Samuel的跳棋程序。 （2）、定理证明方面，1956年Newell等的逻辑理论机（LT）程序；1958年，王浩的工作；1965年，Robinson提出的消解原理。 （3）、模式识别方面，1959年Selfridge的模式识别程序；1965年Roberts编制了可以分辨积木构造的程序。

第一章 人工智能概述 （4）、问题求解方面。1960年，Newell的通用问题求解(GPS)程序。 第一章 人工智能概述 （4）、问题求解方面。1960年，Newell的通用问题求解(GPS)程序。 （5）、1960年，McCarthy研制成功LISP语言。 2、人工智能的知识期（1965-70年代末） （1）、专家系统方面。1965年，Feigenbaum的专家系统DENDRAL，1968年投入使用。DENDRAL对知识表示、存储、获取和推理的技术为以后的专家系统的建造树立了榜样，对AI的发展产生了深刻的影响。之后著名的专家系统有：医学专家系统MYCIN，地质勘探专家系统PROSPECTOR，计算机配置专家系统R1等。 （2）、1969年，国际人工智能联合会议(IJCAI)召开。1970年，“Artificial Intelligence”杂志创刊。 （3）、1977年，Feigenbaum在第五届国际人工智能会议上，提出了“知识过程”的概念。

第一章 人工智能概述 1.5.3 连接主义途径发展概况 3、发展期（20世纪80年代后） 第一章 人工智能概述 3、发展期（20世纪80年代后） 专家系统与知识工程在理论、技术和应用方面都有长足的进步和发展。出现了多专家系统、大型专家系统、微专家系统、分布专家系统等。智能管理信息系统、智能决策支持系统、智能控制系统等。 1.5.3 连接主义途径发展概况 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问题。1987年6月，第一届国际神经网络大会（IJCNN）召开，盛况空前。目前，NN与专家系统、知识工程成为AI的两个主流方向。NN在智能控制、信号处理、最优化、知识工程等领域都有成功应用。 1.5.4 当前发展趋势。 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 等。

第三章 基于谓词逻辑的机器推理 命题逻辑（复习） 命题是具有真假意义的陈述句。 不能被分解成更简单的陈述句的命题称为简单命题 第三章 基于谓词逻辑的机器推理 命题逻辑（复习） 命题是具有真假意义的陈述句。 不能被分解成更简单的陈述句的命题称为简单命题 命题可用小写字母如p,q,r…表示，称为命题变元。 复合命题是由简单命题和联结词联结而成的命题。 最基本的5种联结词是：，，，， 命题公式的定义：（1）单个命题变元是命题公式，称为原子公式；（2）若A、B是命题公式，则 A，A  B，A  B，A  B，A  B也是命题公式；（3）只有有限次地应用（1），（2）形成的符号串才是命题公式。 命题公式的一个指派（赋值）。 永真式（重言式）；永假式（矛盾式）；可满足式。

第三章 基于谓词逻辑的机器推理----命题逻辑（复习） 第三章 基于谓词逻辑的机器推理----命题逻辑（复习） 等价式AB： A  B为重言式。 永真蕴涵A B： A  B为重言式。 命题逻辑的一些重要等价式： 1、双重否定律：A    A 2、幂等律： AA  A, A A  A 3、交换律： AB  BA, A  B  B  A 4、结合律： （A B) C A(B C) (A B) C A  (B C) 5、分配律： A(B C)  (AB) (A C) A  (B  C)  (A  B) (A  C) 6、De Morgan 律： (AB)   A   B (A  B)  A B

第三章 基于谓词逻辑的机器推理----命题逻辑（复习） 第三章 基于谓词逻辑的机器推理----命题逻辑（复习） 7、吸收律： A(A B)  A, A  (A  B)  A 8、零律： AT  T, A  F  F 9、同一律： AF  A, A  T  A 10、排中律： A  A  T 11、矛盾律： A  A  F 12、蕴含等值式: A  B  A B 13、等价等值式： A  B  (A  B) (B  A)

第三章 基于谓词逻辑的机器推理----命题逻辑（复习） 第三章 基于谓词逻辑的机器推理----命题逻辑（复习） 命题逻辑的一些重要的永真蕴涵式（即推理定律） 1、化简式： A B A, A B B 2、附加式： A A B, B A B 3、析取三段论：  A (A  B) B 4、假言推理（分离规则）： A (A B) B 5、拒取式： B (A B)   A 6、假言三段论： (A B) (BC)  A C 7、二难推论: (A  B)  (A C) (BC)  C

第三章 基于谓词逻辑的机器推理----命题逻辑（复习） 第三章 基于谓词逻辑的机器推理----命题逻辑（复习） 命题公式的析取范式 命题变元或命题变元的否定的合取式称为简单合取式。简单合取式的析取式称为析取范式。 命题公式的合取范式 命题变元或命题变元的否定的析取式称为简单析取式。简单析取式的合取式称为合取范式。 任一命题公式都可化为与之等价的析取范式与合取范式。

第三章 基于谓词逻辑的机器推理----3.1 一阶谓词逻辑 第三章 基于谓词逻辑的机器推理----3.1 一阶谓词逻辑 3.1.1 谓词、函词、量词 个体：研究对象中可以独立存在的具体的或抽象的客体。个体用个体常元或个体变元表示，如x,y,z,a,b,c,…等。 谓词：描述个体性质及个体之间相互关系的词。用谓词常元或谓词变元表示，如P、Q、R，…等。 例、命题“2是素数”中，2是个体，“是素数”是谓词。可表示为P(2). 函词（函数）：某些个体是其它个体的函数，描述这种关系的词称为函词。 例、命题“小李的父亲是医生”可表示为Doctor(father(Li)).

第三章 基于谓词逻辑的机器推理----3.1 一阶谓词逻辑 第三章 基于谓词逻辑的机器推理----3.1 一阶谓词逻辑 量词：存在量词“  ”；全称量词“  ”。 例、“任何实数的平方都非负”可表示为 x(R(x) N(s(x))。 “存在偶素数”可表示为 x(E(x) P(x))。 3.1.2 谓词公式 项的定义：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也是谓词公式；3、只有有限次地应用步骤1，2形成的符号串才是谓词公式。

第三章 基于谓词逻辑的机器推理----3.1 一阶谓词逻辑 第三章 基于谓词逻辑的机器推理----3.1 一阶谓词逻辑 辖域： xA 和 xA中，x称为指导变元，A称为x的辖域。A中出现的x称为约束出现。若x的所有出现都是约束出现，则x称为约束变元，否则称为自由变元。 例、xP(x)； x(H(x) G(x,y))； xA(x) B(x) 谓词公式的解释I由下面4部分构成： (a)、非空个体域DI。 (b)、 DI中一些特定元素的集合 ( c)、 DI上特定函数的集合 (d)、 DI上特定谓词的集合 例、给定解释I如下：(a)个体域D=N（自然数集0，1，2，…）； (b)、 ；( c)、 (d)、 为 。

第三章 基于谓词逻辑的机器推理----3.1 一阶谓词逻辑 第三章 基于谓词逻辑的机器推理----3.1 一阶谓词逻辑 判断下列谓词公式的真假： （1）、F( f(x,a), y) F( g(x,y), z); （2）、xy(F( f(x,a), y) F( f(y,a), x)); （3）、 x F( f(x,x), g(x,x)); （4）、 x F( g(x,a), x) 永真式（重言式）：在任何解释下均为真的谓词公式称为永真式。 永假式（矛盾式）：在任何解释下均为假的谓词公式称为永假式。此时称谓词公式是不可满足的。 可满足式：存在解释使谓词公式为真。

第三章 基于谓词逻辑的机器推理----3.1 一阶谓词逻辑 第三章 基于谓词逻辑的机器推理----3.1 一阶谓词逻辑 常用谓词公式的等价式与推理定律 命题逻辑的等价式和推理定律对谓词公式都成立，除此之外，还存在与量词有关的等价式和推理定律。参见教材p61表3.1和3.2。 等价式： 1、消去量词等价式 设个体域为有限集D={a1,a2,…, an}，则有 xA(x)  A(a1)  A(a2) ….  A(an) xA(x)  A(a1) A(a2)  ….  A(an) 2、量词转换律  xA(x)  x A(x)， xA(x)   x A(x)

第三章 基于谓词逻辑的机器推理----3.1 一阶谓词逻辑 第三章 基于谓词逻辑的机器推理----3.1 一阶谓词逻辑 3、量词分配律 x(A(x)  B(x))  xA(x)  xB(x) x(A(x)  B(x))  xA(x)  xB(x) 4、量词辖域扩张及收缩律 若A(x)是任意的含自由出现个体变元x的谓词公式，B中不含x的出现，则 (a)、 x(A(x)  B)  xA(x)  B x(A(x)  B)  xA(x)  B x(A(x)  B)  xA(x)  B x(B  A(x))  B  xA(x)

第三章 基于谓词逻辑的机器推理----3.1 一阶谓词逻辑 第三章 基于谓词逻辑的机器推理----3.1 一阶谓词逻辑 (b)、  x(A(x)  B)  xA(x)  B x(A(x)  B)  xA(x)  B x(A(x)  B)  xA(x)  B x(B  A(x))  B  xA(x) 推理定律： 全称指定规则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是个体域中某一确定元素。

第三章 基于谓词逻辑的机器推理----3.1 一阶谓词逻辑 第三章 基于谓词逻辑的机器推理----3.1 一阶谓词逻辑 以谓词公式的等价式及推理定律为基础进行的推理称为自然演绎推理。例见教材p69。自然演绎推理在机器上实施比较困难，因为推理规则太多。