《人工智能》1课程习题与部分解答234第1章绪论5671.1 什么是人工智能? 它的研究目标是什么?81.2 什么是图灵测试?简述图灵测试的基本过程及其重要特征.91.3 在人工智能的发展过程中，有哪些思想和思潮起了重要作用？101.5 在人工智能的发展过程中，有哪些思想和思潮起了重要作用？111.7 人工智能的主要研究和应用领域是什么？其中，哪些是新的研究热点？1213第2章知识表示方法142.1 什么是知识？分类情况如何？15162.2 什么是知识表示？不同的知识表示方法各有什么优缺点?172.4 人工智能对知识表示有什么要求?182.5 用谓词公式表示下列规则性知识：19自然数都是大于零的整数。

20任何人都会死的。

21[解]定义谓词如下:N(x): “x是自然数”, I(x): “x是整数”, L(x): “x大于0”, D(x):2223“x会死的”, M(x): “x是人”,则上述知识可用谓词分别表示为:24xLNx∨∀→xI(()])))[(x(25xMx→D∀()])()[(x262.6 用谓词公式表示下列事实性知识：27小明是计算机系的学生，但他不喜欢编程。

28李晓新比他父亲长得高。

292.8 产生式系统由哪几个部分组成? 它们各自的作用是什么?302.9 可以从哪些角度对产生式系统进行分类? 阐述各类产生式系统的特点。

312.10简述产生式系统的优缺点。

322.11 简述框架表示的基本构成，并给出框架的一般结构332.12框架表示法有什么特点？342.13试构造一个描述你的卧室的框架系统。

352.14 试描述一个具体的大学教师的框架系统。

36[解] 一个具体大学教师的框架系统为：37框架名：<教师-1>38类属：<大学教师>39姓名：张宇40性别：男年龄：324142职业：<教师>43职称：副教授部门：计算机系4445研究方向：计算机软件与理论工作：参加时间：2000年7月464748工龄：当前年份-2000工资：<工资单>49502.16把下列命题用一个语义网络表示出来(1)树和草都是植物；5152(2)树和草都是有根有叶的；53(3)水草是草，且生长在水中；54(4)果树是树，且会结果；55(5)苹果树是果树的一种，它结苹果。

56[解]575859606162636465666768697071727374752.17在基于语义网络的推理系统中，一般有几种推理方法，简述它们的推理76过程。

772.18 简述语义网络中常用的语义联系。

782.19 用一个语义网络表示：79“我的汽车是棕黄色的”80“李华的汽车是绿色的”[解]参考课件。

812.10 用语义网络和框架方法表示下列知识：82John gives a book to Mary83[解]参考课件。

8485第3章搜索推理技术86873.1 在人工智能中，搜索问题一般包括哪两个重要问题?883.2 简述搜索策略的评价标准。

893.3 比较盲目搜索中各种方法的优缺点。

90试用宽度优先搜索策略，画出搜索树、找出最优搜索路线。

91[解]92（1）搜索树参考课件。

93（2）最优搜索路线：S0→S1→S5→S10.943.5 对于八数码问题，设初始状态和目标状态如图3.2所示：95967 5 7 6 5 97图 3.2 八数码问题98试给出深度优先（深度限制为5）和宽度优先状态图。

99[解]100(1) 深度优先（深度限制为5）状态图为101102(2)宽度优先状态图为1031043.6 什么是启发式搜索? 其中什么是评估函数? 其主要作用是什么?1053.7 最好优先的基本思想是什么? 有什么优缺点?1063.8 对于八数码问题，设初始状态和目标状态如图3.2所示。

设d (x)表示节107点x在搜索树中的深度，评估函数为f (x)=d (x)+w(x)，其中w(x)为启发式函108数。

试按下列要求给出八数码问题的搜索图，并说明满是一种A*算法，找出对109应的最优搜索路径。

110（1）w (x)=h(x)表示节点x中不在目标状态中相应位置的数码个数；111（2）w (x)=p(x)表示节点x的每一数码与其目标位置之间的距离总和。

（3）w (x)=0，情况又如何？112113[解] (1) 8数码的搜索过程如图所示：114115在上面确定h(x)时，尽管并不知道h*(x)具体为多少，但当采用单位代价时，116通过对不在目标状态中相应位置的数码个数的估计，可以得出至少需要移动h(x) 117步才能够到达目标，显然h(x)≤h*(x)。

因此它满足A*算法的要求。

最优搜索路径: 如图粗线所示。

118119(2) 此时8数码搜索图可表示为：120121这时，显然有h(x)≤p(x)≤h*(n)，相应的搜索过程也是A*算法。

然而，p(x) 122比h(n)有更强的启发式信息，由w(x)=p(x)构造的启发式搜索树，比w(x)=h(x) 123构造的启发式搜索树节点数要少。

124（3）若w(x)=0，该问题就变为宽度优先搜索问题。

3.9 如图3.3所示，是5个城市之间的交通路线图，A城市是出发地，E城市125126是目的地，两城市之间的交通费用（代价）如图中的数字，求从A到E的最小127费用交通路线。

128129130131132133134135图3.3 旅行交通图136本题是考察代价树搜索的基本概念，了解这种搜索方法与深度优先和宽度优137先的不同。

首先将旅行交通图转换为代价树如图3.4所示。

138139图3.4 交通图的代价树(1) 如果一个节点已经成为某各节点的前驱节点，则它就不能再作为该节点140141的后继节点。

例如节点B相邻的节点有A和D，但由于在代价树中，A已经作为142B的前驱节点出现，则它就不再作为B的后继节点。

143(2) 除了初始节点A外，其它节点都有可能在代价树中多次出现，为了区分144它们的多次出现，分别用下标1、2、3…标出，但它们都是图中同一节点。

例如145C1和C2都代表图中节点C。

146对上面所示的代价树做宽度优先搜索，可得到最优解为：147A→C1→D1→E2148代价为8。

由此可见，从A城市到E城市的最小费用路线为：149A→C→D→E150如果采用代价树的深度优先搜索，也会得到同样的结果：151A→C→D→E152但注意：这只是一种巧合，一般情况下，这两种方法得到的结果不一定相同。

153再者，代价树的深度优先搜索可能进入无穷分支路径，因此也是不完备的。

1543.10 对于图3.4所示的状态空间图，假设U是目标状态，试给出宽度优先搜155索与深度优搜索的OPEN表和CLOSED表的变化情况。

156157158159160161162图3.5 状态空间图163[解] 宽度优先搜索的OPEN表和CLOSED表的变化情况：1641. OPEN=[A]; CLOSED=[ ] 1652. OPEN=[B,C,D]; CLOSED=[A] 1663. OPEN=[C,D,E,F]; CLOSED=[B,A]1674. OPEN=[D,E,F,G,H]; CLOSED=[C,B, A] 1685. OPEN=[E,F,G,H,I,J]; CLOSED=[D,C,B, A] 1696. OPEN=[F,G,H,I,J,K,L]; CLOSED=[E,D,C,B,A]7. OPEN=[G,H,I,J,K,L,M]（由于L已在OPEN中）;170171CLOSED=[F,E,D,C,B,A]8. OPEN=[H,I,J,K,L,M,N]; CLOSED=[G,F,E,D,C,B,A]1721739. 以此类推，直到找到了U或OPEN=[ ]。

174深度优先搜索的OPEN表和CLOSED表的变化情况：1. OPEN=[A]; CLOSED=[ ] 1751762. OPEN=[B,C,D]; CLOSED=[A] 1773. OPEN=[E,F,C,D]; CLOSED=[B,A]1784. OPEN=[K,L,F,C,D]; CLOSED=[E,B, A] 1795. OPEN=[S,L,F,C,D]; CLOSED=[K,E,B, A] 1806. OPEN=[L,F,C,D]; CLOSED=[S,K,E,B,A]1817. OPEN=[T,F,C,D]; CLOSED=[L,S,K,E,B,A]1828. OPEN=[F,C,D]; CLOSED=[T,L,S,K,E,B,A]1839. OPEN=[M,C,D]（由于L已经在CLOSED中;184CLOSED=[F,T,L,S,K,E,B,A]18510. OPEN=[C,D]; CLOSED=[M,F,T,L,S,K,E,B,A]18611. OPEN=[G,H,D]; CLOSED=[C,M,F,T,L,S,K,E,B,A]18712. 以此类推，直到找到了U或OPEN=[ ]。

188189190第4章自动推理1911924.1什么是推理的控制策略？有哪几种主要的推理驱动模式？1934.2自然演绎推理的基本概念与基本的推理规则。

4.3 什么是合取范式? 什么是析取范式? 什么是Skolem 标准化? 如何将一个194公式化为这些形式? 1954.4 将下列公式化为Skolem 标准型: 196),,,,,(w v u z y x wP v u z y x ∃∃∃∀∀∃197 [解] 在公式中，)(x ∃的前面没有全称量词，)(u ∃的前面有全称量词)(y ∀和198)(z ∀, 在)(w ∃的前面有全称量词)(y ∀,)(z ∀和)(v ∀。

所以，在),,,,,(w v u z y x P 199中，用常数a 代替x, 用二元函数f(y,z)代替u, 用三元函数g(y,z,v)代替w,200去掉前缀中的所有存在量词之后得出Skolem 标准型： 201)),,(,),,(,,,(v z y g v z y f z y a vP z y ∀∀∀ 2024.5化为子句形有哪些步骤?203 [解] 204(1)利用等价谓词关系消去谓词公式中的蕴涵符“→ ”和双条件符“←205→ ”。

206(2)利用等价关系把否定符号“┐”移到紧靠谓词的位置上。

207(3)重新命名变元名，使不同量词约束的变元有不同的名字。

208(4)消去存在量词。

209(5)将公式化为前束形。

210(6)把公式化为Skolem 标准形。

211(7)消去全称量词。

212(9)对变元更名，使不同子句中的变元不同名。

2144.6将下列谓词公式化为子句集: 215(1) (∀x)[~P(x)∨~Q(x)]→(∃y)[S(x,y)∧Q(x)]∧(∀x)[P(x)∨B(x)] 216(2))]]](),([~))],(()([[)([y P y x Q y y x f P y P y x P x →∀∧→∀→∀ 217[解] (1) 转换过程遵照下列9个步骤依此为: 218A. 消去蕴涵符符号： 219)]()()[()]}(),()[()](~)([~){~(x B x P x x Q y x S y x Q x p x ∨∀∧∧∃∨∨∀ 220B.减少否定符号的辖域： 221)]()()[()]}(),()[()]()(){[(x B x P x x Q y x S y x Q x p x ∨∀∧∧∃∨∧∀ 222C. 变量标准化： 223)]()()[()]}(),()[()]()(){[(w B w P w x Q y x S y x Q x p x ∨∀∧∧∃∨∧∀ 224D. 消去存在量词： 225)]()()[()]}())(,([)]()(){[(w B w P w x Q x f x S x Q x p x ∨∀∧∧∨∧∀ 226E. 化为前束型： 227)]()([)]}())(,([)]()(){[)((w B w P x Q x f x S x Q x p w x ∨∧∧∨∧∀∀ 228F. 把母式化为合取范式： 229)]}()([)())](,()(){[)((w B w P x Q x f x S x p w x ∨∧∧∨∀∀ 230G. 消去全称量词： 231)]()([)())](,()([w B w P x Q x f x S x p ∨∧∧∨ 232))(,()(x f x S x p ∨ 234)(x Q 235)()(w B w P ∨ 236I. 子句变量标准化后, 最终的子句集为： 237))(,()(x f x S x p ∨ 238)(y Q 239)()(w B w P ∨ 240(2) 参见课本P122 241A. 消去蕴涵符符号： 242)]]](),([~~))],(()([~[)()[~(y P y x Q y y x f P y P y x P x ∨∀∧∨∀∨∀ 243B. 减少否定符号的辖域: 244)]]](~),([))],(()([~[)()[~(y P y x Q y y x f P y P y x P x ∧∃∧∨∀∨∀ 245C. 变量标准化: 246)]]](~),([))],(()([~[)()[~(w P w x Q w y x f P y P y x P x ∧∃∧∨∀∨∀ 247D. 消去存在量词: 248))]]]((~))(,([))],(()([~[)()[~(x g P x g x Q y x f P y P y x P x ∧∧∨∀∨∀ 249E. 化为前束型: 250))]]]((~))(,([))],(()([[~)()[~)((x g P x g x Q y x f P y P x P y x ∧∧∨∨∀∀ 251F. 把母式化为合取范式: 252))],(()(~)()[~)((y x f P y P x P y x ∨∨∀∀))]]((~)([~))](,()([~x g P x P x g x Q x P ∨∧∨∧ 253G. 消去全称量词: 254))]]((~)([~))](,()([~))],(()(~)([~x g P x P x g x Q x P y x f P y P x P ∨∧∨∧∨∨255H. 消去合取词:)),(()(~)(~y x f P y P x P ∨∨ 256))(,()(~x g x Q x P ∨ 257))((~)(~x g P x P ∨ 258I. 更改变量名: 259)),(()(~)(~11y x f P y P x P ∨∨ 260))(,()(~222x g x Q x P ∨ 261))((~)(~33x g P x P ∨ 2624.7 把下面的表达式转化成子句形式 263（1）)]()()[()]()[()]()[((x Q x P x x Q x x p x ∨∃→∃∨∃264 （2）)]],,()[()],()[)[(()]()[(z y x R z z x Q z x x P x ∀∨∀∃→∀265 （3）)]]],()[(~)],()[)[(()()[(x y R z y x Q z y x P x ∀→∀∀→∀ 266[解] 267(1) ))()()(())()()()((x Q x P x x Q x x P x ∨∃→∃∨∃ 268))()()(())()()()((x Q x P x x Q x x P x ∨∃∨∃∨∃⌝ 269))()()(())()()()((x Q x P x x Q x x P x ∨∃∨∃⌝∧∃⌝ 270))()()(())()()()((x Q x P x x Q x x P x ∨∃∨⌝∀∧⌝∀ 271))()()(())()()()((z Q z P z x Q x x P x ∨∃∨⌝∀∧⌝∀ 272))()(())()()()((a Q a P y Q y x P x ∨∨⌝∀∧⌝∀ 273)))()(())()()()((a Q a P y Q x P y x ∨∨⌝∧⌝∀∀ 274))()(())()((a Q a P y Q x P ∨∨⌝∧⌝ 275))()(())())()()((a Q a P y Q a Q a P x P ∨∨⌝∧∨∨⌝ 276则子句集为 277)}()(())()),()()({a Q a P y Q a Q a P x P S ∨∨⌝∨∨⌝= 278(2) )],,()(),())[(()()(z y x R z z x Q z x x P x ∀∨∀∃→∀ 279)]),,()(),())[(()())(((z y x R z z x Q z x x P x y ∀∨∀∃→∀∀ 280)]),,()(),())[(()()()((z y x R z z x Q z x x P x y ∀∨∀∃∨∀⌝∀281)]),,()(),())[(()())(((z y x R z z x Q z x x P x y ∀∨∀∃∨⌝∃∀ 282)]),,()(),())[(()())(((u y t R u z t Q z t x P x y ∀∨∀∃∨⌝∃∀ 283)),),(()()),(()())(()((221u y y f R u z y f Q z y f P y ∀∨∀∨⌝∀ 284)),),(()),(())(()()()((221u y y f R z y f Q y f P u z y ∨∨⌝∀∀∀ 285)),),(()),(())(((221u y y f R z y f Q y f P ∨∨⌝ 286则子句集为 287)},),(()),(())(({221u y y f R z y f Q y f P S ∨∨⌝= 288(3) )]],()()],()[)[(()()[(x y R z y x Q z y x P x ∀⌝→∀∀→∀ 289)]],()()],()[()[()()[(x y R z y x Q z y x P x ∀⌝∨∀⌝∀∨⌝∀ 290)]],()()],()[)[(()()[(x y R z y x Q z y x P x ∃∨⌝∃∀∨⌝∀ 291)]],()()],()[)[(()()[(x y R u y x Q z y x P x ∃∨⌝∃∀∨⌝∀ 292)]],(),()[()()[(x y R y x Q y x P x ∨⌝∀∨⌝∀ 293)],(),()()[)((x y R y x Q x P y x ∨⌝∨⌝∀∀ 294),(),()(x y R y x Q x P ∨⌝∨⌝ 295则子句集为 296)},(),()({x y R y x Q x P S ∨⌝∨⌝= 2974.10 求证G 是F1和F2的逻辑结论。