第3章-参考答案.docx
《第3章-参考答案.docx》由会员分享,可在线阅读,更多相关《第3章-参考答案.docx(8页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第3章 确定性推理部分参考答案3.8 判断下列公式是否为可合一,若可合一,则求出其最一般合一。(1) P(a, b), P(x, y)(2) P(f(x), b), P(y, z)(3) P(f(x), y), P(y, f(b)(4) P(f(y), y, x), P(x, f(a), f(b) (5) P(x, y), P(y, x)解:(1) 可合一,其最一般和一为:=a/x, b/y。(2) 可合一,其最一般和一为:=y/f(x), b/z。(3) 可合一,其最一般和一为:= f(b)/y, b/x。(4) 不可合一。(5) 可合一,其最一般和一为:= y/x。3.11 把下列谓词公式
2、化成子句集:(1) (x)(y)(P(x, y)Q(x, y)(2) (x)(y)(P(x, y)Q(x, y)(3) (x)(y)(P(x, y)(Q(x, y)R(x, y)(4) (x) (y) (z)(P(x, y)Q(x, y)R(x, z) 解:(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),先消去连接词“”得
3、:(x)(y)(P(x, y)Q(x, y)此公式已为Skolem标准型。 再消去全称量词得子句集: 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)此公式已为前束范式。再消去存在量词,即用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) (4) 对谓词(x) (y) (z)(P(x, y)
4、Q(x, y)R(x, z),先消去连接词“”得:(x) (y) (z)(P(x, y)Q(x, y)R(x, z)再消去存在量词,即用Skolem函数f(x)替换y得:(x) (y) (P(x, y)Q(x, y)R(x, f(x,y)此公式已为Skolem标准型。 最后消去全称量词得子句集:S=P(x, y)Q(x, y)R(x, f(x,y)3-13 判断下列子句集中哪些是不可满足的:(1) PQ, Q, P, P(2) PQ , PQ, PQ, PQ (3) P(y)Q(y) , P(f(x)R(a)(4) P(x)Q(x) , P(y)R(y), P(a), S(a), S(z)R(
5、z)(5) P(x)Q(f(x),a) , P(h(y)Q(f(h(y), a)P(z)(6) P(x)Q(x)R(x) , P(y)R(y), Q(a), R(b) 解:(1) 不可满足,其归结过程为:PQQPPNIL(2) 不可满足,其归结过程为:PQPQQPQPQQNIL(3) 不是不可满足的,原因是不能由它导出空子句。(4) 不可满足,其归结过程略(5) 不是不可满足的,原因是不能由它导出空子句。(6) 不可满足,其归结过程略 3.14 对下列各题分别证明G是否为F1,F2,Fn的逻辑结论:(1) F: (x)(y)(P(x, y)G: (y)(x)(P(x, y)(2) F: (x)
6、(P(x)(Q(a)Q(b)G: (x) (P(x)Q(x)(3) F: (x)(y)(P(f(x)(Q(f(y)G: P(f(a)P(y)Q(y)(4) F1: (x)(P(x)(y)(Q(y)L(x.y)F2: (x) (P(x)(y)(R(y)L(x.y)G: (x)(R(x)Q(x)(5) F1: (x)(P(x)(Q(x)R(x)F2: (x) (P(x)S(x)G: (x) (S(x)R(x) 解:(1) 先将F和G化成子句集: S=P(a,b), P(x,b) 再对S进行归结:P(x,b)P(a,b)NIL a/x 所以,G是F的逻辑结论(2) 先将F和G化成子句集由F得:S1=
7、P(x),(Q(a)Q(b)由于G为: (x) (P(x)Q(x),即 (x) ( P(x) Q(x),可得: S2= P(x) Q(x)因此,扩充的子句集为:S= P(x),(Q(a)Q(b), P(x) Q(x) 再对S进行归结:Q(a)Q(b)Q(a) P(x) Q(x) P(a)P(x)NILQ(a)Q(b) a/b P(x) Q(x)Q(a)a/x P(a)P(x) a/xNIL 所以,G是F的逻辑结论 同理可求得(3)、(4)和(5),其求解过程略。 3.15 设已知:(1) 如果x是y的父亲,y是z的父亲,则x是z的祖父;(2) 每个人都有一个父亲。使用归结演绎推理证明:对于某人
8、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) 对上述扩充的子句集,其归结推理过程如下: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
9、(y)P(r)F(s,r)P(y)P(z)P(y)P(u)NIL x/v,z/ux/s,y/ry/s,z/r y/z y/u 由于导出了空子句,故结论得证。3.16 假设张被盗,公安局派出5个人去调查。案情分析时,贞察员A说:“赵及钱中至少有一个人作案”,贞察员B说:“钱及孙中至少有一个人作案”,贞察员C说:“孙及李中至少有一个人作案”,贞察员D说:“赵及孙中至少有一个人及此案无关”,贞察员E说:“钱及李中至少有一个人及此案无关”。如果这5个侦察员的话都是可信的,使用归结演绎推理求出谁是盗窃犯。解:(1) 先定义谓词和常量设C(x)表示x作案,Z表示赵,Q表示钱,S表示孙,L表示李(2) 将已
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 参考答案
限制150内