求下列谓词公式的子句集

《求下列谓词公式的子句集》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、习题三求下列谓词公式的子句集。(1)xy(P(x,y)Q(x,y))解：去掉存在量词变为：P(a,b)Q(a,b)变成子句集{P(a,b),Q(a,b)}(2)xy(P(x,y)Q(x,y))解：去掉蕴涵符号变为：xy(¬P(x,y)Q(x,y))去掉全称量词变为：¬P(x,y)Q(x,y)变成子句集{¬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y((¬P(x,y)

2、¬Q(x,y))R(x,y))去掉存在量词变为：x((¬P(x,f(x))¬Q(x,f(x)))R(x,f(x)))去掉全称量词变为：(¬P(x,f(x))¬Q(x,f(x)))R(x,f(x)化合取范式为：(¬P(x,f(x))R(x,f(x))(¬Q(x,f(x))R(x,f(x))变元：(¬P(x,f(x))R(x,f(x)))(¬Q(y,f(y))R(y,f(y)))变成子句集{¬P(x,f(x))R(x,f(x)),¬Q(y,f(y))R(y,f(y))}(4)x(P(x)y(P(y)R(x,y))

3、)解：去掉蕴涵符号变为：x(¬(P(x)y(P(y)R(x,y)))去掉存在量词变为：x(¬(P(x)(P(f(x))R(x,f(x)))去掉全称量词变为：(¬(P(x)(P(f(x))R(x,f(x)))化合取范式为：(¬(P(x)P(f(x)))(¬(P(x)R(x,f(x)))变元：(¬(P(x)P(f(x)))(¬(P(y)R(y,f(y)))变为子句集：{¬(P(x)P(f(x)),¬(P(y)R(y,f(y))}(5)x(P(x)x(P(y)R(x,y)))解：去掉蕴涵符号变为：x(P(x)

4、x(¬P(y)R(x,y)))去掉存在量词变为：P(a)x(¬P(y)R(a,y))去掉全称量词变为：P(a)(¬P(y)R(a,y))变成子句集：{P(a)，¬P(y)R(a,y)}(6)xyzuvw(p(x,y,z,u,v,w)(Q(x,y,z,u,v,w)¬R(x,z,w)))解：去掉存在量词变为：zv(p(a,b,z,f(z),v,g(z,v))(Q(a,b,z,f(z),v,g(z,v)¬R(a,z,g(z,v)))去掉全称量词变为：p(a,b,z,f(z),v,g(z,v))(Q(a,b,z

5、,f(z),v,g(z,v)¬R(a,z,g(z,v))变元：p(a,b,x,f(x),y,g(x,y))(Q(a,b,z,f(z),v,g(z,v)¬R(a,z,g(z,v))化成子句集：{p(a,b,x,f(x),y,g(x,y)),Q(a,b,z,f(z),v,g(z,v)¬R(a,z,g(z,v))}3.试判断下列子句集中哪些是不可满足的。(1)S={P(y)¬Q(y),¬P(f(x))Q(y)}解：（1）P(y)¬Q(y)（2）¬P(f(x))Q(z)(适当改名使子句之间不含相同变元利用归结原理：（3）P(y)¬P(f

6、(x))(1)(2){y/z}（4）T{f(x)/y}归结不出空子句，所以原子句集是可以满足的。(2)S={¬P(x)Q(x),¬Q(y)R(y),P(a),R(a)}解：（1）¬P(x)Q(x)（2）¬Q(y)R(y)（3）P(a)（4）R(a)利用归结原理判断（5）Q(a)(1)(3){a/x}（6）R(a)(2)(5){a/x}归结不出空子句，所以是可满足的子句集。(3)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)

7、（3）¬R(z)L(a,z)（4）R(b)（5）Q(b)利用归结原理来进行判断（6）¬Q(y)¬L(a,y)(1)(2){a/x}（7）L(a,b)(3)(4){b/z}（8）¬L(a,b)（6）（5）{b/y}（9）Nil（8）（7）得到NIL所以原子句集不可满足。(4)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)利用归结原理来判断（5）（6）（7）(5)S={P(x)Q(x),¬Q(y)R(y),¬P

8、(z)Q(z),¬R(u)}解：（1）P(x)Q(x)（2）¬Q(y)R(y)（3）¬P(z)Q(z)（4）¬R(u)利用归结原