同等学力申请硕士学位人工智能课件

1、同等学力申请硕士学位人工智能同等学力申请硕士学位人工智能2人工智能的主要内容概述表示知识表示推理确定性推理非确定性推理搜索系统专家系统学习机器学习数据挖掘理解自然语言理解优化人工神经网络遗传算法4人工智能的主要内容概述31. 概述大纲：了解人工智能的提出、几种智能观和主要研究领域。掌握人工智能求解方法的特点。1.1 什么是人工智能1.2 认识智能的不同观点1.3 人工智能求解方法的特点1.4 人工智能的主要研究途径1.5 人工智能的研究和应用领域51. 概述大纲：了解人工智能的提出、几种智能观和主要研究领41.1 什么是人工智能定义：人工智能是用人工的方法在机器（计算机）上实现的智能定义：人工

2、智能学科研究如何制造出人造的智能机器或系统，来模拟人类智能活动的能力，以延伸人们智能的科学。1956年夏季在美国Dartmouth大学举行了一次为期两个月的夏季学术研讨会。并由MacCarthy提议正式采用了“人工智能”这一术语。61.1 什么是人工智能定义：人工智能是用人工的方法在机器（51.2 认识智能的不同观点思维理论：智能来源于思维活动人的一切智慧或智能都来自于大脑的思维活动，人的一切知识都是思维的产物阈值理论：智能取决于可运用的知识智能就是在巨大的搜索空间中迅速找到一个满意解的能力。进化理论：智能可由逐步进化来实现智能取决于感知和行为，取决于对外界复杂环境的适应，智能不需要知识，不需

3、要表示，不需要推理，智能可以由逐步进化来实现。71.2 认识智能的不同观点思维理论：智能来源于思维活动61.3 人工智能求解方法的特点重视知识智能是需要知识的使用大量的领域知识求解问题使用元知识可以提高控制的层次重视推理注重使用启发式信息求解满意解，而非最优解81.3 人工智能求解方法的特点重视知识71.4 人工智能的主要研究途径符号主义连接主义行为主义91.4 人工智能的主要研究途径符号主义8符号主义 Symbolicism又称逻辑主义（Logicism）或计算机学派（Computerism）基于物理符号系统假设和有限合理性原理的人工智能学派。符号主义认为人工智能起源于数理逻辑，人类认知的基

4、本元素是符号（Symbol），认知过程是符号表示上的一种运算。符号主义者走过了一条启发式算法专家系统知识工程的发展道路，尤其是专家系统的成功开发与应用，使人工智能研究取得了突破性的进展。符号主义一直是人工智能的主流派。“classical AI”, “good-old-fashion AI” 10符号主义 Symbolicism又称逻辑主义（Logic9联结主义 Connectionism仿生学派（Bionicsism)、心理学派（Physiologism）源于仿生学对人脑模型的研究基本思想：思维的基元是神经元，而不是符号；思维过程是神经元的联结活动过程，而不是符号运算过程；人工神经网络感知机

5、（Perceptron)多层网络中反向传播算法（BP网络）Hopfield 网络11联结主义 Connectionism仿生学派（Bioni10行为主义 Actionism又称进化主义（Evolutionism）或控制论学派（Cyberneticsism），基本思想：人工智能起源于控制论，提出智能取决于感知和行为，取决于对外界复杂环境的适应，而不是表示和推理。“控制论动物”的研制和实验:Brooks 的六足行走机器人：基于感知-动作模式的模拟昆虫行为的控制系统。12行为主义 Actionism又称进化主义（Evoluti111.5 人工智能的研究和应用领域专家系统机器学习模式识别自然语言理解机

6、器人学计算机视觉博弈自动定理证明智能决策支持系统知识发现和数据挖掘131.5 人工智能的研究和应用领域专家系统12典型题目：人工智能概述1、人工智能注重启发式算法，因而人工智能程序所期求的解答是（ ）（2002）A精确解 B 普遍解 C满意解5、在诞生初期，人工智能被定义为这样一个计算机科学的分支：它是研究（ ）。人工智能程序与通常意义下的程序比较，它具有以下四个特点：（ ）、（ ）、（ ）、（ ）。（2000）14典型题目：人工智能概述1、人工智能注重启发式算法，因而人13典型题目：人工智能概述人工智能作为一门学科，在（ ）年诞生于（ ）。LISP语言是（ ）提出的。MYCIN的诞生地是（

7、）。（1999）计算机实现智能有些什么观点 ？（2004）15典型题目：人工智能概述人工智能作为一门学科，在（ 142.知识表示大纲：掌握知识表示的概念表示方法：掌握逻辑表示法、产生式、语义网络、框架表示；各种表示方法的优缺点、适宜的应用对象。注意表示与推理的关系。会使用知识表示方法对某一具体场景给出表示2.1 知识表示的概念2.2 一阶谓词逻辑表示法2.3 产生式表示法2.4 语义网络表示法2.5 框架表示法162.知识表示大纲：152.1 知识表示的概念2.1.1 知识表示观点陈述性观点Declarative knowledge representation数据结构灵活简洁演绎过程完整而确

8、定系统模块性好工作效率低推理过程不透明，不易理解过程性观点Procedural knowledge representation程序推理过程直接、清晰便于用特殊领域的启发式信息工作效率较高灵活性差对知识的维护不方便172.1 知识表示的概念2.1.1 知识表示观点陈述性观点162.1.2 知识表示的要求1）表示能力一是知识表示范围的广泛性；二是领域知识表示的高效性；三是对非确定性知识表示的支持程度。2）可利用性包括对推理的适应性和对高效算法的支持性。3）可组织性与可维护性4）可实现性5）自然性与可理解性182.1.2 知识表示的要求1）表示能力17知识的表示方法从四个方面学习：概念：什么是？（

9、注意其涵盖的范围）方法：如何用来表示知识（注意几个细节）推理：如何进行推理？特点：19知识的表示方法从四个方面学习：182.2 一阶谓词逻辑表示法2.2.1一阶谓词概念命题(proposition)：一个陈述句称为一个断言。凡有真假意义的断言称为命题。在谓词逻辑中，命题是用谓词(Predication)来表示的。 设D是个体域，P：Dn T，F是一个映射，其中 Dn =(x1,x2,xn)|x1,x2,xnD如果xi都是个体常量、变元或函数，称它为一阶谓词如果某个xi本身又是一个一阶谓词，则称它为二阶谓词范围：本次考试仅包含一阶谓词！202.2 一阶谓词逻辑表示法2.2.1一阶谓词概念范围：本

10、192.2.1一阶谓词概念谓词公式的解释命题公式的一个解释就是对该命题公式中各个命题变元的一次真值指派。合式公式通过连接的原子谓词也可以含有量词212.2.1一阶谓词概念202.2.2 谓词逻辑表示方法 1）定义谓词注意定义变量的取值范围2）用谓词把知识表示为合式公式细节知识注意“”的使用注意量词的使用： 全称量词， 存在量词注意括号的匹配222.2.2 谓词逻辑表示方法 1）定义谓词21例 用谓词逻辑表示如下知识： 王宏是计算机系的一名学生。 李明是王宏的同班同学。 凡是计算机系的学生都喜欢编程序。1) 定义谓词： COMPUTER(x)：x是计算机系的学生。 CLASSMATE(x, y)

11、：x是y的同班同学。 LIKE(x, y)：x喜欢y。2) 可用谓词公式把上述知识表示为： COMPUTER (Wanghong). CLASSMATE (Liming, Wanghong). (x)( COMPUTER(x) LIKE(x, programing).23例 用谓词逻辑表示如下知识： 王宏是计算222.2.3 谓词逻辑表示的特点优点缺点自然：接近自然语言形式知识表示能力差：不能表示非确定性知识明确：可以按照一种标准解释知识库管理困难：缺乏知识的组织原则精确：二值逻辑存在组合爆炸：难以表示启发性知识灵活：知识和知识处理分开系统效率低：推理演算与知识含义分开，抛弃了语义信息，往往使

12、推理过程冗长模块化：各条知识相对独立242.2.3 谓词逻辑表示的特点优点缺点自然：接近自然语言232.3 产生式表示法2.3.1 什么是产生式表示产生式：在自然界的各种知识单元之间存在着大量的因果关系, 这些前提和结论的关系, 用一种“如果, 则”(if then )形式的规则(产生式)来表示产生式系统：把一组产生式放在一起, 让它们互相配合, 协同作用, 一个产生式生成的结论可以供另一个产生式作为前提使用, 以这种方式求得问题的解决, 这就叫产生式系统产生式系统可以算作是一种演绎系统。252.3 产生式表示法2.3.1 什么是产生式表示242.3.2 用产生式方法表示知识事实的表示雪是白的

13、(Snow， Color， White) 王峰热爱祖国(Love，Wangfeng，Country）（对象，属性，值）三元组（关系，对象1，对象2） 三元组（对象，属性，值，可信度因子） 四元组规则的表示PQ IF P THEN Q （置信度）262.3.2 用产生式方法表示知识事实的表示25细节知识：产生式与蕴含式的区别1）蕴含式只能表示确定性知识，其真值只能取真或假，而产生式还可以表示不确定性知识。2）已知事实是否与前提的匹配，产生式系统中的匹配可以是精确的，也可以是不精确的。而谓词逻辑中的蕴含式，其匹配则要求一定是精确的。 27细节知识：262.3.3 产生式系统产生式系统的基本结构 控

14、制系统规则库综合数据库282.3.3 产生式系统产生式系统的基本结构 控制系统综合272.3.3 产生式系统的基本过程初始化综合数据库，把问题的已知事实送入综合数据库中若知识库中不再有未使用规则，说明该问题无解，终止问题求解过程（失败）。 检查规则库的未使用规则中是否存在有其前提可与综合数据库中已知事实相匹配的规则，若有则从中选择一个；否则转（6）。执行当前选中规则，并对该规则作上标记，把执行该规则后所得到的结论作为新的事实放入综合数据库；如果该规则的结论是一些操作，则执行这些操作。292.3.3 产生式系统的基本过程初始化综合数据库，把问题28检查综合数据库中是否包含了该问题的解，若已包含，

15、问题求解过程结束（成功）；否则，转（2）当规则库中还有未使用的规则，但均不能与综合数据库中的已有事实相匹配时，要求用户进一步提供关于该问题的已知事实，若能提供，则转（2）；否则，说明该问题无解，终止问题求解过程。30检查综合数据库中是否包含了该问题的解，若已包含，问题求解29细节知识：产生式系统的类型按推理方向分类正向推理产生式系统逆向推理产生式系统双向推理产生式系统按规则库的性质及结构分类可交换的产生式系统可分解的产生式系统可恢复的产生式系统31细节知识：产生式系统的类型302.3.4 产生式表示方法的特点优点缺点直观性：IFTHEN效率较低：匹配一冲突消解一执行模块性:产生式规则是最基本的

16、知识单元有效性：可以表示不确定性知识一致性：规则格式相同，综合数据库可被所有规则访问不能表示结构性知识322.3.4 产生式表示方法的特点优点缺点直观性：IF312.4 语义网络表示法2.4.1 什么是语义网络语义网络是一种用实体及其语义关系来表达知识的有向图三元组：（结点1，弧，结点2）雪白色颜色ABinfer鸵鸟鸟是一种332.4 语义网络表示法2.4.1 什么是语义网络雪白色颜322.4.2 重要的语义关系1）类属关系：分类关系、成员关系或实例关系类属关系的一个最主要特征是属性的继承性，处在具体层的结点可以继承抽象层结点的所有属性。鸟类动物A-Kind-of分类关系张强共青团A-Memd

17、er-of成员关系李刚 人is-a实例关系342.4.2 重要的语义关系1）类属关系：分类关系、成员关332.4.2 重要的语义关系2）包含关系: 部分与整体之间的关系它和类属关系的最主要区别是包含关系一般不具备属性的继承性。黑板墙Part-of包含关系大脑人体Part-of包含关系352.4.2 重要的语义关系2）包含关系: 部分与整体之间342.4.2 重要的语义关系3）属性关系：事物和其属性之间的关系鸟飞Can属性关系鸟翅膀Have属性关系362.4.2 重要的语义关系3）属性关系：事物和其属性之间352.4.2 重要的语义关系澳门回归香港回归After4) 时间关系书桌子Located

18、-on5) 位置关系猫虎Similar-to6) 相似关系成绩好学习努力 infer7) 推论关系372.4.2 重要的语义关系澳门回归香港回归After4)36概念结点概念结点2.4.3 特殊类型结点1）概念结点李新的自行车是永久牌、蓝色、26型。王红的自行车是金狮牌、红色、24型26型永久 自行车1 李新蓝色 自行车 交通工具 自行车2 红色24型金狮人 王红是一个是一个所有者所有者车型车型品牌品牌是一个是一种颜色实例结点实例结点38概念结点概念结点2.4.3 特殊类型结点1）概念结点李新372.4.3 特殊类型结点2）情况结点燕子巢春天秋天情况鸟鸟窝时间小燕子占有权占有者是一种是一种是一

19、种是一种是一种是一种占有资格是一只占有物开始于结束于小燕子从春天到秋天占有一个巢情况结点392.4.3 特殊类型结点2）情况结点燕子巢春天秋天情况鸟382.4.3 特殊类型结点3）事件和动作结点常河给江涛一张磁盘一张磁盘常河江涛主体客体2给客体1一张磁盘常河江涛主体客体2客体1给给予事件动作动作结点事件结点402.4.3 特殊类型结点3）事件和动作结点常河给江涛一张392.4.3 特殊类型结点比赛篮球赛东方大学神州大学85：89是一种结局客队主队篮球赛事件结点神州大学和东方大学两校篮球队在东方大学进行一场比赛，结局的比分是85：89412.4.3 特殊类型结点比赛篮球赛东方大学神州大学85：4

20、02.4.4 语义网络的推理方式1继承指把对事物的描述从抽象结点传递到具体结点。通过继承可以得到所需结点的一些属性值，它通常是沿着Is-A、A-Kind-of等继承弧进行的。2匹配在知识库的语义网络中寻找与待求解问题相符的语义网络模式422.4.4 语义网络的推理方式1继承41Animal Breathe Skin Move cancanhasBirdFly Wings featherscanhashasFish CanarySing yellowcancolorOstrich Fly tall cannotisIs AIs AIs AIs A2.4.4 语义网络的推理方式Can a cana

21、ry sing?Can a canary fly?Can a ostrich breathe?43Animal Breathe Skin Move can422.4.5 语义网络表示法的特点优点缺点结构性：事物间的各种语义联系非严格性：含义完全依赖于处理程序对它所进行的解释联想性：作为人类联想记忆模型复杂性：表示知识的手段多表示形式不一致自索引性：通过连接结点的弧可以找出该结点有关的信息，避免组合爆炸问题自然性：自然语言与语义网络442.4.5 语义网络表示法的特点优点缺点结构性：事物间的432.5 框架表示法2.5.1 什么是框架把有关于某个概念的所有相关信息组织在一起就构成一个框架。在框架

22、理论中，框架是知识的基本单位，把一组有关的框架连接起来便可形成一个框架系统。在框架系统中，系统的行为由该系统内框架的变化来实现，系统的推理过程由框架之间的协调来完成452.5 框架表示法2.5.1 什么是框架44槽名1侧面名1 值1, 值2侧面名2值1, 值2槽名n侧面名1 值1, 值2侧面名m 值1, 值2约束约束条件1约束条件t46槽名1侧面名1 值1, 值2侧面名2值1, 45 框架名：（硕士生） 姓名: 单位（姓，名） 性别：范围（男，女） 默认：男 年龄：单位（岁） 条件：岁16 学习专业：单位（专业名） 研究方向：单位（方向名） 导师姓名：单位（姓，名） 参加课题：范围（国家级，省

23、部级，其他） 默认：国家级 学籍：（硕学籍） 住址：单位（楼号，房间号） 电话：单位（ （区号），话机号） 入学时间：单位（年，月） 学制：单位（年） 默认：3年“单位”指定槽值的格式；“范围”说明槽值限制在指定的范围内；“条件”说明槽值应该满足的限制条件“（）”表示是框架名“默认”说明当相应槽没填入槽值时以其默认值作为该槽的槽值47 框架名：（硕士生） 姓名46对于一个框架，当把具体信息填入其槽或侧面后，就得到一个该框架的实例框架。框架名： 姓名：杨叶 性别：女 年龄：23 学习专业：计算机应用技术 研究方向：人工智能 导师姓名：林海 参加课题： 学籍：（硕学籍-1） 住址：16号楼316房

24、间 电话：（010）66668888 入学时间：2000年9月 学制：48对于一个框架，当把具体信息填入其槽或侧面后，就得到一个该47细节知识：特殊槽值Ifneeded：如果需要在不可能提供统一缺省值的情况下，提供计算函数或推理过程来产生一个槽值Ifadded：如果必要在给类的某个体的属性进行修改时，提供提供计算函数或推理过程进行必要的后续处理49细节知识：特殊槽值482.5.2 预定义槽名1）is-a槽2）AKO槽3）subclass槽上述3种槽指出事物间在抽象概念上的类属关系4）Instance槽5）partof 槽6）infer糟7）possiblereason 槽8）similar 槽

25、502.5.2 预定义槽名1）is-a槽492.5.3 用框架表达知识问题求解主要是通过对框架的匹配与填槽来实现512.5.3 用框架表达知识502.5.4 框架表示法的特点优点缺点结构性：可以表达各个框架之间纵向和横向关系缺乏框架的形式理论深层性：通过继承关系、因果关系等组织深层关系缺乏过程性知识表示继承性：自然性：自然语言522.5.4 框架表示法的特点优点缺点结构性：可以表达各个51典型题目：知识的表示1、开发专家系统所要解决的基本问题有三个，那就是知识的获取，知识的表示和（ ）；知识的表示的方法主要有（ ），（ ），（ ）和（ ）。 （2001）2、常用的知识表示方法有逻辑表示法、（

26、）、（ ）、（ ）、（ ）等。 （1999）3、建造专家系统常用的知识表示方法是（ ）（2006）。A. 逻辑法 B.语义网 C. 产生式53典型题目：知识的表示1、开发专家系统所要解决的基本问题有52典型题目4、语义网络是（ ）表示的结点1，有向弧，结点2 三元式连接而成的。其结点表示（ ），其弧表示（ ）。（2001）5、语义网络表达知识时，有向弧AKO链、ISA链时用来表达结点知识的（ ）（2002）A无悖性 B 可扩充性 C 继承性6、语义网络中，为了进行节点（结点，node）间节点属性的集成推理，规定了两个约定俗成的链（弧，arc），命名为（ ）和（ ），用来标明类与子类、类与个体之

27、间的关系。（2000）54典型题目4、语义网络是（ ）表示的53典型题目7、产生式规则与蕴涵规则的区别在于产生式规则（ ），而蕴涵规则（ ）。（2002）8、产生式规则与蕴涵规则的区别在于：产生式规则（ ），而蕴涵式（ ）。 （2000）9、给出框架表示的一般形式（2004）55典型题目7、产生式规则与蕴涵规则的区别在于产生式规则（ 54四（9分）用框架表示下述地震事件（2001）【虚拟新华社3月15日电】昨日，在云南玉溪地区发生地震，造成财产损失约10万元，统计部门如果需要详细的损失数字可电询62332931。另据专家认为震级不会超过4级，并认为地处无人区，不会造成人员伤亡。56四（9分）用

28、框架表示下述地震事件（2001）55三、用框架表示下述风灾事件（2000）【虚拟新华社9月16日电】国家气象局命名的“61年2号”台风于昨日下午4时在浙江舟山地区登陆。据专家经验，认为风力大于等于8级。但风力中心的准确值，有待数据处理，目前尚未发布。此次台风造成的损失，尚未得到报告。若需要详细的损失数字，可电询自然灾害统计中心。另据国家气象局介绍说，是前曾经得到国际气象组织的预报：昨日上午于太平洋赤道地区生成高压气旋，将向北移动，于浙江登陆。依照国际惯例将其命名为“Carla”飓风，我国也予以承认。至于“Calar”是否就是登陆的“61年2号”，尚需另外加以核查。57三、用框架表示下述风灾事件

29、（2000）563. 推理3.1 推理的概念和分类3.2 推理的逻辑基础3.2 归结推理（重点）3.3 不确定推理3.3.1 不确定推理的基本问题3.3.2 可信度方法的计算（重点）3.3.3 主观贝叶斯方法的基本思想3.3.4 证据理论的基本思想583. 推理3.1 推理的概念和分类573.1 推理方法及其分类推理方法主要解决在推理过程中前提与结论之间的逻辑关系，以及在非精确性推理中不确定性的传递问题。3.1.1 推理方法的分类1) 按推理的逻辑基础分类演绎推理归纳推理默认推理593.1 推理方法及其分类推理方法主要解决在推理过程中前58（1）演绎推理一般个别:从已知的一般性知识出发，去推出

30、蕴含在这些已知知识中的适合于某种个别情况的结论。核心是三段论：由一个大前提、一个小前提和一个结论三部分组成的。例如：计算机系的学生都会编程序；程强是计算机系的一位学生；程强会编程序。60（1）演绎推理一般个别:从已知的一般性知识出发，去推出59（2）归纳推理个别一般:从一类事物的大量特殊事例出发，去推出该类事物的一般性结论。基本思想：先从已知事实中猜测出一个结论，然后对这个结论的正确性加以证明确认，数学归纳法就是归纳推理的一种典型例子。如果按照所选事例的广泛性可分为完全归纳推理和不完全归纳推理；如果按照推理所使用的方法可分为枚举归纳推理、类比归纳推理、统计归纳推理和差异归纳推理等。61（2）归

31、纳推理个别一般:从一类事物的大量特殊事例出发，60（3）默认推理默认推理是在知识不完全的情况下假设某些条件已经具备所进行的推理，因此也称为缺省推理。在推理过程中，如果发现原先的假设不正确，就撤消原来的假设以及由此假设所推出的所有结论，重新按新情况进行推理。由于默认推理允许在推理过程中假设某些条件是成立的，这就解决了在一个不完备的知识集中进行推理的问题。62（3）默认推理默认推理是在知识不完全的情况下假设某些条件61（4）演绎推理与归纳推理的区别演绎推理是在已知领域内的一般性知识的前提下，通过演绎求解一个具体问题或者证明一个结论的正确性。它所得出的结论实际上早已蕴含在一般性知识的前提中，演绎推理

32、只不过是将已有事实揭示出来，因此它不能增殖新知识归纳推理所推出的结论是没有包含在前提内容中的。这种由个别事物或现象推出一般性知识的过程，是增殖新知识的过程。63（4）演绎推理与归纳推理的区别演绎推理是在已知领域内的一622）按所用知识的确定性分类确定性推理:是指推理所使用的知识和推出的结论都是可以精确表示的，其真值要么为真，要么为假，不会有第三种情况出现。不确定性推理:是指推理时所用的知识不都是确定的，推出的结论也不完全是确定的，其真值会位于真与假之间。由于现实世界中的大多数事物都具有一定程度的不确定性，并且这些事物是很难用精确的数学模型来进行表示与处理的，因此不确定性推理也就成了人工智能的一

33、个重要研究课题642）按所用知识的确定性分类确定性推理:是指推理所使用的知633）按推理过程的单调性单调性：推理过程所得到的结论是否越来越接近目标单调推理：是指在推理过程中，每当使用新的知识后，所得到的结论会越来越接近于目标，而不会出现反复情况，即不会由于新知识的加入否定了前面推出的结论，从而使推理过程又退回到先前的某一步。非单调推理：是指在推理过程中，当某些新知识加入后，会否定原来推出的结论，使推理过程退回到先前的某一步。非单调推理往往是在知识不完全的情况下发生的。在这种情况下，为使推理能够进行下去，就需要先作某些假设，并在此假设的基础上进行推理。但是，当后来由于新的知识加入，发现原来的假设

34、不正确时，就需要撤销原来的假设以及由此假设为基础推出的一切结论，再运用新知识重新进行推理653）按推理过程的单调性单调性：推理过程所得到的结论是否越643.1.2 推理的控制策略及其分类由于智能系统的推理过程一般表现为一种搜索过程，因此，推理的控制策略又可分为推理策略和搜索策略。推理策略主要解决推理方向、冲突消解等问题，如推理方向控制策略、求解策略、限制策略、冲突消解策略等；搜索策略主要解决推理线路、推理效果、推理效率等问题。按照推理方向，分为正向推理、逆向推理、混合推理及双向推理；求解策略是指仅求一个解，还是求所有解或最优解等。限制策略是指对推理的深度、宽度、时间、空间等进行的限制。冲突消解

35、策略是指当推理过程有多条知识可用时，如何从这多条可用知识中选出一条最佳知识用于推理的策略663.1.2 推理的控制策略及其分类由于智能系统的推理过程653.2 推理的逻辑基础3.2.1 谓词公式的解释设D是谓词公式P的非空个体域，若对P中的个体常量、函数和谓词按如下规定赋值称这些指派为P在D上的一个解释：1）为每个个体常量指派D中的一个元素；2）为每个n元函数指派一个从Dn到D的一个映射，其中 Dn (x1,x2,xn)|x1,x2,xn D3）为每个n元谓词指派一个从Dn到T,F的映射673.2 推理的逻辑基础3.2.1 谓词公式的解释663.2.2谓词公式的永真性与可满足性如果谓词公式P对

36、非空个体域D上的任一解释都取得真值T(F)，则称P在D上是永真(假)的；如果P在任何非空个体域上均是永真的，则称P永真(假) 。永假性又称不可满足性或不相容性。对于谓词公式 P，如果至少存在D上的一个解释，使公式P在此解释下的真值为T，则称公式 P在D上是可满足的。谓词公式的可满足性又称为相容性.683.2.2谓词公式的永真性与可满足性如果谓词公式P对非空67谓词公式的等价性与永真蕴含性设P与Q是D上的两个谓词公式，若对D上的任意解释，P与Q都有相同的真值，则称 P与Q在D上是等价的。如果D是任意非空个体域，则称 P与Q是等价的，记作P Q。常用的等价式：1）双重否定率 P P2）交换率 PQ

37、 QP， PQ QP3）结合率 (PQ)R P(QR), (PQ)R P (QR)4）分配率 P(QR) (PQ)(PR) P(QR) (PQ)(PR)69谓词公式的等价性与永真蕴含性设P与Q是D上的两个谓词公式68谓词公式的等价性与永真蕴含性(5)狄摩根定律 (PQ) P Q (PQ)P Q(6)吸收率 P(PQ) P， P(P Q) P(7)补余率 PP T , P P F(8)连词化归率 PQ P Q , P Q (PQ) (QP) (9)量词转换率 (x)P (x)(P) (x)P (x)(P)(10)量词分配率 (x)(PQ) (x)P(x)Q (x)(PQ) (x )P(x )Q7

38、0谓词公式的等价性与永真蕴含性(5)狄摩根定律 (69谓词公式的等价性与永真蕴含性对谓词公式 P和 Q，如果 PQ永真，则称 P永真蕴含 Q，且称 Q为 P的逻辑结论，P为Q的前提，记作P=Q。常用的永真蕴含式： （1）化简式 PQ = P， PQ =Q （2）附加式 P = PQ， Q = PQ （3）析取三段论 P，P V Q = Q （4）假言推理 P，PQ = Q （5）拒取式 Q，P Q = P （6）假言三段论 P Q，Q R = P R 71谓词公式的等价性与永真蕴含性对谓词公式 P和 Q，如果 70谓词公式的等价性与永真蕴含性常用的永真蕴含式： （7）二难推理 P Q，P R，

39、Q R = R （8）全称固化 （ x）P（x） = P（y） 其中，y是个体域中的任一个体， （9）存在固化 （ x）P（x） = P（y） 其中，y是个体域中某一个可以使P（y）为真的个体其他推理规则： （1）P规则，T规则，CP规则 （2）反证法： Q为P的逻辑结论，当且仅当P Q是不可满足的。 72谓词公式的等价性与永真蕴含性常用的永真蕴含式：713.2.3谓词公式的范式范式是公式的标准形式，公式往往需要变换为同它等价的范式，以便对它们作一般性的处理。在谓词逻辑中分为两种：前束范式：量词在谓词公式的前面Skolem范式：存在量词都在全称量词之前例如：(x)(z)(y)(P(x)Q(y,

40、 z) R(x，z)任一谓词公式均可化为与其对应的Skolem范式733.2.3谓词公式的范式范式是公式的标准形式，公式往往需72置换(Substitution)：在一个谓词公式中用置换项去替换变量。置换是形如 t1/x1,t2/x2,tn/xn 的有限集合。ti/xi表示用ti置换xi。要求:ti与xi不能相同，要求:xi不能循环地出现在另一个ti中E.g.a/x, c/y, f(b)/z 对 g(y)/x, f(x)/y 错 g(a)/x, f(x)/y 对合一可以简单地理解为是寻找项对变量的置换，使两个谓词公式一致3.2.4 置换与合一74置换(Substitution)：在一个谓词公式

41、中用置换733.3 归结演绎推理大纲搞清推理思路：采用反演法来证明定理ABHerbrand 定理：归结法的完备性建立在Herbrand 定理之上归结演绎推理是一种基于鲁宾逊(Robinson)归结原理的机器推理技术。鲁宾逊归结原理亦称为消解原理, 是鲁宾逊于1965年在海伯伦(Herbrand)理论的基础上提出的一种基于逻辑的“反证法”。在人工智能中, 几乎所有的问题都可以转化为一个定理证明问题。其实质是要对前提 P和结论 Q, 证明 PQ永真。753.3 归结演绎推理大纲743.3.1 归结演绎推理P Q P QP Q 永真 (P Q) 永假( P Q)永假 P Q永假P Q P1 P2 P

42、nP1 P2 Pn NIL问题:1. 如何转换?2. 如何判断一个公式与NIL等价 ?763.3.1 归结演绎推理P Q P 753.3.2 如何转换?1. 基本概念:文字: 单个谓词及其否定形式P(x), P(x)子句: 通过析取连接的谓词P(x) Q(y), P(x, f(x) Q(x, g(x)空子句(Nil): 没有任何谓词子句集：子句 + Nil773.3.2 如何转换?1. 基本概念:763.3.2 如何转换?(C1)(1) 删除连接符号 “” 和 “”PQ P Q , P Q (PQ) (QP) (P Q) ( P Q)E.g. (x)(y)P(x, y) (y )(Q(x, y

43、) R(x, y) (x)(y)P(x, y) (y)(Q(x, y) R(x, y)(2) 把否定号放在谓词近前 (P) P (PQ) PQ (PQ) PQ (x)P(x) P, (x)P(x) PE.g.(x)(y) P(x, y) (y )( Q(x, y) R(x, y)783.3.2 如何转换?(C1)(1) 删除连接符号 “773.3.2 如何转换?(C2)(3) 标准化：把位于同一个量词辖域内的变量变量更名.E.g. (x)(y) P(x, y) (z )( Q(x, z) R(x, z) (4) 把所有量词都放在公式前面E.g. (x) (y) (z )(P(x, y) ( Q

44、(x, z) R(x, z)(5) 删除存在量词(a) 存在量词不在任何全称量词内: 把相应的变量换成一个常量;(b)存在量词在全称量词内: 把相应的变量换成一个函数;E.g. (x1)(x2)(xn)(y)P(x1, x2, , xn, y)y = f(x1, x2, , xn) Skolem 函数E.g. (x) (P(x, f(x)( Q(x, g(x) R(x, g(x)793.3.2 如何转换?(C2)(3) 标准化：把位于同一783.3.2 如何转换?(C3)(6) 把公式转换为skolem形式(x1)(x2)(xn)M(x1, x2, , xn), M是一个由合取符号连接的几个子

45、句(7) 删除全称量词E.g. P(x, f(x) ( Q(x, g(x) R(x, g(x)(8) 删除合取符号: P(QR) (PQ)(PR)e.g. P(x, f(x) Q(x, g(x) P(x, f(x) R(x, g(x)(9) 必要的化对变量更名e.g. P(x, f(x) Q(x, g(x) P(y, f(y) R(y, g(y)803.3.2 如何转换?(C3)(6) 把公式转换为sko793.3.3 归结反演应用归结原理证明定理的过程称为归结反演。已知F, 证明目标G为真的归结反演过程如下：否定目标公式G, 得 G；把 G并入到公式集F中, 得到 F, G；把F, G化为子

46、句集S；应用归结原理对子句集S中的子句进行归结, 并把每次得到的归结式并入S中。如此反复进行, 若出现空子句, 则停止归结, 此时就证明了G为真。813.3.3 归结反演应用归结原理证明定理的过程称为归结反80PQRRPQPQTQTTNIL图一个命题逻辑的归结演绎树 解：1) 假设结论R为假, 即R为真, 将R加入公式集2) 化为子句集 S= P P QR, SQ, TQ , T , R 例设已知的公式集为P, (PQ)R, (ST) Q, T, 求证结论R。82PQRRPQPQTQTTNIL图81谓词逻辑的归结反演例： 已知 F：(x)(彐y)A(x, y)B(y) (彐y) (C(y)D(

47、x, y) G： (彐x) C(x) ( x)( y)(A(x, y) B(y)求证：G是F的逻辑结论。证明：1) 把G否定, 并放入F中, 得到的F, G为 : F: ( x)(彐y)A(x, y)B(y) (彐y) (C(y)D(x, y), G: ( (彐x) C(x) ( x)( y)(A(x, y) B(y) )2)F, G化成于句集, 得到 (1) A(x, y) B(y) C(f(x) ) (2) A(u, v) B(v) D(u, f(u) ) (3)C(z) (4) A(m, n) (5) B(k)83谓词逻辑的归结反演例： 已知 F：(x)(彐y)A(82A(x, y) B

48、(y) C(f(x)C(z)A(x, y) B(y)f(x)/zA(m, n)B(n)m/x, n/yB(k)NILk/n归结树 (1) A(x, y) B(y) C(f(x) ) (2) A(u, v) B(v) D(u, f(u) ) (3)C(z) (4) A(m, n) (5) B(k)84A(x, y) B(y) C(f(x)C(z831）广度优先策略1)从初始子句集S0出发, 对S0中的作出所有可能的归结, 得到第一层归结式, 把这些归结式的集合称之为S12)用S0中的全部子句和S1中的子句作出所有可能的归结, 得到第二层归结式, 把这些归结式的集合称之为S23)用S0和S1中的全

49、部子句和S2中的子句作出所有可能的归结, 得到第三层归结式, 把这些归结式的集合称之为S33.3.4 归结演绎推理的归结策略851）广度优先策略3.3.4 归结演绎推理的归结策略841) 广度优先策略例 S0=I(x) R(x), I(a), R(y) L(y), L(a)解:从S0出发, 依次构成S1, S2, .直到空子句特点：效率低完备的归结策略I(a)I(x) R(x)R(y) L(y)L(a)S0R(a)I(x) L(x)R(a)S1L(a)L(a)I(a)I(a)NILS2861) 广度优先策略例 S0=I(x) R(x),852) 支持集策略每一次参加归结的两个亲本子句中, 至少

50、应该有一个是由目标公式的否定所得到的子句或它们的后裔。特点：完备的效率较高I(x)R(x)I(a)R(y) L(y)L(a)S0:R(a)I(x)L(x)S1:L(a)L(a)I(a)S2:NILS3:872) 支持集策略每一次参加归结的两个亲本子句中, 至少应863) 单文字子句策略要求参加归结的两个亲本子句中至少有一个是单文字子句特点：不完备效率较高：归结式包含的文字数将少于其亲本子句中的文字数, 这将有利于向空子句的方向发展SS1S2I(x) R(x)R(y) L(y)I(a)L(a)R(a)R(a)NIL883) 单文字子句策略要求参加归结的两个亲本子句中至少有一874) 线性输入策略

51、每次归结都包含一个来自初始子句特点：不完备；效率较高SS1S2I(x) R(x)R(y) L(y)I(a)L(a)R(a)R(a)NILI(x)L(x)S3I(a)L(a)I(a)L(a)894) 线性输入策略每次归结都包含一个来自初始子句SS1S885) 祖先过滤策略在线性输入策略的基础上放宽对子句的限制每次参加归结的两个亲本子句至少有一个是初始子句集中的子句一个子句应该是另一个子句的先辈子句例：S=Q(x)P(x), Q(y)P(y), Q(w)P(w), Q(a)P(a)Q(x) P(x)Q(y) P(y)P(x)Q(w) P(w)Q(w)Q(a) P(a)P(a)NIL可以证明祖先过滤

52、策略也是完备的905) 祖先过滤策略在线性输入策略的基础上放宽对子句的限制896) 删除策略1) 纯文字删除法例：S=PQR, QR, Q, R2)重言式删除法例：P(X) P(X), P(X) Q(X) P(X)3)包孕删除法设子句C1和C2, 如果存在一个置换, 使得C1 C2, 则称C1包孕于C2例 P(x)包孕于 P(y)Q(z) = yx P(x)包孕于P(a) = (ax) P(x)包孕于P(a)Q(z) = ax P(x)Q(z)包孕于P(f(a)Q(a)R(y) = f(a)x P(x)Q(y)包孕于 P(a)Q(u)R(w) = ax, uy916) 删除策略1) 纯文字删除

53、法903.3.5 用归结反演求进行问题求解步骤如下：l)把问题的已知条件用谓词公式表示出来, 并化为相应的子句集；2)把问题的目标的否定用谓词公式表示出来, 并化为子句集；3)对目标否定子句集中的每个子句, 构造该子句的重言式，并把这些重言式加入到前提子句集中, 得到一个新的子句集；4)对这个新的子句集, 应用归结原理求出其证明树, 这时证明树的根子句不为空, 称这个证明树为修改证明树；5)用修改证明树的根子句作为回答语句, 则答案就在此根子句中重言式：把该目标否定子句和此目标否定子句的否定之间再进行析取所得到的子句923.3.5 用归结反演求进行问题求解步骤如下：91已知：张和李是同班同学,

54、 如果x和y是同班同学, 则x的教室也是y的教室, 现在张在302教室上课。问：现在李在哪里上课？解：1)定义谓词： C(x, y) x和y是同班同学；At(x, u) x在u教室上课。2)把已知前提用谓词公式表示如下：C(zhang, li); At(zhang, 302)( x)( y)( z)(C(x, y) At(x, u) At(y, u)目标：(彐v)At(li, v)3) 把上述公式化为子句集：C(zhang, li), At(zhang, 302), C(x, y) At(x, u) At(y, u)4) 目标的重言式: At(li, v) At(li, v)93已知：张和李是

55、同班同学, 如果x和y是同班同学, 则x的92C(zhang, li), At(zhang, 302), C(x, y) At(x, u) At(y, u) At(li, v) At(li, v)li/y, v/uzhang/x302/vC(x, y) At(x, u) At(y, u)At(li, v) At(li, v)At(li, v) C(x, li) At(x, v)C(zhang, li)At(li, v) At(zhang, v)At(zhang, 302)At(li, 302)94C(zhang, li), At(zhang, 3093典型题目：确定性推理1、单元归结法（ ）一

56、种完备的归结方法。(2005)A是 B不是4. 子句C1= P Q 和C2 = P Q的归结式是（ ）。（2006）A. 空子句 B. 重言式 C. 任意子句3、子句C1= P Q和C2 = P Q的归结式（ ）空子句。（2005）A. 是 B.不是2、用反演（refutation）归结求证结论时，若当前归结式是空子句（NIL），则表示（ ）。（2002）A 结论得证 B 结论证不出 C 可删除95典型题目：确定性推理1、单元归结法（ ）一种完备的归94典型题目：确定性推理2、反演（refutation）归结（消解，resolution）证明定理时，若当前归结式（消解式，resolvent）是

57、（ ）则定理得到证明。（2001）A永真式 B包孕式（subsumed）C空子句8、以反演归结证明子句集S不可满足的过程中，当前归结式是（ ）或者（ ），则可删除。（2001）7、谓词逻辑下，子句 C1和C2。若是互补句节的（ ）合一子，则其归结式（消解式，resolvent）C（ ）（2001）96典型题目：确定性推理2、反演（refutation）归结95典型题目：确定性推理1、命题逻辑下，可以归结（消解，resolution）的子句C1、C2，在某解释下C1、C2为真，则其归结式（消解式，resolvent）C在该解释下（ ）(2000)A必真 B必假 C真假不能断言1、标准逻辑（谓词逻

58、辑）中，重言式是指（ ）（2001）A永真 B永假 C 非永真（invalid）6、用反演（refutation）归结证明定理，证明过程是这样结束的：若（ ）则定理得证；若（ ）则证明失败。（2000）97典型题目：确定性推理1、命题逻辑下，可以归结（消解，re96典型题目：确定性推理二、证明题（共10 分）（2005/2004/2003）依支持集策略的归结方法来证明：A1 A2 A3 B，其中98典型题目：确定性推理二、证明题（共10 分）（2005/97典型题目：确定性推理四（9分）化下列逻辑表达式为不含存在量词的前束形（prenexs form）：（2002）二、证明题（共8 分）（20

59、06年）试用归结法证明，对任意的集合S和T，必有STS 。（提示：需将交集、包含关系的定义，用逻辑式表达并作为证明的条件）99典型题目：确定性推理四（9分）化下列逻辑表达式为不含存在98典型题目：确定性推理三、（9分）用标准逻辑（经典逻辑、谓词逻辑）的子句集表示下述刑侦知识，并用反演归结的线性策略证明结论。（2001） 现定义如下谓词（其项变量X、Y、Z，皆为全程变量）thief(X)-某人X是个贼；likes(X, Y)-某人X喜欢某物Y；may_steal(X, Y)-某人X可能偷窃某物Y；用子句集表达下述刑侦知识：John是贼。Paul喜欢喝酒（wine）。Paul（也）喜欢奶酪（che

60、ese）。如果Paul喜欢某物则John也喜欢某物。如果某人是贼，而且他喜欢某物，则他就可能会偷窃该物。求证结论：John可能会偷窃了什么？即求证目标：may_steal(John, Z)，Z = ?100典型题目：确定性推理三、（9分）用标准逻辑（经典逻辑、993.3 不确定推理大纲：理解基本概念和意义掌握表示问题、计算问题、语义解释等三个问题3.3.1不确定推理的基本概念问题3.3.2 可信度方法（重点）3.3.3 主观Bayes方法3.3.4 证据理论3.3.5 基于案例的推理1013.3 不确定推理大纲：理解基本概念和意义掌握表示问题1003.3.1不确定推理的基本概念1.什么是不确定