资源描述
第1章概述1、重点掌握人工智能的几种定义。2、掌握目前人工智能的三个主要学派及 其认知观。3、一般了解人工智能的主要研究范围和 应用领域。人工智能的三大学派及其认知观：(1)符号主义： 认为人工智能起源于数理逻辑。(2)连接主义： 认为人工智能起源于仿生学，特别是对人脑模型的研究。(3)行为主义： 认为人工智能起源于控制论。第2章确定性知识系统n 重点掌握用谓词逻辑法、产生式表示、语义网络法、框架表示法来描述问题，解决问题；n 重点掌握归结演绎推理方法谓词逻辑法 一阶谓词逻辑表示法适于表示确定性的知识。它具有自然性、精确性、严密性及易实现等特点。 用一阶谓词逻辑法表示知识的步骤如下：（1）定义谓词及个体，确定每个谓词及个体的确切含义。（2）根据所要表达的事物或概念，为每个谓词中的变元赋以特定的值。（3）根据所要表达的知识的语义，用适当的连接符号将各个谓词连接起来，形成谓词公式。例1：设有下列事实性知识： 张晓辉是一名计算机系的学生，但他不喜欢编程序。 李晓鹏比他父亲长得高。请用谓词公式表示这些知识。（1）定义谓词及个体。Computer(x):x是计算机系的学生。Like(x,y):x喜欢y。Higher(x,y):x比y长得高。这里涉及的个体有：张晓辉(zhangxh),编程序(programming), 李晓鹏(lixp)，以及函数father(lixp)表示李晓鹏的父亲。 第二步：将这些个体代入谓词中，得到 Computer(zhangxh) Like(zhangxh, programming)Higher(lixp, father(lixp)n 第三步：根据语义，用逻辑联结词将它们联结起来，就得到了表示上述知识的谓词公式。Computer(zhangxh) Like(zhangxh, programming) Higher(lixp, father(lixp)例2：设有下列语句，请用相应的谓词公式把它们表示出来：（1）人人爱劳动。（2）自然数都是大于零的整数。（3）西安市的夏天既干燥又炎热。 （4）喜欢读三国演义的人必读水浒。 （5）有的人喜欢梅花，有的人喜欢菊花，有的人既喜欢梅花又喜欢菊花。（6）他每天下午都去打篮球。解：（1）人人爱劳动。定义谓词如下：Man(x):x是人。Love(x,y):x爱y。（x)(Man(x)Love(x,劳动） 解：（1）人人爱劳动。定义谓词如下：Man(x):x是人。Love(x,y):x爱y。（x)(Man(x)Love(x,劳动） （2）自然数都是大于等于零的整数。定义谓词如下：N(x):x是自然数。I(x):x是整数。GZ(x):x大于等于零。（x)(N(x)(GZ(x）I(x)） (3) 西安市的夏天既干燥又炎热。 定义谓词： SUMMER(x):x处于夏天。 DRY(x):x很干燥。 HOT(x):x很炎热。SUMMER(Xian)DRY(Xian)HOT(Xian) （4）喜欢读三国演义的人必读水浒。 定义谓词： MAN(x)：x是人。 LIKE(x,y)：x喜欢读y。 (x)(MAN(x)LIKE(x, SANGUOYANYI) LIKE(x, SHUIHU)（5）有的人喜欢梅花，有的人喜欢菊花，有的人既喜欢梅花又喜欢菊花。定义谓词：MAN(x):x是人。LIKE(x,y): x喜欢y。 Meihua表示梅花，Juhua表示菊花， ($x)(MAN(x) LIKE(x, Meihua) ($y)(MAN(y) LIKE(y, Juhua) ($z)(MAN(z) (LIKE(z, Meihua) LIKE(z,Juhua)（6）他每天下午都去打篮球。 定义谓词及个体：设TIME(x):x是下午。PLAY(x,y):x去打y， Liming表示李明， Basketball表示足球，则:（x）TIME(x)PLAY(Liming,Basketball) 产生式系统n 产生式系统的组成n 产生式系统由3个部分组成，即全局数据库、规则库和控制策略， 综合数据库，用于存放求解过程中各种当前信息的数据结构，如问题是的初始状态、事实或证据、中间推理结论和最后结果等。 规则库，用于存放与求解问题有关的某个领域知识的规则之集合及其交换规则。 其基本形式为 IF 前提 THEN 结论 控制策略的作用是说明下一步应该选用什么规则。2.2.4 语义网络法 语义网络是1968年J.R.Quillian在研究人类联想记忆时提出的心理学模型。 语义网络的概念每个语义基元可表示为三元组： （结点1，弧，结点2） 节点代表实体 弧是有方向和标注的n 方向体现了结点所代表的实体的主次关系n 标注表示它所连接的两个实体之间的语义联系n 连接的两个节点间的某种语义联系或语义关系。 语义网络表示一元关系、二元关系和多元关系： 多元关系表示方法：通过增加关系结点、动作结点、事件结点或情况结点等的方法把多元关系转化为多个二元关系。例1、用一个语义网络表示下列命题。(1) 树和草都是植物；(2) 树和草是有根有叶的；(3) 水草是草，且长在水中；(4) 果树是树，且会结果；(5) 苹果树是果树中的一种，它结苹果。分析：问题涉及的对象有： 植物、树、草、水草、果树、苹果树各对象的属性分别为： 树和草的属性：有根、有叶； 水草的属性：长在水中； 果树的属性：会结果； 苹果树的属性：结苹果。2.2.4 框架表示 1974年，由Minsky在“A framework for representing knowledge”中提出。 框架是一种描述所论对象属性的数据结构。 所论对象可以是一个事物、一个事件或者一个概念 。一个框架由若干个“槽”组成，每个“槽”又可划分为若干个“侧面”。一个槽用于描述所论及对象的某一方面的属性，一个侧面用于描述相应属性的一个方面。槽和侧面所具有的属性值分别称为槽值和侧面值。槽值可以是逻辑型或数字型的，具体的值可以是程序、条件、默认值或是一个子框架。 （1）框架的基本结构 一个框架通常由若干个称为“槽”的结构组成 每一个槽又可以根据实际情况拥有若干个“侧面” 每一个侧面也可以拥有若干个“侧面值” 框架的槽值和侧面值，可以是数字、字符串、布尔值，也可以是一个在满足某个给定条件时需执行的动作或过程，还可以是另外一个框架。 槽或侧面值可附加约束信息。例： 一个用来描述硕士生有关情况的框架Frame 姓名: 单位（姓，名） 性别：范围（男，女） 默认：男 年龄：单位（岁） 条件：岁16 学习专业：单位（专业名） 研究方向：单位（方向名） 导师姓名：单位（姓，名） 参加课题：范围（国家级，省部级，其他） 默认：国家级 学籍： 住址：单位（楼号，房间号） 电话：单位（ （区号），话机号） 入学时间：单位（年，月） 学制：单位（年） 默认；3年n 例：用框架表示下述报道的地震事件n 【虚拟新华社3月15日电】昨日，在云南玉溪地区发生地震，造成财产损失约10万元，统计部门如果需要详细的损失数字，可电询62332931。另据专家认为震级不会超过4级，并认为地处无人区，不会造成人员伤亡。n 提示：分析概括用下划线标出的要点，经过概念化形成槽（slot）、侧面（facet）值。特别要注意，“值”（value）、“默认值”（default）、“如果需要值”（if-needed）、“如果附加值”（if-added）的区别与应用，建议采用格式如下，不用的侧面值可删。 鲁滨逊归结原理n 重点掌握子句集的求解步骤和归结反演过程，掌握归结推理的规则。归结反演求解过程1、归结反演给出一个公式集S和目标公式L，通过反证或反演来求证目标公式L，其证明步骤如下：(1)否定目标L，得L；(2)把L添加到S中去；(3)把新产生的集合L，S化成子句集；(4)应用归结原理，力图推导出一个表示矛盾的空子句NIL。 问题归约法 问题归约法的概念v 已知问题的描述，通过一系列变换把此问题最终变为一个子问题集合；这些子问题的解可以直接得到，从而解决了初始问题。v 该方法也就是从目标(要解决的问题)出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个平凡的本原问题集合。这就是问题归约的实质。 问题归约法的组成部分（1）一个初始问题描述；（2）一套把问题变换为子问题的操作符；（3）一套本原问题描述。 第3章搜索推理技术n 重点掌握各种盲目搜索策略、A算法、A*算法、博弈树的-剪枝算法 n 和搜索相对应的知识表示法一般有两种：n 状态空间法：（S，F，G）n 与或图表示法：基于一种分解与变换的思想，利用树状结构对复杂问题进行表示，使复杂问题简单化。3.2 盲目搜索 盲目搜索又叫做无信息搜索，一般只适用于求解比较简单的问题。宽度优先搜索和深度优先搜索，属于盲目搜索方法。 Open表、closed表代价树的盲目搜索 宽度优先搜索的推广 用来解决从起始状态至目标状态的具有最小代价的路径问题。 从起始节点S到任一节点i的路径代价记为g(i)。 从节点i到它的后继节点j的连接弧线代价记为c(i，j)； 则节点j的路径代价为g(j)=g(i)+c(i,j)。 待扩展的节点是路径代价最小的节点。 3.3 启发式搜索 盲目搜索的不足：效率低，耗费过多的计算空间与时间。 宽度优先、深度优先搜索，或代价树搜索算法,其主要的差别是OPEN表中待扩展节点的顺序问题。人们就试图找到一种方法用于排列待扩展节点的顺序，即选择最有希望的节点加以扩展，那么，搜索效率将会大为提高。 启发信息：进行搜索技术一般需要某些有关具体问题领域的特性的信息。 把利用启发信息的搜索方法叫做启发式搜索方法。 启发式搜索策略 启发信息用于决定要扩展的下一个节点， 这种搜索总是选择“最有希望”的节点作为下一个被扩展的节点。A算法 A算法：在状态空间搜索中，每一步都利用估价函数f(n)=g(n)+h(n)对Open表中的节点进行排序。 类型： 全局择优： 从Open表的所有节点中选择一个估价函数值最小的进行扩展。 局部择优：仅从刚生成的子节点中选择一个估价函数值最小的进行扩展。 u A算法存在的问题： 不能保证总是找到问题的最优解。u 解决办法：对A算法的估价函数增加一些限制条件 应用：A*算法求解8数码问题3.5 博弈树搜索过程u 首先假定，有一个评价函数f(n) 可以对所有的棋局进行评估u 考虑双方对弈若干步之后，从可能的走步中选一步相对好棋的着法来走，即在有限的搜索深度范围内进行求解。u 静态估计函数 f 一般规定有利于MAX的势态， f(p)取正值 有利于MIN的势态，f(p)取负值 势均力敌的势态，f(p)取0值 若f(p)，则表示MAX赢 若f(p)，则表示MIN赢 -搜索过程思想u 极大节点的下界为 u 极小节点的上界为 u 剪枝的条件 后辈节点的值祖先节点的值时，剪枝 后辈节点的值祖先节点的值时，剪枝 u 简记为 极小极大，剪枝 极大极小，剪枝u a、b值的性质 MAX节点的a值永不减少 MIN节点的b值永不增加 第四章 计算智能遗传算法 结构组成、基本原理、算法步骤第五章 不确定性推理掌握 n 可信度推理 n 主观Bayes推理第二章语义练习请对下列命题分别写出它们的语义网络：(1) 每个学生都有一台计算机。gGS解：占有权计算机学生AKOISAISAFOwnsOwnercosg(2) 高老师从3月到7月给计算机系学生讲计算机网络课。 解：7月8月StartEnd老师ISAObjectSubject高老师计算机系学生讲课事件ActionCaurse计算机网络讲课(5) 红队与蓝队进行足球比赛，最后以3：2的比分结束。 解：比赛AKOParticipants1Outcome3:22足球赛红队Participants 2蓝队请把下列命题用一个语义网络表示出来：(1) 树和草都是植物；解：植物AKOAKO草树(2) 树和草都有叶和根；根叶 解：HaveHave植物是一种是一种草树(3) 水草是草，且生长在水中； 解：LiveAKOAKO水草水中植物草(4) 果树是树，且会结果； 解：CanAKOAKO果树结果植物树(5) 梨树是果树中的一种，它会结梨。 解：CanAKOAKO梨树树果树结梨假设有以下一段天气预报：“北京地区今天白天晴，偏北风3级，最高气温12，最低气温-2，降水概率15%。”请用框架表示这一知识。解：Frame 地域：北京 时段：今天白天 天气：晴 风向：偏北 风力：3级 气温：最高：12度 最低：-2度 降水概率：15%按“师生框架”、“教师框架”、“学生框架”的形式写出一个框架系统的描述。解：师生框架Frame Name：Unit（Last-name，First-name） Sex：Area（male，female） Default：male Age：Unit（Years）Telephone：Home Unit（Number）Mobile Unit（Number） 教师框架Frame AKO Major：Unit（Major-Name） Lectures：Unit（Course-Name） Field：Unit（Field-Name） Project ：Area（National，Provincial，Other） Default：Provincial Paper：Area（SCI，EI，Core，General） Default：Core 学生框架Frame AKO Major：Unit（Major-Name） Classes：Unit（Classes-Name） Degree：Area（doctor，mastor, bachelor） Default：bachelor 一、 填空：1. 谓词逻辑是一种表达能力很强的形式语言，其真值的特点和命题逻辑的区别是_真值不唯一_。2. 设P是谓词公式，对于P的任何论域，存在P为真的情况，则称P为_重言式_。3. 谓词公式G是不可满足的，当且仅当对所有的解释_G都为假_ 。4. 利用归结原理证明定理时，若得到的归结式为_空子句_，则结论成立。5. 若C1= PQ，C2=PQ，则C1和C2的归结式R（C1，C2）=_PP或QQ 。6. 若C1=P(x) Q(x)，C2= P(a) R(y)，则C1和C2的归结式R（C1，C2）= _ Q（a）R（y）_7. 有子句集S=P(x),P(y)，其MGU=_y/x _。8. 产生式系统有三部分组成综合数据库， 知识库和推理机。其中推理可分为 正向推理和反向推理。 。 9. (x)(y)(On(x,y) Above(x,y)化成子句形式为：on(x,y) Above(x,y) 。10. 从已知事实出发，通过规则库求得结论的产生式系统的推理方式是 正向推理 11. 在谓词公式中，紧接于量词之后被量词作用的谓词公式称为该量词的辖域 ，而在一个量词的辖域中与该量词的指导变元相同的变元称为 约束变元 ，其他变元称为 自由变元 。12. 假言推理（AB）A B ，假言三段论（AB）（BC） AC 13. 某产生式系统中的一条规则：A（x）B（x），则前件是 A（x） ，后件是 B（x）。14. 在框架和语义网络两种知识表示方法中，框架 适合于表示结构性强的知识，而 语义网络 则适合表示一些复杂的关系和联系的知识。二、选择题： 1.在公式中y$x p(x,y)，存在量词是在全称量词的辖域内，我们允许所存在的x可能依赖于y值。令这种依赖关系明显地由函数所定义，它把每个y值映射到存在的那个x。这种函数叫做（ ） A. 依赖函数 B. Skolem函数 C. 决定函数 D. 多元函数2.产生式系统的推理不包括（ ） A. 正向推理 B. 逆向推理 C. 双向推理 D. 简单推理3.下列哪部分不是专家系统的组成部分（ ） A. 用户 B. 综合数据库 C. 推理机 D. 知识库 4、谓词逻辑下，子句, C1=LC1, C2= LC2, 若是互补文字的（最一般）合一置换，则其归结式C=（ ）A) C1C2B)C1C2C)C1C2D)C1 C25. 语义网络表达知识时，有向弧AKO 链、ISA 链是用来表达节点知识的（ ）。A.无悖性 B.可扩充性 C.继承性 D. 相似性三、简答题1.将下列自然语言转化为谓词表示形式：(1) 所有的人都是要呼吸的。(2) 每个学生都要参加考试。(3) 任何整数或是正的或是负的。解：设 M(x)：x是人,H(x)：x要呼吸。 P(x)：x是学生， Q(x)：x要参加考试。 J(x)：x是整数， R(x)：x是正数，N(x)：x是负数。则上述三题就记为：(1) V-x(M(x)H(x)(2) V-x(P(x)Q(x)(3) V-x(I(x)R(x)N(x)2.试实现一个“大学教师”的框架，大学教师类属于教师，包括以下属性：学历（学士、硕士、博士）、专业（计算机、电子、自动化、）、职称（助教、讲师、副教授、教授）解：框架名：类属：学历：(学士、硕士、博士)专业：（计算机、电子、自动化、.）职称：（助教、讲师、副教授、教授）3.用谓词逻辑形式化下列描述“不存在最大的整数”解：定义谓词G(x)：x为整数D(x,y)：x大于y形式化为：或者4 将命题：“某个学生读过三国演义”分别用谓词公式和语义网络表示答：谓词公式表示：x(student(x)read(x,三国演义)语义网络表示如图：5将下列谓词公式化成子句集答： /消去存在量词 /消去存在量词子句集：6试用线性消解策略证明：子句集S= PQ, PR, QR, R 是可消解的。解： QRR QRPQ,PR QRRNIL 7设有如下关系：（1）如果x是y的父亲，y又是z的父亲，则x是z的祖父；（2）老李是大李的父亲；（3）大李是小李的父亲；问上述人员中谁和谁是祖孙关系？解:现定义如下谓词F(x,y)- x是y的父亲;G(x,z)- x是y的祖父;用谓词逻辑表示已知与求解:(1) F(x,y)F(y,z)G(x,z)(2) F(L,D)(3) F(D,X)(4) G(u,v),u=?,v=?其中,L表示老李,D表示大李,X表示小李。先证存在祖孙关系 F(x,y)F(y,z)G(x,z)从(1)变换 F(L,D)从(2)变换 F(D,X)从(3)变换 G(u,v)结论的否定 F(D,z)G(L,z)归结,置换L/x,D/y G(L,X)归结,置换X/z 归结,置换L/u,X/v得证,说明存在祖孙关系。为了求解用一个重言式 G(u,v)G(u,v) 用重言式代替结论的否定,重言式恒为真 F(D,z)G(L,z)归结,置换L/x,D/y G(L,X)归结,置换X/z G(L,X)归结,置换L/u,X/v得结果:L是X的祖父，即老李是小李的祖父。第3章 确定性推理部分参考答案3.8 判断下列公式是否为可合一，若可合一，则求出其最一般合一。(1) P(a, b), P(x, y)(2) P(f(x), b), P(y, z)(3) P(f(x), y), P(y, f(b)(4) P(f(y), y, x), P(x, f(a), f(b) (5) P(x, y), P(y, x)解：(1) 可合一，其最一般和一为：=a/x, b/y。(2) 可合一，其最一般和一为：=y/f(x), b/z。(3) 可合一，其最一般和一为：= f(b)/y, b/x。(4) 不可合一。(5) 可合一，其最一般和一为：= y/x。3.11 把下列谓词公式化成子句集：(1) (x)(y)(P(x, y)Q(x, y)(2) (x)(y)(P(x, y)Q(x, y)(3) (x)(y)(P(x, y)(Q(x, y)R(x, y)(4) (x) (y) (z)(P(x, y)Q(x, y)R(x, z) 解：(1) 由于(x)(y)(P(x, y)Q(x, y)已经是Skolem标准型，且P(x, y)Q(x, y)已经是合取范式，所以可直接消去全称量词、合取词，得 P(x, y), Q(x, y) 再进行变元换名得子句集： S= P(x, y), Q(u, v) (2) 对谓词公式(x)(y)(P(x, y)Q(x, y)，先消去连接词“”得：(x)(y)(P(x, y)Q(x, y)此公式已为Skolem标准型。 再消去全称量词得子句集： S=P(x, y)Q(x, y) (3) 对谓词公式(x)(y)(P(x, y)(Q(x, y)R(x, y)，先消去连接词“”得：(x)(y)(P(x, y)(Q(x, y)R(x, y)此公式已为前束范式。再消去存在量词，即用Skolem函数f(x)替换y得：(x)(P(x, f(x)Q(x, f(x)R(x, f(x)此公式已为Skolem标准型。 最后消去全称量词得子句集： S=P(x, f(x)Q(x, f(x)R(x, f(x) (4) 对谓词(x) (y) (z)(P(x, y)Q(x, y)R(x, z)，先消去连接词“”得：(x) (y) (z)(P(x, y)Q(x, y)R(x, z)再消去存在量词，即用Skolem函数f(x，y)替换z得：(x) (y) (P(x, y)Q(x, y)R(x, f(x,y)此公式已为Skolem标准型。 最后消去全称量词得子句集：S=P(x, y)Q(x, y)R(x, f(x,y)3-13 判断下列子句集中哪些是不可满足的：(1) PQ, Q, P, P(2) PQ , PQ, PQ, PQ (3) P(y)Q(y) , P(f(x)R(a)(4) P(x)Q(x) , P(y)R(y), P(a), S(a), S(z)R(z)(5) P(x)Q(f(x),a) , P(h(y)Q(f(h(y), a)P(z)(6) P(x)Q(x)R(x) , P(y)R(y), Q(a), R(b) 解：(1) 不可满足，其归结过程为：PQQPPNIL(2) 不可满足，其归结过程为：PQPQQPQPQQNIL(3) 不是不可满足的，原因是不能由它导出空子句。(4) 不可满足，其归结过程略(5) 不是不可满足的，原因是不能由它导出空子句。(6) 不可满足，其归结过程略 3.14 对下列各题分别证明G是否为F1,F2,Fn的逻辑结论：(1) F: (x)(y)(P(x, y)G: (y)(x)(P(x, y)(2) F: (x)(P(x)(Q(a)Q(b)G: (x) (P(x)Q(x)(3) F: (x)(y)(P(f(x)(Q(f(y)G: P(f(a)P(y)Q(y)(4) F1: (x)(P(x)(y)(Q(y)L(x.y)F2: (x) (P(x)(y)(R(y)L(x.y)G: (x)(R(x)Q(x)(5) F1: (x)(P(x)(Q(x)R(x)F2: (x) (P(x)S(x)G: (x) (S(x)R(x) 解：(1) 先将F和G化成子句集： S=P(a,b), P(x,b) 再对S进行归结：P(x,b)P(a,b)NIL a/x 所以，G是F的逻辑结论(2) 先将F和G化成子句集由F得：S1=P(x)，(Q(a)Q(b)由于G为： (x) (P(x)Q(x)，即 (x) ( P(x) Q(x)，可得： S2= P(x) Q(x)因此，扩充的子句集为：S= P(x)，(Q(a)Q(b)， P(x) Q(x) 再对S进行归结：Q(a)Q(b)Q(a) P(x) Q(x) P(a)P(x)NILQ(a)Q(b) a/b P(x) Q(x)Q(a)a/x P(a)P(x) a/xNIL 所以，G是F的逻辑结论 同理可求得(3)、(4)和(5)，其求解过程略。 3.15 设已知：(1) 如果x是y的父亲，y是z的父亲，则x是z的祖父；(2) 每个人都有一个父亲。使用归结演绎推理证明：对于某人u，一定存在一个人v，v是u的祖父。 解：先定义谓词 F(x,y)：x是y的父亲 GF(x,z)：x是z的祖父 P(x)：x是一个人 再用谓词把问题描述出来： 已知F1：(x) (y) (z)( F(x,y)F(y,z)GF(x,z) F2：(y)(P(x)F(x,y) 求证结论G：(u) (v)( P(u)GF(v,u) 然后再将F1，F2和G化成子句集： F(x,y)F(y,z)GF(x,z) P(r)F(s,r) P(u) GF(v,u) 对上述扩充的子句集，其归结推理过程如下：F(x,y)F(y,z)GF(x,z)GF(v,u)F(x,y)F(y,z)P(r)F(s,r)F(y,z)P(y)P(r)F(s,r)P(y)P(z)P(y)P(u)NIL x/v,z/ux/s,y/ry/s,z/r y/z y/u 由于导出了空子句，故结论得证。3.16 假设张被盗，公安局派出5个人去调查。案情分析时，贞察员A说：“赵与钱中至少有一个人作案”，贞察员B说：“钱与孙中至少有一个人作案”，贞察员C说：“孙与李中至少有一个人作案”，贞察员D说：“赵与孙中至少有一个人与此案无关”，贞察员E说：“钱与李中至少有一个人与此案无关”。如果这5个侦察员的话都是可信的，使用归结演绎推理求出谁是盗窃犯。解：(1) 先定义谓词和常量设C(x)表示x作案，Z表示赵，Q表示钱，S表示孙，L表示李(2) 将已知事实用谓词公式表示出来赵与钱中至少有一个人作案：C(Z)C(Q)钱与孙中至少有一个人作案：C(Q)C(S)孙与李中至少有一个人作案：C(S)C(L)赵与孙中至少有一个人与此案无关： (C (Z)C(S)，即 C (Z) C(S)钱与李中至少有一个人与此案无关： (C (Q)C(L)，即 C (Q) C(L)(3) 将所要求的问题用谓词公式表示出来，并与其否定取析取。设作案者为u，则要求的结论是C(u)。将其与其否)取析取，得： C(u) C(u)(4) 对上述扩充的子句集，按归结原理进行归结，其修改的证明树如下：C(Z)C(Q)C (Z) C(S)C(Q)C(S)C(Q)C(S)C(Q)C(u)C(u)C(Q) Q/u 因此，钱是盗窃犯。实际上，本案的盗窃犯不止一人。根据归结原理还可以得出：C(S)C(L)C (Q) C(L)C(S)C(Q)C(Q)C(S)C(S)C(u)C(u)C(S)C (Q) C(L)C(S)C(L)C(Q)C(S)C(S)C(Q)C(u)C(u)C(S) S/u C(S) 因此，孙也是盗窃犯。3.18 设有子句集： P(x)Q(a, b), P(a)Q(a, b), Q(a, f(a), P(x)Q(x, b)分别用各种归结策略求出其归结式。解：支持集策略不可用，原因是没有指明哪个子句是由目标公式的否定化简来的。删除策略不可用，原因是子句集中没有没有重言式和具有包孕关系的子句。单文字子句策略的归结过程如下：Q(a, f(a)P(x)Q(a, b) b/f(a)P(x)Q(x, b)P(a)Q(a, f(a)Q(a, b) a/x b/f(a)Q(a, b)用线性输入策略（同时满足祖先过滤策略）的归结过程如下：P(a)Q(a, b)P(x)Q(a, b)P(x)Q(x, b)P(a) a/xa/xQ(a, f(a)Q(a,b) b/f(a)NIL 3.19 设已知：(1) 能阅读的人是识字的；(2) 海豚不识字；(3) 有些海豚是很聪明的。请用归结演绎推理证明：有些很聪明的人并不识字。解：第一步，先定义谓词， 设R(x)表示x是能阅读的；K(y)表示y是识字的；W(z) 表示z是很聪明的；第二步，将已知事实和目标用谓词公式表示出来能阅读的人是识字的：(x)(R(x)K(x)海豚不识字：(y)(K (y)有些海豚是很聪明的：(z) W(z)有些很聪明的人并不识字：(x)( W(x)K(x) 第三步，将上述已知事实和目标的否定化成子句集： R(x)K(x)K (y)W(z)W(x)K(x) 第四步，用归结演绎推理进行证明W(z)W(x)K(x)K (y)K(z)NIL3.20 对子句集： PQ, QR, RW, RP, WQ, QR 用线性输入策略是否可证明该子句集的不可满足性？ 解：用线性输入策略不能证明子句集PQ, QR, RW, RP, WQ, QR 的不可满足性。原因是按线性输入策略，不存在从该子句集到空子句地归结过程。3.21 对线性输入策略和单文字子句策略分别给出一个反例，以说明它们是不完备的。3.22 分别说明正向、逆向、双向与/或形演绎推理的基本思想。3.23 设已知事实为 (PQ)R) (S(TU) F规则为 S(XY)Z试用正向演绎推理推出所有可能的子目标。解：先给出已知事实的与/或树，再利用F规则进行推理，其规则演绎系统如下图所示。由该图可以直接写出所有可能的目标子句如下： PQPQPQYRTU RXZRYZ 所有子目标UTZYXRQP所有目标UTZYXRQPYXZXYSUTTUS所有目标UTZYXRQP所有目标YZUTXPRQYXXYF规则ZXYXYZSSUTQPTUQP已知事实已知事实TUSR(PQ)TURS(PQ) (S(TU)(PQ)R) (S(TU)(PQ)R)(PQ)R) (S(TU)(PQ)R) (S(TU)3.24 设有如下一段知识：“张、王和李都属于高山协会。该协会的每个成员不是滑雪运动员，就是登山运动员，其中不喜欢雨的运动员是登山运动员，不喜欢雪的运动员不是滑雪运动员。王不喜欢张所喜欢的一切东西，而喜欢张所不喜欢的一切东西。张喜欢雨和雪。”试用谓词公式集合表示这段知识，这些谓词公式要适合一个逆向的基于规则的演绎系统。试说明这样一个系统怎样才能回答问题：“高山俱乐部中有没有一个成员，他是一个登山运动员，但不是一个滑雪运动员？”解：(1) 先定义谓词A(x) 表示x是高山协会会员S(x) 表示x是滑雪运动员C(x) 表示x是登山运动员L(x,y) 表示x 喜欢y (2) 将问题用谓词表示出来“张、王和李都属于高山协会A(Zhang)A(Wang)A(Li)高山协会的每个成员不是滑雪运动员，就是登山运动员(x)(A(x)S(x)C(x)高山协会中不喜欢雨的运动员是登山运动员(x)(L(x, Rain)C(x)高山协会中不喜欢雪的运动员不是滑雪运动员(x)(L(x, Snow) S(x)王不喜欢张所喜欢的一切东西(y)( L(Zhang, y) L(Wang ,y) 王喜欢张所不喜欢的一切东西(y)( L(Zhang, y)L(Wang, y)张喜欢雨和雪L(Zhang , Rain)L(Zhang , Snow)(3) 将问题要求的答案用谓词表示出来高山俱乐部中有没有一个成员，他是一个登山运动员，但不是一个滑雪运动员？ (x)( A(x)C(x) S(x) (4) 为了进行推理，把问题划分为已知事实和规则两大部分。假设，划分如下：已知事实：A(Zhang)A(Wang)A(Li)L(Zhang , Rain)L(Zhang , Snow)规则：(x)(A(x)S(x)C(x)(x)(L(x, Rain)C(x)(x)(L(x, Snow) S(x)(y)( L(Zhang, y) L(Wang ,y)(y)( L(Zhang, y)L(Wang, y) (5) 把已知事实、规则和目标化成推理所需要的形式事实已经是文字的合取形式：f1: A(Zhang)A(Wang)A(Li)f2: L (Zhang , Rain)L(Zhang , Snow)将规则转化为后件为单文字的形式：r1: A(x)S(x)C(x)r2: L(x, Rain)C(x)r3: L(x, Snow) S(x)r4: L(Zhang, y) L(Wang ,y)r5: L(Zhang, y)L(Wang , y) 将目标公式转换为与/或形式 A(x)(C(x) S(x) (6) 进行逆向推理逆向推理的关键是要能够推出L(Zhang , Rain)L(Zhang , Snow)，其逆向演绎过程如下图所示。 A(x)(C(x) S(x)C(x) S(x) A(x)C(x) S(x)r2r34L(x, Rain)L(x, Snow)Wang/x, y/RainWang /x, y/SnowL(Wang, y)L(Wang, y)r4r4L(Zhang, y)L(Zhang, y)Rain/ySnow/yL(Zhang, Snow)L(Zhang, Rain)
展开阅读全文