第十九章 谓词逻辑

§1 谓词代数 一、项与原子公式 一数的平方与一数的平方根之和大于0”。 命题涉及3个个体对象:两个不确定数，x1,x2 一个常数0，用c1表示； 涉及3个函数，两个一元运算(即平方与平方根)，分别记为f1(1),f1(2)， 求和运算则是二元运算，用f2(1)表示； 最后，还有一个关于数的二元关系“大于”，用R2(1)表示。 命题表示成R2(1)(f2(1)(f1(1)(x1),f1(2)(x2)),c1)。 这个命题是否正确，取决于对x1,x2所作的赋值。 若x1,x2都是非负实数且至少有一个不为0，则命题正确 若x1,x2都为0，则命题不正确。

通过分解命题可以发现，命题的内部结构包含了下述内容： (1)一些个体对象及对它们进行的某些运算； (2)关于这些对象的一个关系。

定义19.1:由表示某种不确定的可列个个体对象全体所组成的集合称为个体变元集，记为X={x1,…,xn,…}，这里xi称为个体变元，用来表示不确定的个体对象。由表示某种确定的个体对象全体所组成的集合称为个体常元集，它是可列集或有限集，也可以是空集，记为C= {c1,…,cn,…}，这里ci称为个体常元，用来表示某个确定的个体对象。

,这里Tn={fni|ar(fni)=n}， 并且|Tn|≤0(故|T(1)|≤0),由定理19.1，可构造X∪C上的自由T(1)-代数I。当T(1)=时，I=X∪C；当T(1)，I= , 其中I0=X∪C (这是因为T0=)，I1={(f1i,xj)|f1iT1,xjX}∪{(f1i,cj)|f1iT1,cjC} ∪(f2i,xj,xk)|f2iT2,xj,xkX} ∪(f2i,xj,ck)|f2iT2,xjX,ckC} ∪(f2i,cj,xk)|f2iT2,xkX,cjC} ∪(f2i,cj,ck)|f2iT2,cj,ckC}∪ ∪(fki,y1,y2,yk)|fkiTk,yiX∪C}∪

随着n的增大In将更为复杂。 在I上定义运算fki:Ik→I，使得fki(a1,,ak)=(fki,a1,,ak)，这里ajI (j=1,,k)，即fki为I上的第i个k元运算。 定义19.2:X∪C上的自由T(1)-代数I称为项集，I中的每个元素称为项，不含个体变元的项称为闭项，I上的代数运算fni称为第i个n元函数词。如果X∪C,T(1)可列，项集I也是可列集。

例：设C=,T=({f11,f21|ar(f11)=1, ar(f21)=2,求I0，I1，I2，

集上的所有n元关系，即Rn ={Rni|ar(Rni)=n} 定义19.4:对任意的RniRnR，称I上的n元关系Rni(t1, ,tn)为I上的原子公式(特别地，R0i就是原子命题公式),这里t1, ,tnI,Rni称为第i个n元谓词。基于关系集R的所有I上的原子公式全体称为I的原子公式集，记为Y。 原子公式集Y是可列集。 C=, T(1)=,R=R0(这里R0为0元关系集)时，原子公式就是命题逻辑中的命题变元即原子命题。

二、谓词代数 例：设A={1,…,100}，对于命题“A中所有数都大于0”. ci表示数字i，R2i表示二元关系“大于”， 命题形式化地表示为： R2i(c1,0)…R2i(c100,0)。 当A为正实数集时，就不能用上述方式表示。为此引进记号xR2i(x,0)来表示上面的命题。这里x称为全称量词。

注意:x中的x只是虚设的，xR2i(x,0)并不依赖于x，事实上也可用yR2i(y,0)表示上述命题。 对于命题“对所有的x，使得有p(x)就必有q(x)”，可表示为x (p(x)→q(x))。 设A={-2,-1,0,1,2},对于命题“在A中必存在大于0的数”， 令ci表示数字i，R2(1)表示二元关系“大于”，则命题可形式化地表示为： R2(1)(c-2,0)R2(1)(c-1,0)R2(1)(c0,0) R2(1)(c1,0)R2(1)(c2,0)。

当A为实数集时，就不能用上述方式表示 引进记号xR2(1)(x,0)来表示上面的命题。这里x称为存在量词。要注意的是，在x中的x只是虚设的，xR2(1)(x,0)并不依赖于x，事实上也可用yR2(1)(y,0)表示上述命题。 存在量词与全称量词有联系。 对命题“不存在x具有性质p”， 可表示为(xp(x))， 也可表示为x(p(x))。

因此x和x有相同的含义，所以在构造模型时，就不需要包括存在量词，而只要定义x=x。 谓词代数建立在原子公式集Y上，并且谓词代数P(Y)除了必须是 {F, →}-代数外，还必须使个体变元集X中的每个个体变元x，都有函数x:P(Y)→P(Y)。

定义19.5:原子公式集(作为生成元集) Y={Rn(t1, ,tn)|RnR,tiI, 1i n}上关于类型{F,→,x|xX}的自由代数称为谓词代数，记为P(Y)，P(Y)中的元素称为谓词合式公式，因此P(Y)也称为谓词公式集。这里F是0元运算，→为二元运算，而x则是一元运算。

与命题代数类似，可利用F，→和x来定义一元运算和x以及其它二元运算, , ，现定义如下：

定义19.6:在谓词合式公式q=xp(这里表示或)中，称p为x的辖域。p中x的出现称为x在q中的约束出现。p中不是约束出现的其它变元的出现称为变元在q中的自由出现。如果变元x在q中约束出现，则称x是q中的约束变元。如果变元x在q中自由出现，则称x是q中的自由变元。 q中自由出现的个体变元全体构成的集合用var(q)表示，若var(q)=，则称q为闭式，此时q中无自由变元。 x可能既是自由变元，又是约束变元。

对于AP(Y)，A中所有公式的自由变元全体构成的集合用var(A)来表示。 例:指出下列谓词公式中，量词的辖域，个体变元的自由出现和约束出现： (1)x(R11(x)→yR21(x,y)) (2)x(xR11(x)→R21(x,y))→R22(x,y) 解:在(1)中,量词y的辖域是R21(x,y)，量词x的辖域是R11(x)→yR21(x,y)，x的两次出现都是约束出现，y也是约束出现的，x和y都是约束变元,是闭式

(2)x(xR11(x)→R21(x,y))→R22(x,y) 在(2)中，x的辖域是R11(x)，x的辖域是xR11(x)→R21(x,y)。

定义19.7:设p(x)是P(Y)中谓词合式公式，x是其自由变元之一，t(z)是项，z 代表t中的任一个个体变元。当x不出现在p的z的辖域内，则称t对于p中的x是自由的，否则就称t对于p中的x是不自由的。 当t代入p(x)中的x而得p(t(z))时，z应是p的自由变元，但如果x出现在p的z的辖域内，z就成为p(t(z))中的约束变元 这时t对于p中的x是不自由的，变元的性质就完全不同了,这在语义解释时即可发现。

例:在x1R21(x1,x2)→x3R22(x3,x1)中，项f21(x1,x3)对自由变元x1,x2都是不自由的；

约定:用p(x)或p表示P(Y)中的元素(即谓词合式公式) p(x)并不意味着x在p(x)中是自由出现的，x可以不自由出现，甚至不出现。 用p(t)表示由项t去替换p(x)中所有自由出现的x所得到的结果。 例：p(x2)=x1R21(x1,x2)→x3R22(x3,x1) p(f22(x2,x3))=x1R21(x1, f22(x2,x3))→ x3R22(x3,x1) p(x1)=x1R21(x1,x2)→x3R22(x3,x1) p(f11(x2))=x1R21(x1, x2))→ x3R22(x3,f11(x2))

定义19.8：设pP(Y)，p的量词深度和层次分别用d(p)和l(p)表示，定义为： (i)d(F)=l(F)=d(q)=l(q)=0，q是P(Y)中的原子公式。 (ii)d(p1→p2)=max{d(p1),d(p2)}， l(p1→ p2)=1+max{ l(p1),l(p2)}。

作业:P256 1,2,6,7,8