离散数学 赵一鸣 阚海斌 吴永辉 dshu25

《离散数学 赵一鸣 阚海斌 吴永辉 dshu25》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十九章谓词逻辑§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，则命题不正确。通过分解命题可

2、以发现，命题的内部结构包含了下述内容：(1)一些个体对象及对它们进行的某些运算；(2)关于这些对象的一个关系。定义19.1:由表示某种不确定的可列个个体对象全体所组成的集合称为个体变元集，记为X={x1,…,xn,…}，这里xi称为个体变元，用来表示不确定的个体对象。由表示某种确定的个体对象全体所组成的集合称为个体常元集，它是可列集或有限集，也可以是空集，记为C={c1,…,cn,…}，这里ci称为个体常元，用来表示某个确定的个体对象。对于类型T(1)=,这里Tn={fni

3、ar(fni)=n}，并且

4、Tn

5、≤0(故

6、T(1)

7、≤0),由定理19.1，

8、可构造X∪C上的自由T(1)-代数I。当T(1)=时，I=X∪C；当T(1)，I=,其中I0=X∪C(这是因为T0=)，I1={(f1i,xj)

9、f1iT1,xjX}∪{(f1i,cj)

10、f1iT1,cjC}∪(f2i,xj,xk)

11、f2iT2,xj,xkX}∪(f2i,xj,ck)

12、f2iT2,xjX,ckC}∪(f2i,cj,xk)

13、f2iT2,xkX,cjC}∪(f2i,cj,ck)

14、f2iT2,cj,ckC}∪∪(fki,y1,y2,yk)

15、fkiTk,yiX∪C}∪随着n的增大In将更为复杂。在I上定

16、义运算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

17、ar(f11)=1,ar(f21)=2,求I0，I1，I2，定义19.3:设关系集R=Rn表示某个对象集上的所有n元关系，即Rn={Rni

18、ar(Rni)=n}定义19.4:对任意的Rni

19、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为正实数集时，就不能用上述方式表

20、示。为此引进记号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为实数集时，就不

21、能用上述方式表示引进记号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(

22、Y)→P(Y)。定义19.5:原子公式集(作为生成元集)Y={Rn