解释和赋值 解释是对每个符号说明其含义.赋值是指岀每个公式的真假值 将非逻辑符号集￡记为C={F}erU{}enU{ck}kek 解释的定义 定义3.,15对非逻辑符号集C,Nc的解释工是如下的四元序列 (Dr,{F}i∈r,{}∈J,{c}k∈) ·Dx是一个非空集合,称为工的论域或个体域,简记为D ·对C的每个谓词变元符号F,设其为n元的(∈D,是D上的 个n元关系,即F≤D,称F为F在工中的解释 ·对C的每个函数变元符号f,设其为m元的(∈J),方是D上的 一个m元函数,即方:Dm→D是一个映射,称为f在工中 的解释; ·对C的每个个体常元符号Ck(k∈K),是D中一个元素,即 ∝∈D,称∝为ck在工中的解释. 指派的定义 定义3.16设工是C的一个解释,D为工的论域,Nc在工中的 个指派是指如下的函数σ:{x0,x1,x2,…}→D.此时,σ(x;)∈D称 为x;在指派σ下的值(∈N) 定义3.18 设σ是Nc在解释工中的一个指派,x;是一个个体变元符号,a∈D, a(x;/a)是Nc在工中的如下指派: (x;/a)(x) a(x)j≠ 即:σ(x;/a)是将a中对x;指派的值改为a,其余x;(≠i,j∈N)的 值保持不变.σ(x;/a)又称为σ的一个xr-指派
L L = {Fi}i∈I ∪ {fj}j∈J ∪ {ck}k∈K. 3.15 L, NL I DI, {Fi}i∈I , {fj}j∈J , {ck}k∈K • DI I ! , " D . • L #$ Fi, % n (i ∈ I), Fi D & n ' ( Fi ⊆ Dn, Fi Fi I ) • L *$ fj , % m (j ∈ J), fj D & m * ( fj : Dm → D + fj fj I ) • L , Ck (k ∈ K), ck D ( ck ∈ D, ck ck I 3.16 % I L D I NL I - * σ : {x0, x1, x2, · · ·} → D. ./ σ(xi) ∈ D xi - σ (i ∈ N) 3.18 % σ NL I - xi $ a ∈ D, σ(xi/a) NL I - σ(xi/a)(xj) = a j = i σ(xj) j = i ( σ(xi/a) σ xi -0 a, xj (j = i, j ∈ N ) 123$ σ(xi/a) σ xi– - 1
例3.20 设C={F2,丹1,,3,C},对此C可以有如下两个解释: (1)1=(N,{F2},{,乃,},{可}》)其中 N为自然数集 P为N上的相等关系,即: F2={<m,n>|n∈N} f为N上的后继函数,即 f1:N→N,f1(m)=m+1(任n∈N) f为N上的加法函数,即 f:N2→N,f(<m,n>)=m+m(任m,n∈N) f3为N上的乘法函数,即 f3:N2→N,(<m,m>)=m·n(任m,n∈N) 为N中的元素0 (2)l2=(Q,{F2},{升1,,f},{2}),其中: Q为有理数集; F2为Q上的相等关系; 升为Q上的加1运算,即: f1:Q→Q,f(a)=a+1(任a∈Q 几与分别为Q上的加法与乘法函数 仍为Q中的元素0. 注:同一个一阶语言C可以有多个不同的解释
! 3.20 % L = {F2 , f 1 1 , f 2 2 , f 2 3 , c}, . L 4"#5 (1) I1 = N, {F2}, {f 1 1 , f 2 2 , f 2 3 }, {c}, N $6) F2 N &%7' ( F2 = {< n, n > | n ∈ N} f 1 1 N &89* ( f 1 1 : N → N, f 1 1 (n) = n +1 (: n ∈ N) f 2 2 N &;<* ( f 2 2 : N2 → N, f 2 2 (< m, n >) = m + n (: m, n ∈ N) f 2 3 N &=<* ( f 2 3 : N2 → N, f 2 3 (< m, n >) = m · n (: m, n ∈ N) c N 0. (2) I2 = Q, {F2}, {f 1 1 , f 2 2 , f 2 3 }, {c}, Q #>) F2 Q &%7') f 1 1 Q &; 1 &' ( f 1 1 : Q → Q, f 1 1 (a) = a +1 (: a ∈ Q) f 2 2 ( f 2 3 ?Æ Q &;<(=<* c @ Q 0. ): ÆA*+ L 4"#B3Æ 2
项的值 设σ是Nc在I中的一个指派,如下归纳定义Nc的项t在I中σ 下的值切(简记为t) (1)当t为个体变元符号x1(∈N)时,(x1)=0(x) (2)为t为个体常元符号ck时,(ck)=ck (3)当t为門(t1,t2,……,tm)时,=「m(t,鸪,……,tm) 在例320中,是Nc在1中的如下指派: a(x;)=i(任i∈N) 则:x=0(x;)=i(i∈N) C=0 (1(x1)=f(x)=升(1)=1+1=2∈N (f2(x1,x2)=f2(x,x) (f3(x1,x2)=f(x1,m)=x:吗=3 (1(2(x1,x4))=f1(2(x1,x4)”)=升(f(x,x4) (x1+x4)+1=1+4+1=6 对任任意项t及指派σ,t∈D
, % σ NL I - CDE NL - t I σ t σ I (" t σ): (1) F t $ xi (i ∈ N ) / (xi) σ I = σ(xi) . (2) t , ck / (ck) σ I = ck . (3) F t f m(t1, t2, ··· , tm) / t σ I = f m(t σ 1 , tσ 2 , ··· , tσ m). ! G 3.20 σ NL I1 - σ(xi) = i (: i ∈ N ) . xσ i = σ(xi) = i(i ∈ N ) cσ = c = 0 (f 1 1 (x1))σ = f 1 1 (xσ 1 ) = f 1 1 (1) = 1 + 1 = 2 ∈ N (f 2 2 (x1, x2))σ = f 2 2 (xσ 1 , xσ 1 ) = xσ 1 + xσ 2 =1+2=3 (f 2 3 (x1, x2))σ = f 3 2 (xσ 1 , xσ 1 ) = xσ 1 · xσ 2 = 3 (f 1 1 (f 2 2 (x1, x4)))σ = f 1 1 ((f 2 2 (x1, x4))σ ) = f 1 1 (f 2 2 (xσ 1 , xσ 4 )) = (xσ 1 + xσ 4 )+1=1+4+1=6 ::/- t H - σ, t σ ∈ D. 3
公式的值 定义3.19设σ是Nc在解释Ⅰ中的一个指派,如下归纳定义N 的“公式α在I中被a满足” 当a是原子公式F"(t1,t,…,tn)时,α在工中被σ满足当且仅 当F(,杩,……,切成立,即当且仅当<,鸪,…,切>∈Fn 当a为(β)时,a在工中被a满足当且仅当β在工中不被 满足 ·当a为(a1→a2)时,a在工中被a满足当且仅当a1在工中 不被σ满足或者a2在工中被σ满足. ·当a为(Vx)时,a在工中被a满足当且仅当对每个a∈Dx β在工中都能被a(x;/a)满足 记a在I中被0满足为Ia,否则记为I方a.从而 (1)IGF"(t,t,…,tn)当且仅当<切,鸪,…,胡>∈F (2)Ib-B当且仅当I片 (3)Ia1→a当且仅当:若Ia,则rha2 (4)1(x)当且仅当:对任意a∈D,(x;aB (5)IhaB当且仅当Ia或I ()Ia∧B当且仅当Ia而且r (7)Ia当且仅当Ila的充要条件为Il (8)IG(x)当且仅当:存在a∈D,使得I
01 3.19 % σ NL I - CDE NL I α I J σ K2L • F α 34 Fn(t1, t2, ··· , tn) / α I J σ K2FMN F Fn(t σ 1 , tσ 2 , ··· , tσ n) OP (FMNF < tσ 1 , tσ 2 , ··· , tσ n >∈ Fn. • F α (¬ β) / α I J σ K2FMNF β I 3J σ K2 • F α (α1 →α2) / α I J σ K2FMNF α1 I 3J σ K2!5 α2 I J σ K2 •··· • F α (∀xi)β / α I J σ K2FMNF a ∈ DI, β I QRJ σ(xi/a) K2 α I J σ K2 I | σ α, S. I | σ / α . TU (1) I | σ Fn(t1, t2, ··· , tn) FMNF < tσ 1 , tσ 2 , ··· , tσ n >∈ Fn; (2) I | σ ¬ β FMNF I | σ / β; (3) I | σ α1→α2 FMNFV I | σ α1, . I | σ α2; (4) I | σ (∀xi)β FMNF:/ a ∈ D, I | σ(xi/a) β . (5) I | σ α ∨ β FMNF I | σ α ! I | σ β; (6) I | σ α ∧ β FMNF I | σ α UM I | σ β; (7) I | σ α↔β FMNF I | σ α W67X I | σ β; (8) I | σ (∃xi)β FMNFY a ∈ D, Z[ I | σ(xi/a) β 4
例3.21 设C={F2} I=<N,{P},,0>是C的一个解释,其中R={<a,a>a∈N} 1,a2, 为D中元素的序列,满足 1=a2 a是Nc在I中的如下指派:0(x1)=a;(任i∈N) 当a为Kc中下列公式时,Ia成立与否? (1)P2(x1,x2 (3)P2(x1,x2)→F2(x2x3); 1)Vx1F2(x1,x2); 解: (1)IF2(x1,x2)当且仅当<,吗>∈当且仅当<a1,a2>∈R 由于a1=a2,故<a,a2>∈R,从而IhP2(x,m2 (2)IbF(x2,x3)当且仅当<吗,>∈P,当且仅当<a,a3>∈R 由于a2≠a3,故< gR,从而I佑P2(x2,x3) (3)IlF2(ax;x2)→P2(x2,x3)当且仅当rP2(x1,a2)或IlF(x2,m3) 但由(1)(2)知:IP2(x1,x2)→F2(x2,x3) (4)Iax1F2(x1,x2) 当且仅当:任意a∈D,I (x1/a 1,T2 当且仅当:任意a∈D,<x(x1/a)(1/)>∈F2 当且仅当:任意a∈D,<a,a2>∈R 但a3∈D,<a3,02>gR.从而IVx1F(x1,x2)
! 3.21 % L = {F2 }. I =< N, {R}, ∅, ∅ > L R = {< a, a > |a ∈ N}. a1, a2, ··· , an, ··· D K2 a0 = a1 = a2 = a3. σ NL I - σ(xi) = ai (: i ∈ N ). F α KL / I | σ α OP(S\ (1) F2(x1, x2); (2) F2(x2, x3); (3) F2(x1, x2)→F2(x2, x3); (4) ∀x1F2(x1, x2); (5) ∀x1∃x2F(x1, x2) . (1) I | σ F2(x1, x2) FMNF < xσ 1 , xσ 2 >∈ F2 FMNF < a1, a2 >∈ R. 89 a1 = a2, ] < a1, a2 >∈ R, TU I | σ F2(x1, x2). (2) I | σ F2(x2, x3) FMNF < xσ 2 , xσ 3 >∈ F2, FMNF < a2, a3 >∈ R. 89 a2 = a3, ] < a2, a3 >∈ R, TU I | σ / F2(x2, x3). (3) I | σ F2(x1, x2)→F2(x2, x3) FMNF I | σ / F2(x1, x2) ! I | σ F2(x2, x3). ^8 (1)(2) : I | σ / F2(x1, x2)→F2(x2, x3). (4) I | σ ∀x1F2(x1, x2) FMNF:/ a ∈ D, I | σ(x1/a) F2(x1, x2). FMNF:/ a ∈ D, < xσ(x1/a) 1 , x σ(x1/a) 2 >∈ F2. FMNF:/ a ∈ D, < a, a2 >∈ R. ^ a3 ∈ D, < a3, a2 >∈ R. TU I | σ / ∀x1F2(x1, x2). 5