人工智能复习题(学校内部资料).doc

1设有如下关系：(1) 如果X是Y父亲，Y又是Z的父亲，则X是Z的祖父。（2）老李是大李的父亲。3.大李是小李的父亲。4问：上述人员中谁和谁是祖孙关系。1 引入谓词 P(x,y):表示x是y的父亲； Q(x,y):表示x是y的祖父于是有：A1: (x)(y)(z)P(x,y) (P(y,z)Q(x,z)SA1: P(x,y) P(y,z) Q(x,z) A2: P(Lao, Da) SA2 : P(Lao, Da) A3: P(Da, Xiao)SA3 : P(Da, Xiao) B: (x) (y)Q(x,y) SB: Q(x,y) ANS(x,y) 变量换名后，相应的子句集如下：SP(x,y) P(y,z) Q(x,z), P(Lao, Da), P(Da, Xiao), Q(u,v) ANS(u,v)下面进行归结：(1) P(x,y) P(y,z) Q(x,z) (2) P(Lao, Da) (3) P(Da, Xiao) (4) Q(u,v) ANS(u,v) (5) P(Da, z) Q(Lao,z) (6) Q(Lao,Xiao) (7) ANS(Lao, Xiao) /(1) (2) 归结, Lao/x,Da/y (3) (5)归结,Xiao/z (4) (6)归结,Lao/u, Xiao/v得到结果：ANS(Lao, Xiao), 即老李是小李的祖父。2证明梯形的对角线与上下底构成的内错角相等。解：设已给梯形的顶点依次为a ,b ,c ,d 。引入谓词T(x ,y,u,v)表示以xy为上底，uv为下底的梯形。P(x,y,u,v)表示x yu v E(x ,y ,z,u ,v ,w)表 xyz=uvw 归结(1)T（x,y,u,v）P(x,y,u,v) 由TP推出的 (2)P(x,y,u,v) E(x,y,v,u,v,y) 由PE推出的 (3)T（a,b,c,d）(4)E(a,b,d,c,d,b)(5) P(a,b,c,d) （6）P(a,b,c,d) （7）NIL / (1) (3) 归结(2) (4)归结 5) (6)归结证明A1A2G由题意可知：首先要将公式化作SKOLEM标准型：结果为：S1=P(x) Q(x), P(x) R(x); S2=P(a) S(a); SG=S(x) R(x) ;从而得到子句集：SP(x) Q(x), P(x) R(x), P(a) ,S(a), S(x) R(x)使用归结规则建立推理过程：（1）P(x) Q(x)（2）P(x) R(x)（3）P(a)（4）S(a) 5）S(x) R(x)（6）R（a）（7）R（a）（8）NIL /（2）（3）归结（4）（5）归结（6）（7）归结故命题得证。4、任何通过计算机考试并获奖的人都是快乐的，任何肯学习或幸运的人都可通过所有考试，张三不肯学习但他是幸运的，任何幸运的人都能获奖。4证明学生是否快乐的问题：(1).任何通过计算机考试得并获奖得人都是快乐的： 由于得到的子句集为空子句集，这就证明了张三是快乐的结论。 （1） (x)(PASS(puter)WIN(x.award)ENJOYMENT(x)设已知凡是清洁的东西就有人喜欢；（2）人们都不喜欢苍蝇。用 (2).任何肯学习或幸运的人都可以通过考试归纳法证，苍蝇不清洁证：引入谓词( 解：clear(x)表示清洁的东西like(x,y)表示喜欢于是(3)张三不肯学习但他是幸运的：A1: (x) (y)(clear(x)like(y,x)SA1: clear(x) like(y,x) A2: (x) (like(x, fly)(4)任何幸运得人都能获奖：SA2 : like(x, fly) B: clear(fly) SB: clear(fly)先将上述谓词转化为Skolem范式，利用量词消去规则并改名，对结论进行否定后得如下子句集： PASS（x,computer） 由（1）得变量换名后，相应的子句集如下： Sclear(x)like(y,x), like(z, fly), clear(fly) STUDY(y) PASS(y,z) 下面进行归结：(1) clear(x)like(y,x)(2) like(z, fly)(3) clear(fly) LUCKY(u) PASS(u,v) 由（2）得(4) like(y,fly) (1) (3) 归结, fly/x,(5) NIL (2) (4)归结,z/y STUDY(zhangsan) LUCKY(zhangsan) 由（3）得 LUCKY(w) WIN(w,award) 由（4）得 ENJOYMENT(zhangsan) 此句为结论的否定下面对上述子句集，再利用反演树对消减的过程进行描述，如图47所示。PASS（x,computer）LUCKY(w) WIN(w,award)PASS（w,computer） ENJOYMENT(w) LUCKY(w) ENJOYMENT(zhangsan) PASS（zhangsan,computer）LUCKY(zhangsan) LUCKY(zhangsan)PASS（zhangsan,computer） LUCKY(u) PASS（u,v）LUCKY(zhangsan) LUCKY(zhangsan)null图47 学生快乐问题消解反演树uuu 词汇表1. 1人工智能 是计算机科学的一个分支，是研究和解释模拟人类智能和智能行为的学科。2.子句（子句集） 逻辑公式，是一些文字的析取（子句的集合）。3.专家系统 是人工智能系统的典型代表，一般由知识库、推理机组成，已有广泛应用。4.不确定性推理 知识的不精确性模糊性随机性统称为不确定性，在不确定意义下的推理为不确定推理。5.反演 采用证明AB的不可满足性来证明A B，是一种反演（反驳）证明法。6.可满足性指一个逻辑公式，若在某个解释下取值为真，便说这个公式是可满足的。7.归纳 是一种由实例得出一般性结论的推理。8.归结 是定理证明的一种方法。 9.句法分析 对自然语言句子的一种分析方法，采用句法规则来作句子分析，并给出句子的结构。10.产生式系统 是一种以产生式表示知识的专家系统，是最常用的一种专家系统。11.自然语言处理 是人工智能研究的一个领域，使用机器来对自然语言文本来进行词、语法、语义分析， 以便回答问题，作文摘，机器翻译等。12.合一 对两个原子谓词，通过变量置换而合一化的过程。13.合取范式 对一个谓词公式，通过等值演算化成如() () ()形式，称原公式的合取范式。14.过程性知识 是一种表示和求解为一体的知识表示类型。15.完备性 如归结法是完备的，指凡一阶逻辑的定理，均可用归结法来证明。16.启发式搜索 是一种试探性的、不精确的、模糊的依于经验知识的搜索方法，常能明显化简问题求解的复杂性17.陈述性知识 是一种表示和求解分离的知识表示类型。18.知识表示 是知识存储于计算机中的一种数据结构，同时强调使用方法。19.定理证明 指的是给一种机械化算法来让计算机自动证明定理。20.规则一种形式为 如果A那么B的语句为规则，专家系统中通过使用规则进行推理，即若条件A成立，使用这条规则便可推得出B。非单调推理 一种非标准逻辑下的推理方法，随知识的增加原有结论不一定随之增加，甚至会减少，就是非单调推理要研究的内容。 21.知识获取从书本、专家等信息源寻求有用的知识便是知识获取，是知识工程的三大任务(知识获取、知识表示和知识利用)之一。22.语义网络 一种用有向图来表示知识的方法。23.语义 是一种事物描述的另一种解释形式，如自然语言语句的语义分析，指用语句的某种含义来理解语句。24.控制策略 问题求解过程中，为提高效率而采取的技术手段。25.框架表示 是一种知识表示方法，是对某类情景的结构化表示。1 什么是人工智能对于人工智能还难以给出严格的定义，但可从不同侧面作些描述。人工智能是计算机科学的一个分支，是研究使计算机来完成能表现出人类智能的任务的学科。主要包括计算机实现智能的原理、制造类似于人脑的智能计算机、以及使计算机更巧妙些实现高层次的应用。它涉及到计算机科学、心理学、哲学和语言学等学科。总的目标是增强人的智能。还可以说，人工智能是研究怎样使计算机来模仿人脑所从事的推理、学习、思考、规划等思维活动，来解决需人类专家才能处理的复杂问题。如医疗诊断、石油测井解释、气象预报、运输调度和管理决策等课题。从实用观点看，人工智能是一门知识工程学：以知识为对象，研究知识的获取、知识的表示方法和知识的使用。同传统的计算机程序相比较，人工智能首先研究的是以符号表示的知识而不是数值数据为研究对象。其次，采用的是启发式推理方法而不是常规的算法。另外，控制结构与领域知识是分离的，还允许出现不正确的解答。2人工智能基础的五个基本问题(1)知识与概念化是否是人工智能的核心(2)认知能力能否与载体分开来研究(3)认知的轨迹是否可用类自然语言来描述?(4)学习能否与认知分开来研究？(5)所有的认知是否有一种统一的结构?3.图灵实验内容Turing 提出的智能实验，参加者是计算机、被实验的人以及主持实验的人。由主持人提出问题，计算机和被实验的人来回答，被实验者在回答问题时尽可能地向主持人表示他是真正的人，计算机也尽可能逼真地模仿人的思维。如果主持人通过听取对问题的回答分辨不出哪个是人的回答时，便可认为被试验的计算机是有智能的了。有人对这样设计的实验提出了疑义：认为这种实验只反映了结果的比较而没有涉及思维的过程，而且也没明确此人是个孩子还是有良好素质的成年人参加了实验。4.机器实现智能的几种观点符号主义认为人类智能的基本单元就是符号，认识过程就是符号表示下的符号运算，思维就是符号计算。连结主义(神经网络)认为智能的基本单元是神经元，认知过程就是基于神经网的计算。90年代初Brooks又提出了无需表示无需推理回到物理的现实世界的智能观。u 应用问题：(一) 搜索问题 1 有一农夫带一条狼，一只羊和一框青菜与从河的左岸乘船倒右岸，但受到下列条件的限制：(1) 船太小，农夫每次只能带一样东西过河；(2) 如果没有农夫看管，则狼要吃羊，羊要吃菜。请设计一个过河方案，使得农夫、浪、羊都能不受损失的过河，画出相应的状态空间图。题示：(1) 用四元组（农夫，狼，羊，菜）表示状态，其中每个元素都为0或1，用0表示在左岸，用1表示在右岸。(3) 把每次过河的一种安排作为一种操作，每次过河都必须有农夫，因为只有他可以划船。解：第一步，定义问题的描述形式用四元组S=（f，w，s，v）表示问题状态，其中，f，w，s和v分别表示农夫，狼，羊和青菜是否在左岸，它们都可以取1或0，取1表示在左岸，取0表示在右岸。第二步，用所定义的问题状态表示方式，把所有可能的问题状态表示出来，包括问题的初始状态和目标状态。由于状态变量有4个，每个状态变量都有2种取值，因此有以下16种可能的状态：S0=(1,1,1,1)，S1=(1,1,1,0)，S2=(1,1,0,1)，S3=(1,1,0,0)S4=(1,0,1,1)，S5=(1,0,1,0)，S6=(1,0,0,1)，S7=(1,0,0,0)S8=(0,1,1,1)，S9=(0,1,1,0)，S10=(0,1,0,1)，S11=(0,1,0,0)S12=(0,0,1,1)，S13=(0,0,1,0)，S14=(0,0,0,1)，S15=(0,0,0,0)人工智能复习(整理)其中，状态S3，S6，S7，S8，S9，S12是不合法状态，S0和S15分别是初始状态和目标状态。第三步，定义操作，即用于状态变换的算符组F由于每次过河船上都必须有农夫，且除农夫外船上只能载狼，羊和菜中的一种，故算符定义如下：L(i)表示农夫从左岸将第i样东西送到右岸（i=1表示狼，i=2表示羊，i=3表示菜，i=0表示船上除农夫外不载任何东西）。由于农夫必须在船上，故对农夫的表示省略。R (i)表示农夫从右岸将第i样东西带到左岸（i=1表示狼，i=2表示羊，i=3表示菜，i=0表示船上除农夫外不载任何东西）。同样，对农夫的表示省略。这样，所定义的算符组F可以有以下8种算符：L (0)，L (1)，L (2)，L (3)R(0)，R(1)，R (2)，R (3)第四步，根据上述定义的状态和操作进行求解。该问题求解过程的状态空间图如下：(1,1,l,1)L(2)(0,1,0,1)R(0)(1,1,0,1)L(3)L(1)(0,1,0,0)(0,0,0,1)R(2)R(2)(1,1,1,0)(1,0,1,1)L(2)L(3)(0,0,1,0)R(0)(1,0,1,0)L(2)(0,0,0,0)(二) 与或图搜索1.用一字棋说明极大极小搜索过程的原理，并画出第一阶段的搜索树。(三) 谓词逻辑要求：复习数理逻辑，明白命题逻辑、一阶谓词逻辑的基本概念，熟练谓词演算，会求谓词公式的前束范式和Skolem标准形等。【知识点】1. 子句集建立2. 归结式3. 归结推理过程4. 子句形 Skolem标准形 子句与子句集 G与S在不可满足意义下是一致的5. 归结原理 置换与合一 归结式 归结推理过程 归结法完备性1 不是每个计算机系的学生都喜欢在计算机上编程序。解：定义谓词S(x)：x是计算机系学生L(x, pragramming)：x喜欢编程序U(x,computer)：x使用计算机将知识用谓词表示为： (x) (S(x)L(x, pragramming)U(x,computer)2.新型计算机速度