替换定理 引理 设s,x;和t分别是N中的项、个体变元符号和项.s是将S中 所有r;换为t所得的项.σ为Nc在其某个解释Ⅰ中的一个指派, o′=o(x;/).则s=(s) F' g(C 证:对s的复杂性归纳证明:s7=(s) (1)当S为个体变元符号时 (1.1)若S为x,则s为t,从而s=0(x;)=t=(s)° 2)若s为个体变元符号x;(≠i),则。也为x,从而 (1.3)若s为个体变常元符号c则s也为c从而s=2=(s)0 (2)若S是形如門(S1,S2,……,Sm)的项,其中:严m是C的 个m元函数变元符号,S1,82,…,Sm是Nc中项.以S记: 将S;中所有x;换为t得到的项(任j:1≤j≤m).则:s fm(s1,s2…,Sm)由归纳假设知:s=((1≤j≤m,则 s=m(s,s,…,s)=f(s1),(s2),…,(Sn))=(s 归纳证毕,(*)成立UV C WC % s, xi p t ?Æ NL -q$p- s  s  I# xi r t I[- σ  NL  a￾ I  - σ = σ(xi/tσ). . sσ = (s ) σ. sσ : ··· σ (xi) ··· ··· σ (xi) ··· ↓ ↓ s : ( ··· xi ··· ··· xi ··· ) s : ( ··· t ··· ··· t ··· ) ↑ ↑ (s ) σ : ··· t σ ··· ··· t σ ··· E s bFGCDH  sσ = (s ) σ (∗) (1) F s $/ (1.1) V s  xi, . s  t, TU sσ = σ (xi) = t σ = (s ) σ. (1.2) V s $ xj (j = i), . s X xj, TU sσ = σ (xj) = σ(xj)=(s ) σ. (1.3) V s $, c, . s X c, TU sσ = c = (s ) σ. (2) V s L f m(s1, s2, ··· , sm) -  f m L   m *$ s1, s2, ··· , sm NL -" s j   sj I# xi r t [n- (: j : 1 ≤ j ≤ m). . s = f m(s 1, s 2, ··· , s m). 8CD%:sσ j = (s j) σ (1 ≤ j ≤ m), . sσ = f m(sσ 1 , sσ 2 , ··· , sσ m) = f m((s 1) σ , (s 2) σ , ··· , (s m) σ)=(s ) σ. CDHs (∗) OP 11