人工智能期末试题

2.证明G是否为1F,2F,……，nF的逻辑结论。1F：xxxxRQP1F：xxxSPG：xxxRS2.先把G否定，并放入F中，得到的｛F1,F2,¬G｝为｛xxxxRQP，xxxSP，¬（xxxRS）｝再把｛F1,F2,¬G｝化为子句集，得到①)x()x(QP②)y()y(RP③)a(P④)a(S⑤)b()b(RS其中①②是由F1化为的两个子句，③④是由F2化为的两个子句，⑤是由G化为的子句。由子句集可以看出只有唯一的一个Q因此可以得出G不是F的逻辑结构。3.假设张被盗，公安局派出5人去调查。案情分析时，侦查员A说：“赵与钱中至少有一人作案”；侦查员B说：“钱与孙中至少有一人作案”；侦查员C说：“孙与李中至少有一人作案”；侦查员D说：“赵与孙中至少有一人与此案无关”；侦查员E说：“钱与李中至少有一人与此案无关”。如果这5个侦查员的话都是可信的，试用归结演绎推理求出谁是盗窃犯。3.解：(1)先定义谓词和常量设C(x)表示x作案，Z表示赵，Q表示钱，S表示孙，L表示李(2)将已知事实用谓词公式表示出来赵与钱中至少有一个人作案：C(Z)∨C(Q)钱与孙中至少有一个人作案：C(Q)∨C(S)孙与李中至少有一个人作案：C(S)∨C(L)赵与孙中至少有一个人与此案无关：¬(C(Z)∧C(S))，即¬C(Z)∨¬C(S)钱与李中至少有一个人与此案无关：¬(C(Q)∧C(L))，即¬C(Q)∨¬C(L)(3)将所要求的问题用谓词公式表示出来，并与其否定取析取。设作案者为u，则要求的结论是C(u)。将其与其否取析取，得：¬C(u)∨C(u)(4)对上述扩充的子句集，按归结原理进行归结，其修改的证明树如下：因此，钱是盗窃犯。实际上，本案的盗窃犯不止一人。根据归结原理还可以得出：因此，孙也是盗窃犯。4.设有如图所示的与/或树，请分别用和代价法、最大代价法求解树的代价。4.解：若按和代价法，则该解树的代价为：C(S)∨C(L)¬C(Q)∨¬C(L)C(S)∨¬C(Q)C(Q)∨C(S)C(S)¬C(u)∨C(u)C(S){S/u}C(Q)∨C(S)¬C(Z)∨¬C(S)C(Z)∨C(Q)C(Q)∨¬C(S)C(Q)¬C(u)∨C(u)C(Q){Q/u}ABCDE5761223t12t2t3t4h(A)=2+3+2+5+2+1+6=21若按最大代价法，则该解树的代价为：h(A)=max{h(B)+5,h(C)+6}=max{(h(E)+2)+5,h(C)+6}=max{(max(2,3)+2)+5,max(2,1)+6}=max((5+5),(2+6))=105.设有如下一组推理规则：1r：IF1ETHEN2E（0.6）2r：IF2EAND3ETHEN4E(0.7)3r：IF4ETHENH（0.8）4r：IF5ETHENH(0.9)且已知CF(1E)=0.5，CF(3E)=0.6,CF(5E)=0.7,求CF(H)。5.解：(1)先由r1求CF(E2)CF(E2)=0.6×max{0,CF(E1)}=0.6×max{0,0.5}=0.3(2)再由r2求CF(E4)CF(E4)=0.7×max{0,min{CF(E2),CF(E3)}}=0.7×max{0,min{0.3,0.6}}=0.21(3)再由r3求CF1(H)CF1(H)=0.8×max{0,CF(E4)}=0.8×max{0,0.21)}=0.168(4)再由r4求CF2(H)CF2(H)=0.9×max{0,CF(E5)}=0.9×max{0,0.7)}=0.63(5)最后对CF1(H)和CF2(H)进行合成，求出CF(H)CF(H)=CF1(H)+CF2(H)+CF1(H)×CF2(H)=0.6926.设U=V=W=｛1，2，3，4｝且有如下规则：1r：IFxisFTHENyisG2r：IFyisGTHENzisH3r：IFxisFTHENzisH其中，F,G,H的模糊集分别为F=1/1+0.8/2+0.5/3+0.4/4G=0.1/2+0.2/3+0.4/4H=0.2/2+0.5/3+0.8/4请用模糊关系CR验证满足模糊三段论。6.先求FG上的关系c1R，c1R=4.02.01.004.02.01.004.02.01.004.02.01.00再求GH上的关系2CR,2CR=4.04.02.002.02.02.001.01.01.000000最后求FGH的关系R，R=c1Rc1R=4.04.02.004.04.02.004.04.02.004.04.02.002.(龙云献）简述用A*算法求解问题时为什么会出现重复扩展节点问题，解决的方法有哪些？答：当问题有解时，A*算法总是找到问题的最优解结束。如果h函数定义的不合理，则当扩展一个节点时，不一定就找到了从初始节点到该节点的最优路径，对于这样的节点，就有可能被多次扩展。特别是如果这样的节点处于问题的最优解路径上时，则一定会被多次扩展。解决的方法一是对h函数的定义给出限制，使得h满足单调性。对于满足单调性条件的h，则一定不会出现重复扩展节点问题。二是对A*算法加以改进，使用修正的A*算法进行搜索，则可以减少重复扩展节点问题。3.（刘林洋）简述回溯策略与深度优先策略的不同点。答：回溯搜索策略与深度有限搜索策略最大的不同是深度有限搜索策略属于图搜索，而回溯搜索则不是图搜索。在回溯搜索中，只保留了从初始节点到当前节点的搜索路径。而深度优先搜索，则保留了所有的已经搜索过的路径。4.(张松)设有如下两个模糊关系：请写出R1与R2的合成R1οR2。解：R(1,1)=(0.3∧0.2)∨(0.7∧0.6)∨(0.2∧0.9)=0.2∨0.6∨0.2=0.6R(1,2)=(0.3∧0.8)∨(0.7∧0.4)∨(0.2∧0.1)=0.3∨0.4∨0.1=0.4R(2,1)=(1∧0.2)∨(0∧0.6)∨(0.4∧0.9)=0.2∨0∨0.4=0.4R(2,2)=(1∧0.8)∨(0∧0.4)∨(0.4∧0.1)=0.8∨0∨0.1=0.8R(3,1)=(0∧0.2)∨(0.5∧0.6)∨(1∧0.9)=0.2∨0.6∨0.9=0.9R(3,2)=(0∧0.8)∨(0.5∧0.4)∨(1∧0.1)=0∨0.4∨0.1=0.4因此有1.09.04.06.08.02.015.004.0012.07.03.021RR4.09.08.04.04.06.021RR5.（张松）设U=V={1，2，3，4}且有如下推理规则：IFxis少THENyis多其中，“少”与“多”分别是U与V上的模糊集，设少=0.9/1+0.7/2+0.4/3多=0.3/2+0.7/3+0.9/4已知事实为xis较少“较少”的模糊集为较少=0.8/1+0.5/2+0.2/3请用模糊关系Rm求出模糊结论。解：先用模糊关系Rm求出规则IFxis少THENyis多所包含的模糊关系RmRm(1,1)=(0.9∧0)∨(1-0.9)=0.1Rm(1,2)=(0.9∧0.3)∨(1-0.9)=0.3Rm(1,3)=(0.9∧0.7)∨(1-0.9)=0.7Rm(1,4)=(0.9∧0.9)∨(1-0.9)=0.7Rm(2,1)=(0.7∧0)∨(1-0.7)=0.3Rm(2,2)=(0.7∧0.3)∨(1-0.7)=0.3Rm(2,3)=(0.7∧0.7)∨(1-0.7)=0.7Rm(2,4)=(0.7∧0.9)∨(1-0.7)=0.7Rm(3,1)=(0.4∧0)∨(1-0.4)=0.6Rm(3,2)=(0.4∧0.3)∨(1-0.4)=0.6Rm(3,3)=(0.4∧0.7)∨(1-0.4)=0.6Rm(3,4)=(0.4∧0.9)∨(1-0.4)=0.6Rm(4,1)=(0∧0)∨(1-0)=1Rm(4,2)=(0∧0.3)∨(1-0)=1Rm(4,3)=(0∧0.7)∨(1-0)=1Rm(3,4)=(0∧0.9)∨(1-0)=1即：0.10.30.70.90.30.30.70.70.60.60.60.61111mR因此有'0.10.30.70.90.30.30.70.70.8,0.5,0.2,00.60.60.60.611110.3,0.3.0.7,0.8Y即，模糊结论为Y’={0.3,0.3,0.7,0.8}6.(张松)设已知：(1)如果x是y的父亲，y是z的父亲，则x是z的祖父；(2)每个人都有一个父亲。使用归结演绎推理证明：对于某人u，一定存在一个人v，v是u的祖父。解：先定义谓词F(x,y)：x是y的父亲GF(x,z)：x是z的祖父P(x)：x是一个人再用谓词把问题描述出来：已知F1：(x)(y)(z)(F(x,y)∧F(y,z))→GF(x,z))F2：(y)(P(x)→F(x,y))求证结论G：(u)(v)(P(u)→GF(v,u))然后再将F1，F2和¬G化成子句集：①¬F(x,y)∨¬F(y,z)∨GF(x,z)②¬P(r)∨F(s,r)③P(u)④¬GF(v,u))对上述扩充的子句集，其归结推理过程如下：{x/v,z/u}{x/s,y/r}{y/s,z/r}{y/z}{y/u}由于导出了空子句，故结论得证。¬F(x,y)∨¬F(y,z)∨GF(x,z)¬GF(v,u)¬F(x,y)∨¬F(y,z)¬P(r)∨F(s,r)¬F(y,z)∨¬P(y)¬P(r)∨F(s,r)¬P(y)∨¬P(z)¬P(y)P(u)NIL1.假设有以下一段天气预报：“贵阳地区今天白天晴，东北风1级，最高气温25º，最低气温16º，降水概率10%，湿度64%。”请用框架表示这一知识。（陈丽丽）解：Frame天气预报地域：贵阳时段：今天白天天气：晴风向：东北风力：1级气温：最高：25度最低：16度降水概率：10%湿度：64%2.把下列谓词公式化成子句集：（陈丽丽）(1)(x)(y)(P(x,y)∧Q(x,y))(2)(x)(y)(P(x,y)∨(Q(x,y)→R(x,y)))解：(1)由于(x)(y)(P(x,y)∧Q(x,y))已经是Skolem标准型，且P(x,y)∧Q(x,y)已经是合取范式，所以可直接消去全称量词、合取词，得{P(x,y),Q(x,y)}再进行变元换名得子句集：S={P(x,y),Q(u,v)}(2)对谓词公式(x)(y)(P(x,y)∨(Q(x,y)→R(x,y)))，先消去连接词“→”得：(x)(y)(P(x,y)∨(¬Q(x,y)∨R(x,y)))此公式已为前束范式。再消去存在量词，即用Skolem函数f(x)替换y得：(x)(P(x,f(x))∨¬Q(x,f(x))∨R(x,f(x)))此公式已为Skolem标准型。最后消去全称量词得子句集：S={P(x,f(x))∨¬Q(x,f(x))∨R(x,f(x))}(1)有的人喜欢梅花，有的人喜欢菊花，有的人既喜欢梅花又喜欢菊花。解：定义谓词P(x)：x是人L(x,y)：x喜欢y其中，y的个体域是{梅花，菊花}。将知识用谓词表示为：(x)(P(x)→L(x,梅花)∨L(x,菊花)∨L(x,梅花)∧L(x,菊花))(2)新型计算机速度又快，存储容量又大。解：定义谓词NC(x)：x是新型计算机F(x)：x速度快B(x)：x容量大将知识用谓词表示为：(x)(NC(x)→F(x)∧B(x))(3)凡是喜欢编程序的人都喜欢计算机。解：定义谓词P(x)：x是人L(x,y)：x喜欢y将知识用谓词表示为：(x)(P(x)∧L(x,pragramming)→L(x,computer))、设有如下一组推理规则:r1:IFE1THEN