2 1 1
2 2 2 : (1) : A 0, A 1, A 2, (2) : (3) : (, ) : 1. 2. 3. 4. 5.?? ( A 1 ) ((A 1 2.1. 2
2 2 : (a) A i (b) α β ( α) (α β) (α β) (α β) (α β) (c) 1. α β 2. A 0, A 1, A 2, A B P Q (a) (b) (c) (b) X X α β ( α) (α β) X { } = {X : A i X X } (c) α ( A 1 ) (A 1 A 2 ) (( A 1 ) A 2 ) (φ 0, φ 1,..., φ n ) α φ n α i n φ i j, k < i φ i ( φ j ) (φ j φ k ) α α 3
3 2 2.1 ( ). P (α) (1) A i, P (A i ) ; (2) α β, P (α) P (β) P (( α)) P ((α β)) P (α) α 2.1. : P (α) α P (α) A i, P (A i ) P (α) P (β) α β ( α) (α β) P (( α)) P ((α β)) P (α) 3 {T, F } T F {1, 0} S S v S v : S {T, F } S S f : { } { } f (α) = ( α) f : { } { } 4
2 3 f (α, β) = (α β) S S?? v S v (0) A S v(a) = v(a) v : S {T, F } (1) (2) (3) (4) (5) v((α β)) = v((α β)) = v((α β)) = v(( α)) = { { { v((α β)) = { T, v(α) = F ; F, T, v(α) = T v(β) = T ; F, T, v(α) = T v(β) = T ; F, F, v(α) = T v(β) = F ; T, { T, v(α) = v(β); F, v α β ( α) (α β) (α β) (α β) (α β) T T F T T T T T F F F T F F F T T F T T F F F T F F T T v v v A 3 A 4 5
3 2 (A B) B A B T 1 A B F T 2 B F F F T F F T α β (α β) T T T T F F F T X F F Y X Y X = Y = T X = T Y = F A B A X = F Y = T A B X = Y = F A B 2.1. α (((B (A C)) ((B A) C))) v(a) = v(b) = T v(c) = F v(α) v(α) = T 6
2 3 v v n! 0! = 1 n, (n + 1)! = (n + 1) n! 1 f n f 0 = f 1 = 1 n, f n+2 = f n + f n+1 2.2. S v v : S {T, F } (0) (5) 2.2 v φ v(φ) = T 2.2. Σ τ Σ = τ Σ τ Σ = τ τ Σ Σ = τ v [ σ Σ v(σ) = T v(τ) = T ] 2.2. (1) {(α β)} = α (2) {A, ( A)} B τ = τ = τ v v Σ = {σ} {σ} = τ σ = τ σ = τ τ = σ σ τ (1) 1 Fibonacci 1170-1250 ((A (B C)) ((A B) C)) ((A (B C)) ((A B) C)) 7
4 2 (2) ((A B) (B A)) ((A B) (B A)) (3) ((A (B C)) ((A B) (A C))) ((A (B C)) ((A B) (A C))) (4) (( ( A)) A) (5) 2 (( (A B)) (( A) ( B))) (( (A B)) (( A) ( B))) (6) (A ( A)) ( (A ( A))) ((A B) (( B) ( A))) 4 A B C A B C A B B C 2.3 ( ). α 2 Augustus De Morgan 1806-1871 8
2 5 (1) α (2) α ( α 0 ) α 0 (3) α (α 1 α 2 ) α 1 α 2 (2) (3) α 0 α 1 α 2 : P (α) (1) (2) (3) α P (α) (1) (2) (3) (1) (2) (3) α (2) (3) (2) (3) (3) (2) α = (α 1 1 α 2 ) = (β 1 2 β 2 ) = α 1 1 α 2 ) = β 1 2 β 2 ) 2.1 α 1 = β 1 α 1 β 1 1 α 2 ) = 2 β 2 ) 1 = 2 α 2 = β 2 (1) (2) A B (( A) B)) (3) α β γ ((α (β γ)) 5 9
5 2 {T, F } k {T, F } B k- α A 1, A 2,, A n α n- B n α B n α(x 1,..., X n ) = A 1,, A n X 1,, X n α α n- n- B n α 0-0- α β ( α) (α β) (A ) v v( ) = T v( ) = F 2.3. 0-2.4. 16 0-1- A A B B A B 3 (A B) A B 4 (A B) A < B A > B A + B F, T 0, 1 1 + 1 = 0 n- 2.5. M(A, B, C) = A, B, C M(T, F, T ) = T M(F, F, T ) = F M (A B C) ( A B C) (A B C) (A B C) 2.4. n- G n 1 α α G G = B n α 3 Charles Sanders Peirce 1839-1914 4 Henry M. Sheffer 1882-1964 10
2 5 : 1 G {F } G F α = (A A) 2 1 G k n- T k T k 1 X 1 = (X 11, X 12,..., X 1n ), X 2 = (X 21, X 22,..., X 2n ),.. X k = (X k1, X k2,..., X kn ) A j, X ij = T ; β ij = A j, γ i = β i1 β i2 β in, α = γ 1 γ 2 γ k G = B n α 1 i k B n α(x i ) = T = G(X i ) {A 1, A 2,, A n } X i γ i Y X i γ i α B n α(y ) = F = G(Y ) α α = γ 1 γ 2 γ k γ i = β i1 β i2 β ini β ij 2.1. φ C C {,, } 2.2. {, } {, } : 2.6. {, } 11
6 2 C C,,, C C C C A C A B A f(a, B) A f(a, A) A : α α T α T α A α A A = α 6 Λ Γ Γ Γ Γ Λ φ Γ Γ φ 12
2 6 L α β α β α β (α β) α β (α β) (β α) L Λ (A1) α (β α) (A2) (α (β γ)) ((α β) (α γ)) (A3) ( β α) (( β α) β) α β γ L 5 α α β β 2.3. Γ φ α n = φ i n (a) α i Γ Λ (α 0, α 1,, α n ), (b) j, k < i, α i α j α k α k = α j α i φ Γ Γ φ Γ φ 1. Γ Γ α α 2. Γ α Γ Γ 0 Γ 0 α 2.2. α α α : 1. (α (α α) α) (α (α α)) (α α) 2. α (α α) α 3. (α (α α)) (α α) 4. α (α α) 5. α α 5 modus ponens MP 13
7 2 2.5 ( ). Γ α β Γ {α} β Γ α β {α} β α β : (β 1, β 2, β n ) Γ {α} β β n = β i 1 i n Γ α β i i = 1 β 1 Γ α β 1 (α β 1 ) (A1) Γ α β 1 2.2 k < i Γ α β k β i Γ α β i β j β l = β j β i (j, l < i) i = 1 1 i Γ α β j Γ α (β j β i ) (α (β j β i )) (α β j ) (α β i ) (A2) Γ α β i 2.3. 1. {α β, β γ} α γ 2. {α (β γ), β} α γ 7 6 6 [?] 6 William W. Tait 1929-14
2 7 (1) A 0, Ā0, A 1, Ā1, i A i Āi (2) (3) ( ) α A A = Ā Ā = A (α β) = α β (α β) = α β α β α β Γ = {α 1, α 2,, α n } α 1 α 2 α n Γ, α Γ {α} Γ Γ, A i, Āi ( ): Γ, α i Γ, (α 0 α 1 ) i = 0, 1 ( ): : Γ, α 0 Γ, α 1 Γ, (α 0 α 1 ) Γ, α Γ, α Γ Γ Γ Γ Γ Γ Γ 2.7. Γ α Γ, α, α : Γ α α A i α Āi Γ, α, α α Āi 15
7 2 α α 0 α 1 α α 0 α 1 i = 0, 1 Γ, α i, α i D i α α 0 α 1 2.8. D 0. Γ, α 0, α 0 Γ, α 0 α 1, α 0 D 1. Γ, α 1, α 1 Γ, α 0 α 1, α 1 Γ, α 0 α 1, α 0 α 1 Γ, α 0, α 1 Γ, α 0 α 1 : ( ) Γ, α 0, α 1 Γ, α 0, α 0 α 1 Γ, α 0 α 1, α 0 α 1 Γ, α 0 α 1, α 0 α 1 Γ, α 0 α 1 Γ {α 0 α 1 } {a, b, c} {a, b}, c {a}, b, c Γ = {α 1, α 2,, α n } α 1 α 2 α n 2.9. {a, b, c} {a, b}, c (rw) ((α β) (β γ)) (α γ) : p q p q ((α β) (β γ)) ( α γ) {γ, β}, α, α {γ, β, α}, α (rw) { α, γ}, β, β {γ, β, α}, β (rw) ( ) {γ, α, β}, α β {γ, α, α β}, β (rw) { α, α β}, γ, γ {γ, α, α β}, γ (rw) ( ) {γ, α, α β}, β γ (α β), (β γ), α, γ (rw) ((α β) (β γ)), ( α γ) ( ) ((α β) (β γ)) ( α γ) ( ) 16
2 8 8 2.6 ( ). Σ τ Σ τ Σ = τ τ = τ L : (A1) (A2) (A3) Σ τ Σ τ (β 1, β 2, β n ) β n = τ v Σ i 1 i n v β i v β k (k < i) v β i β i β i Σ v v β i β i β j β k = β j β i j, k < i v β j β k v β i v β n v τ 2.7 ( ). Σ = τ Σ τ. 2.4. Σ α Σ α Σ α Σ 2.3. Σ β Σ β 17
8 2 :?? 2.4. Σ τ Σ { τ} : ( ) Σ τ τ Σ { τ} τ Σ { τ} τ Σ { τ} ( ) Σ { τ} 2.3 Σ { τ} τ Σ τ τ (A3) ( τ τ) ( τ τ) τ Σ τ 2.5. Σ Σ Σ Σ 2.5. : (a) Σ Σ (b) Σ = τ Σ τ : (a) (b) (a) Σ = τ Σ τ Σ τ 2.4 Σ { τ} (a) v v( τ) = T v(τ) = T Σ = τ v Σ (b) (a) (b) Σ Σ Σ τ Σ = τ (b) τ Σ τ Σ (a) α, {α} 2.6 ( 7 ). Σ : α 1, α 2, { n } n N 0 = Σ, n {α n+1 }, n+1 = n { α n+1 }, n {α n+1 } ; n {α n+1 } 7 Adolf Lindenbaum 1904-1941 18
2 8 n n ( ) n N n Σ ( ) α α α 2.7. v v(a) = T A v : α v(α) = T α?? 2.7 = α α (A1) (A2) (A3) (1) Γ α β Γ β α α β α (2) α (α β)?? (3) Σ α Σ β Σ (α β)?? 2.8. α A 1,, A k v A 1,, A k A i A i v v(a i ) = T A i A i A i α v α v(α) = T α α α {A 1,, A k} α : P (α) P (α) α {A 1,, A k } Σ v v A i P (A i ) P (α) β = α P (β) v 1 v(β) = T v(α) = F α α Σ α Σ β β = β = α = α 19
8 2 2 v(β) = F v(α) = T α α Σ α α α Σ β β = α P (α) P (β) γ = α β P (γ) v 1 v(α) = F v(γ) = T Σ α α α (2) Σ α β Σ γ 2 v(β) = T v(γ) = T Σ β β β (1) Σ α β Σ γ 3 v(α) = T v(β) = F v(γ) = F Σ α Σ β (3) Σ (α β) Σ γ 2.8 ( ). = α α L : α A 1, A 2,, A k α 2.8 {A 1, A 2,, A k } α α α α {A 1, A 2,, A k 1, A k} α {A 1, A 2,, A k 1, A k} α {A 1, A 2,, A k 1 } A k α {A 1, A 2,, A k 1 } A k α?? (A k α) ( A k α) α {A 1, A 2,, A k 1 } α α 2.9 ( ). Σ Σ : Σ Σ Σ Σ Σ A A Σ Σ 0 Σ 0 A A Σ 0 = A A Σ 0 20
2 8 2.10. M M R M x y xry x = y yrx : M S {p ab : a, b M} M S Γ Γ = { p aa : a M} {p ab p bc p ac : a, b, c M} {p ab p ba : a, b M, a b} Γ Γ Γ M L L L α L α α P NP http://www.claymath.org/millennium/p_vs_np/ 21
9 2 9 8 1959 9 19 2, α ( α) p q (( p) ( q)) α α = α, (1) (2) K 8 Clarence Irving Lewis 1883-1964 9 Saul Kripke 1940-22
2 9 2.6. (a) F = (W, R) W R W (b) W V (c) M = (F, V ) M M = (W, R, V ) W xry x y y x A V A V (A) A A, B, C V A, B, C 2.7. α M w (M, w) = α (1) A i (M, w) = A i w V (A i ) (2) (M, w) = ( β) (M, w) = β (M, w) = β (3) (M, w) = (β γ) (M, w) = β (M, w) = γ (4) (M, w) = ( β) w W Rww (M, w ) = β (M, w) = α α M w 2.8. α M = (W, R, V ) M = α w W (M, w) = α 2.11. F = (W, R) W = {u, v, w} R = {(u, v), (u, w)} v w u 2.1: F = (W, R) V : {A, B} P(W ) V (A) = {u, v} V (B) = {v} A u, v B v (M, u) = (A B) (M, u) = A B 23
9 2 2.9. α = α M M = α 2.12. = (α β) ( α β) : M = (W, R, V ) w W (M, w) = (α β) ( α β) (M, w) = (α β) 2.7 3 (M, w) = (α β) (M, w) = α β (M, w) = (α β) (M, w) = α (M, w) = β 2.7 4 Rww w (M, w ) = α β (M, w ) = α (M, w ) = β (M, w) = β K 6 (A1) (A2) (A3) K : (α β) ( α β) K (A1) (A2) (A3) α, β, γ RN 10 α α α K K α Γ K α 2.13. K (α β) ( α β) : (A1) (A2) {α β, α} K β 1. α β 2. (α β) 3. (α β) ( α β) 4. α β 10 Rule of Necessitation 24
2 9 5. α 6. β K L K ( α) β 1, β 2, B i β i B i A 3 (A 1 A 2 ) B 5 B 29 A 3 ( A 3 ) (A 1 A 2 ) B 5 B 5 B 29 B i 2.9. α K α : α α α B i β i 2.10. {α : α Γ} K β Γ K β : Γ K- Γ K- α α Γ α Γ K- Γ K Γ K α α Γ K K- K- 2.10. Γ K- β Γ {α : α Γ} K-, β : β Γ Σ = {α : α Γ} Σ β Σ Σ K- β β Γ Σ = {α : α Γ} Σ K β Σ K β Σ { β} K- Σ { β} K- β K- 2.10 Γ K β K- Γ K β Γ 25
9 2 K 2.11 ( K ). K α α : 2.12 ( K ). = α K α K α M w (M, w) = α M = (W, R, V ) α K α w W (M, w) = α 2.10. K M = (W, R, V ) W = {Γ : Γ K- } (Γ, Γ ) R {α : α Γ} Γ V (A i ) = {Γ W : A i Γ} 2.11. M = (W, R, V ) K α Γ W (M, Γ) = α α Γ : α α A i 2.7 (M, Γ) = A i Γ V (A i ) V Γ V (A i ) A i Γ 1 α β 2.7 (M, Γ) = β (M, Γ) = β β Γ K- 2 α β γ 3 α β (M, Γ) = β 2.7 W (Γ, ) R (M, ) = β β β (Γ, ) R R W {α : α Γ} β 2.10 β Γ β Γ 2.10 R W (Γ, ) R β (M, ) = β (M, Γ) = β 2.12 K α { α} K- K- Γ M = (W, R, V ) Γ α Γ 2.11 (M, Γ) = α = α 26