人工智能(部分习题答案) 下载本文

这样,所定义的算符组F可以有以下8种算符: L (0),L (1),L (2),L (3) R(0),R(1),R (2),R (3)

第四步,根据上述定义的状态和操作进行求解。 该问题求解过程的状态空间图如下:

L(2) (0,1,0,1) R(0) (1,1,0,1) L(1) (0,0,0,1) R(2) (1,0,1,1) L(3)

(0,0,1,0) R(0)

(1,0,1,0) L(2) (0,0,0,0)

L(3) (0,1,0,0)

R(2) (1,1,1,0) L(2)

3.5什么是谓词公式?什么是谓词公式的解释?设D={1,2},试给出谓词公式(?x)(?y)(P(x,y)?Q(x,y))的所有解释,并且对每一种解释指出该谓词公式的真值。

解:谓词公式是按照下述五个规则由原子公式、连接词、量词及圆括号所组成的字符串。

(1)原子谓词公式是合式公式。 (2)若A是合式公式,则?A也是合式公式。 (3)若A和B都是合式公式,则A?B、A?B、A?B、A?B也都是合式公式。 (4)若A是合式公式,x是任一个体变元,则(?x)A和(?x)A也都是合式公式。 (5)只有按(1) ? (4)所得的公式才是合式公式。 谓词公式的解释:设D为谓词公式P的个体域,若对P中的个体常量、函数和谓词按照如下规定赋值:(1)为每个个体常量指派D中的一个元素;(2)为每个n元函数指派一个从Dn到D的映射,其中Dn={(x1,x2,?,xn)| x1,x2,?,xn ?D} (3)为每个n元谓词指派一个从Dn到{F,T}的映射;则这些指派称为公式P在D上的解释。

下面给出本题的所有解释:

1. 对谓词指派的真值为:P(1,1)=T,P(1,2)=F,P(2,1)=T,P(2,2)=F,Q(1,1)=T,Q(1,2)=F,

Q(2,1)=T,Q(2,2)=F,在此解释下,x=1时,P(1,1)?Q(1,1)为T,P(1,2)?Q(1,2)为T;x=2时,P(2,1)?Q(2,1)为T,P(2,2)?Q(2,2)为T。所以在此解释下,本题谓词公式的真值为T。 2. 对谓词指派的真值为:P(1,1)=T,P(1,2)=F,P(2,1)=F,P(2,2)=T,Q(1,1)=T,Q(1,2)=F,

Q(2,1)=T,Q(2,2)=F,在此解释下,x=1时,P(1,1)?Q(1,1)为T,P(1,2)?Q(1,2)为T;x=2时,P(2,1)?Q(2,1)为T,P(2,2)?Q(2,2)为F。所以在此解释下,本题谓词公式的真值为T。 3. 对谓词指派的真值为:P(1,1)=F,P(1,2)=T,P(2,1)=T,P(2,2)=F,Q(1,1)=T,Q(1,2)=F,

Q(2,1)=T,Q(2,2)=F,在此解释下,x=1时,P(1,1)?Q(1,1)为T,P(1,2)?Q(1,2)为F;x=2时,P(2,1)?Q(2,1)为T,P(2,2)?Q(2,2)为T。所以在此解释下,本题谓词公式的真值为T。 4. 对谓词指派的真值为:P(1,1)=F,P(1,2)=T,P(2,1)=F,P(2,2)=T,Q(1,1)=T,Q(1,2)=F,

6

Q(2,1)=T,Q(2,2)=F,在此解释下,x=1时,P(1,1)?Q(1,1)为T,P(1,2)?Q(1,2)为F;x=2时,P(2,1)?Q(2,1)为T,P(2,2)?Q(2,2)为F。所以在此解释下,本题谓词公式的真值为F。 5. 对谓词指派的真值为:P(1,1)=T,P(1,2)=F,P(2,1)=T,P(2,2)=F,Q(1,1)=T,Q(1,2)=F,

Q(2,1)=F,Q(2,2)=T,在此解释下,x=1时,P(1,1)?Q(1,1)为T,P(1,2)?Q(1,2)为T;x=2时,P(2,1)?Q(2,1)为F,P(2,2)?Q(2,2)为T。所以在此解释下,本题谓词公式的真值为T。 6. 对谓词指派的真值为:P(1,1)=T,P(1,2)=F,P(2,1)=T,P(2,2)=F,Q(1,1)=F,Q(1,2)=T,

Q(2,1)=T,Q(2,2)=F,在此解释下,x=1时,P(1,1)?Q(1,1)为F,P(1,2)?Q(1,2)为T;x=2时,P(2,1)?Q(2,1)为T,P(2,2)?Q(2,2)为T。所以在此解释下,本题谓词公式的真值为T。 7. 对谓词指派的真值为:P(1,1)=T,P(1,2)=F,P(2,1)=T,P(2,2)=F,Q(1,1)=F,Q(1,2)=T,

Q(2,1)=F,Q(2,2)=T,在此解释下,x=1时,P(1,1)?Q(1,1)为F,P(1,2)?Q(1,2)为T;x=2时,P(2,1)?Q(2,1)为F,P(2,2)?Q(2,2)为T。所以在此解释下,本题谓词公式的真值为F。 8. 对谓词指派的真值为:P(1,1)=T,P(1,2)=F,P(2,1)=F,P(2,2)=T,Q(1,1)=T,Q(1,2)=F,

Q(2,1)=F,Q(2,2)=T,在此解释下,x=1时,P(1,1)?Q(1,1)为T,P(1,2)?Q(1,2)为T;x=2时,P(2,1)?Q(2,1)为T,P(2,2)?Q(2,2)为T。所以在此解释下,本题谓词公式的真值为T。 9. 对谓词指派的真值为:P(1,1)=T,P(1,2)=F,P(2,1)=F,P(2,2)=T,Q(1,1)=F,Q(1,2)=T,

Q(2,1)=T,Q(2,2)=F,在此解释下,x=1时,P(1,1)?Q(1,1)为F,P(1,2)?Q(1,2)为T;x=2时,P(2,1)?Q(2,1)为T,P(2,2)?Q(2,2)为F。所以在此解释下,本题谓词公式的真值为F。 10. 对谓词指派的真值为:P(1,1)=T,P(1,2)=F,P(2,1)=F,P(2,2)=T,Q(1,1)=F,Q(1,2)=T,

Q(2,1)=F,Q(2,2)=T,在此解释下,x=1时,P(1,1)?Q(1,1)为F,P(1,2)?Q(1,2)为T;x=2时,P(2,1)?Q(2,1)为T,P(2,2)?Q(2,2)为T。所以在此解释下,本题谓词公式的真值为T。 11. 对谓词指派的真值为:P(1,1)=F,P(1,2)=T,P(2,1)=T,P(2,2)=F,Q(1,1)=T,Q(1,2)=F,

Q(2,1)=F,Q(2,2)=T,在此解释下,x=1时,P(1,1)?Q(1,1)为T,P(1,2)?Q(1,2)为F;x=2时,P(2,1)?Q(2,1)为F,P(2,2)?Q(2,2)为T。所以在此解释下,本题谓词公式的真值为F。 12. 对谓词指派的真值为:P(1,1)=F,P(1,2)=T,P(2,1)=T,P(2,2)=F,Q(1,1)=F,Q(1,2)=T,

Q(2,1)=T,Q(2,2)=F,在此解释下,x=1时,P(1,1)?Q(1,1)为T,P(1,2)?Q(1,2)为T;x=2时,P(2,1)?Q(2,1)为T,P(2,2)?Q(2,2)为T。所以在此解释下,本题谓词公式的真值为T。 13. 对谓词指派的真值为:P(1,1)=F,P(1,2)=T,P(2,1)=T,P(2,2)=F,Q(1,1)=F,Q(1,2)=T,

Q(2,1)=F,Q(2,2)=T,在此解释下,x=1时,P(1,1)?Q(1,1)为T,P(1,2)?Q(1,2)为T;x=2时,P(2,1)?Q(2,1)为F,P(2,2)?Q(2,2)为T。所以在此解释下,本题谓词公式的真值为T。 14. 对谓词指派的真值为:P(1,1)=F,P(1,2)=T,P(2,1)=F,P(2,2)=T,Q(1,1)=T,Q(1,2)=F,

Q(2,1)=F,Q(2,2)=T,在此解释下,x=1时,P(1,1)?Q(1,1)为T,P(1,2)?Q(1,2)为F;x=2时,P(2,1)?Q(2,1)为T,P(2,2)?Q(2,2)为T。所以在此解释下,本题谓词公式的真值为T。 15. 对谓词指派的真值为:P(1,1)=F,P(1,2)=T,P(2,1)=F,P(2,2)=T,Q(1,1)=F,Q(1,2)=T,

Q(2,1)=T,Q(2,2)=F,在此解释下,x=1时,P(1,1)?Q(1,1)为T,P(1,2)?Q(1,2)为T;x=2时,P(2,1)?Q(2,1)为T,P(2,2)?Q(2,2)为F。所以在此解释下,本题谓词公式的真值为F。 16. 对谓词指派的真值为:P(1,1)=F,P(1,2)=T,P(2,1)=F,P(2,2)=T,Q(1,1)=F,Q(1,2)=T,

Q(2,1)=F,Q(2,2)=T,在此解释下,x=1时,P(1,1)?Q(1,1)为T,P(1,2)?Q(1,2)为T;x=2时,P(2,1)?Q(2,1)为T,P(2,2)?Q(2,2)为T。所以在此解释下,本题谓词公式的真值为T。

3.9判断以下公式对是否可合一;若可合一,则求出最一般的合一。

(1)P(a,b), P(x,y) 解:依据算法:

(1) 令W={P(a,b),P(x,y)}。 (2) 令?0=?,W0=W。 (3) W0未合一。

7

(4) 从左到右找不一致集,得D0={a,x}。 (5) 取x0=x,t0=a,则

?1=?0?{ t0/ x0}=?0?{a/ x}={a/ x} W1= W0?1={P(a,b),P(a,y)}

(3’) W1未合一。

(4’) 从左到右找不一致集,得D1={b,y}。

(5’) 取x1=y,t1=b,则

?2=?1?{ t1/ x1}=?1?{b/ y}={a/ x}?{b/ y}={a/x,b/y} W2= W1?2={P(a,b),P(a,b)}

(3’’) W2已合一,因为其中包含相同的表达式,这时?2={a/x,b/y}即为所求的mgu。

(2)P(f(z)),b), P(y,x) 解:依据算法:

(1) 令W={P(f(z),b),P(y,x)}。 (2) 令?0=?,W0=W。 (3) W0未合一。

(4) 从左到右找不一致集,得D0={f(z),y}。 (5) 取x0=y,t0=f(z),则

?1=?0?{ t0/ x0}=?0?{f(z)/ y}={f(z)/y} W1= W0?1={P(f(z),b),P(f(z),x)}

(3’) W1未合一。

(4’) 从左到右找不一致集,得D1={b,x}。

(5’) 取x1=x,t1=b,则

?2=?1?{ t1/ x1}=?1?{b/ x}={ f(z)/ y}?{ b/ x}={f(z)/y,b/x} W2= W1?2={P(f(z),b),P(f(z),b)}

(3’’) W2已合一,因为其中包含相同的表达式,这时?2={f(z)/y,b/x}即为所求的mgu。(3)P(f(x),y), P(y,f(a)) 解:依据算法:

(1) 令W={P(f(x),y),P(y,f(a))}。 (2) 令?0=?,W0=W。 (3) W0未合一。

(4) 从左到右找不一致集,得D0={f(x),y}。 (5) 取x0=y,t0=f(x),则

?1=?0?{ t0/ x0}=?0?{f(x)/ y}={f(x)/y} W1= W0?1={P(f(x),f(x)),P(f(x),f(a))}

(3’) W1未合一。

(4’) 从左到右找不一致集,得D1={y,f(a)}。

(5’) 取x1=y,t1=f(a),则

?2=?1?{ t1/ x1}=?1?{f(a)/ y}={ f(x)/ y}?{ f(a)/ y}={f(x)/y} W2= W1?2={P(f(x),f(x)),P(f(x),f(a))}

(6) 算法终止,W的mgu不存在。 (4)P(f(y),y,x), P(x,f(a),f(b)) 解:依据算法:

(1) 令W={P(f(y),y,x),P(x,f(a),f(b))}。 (2) 令?0=?,W0=W。

8

(3) W0未合一。

(4) 从左到右找不一致集,得D0={f(y),x}。 (5) 取x0=x,t0=f(y),则

?1=?0?{ t0/ x0}=?0?{f(y)/ x}={f(y)/x} W1= W0?1={P(f(y),y,f(y)),P(f(y),f(a),f(b))}

(3’) W1未合一。

(4’) 从左到右找不一致集,得D1={y,f(a)}。

(5’) 取x1=y,t1=f(a),则

?2=?1?{ t1/ x1}=?1?{f(a)/ y}={ f(y)/ x}?{ f(a)/ y}={f(f(a))/x,f(a)/y} W2= W1?2={P(f(f(a)),f(a),f(f(a))),P(f(f(a)),f(a),f(b))}

(6) 算法终止,W的mgu不存在。 (5)P(x,y), P(y,x) 解:依据算法:

(1) 令W={P(x,y),P(y,x)}。 (2) 令?0=?,W0=W。 (3) W0未合一。

(4) 从左到右找不一致集,得D0={x,y}。 (5) 取x0=x,t0=y,则

?1=?0?{ t0/ x0}=?0?{y/ x}={y/ x} W1= W0?1={P(y,y),P(y,y)}

(3’) W2已合一,因为其中包含相同的表达式,这时?1={y/x}即为所求的mgu。

3.13把下列谓词公式分别化为相应的子句集:

(1)(?z)(?y)(P(z,y)?Q(z,y)) 解:所求子句集为S={P(z,y),(z,y)} (2)(?x)(?y)(P(x,y)?Q(x,y)) 解:原式?(?x)(?y)(?P(x,y)?Q(x,y)) 所求子句集为S={?P(x,y)?Q(x,y)} (3)(?x)(?y)(P(x,y)?(Q(x,y)?R(x,y))) 解:原式?(?x)(?y)(P(x,y)?(?Q(x,y)?R(x,y))) ?(?x)(P(x,f(x))?(?Q(x,f(x))?R(x,f(x)))) 所求子句集为S={ P(x,f(x))?(?Q(x,f(x))?R(x,f(x)))} (4)(?x) (?y) (?z)(P(x,y)?Q(x,y)?R(x,z)) 解:原式?(?x) (?y) (?z)(?P(x,y)?Q(x,y)?R(x,z)) ?(?x) (?y) (?P(x,y)?Q(x,y)?R(x,f(x,y))) 所求子句集为S={?P(x,y)?Q(x,y)?R(x,f(x,y))}

(5)(?x) (?y) (?z) (?u) (?v) (?w)(P(x,y,z,u,v,w)?(Q(x,y,z,u,v,w)??R(x,z,w))) 解

?(?x)

(?y) (?y)

(?z)

(?u)

(?v) (?z)(?v)

(P(x,y,z,u,v,f(z,v))?(Q(x,y,z,u,v,f(z,v))??R(x,z,f(z,v))))

?(?x)

(P(x,y,z,f(z),v,f(z,v))?(Q(x,y,z,f(z),v,f(z,v))??R(x,z,f(z,v))))

?(?z)(?v) (P(a,b,z,f(z),v,f(z,v))?(Q(a,b,z,f(z),v,f(z,v))??R(a,b,f(z,v)))) 所求子句集为S={ P(a,b,z,f(z),v,f(z,v)),Q(a,b,z,f(z),v,f(z,v))??R(a,b,f(z,v))}

3.14判断下列子句集中哪些是不可满足的:

(1)S={?P?Q, ?Q,P, ?P }

9

解:使用归结推理:

(1) ?P?Q (2) ?Q (3)P (4) ?P (3)与(4)归结得到NIL,因此S是不可满足的。 (2)S={P?Q, ?P?Q,P??Q, ?P??Q } 解:使用归结推理:

(1) P?Q (2) ?P?Q (3) P??Q (4) ?P??Q (1)与(2)归结得 (5)Q (3)与(5)归结得 (6)P (4)与(6)归结得 (7) ?Q

(5)与(7)归结得NIL,因此S是不可满足的。 (3)S={P(y)?Q(y), ?P(f(x)) ?R(a) } 解:使用归结推理:

设C1= P(y)?Q(y),C2=?P(f(x)) ?R(a),选L1= P(y),L2=?P(f(x)),则

L1与L2的mgu是?={f(x)/y},C1 与C2的二元归结式C12=Q(f(x))?R(a),因此S是可满足的。 (4)S={?P(x)?Q(x), ?P(y)?R(y),P(a), S(a), ?S(z)??R(z) } 解:使用归结推理:

(1) ?P(x)?Q(x) (2) ?P(y)?R(y) (3) P(a) (4) S(a) (5) ?S(z)??R(z) (2)与(3)归结得到 (6)R(a) (4)与(5)归结得到 (7) ?R(a)

(6)与(7)归结得到NIL,因此S是不可满足的。

(5)S={?P(x)? ?Q(y) ? ?L(x,y), P(a), ?R(z) ? L(a,z) ,R(b),Q(b) } 解:使用归结推理:

(1) ?P(x)? ?Q(y) ? ?L(x,y) (2) P(a) (3) ?R(z) ? L(a,z) (4) R(b) (5) Q(b) (1)与(2)归结得到 (6) ?Q(y) ? ?L(a,y) (5)与(6)归结得到 (7) ?L(a,b) (3)与(4)归结得到 (8) L(a,b)

(7)与(8)归结得到NIL,因此S是不可满足的。

(6)S={?P(x)?Q(f(x),a), ?P(h(y))?Q(f(h(y)),a) ??P(z) } 解:使用归结推理:

令C1= ?P(x)?Q(f(x),a),C2= ?P(h(y))?Q(f(h(y)),a) ??P(z) 则 C2内部的mgu是?={h(y)/z},合一后C2’=?P(h(y))?Q(f(h(y)),a) 选L1=?P(x),L2=?P(h(y)) 则 L1与L2的mgu是?={h(y)/x},

C1 与C2’的二元归结式C12=?P(h(y))?Q(f(h(y)),a),因此S是可满足的。 (7)S={P(x)? Q(x) ? R(x), ?P(y) ? R(y) , ?Q(a), ?R(b) } 解:使用归结推理:

(1) P(x)? Q(x) ? R(x) (2) ?P(y) ? R(y) (3) ?Q(a) (4) ?R(b) (1)与(3)归结得到 (5) P(a) ? R(a) (2)与(4)归结得到 (6) ?P(b) (5)与(6)归结得到 (7) R(b)

(4)与(7)归结得到NIL,因此S是不可满足的。 (8)S={P(x)?Q(x), ?Q(y)?R(y), ?P(z)?Q(z) , ?R(u)} 解:使用归结推理:

(1) P(x)?Q(x) (2) ?Q(y)?R(y) (3) ?P(z)?Q(z) (4) ?R(u)

10

福利:打开支付宝首页搜索“608066754”即可领取红包,吃个早点,买杯饮料肯定够了,红包加倍最高可以领取99元红包!

「觉得内容不错,打赏支持一下」

南京廖华

觉得内容不错,打赏支持一下

使用微信扫描二维码完成支付

福利:打开支付宝扫描二维码领红包,可免费下载资料 微信:17702577729