复旦大学：《离散数学——代数结构与数理逻辑》PPT课件_25/29

第十九章谓词逻辑

第十九章 谓词逻辑

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

§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)一些个体对象及对它们进行的某些运 算 n(2)关于这些对象的一个关系

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

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

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

对于类型T=U,这里Tn={ f ar(f)=n} 并且T然0(故Na),由定理191,可构 造X∪C上的自由T代数I。当T=②时, l=XUC;当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元运 定义192X∪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元运 算。  定义19.2:X∪C上的自由T(1) -代数I称为项 集，I中的每个元素称为项，不含个体变 元的项称为闭项，I上的代数运算fn i称为 第i个n元函数词。如果X∪C,T(1)可列， 项集I也是可列集

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

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

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

 定义19.3:设关系集R=   n=0 Rn Rn表示某个对象 集上的所有n元关系，即Rn ={Rn i |ar(Rn i )=n} 定义19.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称为全称量词

注意x中的x只是虚设的,vxR2(x,0)并 不依赖于x,事实上也可用wyR2y,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)