人工智能讲稿难点.doc

人工智能Artificial Intelligence AI 第一章：概述 产业革命成功地实现了用机器来替代人类长期从事的一些笨重、危险的体力劳动，可以说人类的体能在力量和速度上被机器放大了。机器甚至能完成人类手工不能完成的许多工作，机器使人类从繁重的体力劳动中解放出来。人类很早就开始了智能问题的研究和探索，到20世纪50年代（1950），随着数字计算机的发明和快速发展，被日益广泛的应用于替代人类进行数字运算处理，极大的提高了数字运算的速度和效率。人们自然联想到能否用这样的“机器”来替代人类非数字运算的其它智力劳动，放大人类的智能。许多学科的一大批科学家和工程技术人员投入到这一领域的研究和开发。人工智能经过长期的孕育过程，终于诞生了。人工智能是当前科学技术发展中的一门前言学科；是一门新思想、新观念、新理论、新技术不断出现的科学，正在迅速发展的学科。它是在计算机科学、控制论、信息论、神经心理学、哲学、语言学等众多学科的基础上发展起来的，是一门综合性的边缘学科。1.1 什么是人工智能1.1.1 智能 （ Intelligence ）什么是智能？智能的本质是什么？是古今中外许多科学家至今仍在努力探索的问题，一直没有完全解决。智能问题被列为四大自然奥秘之一：- 智能的发生、物质的本质、宇宙的起源、生命的本质。一、关于智能的理论目前人们通常基于对人的大脑的已有认识，将其与智能的外在表现结合起来，从不同角度、不同侧面、用不同的方法对智能进行研究，提出的观点和得出的结论也不相同。很难给出一个统一的、科学的智能定义。其中比较有影响的思维理论、知识阈值理论、进化理论等。1 思维理论认为智能的核心是思维，人的一切智慧或智能都来自于大脑的思维活动，人的一切知识都是人们思维的产物，因而通过对思维规律和方法的研究可望揭示智能的本质。2 知识阈值理论强调知识对于智能的重要性和作用。认为智能行为取决于知识的数量及其一般化程度，一个系统之所以具有智能是因为它具有可运用的知识。将智能定义为：智能就是在巨大搜索空间中找到满意解的能力。这一理论在人工智能发展史上有着重要的影响，知识工程、专家系统等都是在这一理论影响下发展起来的。3 进化理论有 MIT 的 R.A.Brook 教授提出，1991年提出“没有表达的智能”，1992年提出“没有推理的智能”。认为人的本质能力是在动态环境中的对外界事物的感知能力、行动能力、维持生命的能力和繁衍生息的能力等，正是这些能力为智能的发展提供了基础。这个理论的核心是用控制取代表式，从而去消概念、模型、及显示表示的知识，否定抽象对于智能及智能模拟的必要性，强调分层结构对于智能进化的可能性和必要性。尚未形成完整的理论体系。二、智能的特征1 具有感知能力通过视觉、听觉、触觉、味觉、嗅觉等感知器官获取外界环境信息，经过大脑加工为知识。人类感知的信息80%通过视觉、10%通过听觉。2 具有记忆及思维能力记忆和思维是人脑的重要功能，是人类具有智能的根本原因之所在。记忆 存储感知的环境信息和有思维产生的值是。思维 对记忆的信息进行处理，即利用已有知识对信息进行分析、计算、比较、判断、推理、决策等。思维是一个动态的过程，是获取知识和运用知识求解问题的根本途径。三种思维方式：逻辑思维（抽象思维）形象思维（直感思维）顿悟思维（灵感思维）3 具有学习能力和自适应能力学习是人的本能，每个人随时随地都在学习。自觉的、有意识的学习；不自觉、无意识的学习；有教师指导的学习；通过自身实践的学习。人类通过和环境的相互作用，不断的进行学习、积累知识、增长能力，适应环境的变化。由于人类个体所出的环境不同、条件不同，学习的效果不同，体现出个体智能的差异性。4 具有行为能力响应感知的环境输入信息，自觉或下意识的做出动作行为。1.1.2 人工智能 Artificial Intelligence1 智能机器 能够在各种环境下，自主地或交互地执行各种拟人任务的机器。2 人工智能学科 是计算机科学中涉及研究、设计和使用智能机器的一个分支。它的近期目标在于研究用机器来模仿和执行人脑的某些功能，并开发相关理论和技术。3 人工智能能力 智能机器执行的通常与人类智能有关的功能，如感知、分析、判断、推理、证明、识别、理解、设计、思考、规划、学习和问题求解等思维活动。4 人工智能是计算机科学的一个分支，是研究使用计算机来完成能表现人类智能任务的科学。主要包括计算机实现智能的原理，制造类似人脑的智能计算机，以及使计算机更巧妙地实现更高级的应用。它涉及到计算机科学、心理学、哲学和语言学等。总的目标是扩展人类的智能活动。5 从实用的观点看，是一门知识工程学，以知识为对象，研究知识的获取、知识的表示方法、知识的实用。6 Nils J. Nilsson (U.S.A)Artificial Intelligence ( AI ), Broadly ( and some what circularly ) defined, is concerned with intelligent behavior in artifacts. Intelligent behavior, in turn, involves perception, reasoning, learning, communicating, and acting in complex environments. AI has as one of its long-term goals the development of machines that can do these things as well as humans can, or possibly even better. Another goal of AI is to understand this kind of behavior whether it occurs in machines or in humans or other animals. Thus, AI has both engineering and scientific goals. 1.1.3 机器智能实验 - 图灵实验A. M. Turing 19241954 英国超时代的天才数学家。1950年发表论文 ”Computing Machinery and Intelligence”，文中提出 Can Machines think? 并给出了著名的 Turing Test - 图灵测试，用于测试一台机器是否具有智能。图灵测试：将智力健全的人和智能机器分别置于两个房间，彼此不可见，但可以通话。通过交谈，如果人不能辨别对方是计器或是人，那么这台机器即具有智能。 图灵还设计了成为“图灵梦想”的问题对答：人询问者、机器智者；假设两者都读过狄更斯 ( C. Dickens ) 的小说匹克威克外传。询问者： 你的14行诗的首行为“你如同夏日”，你不觉得“春日”更好吗？智 者： 它不合韵。询问者： “冬日”如何？它可是完全合韵的。智 者： 它确是合韵的，但没有人愿被比为“冬日”。询问者： 你不是说过匹克威克先生能让你想起圣诞节吗？智 者： 是的。询问者： 圣诞节是冬天的一个日子，我想匹克威克先生对这个比喻不会介意吧？智 者： 我认为你不够严谨，“冬日”指的是一般的冬天的日子，而不是某个特别的日子，如圣诞节。 图灵测试存在的问题：1。人的智力水平；2。问题的智力标准；3。实验强调了结果，不能反映思维的过程。1.1.4 人工智能与传统程序的区别1. 研究符号表示的知识，而不只是数值、数据；2. 启发式推理方法，而不是传统算法；3. 控制结构和领域知识分离；4. 允许结果误差、甚至错误。1.2 人工智能发展简史“人工智能”，1956年首次作为一门新兴学科正式提出，现在已经成为一门充满生机和希望的前沿学科，是涉及到计算机科学、心理学、哲学、数学等许多学科的交叉学科。已经获得了许多重要的理论和技术成果。它的发展经历了孕育、形成、发展等几个阶段。一、孕育（1956年之前）1公元前，亚里斯多德（Aristotle, 公元前384322年）在其名著工具论中提出了形式逻辑的一些主要定律，他提出的三段论至今仍是演绎推理的基本依据。2英国科学家培根（ F. Bacon, 1562-1626 ）曾系统提出了归纳法。3德国数学家莱布尼兹（ G. Leibniz, 16461761 ）提出了万能符号和推理计算的思想4英国逻辑学家布尔（G. Boole,18151864）布尔代数在思维法则中首先用符号语言描述了思维活动的基本推理规则。5 英国数学家图灵（ Turing ）1936年提出理想计算的数字模型图灵机为数字计算机诞生奠定理论基础。6美国神经生理学家麦克洛奇（W. Moculloch）与匹滋（W. pits）1947年提出一个神经网络模型（MP）模型，至今仍在使用。7美国数学家莫克利（J.W.Mauchly）和埃克特（J.P.Eckert）在1946年研制出的第一台电子计算机ENIAC。二、形成（1956-1969）1956年夏天，美国Dartmouth大学年轻的数学助教J. W. McCarthy 联合他的三个朋友：M. L. Minsky - 哈佛大学年轻的数学家和神经学家， N. Lochester - IBM 信息研究中心负责人， C. E. Shannon - 贝尔实验室研究信息的数学家 ，四人共同发起并邀请： T. More - IBMA. L. Samuel - IBMO. Selfredge - MITR. Solomonff - MITA. Newell - RANDH. A. Simon Carnagie （卡奈基梅隆大学）举办长达两个月的夏季研讨班。这次会上首次使用”Artificial Intelligence AI ”一词，标志着AI学科的正式诞生。 自这次会议后10年，人工智能研究取得了许多令人瞩目的成就。1 纽厄尔.肖和西蒙合作编制了称逻辑理论机的程序系统，模拟人用数学逻辑证明定理的思维规律，用分解（分解为子问题），代入（常量代入变量），替换等方法，处理待定的定理。该程序证明了数学原理第二章中的38条定理，改进后，1963年证明了该章全部52条定理。2 1956年塞缪尔研制跳棋程序具有自学习、自组织和自适应能力，是一个启发式程序。可以向人学习下棋经验，自己积累经验，学习棋谱。1959年击败本人，1960 年击败一个洲冠军。31958年美籍华人数理逻辑学家王浩，在IBM 704上证明了数学原理中有关命题演算的全部220条定理，150条谓词演算定理中的80%。1959年用8.4分钟完成上述全部工作。41965年Robinson提出归结原理。5模式识别方面1959年O. Selfredge模式识别程序。1965年Roberts 编制出分辨积木结构程序。6 题求解方面1960年Newell等通过心理学实验总结出了人们求解问题的规律，编制了通用问题求解程序GPS，可用来求解11种问题，GPS研究共持续10年。7 家系统方面E. A. Feigenbaum自1965年开始研究DENDRAL，1968年完成并进入使用。质谱仪数据，推断化合物的分子结构。8 人工智能语言1960年McCarthy研制出Lisp语言。9 1969年成立了国际人工智能联合会（IJCAI）, International Joint Conferences On Artificial Intelligence 里程碑，标志人工智能学科得到肯定与公认。三、发展（1970年后）世界范围的研究和探索。 1972年法国马赛大学的A.Comerauer，实现prolog。1972年MYCIN诊断和治疗感染新性疾病专家系统。1970年 International Journal of AI 创刊。1972年WinograelShrdlv 自然语言理解系统。1974年Minsky框架表示法。1977年Feignbaum知识工程。其它专家系统：80年代专家系统和知识工程迅速发展，推理技术、知识获取、自然语言理解、机器视觉研究、不确定、非单调推理、定性推理。神经网络提出Hopfield网络，Rumelhart提出BP学习算法。90年代，理论化、实用化方向迅速发展。四、 中国人工智能研究1978年智能模拟研究纳入国家计划。1984年智能计算机及其系统全国学术讨论。1986年智能计算机系统、智能机器人和智能信息处理（含模式识别）纳入高技术计划。1993年智能控制和智能自动化纳入攀登计划。1981年后相继成立：中国人工智能学会（CAAL）;全国高校人工智能研究会；中国计算机学会人工智能与模式识别专业；中国自动化学会模式识别委员会与机器智能委员会；中国软行业协会人工智能协会；中国智能机器人专业委员会；中国计算机视觉与智能制专业委员会；中国智能自动化专业委员会。1989年召开中国人工智能控制联合会议。1987年模式识别与人工智能创刊。五、 曲折经历Newell和Simon 1958年预言：不出十年计算机将成为世界象棋冠军，除非通过一个比赛规则不准它参加。不出十年计算机将发现并证明那时还未明的数字定理。不出十年计算机将谱写出具有相当美学价值并被评论家们认可的乐曲。不出十年大多数心里学家的理论将采用计算机程序来形成。然而多年过去了，没有一样完全实现。塞缪尔的下棋程序与世界冠军对弈时，5：4败。机器翻译更是出了很多问题，只依赖一部双向字典进行互译：英语：out of sight, out of mind; 俄语：又瞎又疯； 英语：Time flies like an arrow 光阴似箭 日语，回译变成：苍蝇喜欢箭 Flies like an arrow.俄语：The spirit is willing ，but the flesh is weak心有余而力不足英语：The wine is good ，but the meat is spoiled酒是好的，但肉变质了。英美减少对人工智能研究的资助。前苏联将其视为异端邪说。中国更没有涉入该领域。1 图灵机和冯.诺依曼机处理智能活动的不足。2 博弈的困难：组合爆炸，状态空间巨大，跳棋：1010 , 国际象棋10100, 围棋101000 ,如此巨大的状态空间，现有计算机无法忍受。1997年5月3日5月11日世界国际象棋大师卡斯帕罗夫与IBM公司的RS/6000SP（深蓝）计算机下棋，深蓝以3.5：2.5胜，其并速计算能力为210100步/S。3 机器翻译。 4 自动定理证明和GPS局限。5 模式识别困惑。6 自动程序设计的困难。Simon 1988年12月，日本东京第二次第五代计算机系统国际会议说：从一开始，人工智能和认知科学工作者就因过分乐观而受人指责。我希望我们已为某些乐观而感到内疚了，而且对于一个经历了30多年历程才走到今天这一步的一个领域来说，我也不认为这种指责和内疚是过分的。1.3 人工智能的研究与应用领域一 问题求解 通过搜索方法寻找问题求解操作的一个合适序列以满足问题的要求。二 逻辑推理和定理证明三 自然语言理解四 自动程序设计程序验证，程序综合。五 专家系统六 机器学习七 机器人八 模式识别九 人工神经网络 十 机器视觉十一 智能控制十二 智能检索十三 智能决策支持（专家系统）十四 Agent 及应用1.4 人工智能的研究途径一 以符号处理为核心的方法功能模拟，不管人脑思维过程。二 以网络连接为主的连接机制方法模拟人脑的物理结构，思维过程。三 系统集成两者集成：1.5 人工智能的研究目标一 近期目标1、 如何用计算机去做过去只有靠人的智力才能完成的工作。2、 依赖现有计算机去模拟人类某些智能行为的基本理论、基本技术和基本方法。3、 探讨智能的基本机理。二 最终目标1、 造出智能机器。2、 李艾特和费根鲍姆提出9个最终目标：（1）理解人知识；（2）有效的自动化；（3）有效的智能拓展；（4）超人智力（5）通用问题解；（6）连贯性交谈；（7）自治自主决策；（8）学习；（9）储存信息。1.6 人工智能的争论与展望一、 争论1、 信与不信2、 学派之争。二、 对人类的影响1、 经济影响2、 社会影响3、 文化影响三、 展望 第二章：知识表示方法 将要求解的问题以计算机能理解并能有效处理的知识的表达方法。2.1 状态空间法2.1.1 问题的状态描述1 状态 ( state )为描述某类不同事物间差别而引入的一组最少变量q1、q2、.、qn的有序集合。矢量形式：Q= q0,q1,qn T状态变量：qi ( I=0,1,n )给定每个变量的一组值就得到一个具体的状态。Q1= q01,q11,q21,qn1 T例如：确定地球表面位置-经、纬度 矩形面积-长、高2 操作符（算符）( Operator )使问题从一种状态变为另一种状态的手段。3 问题的状态空间 ( State Space )一个表示该问题空间全部可能状态及其关系的图。概括起来可以用一个三元集合来表示问题的状态空间。问题所有可能的初始状态描述集合S集合操作符（算符）集合F集合目标状态描述G集合可以抽象地表示为：（ S，F，G ）例：15 Puzzle Problem 1 2 3 45 6 7 89 10 11 1213 14 15 操作符 初始状态 目标状态 3 5 8 76 2 1 49 15 1413 12 11 10 MoveUp MoveDown MoveLeft MoveRight2.1.2 状态图示法图示方法形象、直观，帮助对问题的理解。显式图示、隐式图示1 有向图 ( Directed Graph )节点，及连接节点的有向弧线的集合。 Ni (父节点、祖先节点) Nj(子节点、后裔节点) A B D E 祖先节点 后裔节点2 状态空间图示 用节点表示状态 弧线连接表示状态之间的关系，变化方向。可以在弧线上标注操作符，以及可能的路径代价。 Operator C( Ni,Nj) Ni (父节点、祖先节点) Nj(子节点、后裔节点) 路径代价：C( Ni,Nj )用来帮助确定使用某条路线求解问题的花费。2.1.3 状态空间表示举例例一：(Page 20) 一个推销员从A城市出发，旅行经过B、C、D、E四个城市，然后回到A市， 其他城市只能经过一次，寻找一条花费最少的旅行路径。 初始状态 (A,) 目标状态(A,x,y,z,u,A) 其中x,y,z,u为B,D,C,E之一 7 6 10 13 B 7 10 7 E A 13 10 6 C 9 6 10 5 D (A,B,)(AD,)(AC,)(AE,) . . . (A,C,D,E,B,A) 总的路径代价：Cost=6+5+6+10+7=34例二：( Page 21) 猴子和香蕉问题 ( Monkey and Banana Problem ) 在房间的a 处有一只猴子，b 处有一个箱子，c 处挂着一串香蕉，猴子欲想拿取香蕉，他必须首先走到 b 处，推动箱子到 C 处，然后爬上箱子才可以。假设猴子和箱子都只能做一维运动。用状态空间求解此问题。 C A C B 解：1 引入状态变量W 表示猴子的水平位置；x 布尔变量，标记猴子是否在箱子上。x = 1 猴子在箱子上,x = 0 不在箱子上；Y 箱子的水平位置；z 布尔变量，标记猴子是否已经拿到香蕉。z = 1 猴子拿到香蕉。用状态集合表示：（ W, x, Y, z ）初始状态：（ a, 0, b, 0 ）目标状态：（ c, 1, c, 1 ）2 引入操作算符(1)goto( U )猴子走到U位置 使用条件：y = 0 即猴子不能在箱子上。 使用goto(U)产生的状态变化： goto(U) （ W, 0, Y, z ） （ U, 0, Y, z ）(2)pushbox(U) 使用条件：y = 0 AND W=Y 即猴子不能在箱子上,且两者在同一位置。 使用pushbox(U)产生的状态变化： pushbox(U) （ W, 0, W, z ） （ U, 0, U, z ）(3)climbbox() 使用条件：y = 0 AND W=Y 即猴子不能在箱子上,且两者在同一位置。 使用climbbox()产生的状态变化： climbbox() （ W, 0, W, z ） （ U, 1, U, z ）(4)grasp() 使用条件：x = 1 AND W=Y=c 即猴子在箱子上,且两者都在c位置。 使用climbbox()产生的状态变化： climbbox() （ W, 0, W, z ） （ U, 1, U, z ）(3)用状态图求解( a, 0, b, 0 )Goto(U)( b, 1, b, 0 )( U, 0, b, 0 ) goto(U) U=b AND climbbox() U=bPushbox(V)( V, 0, V, 0 ) U=VGoto(U) pushbox(V) V=cclimbbox()Goto(U)( U, 0, V, 0 )( c, 1, c, 0 )Grasp()( c, 1, c, 1 )猴子拿香蕉的最佳操作序列： goto(b), pushbox(c), climbbox(), grasp() 22 问题归约法（ Problem Reduction ）问题归约法是通过操作符（算符）变换将初始问题集合，简化为一个简单的子问题的集合，直到这个子问题集合可以直接求解，从而使原问题得到解决。2.2.1 问题的归约描述一、 梵塔问题 （ Tower of Hanoi Puzzle）在三根柱子的一根上，按大小依次放有N个圆盘，现在要将这些盘子移动到另一根柱子上，可以借助第三根柱子。移动规则：每次只能移动一片；任何时候大盘子都不能压在小盘子上。使用状态空间法求解，共有27个节点（状态）。 1 2 3ABC问题规约分析：1. 要将所有的盘子都移动到3柱上，首先必须将C移动到3柱，且移动之前3柱为空。2. 只有在移开A、B后，才能移C，且A、B最好不要放在3柱上，即A、B应移动到2柱子上。3. 完成上述移动后，关键一步是将C从1移动到3，并继续上述过程，直至完成。由上述分析可见，可以将三盘子的移动问题，简化为一个盘子（C），和两个盘子（A、B）的移动问题，进一步分析，可将两个盘子的问题化也简为一个盘子的问题。通过分析将初始问题归约为三个子问题：.移动A、B到2柱的两盘问题.移动C盘到3柱的一盘问题.移动A、B到3柱的两盘问题解决了这三个子问题，则初始的三盘问题亦得到解决。二、 本原问题 本原问题：可以直接求解的问题叫做本原问题。 例：上面的移动一个盘子的问题。三、 问题的规约表示（描述）1 初始问题S即要求解问题的数学描述。2 算子集合O通过操作算子将一个问题转换成若干个子问题。3 本原问题集合P其中的每一个问题都不需要再证明，自然成立的问题。如公理、已知事实、或已经证明过的问题。这样问题归约法也可以抽象表示为：（ S，O，P ）归约目的：最终产生本原问题。 算子 算子 算子初始问题 子问题集合 子问题集合 本原问题问题归约中，如果每运用一次操作算子，只产生一个子问题，即为状态空间法。2.2.2 归约问题的与或图表示 S G1 G3 G2 1. 与或图起始节点对应初始问题描述其他节点对应子问题描述（1） 表示或关系 G1 OR G2 OR G3 S 表示G1、G2、G3中只要有一个可解，则S可解。 S G1 G3 G2 （2） 表示与关系在节点间加连接线，表示与关系。G1 AND G2 AND G3 S表示G1、G2、G3同时可解，则S可解。2. 终叶节点对应于本原问题描述的节点。3. 可解节点(1) 终叶节点是可解节点（对应本原问题）。(2) 如果某个非终叶节点有或后继节点，那么只有当其后继节点中至少有一个节点可解，则此非终叶节点可解。(3) 如果某个非终叶节点有与后继节点，那么只有当其全部后继节点可解时，此非终叶节点可解。4. 不可解节点(1) 没有后裔、并且不是终叶节点的节点不可解。(2) 如果某非终叶节点有或后继节点，当其所有后裔节点都不可解时，此非终叶节点不可解。(3) 如果某非终叶节点有与后继节点，其后裔节点只要有一个不可解，此非终叶节点不可解。2.2.3 问题归约机理2.3 谓词逻辑法( Predicate Logic )逻辑证明符号化逻辑方法是一种形式语言，也是到目前为止能够表达人类思维活动的一种最精确的语言，它与人类的自然语言较为接近，有很方便计算机处理和存储，最早成为人工智能的一种知识表示方法。现在已经发展有命题逻辑、谓词逻辑和多值逻辑三个层次，我们这里着重介绍一阶谓词逻辑。2.3.1 谓词演算( Predicate Calculus )一、 语法和语义1. 谓词逻辑组成 谓词符号表示事实、个体性质、个体之间关系、事件、情形等等。 变量符号 常量符号 函数符号 其他辅助符号括号、标点符号等。例：（1）机器人(Robot)在1号房间(Room1)里。 INROOM( Robot,Room1 ) 事实,INROOM,谓词符号；Robot,Room1常量符号。 INROOM( x,y ) x,y变量符号。 （2）李的父亲和母亲结婚。 MARRIED father( Li ), Mother( Li ) MARRIED谓词符号；father(Li),Mother(Li)函数。2. 项(1) 常量符号、变量符号是项；(2) 是任意n元函数，是项，则是项；(3) 有限次使用(1)、(2)生成的符号串叫做项。3. 原子公式 是任意n元谓词，是项，则是原子公式。二、 连(接)词和量词1. 连词(1) 合取(与)符号： 定义：A B 为真，当且仅当A、B同时为真。例子： 我喜欢音乐和绘画。 LIKE（ I，Music ） LIKE( I, Painting )同时性 李住在一幢黄色的房子里。 LIVES（ Li, House1 ） LIVES( House1, Yellow )同时性 (2) 析取（或）符号：定义：A B为假，当且仅当A、B同时为假。例子：李明大篮球或踢足球。 PLAYS（LiMing,Basketball）PLAYS（LiMing,Football）排斥或：一种可能发生，另一种可能性不可能发生的情形。 李现在在教室，或在实验室。 李在教室，就不可能在实验室；反之亦然。(3) 否定（非）符号：、定义：A为真，当且仅当A为假。例子：机器人不在2号房间里。 INROOM（Robot,Room2）排斥或例子：李现在在教室，或在操场。IN(Li,Classroom) IN(Li,Field) IN(Li,Classroom) IN(Li,Field) 李在教室，不在操场； 李在操场，不在教室(4) 蕴涵符号： ， =定义：A = B为假，当且仅当A为真，B为假。等价式：A B表达语义：如果A，则B。例子：如果刘华跑得最快，那么他取得冠军。 RUNS(LiuHua,Fastest) = WINS(LiuHua,Champion)2. 量词(1) 全称量词表达变量x在其论域内的所有可能取值，即对所有的x。记为：（）例子： 对所有的x， P(x)为真。()P(x) 所有的狗都有尾巴。() DOG(x) = HAVE(x,Tail) (2) 存在量词表达变量x在其论域内，存在着、有一个、或至少有一个取值，使P(x)为真。记为：()例子： 至少有一个x， 是P(x)为真。()P(x) 1号房间内有一个物体。()INROOM(x,Room1) 有的狗是黄色的。() DOG(x) = COLOR(x,Yellow) 2.3.3 谓词公式（合适、合式）一、 谓词公式定义1 原子公式是谓词公式；2 若A是谓词公式，则A也是谓词公式；3 若A、B是谓词公式，则 A B、A B、A = B也是谓词公式；4 若A是谓词公式，x为A的自由变元，则()A、()A也是谓词公式；5 按14 运算得出的表达式是谓词公式。例子：任何整数或为正，或为负。 引入谓词：I(x) x为整数 P(x) x为正数 N(x) x为负数() I(x) = (P(x) N(x) (P(x) N(x) 二、 谓词公式性质两个概念： 真值表PQPQPQPQP=QPQFFTTFFTTFTTFTFTTTFFTTFFFTTFFTTTT 谓词公式的等价公式两个谓词公式，无论如何解释，若两者的真值表相同，则两公式为等价谓词公式。1(P) P (否定之否定肯定)2. PQ P = Q3. 德.摩根定律( De.Morgen) (PQ） PQ (PQ) PQ 4. 分配率 P(QR) (PQ) (PR) P(QR) (PQ) (PR)5. 交换率 PQ QP PQ QP5. 结合率(PQ)R P(QR)(PQ)R P(QR)7. 逆否率P=Q Q = PPQ QP8. ()P(x) () P(x) ()P(x) () P(x) 验证：假定x的论域为非空有限集合，即x=()P(x) () P(x) 9. () P(x) Q(x) ()P(x) ()Q(x) () P(x) Q(x) () P(x) ()Q(x)10. ()P(x) ()P(y) ()P(x) ()P(y)Example: For every set y, there is a set y, such that the cardinality of y is greater than the cardinality of x.Import Predicate: SET(x) x is a set. CARD(x,y) y is the cardinality of x, and x is a set. GREAT(x,y) x is greater than y.()SET(x) = ()()()SET(y) CARD(x,u) CARD(y,v) GREAT(v,u)2.3.3 置换与合一一、 置换(Substitution)在表达式中，用特定的项去代换原来的变量。例子：Px, f(y), Bs1=z/x, w/y, Pz, f(w), Bs2=A/y, PA, f(y), Bs3=q(z)/x, A/y, Pq(z), F(a), Bs4=c/x, A/y, Pc, f(A), B置换能结合，但不一定能交换。L 一个表达式；s1,s2 为两个置换， 则 但是：二、 合一(Unification)寻找项对变量的置换，使得两个可合一（具有相同规律）的公式一致。 为可合一公式集合； s 寻找到的置换。做置换s ，使得：，即使得可合一公式集合中的每一个表达式，通过置换变的相同。例子：Px,f(y),B, Px,f(B),B s=A/x, B/y Px,f(y),Bs = PA,f(B),B Px,f(B),bs = PA,f(B),B 三、 最通用（一般）合一者 mgu (most general unifier)如果 Ei 是一个可合一公式集合，s 是任一合一者，使得 Eis=Eigs 成立，则称g 为最一般合一者。上例中：g=B/y; s=A/x四、 合一算法1 分歧集合(Disagreement Set)设有一非空有限公式集合 F=F1,F2,Fn， 从F中各个公式的第一个符号同时向右比较， 知道发现第一个不尽相同的符号为止， 从F的各个公式中取出那些以第一个不一致符号开始的最大的子表达式为元素，组成一个集合D， 称为F的分歧集合。2. 合一算法设F为非空有限公式集合，求mgu: 置 k=0， Fk=F， 其中为空集合，是不含任何元素的空置换； 若Fk只含有一个表达式， 算法停止， 就是mgu； 否则，找出Fk的分歧集Dk; 若Dk中存在元素，其中是变元，是项，且不在中出现，则置： k=k+1 GOTO 算法停止，F的mgu不存在。例1：F=Pa,x,f(g(y), Pz,h(z,u),f(u) 求mgu 。 不是单一表达式， k=1 k=2 k=3 为单一表达式， mgu=例2：P(x),P(A)-mgu=A/x例3：Pf(x),y,g(y), Pf(x),x,g(y)-mgu=x/y例4：Pf(x,g(A,y), g