人工智能与知识工程课程复习题.doc

1、第 1 页“人工智能与知识工程”课程复习题一、 辨析题1. 人工智能作为一门学科，在 1956 年诞生于美国 Dartmouth 大学。 （正确）2. 英国数学家图灵 1950 年在思想（mind）杂志上发表的论文 “计算机与智力”是人工智能学科正式诞生的标志。 （错误）3. 人工智能是一门新兴的学科，对它的研究有逻辑学派、认知学派、知识工程学派等许多学派。 （正确）4. 关于人工智能研究的途径目前主要有两种观点，一种观点被称为符号主义，另一种观点被称为联结主义。 （正确）5. 谓词演算与命题演算在问题的描述和求解方面的能力是相同的。 （错误）6. 谓词逻辑只是在命题逻辑的基础上增加了谓词。

2、（错误）7. 如果两个谓词公式等价，则表明它们只是在形式上不同，其逻辑意义完全相同。（正确）8. 由推理规则产生的谓词演算公式不是永真的。 （正确）9. 由文字组成的子句未必是逻辑命题。 （错误）10. 一个谓词演算公式与它的 Skolem 标准型在逻辑上是等价的。 （错误）11. 知识表示包括一个系统，该系统提供到知识体的通路和对知识体访问的手段（亦即计算处理过程） ，知识体是存放在存储器中的数据结构。 （正确）12. 蕴涵式和产生式在表示规则性知识时，虽然形式上相同，但功能上完全不同。 （正确）13. 产生式规则就是命题逻辑或谓词逻辑中的蕴涵式。 （错误）14. 产生式知识表示方法属于陈述

3、性知识表示的观点。 （错误）15. 产生式系统中只有规则库是用来表示知识的。 （错误）16. 产生式系统的推理机不包含知识。 （错误）二、 单项选择题1. 与谓词演算公式 等价的公式是 （ B）),(),()(yxQPyxA. B. ,)(yx ),(),(yxQPC. D. ),()yx)(yx2. 与谓词演算公式 等价的命题是 （ C）(QPA. B. )xx)()(yQxPC. D. (3. 谓词演算公式 和 的最一般合一式是 （ B）),yaxP),bz第 2 页A. B. ybza, ybzax,C. D. 不可合一，所以没有最一般合一式x4. 谓词演算公式 和 的最一般合一式是 （

4、 C）),(yfP)(,afA. B. xxayf,)(C. D. 不可合一，所以没有最一般合一式yaf,)(5. 一个子句集在删除其中被包孕的子句后所得到的新子句集，与原子句集在不可满足的意义下 （ A）A. 等价 B. 不等价C. 有时等价，有时不等价 D. 是否等价不能确定6. 一个子句集在删除其中的重言式后所得到的新子句集，与原子句集在不可满足的意义下 （ A）A. 等价 B. 不等价C. 有时等价，有时不等价 D. 是否等价不能确定7. 子句集 ， （ B）),()(,)( dcTRdxTSA. 是不可满足的 B. 是可满足的C. 有时可满足，有时不可满足 D. 是否可满足不能确定8

5、. 对两个子句 和 进行消解，得到的结果是 （ B）),()x),(cA. 空子句 B. )(cRC. D. ),(dxT,dT9. 设 和 是可以归结的两个子句，在某解释下 的真值为 T，而 的真值为 F，1C2 1C2C则其归结式 在该解释下的真值 （ D）A. 为 T B. 为 FC. 既不为 T，也不为 F D. 不能确定10. 设 和 是可以消解的两个子句，在某解释下 和 的真值都为 T，则其消解式12 12在该解释下的真值 （ A）CA. 为 T B. 为 FC. 既不为 T，也不为 F D. 不能确定11. “黑色 Buick 车的引擎不能转动，并且电瓶内有电。 ”为了能够用一个

6、产生式系统检测这辆汽车的故障，应当把这些已知事实加入系统的 （ A）A. 综合数据库 B. 规则库C. 综合数据库、规则库 D. 推理机12. “蒙蒙是学龄儿童，身上有红色斑点，并且发烧。 ”为了能够用产生式系统诊断蒙第 3 页蒙所患的疾病，应当把这些事实加入系统的 （ C）A. 综合数据库和规则库 B. 规则库C. 综合数据库 D. 推理机三、 设F: ),()()(,()( yxTRyQyxPG: ,xR求证：G 是 F 的逻辑结论。证明：首先将 F 和 G 的否定化为子句集F 的子句集为 )(,)(,()(),(1 xfTyQxPfRyQxPS G 的否定的子句集为 ,2baz然后对子句

7、集 按以下过程进行归结1(1) (2) )()(,(xfRyQxP )(,)(,(xfTyQxP(3) (4) (5) )zR,ba(6) (1)与(3) 归结 )(,(yx )(zxf(7) (4)与(6) 归结 )bQ,yba(8) NIL (5)与 (7)归结由于归结出空子句，从而证明 G 是 F 的逻辑结论。四、设F1: ),()()( yxLyQxPF2: RG: )()(xx求证：G 是 F1，F 2 的逻辑结论。证明：首先将 F1，F 2 和 G 的否定化为子句集F1 的子句集为 ),()()(yxLQxPSF2 的子句集为 ,2 zaRa第 4 页G 的否定的子句集为 )(,3

8、bQRS然后对子句集 按以下过程进行归结，从中归结出空子句21(1) (2) (3) (4) (5),()()(yxLxP)(aP),()zaLR)(bR(6) (1)与(2) 归结 bQay x(7) (3)与(4) 归结 (8) (7)与(6) 归结 ),(aLzb)(bQy(9) NIL (8)与 (5)归结从而证明 G 是 F1，F 2 的逻辑结论。五、证明： )()()()()( xRTxxPxRQxP 证明：第一步：先对结论否定并与前提合并得谓词公式 GG： )()()()()()( xxxxx 第二步：将公式 G 化为子句集，可将 G 看作以下三项的合取G1： )()(RQPG2

9、： xTxG3： )()(对每一项分别求子句集G1 的子句集为 )(),(1 xRPxQSG2 的子句集为 ),(2aTPG3 的子句集为 )(3x从而得到 G 的子句集 )()(,)(,)(,)(321 xRTaPxRQSS 第三步：应用归结原理，对子句集中的子句进行归结(1) (2) (3) (4) (5) )(xP)(xP)()()()(6) (2)与(3) 归结 (7) (4)与(5)归结 )(aRaaRxa(8) NIL (6)与 (7)归结第 5 页由此得出子句集是不可满足的，即 G 是不可满足的，从而命题得证。六、证明： )()()()()( yCDyyQyCByQ 证明：第一步

10、：对结论否定并与前提合并得谓词公式G： )()()()()()( yyDyyy 第二步：将公式 G 化为子句集，可将 G 看作三项的合取，G1： )()(CBQG2： yDyG3： )()(对每一项分别求子句集G1 的子句集为 )(),(1 yCQyBSG2 的子句集为 ),(2aDG3 的子句集为 )(3y从而得到 G 的子句集 )()(,)(,)(,)(321 xCDaQyCBQSS 第三步：应用归结原理，对子句集中的子句进行归结(1) (2) (3) (4) )(yB)(y)()(5) (6) (2)与(3)归结 (7) xCD)(ayaa(4)与(5)归结为 (8) NIL (6)与(

11、7)归结由此得出子句集是不可满足的，即 G 是不可满足的，从而命题得证。七、已知：(1) John 是贼；(2) Paul 喜欢酒和奶酪；(3) 如果 Paul 喜欢某物，则 John 也喜欢某物；(4) 如果某人是贼，而且他喜欢某物，则他就可能会偷窃某物。试用归结原理求取问题“John 可能会偷窃什么？” 的答案。解：第一步：定义谓词，将已知条件用谓词公式表示出来，并化成子句集。(1) 定义谓词第 6 页表示 是贼； 表示 喜欢 ； 表示 可能会盗窃 。)(xthief ),(yxlikey),( yxstealmy(2) 将已知条件表示成谓词公式F1： )(JontiefF2： ),(,c

12、hesPaullikwPaullkF3： )()( xJonxiexF4： ),( ),(yxstealmylikethfy(3) 将谓词公式化为子句集得 ),( ),()( ),(),(,1 vustelyvuliketief xJohnlikexPaulikechPiwnPalJonS第二步：把问题用谓词公式表示出来，并将其否定与谓词 作析取得)(wANSWERG： )(),( ANSWERJohnstealmy第三步：将谓词公式 G 化为子句集 2)(),( 2 wJstelyS将 与 合并得1 21S第四步：应用归结原理对子句集中的子句进行归结(1) (2) (3) (4) )(Joh

13、ntief ),(inePaullik ),(chesPaullik(4) (5) ),(,xliexPaulk ,( ),( vtmyvthf( wANSWERJstmy(6) (1)与(4) 归结为 ), ), vJonstealyvohnlike uJohn(7) (2)与(4) 归结 (wiJ xie(8) (3)与(4) 归结 ),ceslik chs(9) (7)与(6) 归结 (inJohtalmy vwine(10) (8)与(6) 归结 ),cesse cs第 7 页(11) (9)与(5) 归结 )(wineANSWERwine(12) (10)与(5) 归结 chschs

14、第五步：得到了归结式 和 ，因此答案是 John 可能)(ieASER)(eANSWER会盗窃 wine 和 cheese。八、已知：(1) 任何人的兄弟不是女性；(2) 任何人的姐妹必是女性；(3) Mary 是 Bill 的姐妹。试用归结原理证明：Mary 不是 Bill 的兄弟。证明：第一步：定义谓词，将待证明的问题的前提条件和结论用谓词公式表示出来。(1) 定义谓词：表示 是 的兄弟； 表示 是 的姐妹； 表示),(yxbrothey),(yxsiter )(xfemal是女性。(2) 将待证明问题的前提条件和结论表示成谓词公式：F1： )(),()( xfemalyxbrotheyx

15、F2： siF3： ),(BlMaryiteG： iboh第二步：将 F1，F 2，F 3 和 G 的否定分别化成对应的子句F1 对应的子句： )(),(xfemalyxrteF2 对应的子句： siF3 对应的子句： ),(BilMaryteG 的否定对应的子句： ,ilboh第三步：应用归结原理，对由以上子句所组成的子句集进行归结(1) (2) )(),(xfemalyxbrothe)(),(xfemalyxsitr(3) (4) BilMasi BlMbroth(5) (1)与(4) 归结 )(ryfel ,yilxar第 8 页(6) (2)与(3)归结 )(Maryfeml ,yBi

16、lxMar(8) NIL (5)与 (6)归结这样就由于否定结论“Mary 不是 Bill 的兄弟”而推出了矛盾，从而证明原来的结论是正确的。九、已知三个柱子 1，2，3 和二个盘子 A，B（A 比 B 小） 。初始状态下，A ，B依次放在 1 柱上。目标状态是 A，B 依次放在 3 柱上。条件是每次只可移动一个盘子，盘子上方是空时方可移动，而且任何时候都不允许大盘在小盘之上。试用状态空间表示该二阶 Hanoi 塔问题，并通过状态空间图求出该二阶 Hanoi 塔问题的盘移动次数最少的最优解。解：首先按以下步骤将问题以状态空间的形式表示出来。第一步，定义问题的状态描述形式。设用 表示问题的状态，

17、 表示盘),(BAkkSAkS子 A 所在的柱号， 表示盘子 B 所在的柱号。BkS第二步，用所定义的状态描述形式把问题的所有可能状态都表示出来，并确定出问题的初始状态集合描述和目标状态集合描述。本问题所有可能的状态共有 9 种，各状态的形式描述如下：)1,(0S)2,(S)3,1(S)1,2(S)2 ,(4S325678问题的初始状态集合为 ，目标状态集合为 。0 G第三步，定义一组算符。定义算符 表示把盘子 A 从第 i 号柱子移到第 j 号柱子的),(jiA操作；算符 表示把盘子 B 从第 i 号柱子移到第 j 号柱子的操作。这样定义的算符),(jiB组 中共有 12 个算符，它们分别是

18、F)2,1(A)3,()1,2()3,()1,()2 ,3(B至此，该问题的状态空间 构造完成。这就完成了对问题的状态空间表示。),(GFS然后，根据该状态空间的 9 种可能和 12 种算符，构造它的状态空间图。其状态空间图如下图所示。第 9 页在状态空间图中，从初始节点 （状态 ）到目标节点 （状态 ）的任何一)1 ,(0S)3 ,(8S条通路都是问题的一个解。但其中最短路径的长度是 3，它由三个算符 ，)2 ,1(A和 组成，这就是盘移动次数最少的最优解。)3 ,1(B) ,2(A十、根据下面的事实构造一个产生式系统的规则库和数据库，并分别运用正向推理方式和反向推理方式结合规则排序控制策略

19、，给出问题“李先生会出交通事故吗？”的答案。要求说明用这两种推理方式解答问题的过程。(1) 35 岁到 55 岁的人是中年人；(2) 中年人是老练而细心的；(3) 老练、细心并有驾驶技术的人是不会出交通事故的；(4) 李先生 43 岁，并有驾驶技术；(5) 李太太 35 岁；(6) 李公子 12 岁。解：产生式系统的规则库 R 包含以下三条规则R1：如果 x 是 35 岁到 55 岁，则 x 是中年人；R ：如果 x 是中年人，则 x 是老练而细心的；R ：如果 x 是老练、细心并有驾驶技术的，则 x 是不会出交通事故的；初始状态下产生式系统的综合数据库 F 包含以下事实：F1：李先生 43

20、岁，并有驾驶技术；F2：李太太 35 岁；F3：李公子 12 岁；正向推理方式求解问题的过程如下：根据综合数据库中的事实在 R 中找出匹配规则 R1，执行 R1 得到新的事实“李先生是中年人，并有驾驶技术” ，将新的事实作为 F4 加入综合数据库中。根据综合数据库中的事实在 R 中找出匹配规则 R1，R 2，执行 R1 得到新的事实“李太太是中年人” ，将新的事实作为 F5 加入综合数据库中。根据综合数据库中的事实在 R 中找出匹配规则 R2，执行R2 得到新的事实“李先生是老练而细心的，并有驾驶技术” ，将新的事实作为 F6 加入综1, 12, 1 3, 12, 3 3, 23, 3 1,

21、3 1, 2 2, 2图 二阶 Hanoi 塔问题的状态空间图第 10 页合数据库中。根据综合数据库中的事实在 R 中找出匹配规则 R2，执行 R2 得到新的事实“李太太是老练而细心的” ，将新的事实作为 F7 加入综合数据库中。根据综合数据库中的事实在 R 中找出匹配规则 R3，执行 R3 得到新的事实“李先生是不会出交通事故的” ，将新的事实作为 F8 加入综合数据库中。此时，综合数据库中已包含问题的答案，因此过程结束。反向推理方式求解问题的过程如下：用目标事实“李先生不会出交通事故”与规则库中规则的后件进行匹配，得到匹配规则R 。由于 R 的前件不是已知事实，因此将前件作为子目标再与规则库中规则的后件进行匹配，得到匹配规则 R2。由于 R2 的前件还不是已知事实，因此将其作为子目标再与规则库中规则的后件进行匹配，得到匹配规则 R1。由于 R1 的前件是已知事实，从而推理过程结束，得出问题的答案“李先生不会出交通事故” 。