解释和赋值 解释是对每个符号说明其含义.赋值是指岀每个公式的真假值 将非逻辑符号集￡记为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={|n∈N} f为N上的后继函数,即 f1:N→N,f1(m)=m+1(任n∈N) f为N上的加法函数,即 f:N2→N,f()=m+m(任m,n∈N) f3为N上的乘法函数,即 f3:N2→N,()=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} f 1 1 N &89* ( f 1 1 : N → N, f 1 1 (n) = n +1 (: n ∈ N) f 2 2 N &;) = m + n (: m, n ∈ N) f 2 3 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 ∈ 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 ∈ 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=是C的一个解释,其中R={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)当且仅当∈当且仅当∈R 由于a1=a2,故∈R,从而IhP2(x,m2 (2)IbF(x2,x3)当且仅当∈P,当且仅当∈R 由于a2≠a3,故∈F2 当且仅当:任意a∈D,∈R 但a3∈D,gR.从而IVx1F(x1,x2)
! 3.21 % L = {F2 }. I = L R = { |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 ∈ F2 FMNF ∈ R. 89 a1 = a2, ] ∈ R, TU I | σ F2(x1, x2). (2) I | σ F2(x2, x3) FMNF ∈ F2, FMNF ∈ R. 89 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, ∈ F2. FMNF:/ a ∈ D, ∈ R. ^ a3 ∈ D, ∈ R. TU I | σ / ∀x1F2(x1, x2). 5
(5)IhWm132F2(x,x2) 当且仅当:任意a∈D,Iba3n2FP(x1,2) 当且仅当:任意a∈D,存在b∈D,使得 I o(aia(] F(x1, 22) 当且仅当:任意a∈D,存在b∈D,使得:∈R 最后一个条件是成立的,因为只要取b=a即可 故Ih132F 例3.22 C与11如例320,σ为C在1中的任一个指派.问在I1中是否 满足下面的公式B vx1Vx2(x3P2(f3(x1,x23),x2)Ax4F2(f3(x2,x4),x1)→F2(x1,x2) 答:1B 对任意m1∈N (x1/1) (3x3F2(3(x1,x3),x2) ∧彐x4F2(f3(x2,x4),x1)→F2(x1,x2) 对任意的m1∈N,m∈N, (x1/1 m72 (彐x3F2(3(x,x3),x2)x4F2(3(x2,x4),x1)→F2(x1,x2 对任意m1,m2∈N 若11 T(x1/m1)(x2/m2 彐x3F2(f(x1,x3),x2)∧彐x4F2(3(x2,x4),x1), 则I1 0(x1/m1)(x2/m2)
(5) I | σ ∀x1∃x2F2 (x1, x2) FMNF:/ a ∈ D, I | σ(x1/a) ∃x2F2(x1, x2). FMNF:/ a ∈ D, Y b ∈ D, Z[ I | σ(x1/a)(x2/b) F2(x1, x2). FMNF:/ a ∈ D, Y b ∈ D, Z[ ∈ R. ;87XOP σ I1 S K2` β: ∀x1∀x2((∃x3F2(f 2 3 (x1, x3), x2) ∧ ∃x4F2(f 2 3 (x2, x4), x1)) → F2(x1, x2)) ?I1 | σ β ⇔ :/ m1 ∈ N , I1 | σ(x1/m1) ∀x2((∃x3F2(f 2 3 (x1, x3), x2) ∧ ∃x4F2(f 2 3 (x2, x4), x1)) → F2(x1, x2)). ⇔ :/ m1 ∈ N , m2 ∈ N , I1 | σ(x1/m1)(x2/m2) (∃x3F2(f 2 3 (x1, x3), x2)∧∃x4F2 (f 2 3 (x2, x4), x1)) → F2 (x1, x2). ⇔ :/ m1, m2 ∈ N , V I1 | σ(x1/m1)(x2/m2) ∃x3F2(f 2 3 (x1, x3), x2) ∧ ∃x4F2 (f 2 3 (x2, x4), x1), . I1 | σ(x1/m1)(x2/m2) F2 (x1, x2). 6
分对任意m1,m∈N, 若Iosm/(ym3xF2(∫m2,2 且I1 (1/m1)(x2/m2 x4F2(3(x2,x4),x1) 则h1hn (x1/m1)(x2/m2 F2(x1,2) 分对任意m1,m2∈N, 若存在m3∈N使得 1 (x1/m1)(x2/m2)(x3/m F2(3(x1,x3,x2) 且存在m4∈N使得 11 (x1/m1)(x2/m2)(x4/m4) mF2(3(x2,x小,x1 则11 σ(x1/m1x2/m2 台对任意m1,m2∈N, 若存在m3∈N使得m1·m3=m2 且存在m4∈N使得m2·m4=m 则m1 台对任意m,m2∈N,若m1|m2,且m2m1,则m1=m2 从而h6 类似地,对C在I2如的任一个指派O 1份B分对任意m1,m2∈Q, 若存在m3∈Q使得m1·m3=m2 且存在m4∈Q使得m2·m4=m1, 71 m72 从而3
⇔ :/ m1, m2 ∈ N , V I1 | σ(x1/m1)(x2/m2) ∃x3F2(f 2 3 (x1, x3), x2), M I1 | σ(x1/m1)(x2/m2) ∃x4F2(f 2 3 (x2, x4), x1), . I1 | σ(x1/m1)(x2/m2) F2(x1, x2). ⇔ :/ m1, m2 ∈ N , VY m3 ∈ N Z[ I1 | σ(x1/m1)(x2/m2)(x3/m3) F2(f 2 3 (x1, x3), x2), MY m4 ∈ N Z[ I1 | σ(x1/m1)(x2/m2)(x4/m4) F2(f 2 3 (x2, x4), x1), . I1 | σ(x1/m1)(x2/m2) F2 (x1, x2). ⇔ :/ m1, m2 ∈ N , VY m3 ∈ N Z[ m1 · m3 = m2, MY m4 ∈ N Z[ m2 · m4 = m1, . m1 = m2. ⇔ :/ m1, m2 ∈ N , V m1|m2, M m2|m1, . m1 = m2. TU I1 | σ β . @AB, L I2 : - σ, I2 | σ β ⇔ :/ m1, m2 ∈ Q, VY m3 ∈ Q Z[ m1 · m3 = m2, MY m4 ∈ Q Z[ m2 · m4 = m1, . m1 = m2. TU I2 | σ / β 7
定理313 设σ1,σ2是Nc在其某个解释Ⅰ中的两个指派,t(v1,℃,…,tn) 是Nc的一个项,其中:,v,…,tn是Nc的个体变元符号, t(v1,℃2,…,tn)中出现的个体变元符号都在1,t2,…,Cn中, 若对任意i:1≤i≤n,01(t;)=02(v),则t1=t2 证:对t的复杂性归纳证明,即对t中所含的函数变元符号的个数d 进行归纳证明. (1)当d=0时,t为个体变元符号或个体常元符号 (1.1)若t为个体变元符号,则t必为1,t2,…,tn中的某 个,不妨设t=v(某i:1≤≤m,则 01(v)=02(v7) (1.2)若t为个体变元符号c时,则:切=c1=2=c2=t2 (2)假设d0) 设t中含有l个函数变元符号,t=尸"(t1,t2,……,tm),其 中:m是C中的一个m元函数变元符号,t1,t2,…,tm是Nc 的项,由归纳假设得:=t,切2=t2,…,切=tm,从而 归纳证完,命题成立 定理313说明:项t(U1,2,……,Un)在指派a下的值t只与 σ对t中出现的个体变元符号1,v2 U指派的值有关,与σ 对其它个体变元符号指派的值无关
C 3.13 % σ1, σ2 NL a I 5 - t(v1, v2, ··· , vn) NL - v1, v2, ··· , vn NL $ t(v1, v2, ··· , vn) D$Q v1, v2, ··· , vn V:/ i : 1 ≤ i ≤ n, σ1(vi) = σ2(vi), . t σ1 = t σ2. E t bFGCDH ( t I *$ d cJCDH (1) F d = 0 / t $!, (1.1) V t $ . t d v1, v2, ··· , vn a 3e% t = vi (a i : 1 ≤ i ≤ n), . t σ1 = v σ1 i = σ1(vi) = σ2(vi) = v σ2 i = t σ2 (1.2) V t $ c / . t σ1 = cσ1 = c = cσ2 = t σ2. (2) % d 0). % t # l *$ t = f m(t1, t2, ··· , tm), f m L m *$ t1, t2, ··· , tm NL - 8CD%[ t σ1 1 = t σ2 1 , t σ1 2 = t σ2 2 , ···, t σ1 m = t σ2 m , TU t σ1 = f m(t σ1 1 , tσ1 2 , ··· , tσ1 m ) = f m(t σ2 1 , tσ2 2 , ··· , tσ2 m ) = t σ2. CDHM fKOP E> 3.13 - t(v1, v2, ··· , vn) - σ t σ =( σ t D$ v1, v2, ··· , vn -#' ( σ N$ -O' 8
定理3.14 设σ1,σ2是Nc在其某个解释Ⅰ中的两个指派,a(t1,v2,…,tn) 是Nc的一个公式,其中:U1,v2,…,tn是Nc的个体变元符号, a(v,v2,…,tn)的自由变元符号都在t1,t,…,℃n中,若对任 意i:1≤i≤n,1(v)=02(v),则Ima当且仅当Iha 证:对公式a中所含的联结词与量词的个数d进行归纳证明. (1)当d=0时,a为原子公式,设a为F(t1,t2,…,tn), 其中:F为C的一个n元谓词变元符号,t,t2,…,tn是Nc 的项.由于a中没有量词,则在t;中出现的每个个体变元符号都是 a的自由变元(1≤≤m),从而在t;中出现的每个个体变元符号在 σ1与σ2下的指派的值相等,由定理3.13知:对任意讠:1≤≤n =增.从而Ia当且仅当rP"(t,t,……,t) 当且仅当∈F 当且仅当∈F 当且仅当ⅠF(t1,t2,…,tn 当且仅当I=a (2)假设命题对所有满足d<l的d成立,考察d=l时情形 (≥1) (21)当a为(③)时,由归纳假设知:aB当且仅当I6 从而Ia当且仅当B当且仅当B 当且仅当1B当且仅当I-B 当且仅当I
C 3.14 % σ1, σ2 NL a I 5 - α(v1, v2, ··· , vn) NL v1, v2, ··· , vn NL $ α(v1, v2, ··· , vn) $8$Q v1, v2, ··· , vn V: / i : 1 ≤ i ≤ n, σ1(vi) = σ2(vi), . I | σ1 α FMNF I | σ2 α E α I jk#(l# d cJCDH (1) F d = 0 / α 34 % α Fn(t1, t2, ··· , tn), Fn L n #$ t1, t2, ··· , tn NL - 89 α m#l# . ti D$Q α $8$ (1 ≤ i ≤ n), TU ti D$ σ1 ( σ2 -%7 8E> 3.13 ::/ i : 1 ≤ i ≤ n, t σ1 i = t σ2 i . TU I | σ1 α FMNF I | σ1 Fn(t1, t2, ··· , tn), FMNF ∈ Fn , FMNF ∈ Fn , FMNF I | σ2 Fn(t1, t2, ··· , tn), FMNF I | σ2 ‘ α. (2) %fKI#K2 d<l d OP gh d = l /iL (l ≥ 1). (2.1) F α (¬ β) / 8CD%:I | σ1 β FMNF I | σ2 β. TU I | σ1 α FMNF I | σ1 ¬ β FMNF I | σ1 / β FMNF I | σ2 / β FMNF I | σ2 ¬ β FMNF I | σ2 α. 9
22)当a为(a1→a2)时,由归纳假设知: 1ma1当且仅当Ⅰ同Q1 Ia2当且仅当Ⅰha2 从而Ia当且仅当1ba1→02 当且仅当Iha1或I 当且仅当Ⅰ房a1或Ⅰ后a2 当且仅当Iha1→a2 当且仅当I=a (2.3)当a为(Vo)时,其中v为C的一个个体变元符号.由 于a的自由变元符号都在v1,U2,…,vn中,故β的自由变元符号 都在v,U1,℃2,…,n中 注意到:a1(o/a)(v)=02(v0/a)(v)(对任意的i:0≤i≤m) 由归纳假设得:1n0B当且仅当12(1B 从而Ia当且仅当rby0 当且仅当:对任意a∈D,I 1(0/a 当且仅当:对任意a∈D,r O2(0/a 当且仅当Ih=V06 当且仅当Ia 归纳证完,命题成立 定理314是说:对公式a(,t2,…,n)来说,“Ia”成 立与否只与σ对α的自由变元U1,2,……,tn指派的值有关,与σ 对其它个体变元符号指派的值无关
(2.2) F α (α1→α2) / 8CD%: I | σ1 α1 FMNF I | σ2 α1, I | σ1 α2 FMNF I | σ2 α2. TU I | σ1 α FMNF I | σ1 α1→α2 FMNF I | σ1 / α1 ! I | σ1 α2 FMNF I | σ2 / α1 ! I | σ2 α2 FMNF I | σ2 α1→α2 FMNF I | σ2 α. (2.3) F α (∀v0)β / v0 L $ 8 9 α $8$Q v1, v2, ··· , vn ] β $8$ Q v0, v1, v2, ··· , vn P/nσ1(v0/a)(vi) = σ2(v0/a)(vi) (:/ i : 0 ≤ i ≤ n). 8CD%[ I | σ1(v0/a) β FMNF I | σ2(v0/a) β, TU I | σ1 α FMNF I | σ1 ∀v0β. FMNF:/ a ∈ D, I | σ1(v0/a) β. FMNF:/ a ∈ D, I | σ2(v0/a) β. FMNF I | σ2 ∀v0β. FMNF I | σ2 α. CDHM fKOP E> 3.14 α(v1, v2, ··· , vn) o “ I | σ α ” O P(S=( σ α QRST v1, v2, ··· , vn -#' ( σ N$ -O' 10