复旦大学：《离散数学 Discrete Mathematics（下）》英文课件（赵一鸣）26/32

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

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

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

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

对于类型T=U,这里Tn={ar(f1)=n}, 并且TN0故好0,由定理191,可构造 X∪C上的自由T(-代数I。当T(=②时, I=X∪C;当T,I=U,其中I=XUC (这是因为T0=) l1={,x川f∈T;xX}U(f,c)f1∈eTn,∈C 2yjAk川12 ∈ 294jAk ∈X U(2,xpu)f2∈T2x∈X,k∈C (f2,cpx)f2∈T2,xk∈X,c∈C U( 2]js 2pk∈C}U U(f’y12y2,yk)fk∈Ty;∈x∪C}∪

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

随着n的增大L将更为复杂。 在I上定义运算fⅣ,使得 f(a1,…,a)=(321…2a),这里a;∈I j=1,k),即f为Ⅰ上的第个k元运 定义212X∪C上的自由T(代数称为项 集,I中的每个元素称为项,不含个体变 元的项称为历亟,I上的代数运算f称为 第个n元函数词。如果XUC,T可列, 项集I也是可列集

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

例:设C=②,T=({f1ar(1)=1,ar(2)=2,求 09119129

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

定义213设关系集R=RR表示某个对象 集上的所有n元关系,即Rn={ Rn are(R)=n} 定义21对任意的R∈Rn三R,称I上的n元关 系Ru(t1,…,t为上的原子公式特别地,R0 就是原子命题公式,这里t,…,tn∈I,R称为第i 个n元谓词。基于关系集R的所有I上的原子公 式全体称为原子公式集,记为Y 原子公式集Y是可列集。 C=,T(=,R=R0这里R为0元关系集)时,原子公 式就是命题逻辑中的命题变元即原子命题。2

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

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

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

注意Vx中的x只是虚设的,∨xR2(x,0)并 不依赖于x,事实上也可用yR2(y,0)表示 上述命题。 对于命题“对所有的x,使得有p(x)就必有 q(x)”,可表示为x(p(x)→q(x) 设A={-2,-1,0,1,2}对于命题“在A中必存在 大于0的数”, 令c表示数字i,R2)表示二元关系“大 于”,则命题可形式化地表示为 R2(c20)R2(c1,0NR2(c00) R2(c1,0)R21(c20)

 注意:x中的x只是虚设的，xR2 i (x,0)并 不依赖于x，事实上也可用yR2 i (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(x,0来表示上面的命题。 这里3x称为存在量词。要注意的是,在 彐x中的x只是虚设的,丑xR2(x0)并不依 赖于x,事实上也可用彐yR2(y,0)表示上 述命题。 存在量词与全称量词有联系 对命题“不存在x具有性质p”, 可表示为(彐xp(x) ■也可表示为vx(p(x)

 当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上,并且谓 词代数PY)除了必须是,→}代数外, 还必须使个体变元集X中的每个个体变元 x,都有函数x:P(Y)→P(Y)

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