谓词演算的推理理论-永真推理系统

《谓词演算的推理理论-永真推理系统》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章谓词演算的推理理论4.1谓词演算的永真推理系统4.1.1公理系统的组成部分4.1.2公里系统的推理过程4.2谓词演算的假设推理系统4.3谓词演算的归结推理系统4.1.1公理系统的组成部分一、语法部分(一)基本符号(二)公理(三)规则二、语义部分三、关于公理的几点说明（一）基本符号公理系统所允许出现的全体符号的集合。(1)命题变元：P，Q，R，……等字母表示命题变元(2)个体变元：x，y，……等小写字母表示个体变元(3)谓词变元：X，Y，……等大写字母表示谓词变元(4)联结词：、、、、是联结词(5)量词：全称量词、存在量词(6)括号：(，)是括

2、号(7)全称封闭符：△基本符号（续）(8)合式公式：(i)原子命题P是合式公式；(ii)谓词填式A(x1，x2，x3，…，xn)是合式公式；(iii)若A是公式，则A是合式公式；(iv)若A和B是合式公式，则(AB)，(AB)，(AB)，(AB)为公式；(v)若A是合式公式，x是A中出现的任何个体变元，则xA(x)，xA(x)为合式公式；(vi)只有有限次使用(i)、(ii)、(iii)、(iv)、(v)所得到的式子才是合式公式。基本符号（续）(9)全称封闭式：设为含有n个自由变元的公式，如果在前用全称量词把n个自由变元约束起来后所得到的公式，

3、称为的全称封闭式。记为△。例写出下式的全称封闭式=xP(x，y)uQ(u，v)解：△=△(xP(x，y)uQ(u，v))=yv(xP(x，y)uQ(u，v))（二）公理公理1△(PP)公理2△((P(QR))(Q(PR)))公理3△((PQ)((QR)(PR)))公理4△((P(PQ))(PQ))公理5△((PQ)(PQ))公理6△((PQ)(QP))公理7△((PQ)((QP)(PQ)))调头传递凝缩与有关（二）公理公理8△((PQ)P)公理9△((PQ)Q)公理10△

4、(P(Q(PQ)))公理11△(P(PQ))公理12△(Q(PQ))公理13△((PR)((QR)((PQ)R)))公理14△((PQ)(QP))公理15△(PP)与∨有关与有关与∧有关（二）公理公理20△(xP(x)P(x))公理21△(P(x)xP(x))如果只有一个自由变元，公理20与公理21可以分别理解如下：x(yP(y)P(x))x(P(x)yP(y))与量词有关（三）规则(1)分离规则：如果△(AB)且△A，则△B。(2)全称规则：△(P(x))├△(xP(x))(其中中不

5、含自由的x)(3)全称量词消去规则：△xP(x)├P(x)(x可以为任意的变元)(4)存在量词引入规则：△(P(x))├△(xP(x))(其中中不含自由的x)回顾:量词作用域的收缩与扩张设公式中不含有自由的x，则下面的公式成立:x((x)→)=(x(x)→)x(→(x))=(→x(x))x((x)→)=(x(x)→)x(→(x))=(→x(x))存在量词引入全称量词引入二、语义部分(1)公理是永真公式。(2)规则规定如何从永真公式推出永真公式。分离规则指明，如果△(AB)永真且△A永真，则△B也为

6、永真公式。(3)定理为永真公式，它们是从公理出发利用上述规则推出来的公式。三、关于公理的几点说明(1)本系统中不引入代入规则，它的作用由下面的(2)来实现；(2)本系统中的所有公理我们把它看作公理模式，即只要形如某一公理，我们就称其为某一公理。如△(PP)、△((P(QR))(P(QR)))、△(xP(x)xP(x)))等均为公理1。第四章谓词演算的推理理论4.1谓词演算的永真推理系统4.1.1公理系统的组成部分4.1.2公里系统的推理过程4.2谓词演算的假设推理系统4.3谓词演算的归结推理系统例1(p41)已知定理△(P(QP)),求证:

7、全0规则△(x)├△x(x)证明：(1)△(x)(2)△((x)((PP)(x)))引用定理(3)△((PP)(x))(2)(1)分离(4)△((PP)x(x))全称规则(3)(5)△(PP)公理(1)(6)△x(x)(4)(5)分离则有全0规则△(x)├△x(x)全n规则、存n规则全n规则：△(1(2(…(n(x))…)├△(1(2(…(nx(x))…)存n规则：△(1(2(…(n((x)))…)├△(1(2(…(n(x(x)))…)全1规则=全称规

8、则存0规则=存在规则例试