人工智能导论全套ppt课件演示课件.ppt

人工智能导论,教材： 王万良人工智能导论（第3版） 高等教育出版社，2011. 2,2,第 1 章 绪论,教材： 王万良人工智能导论（第3版） 高等教育出版社，2011. 2,人工智能导论,3,第1章 绪论,1956年正式提出人工智能（artificial intelligence, AI）这个术语并把它作为一门新兴科学的名称。,4,第1章 绪论,1.1 人工智能的基本概念 1.2 人工智能的发展简史 1.3 人工智能研究的基本内容1.4 人工智能的主要研究领域,5,第1章 绪论,1.1 人工智能的基本概念 1.2 人工智能的发展简史 1.3 人工智能研究的基本内容1.4 人工智能的主要研究领域,6,1.1.1 智能的概念,自然界四大奥秘：物质的本质、宇宙的起源、生命的本 质、智能的发生。 对智能还没有确切的定义，主要流派有： （1）思维理论：智能的核心是思维 （2）知识阈值理论：智能取决于知识的数量及一般化程度 （3）进化理论：用控制取代知识的表示 智能是知识与智力的总和,知识是一切智能行为的基础,获取知识并应用知识求解问题的能力,7,感知能力：通过视觉、听觉、触觉、嗅觉等感觉器官感知外部世界的能力。 80%以上信息通过视觉得到，10%信息通过听觉得到。,1.1.2 智能的特征,存储由感知器官感知到的外部信息以及由思维所产生的知识,对记忆的信息进行处理,2. 记忆与思维能力,8,（1）逻辑思维（抽象思维）依靠逻辑进行思维。思维过程是串行的。容易形式化。思维过程具有严密性、可靠性。,1.1.2 智能的特征,（2）形象思维（直感思维） 依据直觉。 思维过程是并行协同式的。 形式化困难。 在信息变形或缺少的情况下仍有可能得到比较满意的结果。,9,4. 行为能力（表达能力）,1.1.2 智能的特征,（3）顿悟思维（灵感思维） 不定期的突发性。 非线性的独创性及模糊性。 穿插于形象思维与逻辑思维之中。,人们的感知能力：用于信息的输入。行为能力：信息的输出。,10,人工智能：用人工的方法在机器（计算机）上实现的智能；或者说是人们使机器具有类似于人的智能。,1.1.3 人工智能,人工智能学科：一门研究如何构造智能机器（智能计算机）或智能系统，使它能模拟、延伸、扩展人类智能的学科。 图灵测试：1950年图灵发表的计算机与智能中设计了一个测试，用以说明人工智能的概念。,11,第1章 绪论,1.1 人工智能的基本概念 1.2 人工智能的发展简史 1.3 人工智能研究的基本内容1.4 人工智能的主要研究领域,12,1.2 人工智能的发展简史,1.2.1 孕育（1956年之前）公元前，亚里斯多德（Aristotle）：三段论培根（F. Bacon）：归纳法莱布尼茨（G. W. Leibnitz）：万能符号、推理计算布尔（G. Boole）：用符号语言描述思维活动的基本推理法则1936年，图灵：图灵机1943年，麦克洛奇（W. McCulloch）、匹兹(W. Pitts)：MP模型,13,1.2 人工智能的发展简史,1.2.1 孕育（1956年之前）美国爱荷华州立大学的阿塔纳索夫教授和他的研究生贝瑞在1937年至1941年间开发的世界上第一台电子计算机“阿塔纳索夫贝瑞计算机（Atanasoff-Berry Computer，ABC）”为人工智能的研究奠定了物质基础。,14,1.2.2 形成（1956年1969年）,1956年夏，当时美国达特茅斯大学数学助教、现任斯坦福大学教授麦卡锡和哈佛大学数学和神经学家、现任MIT教授明斯基、IBM公司信息研究中心负责人洛切斯特、贝尔实验室信息部数学研究员香农共同发起，邀请普林斯顿大学莫尔和IBM公司塞缪尔、MIT的塞尔夫里奇和索罗莫夫以及兰德公司和卡内基梅隆大学的纽厄尔、西蒙等10名年轻学者在达特莫斯大学召开了两个月的学术研讨会，讨论机器智能问题。会上经麦卡锡提议正式采用“人工智能”这一术语，标志着人工智能学科正式诞生。麦卡锡因而被称为人工智能之父。此后，美国形成了多个人工智能研究组织，如纽厄尔和西蒙的Carnegie RAND协作组，明斯基和麦卡锡的MIT研究组，塞缪尔的IBM工程研究组等。,15,1.2.2 形成（1956年1969年）,1956年以后，人工智能的研究在机器学习、定理证明、模式识别、问题求解、专家系统及人工智能语言等方面都取得了许多引人瞩目的成就 。 1969年，成立了国际人工智能联合会议（International Joint Conferences on Artificial Intelligence，IJCAI）。 1970年，创刊了国际性的人工智能杂志（Artificial Intelligence）。,16,1.2.3 发展（1970年 ）,20世纪60年代末，人工智能研究遇到困难，如机器翻译。1966年美国顾问委员会的报告裁定：还不存在通用的科学文本机器翻译，也没有很近的实现前景。英国、美国中断了大部分机器翻译项目的资助。1977年，费根鲍姆在第五届国际人工智能联合会议上提出了“知识工程”概念，推动了知识为中心的研究。1981年，日本宣布第五代计算机发展计划，并在1991年展出了研制的PSI3智能工作站和由PSI3构成的模型机系统。 我国自1978年开始把“智能模拟”作为国家科学技术发展规划的主要研究课题。1981年成立了中国人工智能学会。现在，人工智能已经成为计算机、航空航天、军事装备、工业等众多领域的关键技术。,17,第1章 绪论,1.1 人工智能的基本概念 1.2 人工智能的发展简史 1.3 人工智能研究的基本内容1.4 人工智能的主要研究领域,18,1.3 人工智能研究的基本内容,知识表示 知识表示：将人类知识形式化或者模型化。 知识表示方法：符号表示法、连接机制表示法。,符号表示法：用各种包含具体含义的符号，以各种不同的方式和顺序组合起来表示知识的一类方法。例如，一阶谓词逻辑、产生式等。 连接机制表示法：把各种物理对象以不同的方式及顺序连接起来，并在其间互相传递及加工各种包含具体意义的信息，以此来表示相关的概念及知识。例如，神经网络等。,19,2. 机器感知,2. 机器感知 机器感知：使机器（计算机）具有类似于人的感知能力。以机器视觉(machine vision)与机器听觉为主。,1.3 人工智能研究的基本内容,3. 机器思维机器思维：对通过感知得来的外部信息及机器内部的各种工作信息进行有目的的处理。,20,2. 机器感知,4. 机器学习 机器学习（machine learning）：研究如何使计算机具有类似于人的学习能力，使它能通过学习自动地获取知识。 1957年，Rosenblatt研制成功了感知机。,1.3 人工智能研究的基本内容,5. 机器行为 机器行为：计算机的表达能力，即“说”、“写”、“画”等能力。,21,第1章 绪论,1.1 人工智能的基本概念 1.2 人工智能的发展简史 1.3 人工智能研究的基本内容1.4 人工智能的主要研究领域,22,1.4 人工智能的主要研究领域,1. 自动定理证明,定理证明的实质是证明由前提 P 得到结论 Q 的永真性。 1958年，王浩证明了有关命题演算的全部定理（220条）、谓词演算中150条定理的85%。 1965年鲁宾逊（Robinson）提出了归结原理，使机器定理证明成为现实。 我国著名数学家、中国科学院吴文俊院士把几何代数化，建立了一套机器证明方法，被称为“吴方法”。,23,1.4 人工智能的主要研究领域,2. 博弈 下棋、打牌、战争等一类竞争性的智能活动。 1956年，塞缪尔研制出跳棋程序。 1991年8月，IBM公司研制的Deep Thought 2计算机系统与澳大利亚象棋冠军约翰森（D.Johansen）举行了一场人机对抗赛，以1：1平局告终。 1996年2月10日至17日 ，IBM公司的“深蓝”计算机系统与卡斯帕罗夫进行了六局比赛，以3.5比2.5的总比分赢得这场世人瞩目的“人机大战”的胜利。,24,1.4 人工智能的主要研究领域,2. 博弈 2004年6月8日，中国首届国际象棋人机对弈开战。国际象棋特级大师诸宸与“紫光之星”笔记本电脑对阵。诸宸在最后关头被电脑抓住破绽，先负一局。4天后诸宸灵活变阵，但再负一局。,25,2007年台北国际发明暨技术交易展览上，第三代智能机器人DOC 现场表演下棋。,1.4 人工智能的主要研究领域,26,1.4 人工智能的主要研究领域,模式识别（pattern recognition）：研究对象描述和分类方法的学科。分析和识别的模式可以是信号、图象或者普通数据。文字识别：邮政编码、车牌识别、汉字识别。人脸识别：反恐、商业。物体识别：导弹、机器人。,3. 模式识别,27,1.4 人工智能的主要研究领域,4. 机器视觉,机器视觉(machine vision)或计算机视觉(computer vision)是用机器代替人眼睛进行测量和判断。 机器视觉系统是指通过图像摄取装置将被摄取的目标转换成图像信号，传送给专用的图像处理系统，根据像素分布和宽度、颜色等信息，转换成数字信号，抽取目标的特征，根据判别结果控制现场的设备动作。 机器视觉应用在半导体及电子、汽车、冶金、制药、食品饮料、印刷、包装、零配件装配及制造质量检测等。,28,1.4 人工智能的主要研究领域,5. 自然语言理解 研究如何让计算机理解人类自然语言，包括回答问题、生成摘要、翻译等。 1957年，在苏联人造卫星成功发射的刺激下,美国国家研究会大力支持对俄科技论文的计算机翻译。人们最初以为机器翻译只要将双向词典及一些词法知识放进计算机就行了。后来发现有时会出现十分荒谬的错误。,“The spirit is willing but the flesh is weak”心有余而力不足。 俄语 “The wine is good but the meat is spoiled”酒是好的但肉变质了。,29,1.4 人工智能的主要研究领域,6. 智能信息检索,智能信息检索系统的功能： (1) 能理解自然语言。 (2) 具有推理能力。 (3) 系统拥有一定的常识性知识。,7. 数据挖掘与知识发现,数据挖掘的目的是从数据库中找出有意义的模式(一组规则、聚类、决策树、依赖网络或其他方式表示的知识)。 数据挖掘过程：数据预处理、建模、模型评估及模型应用。,30,1.4 人工智能的主要研究领域,8. 专家系统,专家系统模拟人类专家求解问题的思维过程求解领域内的各种问题，其水平可以达到甚至超过人类专家的水平。 1965年费根鲍姆研究小组开始研制第一个专家系统分析化合物分子结构的DENDRAL，1968年完成并投入使用。 1971年MIT开发成功求解一些数学问题的MYCSYMA专家系统。拉特格尔大学开发的清光眼诊断与治疗的专家系统CASNET。 1972年斯坦福大学肖特里菲等人开始研制用于诊断和治疗感染性疾病的专家系统MYCIN。 1976年斯坦福研究所开始开发探矿专家系统PROSPECTOR，1980年首次实地分析华盛顿某山区地质资料，发现了一个钼矿。 1981年斯坦福大学研制成功专家系统AM，能模拟人类进行概括、抽象和归纳推理，发现某些数论的概念和定理。,31,1.4 人工智能的主要研究领域,9. 自动程序设计,程序综合：用户只需要告诉计算机要“做什么”， 无须说明“怎么做”，计算机就可自动实现程序的设计。 程序正确性的验证：研究出一套理论和方法，通过运用这套理论和方法就可以证明程序的正确性。,32,1.4 人工智能的主要研究领域,10. 机器人,20世纪60年代初，研制出尤尼梅特和沃莎特兰两种机器人。 机器人发展：程序控制机器人（第一代） 、自适应机器人（第二代）、智能机器人（现代）。,33,1.4 人工智能的主要研究领域,美国军用机器人携带火箭,34,美军排爆机器人,1.4 人工智能的主要研究领域,35,美军投入伊拉克战场的可携带侦察机器人,1.4 人工智能的主要研究领域,36,1.4 人工智能的主要研究领域,11. 组合优化问题,组合优化问题：旅行商问题、生产计划与调度、物流中的车辆调度、智能交通、通信中的路由调度、计算机网络信息调度等 NP完全问题：用目前知道的最好的方法求解，问题求解需要花费的时间是随问题规模增大以指数关系增长。,12. 人工神经网络,人工神经网络：一个用大量简单处理单元经广泛连接而组成的人工网络，用来模拟大脑神经系统的结构和功能 。,37,1.4 人工智能的主要研究领域,分布式人工智能系统以鲁棒性作为控制系统质量的标准，并具有互操作性，即不同的异构系统在快速变化的环境中，具有交换信息和协同工作的能力。 分布式问题求解：把一个具体的求解问题划分为多个相互合作和知识共享的模块或者结点。 多智能体系统：研究各智能体之间行为的协调。,13. 分布式人工智能与多智能体,38,1.4 人工智能的主要研究领域,国际知名美籍华裔科学家傅京孙（K S. Fu）在1965年首先把人工智能的启发式推理规则用于学习控制系统。 智能控制的两个显著特点：第一，智能控制是同时具有知识表示的非数学广义世界模型和传统数学模型混合表示的控制过程。第二，智能控制的核心在高层控制，其任务在于实际环境或过程进行组织，即决策与规划，以实现广义问题求解。 智能控制的基本类型：（1）专家智能控制 （2）模糊控制（3）神经网络控制,14. 智能控制,39,1.4 人工智能的主要研究领域,智能仿真是将AI引入仿真领域，建立智能仿真系统。 仿真是对动态模型的实验，即行为产生器在规定的实验条件下驱动模型，从而产生模型行为。仿真是在描述性知识、目的性知识及处理知识的基础上产生结论性知识。 利用AI对整个仿真过程（建模、实验运行及结果分析）进行指导，在仿真模型中引进知识表示，改善仿真模型的描述能力，为研究面向目标的建模语言打下基础，提高仿真工具面向用户、面向问题的能力，使仿真更有效地用于决策，更好地用于分析、设计及评价知识库系统。,15. 智能仿真,40,1.4 人工智能的主要研究领域,智能CAD（简称ICAD）就是把人工智能技术引入计算机辅助设计领域，建立智能CAD系统。AI几乎可以应用到CAD技术的各个方面。从目前发展的趋势来看，至少有下述四个方面： （1）设计自动化。 （2）智能交互。 （3）智能图形学。 （4）自动数据采集。,16. 智能CAD,41,1.4 人工智能的主要研究领域,智能CAI就是把AI引入计算机辅助教学领域。 ICAI系统一般分成专门知识、教导策略和学生模型和自然语言的智能接口。 ICAI应具备下列智能特征：（1）自动生成各种问题与练习。（2）根据学生的学习情况自动选择与调整教学内容与进度。（3）在理解教学内容的基础上自动解决问题生成解答。（4）具有自然语言生成和理解能力。（5）对教学内容有理解咨询能力。（6）能诊断学生错误，分析原因并采取纠正措施。（7）能评价学生的学习行为。（8）能不断地在教学中改善教学策略。,17. 智能CAI,42,1.4 人工智能的主要研究领域,智能管理就是把人工智能技术引入管理领域，建立智能管理系统，研究如何提高计算机管理系统的智能水平，以及智能管理系统的设计理论、方法与实现技术。 智能决策就是把人工智能技术引入决策过程，建立智能决策支持系统。 智能决策支持系统是由传统决策支持系统再加上相应的智能部件就构成了智能决策支持系统。 智能部件可以是专家系统模式、知识库模式等。,18. 智能管理与智能决策,43,1.4 人工智能的主要研究领域,多媒体计算机系统就是能综合处理文字、图形、图像和声音等多种媒体信息的计算机系统。 智能多媒体就是将人工智能技术引入多媒体系统，使其功能和性能得到进一步发展和提高。 多媒体技术与人工智能所研究的机器感知、机器理解等技术不谋而合。人工智能的计算机视听觉、语音识别与理解、语音对译、信息智能压缩等技术运用于多媒体系统，将会使现在的多媒体系统产生质的飞跃。,19. 智能多媒体系统,44,1.4 人工智能的主要研究领域,智能操作系统的基本模型：以智能机为基础，能支撑外层的AI应用程序，实现多用户的知识处理和并行推理。 智能操作系统三大特点：并行性：支持多用户、多进程，同时进行逻辑推理等;分布性：把计算机硬件和软件资源分散而又有联系地组织起来，能支持局域网和远程网处理;智能性：一是操作系统处理的是知识对象，具有并行推理功能，支持智能应用程序运行;二是操作系统的绝大部分程序使用AI程序编制，充分利用硬件并行推理功能;三是具有较高智能程序的自动管理维护功能，如故障的监控分析等，帮助维护人员决策。,20. 智能操作系统,45,1.4 人工智能的主要研究领域,智能计算机系统就是人们正在研制的新一代计算机系统。 智能计算机系统从基本元件到体系结构，从处理对象到编程语言，从使用方法到应用范围，同当前的诺依曼型计算机相比，都有质的飞跃和提高，它将全面支持智能应用开发，且自身就具有智能。,21. 智能计算机系统,46,1.4 人工智能的主要研究领域,智能通信就是把人工智能技术引入通信领域，建立智能通信系统。 智能通信就是在通信系统的各个层次和环节上实现智能化。例如在通信网的构建、网管与网控、转接、信息传输与转换等环节，都可实现智能化。这样，网络就可运行在最佳状态，具有自适应、自组织、自学习、自修复等功能。,22. 智能通信,47,1.4 人工智能的主要研究领域,智能网络系统就是将人工智能技术引入计算机网络系统。如在网络构建、网络管理与控制、信息检索与转换、人机接口等环节，运用AI的技术与成果。 AI的专家系统、模糊技术和神经网络技术可用于网络的连接接纳控制、业务量管制、业务量预测、资源动态分配、业务流量控制、动态路由选择、动态缓冲资源调度等许多方面。,23. 智能网络系统,48,1.4 人工智能的主要研究领域,人工生命是以计算机为研究工具，模拟自然界的生命现象，生成表现自然生命系统行为特点的仿真系统。主要研究进化的模式和方式、人工仿生学、进化博弈、分子进化、免疫系统进化、学习等；具有自治性、智能性、反应性、预动性和社会性的智能主体的形式化模型、通信方式、协作策略；研究生物感悟的机器人、自治和自适应机器人、进化机器人、人工脑。,24. 人工生命,第 2 章 知识表示,教材： 王万良人工智能导论（第3版） 高等教育出版社，2011. 2,50,第2章 知识表示,人类的智能活动主要是获得并运用知识。知识是智能的基础。为了使计算机具有智能，能模拟人类的智能行为，就必须使它具有知识。但知识需要用适当的模式表示出来才能存储到计算机中去，因此，知识的表示成为人工智能中一个十分重要的研究课题。本章将首先介绍知识与知识表示的概念，然后介绍一阶谓词逻辑、产生式、框架、语义网络等当前人工智能中应用比较广泛的知识表示方法，为后面介绍推理方法、专家系统等奠定基础。,51,第2章 知识表示,2.1 知识与知识表示的概念 2.2 一阶谓词逻辑表示法 2.3 产生式表示法 2.4 框架表示法,52,第2章 知识表示,2.1 知识与知识表示的概念 2.2 一阶谓词逻辑表示法 2.3 产生式表示法 2.4 框架表示法,53,2.1.1 知识的概念,知识：在长期的生活及社会实践中、在科学研究及实验中积累起来的对客观世界的认识与经验。知识：把有关信息关联在一起所形成的信息结构。 知识反映了客观世界中事物之间的关系，不同事物或者相同事物间的不同关系形成了不同的知识。,信息关联形式：“如果，则” 如果大雁向南飞，则冬天就要来临了。, 规则, 事实,例如： “雪是白色的” 。 “如果头痛且流涕，则有可能患了感冒” 。,54,2.1.2 知识的特性,1.相对正确性 任何知识都是在一定的条件及环境下产生的，在这种条件及环境下才是正确的。,1+1=2 （十进制）1+1=10 (二进制）,55,2.1.2 知识的特性,不确定性,随机性引起的不确定性 模糊性引起的不确定性 经验引起的不确定性 不完全性引起的不确定性,知识状态：“真” “假” “真”与“假”之间的中间状态,“如果头痛且流涕，则有可能患了感冒”,小李很高,56,2.1.2 知识的特性,可表示性与可利用性 知识的可表示性: 知识可以用适当形式表示出来，如用语言、文字、图形、神经网络等。 知识的可利用性: 知识可以被利用。,57,2.1.3 知识的表示,知识表示（knowledge representation）：将人类知识形式化或者模型化。 知识表示是对知识的一种描述，或者说是一组约定，一种计算机可以接受的用于描述知识的数据结构。 选择知识表示方法的原则：,（1）充分表示领域知识。 （2）有利于对知识的利用。（3）便于对知识的组织、维护与管理。 （4）便于理解与实现。,58,第2章 知识表示,2.1 知识与知识表示的概念 2.2 一阶谓词逻辑表示法 2.3 产生式表示法 2.4 框架表示法,59,2.2 一阶谓词逻辑表示法,60,2.2 一阶谓词逻辑表示法,2.2.1 命题2.2.2 谓词2.2.3 谓词公式2.2.4 谓词公式的性质2.2.5 一阶谓词逻辑知识表示方法2.2.6 一阶谓词逻辑表示法的特点,61,命题逻辑：研究命题及命题之间关系的符号逻辑系统。 命题逻辑表示法：无法把它所描述的事物的结构及逻辑特征反映出来，也不能把不同事物间的共同特征表述出来。,2.2.1 命题,命题（proposition）：一个非真即假的陈述句。 若命题的意义为真，称它的真值为真，记为 T。 若命题的意义为假，称它的真值为假，记为 F。 一个命题可在一种条件下为真，在另一种条件下为假。,例如：35,例如：太阳从西边升起,例: 1110,P：老李是小李的父亲,P：北京是中华人民共和国的首都,P：李白是诗人Q：杜甫也是诗人,62,2.2.2 谓词,谓词的一般形式： P (x1, x2, xn)个体 x1, x2, xn ：某个独立存在的事物或者某个抽象的概念；谓词名 P：刻画个体的性质、状态或个体间的关系。,“老张是一个教师”：一元谓词 Teacher (Zhang) “53” ：二元谓词 Greater (5, 3) “Smith作为一个工程师为IBM工作”： 三元谓词 Works (Smith, IBM, engineer),（1）个体是常量：一个或者一组指定的个体。,63,2.2.2 谓词,（2）个体是变元（变量）：没有指定的一个或者一组个体。,“小李的父亲是教师”：Teacher (father (Li) ),（3）个体是函数：一个个体到另一个个体的映射。,“x5” ：Less(x, 5),（4）个体是谓词,“Smith作为一个工程师为IBM工作”：二阶谓词 Works (engineer (Smith), IBM),64,2.2.3 谓词公式,1. 连接词（连词）（1）： “否定” （ negation ）或 “非”。（2）： “析取”（disjunction）或。（3）： “合取”（conjunction）与。,“机器人不在2号房间”： Inroom (robot, r2),“李明打篮球或踢足球”：Plays (Liming, basketball) Plays (Liming, football),“我喜欢音乐和绘画”： Like (I, music) Like (I, painting),65,2.2.3 谓词公式,1. 连接词（连词）（4）：“蕴含”(implication)或 “条件”(condition)。,“如果刘华跑得最快，那么他取得冠军。” ： RUNS (Liuhua，faster)WINS (Liuhua ，champion),（5） ：“等价”（equivalence）或“双条件” （bicondition）。 P Q: “P当且仅当Q”。,66,2.2.3 谓词公式,1. 连接词（连词）,谓词逻辑真值表,67,2.2.3 谓词公式,2. 量词（quantifier）（1）全称量词（universal quantifier）（ x）：“对个体域中的所有（或任一个）个体 x ”。,“所有的机器人都是灰色的”： ( x)ROBOT (x) COLOR (x，GRAY),（2）存在量词（existential quantifier）（ x）：“在个体域中存在个体 x ”。,“1号房间有个物体”： （ x）INROOM（x，r1）,68,2.2.3 谓词公式,全称量词和存在量词举例：,( x)( y) F(x, y) 表示对于个体域中的任何个体x都存在个体y，x与y是朋友。 ( x)( y) F(x, y) 表示在个体域中存在个体x，与个体域中的任何个体y都是朋友。 ( x)( y) F(x, y) 表示在个体域中存在个体x与个体y，x与y是朋友。 ( x)( y) F(x, y) 表示对于个体域中的任何两个个体x和y，x与y都是朋友。,69,2.2.3 谓词公式,全称量词和存在量词出现的次序将影响命题的意思。例如：,( x)( y)(Employee(x) Manager(y, x) : “每个雇员都有一个经理。” ( y)( x)(Employee(x) Manager(y, x): “有一个人是所有雇员的经理。”,70,2.2.3 谓词公式,3. 谓词公式定义2.2 可按下述规则得到谓词演算的谓词公式：,(1)单个谓词是谓词公式，称为原子谓词公式。(2)若A是谓词公式，则A也是谓词公式。 (3)若A，B都是谓词公式，则AB，AB，AB， A B也都是谓词公式。 若A是谓词公式，则 ( x) A，( x)A也是谓词公式。 有限步应用（1）（4）生成的公式也是谓词公式。,连接词的优先级别从高到低排列： ， ， ， ，,71,2.2.3 谓词公式,4量词的辖域 量词的辖域：位于量词后面的单个谓词或者用括弧括起来的谓词公式。约束变元与自由变元：辖域内与量词中同名的变元称为约束变元，不同名的变元称为自由变元。,例如： ( x)(P(x, y) Q (x, y)R(x, y) (P(x, y) Q (x, y) ：( x)的辖域，辖域内的变元x是受（ x）约束的变元，R(x, y)中的x是自由变元。 公式中的所有y都是自由变元。,72,2.2.4 谓词公式的性质,1. 谓词公式的解释 谓词公式在个体域上的解释：个体域中的实体对谓词演算表达式的每个常量、变量、谓词和函数符号的指派。,Friends (george, x)Friends (george, susie) TFriends (george, kate) F,对于每一个解释，谓词公式都可求出一个真值（T或F）。,73,2.2.4 谓词公式的性质,2. 谓词公式的永真性、可满足性、不可满足性,定义2.5 对于谓词公式P，如果至少存在一个解释使得P在此解释下的真值为T，则称P是可满足的，否则，则称P是不可满足的。,定义2.4 如果谓词公式P对个体域D上的任何一个解释都取得真值F，则称P在D上是永假的；如果P在每个非空个体域上均永假，则称P永假。,定义2.3 如果谓词公式P对个体域D上的任何一个解释都取得真值T，则称P在D上是永真的；如果P在每个非空个体域上均永真，则称P永真。,74,2.2.4 谓词公式的性质,3. 谓词公式的等价性,定义2.6 设P与Q是两个谓词公式，D是它们共同的个体域，若对D上的任何一个解释，P与Q都有相同的真值，则称公式P和Q在D上是等价的。如果D是任意个体域，则称P和Q是等价的，记为P Q 。（4）德.摩根律(De. Morgen) （8）连接词化规律（蕴含、等价等值式） （10）量词转换律,75,2.2.4 谓词公式的性质,4. 谓词公式的永真蕴含,定义2.7 对于谓词公式P与Q，如果PQ永真，则称公式P永真蕴含Q，且称Q为P的逻辑结论，称P为Q的前提，记为P Q。（3）假言推理 （4）拒取式推理 （5）假言三段论,76,2.2.4 谓词公式的性质,谓词逻辑的其他推理规则 P规则：在推理的任何步骤上都可引入前提。 T规则：在推理过程中，如果前面步骤中有一个或多个公式永真蕴含公式S，则可把S引入推理过程中。 CP规则：如果能从任意引入的命题R和前提集合中推出S来，则可从前提集合推出R S来。,77,2.2.4 谓词公式的性质,所有的人都是会死的， 因为诸葛亮是人， Human（Zhugeliang） 所以诸葛亮是会死的。 Die（Zhugeliang）, 1 P规则 2 Human（Zhugeliang） P规则 1, 2 Die（Zhugeliang） T规则,78,2.2.4 谓词公式的性质,谓词逻辑的其他推理规则： 反证法： ，当且仅当 ，即Q为P的逻辑结论，当且仅当 是不可满足的。,定理：Q为 ， ， ， 的逻辑结论，当且仅当 是不可满足的。,79,2.2.5 一阶谓词逻辑知识表示方法,谓词公式表示知识的步骤：（1）定义谓词及个体。（2）变元赋值。（3）用连接词连接各个谓词，形成谓词公式。,例如： 用一阶谓词逻辑表示下列关系数据库。住户 房间 电话号码 房间Zhang 201 491 201Li 201 492 201Wang 202 451 202Zhao 203 451 203,Occupant,Telephone,80,用一阶谓词表示： Occupant（Zhang ， 201） Occupant（Li，201） Occupant（Wang， 202） Occupant（Zhao， 203） Telephone（491，201） Telephone（492，201） Telephone（451，202） Telephone（451，203）,2.2.5 一阶谓词逻辑知识表示方法,81,2.2.6 一阶谓词逻辑表示法的特点,优点： 自然性 精确性 严密性 容易实现,应用：（1）自动问答系统（Green等人研制的QA3系统）（2）机器人行动规划系统（Fikes等人研制的STRIPS系统）（3）机器博弈系统（Filman等人研制的FOL系统）（4）问题求解系统（Kowalski等设计的PS系统）,局限性： 不能表示不确定的知识 组合爆炸 效率低,82,第2章 知识表示,2.1 知识与知识表示的概念 2.2 一阶谓词逻辑表示法 2.3 产生式表示法 2.4 框架表示法,83,2.3 产生式表示法,2.3.1 产生式2.3.2 产生式系统2.3.3 产生式系统动物识别系统2.3.4 产生式表示法的特点,84,2.3.1 产生式,“产生式”：1943年，美国数学家波斯特（E. Post）首先提出。 1972年，纽厄尔和西蒙在研究人类的认知模型中开发了基于规则的产生式系统。产生式通常用于表示事实、规则以及它们的不确定性度量，适合于表示事实性知识和规则性知识。,85,2.3.1 产生式,确定性规则知识的产生式表示,2. 不确定性规则知识的产生式表示,基本形式： IF P THEN Q 或者： 例如： r4：IF 动物会飞 AND 会下蛋 THEN 该动物是鸟,基本形式： IF P THEN Q （置信度） 或者： （置信度） 例如： IF 发烧 THEN 感冒 （0.6）,86,2.3.1 产生式,3. 确定性事实性知识的产生式表示,4. 不确定性事实性知识的产生式表示,三元组表示：（对象，属性，值） 或者：（关系，对象1，对象2） 例： 老李年龄是40岁： （Li，age，40） 老李和老王是朋友：（friend，Li，Wang）,四元组表示：（对象，属性，值，置信度） 或者： （关系，对象1，对象2，置信度）例：老李年龄很可能是40岁：（Li，age，40，0.8） 老李和老王不大可能是朋友：（friend，Li，Wang，0.1）,87,2.3.1 产生式,产生式与谓词逻辑中的蕴含式的区别：（1）除逻辑蕴含外，产生式还包括各种操作、规则、变换、算子、函数等。例如，“如果炉温超过上限，则立即关闭风门”是一个产生式，但不是蕴含式。（2）蕴含式只能表示精确知识，而产生式不仅可以表示精确的知识，还可以表示不精确知识。蕴含式的匹配总要求是精确的。产生式匹配可以是精确的，也可以是不精确的，只要按某种算法求出的相似度落在预先指定的范围内就认为是可匹配的。,88,2.3.1 产生式,产生式的形式描述及语义巴科斯范式BNF（backus normal form）,:= :=|:=|:=ANDAND |OROR:=(，),符号“:=”表示“定义为”；符号“|”表示“或者是”；符号“ ”表示“可缺省”。,89,2.3.2 产生式系统,控,制,规则库,推理机,综合数据库,产生式系统的基本结构,90,2.3.2 产生式系统,1. 规则库,2. 综合数据库,规则库: 用于描述相应领域内知识的产生式集合。,综合数据库(事实库、上下文、黑板等)：一个用于存放问题求解过程中各种当前信息的数据结构。,3控制系统,控制系统（推理机构）：由一组程序组成，负责整个产生式系统的运行，实现对问题的求解。,91,2.3.2 产生式系统,3控制系统（续）,控制系统要做以下几项工作： （1）从规则库中选择与综合数据库中的已知事实进行匹配。 （2）匹配成功的规则可能不止一条，进行冲突消解。（ 3）执行某一规则时，如果其右部是一个或多个结论，则把这些结论加入到综合数据库中：如果其右部是一个或多个操作，则执行这些操作。 （ 4）对于不确定性知识，在执行每一条规则时还要按一定的算法计算结论的不确定性。（ 5）检查综合数据库中是否包含了最终结论，决定是否停止系统的运行。,92,2.3.3 产生式系统的例子动物识别系统,例如：动物识别系统识别虎、金钱豹、斑马、长颈鹿、鸵鸟、企鹅、信天翁等七种动物的产生式系统。,93,2.3.3 产生式系统的例子动物识别系统,规则库：,r1： IF 该动物有毛发 THEN 该动物是哺乳动物r2： IF 该动物有奶 THEN 该动物是哺乳动物r3： IF 该动物有羽毛 THEN 该动物是鸟r4： IF 该动物会飞 AND 会下蛋 THEN 该动物是鸟r5： IF 该动物吃肉 THEN 该动物是食肉动物r6： IF 该动物有犬齿 AND 有爪 AND 眼盯前方 THEN 该动物是食肉动物r7： IF 该动物是哺乳动物 AND 有蹄 THEN 该动物是有蹄类动物r 8： IF 该动物是哺乳动物 AND 是反刍动物 THEN 该动物是有蹄类动物,94,2.3.3 产生式系统的例子动物识别系统,r9： IF 该动物是哺乳动物 AND 是食肉动物 AND 是黄褐色 AND 身上有暗斑点 THEN 该动物是金钱豹 r10：IF 该动物是哺乳动物 AND 是食肉动物 AND 是黄褐色 AND 身上有黑色条纹 THEN 该动物是虎 r11： IF 该动物是有蹄类动物 AND 有长脖子 AND 有长腿 AND 身上有暗斑点 THEN 该动物是长颈鹿 r 12：IF 该动物有蹄类动物 AND 身上有黑色条纹 THEN 该动物是斑马r13：IF 该动物是鸟 AND 有长脖子 AND 有长腿 AND 不会飞 AND 有黑白二色 THEN 该动物是鸵鸟r14： IF 该动物是鸟 AND 会游泳 AND 不会飞 AND 有黑白二色 THEN 该动物是企鹅 r15： IF 该动物是鸟 AND 善飞 THEN 该动物是信天翁,95,2.3.3 产生式系统的例子动物识别系统,设已知初始事实存放在综合数据库中： 该动物身上有：暗斑点，长脖子，长腿，奶，蹄 推理机构的工作过程 ：（1）从规则库中取出r1，检查其前提是否可与综合数据库中的已知事实匹配。匹配失败则r1不能被用于推理。然后取r2进行同样的工作。匹配成功则r2被执行。 综合数据库 ： 该动物身上有：暗斑点，长脖子，长腿，奶，蹄，哺乳动物,96,2.3.3 产生式系统的例子动物识别系统,（2）分别用r3，r4，r5，r6综合数据库中的已知事实进行匹配，均不成功。 r7匹配成功，执行r7 。 综合数据库： 该动物身上有：暗斑点，长脖子，长腿，奶，蹄，哺乳动物，有蹄类动物（3）r11匹配成功，并推出 “该动物是长颈鹿” 。,推理机构的工作