1. 用谓词逻辑知识表示方法表示如下知识:(1) 有人喜欢梅花,有人喜欢菊花,有人既喜欢梅花又喜欢菊花。
(2) 不是每个计算机系的学生都喜欢在计算机上编程序。
解:(1)定义谓词P(x):x是人L(x,y):x喜欢y其中,y的个体域是{梅花,菊花}。
将知识用谓词表示为:(x)(P(x)→L(x, 梅花)∨L(x, 菊花)∨L(x, 梅花)∧L(x, 菊花))解:(2)定义谓词S(x):x是计算机系学生L(x, pragramming):x喜欢编程序U(x,computer):x使用计算机将知识用谓词表示为:(x) (S(x)→L(x, pragramming)∧U(x,computer))2. 请用语义网络表示如下知识:高老师从3月到7月给计算机系的学生讲“计算机网络”课。
解:3. 判断以下子句集是否为不可满足{P(x)∨Q(x )∨R(x), ﹁P(y)∨R(y), ﹁Q(a), ﹁R(b)}解:采用归结反演,存在如下归结树,故该子句集为不可满足。
4、证明G是F的逻辑结论F: (x)(y)(P(f(x))∧(Q(f(y)))G: P(f(a))∧P(y)∧Q(y)证:先转化成子句集对F,进行存在固化,有P(f(v))∧(Q(f(w)))得以下两个子句P(f(v)),Q(f(w))对﹁G,有﹁P(f(a))∨﹁P(y) ∨﹁Q(y)先进行内部合一,设合一{f(a)/y},则有因子﹁P(f(a)) ∨﹁Q(f(a))再对上述子句集进行归结演绎推理。
其归结树如下图所示,即存在一个到空子句的归结过程。
因此G为真。
5 设有如下结构的移动将牌游戏:其中,B表示黑色将牌,W表是白色将牌,E表示空格。
游戏的规定走法是:(1) 任意一个将牌可移入相邻的空格,规定其代价为1;(2) 任何一个将牌可相隔1个其它的将牌跳入空格,其代价为跳过将牌的数目加1。
游戏要达到的目标什是把所有W都移到B的左边。
对这个问题,请定义一个启发函数h(n),并给出用这个启发函数产生的搜索树。
你能否判别这个启发函数是否满足下界要求在求出的搜索树中,对所有节点是否满足单调限制解:设h(x)=每个W左边的B的个数,f(x)=d(x)+3*h(x),其搜索树如下:6 设有如下一组推理规则:r1: IF E1THEN E2r2: IF E2AND E3THEN E4r3: IF E4THEN Hr4: IF E5THEN H且已知CF(E1)=, CF(E3)=, CF(E5)=。
求CF(H)=解:(1) 先由r1求CF(E2)CF(E2)= × max{0,CF(E1)}= × max{0,}=(2) 再由r2求CF(E4)CF(E4)= × max{0, min{CF(E2 ), CF(E3 )}}= × max{0, min{, }}=(3) 再由r3求CF1(H)CF1(H)= × max{0,CF(E4)}= × max{0, }=(4) 再由r4求CF2(H)CF2(H)= ×max{0,CF(E5)}= ×max{0, }=(5) 最后对CF1(H )和CF2(H)进行合成,求出CF(H)CF(H)= CF1(H)+CF2(H)- CF1(H) ×CF2(H)=7 设训练例子集如下表所示:请用ID3算法完成其学习过程。
解:设根节点为S,尽管它包含了所有的训练例子,但却没有包含任何分类信息,因此具有最大的信息熵。
即:H(S)= - (P(+)log 2P(+) - P(-)log2 P(-))式中P(+)=3/6,P(-)=3/6即有H(S)= - ((3/6)*log (3/6) - (3/6)*log (3/6))= *(-1) - *(-1) = 1按照ID3算法,需要选择一个能使S的期望熵为最小的一个属性对根节点进行扩展,因此我们需要先计算S关于每个属性的条件熵:H(S|x i)= ( |S T| / |S|)* H(S T) + ( |S F| / |S|)* H(S F)其中,T和F为属性x i的属性值,S T和S F分别为x i=T或x i=F时的例子集,|S|、| S T|和|S F|分别为例子集S、S T和S F 的大小。
下面先计算S关于属性x1的条件熵:在本题中,当x1=T时,有:S T={1,2,3}当x1=F时,有:S F={4,5,6}其中,S T和S F中的数字均为例子集S中例子的序号,且有|S|=6,| S T |=| S F |=3。
由S T可知:P(+)=2/3,P(-)=1/3则有:H(S T)= - (P(+)log2 P(+) - P(-)log2 P(- ))= - ((2/3)log2(2/3)- (1/3)log2(1/3)) ==再由S F可知:P SF(+)=1/3,P SF(-)=2/3则有:H(S F)= - (P SF(+)log2 P ST(+) - P SF(-)log2 P SF(- ))= - ((2/3)log2(2/3)- (1/3)log2(1/3)) =将H(S T)和H (S F)代入条件熵公式,有:H(S|x1)=(|S T|/|S|)H(S T)+ (|S F|/|S|)H(S F)=(3/6)﹡+ (3/6)﹡=下面再计算S关于属性x2的条件熵:在本题中,当x2=T时,有:S T={1,2,5,6}当x2=F时,有:S F={3,4}其中,S T和S F中的数字均为例子集S中的各个例子的序号,且有|S|=6,| S T |=4,| S F |=2。
由S T可知:P ST (+) = 2/4P ST (-) = 2/4则有:H(S T)= - (P ST (+)log2 P ST (+) - P ST (-)log2 P ST (- ))= - ((2/4)log2(2/4) - (2/4)log2(2/4))=1再由S F可知:P SF (+)=1/2P SF (-)=1/2则有:H(S F)= - (P(+)log2 P(+) - P(-)log2 P(- ))= - ((1/2)log2(1/2)- (1/2)log2(1/2))=1将H(S T)和H (S F)代入条件熵公式,有:H(S|x2)=(|S T|/|S|)H(S T)+ (|S F|/|S|)H(S F)=(4/6)﹡1 + (2/6)﹡1=1可见,应该选择属性x1对根节点进行扩展。
用x1对S扩展后所得到的部分决策树如下图所示。
8八数码难题f(n)=d(n)+P(n)d(n) 深度P(n)与目标距离显然满足P(n)≤ h*(n)即f*=g*+h*9 修道士和野人问题解:用m表示左岸的修道士人数,c表示左岸的野人数,b表示左岸的船数,用三元组(m, c, b)表示问题的状态。
对A*算法,首先需要确定估价函数。
设g(n)=d(n),h(n)=m+c-2b,则有f(n)=g(n)+h(n)=d(n)+m+c-2b其中,d(n)为节点的深度。
通过分析可知h(n)≤h*(n),满足A*算法的限制条件。
M-C问题的搜索过程如下图所示。
10 设有如下一组知识: r 1:IF E 1 THEN H r 2:IF E 2 THEN H r 3:IF E 3 THEN Hr 4:IF E 4 AND ( E 5 OR E 6) THEN E 1 已知:CF(E 2)=,CF(E 3)=,CF(E 4)=,CF(E 5)=, CF(E 6)= 求:CF(H)= 解:由r 4得到:CF(E 1)=×max{0, CF(E 4 AND (E 5 OR E 6))} = ×max{0, min{CF(E 4), CF(E 5 OR E 6)}} =×max{0, min{CF(E 4), max{CF(E 5), CF(E 6)}}} =×max{0, min{CF(E 4), max{, }}} =×max{0, min{, }} =×max{0, } =由r 1得到:CF 1(H)=CF(H, E 1)×max{0, CF(E 1)} =×max{0, } = 由r 2得到:CF 2(H)=CF(H, E 2)×max{0, CF(E 2)} =×max{0, } =由r 3得到:CF 3(H)=CF(H, E 3)×max{0, CF(E 3)} =×max{0, } =根据结论不精确性的合成算法,CF 1(H)和CF 2(H)同号,有:67.017.084.048.036.048.036.0)()()()()(21212,1=-=⨯-+=⨯-+=H CF H CF H CF H CF H CFCF 12(H)和CF 3(H)异号,有:{}{}53.07.037.03.0,67.0min 13.067.0)(,)(min 1)()()(32,132,13,2,1==--=-+=H CF H CF H CF H CF H CF即综合可信度为CF(H)=11 设有如下知识:r1: IF E1()AND E2() THEN E5 () r2: IF E3()AND E4()AND E5()THEN H () 已知: CF (E1)=,CF (E2)=,CF (E3)=,CF (E4)= 求: CF (H )= 解:CF(E1 AND E2)=*+*= CF(E5)=*=CF(E3 AND E4 AND E5) =*+*+*=CF(H)=*=12设有如下规则:r1: IF E1 AND E2THEN A={a1, a2} CF={, } r2: IF E3 THEN H={h1, h2} CF={, }r3: IF A THEN H={h1, h2} CF={, }已知用户对初始证据给出的确定性为:CER(E1)= CER(E2)=CER(E3)=并假Ω定中的元素个数∣Ω∣=10求:CER(H)=解:由给定知识形成的推理网络如下图所示:(1) 求CER(A)由r1:CER(E1AND E2)=min{CER(E1), CER(E2)}=min{, } =m({a1}, {a2})={×, ×} = {, }Bel(A)=m({a1})+m({a2})=+=Pl(A)=1-Bel(﹁A)=1-0=1f(A)=Bel(A)+|A|/|Ω|[Pl(A)-Bel(A)]=+2/10*[]=故CER(A)=MD(A/E')×f(A)=(2) 求CER(H)由r2得m1({h1}, {h2})={CER(E3)×, CER(E3)×}={×, ×}={, }m1(Ω)=1-[m1({h1})+m1({h2})]=1-[+]=由r3得m 2({h 1}, {h 2})={CER(A)×, CER(A)×} ={×, ×} ={, }m 2(Ω)=1-[m 2({h 1})+m 2({h 2})] =1-[+]=求正交和m=m 1⊕m 2 K=m 1(Ω)×m 2(Ω)+m 1({h 1})×m 2({h 1})+m 1({h 1})×m 2(Ω)+m 1(Ω)×m 2({h 1}) +m 1({h 2})×m 2({h 2})+m 1({h 2})×m 2(Ω)+m 1(Ω)×m 2({h 2}) =×+×+×+× +×+×+× =++++++ =32.0]06.046.065.036.006.036.0[88.01})]({)()(})({})({})({[1)(12121112111=⨯+⨯+⨯⨯=•Ω+Ω•+••=h m m m h m h m h m Kh m同理可得:34.0]29.046.065.018.029.018.0[88.01})]({)()(})({})({})({[1)(22122122212=⨯+⨯+⨯⨯=⨯Ω+Ω⨯+⨯⨯=h m m m h m h m h m Kh m故有:m(Ω)=1-[m({h 1})+m({h 2})] =1-[+] = 再根据m 可得Bel(H)=m({h 1})+m({h 2}) = + = Pl(H)=m(Ω)+Bel(H)=+=173.0)66.01(10266.0)]()([)()(=-⨯+=-•Ω+=H Bel H Pl HH Bel H fCER(H)=MD(H/E')×f(H)=13用ID3算法完成下述学生选课的例子 假设将决策y 分为以下3类: y 1:必修AI y 2:选修AI y 3:不修AI做出这些决策的依据有以下3个属性:x 1:学历层次 x 1=1 研究生,x 1=2 本科 x 2:专业类别 x 2=1 电信类,x 2=2 机电类x 3:学习基础 x 3=1 修过AI ,x 3=2 未修AI 表给出了一个关于选课决策的训练例子集S 。