大学课程《人工智能》课后习题及答案.pdf 35页

'大学课程《人工智能》课后答案第一章课后习题1、对N＝5、k≤3时，求解传教士和野人问题的产生式系统各组成部分进行描述（给出综合数据库、规则集合的形式化描述，给出初始状态和目标条件的描述），并画出状态空间图。2、对量水问题给出产生式系统描述，并画出状态空间图。有两个无刻度标志的水壶，分别可装5升和2升的水。设另有一水缸，可用来向水壶灌水或倒出水，两个水壶之间，水也可以相互倾灌。已知5升壶为满壶，2升壶为空壶，问如何通过倒水或灌水操作，使能在2升的壶中量出一升的水来。3、对梵塔问题给出产生式系统描述，并讨论N为任意时状态空间的规模。相传古代某处一庙宇中，有三根立柱，柱子上可套放直径不等的N个圆盘，开始时所有圆盘都放在第一根柱子上，且小盘处在大盘之上，即从下向上直径是递减的。和尚们的任务是把所有圆盘一次一个地搬到另一个柱子上去（不许暂搁地上等），且小盘只许在大盘之上。问和尚们如何搬法最后能完成将所有的盘子都移到第三根柱子上（其余两根柱子，有一根可作过渡盘子使用）。求N＝2时，求解该问题的产生式系统描述，给出其状态空间图。讨论N为任意时，状态空间的规模。4、对猴子摘香蕉问题，给出产生式系统描述。一个房间里，天花板上挂有一串香蕉，有一只猴子可在房间里任意活动（到处走动，推移箱子，攀登箱子等）。设房间里还有一只可被猴子移动的箱子，且猴子登上箱子时才能摘到香蕉，问猴子在某一状态下（设猴子位置为a，箱子位置为b，香蕉位置为c），如何行动可摘取到香蕉。5、对三枚钱币问题给出产生式系统描述及状态空间图。设有三枚钱币，其排列处在"正、正、反"状态，现允许每次可翻动其中任意一个钱币，问只许操作三次的情况下，如何翻动钱币使其变成"正、正、正"或"反、反、反"状态。6、说明怎样才能用一个产生式系统把十进制数转换为二进制数，并通过转换141.125这个数为二进制数，阐明其运行过程。7、设可交换产生式系统的一条规则R可应用于综合数据库D来生成出D"，试证明若R存在逆，则可应用于D"的规则集等同于可应用于D的规则集。8、一个产生式系统是以整数的集合作为综合数据库，新的数据库可通过把其中任意一对元素的乘积添加到原数据库的操作来产生。设以某一个整数子集的出现作为目标条件，试说明该产生式系统是可交换的。第二章课后习题 第二章课后习题1、用回溯策略求解如下所示二阶梵塔问题，画出搜索过程的状态变化示意图。对每个状态规定的操作顺序为：先搬1柱的盘，放的顺序是先2柱后3柱；再搬2柱的盘，放的顺序是先3柱后1柱；最后搬3柱的盘，放的顺序是先1柱后2柱。2、滑动积木块游戏的棋盘结构及某一种将牌的初始排列结构如下：其中B表示黑色将牌，W表示白色将牌，E表示空格。游戏的规定走法是：（1）任意一个将牌可以移入相邻的空格，规定其耗散值为1；（2）任意一个将牌可相隔1个或2个其他的将牌跳入空格，规定其耗散值等于跳过将牌的数目；游戏要达到的目标是使所有白将牌都处在黑将牌的左边（左边有无空格均可）。对这个问题，定义一个启发函数h(n)，并给出利用这个启发函数用算法A求解时所产生的搜索树。你能否辨别这个h(n)是否满足下界范围？在你的搜索树中，对所有的节点满足不满足单调限制？3、对1.4节中的旅行商问题，定义两个h函数（非零），并给出利用这两个启发函数用算法A求解1.4节中的五城市问题。讨论这两个函数是否都在h*的下界范围及求解结果。4、2.1节四皇后问题表述中，设应用每一条规则的耗散值均为1，试描述这个问题h*函数的一般特征。你是否认为任何h函数对引导搜索都是有用的？5、对N＝5，k≤3的M－C问题，定义两个h函数（非零），并给出用这两个启发函数的A算法搜索图。讨论用这两个启发函数求解该问题时是否得到最佳解。6、证明OPEN表上具有f(n)＜f*(s)的任何节点n，最终都将被A*选择去扩展。7、如果算法A*从OPEN表中去掉任一节点n，对n有f(n)＞F（F＞f*(s)），试说明为什么算法A*仍然是可采纳的。8、用算法A逆向求解图2.7中的八数码问题，评价函数仍定义为f(n)=d(n)+w(n)。逆向搜索在什么地方和正向搜索相会。 9、讨论一个h函数在搜索期间可以得到改善的几种方法。10、四个同心圆盘的扇区数字如图所示，每个圆盘可单独转动。问如何转动圆盘使得八个径向的4个数字和均为12。第三章课后习题1、数字重写问题的变换规则如下：6→3，34→3，16→4，23→2，14→2，22→1，1问如何用这些规则把数字6变换成一个由若干个1组成的数字串。试用算法AO*进行求解，并给出搜索图。求解时设k-连接符的耗散值是k个单位，h函数值规定为：h（1）＝0，h（n）＝n（n≠1）。2、余一棋的弈法如下：两棋手可以从5个钱币堆中轮流拿走一个、两个或三个钱币，拣起最后一个钱币者算输。试通过博弈证明，后走的选手必胜，并给出一个简单的特征标记来表示取胜策略。3、对下图所示的博弈树，以优先生成左边节点顺序来进行α-β搜索，试在博弈树上给出何处发生剪枝的标记，并标明属于α剪枝还是β剪枝。 4、AO*算法中，第7步从S中选一个节点，要求其子孙不在S中出现，讨论应如何实现对S的控制使得能有效地选出这个节点。如下图所示，若E的耗散值发生变化时，所提出的对S的处理方法应能正确工作。5、如何修改AO*算法使之能处理出现回路的情况。如下图所示，若节点C的耗散值发生变化时，所修改的算法能正确处理这种情况。6、对3×3的一字棋，设用+1和-1分别表示两选手棋子的标记，用0表示空格，试给出一字棋产生式系统的描述。7、写一个α-β搜索的算法。8、用一个9维向量C来表示一字棋棋盘的格局，其分量根据相应格内的×，空或○的标记分别用+1，0，或-1来表示。试规定另一个9维向量W，使得点积C·W可作为MAX选手（棋子标记为×）估计非终端位置的一个有效的评价函数。用这个评价函数来完成几步极小-极大搜索，并分析该评价函数的效果。 第四章课后习题1、化下列公式成子句形式：（1）（x）[P（x）→P（x）]（2）{~{（x）P（x）}}→（x）[~P（x）]（3）~（x）{P（x）→{（y）[P（y）→P（f（x，y））]∧~（y）[Q（x，y）→P（y）]}}（4）（x）（y）{[P（x，y）→Q（y，x）]∧[Q（y，x）→S（x，y）]}→（x）（y）[P（x，y）→S（x，y）]2、以一个例子证明置换的合成是不可交换的。3、找出集{P（x，z，y），P（w，u，w），P（A，u，u）}的mgu。4、说明下列文字集不能合一的理由：（1）{P（f（x，x），A），P（f（y，f（y，A）），A）}（2）{~P（A），P（x）}（3）{P（f（A），x），P（x，A）}5、已知两个子句为Loves（father（a），a）~Loves（y，x）∨Loves（x，y）试用合一算法求第一个子句和第二个子句的第一个文字合一时的结果。6、用归结反演法证明下列公式的永真性：（1）（x）{[P（x）→P（A）]∧[P（x）→P（B）]}（2）（z）[Q（z）→P（z）]→{（x）[Q（x）→P（A）]∧[Q（x）→P（B）]}（3）（x）（y）{[P（f（x））∧Q（f（B））]→[P（f（A））∧P（y）∧Q（y）]}（4）（x）（y）P（x，y）→（y）（x）P（x，y）（5）（x）{P（x）∧[Q（A）∨Q（B）]}→（x）[P（x）∧Q（x）]7、以归结反演法证明公式（x）P（x）是[P（A1）∨P（A2）]的逻辑推论，然而，（x）P（x）的Skolem形即P（A）并非[P（A1）∨P（A2）]的逻辑推论，请加以证明。8、给定下述语句：Johnlikesallkindsoffood.Applesarefood.Anythinganyoneeatsandisn"tkilledbyisfood. Billeatspeanutsandisstillalive.SueeatseverythingBilleats.（1）用归结法证明"Johnlikespeanuts。"（2）用归结法提取回答"WhatfooddoesSueeat?"9、已知事实公式为（（x）（y）（z）（Gt（x，y）∧Gt（y，z）→Gt（x，z））（u）（v）（Succ（u，v）→Gt（u，v）（x）（~Gt（x，x））求证Gt（5，2）试判断下面的归结过程是否正确？若有错误应如何改进：10、设公理集为（u）LAST（cons（u，NIL），u）（cons是表构造函数）（x）（y）（z）（LAST（y，z）→LAST（cons（x，y），z））（LAST（x，y）代表y是表x的最末元素）（1）用归结反演法证明如下定理：（v）LAST（cons（2，cons（1，NIL）），v）（2）用回答提取过程求表（2，1）的最末元素v。（3）简要描述如何使用这个方法求长表的最末元素。11、对一个基于规则的几何定理证明系统，把下列语句表示成产生式规则：（1）两个全等的三角形的对应角相等。（2）两个全等的三角形的对应边相等。 （3）如果两个三角形对应边是相等的，则这两个三角形全等。（4）一个等腰三角形的底角是相等的。12、我们来考虑下列一段知识：Tony、Mike和John属于Alpine俱乐部，Alpine俱乐部的每个成员不是滑雪运动员就是一个登山运动员，登山运动员不喜欢雨而且任一不喜欢雪的人不是滑雪运动员，Mike讨厌Tony所喜欢的一切东西，而喜欢Tony所讨厌的一切东西，Tony喜欢雨和雪。以谓词演算语句的集合表示这段知识，这些语句适合一个逆向的基于规则的演绎系统。试说明这样一个系统怎样才能回答问题"有没有Alpine俱乐部的一个成员，他是一个登山运动员但不是一个滑雪运动员呢？"13、一个积木世界的状态由下列公式集描述：ONTABLE（A）CLEAR（E）ONTABLE（C）CLEAR（D）ON（D，C）HEAVY（D）ON（B，A）WOODEN（B）HEAVY（B）ON（E，B）绘出这些公式所描述的状态的草图。下列语句提供了有关这个积木世界的一般知识：每个大的蓝色积木块是在一个绿色积木块上。每个重的木制积木块是大的。所有顶上没有东西的积木块都是蓝色的。所有木制积木块是蓝色的。以具有单文字后项的蕴涵式的集合表示这些语句。绘出能求解"哪个积木块是在绿积木块上"这个问题的一致解图（用B规则）。答案第一章课后习题答案说明：由于人工智能的很多题目都很灵活，以下解答仅供参考。第1题答：1，综合数据库定义三元组：（m,c,b）其中：，表示传教士在河左岸的人数。 ，表示野人在河左岸的认输。，b=1，表示船在左岸，b=0，表示船在右岸。2，规则集规则集可以用两种方式表示，两种方法均可。第一种方法：按每次渡河的人数分别写出每一个规则，共(30)、(03)、(21)、(11)、(10)、(01)、(20)、(02)八种渡河的可能（其中(xy)表示x个传教士和y个野人上船渡河），因此共有16个规则（从左岸到右岸、右岸到左岸各八个）。注意：这里没有(12)，因为该组合在船上的传教士人数少于野人人数。规则集如下：r1：IF(m,c,1)THEN(m-3,c,0)r2：IF(m,c,1)THEN(m,c-3,0)r3：IF(m,c,1)THEN(m-2,c-1,0)r4：IF(m,c,1)THEN(m-1,c-1,0)r5：IF(m,c,1)THEN(m-1,c,0)r6：IF(m,c,1)THEN(m,c-1,0)r7：IF(m,c,1)THEN(m-2,c,0)r8：IF(m,c,1)THEN(m,c-2,0)r9：IF(m,c,0)THEN(m+3,c,1)r10：IF(m,c,0)THEN(m,c+3,1)r11：IF(m,c,0)THEN(m+2,c+1,1)r12：IF(m,c,0)THEN(m+1,c+1,1)r13：IF(m,c,0)THEN(m+1,c,1)r14：IF(m,c,0)THEN(m,c+1,1)r15：IF(m,c,0)THEN(m+2,c,1)r16：IF(m,c,0)THEN(m,c+2,1)第二种方法：将规则集综合在一起，简化表示。规则集如下：r1：IF(m,c,1)and0=jori=0)THEN(m-i,c-j,0)r2：IF(m,c,0)and0=jori=0)THEN(m+i,c+j,1)3，初始状态：(5,5,1)4，结束状态：(0,0,0)第2题答：1，综合数据库定义两元组：（L5,L2）其中：0<=L5<=5，表示容量为5升的壶的当前水量。0<=L2<=2，表示容量为2升的壶的当前水量。2，规则集r1：IF(L5,L2)THEN(5,L2)/*将L5灌满水*/r2：IF(L5,L2)THEN(L5,2)/*将L2灌满水*/ r3：IF(L5,L2)THEN(0,L2)/*将L5水到光*/r4：IF(L5,L2)THEN(L5,0)/*将L2水到光*/r5：IF(L5,L2)andL5+L2<=5THEN(L5+L2,0)/*L2到入L5中*/r6：IF(L5,L2)andL5+L2>5THEN(5,L5+L2-5)/*L2到入L5中*/r7：IF(L5,L2)andL5+L2<=2THEN(0,L5+L2)/*L5到入L2中*/r8：IF(L5,L2)andL5+L2>5THEN(L5+L2-2,2)/*L5到入L2中*/3，初始状态：(5,0)4，结束条件：(x,1)，其中x表示不定。当然结束条件也可以写成：(0,1)第3题答：1，综合数据库定义三元组：(A,B,C)其中A,B,C分别表示三根立柱，均为表，表的元素为1～N之间的整数，表示N个不同大小的盘子，数值小的数表示小盘子，数值大的数表示大盘子。表的第一个元素表示立柱最上面的柱子，其余类推。2，规则集为了方便表示规则集，引入以下几个函数：first(L)：取表的第一个元素，对于空表，first得到一个很大的大于N的数值。tail(L)：取表除了第一个元素以外，其余元素组成的表。cons(x,L)：将x加入到表L的最前面。规则集：r1:IF(A,B,C)and(first(A)f*(s)的节点，不会被A*所扩展。所以如果从OPEN表中去掉f(n)>f*(s)的节点，不会影响A*的可采纳性。而F是f*(s)的上界范围，因此去掉f(n)>F的节点也同样不会影响A*的可采纳性。第8题提示：对于8数码问题，逆向搜索和正向搜索是完全一样的，只是把目标状态和初始状态对调就可以了。第9题提示：在搜索期间改善h函数，是一种动态改变h函数的方法。像改进的A*算法中，对NEST中的节 点按g值的大小选择待扩展的节点，相当于令这些节点的h＝0，就是动态修改h函数的一种方法。由定理6，当h满足单调条件时，A*所扩展的节点序列，其f是非递减的。对于任何节点i，j，如果j是i的子节点，则有f(i)≤f(j)。利用该性质，我们可以提出另一种动态修改h函数的方法：f(j)=max(f(i),f(j))以f(j)作为节点j的f值。f值的改变，隐含了h值的改变。当h不满足单调条件时，经过这样修正后的h具有一定的单调性质，可以减少重复节点的可能性。第10题提示：很多知识对求解问题有好处，这些知识并不一定要写成启发函数的形式，很多情况下，也不一定能清晰的写成一个函数的形式。为了叙述方便，我们将两个相对的扇区称为相对扇区，图中阴影部分的扇区称为阴影扇区，非阴影部分的扇区称为非阴影扇区。由题意，在目标状态下，一个扇区的数字之和等于12，一个相对扇区的数字之和等于24，而一个阴影扇区或者非阴影扇区的数字之和为48。为此，我们可以将目标进行分解，首先满足阴影扇区的数字之和为48（这时非阴影部分的数字和也一定为48）。为了这个目标我们可以通过每次转o动圆盘45实现。在第一个目标被满足的情况下，我们再考虑第二个目标：每一个相对扇区的数字和为24。o在实现这个目标的过程中，我们希望不破坏第一个目标。为此我们采用转动90的方式实现，这样即可以调整相对扇区的数字和，又不破坏第一个目标。在第二个目标实现之后，我们就可以实现最终目标：扇区o内的数字和为12。同样我们希望在实现这个目标的时候，不破坏前两个目标。为此我们采用转动180的方式实现。这样同样是即可以保证前两个目标不被破坏，又可以实现第三个目标。经过这样的分析以后，我们发现该问题就清晰多了。当然，是否每一个第一、第二个目标的实现，都能够实现第三个目标呢？有可能不一定。在这种情况下，就需要在发现第三个目标不能实现时，重新试探其他的第一、第二个目标。第三章课后习题答案说明：由于人工智能的很多题目都很灵活，以下解答仅供参考。第1题答：此题要求按照课中例题的方式，给出算法，以下是每个循环结束时的搜索图。 上面这种做法比较简单，也可以如下做： 第2题答：从该搜索图可以看出，无论先走者选择哪个走步，后走者都可以走到标记为A的节点，该节点只剩下一枚钱币，所以先走者必输。对于一般的具有n个钱币的情况，当n＝4×m＋1时，后走者存在取胜策略。因为后走者可以根据先走者的走法，选择自己的走法，使得双方拿走的钱币数为4，这样经过m个轮回后，共拿走了4×m个钱币，只剩下了一枚钱币，而此时轮到先走者走棋。所以在这种情况下，后走者存在取胜的策略。对于钱币数不等于4×m＋1的情况，先走者可以根据实际的钱币数选择取走的钱币数，使得剩下的钱币数为4×m＋1个，此时先走者相当于4×m＋1个钱币时的后走者了。因此在这种情况下，先走者存在获胜的策略。第3题答： 第四章课后习题答案第1题答：（1）(x)[P(x)→P(x)](x)[~P(x)∨P(x)]{~P(x)∨P(x)}（2）{~{(x)P(x)}}→(x)[~P(x)]{(x)P(x)}∨(x)[~P(x)]{(x)P(x)}∨(y)[~P(y)](x)(y)[P(x)∨~P(y)]{P(x)∨~P(f(a))}（3）~(x){P(x)→{(y)[P(y)→P(f(x，y))]∧~(y)[Q(x，y)→P(y)]}}~(x){P(x)→{(y)[~P(y)∨P(f(x，y))]∧~(y)[~Q(x，y)∨P(y)]}}~(x){P(x)→{(y)[~P(y)∨P(f(x，y))]∧(y)[Q(x，y)∧~P(y)]}}~(x){P(x)→{(y)[~P(y)∨P(f(x，y))]∧(z)[Q(x，z)∧~P(z)]}}~(x){~P(x)∨{(y)[~P(y)∨P(f(x，y))]∧(z)[Q(x，z)∧~P(z)]}}(x){P(x)∧{(y)[P(y)∧~P(f(x，y))]∨(z)[~Q(x，z)∨P(z)]}}(x)(y)(z){P(x)∧{[P(y)∧~P(f(x，y))]∨[~Q(x，z)∨P(z)]}}(x)(y)(z){P(x)∧[P(y)∨~Q(x，z)∨P(z)]∧[~P(f(x，y))∨~Q(x，z)∨P(z)]}{P(a)∧[P(b)∨~Q(a，z)∨P(z)]∧[~P(f(a，b))∨~Q(a，z)∨P(z)]}{P(a),P(b)∨~Q(a，z1)∨P(z1),~P(f(a，b))∨~Q(a，z2)∨P(z2)}（4）(x)(y){[P(x，y)→Q(y，x)]∧[Q(y，x)→S(x，y)]}→(x)(y)[P(x，y)→S(x，y)] (x)(y){[P(x，y)→Q(y，x)]∧[Q(y，x)→S(x，y)]}→(x)(y)[P(x，y)→S(x，y)](x)(y){[~P(x，y)∨Q(y，x)]∧[~Q(y，x)∨S(x，y)]}→(u)(v)[~P(u，v)∨S(u，v)]~{(x)(y){[~P(x，y)∨Q(y，x)]∧[~Q(y，x)∨S(x，y)]}}∨(u)(v)[~P(u，v)∨S(u，v)](x)(y){[P(x，y)∧~Q(y，x)]∨[Q(y，x)∧~S(x，y)]}∨(u)(v)[~P(u，v)∨S(u，v)](x)(y)(u)(v){[P(x，y)∧~Q(y，x)]∨[Q(y，x)∧~S(x，y)]}∨[~P(u，v)∨S(u，v)](x)(y)(u)(v){[P(x，y)∨Q(y，x)]∧[P(x，y)∨~S(x，y)]∧[~Q(y，x)∨~S(x，y)]}∨[~P(u，v)∨S(u，v)](x)(y)(u)(v)[P(x，y)∨Q(y，x)∨~P(u，v)∨S(u，v)]∧[P(x，y)∨~S(x，y)∨~P(u，v)∨S(u，v)]∧[~Q(y，x)∨~S(x，y)∨~P(u，v)∨S(u，v)][P(a，y)∨Q(y，a)∨~P(f(y)，v)∨S(f(y)，v)]∧[P(a，y)∨~S(a，y)∨~P(f(y)，v)∨S(f(y)，v)]∧[~Q(y，a)∨~S(a，y)∨~P(f(y)，v)∨S(f(y)，v)]{P(a，y1)∨Q(y1，a)∨~P(f(y1)，v)∨S(f(y1)，v),P(a，y2)∨~S(a，y2)∨~P(f(y2)，v2)∨S(f(y2)，v2),~Q(y3，a)∨~S(a，y3)∨~P(f(y3)，v3)∨S(f(y3)，v3)}第2题答：设有两个置换s1={a/x}和s2={x/y}，合适公式P(x,y)。则：P(x,y)s1s2=P(a,x)P(x,y)s2s1=P(a,a)二者不相等。所以说，置换的合成是不可交换的。第3题答：{A/x,A./y,A/z,A/w,A/u}第4题答：（1）{P(f(x，x)，A)，P(f(y，f(y，A))，A)}在合一时，f(x,x)要与f(y,f(y,a))进行合一，x置换成y后，y要与f(y,a)进行合一，出现了嵌套的情况，所以不能进行合一。（2）{~P（A），P（x）}一个是谓词P，一个是P的反，不能合一。（3）{P（f（A），x），P（x，A）}在合一的过程中，x置换为f(A)，而f(A)与A不能合一。第5题答：略第6题答：（1）（x）{[P（x）→P（A）]∧[P（x）→P（B）]}目标取反化子句集：~（x）{[P（x）→P（A）]∧[P（x）→P（B）]}~（x）{[~P（x）∨P（A）]∧[~P（x）∨P（B）]}（x）{[P（x）∧~P（A）]∨[P（x）∧~P（B）]}（x）{[P（x）∧~P（A）]∨P（x）}∧{[P（x）∧~P（A）]∨~P（B）}} （x）{P（x）∧[~P（A）∨P（x）]∧[P（x）∨~P（B）]∧[~P（A）∨~P（B）]}P（x）∧[~P（A）∨P（x）]∧[P（x）∨~P（B）]∧[~P（A）∨~P（B）]得子句集：1,P(x1)2,~P(A)∨P{x2}3,P(x3)∨~P(B)4,~P(A)∨~P(B)（2）（z）[Q（z）→P（z）]→{（x）[Q（x）→P（A）]∧[Q（x）→P（B）]}目标取反化子句集：~{(z)[Q(z)→P(z)]→{(x)[Q(x)→P(A)]∧[Q(x)→P(B)]}}~{(z)[~Q(z)∨P(z)]→{(x)[~Q(x)∨P(A)]∧[~Q(x)∨P(B)]}}~{~{(z)[~Q(z)∨P(z)]}∨{(x)[~Q(x)∨P(A)]∧[~Q(x)∨P(B)]}}(z)(x){[~Q(z)∨P(z)]∧{[Q(x)∧~P(A)]∨[Q(x)∧~P(B)]}}(z)(x){[~Q(z)∨P(z)]∧{Q(x)∧[Q(x)∨~P(B)]∧[~P(A)∨Q(x)]∧[~P(A)∨~P(B)]}[~Q(z)∨P(z)]∧Q(x)∧[Q(x)∨~P(B)]∧[~P(A)∨Q(x)]∧[~P(A)∨~P(B)]得子句集：1,~Q(z)∨P(z)2,Q(x2)3,Q(x3)∨~P(B)4,~P(A)∨Q(x4)5,~P(A)∨~P(B) （3）（x）（y）{[P（f（x））∧Q（f（B））]→[P（f（A））∧P（y）∧Q（y）]}目标取反化子句集：~(x)(y){[P(f(x))∧Q(f(B))]→[P(f(A))∧P(y)∧Q(y)]}~(x)(y){~[P(f(x))∧Q(f(B))]∨[P(f(A))∧P(y)∧Q(y)]}(x)(y){[P(f(x))∧Q(f(B))]∧[~P(f(A))∨~P(y)∨~Q(y)]}P(f(x))∧Q(f(B))∧[~P(f(A))∨~P(y)∨~Q(y)]得子句集：1，P(f(x1))2，Q(f(B))3，~P(f(A))∨~P(y3)∨~Q(y3)（4）（x）（y）P（x，y）→（y）（x）P（x，y）目标取反化子句集：~{(x)(y)P(x，y)→(y)(x)P(x，y)}~{~[(x)(y)P(x，y)]∨(y)(x)P(x，y)}~{~[(x)(y)P(x，y)]∨(v)(u)P(u，v)} [(x)(y)P(x，y)]∧(v)(u)~P(u，v)(x)(y)(v)(u)P(x，y)]∧~P(u，v)P(a，y)∧~P(u，f(y))得子句集：1，P(a，y1)2，~P(u，f(y2))（5）（x）{P（x）∧[Q（A）∨Q（B）]}→（x）[P（x）∧Q（x）]目标取反化子句集：~{(x){P(x)∧[Q(A)∨Q(B)]}→(x)[P(x)∧Q(x)]}~{~{(x)P(x)∧[Q(A)∨Q(B)]}∨(x)[P(x)∧Q(x)]}{(x)P(x)∧[Q(A)∨Q(B)]}∧(x)[~P(x)∨~Q(x)]}{(x)P(x)∧[Q(A)∨Q(B)]}∧(y)[~P(y)∨~Q(y)]}(x)(y){P(x)∧[Q(A)∨Q(B)]∧[~P(y)∨~Q(y)]}P(x)∧[Q(A)∨Q(B)]∧[~P(y)∨~Q(y)]得子句集：1，P(x)2，Q(A)∨Q(B)3，~P(y)∨~Q(y) 第7题答：（1）将（x）P（x）取反化为子句：~（x）P（x）=（x）~P（x）与条件[P（A1）∨P（A2）]合在一起得子句集：{~P（x）,P（A1）∨P（A2）}所以，公式（x）P（x）是[P（A1）∨P（A2）]的逻辑推论。（2）对于（x）P（x）的Skolem形，即P（A），取反后为~P（A），与条件[P（A1）∨P（A2）]合在一起得子句集：{~P（A）,P（A1）∨P（A2）}该子句集不能进行归结，故P（A）不是[P（A1）∨P（A2）]的逻辑推论。第8题答：该问题用谓词公式描述如下：已知：（1）(x){Food(x)→Like(John,x)}（2）Food(Apple)（3）(x)(y){[Eat(y,x)∧~Kill(x,y)]→Food(x)}（4）Eat(Bill,Peanut)∧~Kill(Penut,Bill)（5）(x){Eat(Bill,x)→Eat(Sue,x)}目标1：Like(John,Peanut)目标2：(x)Food(x)∧Eat(Sue,x)已知条件化子句集：（1）(x){Food(x)→Like(John,x)}=(x){~Food(x)∨Like(John,x)}=>{~Food(x)∨Like(John,x)}（2）Food(Apple)（3）(x)(y){[Eat(y,x)∧~Kill(x,y)]→Food(x)}=(x)(y){~[Eat(y,x)∧~Kill(x,y)]∨Food(x)} =(x)(y){~[Eat(y,x)∨Kill(x,y)]∨Food(x)}=>{~Eat(y,x)∨Kill(x,y)∨Food(x)}（4）Eat(Bill,Peanut)∧~Kill(Penut,Bill)=>{Eat(Bill,Peanut),~Kill(Penut,Bill)}（5）(x){Eat(Bill,x)→Eat(Sue,x)}=(x){~Eat(Bill,x)∨Eat(Sue,x)}=>~Eat(Bill,x)∨Eat(Sue,x)目标1取反化子句集：~Like(John,Peanut)目标2取反化子句集：~{(x)Food(x)∧Eat(Sue,x)}=(x)~Food(x)∨~Eat(Sue,x)=>~Food(x)∨~Eat(Sue,x)对于目标1，经变量换名后，得子句集：{~Food(x1)∨Like(John,x1)，Food(Apple)，~Eat(y2,x2)∨Kill(x2,y2)∨Food(x2)，Eat(Bill,Peanut),~Kill(Penut,Bill),~Eat(Bill,x3)∨Eat(Sue,x3),~Like(John,Peanut)}归结树如下：对于目标2，经变量换名后，得子句集：{~Food(x1)∨Like(John,x1)，Food(Apple)，~Eat(y2,x2)∨Kill(x2,y2)∨Food(x2)，Eat(Bill,Peanut),~Kill(Penut,Bill),~Eat(Bill,x3)∨Eat(Sue,x3),~Food(x)∨~Eat(Sue,x)}归结树如下： 修改证明树如下： 得到解答为：Food(Peanut)∧Eat(Sue,Peanut)第9题答：该归结过程存在错误。其原因是由于不同的子句用了相同的变量名引起的。如上图中A、B两个子句的归结，两个子句中的y应该是不同的变量，在归结时，如果用不同的变量分别表示，就不会出现这样的问题了。比如B中的y用y1代替，则归结结果如下：第10题答：化子句集：（u）LAST（cons（u，NIL），u）=>LAST（cons（u，NIL），u）（x）（y）（z）（LAST（y，z）→LAST（cons（x，y），z）） =（x）（y）（z）（~LAST（y，z）∨LAST（cons（x，y），z））=>~LAST（y，z）∨LAST（cons（x，y），z）目标取反：~（v）LAST（cons（2，cons（1，NIL）），v）=（v）~LAST（cons（2，cons（1，NIL）），v）=>~LAST（cons（2，cons（1，NIL）），v）经变量换名后，得子句集：{LAST（cons（u，NIL），u）,~LAST（y，z）∨LAST（cons（x，y），z）,~LAST（cons（2，cons（1，NIL）），v）}归结树如下：修改证明树： 得到解答：LAST(cons(2，cons(1，NIL))，1)，表cons(2，cons(1，NIL))的最后一个元素为1。通过以上归结过程，我们可以看出，该方法求解长表的最后一个元素的方法是，每次将长表去掉第一个元素，直到最后得到了只有一个元素的表，该元素就是长表的最后一个元素。第11题答：略第12题答：我们用Skier(x)表示x是滑雪运动员，Alpinist(x)表示x是登山运动员，Alpine(x)表示x是Alpine俱乐部的成员。问题用谓词公式表示如下：已知：(1)Alpine(Tony)(2)Alpine(Mike)(3)Alpine(John)(4)(x){Alpine(x)→[Skier(x)∨Alpinist(x)]}(5)(x){Alpinist(x)→~Like(x,Rain)}(6)(x){~Like(x,Snow)→~Skier(x)}(7)(x){Like(Tony,x)→~Like(Mike,x)}(8)(x){~Like(Tony,x)→Like(Mike,x)}(9)Like(Tony,Snow)(10)Like(Tony,Rain)目标：(vx){Alpine(x)∧Alpinist(x)∧~Skier(x)}化子句集：(1)Alpine(Tony)(2)Alpine(Mike)(3)Alpine(John)(4)(x){Alpine(x)→[Skier(x)∨Alpinist(x)]}=(x){~Alpine(x)∨[Skier(x)∨Alpinist(x)]}=>~Alpine(x)∨Skier(x)∨Alpinist(x)(5)(x){Alpinist(x)→~Like(x,Rain)}=(x){~Alpinist(x)∨~Like(x,Rain)}=>~Alpinist(x)∨~Like(x,Rain)(6)(x){~Like(x,Snow)→~Skier(x)}=(x){Like(x,Snow)∨~Skier(x)}=>Like(x,Snow)∨~Skier(x)(7)(x){Like(Tony,x)→~Like(Mike,x)}=(x){~Like(Tony,x)∨~Like(Mike,x)}=>~Like(Tony,x)∨~Like(Mike,x)(8)(x){~Like(Tony,x)→Like(Mike,x)}=(x){Like(Tony,x)∨Like(Mike,x)}=>Like(Tony,x)∨Like(Mike,x)(9)Like(Tony,Snow)(10)Like(Tony,Rain)目标取反：~(vx){Alpine(x)∧Alpinist(x)∧~Skier(x)}=(x){~Alpine(x)∨~Alpinist(x)∨Skier(x)}=>~Alpine(x)∨~Alpinist(x)∨Skier(x)经变量换名后，得到子句集：{Alpine(Tony),Alpine(Mike),Alpine(John),~Alpine(x1)∨Skier(x1)∨Alpinist(x1),~Alpinist(x2)∨~Like(x2, Rain),Like(x3,Snow)∨~Skier(x3),~Like(Tony,x4)∨~Like(Mike,x4),Like(Tony,x5)∨Like(Mike,x5),Like(Tony,Snow),Like(Tony,Rain),~Alpine(x)∨~Alpinist(x)∨Skier(x)}归结树如下：第13题答：状态草图： 知识的谓词表示：(x)(y){[BIG(x)∧BLUE(x)]→ON(x,y)∧GREEN(y)}(x){[HEAVY(x)∧WOODEN(x)]→BIG(x)}(x){CLEAR(x)→BLUE(x)}(x){WOODEN(x)→BLUE(x)}目标：(x)(y)GREEN(y)∧ON(x,y)对规则Skolem化，对目标用对偶形式Skolem化后，整理得：事实：ONTABLE（A）CLEAR（E）ONTABLE（C）CLEAR（D）ON（D，C）HEAVY（D）ON（B，A）WOODEN（B）HEAVY（B）ON（E，B）规则：r1:[BIG(x1)∧BLUE(x1)]→ON(x1,f(x1))r2:[BIG(x2)∧BLUE(x2)]→GREEN(f(x2))r3:[HEAVY(x3)∧WOODEN(x3)]→BIG(x3)r4:CLEAR(x4)→BLUE(x4)r5:WOODEN(x5)→BLUE(x5)目标：GREEN(y)∧ON(x,y) 容易验证，只有一个解图是一致的，其合一复合为：{B/x,f(B)/y}带入目标公式，得到解答：GREEN(f(B))∧ON(B,f(B))其含义是，积木B在绿色积木上边。这里的f(B)可以理解为B下面那个积木。书本第三章1．将下面的公式化成子句集～(((P∨～Q)→R)→(P∧R))2．命题是数理逻辑中常用的公式，试使用归结法证明它们的正确性：a)P→(Q→P)b)(P→(Q→R))→((P→Q)→(P→R))c)(Q→～P)→((Q→P)→～Q)3．下列子句是否可以合一，如果可以，写出最一般合一置换a)P(x,B,B)和P(A,y,z)b)P(g(f(v)),g(u))和P(x,x)c)P(x,f(x))和P(y,y)d)P(y,y,B)和P(z,x,z)4．解释P(f(x,x),A)和P(f(y,f(y,A)),A)为什么不能合一5．将下列公式化为skolem子句形a)((x)P(x)∨(x)Q(x))→(x)(P(x)∨Q(x))b)(x)(P(x)→(y)((z)Q(x,y)→～(z)R(y,x)))c)(x)P(x)→(x)(((z)Q(x,z))∨(z)R(x,y,z))6．用归结法证明：存在一个绿色物体，如果有如下条件存在：a)如果可以推动的物体是蓝色的，那么不可以推动的物体是绿色的b)所有的物体或者是蓝色的，或者是绿色的，但不能同时具有两种颜色。c)如果存在一个不能推动的物体，那么所有的可推动的物体是蓝色的。d)物体O1是可以推动的e)物体O2是不可以推动的7．设S={P(x),Q(f(x),y)}，试写出H域上的元素，并写出S的一个基例。答案第1题解：～(((P∨～Q)→R)→(P∧R))=((P∨～Q)→R)∧～(P∧R)=(～(P∨～Q)∨R)∧(～P∨～R)=(～P∨R)∧(Q∨R)∧(～P∨～R) 建立子句集：S={～P∨R,Q∨R,～P∨～R}第2题解：1)要证明P→(Q→P)永真～（Q→P）＝～P∧Q建立子句集：S={～P,Q,P}进行归结：Q～P,P□2)要证明(P→(Q→R))→((P→Q)→(P→R))永真即证明～((P→(Q→R))→((P→Q)→(P→R)))为永假。将其化为合取范式：～((P→(Q→R))→((P→Q)→(P→R)))=(P→(Q→R)∧～((P→Q)→(P→R))=(～P∨～Q∨R)∧(P→Q)∧～(P→R)=(～P∨～Q∨R)∧(～P∨Q)∧P∧～R建立子句集：S={～P∨～Q∨R,～P∨Q,P,～R}进行归结：1)～P∨～Q∨R2)～P∨Q3)P4)～R5)Q（2）（3）归结6)～Q∨R（1）（3）归结7)R（5）（6）归结8)□（4）（7）归结3)要证明(Q→～P)→((Q→P)→～Q)为永真即证明～((Q→～P)→((Q→P)→～Q))为永假将其化为合取范式：～((Q→～P)→((Q→P)→～Q))=(Q→～P)∧(Q→P)∧Q=(～Q∨～P)∧(～Q∨P)∧Q建立子句集：S={～Q∨～P,～Q∨P,Q}进行归结： (1)～Q∨～P(2)～Q∨P(3)Q(4)～P（1）（3）归结(5)P（1）（2）归结(6)□第3题解：1)P(x,B,B)和P(A,y,z)可以合一：Mgu={A/x,B/y,B/z}2)P(g(f(v)),g(u))和P(x,x)不可以合一3)P(x,f(x))和P(y,y)不可以合一4)P(y,y,B)和P(z,x,z)可以合一Mgu={B/x,B/y,B/z}第4题解：因为f(x,x)中的x在置换的时候必须保持相同的形式，因此无论怎么置换都不能置换出而第二式中f(y,f(y,A))的分层嵌套形式，因此两个公式是不能合一的。第5题解：1)((x)P(x)∨(x)Q(x))→(x)(P(x)∨Q(x))=((x)~P(x)∧(x)~Q(x))∨(y)(P(y)∨Q(y))=(y)(x)(~P(x)∧~Q(x)∨P(y)∨Q(y))=(y)(x)((~P(x)∨P(y)∨Q(y))∧(~Q(x)∨P(y)∨Q(y)))化为skolem子句形：(~P(x)∨P(a)∨Q(a))∧(~Q(x)∨P(a)∨Q(a))2)(x)(P(x)→(y)((z)Q(z,y)→～(z)R(y,z)))=(x)(y)(z)(v)(～P(x)∨～Q(z,y)∨～R(y,v))化为skolem子句形：～P(x)∨～Q(z,y)∨～R(y,v)3)(x)P(x)→(x)((z)(Q(x,z))∨(y)R(x,y,z))=(x)(～P(x)∨(z)(Q(x,z)∨(y)R(x,y,z)))=(x)(z)(y)(～P(x)∨Q(x,z)∨R(x,y,z))化为skolem子句形：～P(a)∨Q(a,z)∨R(a,y,z)第6题解：把上述条件化为逻辑表达式：1)(x)(pushable(x))→blue(x))→(x)(～pushable(x)→green(x)) 2)(x)(((blue(x)∧～green(x))∨(～blue(x)∧green(x)))3)(x)(～pushable(x))→(x)(pushable(x)→blue(x))4)pushable(O1)5)～pushable(O2)将结果命题否定：～(x)(green(x))将条件表达式和结果命题化为子句形：由条件1(1)pushable(x)∨green(x)(2)～blue(a)∨pushable(y)∨green(x)由条件2(3)～green(x)∨～blue(x)(4)green(x)∨blue(x)由条件3(5)pushable(x)∨～pushable(y)∨blue(y)由条件4(6)pushable(O1)由条件5(7)~pushable(O2)由结论(8)～green(x)归结：(9)～blue(x)∨pushable(y)(2)(8)(10)～blue(x)(7)(9)(11)blue(x)(4)(8)(12)□(10)(11)第7题解：H＝{a,f(a),f(f(a)),……}S中子句的一个基例为：P(a),Q(f(a),f(a))或者P(f(a)),Q(f(f(a)),a)P1233.23证明R1：所有不贫穷且聪明的人都快乐：∀x(∼Poor(x)∧Smart(x)→Happy(x))R2：那些看书的人是聪明的：∀x(read(x)→Smart(x))R3：李明能看书且不贫穷：read(Li)∧∼Poor(Li)R4：快乐的人过着激动人心的生活：∀x(Happy(x)→Exciting(x))结论李明过着激动人心的生活的否定：∼Exciting(Li)将上述谓词公式转化为子句集并进行归结如下：由R1可得子句： 1Poor(x)∨∼Smart(x)∨Happy(x)由R2可得子句：2∼read(y)∨Smart(y)由R3可得子句：3read(Li)4∼Poor(Li)由R4可得子句：5∼Happy(z)∨Exciting(z)有结论的否定可得子句：6∼Exciting(Li)根据以上6条子句，归结如下：7∼Happy(Li)⑤⑥Li/z8Poor(Li)∨∼Smart(Li)⑦①Li/x9∼Smart(Li)⑧④10∼read(Li)⑨②Li/y11□⑩③由上可得原命题成立参考资料:哈工大人工智能视频教程36讲吉林大学人工智能26讲付宏主讲东南大学人工智能31讲翟玉庆主讲'