N的定理也是Ne的的定理 定理1 设∑与a分别为N中有限公式集与公式,在∑∪{a}的 公式中出现的命题变元符号都在p0,p1, a0,a1,…,am为的公式,以ao,a1,……,an 同时分别替换∑∪{a}的公式中的o,p1,…,Pn, 得到中的公式集∑与公式a 若∑Na,则∑hNa 10
N NL 1 Σ α N , Σ∪{α} p0, p1, · · · , pn , α0, α1, · · · , αn L , α0, α1, · · · , αn Σ ∪ {α} p0, p1, · · · , pn, L Σ0 α0 ❇ Σ `N α, Σ0 `NL α0. 10
定理1的证明 证:因∑卜Na,故存在N中证明序列 ∑1F61,∑2B2, k+k(=∑Fa) 设∑1U…·U∑kU{月1,B2,…,Bk}的公式中出现的 任选定中的m个公式m+1,,n+m, 命题变元符号都在p0,…,Pn,pn+1, ∑1,∑ 2, k,1,2, Bk 的公式中出现的p0,…,Pn,pn+1,…,n2+m同时 分别替换为a0, m2,m+1 an+m得到 x1,∑2,…,∑k,%,B2,…
1 : Σ `N α, N : Σ1 ` β1, Σ2 ` β2, · · · , Σk ` βk (= Σ ` α) Σ1∪· · ·∪Σk∪{β1, β2, · · · , βk} p0, · · · , pn, pn+1, · · · , pn+m . L m αn+1, · · · , αn+m, Σ1, Σ2, · · · , Σk, β1, β2, · · · , βk p0, · · · , pn, pn+1, · · · , pn+m α0, · · · , αn, αn+1, · · · , αn+m Σ01, Σ02, · · · , Σ0k, β01, β02, · · · , β0k. 11
定理1的证明(续) 1,∑2+%2,…,∑k HK 为Na中的一个证明. (因为N的形式规则在写法上同Nc的形式规则相同 也可归纳法进行严格证明) 又xA=2,B=Q,故∑hNga
1 ( ) Σ01 ` β01, Σ02 ` β02, · · · , Σ0k ` β0K NL ✓ . ( N NL . .) Σ0k = Σ0, β0k = α0, Σ0 `NL α0. 12
一个推论 定理2对于c的有限公式集「与公式a1,a2,…,Om 1.若「hNna1,a2, 且a1,Q2,…, an Fno a, Urn. a 2.若a1→a2卜N,a3→4, 且a1卜Na2 Ja3 FNo a4 其证明和命题情形一样
❈ 2 L Γ α1, α2, · · · , αn. 1. Γ `NL α1, α2, · · · , αn, α1, α2, · · · , αn `NL α, Γ `NL α. 2. α1→α2 `NL α3→α4, α1 `NL α2, α3 `NL α4. ✓ ✥ 13
例6 在NG中写出下列公式的证明序列 1.Wa(a→)Ha→xc6,若x不在a中自由出现 2.x(a→)H3a→,若x不在中自由出现 3.Va(a→6)Fa→3x), 4.(a→6)a→Va6
6 NL : 1. ∀x(α→β) `a α→∀xβ, x α ✕✖. 2. ∀x(α→β) `a ∃xα→β, x β ✕✖. 3. ∀x(α→β) ` ∃xα→∃xβ, 4. ∀x(α→β) ` ∀xα→∀xβ, 14