人工智能作业讲解47

作业讲解詹杭龙[e-mail]第一次作业题目：2.11用谓词逻辑公式表示如下自然数公理：（1）每个数都存在一个且仅存在一个直接后继数。参考解答：定义谓词：Equal(x,y):x和y相等，N(x):x是自然数，Succeed(x,y),y是x的后继(x是y的前启)。))),(),((),((zyEqualzxSuceedzyxSuceedyx)))),(),()((),()(()((zyEqualzxSucceedzNzyxSucceedyNyxNx)))),(),(((),((zyEqualzxSuceedzyxSuceedyxor定义函词：succ(x):x的后继))),())(,(())(,((zyEqualxsucczEqualzxsuccyEqualyx2.11（1）不好的解答：仅定义一个谓词，未考虑对“仅存在一个”的描述，A(x)表示x存在一个且仅一个直接后继数。))()((xAxNxEqual(x,y)直接写为x=y，最好用谓词来描述第一次作业题目：2.11用谓词逻辑公式表示如下自然数公理：（2）每个数都不以0为后继数。参考解答：定义谓词：Equal(x,y):x和y相等，N(x):x是自然数，Succeed(x,y),y是x的后继(x是y的前启)。))0,()((xSucceedxNx))0,()((xSucceedxNx不好的解答：未考虑谓词N(x)第一次作业题目：2.11用谓词逻辑公式表示如下自然数公理：（3）每个不同于0的数都存在一个且仅存在一个直接前启数。参考解答：定义谓词：Equal(x,y):x和y相等，N(x):x是自然数，Succeed(x,y),y是x的后继(x是y的前启)。)))),(),()((),()(()0,()((zyEqualxzSucceedzNzxySucceedyNyxEqualxNx)))),(),()((),()(()0,()((zyEqualxzSucceedzNzxySucceedyNyxEqualxNx第一次作业题目：2.12用一阶谓词逻辑表示下面的句子。（1）人人为我，我为人人。参考解答：定义谓词：定义For(x,y)表示x为y,I表示我或I(x)表示x是我。Equal表示x,y是同一个人。不好的解答：1.需要再细分))),(),((),((xIForIxForIxEqualx)))),(),((),(()((xyForyxForyxEqualyxIx))()((xMeforxFormex)),(),(()),((),((yIForIyEqualyIxForIxEqualx第一次作业题目：2.12用一阶谓词逻辑表示下面的句子。（2）鱼我所欲也，熊掌亦我所欲也。参考解答：定义谓词：I表示我或I(x)表示x是我，Fish(x)表示x是鱼，Bearpaw(x)表示x是熊掌。不好的解答：1.描述对象错误2.没有量词)),()()((xIWantxBearpawxFishx))()()((xwWantBearpaxWantFishxIx)),()(()),()((yIWantyBearpawyxIWantxFishx),(),(PawIWantFishIWant第一次作业题目：2.12用一阶谓词逻辑表示下面的句子。（8）历史考试的最高分比生物考试最高分要高。参考解答：主体是比较分数的高低，所以将分数作为变元x，注意是谓词，不是函数，不能写history(x)表示历史最高分可以写History(x)表示x是历史最高分；Biology(x)表示x是生物最高分，Higher(x,y)表示x比y高。不好的解答：1.定义H为历史最高分，B为生物最高分。)),()()((yxHigheryBiologyxHistoryyx),(BHHigher)))(()((xyyHyxBx不够直观第一次作业题目：2.12用一阶谓词逻辑表示下面的句子。（10）星期六，所有的学生或者去参加舞会了，或者工作去了，但是没有两者都去的。参考解答：Student(x)表示x是学生，Dance(x)表示x周六去跳舞了，Work(x)表示x周六去工作了。（带上不带上星期六都可以，如果原题说的是每个星期六的话，最好带上Saturday(x)—(…)）))))()(())()((()((xWorkxDancexWorkxDancexStudentx点评•谓词的作用是描述对象的性质和关系，因此，在定义谓词的时候不应当带有“对象”。例如，forMe，wantFish，wantPaw等。•尽量用符号去表示常量和变量，并注意区分大小写。•，，=等符号表示对象之间的关系，最好定义为谓词，例如Equal(x,y)。•命名规范：最好使用Equal(x,y)，而不是E(x,y)。•形式化的层次应该适当细一点。例子：世上没有无缘无故的爱，也没有无缘无故的恨。•分析题目描述的对象是什么，将其作为变元来分析。第一次作业题目：2.14Hanoi塔表示：已知3个柱子1、2、3，3个盘子A、B、C（A比B大，B比C大）。初始状态时，A、B、C依次放在柱子1上。目标状态是A、B、C依次放在柱子3上。条件是每次可以移动一个盘子，盘子上方为空才可以移动，而且任何时候都不允许大盘子在小盘子的上面。请使用一阶谓词逻辑对这一问题进行描述。2.14参考解答：A，B，C表示盘子(A比B大，B比C大)，1，2，3表示柱子，Plate(x)表示x是盘子,Pillar(x)表示x是柱子，At(x,y)表示盘子x在柱子y上，Bigger(x,y)表示盘子x比盘子y大，Above(x,y)表示盘子x在盘子y上方，Move(x,y,z)表示将x盘从y柱移动到z柱。已知：Bigger(A,B),Bigger(B,C)初始：At(A,1),At(B,1),At(C,1),Above(C,B),Above(B,A)目标：At(A,3),At(B,3),At(C,3),Above(C,B),Above(B,A)移动条件：)),,()),(),()(()),()(()()()((yxuMoveutBiggerytAttPlatetuvAbovevPlatevyPillarxPillaruPlateyxu第一次作业题目：请求出公式的析取范式和合取范式。参考解答：析取范式与合取范式相同，均为：)(QPPQP第二次作业题目：2.20考虑下面不可满足的子句集和：1.对下面每一种策略求其归结反驳。①支持集策略（其中支持集是上述字句列表的最后一个子句）。②祖先过滤策略。③一种既违反支持集也违反祖先过滤的策略。2.说明不存在这种不可满足的子句集合的线性输入归结反驳。2.20参考解答：支持集策略：每次归结时，参与归结的子句中至少有一个是由目标公式的否定所得到的子句或者是它们的后裔。（1）P∨Q（2）P∨┓Q（3）┓P∨Q（4）┓P∨┓Q（5）┓P（3）（4）归结（利用目标公式）（6）┓Q（2）（4）归结（利用目标公式）（7）Q（1）（6）归结（利用目标公式的后裔（6））（8）□（6）（7）归结（利用目标公式的后裔（6）（7））2.20参考解答：祖先过滤：参与归结的两个子句中至少有一个是初始子句集中的子句，或者一个子句是另一个子句的祖先，该策略是完备的。（1）P∨Q（2）P∨┓Q（3）┓P∨Q（4）┓P∨┓Q（5）┓P（3）（4）归结（利用初始子句）（6）┓Q（2）（4）归结（利用初始子句）（7）Q（1）（6）归结（利用初始子句）（8）□（6）（7）归结（（6）是（7）的祖先）第二次作业参考解答：违反支持集也违反祖先过滤的策略（1）P∨Q（2）P∨┓Q（3）┓P∨Q（4）┓P∨┓Q（5）┓P（3）（4）归结（违反支持集策略）（6）P（1）（2）归结（7）□（5）（6）归结（违反祖先过滤策略）第二次作业题目：2.20说明不存在这种不可满足的子句集合的线性输入归结反驳。参考解答：•线性输入：参与归结的两个子句中至少有一个是原始子句集中的子句。该策略是不完备的。•在原问题中所有子句都含有两个文字，而归结一次只能消除掉一个文字，所以不论如何归结，只要参与归结的两个子句有一个是来自原始子句集，那么归结的结果一定不会是□。所以，不存在这种子句集合的线性归结反驳。第二次作业题目：2.24把下面的表达式转换成子句形式。)]()()[()])()[()]()[((xQxPxxQxxPx)]()([))()((xQxPxxxQxxP)]()([))()((zQzPzyQyxPx))]()(())()([(zQzPyQxPzyx))],(()),(()([))],(()),(()([yxfQyxfPyQyxfQyxfPxP))},(()),(()()),,(()),(()({yxfQyxfPyQyxfQyxfPxP参考解答：第二次作业题目：2.24把下面的表达式转换成子句形式。（2）参考解答：)]],,()[()],()[)[(()]()[(zyxRzzxQzxxPx)},,(),()({tybRzbQaP)),,(),(()(zyxzRzxzQxxxP)),,(),(()(zyxzRzxzQxxPx)),,(),(()(zyuzRzuzQuxPx)),,(),(()(tyuRzuQxPtzux)),,(),(()(tybRzbQaPtz注意：常元一般用a,b,c，变元用字母表后面的字母第二次作业题目：2.27对下述公式集合执行合一算法，判断是否可合一，如果可合一，给出最一般合一。（1）（2）（3）))}(),,(,())),((,,({ufuzhzPygfxaPS)},()),(),(({yyPsgafPS))}(),(,())),((,,({yhyhzPzghxaPS2.27参考解答：–核心：合一概念，合一算法（P52页）–（1）解答如下：–（2）答案：不可合一–（3）答案：可合一，mgu=))}(),,(,())),((,,({ufuzhzPygfxaPS},{,,)1000zaDSW))}(),,(,())),((,,({},/{)211ufuahaPygfxaPWza令)},(,{,)311uahxDW未合一))}(),,(,())),((),,(,({},/),(,/{)422ufuahaPygfuahaPWxuahza)),((,)522uygDW未合一)))}(()),(,(,({},/)(,/))(,(,/{)633ygfygahaPWuygxygahza}/)(,/))((,/{yagxaghza第二次作业题目：2.31已知：规则1：任何人的兄弟不是女性。规则2：任何人的姐妹必是女性。事实：Mary是Bill的姐妹。求证：用归结推理方法证明Mary不是Tom的兄弟。参考解答：定义Sister(x,y)表示x是y的姐妹，Brother(x,y)表示x是y的兄弟，Female(x)表示x是女性，论域为所有人的集合。2.31))(),((xFemaleyxBrotheryx))(),((xFemaleyxSisteryx),(BillMarySister),(TomMaryBrother),(),({xFemaleyxBrotherW)},(),,(),(),(TomMaryBrotherBillMarySisterxFemaleyxSister)(MaryFemale)(MaryFemale已知：求证：子句集：1，4归结：(5)(6)2，3归结：5，6归结：□第二次作业