§1谓词代数通过分解命题可以发现，命题的内部结构包含了下述内容：(1)一些个体对象及对它们进行的某些运算；(2)关于这些对象的一个关系。定义19.1:由表示某种不确定的可列个个体对象全体所组成的集合称为个体变元集，记为X={x1,…,xn,…}，这里xi称为个体变元，用来表示不确定的个体对象。由表示某种确定的个体对象全体所组成的集合称为个体常元集，它是可列集或有限集，也可以是空集，记为C={c1,…,cn,…}，这里ci称为个体常元，用来表示某个确定的个体对象。对于类型T(1)=随着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，定义19.3:设关系集R=二、谓词代数例：设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)