一阶谓词演算的形式系统KC ·KC是一个较Nc简洁的谓词演算形式系统 ·Kc是在P的基础上建立的 Kc的各组成部分如下: Nc的形式语言 Kc也是相对于某个任意确定的非逻辑符号C集合它而言的 符号库 1.非逻辑符号: C中符号 2.逻辑符号: (21)个体变元符号:x0,x1,x2 (22)量词符号:V (2.3)联结词符号: (24)辅助符号:),,( Kc的公式(与Nc的公式类似) 1.Kc的项归纳定义如下 (1.1)个体变元与个体常元为Kc的项 (1.2)若t1,t,……,tm为Kc的项,門为Kc的一个 m元函数变元符号,则門(t,t2,…,tm)为Kc 的项
jP_FiZIcY`\ KL • KL | /I NL EK Æ { • KL |3 P >uGW KL 0DÆ)r NL HbXqg KL |#+e/p!n! (^?*8 L @;$ *8Q 1. (^?*8 L =*8 2. ^?*8 (2.1) / .*8 x0, x1, x2, ··· . (2.2) Z*8 ∀ . (2.3) XL*8 ¬, → . (2.4) +?*8 ) , , , (. % KL 1{ (, NL 1{S) 1. KL 5f!"r (1.1) / .,/. KL . (1.2) t t1, t2, ··· , tm KL f m KL / m .7~ .*85 f m(t1, t2, ··· , tm) KL 1
2.Kc的公式归纳定义如下: (21)若t1,t2,……,tn为C的项,F"为Kc的一个7 元谓词变元符号,则F"(t1,t2,…,tn)为Kc的 公式 原子公式 22)若a1,a2为Kc的公式,则(=a1),(a1→a2)为 Kc的公式 (2.3)若a为C的公式,x为Kc的个体变元符号,则 (x)a为Kc的一个公式 注:KC的形式语言是Nc的形式语言的一个子语言,因而它们使 用如下相同概念和约定 自由与约束 括号省略规则 P中公式在Kc中的代入实例 简写公式 (aVβ)为(-a)→)的简写; (aA)为((a→(-)的简写; (aB)为(a→)∧(→a)的简写; (x)a为(-(x)(-a))的简写
2. KL 1{5f!"r (2.1) t t1, t2, ··· , tn L Fn KL / n .Æ .*85 Fn(t1, t2, ··· , tn) KL 1{ /A1{ (2.2) t α1, α2 KL 1{5 (¬ α1), (α1 →α2) KL 1{ (2.3) t α L 1{ x KL / .*85 (∀x)α KL /1{ v KL {-| NL {- /A-$$az 'r.i90! • B(,0} • R8w]45 • P =1{3 KL = syV • E1{ (α ∨ β) ((¬ α)→β) E (α ∧ β) (¬ (α → (¬ β))) E (α↔β) ((α→β) ∧ (β→α)) E (∃x)α (¬ ((∀x)(¬ α))) E 2
Kc的形式推理规则 公理 (K1)a→(→a) (K2)(a→(B→)→(a→B)→(a→7) (K3)(a→-B)→(3→a) (K4)Vra→a(x/t),若t对x在a中自由 (K5)a→Wra,若x不在a中自由出现 (K6)x(a→B)→(ra→x6) (K7)若a是Kc的一个公理,则(wx)a也为Kc的一个公理 其中:a,B,为Kc的公式,x为Kc的个体变元符号,t为Kc 的项 2.规则: 分离规则(M):由a及α→可得到 证明序列 定义3.13Kc公式的一个有限序列α1,a2,…,an称为Kc中的 个证明序列(证明),如果每个a;(1≤i≤m)都满足下列条件之 (1)a;是Kc的一个公理;或 (2)a;是由某两个a,ak(1≤j,k<)应用(M)得到的 此时,称an为Kc的一个内定理,记为Kcn,或简写为Fan
KL HbX]QMr 1. 1U (K1) α→(β→α) (K2) (α→(β→γ))→((α→β)→(α→γ)) (K3) (¬ α→¬ β)→(β→α) (K4) ∀xα → α(x/t), t t # x 3 α =B( (K5) α → ∀xα, t x 3 α =B( (K6) ∀x(α→β) → (∀xα→∀xβ) (K7) t α | KL /1U5 (∀x)α KL /1U j= α, β, γ KL 1{x KL / .*8t KL 2. 45 )T45 (M) ( α A α→β P β. sTfS Lk 3.13 KL 1{ /)\ α1, α2, ··· , αn KL = /8c\8cr6`/ αi (1 ≤ i ≤ n) "_C\F: (1) αi | KL /1U = (2) αi |(eY/ αj , αk (1 ≤ j, k < i) &' (M) x αn KL /g!U , C KL αn, =E αn . 3
代如实例 定理35设a为P的一个内定理,Q是a在KC中的一个代入实 例,则}KcQ 定理36(1)若卜Kca→B,且Ka,则:KE (2)若卜Kc(a→3,且卜Kc(3→),则Kc(a→) 此命题中的(1)仍记为(M),(2)仍记为(T) 例3.14 若项t对个体变元符号x在a中自由,则:}a(x/t)→彐ra 证 因为(a)(x/t)=-(a(x/t),从而 Vx(a)→(-a)(x/t) (K4) (x(-a)→-(a(x/t)→(a(x/t)→-Vx(=a) (命题内定理) (x/)→=x( 即:}a(x/t)→彐a
GVWR LQ 3.5 v α P /g!U α | α 3 KL = / sy V5 KL α LQ 3.6 (1) t KL α→β, l KL α, 5 KL β . (2) t KL (α→β), l KL (β→γ), 5 KL (α→γ). d= (1) qC (M), (2) qC (Tr). R 3.14 t t #/ .*8 x 3 α =B(5 α(x/t)→∃xα . s $ (¬ α)(x/t) = ¬ (α(x/t)), $ ∀x(¬ α)→(¬ α)(x/t) (K4) ∀x(¬ α)→ ¬ (α(x/t)) (∀x(¬ α)→ ¬ (α(x/t))) → (α(x/t)→¬∀x(¬ α)) (dg!U) α(x/t)→¬∀x(¬ α) (M) B α(x/t)→ ∃xα 4
定理37 若}Kca,则卜KcV 证:因KcQ,故存在KC中公式序列 为a的一个证明 下对(1≤a≤m)归纳证明:卜 K. vrai (1)当=1时,a1为一个公理,从而vra1也为一个公理,故 (2)设讠<k时,(*)成立,下证=k时(*)也成立 21)若ak仍为公理,仿(1)可证 (22)若ak是由a,a;(1≤l,j<k)用(M)得到的,不妨设 k.则 FK. V ae K (归纳假设) k Vra;。 (归纳假设) KcVx(a1→ak) (归纳假设) KcVr(a→ak)→(ra→rak) (公理K5 C xa1→VQ (定理36) Ke Va (定理36 归纳证毕,(*)成立,从而卜 k. Vran,即 HK Vca
LQ 3.7 t KL α, 5 KL ∀xα. 8$ KL α, 33 KL =1{\ α1, α2, ··· , αn (= α) α /8c # i (1 ≤ i ≤ n) 5f8c KL ∀xαi (∗) (1) i = 1 x α1 /1U$ ∀xα1 /1U3 KL ∀xα1 . (2) v i<k x (∗) W8 i = k x (∗) W (2.1) t αk q 1U' (1) P8 (2.2) t αk |( αl, αj (1 ≤ l, j < k) ' (M) &v αj = αl→αk. 5 KL ∀xαl, (5fDv) KL ∀xαj (5fDv) KL ∀x(αl→αk). (5fDv) KL ∀x(αl→αk) → (∀xαl→∀xαk) (1U K5). KL ∀xαl→∀xαk, (!U 3.6) KL ∀xαk. (!U 3.6) 5f8 (∗) W$ KL ∀xαn, B KL ∀xα. 5
例3,15(1) 若x不在α中自由出现,则: x(a→B)→(a→Wx) 因FP(P→(q→r)→(s→q)→(P→(s→r) 以Ⅴr(α→β),ra,Vx),a分别替换其中的p,q,T,S得: Kc(vx(a→)→(wra→vx/) →(a→ra)→(vx(a→B)→(a→x/) KcVx(a→B)→(ra→vx3) (K5) Kc(a→vxa)→(wr(a→B)→(a→vx) Kca→Vra x不在a中自由出现,(K5) KcVx(→B)→(a→Vx
R 3.15(1) t x 3 α =B(5 ∀x(α→β)→(α→ ∀xβ) s $ P (p→(q→r)) → ((s→q)→(p→(s→r))). ∀x(α→β), ∀xα, ∀xβ, α ) <j= p, q, r, s KL (∀x(α→β)→(∀xα→∀xβ)) → ((α→∀xα)→(∀x(α→β)→(α→∀xβ))). KL ∀x(α→β)→(∀xα→∀xβ), (K5) KL (α→∀xα)→(∀x(α→β)→(α→∀xβ)). KL α→ ∀xα. x 3 α =B( (K5) KL ∀x(α→β)→(α→∀xβ). 6
例315(2) 若x不在α中自由出现,则: (a→Vx))→m(a→3) 因FP(P→q)→(7→p)→(7→q) 分别以x3,β,α代换其中的p,q,T得: Kc(xB→B)→(a→x3)→a→) K VaB→3 Kc(a→x/)→(a→3) K。A→B A记a→x,B记a→ x不在A中自由出现 KcVm(A→B) (定理37) KcVx(A→B)→(A→VrB) KcA→xB Kc(a→Vx6)→Vm(a→B
R 3.15(2) t x 3 α =B(5 (α→ ∀xβ)→∀x(α→β) s $ P (p→q)→((r→p)→(r→q)), ) ∀xβ, β, α <j= p, q, r KL (∀xβ→β) → ((α→∀xβ)→(α→β)). KL ∀xβ→β, KL (α→∀xβ) → (α→β). KL A→B. A C α→∀xβ, B C α→β x 3 A =B( KL ∀x(A→B). (!U 3.7) KL ∀x(A→B) → (A→∀xB). (1) KL A→∀xB, KL (α→∀xβ) → ∀x(α→β) . 7
例3.16 若}a→3,则 1.}Vra→VxB 2.F彐a→x6 题设 (定理37) (3)+x(a→B)→(ra→x)(K6) (4)vxa→x 2.(1)}a→3 (2)+(a→B)→(=3→-a) (命题内定理 (3)=6 (M (4)Vx=B→vx=a (1) (5)+(x-→x=a)→(-Vx-a→-Vx-B) (6)x-a→-x= (M) 即 彐xa→彐x3
R 3.16 t α→β, 5 1. ∀xα→∀xβ 2. ∃xα→∃xβ. s 1. (1) α→β (v) (2) ∀x(α→β) (!U 3.7) (3) ∀x(α→β)→(∀xα→∀xβ) (K6) (4) ∀xα→∀xβ (M) 2. (1) α→β (2) (α→β)→(¬ β→¬ α) (dg!U) (3) ¬ β→¬ α (M) (4) ∀x¬ β→∀x¬ α (1) (5) (∀x¬ β→∀x¬ α)→(¬ ∀x¬ α→¬∀x¬ β) (6) ¬∀x¬ α→¬∀x¬ β (M) B ∃xα → ∃xβ 8
有前提的推演 定义 定义314设r是Kc的一个公式集(不一定有限)Kc中公式的一 个有限序列a1,a2,……,an称为Kc中由前提r推出an的一个证 明,如果每个α;(1≤≤m)满足下列条件之 a;∈T i)a;是一个公理 i)a;是由a;ak(1≤j,k≤用(M)得到 此时,也称在KC中由前提可推出an,记为Kcan或Tan 性质 性质(1)卜Kca的充要条件是:对Kc的任一个公式集,TKca 性质(2)设∑,a分别是P中公式集与公式,∑U{a}的公式中 出现的命题变元符号都在p0,p1,…,pn之中,将∑与a中的 p0,P1,…,pn分别替换为Kc中公式ao,a1,…,an,得到 Kc的公式集∑与a若∑hPa,则∑HKca 性质(3)若∑卜Ka,∑hKca→,则∑hKc月 性质(4)若∑卜Kca→,∑hKc→7,则∑hKcq→y 性质(5)若∑卜Ka,而x是一个不在∑的任何公式中自由出现的 个个体变元符号,则∑卜KcVa
nU[I^i Lk Lk 3.14 v Γ | KL /1{@ ( !)). KL =1{ /)\ α1, α2, ··· , αn KL =(k Γ αn /8 c , r6`/ αi (1 ≤ i ≤ n) _C\F: (i) αi ∈ Γ . (ii) αi | /1U (iii) αi |( αj, αk (1 ≤ j, k ≤ i) ' (M) x 3 KL =(k Γ P αn , C Γ KL αn = Γ αn. dt dt (1) KL α F|# KL p /1{@ Γ, Γ KL α. dt (2) v Σ, α ) | P =1{@,1{ Σ ∪ {α} 1{= d .*8"3 p0, p1, ··· , pn :=H Σ , α = p0, p1, ··· , pn ) < KL =1{ α0, α1, ··· , αn, KL 1{@ Σ , α . t Σ P α, 5 Σ KL α . dt (3) t Σ KL α, Σ KL α→β, 5 Σ KL β . dt (4) t Σ KL α→β, Σ KL β→γ, 5 Σ KL α→γ . dt (5) t Σ KL α, $ x | / 3 Σ p:1{=B( // .*85 Σ KL ∀xα . 9
性质(5)的证明 因∑HKca,则存在Kc中公式序列 为在前题∑下推出α的一个证明 下对i(1≤a≤m)归纳证明:∑ k Vaai (1)当讠=1时,a1为一个公理或a1∈∑ (1.1)若a1为一个公理,则vra1也为一个公理,故 k. Vaa1, 从而∑} k Vco1 (1.2)若a1∈∑,则x不在a1中自由出现,由(K5)知:卜Kc 1→Vra1,从而∑K1→a1.又∑Kca1,故:∑Kcma1 (2)设讠<k时,(*)成立,下证=k时(*)也成立 (21)若ak仍为公理或ak∈∑,仿(1)可证 22)若ak是由α,a;(1≤l,j<k)用(M)得到的,不妨 设a=→0k.由归纳假设得:∑ kr vaa,∑ Kc Vraj,即: ∑ HK Vo(a→ak).又由于hKcr(at→ak)→(wa→rak) 公理K5.故:∑KcVx(a1→ak)→(ra→rak)由性质(2) 知:∑} K. Vacar→rak,∑ FK. VIa 归纳证毕,(*)成立,从而∑ k. Vrar2,即:∑ k Vca 注:上面的证明只是对定理3.7的证明作了不大的修改
dt (5) HsT s $ Σ KL α, 53 KL =1{\ α1, α2, ··· , αn (= α) 3k Σ α /8c # i (1 ≤ i ≤ n) 5f8c Σ KL ∀xαi (∗) (1) i = 1 x α1 /1U= α1 ∈ Σ. (1.1) t α1 /1U5 ∀xα1 /1U3 KL ∀xα1, $ Σ KL ∀xα1. (1.2) t α1 ∈ Σ, 5 x 3 α1 =B(( (K5) 9 KL α1→∀xα1, $ Σ KL α1→∀xα1. * Σ KL α1, 3Σ KL ∀xα1. (2) v i<k x (∗) W8 i = k x (∗) W (2.1) t αk q 1U= αk ∈ Σ, ' (1) P8 (2.2) t αk |( αl, αj (1 ≤ l, j < k) ' (M) & v αj = αl→αk. (5fDv Σ KL ∀xαl, Σ KL ∀xαj, B Σ KL ∀x(αl → αk). *(+ KL ∀x(αl → αk) → (∀xαl → ∀xαk) (1U K5). 3 Σ KL ∀x(αl→αk) → (∀xαl→ ∀xαk) (< (2) 9 Σ KL ∀xαl→∀xαk, Σ KL ∀xαk. 5f8 (∗) W$ Σ KL ∀xαn, B Σ KL ∀xα. vub 8c;|#!U 3.7 8cE[ - 10