一阶谓词演算的形式系统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