人工智能总结考试小抄重点.pdf

人工智能第一章绪论本课程的学习内容1、智能体如何求解问题一一搜索2、智能体如何进行推理决策一一谓词逻辑与归结原理3、智能体如何描述和保存各种信息- - - 知识表示4、智能体如何通过训练获取和更新知识一一机器学习5、人工智能语言简^ - - - - prolog人类的智能什么是智能智能是个体有目的的行为、 合理的思维，以及有效的适应环境的综合性能力人类个体的智能感知环境：认识客观事物、客观世界与自我学习能力：取得经验、积累知识理解能力：理解知识，并能联想、推理、判断、决策预测能力：洞察事物发展变化的趋势语言能力：运用语言进行描述和概括应对能力：实时、迅速、合理的采取行动人类的智能人工智能与智能人工智能就其本质而言，是对人的思维的信息过程的模拟对于人的思维模拟可以从两条道路进行，一是结构模拟，仿照人脑的结构机制，制 造 出 “ 类人脑”的机器；二是功能模拟，暂时撇开人脑的内部结构，而从其功能过程进行模拟 人工智能”同人类智能的本质区别：人工智能纯系无意识的机械的物理的过程， 人类智能主要是生理和心理的过程人工智能与人类智能S tuart R ussell和 Peter N orvig把当前有关A I 的定义分成四类人工智能与人类智能类人行为与理性行为类人：按照人类模式思考和行为理性：在一定条件下正确的思考和行为理性与全知过马路例子中的智能体2 : 驾驶员计算危险距离与次危险距离如果危险距离内有行人，则紧急刹车如果次危险距离内有行人，则减速慢行否则，保持匀速前进什么是人工智能人 工 智 能(Artificial Intelligence,简称 AI)定义：P21、模拟人类的智能活动，即：感知、学习、理解、预测、应对外部世界的能力2、建造人造的智能系统，能够代替人类完成特定的智能行为人工智能的发展史一先驱神话，幻想和预言中的AI在古代的神话传说中， 技艺高超的工匠可以制作人造人，并为其赋予智能或意识中世纪出现了使用巫术或炼金术将意识赋予无生命物质的传说Samuel Butler的 “ 机器中的达尔文” 一文(1863)探讨了机器通过自然选择进化出智能的可能性.Pamela McCorduck在其著作“ 会思考的机器”中指出的,AI的 起 源 是 “ 古人成为造物神的愿望”形式推理一中国，印度和希腊哲学家均已在公元前的第一个千年里提出了形式推理的结构化方法，如亚里士多德的三段论人工智能的发展史一先驱自动机器1642年，数学家Pascal发明了加法机1694年， 数学家莱布尼兹Leibniz发明了世界上第一台计算器人工智能的发展史一先驱1834年，查尔斯？ 巴 贝 奇(Charles Babbage)构想和设计了一台完全可编程的用于公式演算的多功能计算机一巴贝奇分析仪由于技术条件， 经费限制， 以及无法忍耐对设计不停的修补,这台计算机在他有生之年始终未能问世。

尽管如此，巴贝奇分析仪仍然被公认是第一台打孔卡片计算机人工智能的发展史现代人工智能的孕育期(19434955年)1943年， 麦克克劳奇W.McCulloch和皮兹W.Pitts提出了人工神经元模型，被认为是A I的最早工作，并指出神经元网络可以学习海 布 D .H ebb,对神经元网络提出了一种更新规则，被称为海布学习1951年， 普林斯顿大学的博士研究生明斯基M.Minsky建造了一台神经元网络计算机1950年， 阿兰图灵A.M.Turing发表论文《 计算机器与智能》 ,描绘了 A I的完整景象人工智能的发展史图 灵 ( 1912-1954)英国数学家和逻辑学家，二十世纪最杰出的科学家之一，计算机科学之父，人工智能之父，可与美国的冯? 诺依曼相媲美的电脑天才冯? 诺依曼生前曾多次谦虚地说：现代计算机的概念当属于阿兰？ 图灵人工智能的发展史图灵英年早逝在 他 4 2 年的人生历程中，他的创造力是丰富多彩的24岁提出图灵机理论，28岁破解德国密码系统，3 1 岁开发计算机Colossus3 3 岁设想仿真系统，3 5 岁提出自动程序设计概念，3 8 岁 设 计 “ 图灵测试” 这一朵朵灵感浪花无不闪耀着他在计算机发展史上的预见性。

在他短暂的生涯中，图灵在量子力学、数理逻辑、生物学、化学方面都有深入的研究1948年起， 图灵因为个人生活方面的问题受到一系列不公正的待遇1954年，图灵死在自己的卧室里， 床头有一只咬了一小半的苹果人工智能的发展史图灵最高的成就是在计算机和人工智能方面， 他是这一领域开天辟地的大师为表彰他的贡献， 美国计算机学会A CM 1966年设立了 “ 图灵奖” ，颁发给最优秀的电脑科学家这枚奖章就像“ 诺贝尔奖” 一样，代表了计算机学科的最高荣誉到目前为止，唯一获此殊荣的华人是，Andrew C hi-C hihY ao（ 姚期智） 2000年由于在伪随机数的生成算法、加密算法和通讯复杂性方面的贡献获得图灵奖人工智能的发展史图灵机一条无限长的纸带T APE一个读写头H E A D一套控制规则T ABLE一个状态寄存器“ 图灵机”不是一种具体的机器，而是一种思想模型但是现代电脑确实是用相应的程序来完成设定好的任务 图灵机”奠定了整个现代计算机的理论基础在电脑史上与 “ 冯? 诺依曼机”齐名人工智能的发展史图灵测试第一次给出了检验计算机是否具有智能的哲学思想设想一个人类提问测试者， 一个声称自己是人的计算机A 和一个人类被测试者B测试者提出问题，A 与 B 分别回答。

如 果 A 与 B 的回答，使得人类测试者无法区分是人的回答还是计算机的回答，则计算机具有了智能人工智能的发展史图灵认为：如果在3 0 % 的实验中，机器迷惑了测试者，那么它就通过了测试并且预言，到 2000年将会有足够好的计算机通过图灵测试目前仍然没有能够成功通过图灵测试的电脑， 但已有电脑在测 试 中 “ 骗”过了测试者要通过图灵测试，要求计算机具有更多的技能自然语言处理、自动推理、 计算机感知能力、 知识表示、机器学习等能力，甚至能够模拟人类的情感和弱点人工智能的发展史人工智能的诞生1956:世界上第一次正式的AI会议美国的Dartmouth College,为期2月John McCarthy 正式提出“Artificial Intelligence” 这一术语,44computional rationality”著 名 参 加 者 ：J.McCarthy(1971)、C.Shannon、M.Minsky(1969)、A.Newell(1975) 、A.Simon(1975)、W.McCullochx S.Papert人工智能的发展史早期的期望与繁荣由于根深蒂固的相信“ 一台机器永远不可能做X " ， 一点点的人工智能的实现都是令人震惊的1959: Frank Rosenblatt 提出感知器模型( PerceptronModel）1959: MIT（ 麻 省 理 工 ）AI Lab 正 式 成 立（Minsky 和McCarthy）1958: Newell和Simon的四个预测十年内，计算机将成为世界象棋冠军十年内，计算机将发现或证明有意义的数学定理十年内，计算机将能谱写优美的乐曲十年内，计算机将能实现大多数的心理学理论人工智能的发展史困难与黑暗时期虽然机器能够解决一些极其错综复杂的难题，但有很多对人来说简单到不能再简单的事情，对电脑却难似上青天理解机器翻译问题：无限计算能力的幻觉尝试各种步骤可能组合——组合爆炸智能体结构的限制简单神经元网络虽然能够学习，但表示能力有限人工智能的发展史知识的力量一专家系统的兴起1977年，费根鲍姆E.Feigenbaum（ 1994）提出了 “ 知识工程”的概念，标志着A I研究从传统的以推理为中心，进入到以知识为中心的新阶段。

用大量的规则描述专业知识，采用启发式的解题方法专家系统在医疗、 自然语言理解、工程、军事和商业 等各个领域80年代初，美、英、 日等国先后投资数十亿美元用于AI工业，人工智能重新获得人们的普遍重视然而，商业的投机动机导致了过分承诺，野心勃勃的目标从来没有实现过，投资者在八十年代末重新撤回了投资.人工智能的发展史近年人工智能的发展趋势神经元网络的回归(1986- 今)多层反向神经元网络成为热点里程碑1997年，IBM计算机深蓝击败卡斯帕罗夫；2005年，Stanford开发的一个自动驾驶机器人成功的在一条沙漠小路上行驶131公里；2009年，Blue Brain Project宣称成功模拟部分鼠脑智能体技术兴起(intelligent agents)A I比以往的任何时候都更加谨慎， 却也更加成功人工智能的研究目标感知外部环境一一传感器设计通过学习获得和更新知识一一设计学习方法和元件存储和使用知识一一知识的形式化描述根据环境和知识进行分析、判断、预测和决策一一设计推理决策方法和元件根据决策作出动作和行为一一设计执行器人工智能的研究目标人工智能的应用知识工程以知识本身为处理对象，研究如何运用人工智能和软件技术，设计、构造和维护知识系统专家系统智能搜索引擎机器翻译和自然语言理解数据挖掘和知识发现人工智能的应用自动工程代替人类进行野外勘探、 自动驾驶、高危操作等工作自动驾驶自动装配海洋探索太空探索人工智能的应用机器视觉，模式识别指纹识别；视网膜识别；掌纹识别；人像识别；文字识别；图像识别；车牌识别；人工智能的应用机器思维与推理人机博弈定理证明自动程序设计人工智能的研究方法符号主义一一逻辑推理连接主义一一仿生学、心理学行为主义一一进化、控制论人工智能的研究方法符号主义传统人工智能是符号主义，它以N ewell和 S imon提出的物理符号系统假设为基础。

物理符号系统假设认为物理符号系统是智能行为充分和必要的条件该系统可以进行建立、修改、复制、删除等操作，以生成其它符号结构符号智能是以知识为基础，通过推理进行问题求解人工智能的研究方法连接主义研究非程序的、适应性的、大脑风格的信息处理的本质和能力人们也称它为神经计算1873年， 神经科学的发展使人们认识了神经元， 这一技术很快被运用于研究大脑结构和人类智能近年来的神经元网络迅速发展， 大量的神经网络的机理、模型、 算法不断地涌现出来以数据为基础，通过训练建立联系，进行问题求解包括人工神经网络、遗传算法、模糊系统、进化程序设计、人工生命等人工智能的研究方法行为主义Brooks提出了无需知识表示的智能、无需推理的智能他认为智能只是在与环境的交互作用中表现出来， 人们称为基于行为的人工智能，简言之，称为行为主义在许多方面是行为心理学观点在现代人工智能中的反映刺激反应性原理广泛的应用于简单智能体的构建中人工智能的学科基础人工智能是一门集大成的新兴学科，涉及到许多领域的知识哲学规则能否得到合理的结论意识是什么知识是从哪里来的知识如何导致行动人工智能的学科基础数学什么是合理的规则什么样的问题可以通过计算求解不确定的知识如何进行推理经济学与运筹学如何行为能够获得最好的结果博弈行为决策理论人工智能的学科基础神经科学大脑的结构人类神经系统的结构人类神经系统如何处理信息心理学人类和动物如何思考和行动语言学自然语言如何产生语言与思维的关系人工智能的学科基础控制论如何控制人工制品的按照预定的目标工作计算机工程如何制造具有能干的计算机人工智能第二章与或图搜索问题与或图基本概念耗散值的计算C(n)为k连接符的路径耗散值，N为目标节点集合，{nl ,n2 } 为由k连接符连接的i个节点，k(n,N)为节点n到N的耗散值，贝 肛与或图基本概念耗散值的计算h(s0)=12,h(sl)=9, h(s2)=3,h(s3)=2节点耗散计算公式为：f(n)=g(n)+h(n)f(s0)=12f(sl)=2+9=llf(s2)=2+6+2=10f(s3)=2+5+3=10K连接符需要考虑其全部分支f(k) =f(s2)+f(s3) =20;该算例中sO -sl的路径耗散加了 2次， 应根据实际问题确定与或图基本概念可解性判别一个节点是可解，则节点须满足下列条件之一:①终止节点是可解节点；②一个与节点可解，当且仅当其子节点全都可解；③一个或节点可解，只要其子节点至少有一个可解。

与或图基本概念一个节点是不可解，则节点须满足下列条件之一：①非终止节点的端节点是不可解节点；②一个与节点不可解，只要其子节点至少有一个不可解；③一个或节点不可解，当且仅当其子节点全都不可解与或图基本概念解图解 图 （ 树 ）是由可解节点形成的一个子图（ 树 ） ，这个个子图 （ 树 ） 的根是初始节点，叶为终止节点，且这个子图（ 树 ）还一定是与或图（ 树 ） 从初始节点到目标节点集的路径解图中叶节点集就是目标节点集解图中每一个非终止节点都有后继节点与或图基本概念与或图基本概念与或图应用例：事故树触电事故一般由人的不安全行为和物的不安全状态共同引发 人的不安全状态是指人接触带电体， 包括操作对象带电、触及相邻带电体三种情况物的不安全状态包括防护失效和接地不合格两种情况与或图的启发式算法与或图搜索与状态图搜索类似，也是不断地扩展节点，并配以返回指针，而形成一棵不断生长的搜索树与或图搜索也分为盲目搜索和启发式搜索两大类盲目搜索常用的方法也是深度优先和广度优先两种基本策略与或图的启发式搜索同样依赖于评价函数，其形式一般定义为 f(n)=g(n)+h(n)与或图的启发式搜索同样可以用open表 和 closed表实现，但 是 open表根据K连接符的耗散排序，closed表中多了一列 “ 可解性”判别与或图的启发式算法步 1 把初始节点S O 放 入 O P E N 表；步 2 移 出 OPEN表的耗散值最小的K 连接符对应的节点N放 入 CLOSED表 ，并冠以序号n;步 3 若节点N 可扩展，则做下列工作：⑴ 扩 展 N:将其子节点配上指向父节点的指针后放入OPEN表；⑵可解性判别：考察这些子节点中是否有终止节点。

若有，则标记它们为可解节点，并将它们放入CLOSED表 ，然后由它的可解返回推断其先辈节点的可解性，并对其中的可解节点进行标记如果初始节点SO也被标记为可解节点，则搜索成功，结束⑶ 删 去 OPEN表中具有可解先辈的节点（ 因为其先辈节点已经可解，故已无再考察该节点的必要） ，转 步2;与或图的启发式算法步 4 若 N 不可扩展，则做下列工作：（ 1） 不可解判别：标 记 N 为不可解节点，然后由它的不可解返回推断其先辈节点的可解性，并对其中的不可解节点进行标记如果初始节点SO也被标记为不可解节点，则搜索失败，退出⑵ 删 去 OPEN表中那些具有不可解先辈的节点（ 因为其先辈节点已不可解，故已无再考察这些节点的必要） ，转步2;与或图的启发式算法例: 初始节点为n O , 目标节点为n7, n8任意单步路径耗散恒定为1博弈与对抗搜索问 题 1 : 假如你正跟恋人用通，突然信号断了这时，你会立即拨过去，还是等你的恋人拨过来？问 题 2 : 两个饥饿的人从神仙那里得到了一根鱼竿和一篓鲜鱼 . . .如果是你，你会选择哪个，怎么行动？博弈与对抗搜索博弈(game): 研究类似于棋类、赌博、游戏的，具有斗争、竞争性质的决策行为对决双方( 各方) 的目标是往往冲突的各方在决策时都必须考虑对方的行动各方都以自身利益最大化为决策的准则可以分为合作博弈与非合作博弈两类博弈论(game theory)创始人：冯? 诺依曼博弈与对抗搜索博弈与对抗搜索你每天都在博弈学生阶段：跟同学博弈，跟老师博弈工作了：跟老板、同事博弈，面临优胜劣汰的残酷竞争谈恋爱：跟竞争对手博弈，跟恋人博弈结婚后：跟配偶博弈，跟孩子博弈任何时候：心理博弈，即自己和自己博弈博弈与对抗搜索经典的博弈模型囚徒困境两人因盗窃被捕，可以判他们犯盗窃物品的轻罪。

警方怀疑其有抢劫行为但未获得确凿证据，除非有一人供认或两人都供认囚徒被分离审查，不允许他们之间通信，交代政策如下：如果两人都供认，每个人都将因抢劫加盗窃被判2年监禁；如果两人都拒供，则两人都将因盗窃罪被判半年监禁；如果一人供认而另一个拒供，则供认这被认为有功而免受处罚，拒供者将因抢劫罪、盗窃罪以及拒供重判5年博弈与对抗搜索弱者的生存之道一智猪博弈有两头非常聪明的猪，一大一小，共同生活在一个猪圈里猪圈的一端有一个踏板，另一端有一个食槽踏板连着开放饲料的机关， 踏一下踏板， 食槽里就会出现10个单位食物任何一头猪去踏这个踏板都会付出相当于两个单位食物的成本每只猪都可以选择“ 踏”或 者 “ 不踏”踏板博弈与对抗搜索博弈与对抗搜索猪的选择两智猪一起踏踏板，再一起回槽边进食大猪：8 单位食物；小猪：2 单位食物；减掉踏踏板的2 个成本，大猪收益6 ,小猪收益0大猪踏踏板，小猪槽边守候大猪：6 单位食物，4 ; 小猪：4 单位食物，4小猪踏踏板，大猪槽边守候大猪：10单位食物，1 0 ; 小猪：0 单位食物，-2两猪都不去踏踏板，则都得不到食物，0博弈与对抗搜索博弈与对抗搜索弱者的生存之道一三人决斗A 、B 、C三人决斗，每人有2 颗子弹，每次发一枪。

A 、B 、C的命中概率分别为0.3、0.8、l.O o三人按A 、B 、C顺序依次发射，两轮后对决结束每次可以选择向对手发射，也可以放空枪射中即死问在这场博弈中A 的最优策略博弈与对抗搜索先考虑A 对手会采取什么行动C,命中率为1 , 可选射A 、射 B 、射空如果轮到C发射时只剩一个对手，则一枪解决对手;如果A 、B 都存活，C会选择射谁？博弈与对抗搜索A ,命中率0.3, 可选射B ,射 C,射空如果A 射 B如果A 射 C博弈与对抗搜索对空发射博弈与对抗搜索弱者的生存之道一珍珑棋局博弈与对抗搜索二人零和博弈人工智能的博弈一般指二人零和博弈两位游戏者参与完整信息轮流行动游戏者有输有赢，一方所赢正是另一方所输，而游戏的总成绩永远为零一个笑话：两个经济学家与XX博弈与对抗搜索博弈问题初始状态：当前系统状态（ 棋盘局面） 、轮到哪个游戏者行动后继函数: （ 行动， 状态） ， 一个规则允许的行动与该行动引起系统状态的变化终止测试：判断游戏是否结束收益函数：对系统状态的评价博弈与对抗搜索极大极小值算法搜索过程分为搜索树生成和格局值估计两部分先生成搜索树，然后用评价函数对每种局面进行评估，评价函数值越大，对 我 方 （ MA X ） 越有利，对 敌 方 （ MI N）越不利，反之亦然当 MA X 行棋时，将选择对我方最有利的步骤，也就是可选步骤中评价函数值极大的一步当 MI N行棋时，会选择对我方最不利的步骤，也就是可选步骤中评价函数值极小的一步最终找到对MA X 最有利的行棋步骤博弈与对抗搜索分钱币游戏（ Grundy博弈）规则：一堆钱币，两位选手甲方先将钱币分成数目不同的两小堆乙方再选其中一堆，将其分成数目不同的两小堆甲 方 接 着 分 依 此 类 推直到一方无法将钱币再分成不同的两小堆时认输博弈与对抗搜索7 个硬币的Grundy博弈博弈与对抗搜索三子棋的极大极小值过程规则：井字棋盘，两人对弈任意三子一线即为获胜评价函数, 对局面p:f(p)=e(+p)-e(-p)e(+p)是 p 上有可能使MA X 成三子为一线的数目e(-p)是 p 上有可能使MI N成三子为一线的数目博弈与对抗搜索具有对称性的棋盘可认为是同一局面。

博弈与对抗搜索极大极小值算法的特点优点先按照深度优先方法生成树，再标记评价，思路简单具有完备性缺点空间复杂度和时间复杂度巨大，不具备实用性以中国象棋为例，一盘棋平均走50步，总状态数约为10的161次方， 假设计算机1 毫微秒走一步， 约需10的 145次方年但该算法是博弈问题数学分析和其他算法的基础博弈与对抗搜索极大极小值算法的改进博弈与对抗搜索a- P剪枝对极大极小值算法的改进一边生成节点一边对节点评价，剪去一些没用的分枝一有限深度优先a:对 于 MA X 节点， a 是该节点生成的若干子节点的最大评价值 对于MI N节点， 6 是该节点生成的若干子节点的最小评价值博弈与对抗搜索a 剪枝若 M I N 节点n 的 0 值小于或等于它先辈节点的a 值 ， 则 n 以下的分枝可停止搜索，并令节点n 的倒推值为0 o6 剪枝若 MA X 节 点 n 的 a 值大于或等于它先辈节点的 值 ，则 n以下的分枝可停止搜索，并令节点n 的倒推值为a 博弈与对抗搜索问题1 : 该剪枝是a 剪枝还是剪枝？问题2 : 该剪枝为有限深度优先算法，深度是多少？博弈与对抗搜索例：P75 2.14要求： a 剪枝用\ \ , 0 剪枝用X 在图上标出步骤：1、先标出MA X ( a ) 节点和M I N ( 0 )节点2、从最左边的一枝开始，倒推其先辈节点的a 、 6 值3、按照从左到右的顺序，依次对相邻枝，按照a 6 剪枝条件进行剪枝本章重点与或图的基本概念、解图、可解节点与不可解节点简单问题的与或图表示极大极小值算法的基本思想a 剪枝、 6 剪枝人工智能第二章搜索问题本章的内容与目标搜索与搜索问题搜索问题的求解步骤无信息( 盲目) 搜索有 信 息 ( 启发式)搜索搜索与搜索问题人类的实际搜索行为人工智能所要解决的问题大部分不具备明确的解题步骤，而只能是利用已有的知识一步一步地摸索前进。

根据问题的实际情况不断寻找可利用的知识， 从而构造一条代价较少的推理路线， 使问题得到圆满解决的过程称之为搜索 搜索方法的经典应用8数码问题传教士和野人问题旅行商问题4皇后问题迷宫问题博弈问题搜索方法的一般步骤1、定义状态描述形式2、定义算符一是把问题从一种状态变换到另一种状态的方法代号，即状态演变规则3、确定初始状态（ 初始节点）和目标状态（ 目标节点）4、状态更新一一根据算符更新当前状态5、 目标测试——判断更新后的状态是否为目标状态，若不是则转到4 ,否则转到66、搜索成功, 记录搜索路径用 open表 和 closed表保存搜索经过的各个节点open表 和 closed表的一般结构无信息搜索又称盲目搜索/ 穷举式搜索， 只能按照预先规定的搜索控制策略进行搜索，没有任何中间信息来改变这些控制策略具有盲目性，效率不高，不便于复杂问题的求解常用方法有广度优先搜索和深度优先搜索以及这两种搜索方法的改良方法宽度优先搜索最简便的图的搜索算法之一，属于一种盲目搜寻法目的是系统地展开并检查图中的所有节点，以找寻结果基本思想是首先搜索和初始节点距离为1 的所有顶点，然后再去搜索和出始节点距离为2 的其他顶点，依次类推它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。

宽度优先搜索广度优先搜索算法：步 1 把初始节点S O 放 入 O P E N 表中步 2 若 O P E N 表为空，则搜索失败, 退出步 3 取 OP E N表中前面第一个节点N放 在 C L O S E D 表中,并冠以顺序编号no步 4 若目标节点S g=N , 则搜索成功， 结束步 5 若 N不可扩展，则转步2O步 6 扩 展 N , 将其所有子节点配上指向N 的指针依次放入O P E N 表尾部， 转 步2宽度优先搜索例： 8 数码问题九宫格中有8 个数码，其中只有一个空格规则是一次只能把一个数码移动到空的格子中要求从一个初始状态移动到一个目标状态宽度优先搜索宽度优先搜索优点完备性：如果问题有解，广度优先搜索总能够在有限步内找到目标节点最优性：在不考虑路径耗散的前提下，广度优先搜索总能够找到最浅的目标节点缺点：遍历各个节点，搜索效率差，消耗大量内存和时间宽度优先搜索的拓展一代价树宽度搜索代价树宽度搜索( 代价一致搜索) 对于任意单步路径耗散都是最优的搜索策略其基本思想是优先扩展路径耗散最小的节点对于任意节点n ,用 f(n)来表示n 到初始节点的路径耗散，即代价代价树宽度搜索例： 旅行商问题设 A 、B 、C、D、E 五个城市，旅行者从A 出发，到达城市E ,旅行费用如图所示，走怎样的路线费用最小？要求画出代价树、O P E N 表 和 C L O S E D 表深度优先搜索深度优先搜索总是先扩展搜索树的当前边缘中最深的节点一种最原始的仿生学算法，来源于爬虫在树枝的搜索过程深度优先搜索深度优先搜索算法：步 1 把初始节点S O 放 入 O P E N 表中。

步 2 若 O P E N 表为空，则搜索失败，退出步 3 取 OP E N表中前面第一个节点N放 入 C L O S E D 表中,并冠以顺序编号no步 4 若目标节点S g=N , 则搜索成功, 结束步 5 若 N不可扩展，则转步2O步6 扩展N , 将其所有子节点配上指向N的返回指针依次放入 O P E N 表的首部， 转步2深度优先搜索例：传教士和野人问题有 3 个传教士和3 个野人过河只有一条能装下两个人的船在河的任何一方或者船上，如果野人的人数大于传教士的人数，那么传教士就会有危险.要求安全渡河深度优先搜索分析：由于传教士与野人的总数目是一常数， 所以只要表示出河的某一岸上的情况就可以了另外还需要表示出船的位置因此用一个三元组(M , C , B), 来表示系统状态M 表示河左岸传教士的人数C表示河左岸野人的人数B 表示船的位置，1 表示船在左岸，0 表示船在右岸于是，初始状态为目标状态为深度优先搜索深度优先搜索优点：对内存需求比较少，如果一个节点的全部后代都被完全探索过，那么这个节点和它的全部后继都可以从内存(open表和closed表) 中删掉了缺点：不完备，也不最优回溯搜索策略回溯策略属于深度优先搜索的一种变形与深度优先搜索的区别：扩展一个节点时，每次只产生一个后继节点，而不是全部后继回溯策略只保存单一的解路径，占用内存空间很少，只需要一张表即可完成搜索回溯搜索策略例：四皇后问题在 4 x 4 方格的棋盘内，放置四个皇后使任意两个皇后不在同一行、同一列、同一对角线( 斜线)上要求：找出所有的摆法回溯搜索策略状态描述：单个皇后位置的描述：用(ij)表示皇后在第i行j列系统状态的描述四个皇后((iljl), (i2,j2), (i3J3), (i4,j4))深度优先搜索的拓展一一深度有限搜索深度有限搜索预先设定一个搜索深度1 ,用以解决搜索树无边界的问题搜索过程中认为深度为1的节点没有后继节点，必须回溯缺点：增加了算法的不完备性双向搜索双向搜索同时进行两个搜索，可以采用任意搜索方法一个从初始状态向前搜索另一个从目标状态向后搜索当两个搜索在某个节点相遇时，搜索成功无信息搜索的讨论算法评判完备性一一是否一定能找到目标节点最优性一一搜索得到的解是否最优解时间复杂度一一算法的时间需求空间复杂度一一算法对计算机内存的需求无信息搜索的讨论重复状态扩展一个节点时，新生成的节点已经在open表 或 者 closed表中存在了，这种情况称为重复状态有些情况下，重复状态会导致搜索失败；有些情况下，重复状态可以保留，但是会带来额外的计算资源的消耗因此，一般期望尽可能避免重复状态这时，有可能出现节点指针重新定向的情况无信息搜索的讨论问题的形式化描述状态描述一一用数学方法定义系统状态初始状态、目标状态行动规则一一产生后继节点目标测试一一判断当前节点是否就是目标节点路径耗散一一为每一条搜索路径定义数值化的消耗值无信息搜索的讨论状态描述八数码问题3 X 3 的二维数组行动规则假 设 r[i][j]=O , 则它跟相邻元素可以互换无信息搜索的讨论状态描述4 皇后问题状态：在棋盘上任意放置1・ 4个皇后，每一种放置都是一个状态状态描述：逐一给出各个皇后的放置位置行动规则：增加一个皇后到棋盘上的任何空格无信息搜索的讨论状态描述四色问题，又称四色猜想，世界近代三大数学难题之一要求：只用四种颜色对平面地图染色，要求每两个相同区域不能染成相同颜色1976年美国数学家阿佩尔（ K .Appel）与 哈 肯 （ W.Haken ）宣告借助电子计算机获得了四色定理的证明，又为用计算机证明数学定理开拓了前景无信息搜索的讨论四色问题的状态描述若干地区，四种颜色状态：对任意地区的进行染色，任意染色结果都是一种状态状态描述：用 s[k]表示第k 个地区的染色，逐一列出所有地区的染色就是系统的状态描述行动规则：给一个没有染色的地区染色无信息搜索的讨论吸尘器的世界只有两个房间A 和 B每个房间有可能有灰尘也可能没有吸尘器可以在两个房间里移动如果有灰尘，则吸取；否则移动到另一个房间无信息搜索的讨论课堂练习自动抓药系统三个勺子，容量分别为8 克、5 克 和 2 克可以从药箱把勺子装满或倒空， 也可以从一个勺子倒进另一个勺子目标是从药箱抓1 克药给出状态描述、初始状态、目标状态以及行动规则启发式搜索启发式搜索，也称为有信息搜索，借助问题的特定知识来帮助选择搜索方向在搜索过程中对待扩展的每一个节点进行评估， 得到最好的位置，再从这个位置进行搜索直到目标。

启发式搜索的目的是省略大量无谓的搜索路径，提到效率在启发式搜索中，对节点的评价是十分重要的，评价函数是搜索成败的关键启发式搜索评价函数，也称为启发函数提供问题的启发性信息，按其用途划分，可分为以下三类：用于扩展节点的选择，即用于决定应先扩展哪一个节点，以免盲目扩展用于生成节点的选择，即用于决定应生成哪些后续节点，以免盲目地生成过多无用节点用于删除节点的选择，即用于决定应删除哪些无用节点，以免造成进一步的时空浪费启发式搜索一个节点n的评价函数的构造通常由两部分构成从初始节点到当前节点n的路径耗散从当前节点n到目标节点的期望耗散即：评价函数可表示为：这两部分里， 通常是比较明确的，容易得到而 难以构造，也没有固定的模式，需要根据具体问题分析启发式搜索贪婪搜索优先扩展距离目标最近的节点例：西安到上海的贪婪搜索启发式搜索贪婪搜索的启发函数只考虑待扩展节点到目标节点的期望耗散，而不考虑初始节点到待扩展节点的实际耗散贪婪搜索类似于深度优先搜索，总是先沿着一条枝搜索下去贪婪搜索既不是完备的，也不是最优的启发式搜索A 算法代价树宽度搜索只考虑初始节点到待扩展节点的路径耗散贪婪搜索只考虑待扩展节点到目标节点的期望耗散A 算法既考虑待扩展节点到目标节点的期望耗散，又考虑初始节点到待扩展节点的路径耗散启发式搜索A 搜索算法的步骤步 1 把初始节点S o放 入 O P E N 表。

步 2 若 OPEN表为空，则搜索失败， 退出步 3 移出OPEN表中第一个节点N 放 入 CLOSED表中，并冠以顺序编号no步 4 若目标节点Sg=N ,则搜索成功，结束步 5 若 N 不可扩展，则转步2O步 6 扩 展 N,生成一组子节点, 并利用评价函数为子节点估值 ，对这组子节点做如下处理：(1 )处理重复状态⑵对其余子节点配上指向N 的返回指针后放入OPEN表中,并 对 OPEN表 按 f(n)值以升序排序， 转 步2启发式搜索A 算法举例八数码问题确定用节点深度，也就是初始节点到待扩展节点移动的数码的步数确定不在位数码的总数启发式搜索A 算法的表现极大地依赖于评价函数， 特别是h(n),即： 从节点 n 到目标节点最佳路径的估计耗散假 定 h*(n)表示节点n 到目标节点最佳路径的实际耗散如 果 h(n)> h*(n), 搜索的节点数少，搜索范围小，效率高,但不能保证得到最优解如 果 h(n)v= h*(n), 这种情况下，搜索的节点数多，搜索范围大，效率低，但能得到最优解启发式搜索满足h(n)<= h*(n)条件的A 搜索，称为A* (A・ star)搜索A * 搜索中，h(n)越接近h*(n), 搜索效率越高宽度优先算法可以看作A*算法的特例，即：g(n)是节点所在的层数，h(n)=O代价树宽度搜索也可以看作A*算法的特例，即：g(n)是节点n 的实际路径耗散，h(n)=O跟前两个算法一样，A*算法也具有完备性和最优性启发式搜索例：八数码问题启发函数1: hl(n)=不在位的数码的总数问题1 : 图中SO状 态 h(SO)是什么， h*(SO)又是什么问题2 : 这个启发函数是否一定满足h(n)v=h*(n)问题3 : 对于八数码问题，还能提出其他的启发函数吗？启发式搜索例：八数码问题启发函数2: h2(n)=所有数码到目标位置的距离和( 曼哈顿距 离 )问题1 : 图中SO状 态 h(SO)是什么， h*(SO)又是什么问题2 : 这个启发函数是否一定满足h(n)v= h*(n)启发式搜索A*算法当 h(n)<= h*(n)时，同时满足完备性和最优性要求h(n)越接近于真实耗散h*(n),算法的搜索效率越高， 对内存和时间的需求越小如果满足h(n)= h *(n ),是最完美的A*算法h(n)的设计是A*算法的核心，也是最困难的地方启发式搜索启发式函数的构造思想之一松弛法放松行动规则约束的思想方法八数码问题：行动规则：如果以下条件成立，则一个数码可以从A方格移动到B 方格1、 B 为空2、 A 与 B 相邻放松约束1: A 可以移动到B放松约束2 : 如果A 与 B 相邻，则 A 可以移动到B放松约束3 : 如 果 B 为空，则 A 可以移动到B启发式搜索启发式搜索与最优化问题求解现实问题时往往不能明确的知道解的形式，而是只有一堆约束条件，满足约束条件的状态就是一个合法的解满足约束条件的解可能有很多个， 人们希望找出使某个目标最满意的解，称为最优解这样的问题称为最优化问题目标条件就是搜索中的评价函数启发式搜索最优化问题目标条件（ 评价函数）约束条件表示在所有满足约束条件的解中取目标条件最小的为最优解启发式搜索- 爬山法爬山法模拟人们出游爬山的决策过程以目标值增加的方向为搜索方向如果有多个增加的方向，选使目标值增加速度最快的方向爬山法会在某个峰顶终止，其相邻状态中没有更高的目标值了，称为局部极大值启发式搜索•爬山法爬山法的基本步骤1、初始化，确定初始节点等参数2、检查当前节点是否满足目标条件，如果满足，则搜索成功，结束3、取邻域中每一个相邻节点，计算其目标函数的改进值4、取改进值最大的相邻节点作为搜索目标，替换当前节点5、检查是否满足循环终止条件。

如果满足，则中止循环，否则转步2启发式搜索- 爬山法爬山法的缺陷难以处理山肩的情况贪婪搜索方向不一定是正确的搜索方向启发式搜索•爬山法爬山法的改进随机爬山法：在上山移动中随机的选择下一步可回溯爬山法：给定启发式的回溯策略，允许回头搜索其他节点洪水爬山法：不断寻找改进方向允许水平移动可回溯启发式搜索- 模拟退火算法模拟退火算法(simulated annealing )爬山法是不完备的，有可能停留在局部最优解上随机行走( 遍历)是完备的，但是搜索效率很差模拟退火算法将爬山法与随机行走结合起来，希望同时得到效率和完备性启发式搜索- 模拟退火算法模拟退火过程思想来源于固体退火原理，属于热力学范畴将固体加温至充分高，再让其缓慢冷却加温时，固体内部的粒子随温升脱离原先的平衡态，变为无序状缓慢冷却时，粒子活性逐渐下降，逐渐停留在不同状态，重新形成粒子的排列结构如果降温过程足够缓慢，粒子的排列就会达到一种平衡态，使系统能量最小启发式搜索■模拟退火算法启发式搜索- 模拟退火算法模拟退火的基本步骤：(1 )初始化：初始温度T( 充分大) ，初始状态S ,迭代次数L⑵ 对k = l,……, L重复第⑶至第6步：(3 )产生新解(4 )计 算 增 量=C(S, )-C(S),其 中C(S)为评价函数(5 )若<0则接受9作为新的当前解， 否则以概率exp(・△r /T)接 受 + 作 为 新 的 当 前 解(6 )如果满足终止条件则输出当前解作为最优解，结束程序。

终止条件通常取为连续若干个新解都没有被接受时终止算法7) T逐渐减少，且T > 0 ,然后转第2步启发式搜索•模拟退火算法冷却进度表：是指调整模拟退火法的一系列重要参数，它控制温度参数T的初值及其衰减函数冷却进度表的内容：控制参数T的初值；控制参数T的衰减函数；每一个温度下的迭代次数L ,即每一次随机游走过程，要迭代多少次，才能趋于一个准平衡分布结束条件启发式搜索■■模拟退火算法Metropolis 准则：假 设 在 状 态xold时，系统受到某种扰动而使其状态变为xnewo与此相对应，系统的能量也从E(xold)变成E(xnew)系统由状态xold变为状态xnew的接受概率p为：若At，vO则接受早 作为新的当前解S,否则以概率expGAt，/T)接 受 + 作为新的当前解S启发式搜索- 模拟退火算法模拟退火算法的关键点初始温度必须足够高在每一个温度下，状态的转换必须足够充分温度T的下降必须足够缓慢启发式搜索■■模拟退火算法模拟退火算法的优缺点优点:计算过程简单，通用，鲁棒性强适用于并行处理，可用于求解复杂的非线性优化问题缺点：如果降温过程足够缓慢，多得到的解的性能会比较好，但与此相对的是收敛速度太慢；如果降温过程过快，很可能得不到全局最优解启发式搜索- 遗传算法遗传算法(genetic algorithm, GA)模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型是一种通过模拟自然进化过程的随机优化搜索方法美国M ichigan大学J.Holland教授于1975年首先提出来的启发式搜索•遗传算法启发式搜索- 遗传算法遗传算法的基本思想遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象在每次迭代中，根据适应度评估群体中的所有成员，然后选取适应度最高的个体产生新一代群体在被选中的个体中，一部分保持原样地进入下一代群体；另一部分利用遗传算子（ 选择、交叉和变异） 对这些个体进行组合，产生新一代的候选解群重复此过程，直到满足某种收敛指标为止。

启发式搜索- 遗传算法编码编码就是模拟染色体的结构，染色体是由基因排成的串通过某种编码机制把对象抽象为由特定符号按一定顺序排成的串，常用由0, 1组成的字串常用随机方法生成若干个个体的集合，该集合称为初始种群初始种群中个体的数量称为种群规模启发式搜索- 遗传算法例： 将［ 0, 1］之间的数编码， 精确到小数点以后两位， 即0.01,0.02, 0.03 … 0.991、确定编码长度：根据取值空间，可知有99种编码结果，而 ，因此01编码的长度为7位2、编码：乘 以1 0 0 ,然后转化为7位二进制0.01 T 0000001 0.02 T 00000100.03-*00000110.99 -> 11000113、解码启发式搜索- 遗传算法启发式搜索•遗传算法适应度函数即评价函数，用来描述一个个体的好坏遗传算法中，适应度函数值越大，解的质量越好适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的唯一标准它的设计应结合求解问题本身的要求而定启发式搜索- 遗传算法遗传算子选择算子交叉算子变异算子启发式搜索- 遗传算法选择算子使用选择运算来实现对群体中的个体进行优胜劣汰操作适应度高的个体被遗传到下一代群体中的概率大；适应度低的个体被遗传到下一代群体中的概率小选择操作的任务就是按某种方法从父代群体中选取一些个体 ，遗传到下一代群体启发式搜索- 遗传算法轮盘赌选择算子轮盘赌选择又称比例选择算子其基本思想是：各个个体被选中的概率与其适应度函数值大小成正比启发式搜索- 遗传算法交叉算子交叉运算是指对两个相互配对的染色体按某种方式相互交换其部分基因，从而形成两个新的个体交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起关键作用，是产生新个体的主要方法。

启发式搜索- 遗传算法交叉前：0 .7 4 与 0.29交叉后：0.77与 0.26启发式搜索- 遗传算法变异算子是指个体编码串中的某些基因值用其它基因值来替换， 从而形成一个新的个体遗传算法中的变异运算是产生新个体的辅助方法，它决定了遗传算法的局部搜索能力，同时保持种群的多样性交叉运算和变异运算的相互配合， 共同完成对搜索空间的全局搜索和局部搜索启发式搜索- 遗传算法变异前：0.77变异后：0.73启发式搜索•遗传算法运行参数种群规模终止进化参数交叉概率交叉条件变异概率变异条件启发式搜索- 遗传算法遗传算法的特点遗传算法是一种成功的自适应方法，具有很好的健壮性，易于并处理遗传算法长于全局搜索，它不受搜索空间的限制性假设的约束，能以很大的概率从离散的、多极值的、 含有噪声的复杂问题中找到全局最优解遗传欺骗：在遗传算法进化过程中，有时会产生一些超常的个体，因竞争力太突出而控制了选择运算过程，从而影响算法的全局优化性能，导致算法获得某个局部最优解启发式搜索高级搜索算法的应用机器学习自动控制规划设计调度配置组合优化图像和信号处理本章重点启发式搜索的基本思想、原理和方法利用open表 和 closed表解决搜索问题人工智能第三章谓词逻辑与归结原理概述语言自然语言：人们在日常生活中所使用的语言文字半形式化语言： 自然语言加特定的符号，如数学语言（ 定义、定理等）形式化语言：用精确的数学或机器可处理的公式定义的语言 。

逻辑学语言，弗雷格Frege , 1879）（ p q ） A （ p->r） A 〜 pA ~ r— 〜 p怪物洞穴人工智能的经典实验环境一怪物洞穴（ wumpus世界）洞穴有多个房间组成某个房间中藏着一只怪物wumpus,它会吃掉进入这个房间的人，相邻房间中能够感觉到臭味某些房间中有陷阱，进入房间会被陷阱吞噬，相邻房间中能够感觉到微风游戏的主角是一个智能体，可以进入相邻的房间（ 对角线不可以）智能体有且仅有一支箭，用这支箭可以射杀怪物某个房间中有金子，游戏的目标是智能体找到金子怪物洞穴智能体行动的关键是要根据获得的信息推理，从而判断那个房间有怪物，那个房间有陷阱，那个房间是安全的房间［ 4,2］和［ 2,3］有陷阱，房间［ 3,4］有怪物，房间［ 4,3］有金子3.1命题逻辑3.1命题逻辑命题一能够判断真假的陈述句陈述句真值唯一， 可用二进制表示用小写字母进行标识例1、北京是中国的首都2、长安大学位于钟楼附近3、 1+1=24、计算机系的学生必修C或 JAVA5、坐着花生过黄河5、 x+l=26、吃饭了吗?7、南无阿弥陀佛8、我正在说假话3.1 命题逻辑简单命题与复合命题简单命题：（ 原子命题）一个命题无法分解为更简单的子命题复合命题：由简单命题用联结词联结而成的命题1、由若干简单命题组成；2 : 由联结词联结例：1、北京是中国的首都。

2、长安大学位于钟楼附近3、计算机系的学生必修C或 JAVA4、这家的报价单配置合理并且价格低廉5、“ 李四是犯罪嫌疑人” “ 李四有犯罪动机”3.1命题逻辑合式公式：单个常量或者变量的命题构成合式公式联结词联结的合式公式的组合也是合式公式合式公式的有限次组合称为命题公式命题公式：有限次合式公式组合的形式化描述，本书中以大写字母标识3.1命题逻辑基本联结（ 连接） 符号~非 ，否定， 一 《A与，合取，A ND的首字母V或，析取，vel― 蕴含式 A: a ~*b表示，如 果a 为真，则 b 为真等价联结符号的优先级AV— >9*3.1命题逻辑将命题从语言表述转换为命题公式step l,找出简单命题，并用符号表示step2、分析简单命题间的逻辑关系，用联结符号进行描述例3.1命题逻辑例：怪物洞穴如果房间［ 1,1］中有臭味，则房间［ 1,2］或［ 2,1］中有怪物表示房间［ ij］中有臭味表示房间［ i,j］中有怪物3.1命题逻辑练习：扫雷游戏设Xi,j表示方格罔］ 中有一个地雷写出方格［ 1,1］周围恰好有2颗地雷的命题公式3.1命题逻辑命题公式的赋值对命题公式中的所有的命题变量各赋给一个值0, L真值表3 .1 命题逻辑复合命题的真值例：p : 周杰伦是一个流行歌手q : 人工智能是计算机科学的一个分支r : 牛在天上飞求下列复合命题的真值3 .1 命题逻辑命题公式的分类重言式或永真式tautology ,设 A 为任一命题公式，若 A 在它的各种赋值下取值均为真,则称A 是重言式例：PV~P矛盾式或永假式contradictory设 A 为任一命题公式，若 A 在它的各种赋值下取值均为假,则称A 是永假式。

例： PA 〜 P3 .1 命题逻辑可 满足 式 satisfiable设 A 为任一命题公式，如果存在一组取值使A 为真，则 A为可满足式即：对于命题公式A , 若 A 不是矛盾式，则 称 A 是可满足式例：PAQ非重言式的可满足式既是可满足式，又不是重言式3.1 命题逻辑等值逻辑运算< = > 逻辑等值，等号连接的命题公式等价，三基 本 等 值 算 式 P80交换率： A A B<=>B A A； A VB<=>B V A ;结合率：(A A B) A C<=>A A(B A C ) ;(A VB) V C<=>A V (B V C )；* 分配率： A V (B A C) <=> (A V B) A(A V C );A A(B V C) <=> (A A B) V(A AC )；双重否定律：~~Av=>A ;等赛率： A <=> A A A ; A <=> A V A ;* 摩根律：〜(A V B)v=>〜A A〜B;~(A A B)v=>~A V ~B;3 .1 命题逻辑吸收率：A V(A A B)<=>A;A A (A VB)<=>A ;同一率：A V 0 <=> A; A A 1 <=> A;零率： A V1<=>1; A A 0 <=> 0;排中律：A V -A<=>1矛盾律：A A - A <=> 0* 蕴含等值式：AfBv=>~A V B ;* 等价等值式：A?B<=> (A^B) A(B - A )；假言易位式：A - Bv=>~B - ~A ;等价否定等值式：A ? B<=> ~ A ?〜B;归谬论：(A - B) A (A - ~B)v=>~A ;3.1 命题逻辑合取范式与析取范式简单析取式：有限个命题变元或其否定，析取联结符pVq; ~p Vq ; p ; q合取范式：有限个简单析取式，合取pA(pVq) A(〜p Vq)简单合取式：有限个命题变元或其否定，合取P A q; ~p A q ; p ; q析取范式：有限个简单合取式，析取p v(p A q) V(~p A q)3.1命题逻辑任意命题公式都存在等值的析取范式和合取范式求取合取范式的步骤1、利用蕴含等值式和等价等值式消去命题公式中除卜，V,A｝以外的联结词2、利用摩根律、双重否定律等进行置换，将~ 移到括号里面3、 利用分配律得到合取范式3.1 命题逻辑例P82 计算(p A ( q -*r)) -> s的合取范式(p A (q ->r)) ->s<=> (p A (~ q Vr) ) -*s ; 蕴含等值式<=> ~ (p A (〜q V r)) V s ; 蕴含等值式<=> ~ p V~(~q Vr) V s ; 摩根律< => ~ p V (~ ~ q A ~r) V s; 摩 才 艮 律< = >〜p V( q A -r) V s; 双重否定律< =>(~ p V s ) V ( q A -r); 交换律< => (~p V s V q ) A (- p V s V ~r);分配律3.1命题逻辑例 P82计 算 ((p Vq) -►r) - p 的合取范式((P Vq) -r) -p<=> (~(p Vq) V r) -*p<=> ~ (〜(p V q) V r) V p<=> (~~(p V q) A ~r)V p<=> ( (p V q) A ~r)V p<=> ( p VqV p) A (~r V p )<=> ( p V q) A (~r V p )3.1命题逻辑课堂练习计算合取范式(p->q) A~(~q 一~；蕴含等值式； 蕴含等值式摩根律； 双重否定律分配律；等森律(~p V q) A ~ q A p3.1命题逻辑命题逻辑推理逻辑结论：如果A - B 为重言式，则称B 是 A 的逻辑结论,记 作 A=>BO常用推理定律：附加： A=> (A VB)简化： (A A B) =>A假言推理： ((A - B) A A)=>B拒取式： ((A - B ) 八〜B)=>~A析取三段论：((A V B) A〜A)=>B假言三段论：((A -> B) A (B ->C))=>(A -> C)等价三段论：((A B) A (B C )) => (A C)构造型二难：(A - B) A (C -D ) A ( A V C ) => (BV D)3 .1 命题逻辑命题逻辑推理规则前提引入规则任何证明的步骤上，都可以引入前提；结论引入规则任何证明的步骤上，所得到的结论都可以作为后续证明的前提；置换规则任何证明的步骤上，命题公式中任何子命题都可以用与之等值的命题公式置换；3 .1 命题逻辑例：P84如果今天下雨， 则要带雨伞或雨衣。

如果走路上班；则不带雨衣今天下雨，走路上班，证明要带伞解：p :今天下雨；q :带雨伞；r :带雨衣；s :走路上班前提：p — (qV r)； s —~r; p; s 求证：q证明：1 、 p (q V r) , p前提引入：2、((p - (q V r) ) A p) => q V r假言推理：3 s — ~ r , s前提引入：4 、 ((s ~ r) A s) => ~r假言推理：5 、 ((q V r ) A ~r ) => q析取三段论：3.1命题逻辑例怪物洞穴表示房间［ ij］中有臭味表示房间［ 耳］ 中有怪物表示房间［ i田中有微风表示房间［ ij］ 中有陷阱3.1命题逻辑初始状态，在房间［ 1, 1］ 处没有感觉到微风，也没有臭味，则相邻房间为安全的，既没有怪物也没有陷阱前提：结论：证明：前提引入等价等值式简化前提引入拒 式摩根律3.1命题逻辑归结原理证明的一般方法由已知条件正向推导结论，演绎推理假定结论不成立，逆向推导与已知条件矛盾，反证法命题逻辑证明的归谬思想P85归结原理的思想：如果证明A A ~ B 为永假式，则得证3.1命题逻辑归结方法的思想1、将待证明问题转化为其逆否命题例：条 件 A ,求证B . 即 A - B其逆否命题为：A A ~ B2、求合取范式，得到子句集构成合取范式的有限个简单析取式构成的集合就是子句集3、对子句集进行归结，得到空子句3.1命题逻辑将待证明问题转化为其逆否命题证明问题的一般形式：已知：A 成立求证：B 成立即：证 明 A-*BA — B <=> ~A V B蕴含等值式<=> ~(A A ~B)摩根率A A ~B 即为原命题的逆否命题3 .1 命题逻辑例：证 明 G 是 F 的逻辑结论Fl: P -WF2: ~WG: ~P分析：已知条件为：(P-W ) (~W)结论为：~p贝 h逆否命题为：(P-*W) A(~W)3 .1 命题逻辑子句与子句集P86对问题的逆否命题，求其合取范式对于一个合取范式，该范式中的每一条简单析取式都是一个子句。

子句集：合取范式下的所有子句构成其子句集例：p A (p V q) A (~p V q)子句集为{p, pVq, ~p Vq}3.1命题逻辑归结方法如 果pV q与 ~q V r都为真，贝Ip V r为真证 明1真值表3.1命题逻辑归结式例 {pVq, ~p V q }归结后为：{q}归结的目标一空子句对于一个合取范式，如果有一个子句不可满足，则子句集就不可满足，该合取范式为永假式若一个子句集中包含空子句，则这个子句集一定是不可满足的例：{p, ~p}归结后为{ □}3.1命题逻辑归结法步骤建立待归结命题公式 将证明A-*B为真转化为证明AA~B为矛盾式求合取范式，得到子句集对子句集进行归结归结式作为新子句加入子句集进行归结当归结式为空子句口时停止，证明结束出现空子句口，表示该子句集不可满足归结法的完备性：如果A -B成立，则利用归结法一定可以得到证明3 .1 命题逻辑例：证明(p - q) ->(~q -~ p )证明：要证明原命题为真，只需证明(p -q ) A~ (~q — ~ p)为恒假(p-q) A~ (〜 q -*~p)<=> (~p V q) A ~ (q V ~ p) 蕴含等值式<=> (-p V q) A ~ q A p摩根律于是，子句集为：1 ~ pVq3P{~pVq, ~q, p}4 〜p 1、2归结5 □ 3、4归结由此可得： (p - q) A~(~q —~p)为恒假，原命题为真3.1命题逻辑例：怪兽洞穴1、在房间［ 1,1］处没有感觉到微风，也没有臭味。

2、在房间［ 1,2］处感觉到微风，但没有感觉到臭味3、在房间［ 1,2］处没有感觉到微风，但感觉到臭味求证：房间［ 3,1］处有怪物* ; 房间［ 1,3］处有洞穴；房间［ 2,2］是安全的3.1命题逻辑前提：求证：证明：要证明原命题为真，只需证明以下命题为恒假3.1命题逻辑于是，得到子句集为：3 .1 命题逻辑3 .1 命题逻辑思考：归结算法的计算机实现？{SO,S1,S2,S3... }终止条件：1、生成了空子句，证明结束2、循环结束，没有可以添加的新语句，待证明的定理不成立3 .1 命题逻辑好的归结控制策略初始状态优先选择包含结论的子句进行归结，之后每次都选择上一次归结得到的归结式与其他子句归结容易犯的错误字句集1、PVQ2、~PV~Q3 、 口 1 、 2归结3 .1 命题逻辑归结方法是一种机械化的， 可在计算机上加以实现的推理方法归结方法是一种反向推理形式提供了一种自动定理证明的方法归结的半完备性当定理可以证明时，归结方法是完备的当定理不可证明时，归结方法得不到任何结论，算法不一定会停止3.2谓词逻辑3.2谓词逻辑3.2.1基本概念命题逻辑描述简单的陈述性命题， 但表示量化和谓词过于繁琐，也难以表示个体间的关系3.2谓词逻辑3.2.1 基本概念谓词逻辑C lass(x)表 示 x 在上人工智能课x=张三, 就得到了 si;x=李四, 就得到了 s2;x二 王五，就得到了 S 3;C lass(x, y)表 示 x 在 上 y 课x二 张三， y=人工智能，表示张三在上人工智能课x二 李四， y= 线性代数，表示李四在上线性代数课X二 王五， y=睡觉，表示王五在上睡觉课3.2谓词逻辑3.2.1 基本概念命题是一个陈述句，它一般可分成主语和谓语两部分。

有时还需要用到量词主语：指独立存在的客体，可以是具体事物或抽象概念，也称为个体谓词：描述个体词性质或个体之间关系的词个体域：表示个体变量的取值范围，常用D表示常量：表示具体性质或关系的个体或者谓词变量：表示抽象或泛指的个体或者谓词量词：表示数量的词任意量词？ ：表 示 “ 任意” ，“ 所有” ，也称为全称量词存在量词？ ：表 示 “ 存在”3.2谓词逻辑3.2.1 基本概念例：“ 关羽是人” ，“ 张飞是人”这是两个不同的命题，其主语( 个体) 不同但是谓词是相同的，“ 是人”把谓语部分抽出来，假 设 Human(x)表 示 x 是人这两个命题都可以用这个谓词来描述Human(guanyu)Human(zhangfei)其中x 属于个体变量，guanyu和 zhangfei属于个体常量3 .2 谓词逻辑3.2.1 基本概念例：1、所有的人都是要死的2、有的人能够活到100岁P(x)表 示 x 是要死的， Q(x)表 示 x 活 到 100岁个体域D 为人类集合个体域D 为总个体域集合引入特殊谓词R(x)表 示 x 是人3 .2 谓词逻辑语言描述转换为谓词公式1、确定并说明谓词2、确定个体和个体域3、确定量词4、判断谓词间的逻辑关系3 .2 谓词逻辑例：我是计算机系的学生1、确定并说明谓词：方法一：Student(x,y)表 示 X 是 Y 系的学生2、个体域：X : 学生的集合，y : 系的集合Student(I,computer)方法二：Computer(x)表 示 X 是计算机系的学生Computer(I)注意：必须对谓词进行说明P(I,computer)3 .2 谓词逻辑1、定义并说明谓词Unlike(x,y)表示x 不喜欢y 课2、个体域x 学生的集合，y 课程的集合3、量词存在3 .2 谓词逻辑例：任何人的兄弟都是男性确定并说明谓词Brother(x,y)表 示 x 是 y 的兄弟Male(x)表 示 x 是男性个体域Brother(x,y) x、y : 人的集合Male(x) x : 人的集合量词任意确定逻辑关系与？或？非？蕴含？等价？3 .2 谓词逻辑例：不管黑猫白猫，抓住老鼠就是好猫定义并说明谓词Cat(x,y)表示是x 是 y 颜色的猫Goodcat(x)表 示 x 是好猫Catch(x,Mouse)表 示 x 能抓住老鼠个体域x : 猫的集合，y : 颜色的集合谓词间的关系Cat(x,y)与 Catch(x,Mouse)蕴含 Goodcat(x)量词：任意3 .2 谓词逻辑3.2.1 基本概念量词使用中的注意事项不同的个体域中，命题符号化的形式可能不同没有给定个体域的情况下，应考虑全总个体域如果个体域为有限集 ，对任意谓词P(x)有：多个量词同时出现时，不能颠倒其先后顺利，否则会改变公式的含义。

3 .2 谓词逻辑3.2.1 基本概念例：love(x,y)表 示 x 喜 爱 y表 示 对 任 意 的 X ,都 存 在 喜 爱 的 对 象 y ,即“ 每 一 个 人都 会 喜 爱 某 人 ”表 示 存 在 都 一 个 y ,任 意 的 人 x 都 喜 爱 他 ， 即“ 上 帝 ”3 . 2 谓 词 逻 辑3.2.2 一 阶 谓 词 逻 辑原 子 公 式 ：设为 原 子 公 式 是 项项 ：任 何 常 量 是 项 任 何 变 量 是 项 n > 1 个 参 数 的 任 何 表 达 式是 项 ，而 f 是n阶 的 函 数 ）是 项 闭 包 条 款 ： 其 他 东 西 都 不 是 项 3 . 2 谓 词 逻 辑3.2.2 一 阶 谓 词 逻 辑谓 词 公 式是 任 意 n 元 谓 词 ，, 则 称（ 其 中 ，原子公式是谓词公式若 A 为谓词公式，则 ~ A 也是一个谓词公式若 A 和 B 都是谓词公式，则(A AB), (A VB), (A -B )和(AB)也都是谓词公式若 A 是谓词公式， 和 也都是谓词公式只有有限次应用上述规则得到的公式，才是谓词公式3 .2 谓词逻辑3.2.2 一阶谓词逻辑对于 ，x 称为指导变量A 称为相应量词的辖域?x(p(x))X在辖域A 中的出现称为约束出现x 以外的变量在辖域A 中的出现称为自由出现?x(p(x,y))3 .2 谓词逻辑3.2.2 一阶谓词逻辑例对于指导变量：? 的辖域：X、y 是约束出现还是自由出现y 是约束出现，x 是自由出现3 .2 谓词逻辑3.2.2 一阶谓词逻辑不同量词如果采用相同的指导变量名，易引起混淆一般要求不同的量词使用不同的指导变量名称3 .2 谓词逻辑3.2.2 一阶谓词逻辑当在一个公式中，一个变量符号既是约束出现的变量，又是自由出现的变量时，需要作变量符号更换。

换名规则：将量词辖域中某个约束出现的变量及其指导变量替换为此辖域中未出现过的个体变量符号既作为指导变量约束出现又自由出现， 因此要换掉其中之一换名规则更换的是指导变量可替换为3.2谓词逻辑3.2.2 一阶谓词逻辑替代规则：对某自由出现的个体变量用与原公式中未出现过的变量符号去替代，且处处替代x 既作为指导变量约束出现又自由出现， 且多处自由出现替代规则更换的是自由出现的变量，且处处替代替换为3.2谓词逻辑3.2.2 一阶谓词逻辑谓词公式的解释对谓词公式中的各种变量制定具体的常量去替代一个解释包括非空个体域DD中一部分特定元素；D上一些特定的函数；D上一些特定的谓词如果谓词公式在特定解释下为真，称这个解释满足这个谓词公式，是这个谓词公式的一个模型永真与不可满足3 .2谓词逻辑3.2.2 一阶谓词逻辑例 :p92给定解释I如下个体域：函数 f(x) : f(2)=3, f(3)=2谓词：P(x)为 P(2) =0 ,P(3) =1Q(x,y)为 Q(iJ)=l, ij = 2,3R(x,y)为 R(2,2)= R(3,3)=l, R(2,3)=R(3,2)=0求解释I下，下列谓词公式的真值1、2、3.2谓词逻辑3.2.2 一阶谓词逻辑解1、=> (P(f(2)) A Q(2,f(2))) V (P(f(3)) A Q(3,f(3)))=> (P( ) AQ(2, )) V(P( ) AQ(3, ))=> (1 Al) V(OA1)=>12 、= >=>(R(2,2) V R(2,3)) A (R(3,2) V R(3,3))=>(1 VO) A (OV1)=>13 .2 谓词逻辑3.2.3谓词演算与推理谓词演算公式约束变量换名规则，Q 为任意量词(Qx)P(x)<=> (Qy)P(y) (Qx)P(x,z)<=> (Qy)P(y,z)量词消去等值式，对于有穷个体域量词否定等值式量词分配等值式3 .2 谓词逻辑3.2.3谓词演算与推理量词辖域收缩与扩张等值式3 .2 谓词逻辑3.2.4谓词知识表示谓词逻辑表达的规范形式P 是谓词，而 表示个体( 主体或者客体)知识库：表达知识的一组谓词公式的集合。

语句的集合对环境、规则等信息的结构化描述基于知识的智能体的核心构件3 .2 谓词逻辑3.2.4谓词知识表示定义谓词例 1、小李与小张打网球Play(x,y,z)表 示 x,y在进行z 运动Play ( Li, Zhang, tennis)2、我在长安大学当教师Work ( x, y, z)表 示 x 在 y 单位从事z 工作Work ( Me, Chd, teacher)3、怪物洞穴中某个房间有微风、有臭味、没有怪物、没有陷阱、没有金子Roomij ( x, y, z, m, n ) 参数分别对应有没有微风、臭味、怪物、陷阱、金子Roomi,j( 1,1, 0, 0, 0)3 .2 谓词逻辑3.2.4谓词知识表示例： 准前女友双眼皮， 大眼睛doublefold(x) A bigeyes(x)一头乌黑的头发blackhair(x) A thickhair(x)一身漂亮的呢子大衣beautifuldress(x)走路的姿态赛过模特graceful(x)3 .2 谓词逻辑3.2.4谓词知识表示知识表示例 P 9 7房间里有机器人R obot,积 木 块 B o x 、两个桌子 A 和 B 。

定义谓词Table(A)A 是桌子EmptyHanded(Robot)At(Robot, A)在A旁Holds(Robot, Box)On(Box,A)子A上3.2谓词逻辑3.2.4谓词知识表示初始状态EmptyHanded(Robot)At(Robot, A)On(Box,A)Table(A)Table(B)机器人拿起BoxAt(Robot, A)Holds(Robot, Box)Table(A)Table(B)机器人空器人位置机器人拿着BoxB ox在桌3 .2谓词逻辑3.2.4谓词知识表示3.2谓词逻辑3.2.3谓词演算与推理前束范式一约束在前面的范式将所有的量词都移到最左边就得到了前束范式与合取范式类似，所有的谓词公式都可以改写成前束范式的形式求前束范式的步骤前束范式中每个量词的指导变量不同，如果指导变量相同，则需要利用换名规则进行替换如果自由变量与指导变量相同，则需利用换名规则或替代规则替换其中之一利用量词辖域收缩扩张等值式替换3.2谓词逻辑3.2.3谓词演算与推理例 P 9 4 求前束范式量词与指导变量：自由出现的变量：换名规则替代规则P93 3-73 .2 谓词逻辑3.2.3谓词演算与推理P93 3-8P93 3-3P93 3-43 .2 谓词逻辑3.2.3谓词演算与推理谓词推理例： 20世 纪 70年代的漫画都是日本漫画家创作的， 这幅漫画是20世 纪 70年代的作品；因此它是日本漫画家的作品解：设 P(x):属 于 20世 纪 70年代的漫画Q(y):属于日本漫画家的作品a : 一幅漫画前提：结论：Q(a)证明：前提引入量词消去前提引入假言推理3.3谓词逻辑归结原理3.3谓词逻辑归结原理3.3.1归结原理命题逻辑归结原理：将由前提A得到结论B的证明过程转化为证明A A ~B为矛盾式将其转化为合取范式，得到子句集对于形如 的公式求取子句集时，可以分别求 各自的子句集，再取并集利用归结原理消去互补项，直到得到空子句。

3 .3谓词逻辑归结原理3.3.1 归结原理例 (P f(Q fR )) f ((P f Q) f(P fR))转化为待归结命题公式：(P -(Q f R )) A ~((P - Q )一(P -R))求子句集: 分别对(P - (QTR ) ) 和 ~ (出T Q) T(P IR ))两部分求取子句集，再取并集3 .3谓词逻辑归结原理3.3.1 归结原理归结：1、~PV~QVR2、 ~P V Q3、P4、~R5、 -PVR6、 R7、 □因此得证3 .3 谓词逻辑归结原理3.3.1 归结原理3 .3 谓词逻辑归结原理3.3.1 归结原理谓词逻辑归结原理的重点如何对前束合取范式消去量词命题逻辑谓词逻辑1、2 归结3、5 归结4、6 归结如何利用置换与合一对不同变量的子句进行置换命题逻辑谓词逻辑3 .3 谓词逻辑归结原理3.3.1 归结原理求前束合取范式：方法一：先转化为前束范式，再将辖域中的谓词公式转化为合取范式方法二：⑴消去联结词T 和？ ⑵将联结词~ 向内深入，使之只作用于原子公式⑶利用换名或替代规则使所有约束变元的符号都不同， 并且自由变元与约束变元的符号也不同。

⑷利用量词辖域的扩张和收缩，扩大量词至整个公式⑸再将辖域中的谓词公式转化为合取范式3 .2 谓词逻辑3.2.3谓词演算与推理量词辖域收缩与扩张等值式3 .2 谓词逻辑3.2.3谓词演算与推理求前束合取范式(?x)P(x) - Q(x)?~(?x)P(x) V Q(x)?(?x)(~P(x)) V Q(x)?(?x)(~P(x)) V Q(y)?(?x)(~P(x) V Q(y))?(?x)(~P(x) V Q(y))3 .3 谓词逻辑归结原理3.3.2 Skolem 标准型例求前束合取范式3 .3 谓词逻辑归结原理3.3.2 Skolem 标准型Skolem标准型：对前束合取范式消去所有的量词P100第一步：消去存在量词？：1、如果? 之前(左边) 没有任意量词？ ，则用常量替换? 的指导变量可用常量b 替换x 消去存在量词，得 P(b,a)2、如果? 之前(左边) 有任意量词？，则用任意量词的函数替换? 的指导变量可 用 f(x)替 换 y 消去存在量词，第二步消去任意量词？ ：简单的省略即可3 .3 谓词逻辑归结原理3.3.2 Skolem 标准型例：1、消去存在量词? y 和 ?u :? y 前面有任意量词，指导变量为x , 因此用f(x)替 换 y,?u前面有任意量词，指导变量为x , 因此用g(x)替 换 u2、消去任意量词:3 .3谓词逻辑归结原理3.3.2 Skolem 标准型例 判断下列的消去量词的过程是否正确。

证明：①?x ?y G(x, y)② ？yG(x,y) 消 去?x③G(x, a) 消 去？y对任意x ,都存在一个恒定常量a ,使G(x, a )成立3 .3谓词逻辑归结原理3.3.3子句集定义文字：不含任何联结词的谓词公式子句：一些文字或其非的析取子句集：所有子句的集合计算过程将谓词公式转化为前束合取范式消去存在量词，略去任意量词，得Skolem标准型将各子句提出，得到子句集谓词公式不可满足，当且仅当其子句集不可满足的形如 的谓词公式在求子句集时可以分别对 求子句，再取其并集3 .3 谓词逻辑归结原理3.3.1 归结原理谓词逻辑归结原理的重点如何对前束合取范式消去量词命题逻辑谓词逻辑如何利用置换与合一对不同变量的子句进行置换命题逻辑谓词逻辑3 .3 谓词逻辑归结原理3.3.4置换与合一置换：形如 的有限集合x i 必须是变量，称为置换变量t i 可以是常量、变量或者函数，称为置换项表 示 用 项 t i 替换谓词公式中的变量xi要 求 ti* x i, x i不能循环的出现在另一个t i中{x/y, y/z){x/y, y/x}{x/y, y/z, z/x}3 .3 谓词逻辑归结原理3.3.4置换与合一例: 设有公式P(x,f(y),b)置换 1 为: sl={z/x, w/y}P(x,f(y),b)sl= P(z,f(w),b)置换 2 为： s2={a/y}P(x,f(y),b)s2= P(x,f(a),b)置换 3 为:s3={q(z)/x, a/y}P(x,f(y),b)s3= P(q(z),f(a),b)置换 4 为:s4={c/x, a/y}P(x,f(y),b)s4= P(c, f(a),b)3 .3 谓词逻辑归结原理3.3.4置换与合一例 : 设 0 ={f(y)/x , z/y},入={a/x , b/y, y/z},对 L=P(x,f(y),b),先做。

置换，再做入置换，即求3 .3 谓词逻辑归结原理3.3.4置换与合一置换的合成：对谓词公式 L, 0 = {tl/xl, t2/x2 , ... , tn/xn}和入={ul/yl, u2/y2 , ... , un/yn}为两个置换，则称 为 e 和人的合成，可由下式得到1、如果 ，则消去2、当 ，删去3 .3 谓词逻辑归结原理3.3.4置换与合一例 : 设 0 ={f(y)/x , z/y},入={a/x , b/y, y/z}求3 .3 谓词逻辑归结原理3.3.4置换与合一例：对子句集{ P(x), ~P(a)}做置换{a/x}得 到 { P ( a ) ,〜 P(a)}{ P(x,y), ~P(a,b) V Q(x)}做置换{a/x, b/y}{ P(a,b), ~P(a,b) VQ( ))3 .3 谓词逻辑归结原理3.3.4置换与合一合一：设有公式集,如果存在一个置换使 ， 则称e 是F的一个 哈 O如果谓词公式FL F 2 可合一，那么 就是一对互补项{P(x), ~P(a)}经合一 {a/x}得 到 {P(a), ~P(a)}谓词逻辑归结原理：如果子句集中的两个字句含有互补项，则可以进行归结消去3 .3 谓词逻辑归结原理3.3.4置换与合一例：下列字句都可以归结{P(x), ~ P(x)}{P(X), ~ P(a)}经合一 {a/x}后，{P(x), ~P(a)}可合一{P(x,y), ~ P(a,z)}经合一{a/x,z/y}, {P(x,y), ~P(a,z)}可合一这些子句的文字可合一，都可以进行归结{P(a,x,f(g(y))), ~ P(z,f(a), f(u))}需要一个判断公式集能否合一的算法3 .3 谓词逻辑归结原理3.3.4置换与合一最一般哈" 一"(mgu)设 是谓词公式F的一个合一， 如果对于F的任意一个合一 8 ,都存在一个置换入， 使 ， 则称 是一个最一般^~ o求取办法：对每一项逐一比较并进行合一置换P1041、令2、令3、如果 已经合一，停止迭代， ；否则，找不一致集4、 若 中 存 在 元 素 和 ， 且 不 出 现 于 中 ， 转5 ;否则，不可合一5、令 ，6、k=k+l,转 33 .3谓词逻辑归结原理3.3.4置换与合一例{P(a,x,f(g(y))), ~P(z,f(a),f(u))} ,计算 mgu解:1 W= { P( a , x, f(g(y))), P( z , f(a), f(u)) }23 WO未 合 一 ，从左到右找不一致集，45 令 ，6 k=k+l,# 33 .3 谓词逻辑归结原理3.3.4置换与W-3' W 1 未 合 一 ,从左到右找不一致集,4，56， k=k+l,转 33- W 2未 合 一 ，从左到右找不一致集，4”5八 令已合一，3 .3 谓词逻辑归结原理3.3.5归结式归结式：设 为两个无公共变量的子句，分别是 的文字，如果 可合一，则为的归结式例：1 P(x) VQ (x,y)与 ~P(a) VR (b,z)的归结式:经台" 一~｛ a/x｝置换归结得到：2 P(x,y) VQ (x) VR (x )与〜 P(a,z) V~Q (b)的归结式：经台" 一*｛ a/x, z/y｝归结得到：经合一｛ b/x｝归结得到：P(b,y) VR (b) V~P(a,z)3 .3谓词逻辑归结原理3.3.5归结式几种不能归结的情况谓词不一致不能进行归结如：「6 )与~ (5 5 )不能归结常量之间不能进行归结如：P(a)与 ~P(b)不能归结，不能在常量之间置换｛ a/b｝变量与其函数之间不能进行归结如：P(x)与 ~P(f(x))不能归结，不能做置换｛ f(x)/x｝不能同时消去两个互补对3 .3谓词逻辑归结原理3.3.5归结式如果子句可以简化，应该先简化再归结例C 1可以简化，做合一置换{f(x)/y),取 mgu={g(a)/x},归结式为Q(b) V Q(g(g(a)))3 .3 谓词逻辑归结原理3.3.6归结过程写出谓词关系公式写出待归结的谓词表达式化 为 Skolem标准型求子句集S对 S 中的互补子句进行归结归结式仍加入S , 反复进行归结得到空子句口得证3 .3 谓词逻辑归结原理3.3.6归结过程例：人都是妈生的，张飞是人，张飞是妈生的定义谓词:Mum(x)表 示x是妈生的Human(x)表 示x是人前提：?x (Human(x)Mum(x)),Human(ZF)结论：Mum亿F)写出逆否命题：3 .3谓词逻辑归结原理3.3.6归结过程1. ~Human(x) V Mum(x)2. Human(ZF)3. ~Mum(ZF)3与1归结，经置换｛4. -Human(ZF)5. 4与2归结得到口所以，逆否命题为恒假，原命题为真3 .3谓词逻辑归结原理3.3.6归结过程得到例：已知：R1:会朗读的生物是识字的,R2:海豚 不识字，R3: 海豚是很机灵的。

证明：有些很机灵的东西不会朗读分析：1、需要几个谓词？2、海豚是否必须设为谓词？3、生物是否必须设为谓词？3 .3 谓词逻辑归结原理3.3.6归结过程3 .3 谓词逻辑归结原理3.3.6归结过程3 .3 谓词逻辑归结原理3.3.6归结过程例：设任何通过计算机考试并获奖的人都是快乐的；任何肯学习或幸运的人都能通过所有的考试；张不肯学习但他是幸运的；任何幸运的人都能获奖求证：张是快乐的定义谓词：Pass(x,y)表 示 x 通 过 y 考试Win(x,prize)表 示 x 能获奖Lucky(x)表 示 x 是幸运的Study(x)表 示 x 肯学习Happy(x)表 示 x 是快乐的3 .3 谓词逻辑归结原理3.3.6归结过程写出谓词公式：前提：结论：Happy(zhang), 取否 ~ Happy(zhang)证明：对前提和结论分别求子句3 .3 谓词逻辑归结原理3.3.6归结过程3 .3 谓词逻辑归结原理3.3.6归结过程得子句 ~Study(zhang)Lucky(zhang)得子句 ~Luck(w) V Win(w,prize)结论： ~ Happy(zhang)共得到7 条子句3 .3 谓词逻辑归结原理3.3.6归结过程1、2、3、4、 ~ Study(zhang)5、 Lucky(zhang)6、 ~ Luck(w) V Win(w,prize)7、 - Happy(zhang)8{zhang/x} 1-79{zhang/w} 8-6109-511{zhang/u, computer/v} 10-312、11与 5 归结，得口3 .3 谓词逻辑归结原理3.3.6归结过程本章作业P1233.183.193.203.233.243 .3 谓词逻辑归结原理3.3.7归结过程控制策略控制的要点要解决的问题是归结方法的知识爆炸控制的目的是归结点尽可能少控制的原则是删除不必要的子句或对参加归结的子句加以限制仅选择合适的子句进行归结，避免多余的、不必要的子句归结式出现3 .3 谓词逻辑归结原理3.3.7归结过程控制策略删除策略1、删除永真子句2、删除可被其他子句归类的子句归类：如果两个子句C 和 D , 若 有 置 换 使,则称子句C 把 D 归类，可从子句集中删除D例：两个子句 C=P(x), D=P(a) VQ(y)还原为谓词公式：P(x) A (P(a) V Q(y))取置换{a /x },可知子句C 把 D 归类，D 可删除3 .3 谓词逻辑归结原理3.3.7归结过程控制策略支撑集策略一个不可满足的子句集S 的子集T , 如 果 S-T是可满足的，则 T 为 S 的支撑集对 于 A - B 定理证明问题来说，~ B 就是支撑集归结过程中每次都选择支撑集及其归结式与其他子句归结3 .3 谓词逻辑归结原理3.3.7归结过程控制策略语义归结策略将子句集按一定的语义分为两部分每部分内的子句不允许进行归结，同时引入文字次序。

归结时，其中一个子句的被归结文字是该子句中排序最前的文字例：S={~PV 〜 Q VR,PVQ ,Q VR,~R},文字次序为 P,Q,R,令解释1={〜 P,~Q， 〜R },在I下为假的子句记为s i ,为真的语句记为s 2 ;则3.3谓词逻辑归结原理3.3.7归结过程控制策略归 结s2如 下： 12si3sis2451、2归结，s26R5、3归结，si□76、4归结3.3谓词逻辑归结原理3.3.7归结过程控制策略线性归结策略每次都用上一次归结得到的归结式与其他子句归结单元归结策略每次归结都有一个子句是单元子句，即只含一个文字的子句输入归结策略每次归结必有一个子句是原始子句集中的子句本章重点命题逻辑归结原理将语言描述转化为谓词公式自由出现、约束出现、前束范式置换、置换的合成台 最 一 般 合 一谓词逻辑归结原理1、概述1、概述智能体的一般结构传感器：感知外部环境执行器：根据指令控制智能体的行为学习元件：知识的获取知识库：知识的形式化描述推理决策元件：根据环境与知识做出决策类人思考与认知模型生物学心理学计算机科学1、概述知识的概念：Feigenbaum:知识是经过消减、塑造、解释和转换的信息Bernstein:知识是由特定领域的描述、关系和过程组成的Hayes-roth:知识是事实、信念和启发式规则知识是人类对于客观世界的认识的表达， 是以某种结构化的方式表示的概念、事件和过程1、概述知识的相对正确性环境时间条件目标人类不断发现新知识，替代旧知识，推动历史的前进1、概述令人困扰的知识节俭是美德人生的苦是因为有欲望见义勇为鬼神9999991、概述知识的分类根据内容分类：原理性知识：对客观事实、原理的认识的知识方法性知识：如何利用客观规律去解决问题的知识根据形式分类显式知识：能够直接表达和处理的知识隐式知识：不能够直接表达和处理的知识根据性质分类理论性知识：经验性知识：1、概述知识的分类根据表达的内容分类事实性知识：描述一般性的事实大多数知识都属于事实性知识过程性知识：描述完成某一件事的过程步骤如：某药品的疗程和用法游泳元知识：有关知识的知识。

如：HELP文档1、概述构成系统知识集合所必需的基本知识元素事实：基本知识单元分类、属性、关系、各种事实等等规则：有关行动、动作的具有因果关系的知识控制：多个行动同时激活时，需要排列其优先顺序元知识：对规则的解释、说明、校验等知识，有时与控制重叠1、概述知识表示知识表示是研究用计算机表示知识的可行性、 有效性的一般方法它既是一种数据结构，又是一种处理机制知 识 表 示 =知识的数据结构+知识的处理机制知识表示的方法谓词逻辑产生式规则语义网络框架1、概述知识表示方法的选取表达充分性，具备确切表达有关领域中各种知识的能力；推理有效性，能够与高效率的推理机制密切结合，支持系统的控制策略；知识和元知识的一致，知识和元知识是不同层次的知识，使用统一的表示方法可以简化知识处理；操作维护性，便于知识更新和知识库的维护；理解透明性， 便于人类理解，易读、易懂， 便于知识的获取1、概述知识表示方法的分类谓词逻辑表示优点结构清晰，有效地分离了知识和处理知识的程序；一阶谓词逻辑具有完备的逻辑推理算法；可以保证知识库中新旧知识在逻辑上的一致性和演绎所得结论的正确性；不依赖于任何具体领域，通用性好缺点难以表达不确定性知识和启发性知识推理方法在事实较多时易于出现组合爆炸，推理过程冗长、效率低。

1、概述产生式表示：用 “ if... then”表示知识间的因果关系优点自然性好， “ If...then” 的形式与人类的判断性知识基本一致，便于推理；便于引入各种启发式知识格式固定，形式简单，规则间相互独立，便于统一处理，模块性好缺点推理效率低下难以表现规则间的关系，难以表现结构和层次关系1、概述语义网络表示：利用节点和带标记的边构成有向图描述事件、概念、状况、动作及客体之间的关系优点直观地表现了各节点之间的联系体现了人类思维的联想过程， 便于将自然语言转换成语义网络具有广泛的表示范围和强大的表示能力一种结构化的知识表示法缺点推理规则不明了，不能充分保证结论的严格性和有效性一旦节点个数太多，网络结构复杂，推理就难以进行不便于表达判断性知识1、概述框架表示法：一种描述固定情况的数据结构，便于表示知识的内部结构以及知识间的关系优点与人类的思维和问题求解过程相似表达能力强，层次结构丰富，能够有效的组织知识可以利用过去获得的知识对未来的情况进行预测，因此可以通过框架来认识某一类事物缺点难以保证问题求解的可行性和推理过程的严密性许多实际情况与原型存在较大的差异，适应能力不强各子框架的数据结构如果不一致，会造成推理的困难。

1、概述知识表示观知识表示与推理机分离知识表示与推理一体当前的发展方向混合知识表示面向对象的知识表示2、产生式表示2、产生式表示产生式表示的起源1943, 美国数学家Post构造了形式化的计算工具1955, 美国语言学家乔姆斯基C homsky创立了转换生成语法1960,美国计算机科学家巴克斯Backus提出了巴克斯范式,描 述ALGOL 60的语法规则,1977年获图灵奖1972年， 纽厄尔和西蒙在研究人类的认知模型中开发了基于规则的产生式系统1975年获图灵奖， 人工智能符号主义学派创始人2、产生式表示产生式（ condition-action规则） 的基本形式P -Q 或者 IFPTHEN Q;P :前 件condition,是产生式的前提，它给出了该产生式可否使用的先决条件，由事实的逻辑组合来构成Q :后 件action,是一组结论或操作，它指出当前题P满足时，应该推出的结论或应该执行的动作产生式的含义如果前提P满足，则可推出结论Q或执行Q所规定的操作事实+ 规则2、产生式表示事实：第一类：给一个语言变量赋值如：香蕉是黄色的，老李年龄35岁张韶涵是一个歌手表示 三元组；( 对象，属性，值)香蕉是黄色的 (banana, color, yellow)老李年龄35岁 (Li, age, 35)张韶涵是一个歌手(Angela Chang , job, Singer)2、产生式表示第二类：描述多个语言变量之间的关系如：小莉是小刘的女朋友王老师是张三的导师天青色等烟雨表 示 三 元 组 ； ( 关系，对 象1 ,对 象2)小莉是小刘的女朋友 (girlfriend, Li, Liu)王老师是张三的导师 (tutor, Mr Wang, Zhangsan)天青色等烟雨 (wait for, azure, misty rain)2、产生式表示存在不确定条件的表示四元组： ( 对象，属性，值 ，可信度(0・1之间的数) )硬币有50%的可能为正面向上(coin, up, obverse, 0.5)全 班2/3的同学爱听周杰伦的歌(student, like Jay Chou' songs, true, 0.667)产生式表示有70%的可能会考(CA, test, true, 0.7)2、产生式表示规则表示事实间的因果关系以if then的形式描述一般形式为：前件一后件前件通常为一些事实的合取或者析取后件可以是结论，也可以是动作一个产生式规则的结论可以作为另一个产生式规则的前提2、产生式表示例I f天下雪了 then穿棉袄I f骄傲被现实大海冷冷拍下then懂得要多努力才能走到远方I f水 电 解then ( 生成氢气人生成氧气)If ( 想考研A学习好A毕业生)then 考研成功If （ 动物有犬齿 A有 爪 A 眼盯前方） then食肉动物If （ 有流感症状八（ 去过甲流疫区V 接触过甲流患者））then甲流，可 信 度 x2、产生式表示以产生式规则求解问题的系统称作产生式系统产生式系统的结构2、产生式表示知识库规则库：存放产生式规则包含从初始状态到目标状态的所有变换规则完整性、一致性、准确性、合理性、灵活性数据库：存放事实已知事实中间结果推理结果匹配规则：当数据库中的事实与规则库中的产生式规则的前件相匹配时，该规则被激活，其结论成为中间结果加入数据库2、产生式表示推理机：问题求解的实现部件控制整个产生式系统的运行决定推理路线控制协同规则库与数据库推理机的工作规则匹配冲突消解执行后件终止条件2、产生式表示规则匹配：按一定策略从规则库选择规则与数据库中的事实进行匹配匹配成功：此条规则被激活，加入被激活候选集（ 冲突集）事实：牛； 规则： if牛 then吃草匹配失败：输入与前件矛盾，此条规则被放弃事实：牛； 规则： if马 then吃草匹配无结果：规则前件与事实无关，则该条规则加入待测式规则集事实：牛； 规则： if有 蹄 then吃草2、产生式表示冲突消解：当匹配成功的规则多于一条时，需要根据一定的策略进行选择事实：牛；规则1: i f 牛 then吃草规则2: i f 牛 then有蹄冲突消解策略：依次执行2 条规则2、产生式表示有时多条规则间会存在相互冲突事实：地震，室内，教师，有未成年人规则：R l:if地震八室内then跑出室外R 2:if地震八室内A 教 师 then组织学生跑出室外R 3:if地震八室内A有未成年人then保护未成年人冲突消解策略为：R3> R2> RI2、产生式表示执行后件：如果后件不是问题的目标，则解释并执行规则后件的动作如果后件是一个或者多个结论，则将其加入数据库中事实：牛； 规则： if牛 then有蹄执行结果：将 “ 有蹄”加入数据库中如果后件是一个或多个行动，则按照一定策略执行事实：地震，睡午觉规则：if地震八睡午觉then跑 A 穿衣服终止条件如果后件是问题的目标，则结束，输出求解路径2、产生式表示产生式系统的推理正向推理从已知事实出发，与规则库中的规则匹配的方式自底向上，也称为数据驱动方式反向推理从目标出发，反向使用规则，直到找到已知事实自顶向下，也称为目标驱动方式双向推理正向推理与反向推理同时使用，直到在某一中间结果重合2、产生式表示正向推理的步骤步 1将初始事实置入动态数据库；步 2 用动态数据库中的事实，匹配目标条件， 若目标条件满足，则推理成功，结束。

步 3用待测试规则集中各规则的前件匹配动态数据库中的事实，将匹配成功的规则组成冲突集；步 4若冲突集为空，则运行失败，退出步 5对冲突集做冲突消解，对选择执行的各规则，将其结论加入动态数据库，或执行其动作，转 步22、产生式表示例：植物分类问题的产生式系统描述及其求解设由下列植物识别规则组成一个规则库， 推理机采用正向推理算法，建立一个产生式系统规则R l:if它种子的胚有两个子叶V 它的叶脉为网状then它是双子叶植物R 2: if它种子的胚有一个子叶then它是单子叶植物R 3: if它的叶脉平行then它是单子叶植物R 4: if （ 它是双子叶植物A 它的花托呈杯形）V（ 它是双子叶植 物 八它的花为两性八它的花瓣有 5 枚）then它是蔷薇科植物2、产生式表示R5: i f它是蔷薇科植物八它的果实为核果then它是李亚科植物R6: i f它是蔷薇科植物八它的果实为梨果then它是苹果亚科植物R7: i f它是李亚科植物人它的果皮有毛then它是桃R8: i f它是李亚科植物八它的果皮光滑then它是李R9: i f它的果实为扁圆形八它的果实外有纵沟then它是桃RIO: i f它是苹果亚科植物A它的果实里无石细胞then它是苹果Rll: i f它是苹果亚科植物A它的果实里有石细胞then它是梨R12: i f它的果肉为乳黄色人它的果肉质脆then它是苹果2、产生式表示初始事实：它的果肉为乳黄色它的果实里无石细胞它的果实为梨果它的果实无毛它的花托呈杯形它种子的胚有两个子叶目标条件：该植物是什么设动态数据库、冲突集、待测试规则集均为空2、产生式表示推理过程初始事实写入动态数据库｛ 果肉为乳黄色，果实里无石细胞，果实为梨果，果实无毛，花托呈杯形，种子的胚有两个子叶｝第一次循环用动态数据库的事实匹配目标条件，目标条件不成立用规则库中的规则逐一与数据库匹配R l:if它种子的胚有两个子叶V 它的叶脉为网状then它是双子叶植物“双子叶胚”匹配成功，冲突集为｛ R 1｝R 2: if它种子的胚有一个子叶then它是单子叶植物匹配失败，该条规则放弃R 3: if它的叶脉平行then它是单子叶植物匹配无结果，该条规则加入待测试规则集，待测试规则集｛ R 3｝2、产生式表示事实：｛ 果肉为乳黄色，果实里无石细胞，果实为梨果，果实无毛， 花托呈杯形，种子的胚有两个子叶｝R4:if （ 它是双子叶植物八它的花托呈杯形）V（ 它是双子叶植物八它的花为两性八它的花瓣有5枚）then它是蔷薇科植物“ 双子叶植物”目前的动态数据库无法匹配，匹配无结果，该条规则加入待测试规则集，待测试规则集｛ R3,R4｝R5: i f它是蔷薇科植物A 它的果实为核果then它是李亚科植物“ 果实为梨果” 匹配失败，该条规则放弃R6: i f它是蔷薇科植物八它的果实为梨果then它是苹果亚科植物“ 蔷薇科植物”目前的动态数据库无法匹配，匹配无结果， 该条规则加入待测试规则集, 待测试规则集｛ R3, R4 , R6｝2、产生式表示事实：｛ 果肉为乳黄色，果实里无石细胞，果实为梨果，果实无毛， 花托呈杯形，种子的胚有两个子叶｝R7: i f它是李亚科植物A 它 的 果 皮 有 毛then它是桃”果 实 有 毛 “ 匹配失败，该条规则放弃R8: i f它是李亚科植物八它的果皮光滑then它是李匹配无结果，待测试规则集｛ R3,R4,R6,R8｝R9: i f它的果实为扁圆形A 它的果实外有纵沟then它是桃匹配无结果，待测试规则集｛ R3, R4 , R6, R8, R9｝RIO: i f它是苹果亚科植物A它的果实里无石细胞then它是苹果匹配（ 无结果，待双I试规贝” 集｛ R3, R4 , R6, R8, R9,R10｝2、产生式表示事实：｛ 果肉为乳黄色，果实里无石细胞，果实为梨果，果实无毛， 花托呈杯形，种子的胚有两个子叶｝Rll: i f它是苹果亚科植物人它的果实里有石细胞then它是梨”果实有石细胞“匹配失败，该条规则放弃R12: i f它的果肉为乳黄色人它的果肉质脆then它是苹果匹配无结果， 待测试规贝I集｛ R3, R4 , R6, R8, R9, R10,R12｝冲突消解冲突集｛ R1｝无冲突，则将后件加入动态数据库｛ 果肉为乳黄色，果实里无石细胞，果实为梨果，果实无毛，花托呈杯形，种子的胚有两个子叶，双子叶｝2、产生式表示例：冲突消解同一事实与多条规则匹配成功时，进行冲突消解事实：地震，室内，教师，有未成年人规则：R l:if地震八室内then跑出室外R2: i f地震A室内A 教 师then组织学生跑出室外R 3:if地震八室内A有未成年人then保护未成年人匹配过程R 1 :匹配成功，冲 突集 为｛ R1｝R 2 :匹配成功，冲 突集 为｛ R1,R2｝R 3 :匹配成功，冲 突 集 为｛ RI, R2, R3｝冲突消解，执 行R32、产生式表示不进行冲突消解会引起的错误R 1 :匹配成功，不考虑冲突消解，执 行 后 件 “ 跑出教室” ,数 据 库 ｛ 地震，室外，教师，有未成年人｝R2、R3全部匹配失败不同事实与规则匹配成功时，需要进行冲突消解吗？事实：地震，教师，夏天规则：R l:if地 震then 跑R 2: if教师 t h e n 上课R 3: if夏天 then 穿短袖冲 突 集 {R I, R 2, R 3}冲突消解，执 行 R 1, R 32、产生式表示正向推理总结用规则库中各规则的前件匹配动态数据库中的事实是一种自底向上的推理方法将匹配成功的规则组成冲突集，进行冲突消解反向推理：从目标出发，反向使用规则，直到找到已知事实2、产生式表示反向推理步骤：步 1将初始事实置入动态数据库，将目标条件置入目标集；步 2若目标集为空，则推理成功，结束。

步 3 取目标集中第一个目标， 用动态数据库中的事实同其匹配，若匹配成功，删除该目标，转步2;步 4 用规则集中的各规则的后件同该目标匹配，若匹配成功，则将第一个匹配成功且未用过的规则的前件作为新的目标，并取代原来的父目标而加入目标集，转步3;步5若该目标是初始目标，则推理失败，退出步6将该目标的父目标移回目标集，取代该目标及其兄弟目标，转步32、产生式表示恋爱规则产生式系统设由下列恋爱规则组成一个规则库， 推理机采用逆向推理算法，建立一个产生式系统恋爱的各阶段认识交往赢得好感确立恋爱关系建立长期关系共存反依赖独立共生2、产生式表示规则RI: i f请 人 介 绍then认识R2: i f参 加 聚 会then认识R3: i f搭 讪then认识R4: i f设 计 邂 逅then认识R5: i f认识八一起自习then交往R6: i f认识A送 花then交往R7: i f认识人约会then交往R8: i f交往A （ 有 责 任 心V踏实可靠）then赢得好感2、产生式表示R9: i f交往A （ 温柔善良V善解人意）then赢得好感RIO: i f交往A勤奋努力then赢得好感Rll: i f交往A阳光活泼then赢得好感R12: i f赢得好感人暗示then确立恋爱关系R13: i f赢得好感人明示then确立恋爱关系R14: i f赢得好感人牵手then确立恋爱关系R15: i f恋爱关系A 体贴容让A不百依百顺then建立长期关系2、产生式表示初始事实：设计邂逅送化有责任心勤奋努力明确表示体贴容让不百依百顺目标条件：建立长期关系设动态数据库、目标集、待测试规则集均为空取第一条目标｛ 暗示｝ , 与动态数据库中的事实匹配，匹配不成功用规则库中的规则后件与该目标匹配，无规则的后件能够匹配检查该目标是否为原始目标，不是，则继续执行推理将当前目标的父目标移回目标集，取代该目标及其兄弟目标，转3取第一条目标｛ 一起自习｝ , 与动态数据库中的事实匹配，匹配不成功用规则库中的规则后件与该目标匹配，无规则的后件能够匹配检查该目标是否为原始目标，不是，则继续执行推理将当前目标的父目标移回目标集，取代该目标及其兄弟目标，转32、产生式表示正向推理与反向推理的比较推理方向正向推理是从事实到结论的自底向上的推理反向推理是从目标到事实的自顶向下的推理规则匹配以及匹配成功后的执行方式正向推理是用事实匹配规则的前件，匹配成功则执行后件，将后件的结论加入动态数据库反向推理是用目标匹配规则的后件，匹配成功则将规则前件作为新的目标加入目标集，替换其父目标冲突消解正向推理需要进行冲突消解反向推理不需要冲突消解2、产生式表示动态数据库正向推理不断向动态数据库中添加中间结果；反向推理动态数据库内容不变目标集正向推理的目标集就是初始目标，且推理过程中目标集内容不变反向推理中不断用子目标替代父目标终止条件正向推理：动态数据库中的事实能够与目标匹配反向推理：目标集中的所有目标都匹配成功，即目标集为空2、产生式表示双向推理正向推理与反向推理同时使用，直到在某一中间结果重合2、产生式表示双向推理进 程1和进程2分别执行正向推理和反向推理动态数据库进 程1正向推理向动态数据库添加事实进 程2反向推理使用动态数据库进行匹配终止条件进 程2中的目标集为空，则推理成功2、产生式表示产生式与蕴涵式的异同共同点都表示由条件推出结论不同点蕴涵式是一个逻辑表达式，其逻辑值只有真和假，不能表达不确定的知识。

谓词逻辑中蕴涵式的匹配必须是精确的产生式表示的知识可以是不确定的，产生式的匹配可以是不确定的2、产生式表示产生式与条件语句的主要区别前件结构不同传统程序设计语言中条件语句的左部仅仅是一个布尔表达式产生式的前件可以是一个复杂的结构控制流程不同程序设计语言中条件一旦被激活，就严格地从一个前提向其结论传递产生式系统中满足前提条件的规则被激活后，不一定被立即执行，能否执行将取决于推理机的冲突消解策略2、产生式表示优点自然性好， “ If...then” 的形式与人类的判断性知识基本一致,便于推理；便于引入各种启发式知识格式固定，形式简单，规则间相互独立，便于统一处理，模块性好缺点推理效率低下难以表现规则间的关系，难以表现结构和层次关系专家系统基础专家系统(Expert S ystem, ES )就是能像人类专家一样解决困难、复杂的实际问题的计算机系统专家系统的四个要素：(1)应用于某专门领域⑵拥有专家级知识3)能模拟专家的思维和推理4)能达到专家级水平专家系统基础专家系统是靠知识和推理来解决问题( 不像传统软件系统使用固定的算法来解决问题) ，所以，专家系统是基于知识的智能问题求解系统专家系统则强调知识与推理的分离， 因而系统具有很好的灵活性和可扩充性。

专家系统一般具有解释功能，即在运行过程中一方面能回答用户提出的问题, 另一方面还能对最后的输出( 结论) 或处理问题的过程作出解释有些专家系统还具有“ 学习”能力，即不断对自己的知识进行扩充、完善和提炼专家系统基础系统结构知识库：推理机：动态数据库：人机界面：解释模块：知识库管理模块：第二次实验报告利用产生式规则构建一个简单的专家系统题 目 自 拟 （ 选择、电脑选择、玉石选择. . . .）要求：1、确定推理方法（ 正向还是反向） ，并根据问题设计实现一个简单的不通用推理机（ 匹配、冲突消解）2、规则库要求至少包含15条规则3、初始事实可以任意给定，输入初始事实后能够得到推理结果4、设计人机界面，解释模块提供查询规则的功能5、可以不考虑知识库管理模块6、提交实验报告，实验名称为：基于回溯推理的小型专家系统7、报告中要有推理树3、语义网络3、语义网络语义网络J.R .Quillian 1968年在他的博士论文中作为人类联想记忆的一个显式心理学模型最先提出西蒙1972在自然语言理解中采用了语义网络表示通过概念及其语义关系来表达知识的一种网络图是一种对自然语言概念体系的总体表述3、语义网络语义基元一以有向图表示的三元组结点A 、B 代表实体，表示事物、对象、概念、行为、性质、状态等有向弧R 表 示 A 、 B 之间的某种语义联系， 方向体现了结点的主次关系，A 为主结点， B 为辅结点3、语义网络3、语义网络3、语义网络3、语义网络3、语义网络基本语义关系Is-a 与 part-of 关系描述具有共同属性的不同实体间的分类关系Is-a表示一个实体是另一个实体的实例，表示具体与抽象的关系，其属性具有继承性如：“ 卡拉”是 条 “ 狗”中，卡拉是狗的一个实例，因而卡拉继承了狗的全部属性Part-of表示一个实体是另一个实体的组成部分, 表示部分与整体的关系，其属性不具有继承性如：“ 轮胎”是 “ 汽车”的一部分，但轮胎无法继承汽车的属性3、语义网络3、语义网络属性关系描述实体与其属性之间的关系Have表示一个实体具有另一个实体的属性如：“ 鸟”有 “ 翅膀” ，“ 国庆节”有 “ 阅兵仪式”A kind of, 一个实体是另一个实体的一种类型，属性具有继承性，与Is・ a不同的是，可能出现变异如：“ 鸭嘴兽”属 于 “ 哺乳动物” ，鸭嘴兽继承了哺乳动物的属性，鸭嘴兽属于卵生，这是哺乳动物所不具备的Can表示一个实体具有另一个实体所描述的能力如：草鱼吃水草，3、语义网络3、语义网络3、语义网络其他关系位置关系Located-on 在 •••之上Located-under 在 . . . 之下Located-inside 在 … 里面Located-outside 在… 外面Located-at 在某个位置3、语义网络3、语义网络相近关系Near t o接近关系Similar to相似关系时间关系Before 一个实体的事件在另一个实体的事件之前发生After 一个实体的事件在另一个实体的事件之后发生3、语义网络3、语义网络谓词逻辑到语义网络的转换一元谓词C(x)C和x的含义分别为两个实体，弧表示二者的关系Fruit(apple)谓词含义为苹果是一种水果Class(Zhangsan)谓词含义为张三在上课3、语义网络多元谓词C(x,y)Score(AC,Inter,0:1 )谓词含义为AC米兰和国际米兰在一场比赛中踢成0: 1Tired(barefoot, field, chase(dragonfly))谓词含义为赤脚在田里追蜻蜓追到累了3、语义网络根据自然语言建立语义网络分析自然语言，找出其中的实体，用节点表示分析实体间的语义关系，用有向弧表示1、张三在上java课实体：张三、上课、java关系：状态与课程名2、语义网络是一种知识表示方法实体：语义网络、方法、知识表示关系：类属与用途3、语义网络3、XXX,你妈妈喊你回家吃饭实体：XXX、妈妈、吃饭、回家、找人关系：逐一分析4、旅客交通方式选择行为的计算机模拟方法实体：方法、模拟、计算机、行为、旅客、交通方式、选择关系：逐一分析3、语义网络常见的错误1、表示不完全，部分实体没有进行表示2、 自行添加不需要的实体3、改变语义例：张三是李四的老师3、语义网络语义网络的推理继承把对事物的描述从类结点传递到实例结点通常是沿着is-a或 者 a-kind-of等弧继承3、语义网络常用继承关系(X a kind of Y) and (Y a kind of Z) - X a kind of Z麻 雀 a kind of 鸟， 鸟 a kind of 动物 —麻 雀 a kindo f 动物(X is-a Y) and (Y a kind of Z) - X is-a Z卡 拉is-a狗，狗a kind o f动 物 -卡 拉is-a动物(X a kind of Y) and (Y 有属性 Z) -> X 有属性 Z麻 雀a kind o f鸟，鸟 有属性 翅 膀 一麻雀 有属性翅膀3、语义网络(X is-a Y) and (Y有 属 性Z) - X有 属 性Z卡 拉is-a狗，狗 有属性 爱 吃 肉 一卡拉 有属性 爱吃肉(X 有属性 Y) and (Y a kind of Z) -> X 有属性 Z麻雀有属性 爱 吃 小 米 ，小 米a kind o f粮 食 麻 雀有属性爱吃粮食(X有属性 Y) and (Y is-a Z) - X 有 属 性Z鸟 有 属 性 翅 膀 ，翅 膀is-a飞行工具一鸟有属性飞行工具3、语义网络匹配：在语义网络中寻找与待求解问题相符的语义网络模式步骤：根据待求解问题构造语义网络片断，待求解处标记为空将该语义网络片断与知识库中的语义网络进行匹配，匹配成功时，待求解处对应的事实就是问题的解3、语义网络张三想应聘银行的软件工程师职位，需要那些技能。

根据待求解问题构造语义网络片断与原语义网络进行匹配得解3、语义网络语义网络与语义网的区别语义网络 Semantic network语义网络是一种知识表示的方法，对自然语言概念体系的总体表述，是建立概念联想脉络的基础是由实体和语义关系组成的有向图来表达知识、 描述语义的语义网 Semantic web1998 年 Tim Berners-Lee 提出 Semantic web 的概念是对未来计算机网络的一种设想这个网络中传递的信息能够被计算机自动理解和处理从功能上看它将是一个能够“ 理解”人类信息的智能网络3、语义网络优点直观地表现了各节点之间的联系体现了人类思维的联想过程， 便于将自然语言转换成语义网络具有广泛的表示范围和强大的表示能力一种结构化的知识表示法缺点推理规则不明了，不能充分保证结论的严格性和有效性一旦结点个数太多，网络结构复杂，推理就难以进行不便于表达判断性知识4、框架表示4、框架表示马文？ 明斯基 M arvin Lee M insky, 1969年获图灵奖，是第一位获此殊荣的人工智能学者“ 哪种知识表示方法是最好的？”1975年 M arvin M insky在 论 文 《 框架知识表示》中提出了框架理论。

它针对人们在理解事物、情境或某一故事时的心理学模型，论述了人们理解问题的一种思想方法4、框架表示框架理论的基本观点人脑中已存储有大量事物的典型情景，这些典型情景是以框架的基本知识结构存储在记忆中的当人面临新的情景时，就从记忆中选择（ 粗匹配） 一个合适的框架这个框架是以前记忆的一个知识空框，而其具体内容依新的情景而改变通过对这个空框的细节加工、修改和补充，形成对新的事物情景的认识而这种认识的新框架又可记忆于人脑之中，以丰富人的知识4、框架表示框架结构框架名称一个框架一般由若干个槽组成，一个槽有一个槽值或者有若千个侧面，而一个侧面又有若干个侧面值槽值和侧面值可以是数值、字符串、布尔值，可以是一个动作或过程，还可以是另一个框架的名字4、框架表示关系：槽值为另一个框架的槽也称为关系，将不同的框架连接起来层级关系：每个框架可以有一个或多个父辈结点，也可以有子节点，通过父一子链表达类属关联每个框架都至少要包含一个父框架其他关系： 框架可以通过槽的值相互关联，把从不同角度收集来的信息相互协调起来4、框架表示框架的一般描述形式如下：〈 框架名〉关系槽 名 1 : 槽 值 1侧 面 名 1 1 : 侧 面 值 111, 侧面值112, . . .侧 面 名 1 2 : 侧 面 值 121, 侧面值122, …槽 名 2 : 槽 值 2侧面名2 1 : 侧面值211, 侧面值 212, ...侧面名2 2 : 侧面值221,侧面值 2 2 2 ,…• • •槽 名 k : 槽 值 k侧面名k l : 侧面值k l l ,侧面值 k l2 ,…侧面名k 2 :侧面值k 21,侧面值 k 2 2 ,…4、框架表示框架名： 计算机槽名（ 关系） 一类属： 〈 办公设备〉槽名（ 关系） 一类型：（ 〈 台式计算机, ，〈 便携计算机〉）缺省值： v 台式计算机,槽名一计算器槽名一存储器槽名一控制器槽名一输入设备槽名一输出设备4、框架表示框架名：台式计算机类属： 〈 计算机〉中央处理器:品牌型号数量价格图形处理器：品牌、型号、数量、价格硬盘：品牌、型号、数量、价格内存：品牌、型号、数量、价格主板：品牌、型号、价格输入设备：键盘：品牌、型号、数量、价格鼠标：品牌、型号、数量、价格显示器：品牌、型号、价格4、框架表示框架名：某台计算机类属： v 台式计算机,cpu:品 牌 : Intel型号：i7 860数量：1价格：2000图形处理器：品牌：蓝宝，型号： 5770, 数量： 1 , 价格:1050硬盘：品牌：希捷，型号：1T B ,数量：1 ,价格：560内存：品牌：海盗船，型号：DDR3 2G ,数量：2 ,价格:660主板：品牌：技嘉，型号：P55A-UD3R ,价格：1300键盘鼠标：品牌：罗技，型号：G1 ,价格：180显示器：品牌：三星，型号：P2250 ,价格：14504、框架表示层次关系，一个框架类属于另一个框架上位框架（ 或父框架） ：描述概念的框架下位框架（ 或子框架） ：描述部分或者实例的框架如：框 架 “ 大学教师”是 框 架 “ 某教师”的上位框架而 框 架 “ 教师”是 框 架 “ 大学教师”的上位框架与之对应框 架 “ 某教师” 是 框 架 “ 大学教师”的下位框架而 框 架 “ 大学教师” 是 框 架 “ 教师”的下位框架继承特性：下位框架可以继承上位框架的某些槽值或侧面值。

4、框架表示附加过程. 对框架内容的修改和维护if-added如果加入过程用于存储和修改槽的值，当新的信息加入槽内时执行该过程，且首先检查给定的项目是否是某槽的合法值；if-deleted如果删除过程从槽中删除信息时执行if-needed如果需要过程用于控制槽值的检索，当需要某槽之值而该槽为空时，用某种方法产生槽的值4、框架表示框架名： 教师类属：人教师号：工资：If-needed:检查口令123456If-added:检查口令111111框架名：李华类属：教师教师号：10003工资：2500规 则R :检 查 口 令‘ X ’如果 显 示 ‘ 键入口'并且 读入 V并且 'X，= 'Y ，4、框架表示框架的表达能力框架适合表达结构性的知识概念、对象等知识最适于用框架表示框架的槽就是对象的属性或状态，槽值就是属性值或状态值框架还可以表示行为（ 动 作 ） ，有些过程性事件或情节也可用框架网络来表示4、框架表示产生式规则也可用框架表示例如：产生式规则如果头痛且发烧，则患感冒框架表示可为：框架名：诊 断 1类属：v诊断〉前提：条 件 1 : 头痛条 件 2 : 发烧结论：患感冒框架系统可以看作一类特殊的语义网络，其表示能力更强4、框架表示例：写出大学教师的框架知识表示，要求写出三层框架，并包含一个实例框架，每个框架至少有5 个槽，某个槽要有多个侧面框架名：大学教师类属：v教师,基本资料：姓名：性别：年龄：学历：（ 学士，硕士，博士）缺省值：博士取称：（ 助教，讲师，副教授，教授）缺省值：助教学校：〈 某大学〉学院：V 学院》专业：V 专业〉研究方向：4、框架表示框架名： 教师类属： 〈 知识分子〉类型：（ V 大学教师, ，〈 中学教师, ， 〈 小学教师） ）缺省值： 〈 大学教师〉工作： （ 教学，科研，综合） 缺省值：综合性别：（ 男，女） 缺省值：男年龄：（ 0・ 100）学历：（ 学士，硕士，博士）职称：（ 高级，中级，初级）4、框架表示框架名：某大学教师类属：〈 大学教师〉基本资料姓名：张三性别：男年龄：35学历： 博士职称： 讲师学校：〈 长安大学〉学院： 〈 信息工程学院〉专业： 〈 计算机〉研究方向：人工智能4、框架表示框架名：长安大学类属：v 大学,缺省值：博士缺省值：高级类型：综合性大学学院数：20专职教师人数：约 1700教授：257副教授:584人博士生导师: 约100人科研机构：博士后流动站：6博士点：46硕士点：96学生人数：29000本科生：23000研究生：6000位置：陕西省西安市4、框架表示框架表示下的推理继承：子框架可以拥有其父框架的槽及其槽值。

实现继承的操作有匹配和填槽匹配：就是问题框架同知识库中的框架的模式匹配如果匹配成功，就可获得有关信息填槽：就是沿着框架间的纵向和横向联系，为待求解框架的槽赋值问题框架， 求解某个问题时， 先把问题用一个框架表示出来,然后与知识库中的已有框架进行匹配4、框架表示框架名：企 业1类属：v企业,企业：v行 业1>规模：大部门数：若干核心部门：研发，市场员工数：若干地址：o o O O4、框架表示框架名：新毕业生类属：V 员工,企业：〈 企 业1>部门：（ 研发、市场、售后、总办、人事、后勤）年龄：性别：职务：工程师主管上级：导师：目标：〈 融入部门〉行为准则：4、框架表示框架名：融入部门类属：〈 融入企业〉企业：v企 业 1>行业：〈 行业部门：（ 研发、市场、售后、总办、人事、后勤）部门主管：人事情况：人 员 1:人 员 2:• • •考核指标：指 标 1:指 标 2:♦ • •行为准则：主动性要求：人际关系：自我保护：4、框架表示问题1 : 某个新毕业生是否在该企业的核心部门?建立该毕业生的框架；继承其父框架〈 新毕业生〉 的槽与槽值；空槽填值；在框架〈 企 业 1 ＞ 中查找其核心部门；匹配；问题2 : 某个新毕业生如何能够尽快地融入企业建立该毕业生融入部门的框架；继承其父框架〈 新毕业生〉与 〈 融入部门〉 的槽与槽值；空槽填值；查找其行为准则4、框架表示框架系统的结构图表示将若干的框架按照其关系联结起来可以看作一种特殊的语义网络4、框架表示4、框架表示框架表示法的优缺点优点与人类的思维和问题求解过程相似表达能力强，层次结构丰富，能够有效的组织知识可以利用过去获得的知识对未来的情况进行预测，因此可以通过框架来认识某一类事物缺点难以保证问题求解的可行性和推理过程的严密性许多实际情况与原型存在较大的差异，适应能力不强各子框架的数据结构如果不一致，会造成推理的困难。

5、其它表示方法5、其它表示方法脚本知识表示过程性知识表示直接知识表示5、其它表示方法脚本知识表示将知识以剧本的形式按照一定顺序表示一般由开场条件、角色、道具、场景、尾声等几部分组成开场条件：该系统所描述的事件发生的条件角色：该系统中事件的主体道具：事件动作的对象或者工具场景：描述事件中各个独立发展的过程尾声：描述事件的结果5、其它表示方法病人去医院看病的脚本知识表示开场条件病人生病了病人需要医生治疗病人能够去医院看病，经济、身体条件角色病人医生护士5、其它表示方法道具医院挂号室诊室椅子桌子处方单收费处钱缴费单药房药品5、其它表示方法场 景1进入医院病人进入医院在挂号室挂号病人在诊室门口排队等候治疗场景2诊断病人进入诊室病人向医生诉说症状医生进行诊断医生向病人解释病情医生填写处方单5、其它表示方法场景3缴费病人来到收费处排队病人递交处方单收费处划价病人缴费病人取回处方单、缴费单和找零5、其它表示方法场景4 取药病人来到药房排队递交药方和缴费单药方备药病 人 药场景5 离开病人离开医院5 、其它表示方法结果病人得到了诊断病人得到了药品病人支付了费用医生付出了劳动医院销售了药品5 、其它表示方法脚本的推理必须满足开场条件必须严格按照场景的发生顺序进行推理脚本表示的特点脚本适用于描述结构固定，并且按照严格先后顺序进行的过程表示范围比较狭窄5 、其它表示方法过程性知识表示陈述性知识表示：关于事实、判断、原因等知识的静态描述过程性知识表示：关 于 “ 怎么办”的，隐藏在某个具体过程中的知识。

过程性知识的分类解决某个具体问题的过程步骤如：各种流程客观事物的发展过程如：某种植物生长过程5 、其它表示方法过程性知识表示的结构激发条件描述某个过程的触发条件推理操作按照事先规定的步骤执行推理或者操作结束给出结果5 、其它表示方法过程知识表示：深度优先搜索算法激发条件：给定网络图给定初始节点目标：搜索满足某种条件的节点推理操作步骤：步 1 : 将初始节点置入待搜索节点集合步 2 : 取第一个待搜索节点，搜索其第一个子节点，如果没有子节点，则转步4;步 3 : 检查该节点是否为目标节点，若是则结束；否则将该节点前插入待搜索节点集合，转步2;步 4 : 从待搜索集合中删除第一个节点，转步2;结束：输出搜索结果和搜索路径5 、其它表示方法过程知识表示：毕业生应聘过程激发条件：毕业生，企业招聘推理操作步骤：步 1 : 自我评判与预期爱好： 自己喜欢做什么特长： 自己擅长做什么，需求：最可能找到什么样的工作5 、其它表示方法步 2 : 制作简历1 : 注重特色，不要千篇一律2 : 简历的风格要朴实3 : 简历需要有一定的篇幅，不要只是一页纸4 : 可以根据不同的应聘对象的特点作一些修改步 3 : 投递简历网上投递招聘会投递5 、其它表示方法步 4 : 参加笔试注意事先准备步5 :参加面试1、事先准备2、衣着正式得体3、回答问题表现自己负责、努力、乐观、认同企业文化避免表现自己的缺陷如果实在回答不出来结束：应聘成功或者失败5 、其它表示方法过程性知识表示的特点：优点知识库与推理机合一，表示效率高明确地表示了时间上的先后顺序便于加入启发式规则缺点难以维护，不易添加和修改不易于理解5 、其它表示方法直接表示方法知识表示就是将知识转化为计算机能够接受并处理的形式直接表示方法希望“ 便于人类理解和操作”难点在于计算机如何实现和处理各种模式识别技术使直接表示成为可能计算机无法完全替代人类，因此由计算机自主决策转向计算机辅助人类推理决策5 、其它表示方法典型的直接表示方法文字语音图像本章重点1、产生式规则、正向推理、逆向推理及其匹配过程2、语义网络，能够用语义网络进行知识表示3、框架，能够用框架进行知识表示 。