26 x7 P a0 a1 a2 a3 a4 a5 a6 a7 a8 a9 a6 a10 a11 a6 a12 a13 a14 a15a16 a17 | a18a18a18a19a19a19 a20a20a20 a21a21a21a22a22a22 a23a23a23 a24a24a24 a25a25a25a26a26a26 a27a27a27 N N a28 a29 a29 a30 a31 a32 a30 (G. Gentzen, 1909{1945) a29 N . N a28 a33 a33 a31 N a34 ‘ . | a31 a35a36 a37 a38a40a39 a41 a42 a43a44 a45a46 a47a48 Hilbert a37a49 a50a51 a52a53 a54 a55a56 a57a58 a37 a39 a59 a60 a61 a62a63 a64 a42 a65a66 a67a56 a68a69 a37 a70 a71 a72 1 x7 P N a73 a74 a34 : f:;!g a75 . . : 10 a34 . a76 P a77 a78 a79 a76 a80 2 P (1) p 1 ; p 2 ; : : : ( ) (2) :; ! (2 ) (3) ), ( (2 ) 3 P a34 (1) ; (2) a29 (: ) a81 (3) a33 a29 ( ! ) a81 (4) (1)a33 (2) (3) . 4 P (A1) ( !( ! )) (A2) ( !( ! ))!(( ! )!( ! )) ! (A3) (((: )!(: ))!( ! )) 5 P a34 a28 a33 ( ! ) . (M). (Modus Ponens) (MP). 6 P (D.Hilbert) P a31 P N a31 N P a29 a31 a82a83 a63 a64a84 a85 a37 a86 a87 a60a88 a89 a90 : 1. a91 a92a93 a61 a94 a95 a96 a97a98 a99 , a100 a101a102 a103 a104a61 1982 2. a105a106 a107 a61 a94 a95 a96 a97 a61 a108 a109 a110 a111 a102 a103 a104a61 1991 7 P (A1) !( ! ) (A2) ( !( ! ))!(( ! )!( ! )) (A3) ((: )!(: ))!( ! ) 8 P ? 20 (1) !( ! ) (A1) (2) ( !( ! ))! (( ! )!( ! )) (A2) (3) ( ! )!( ! ) (M)(1)(2) 9 P 15 a28 P a32 : 1 ; 2 ; ; n ( ) i (1 i n), a32 : (1) i ; (2) i a28 ( ) i j ; k (1 j; k < i) (M) . n P a32 a112a112a112 , ‘ P n ‘ n , ( ) n a32 a113a113a113 . a28 20 : ‘ P ( ! )!( ! ) 10 (1) P P a32 a114 . (2) 1 ; 2 ; ; n P a32 , i (1 i n) ‘ i . 11 21 a34 ‘ ! : (1) ‘ !(( ! )! ) (A1) (2) ‘ ( !(( ! )! ))! (( !( ! ))!( ! )) (A2) (3) ‘ ( !( ! ))!( ! ) M(1)(2) (4) ‘ !( ! ) (A1) (5) ‘ ! (M)(3)(4) a115 a34 ‘? 12 : ‘ ! (( ! ) ! ) : (1) ( ! ) ! ( ! ( ! )) ! ( ! ) (2) ( ! ) ! ( ! ( ! )) ! ( ! ) ! ! ( ! ) ! ( ! ( ! )) ! ( ! ) ! ( ! ) ! (3) ( ! ) ! ( ! ( ! )) ! ( ! ) ! ( ! ) (4) ( ! ) ! ( ! ( ! )) (5) ( ! ) ! ( ! ) 13 ( ) (6) ( ! ) ! ( ! ) ! (( ! ) ! ) ! (( ! ) ! ) (7) (( ! ) ! ) ! (( ! ) ! ) (8) (( ! ) ! ) ! (( ! ) ! ) ! ! ! ((( ! ) ! ) ! (( ! ) ! )) ! (9) ! ((( ! ) ! ) ! (( ! ) ! )) (10) ! ((( ! ) ! ) ! (( ! ) ! )) ! ! ( ! (( ! ) ! )) ! ( ! (( ! ) ! )) ! (11) ( ! (( ! ) ! )) ! ( ! (( ! ) ! )) (12) ! (( ! ) ! ) (13) ! (( ! ) ! ) 14 a116a116a116 a116a116a116 a116a116a116 N a29 a81 P a29 a31 N a29 a81 P a29 a31 a29 N P a31 a34 a29 a29 a81 a29 a29 a81 P a117 | a118a119 a120 a121 a23 | a122a123 N 15 9 1. ‘ , ‘ ! , ‘ : . . . ‘ 9 > > > = > > > ; a32 . . . ‘ ! 9 > > > = > > > ; ! a32 ‘ (M) (M) a124 (M) a125 16 9( ) 2. ‘ ! , ‘ ! , ‘ ! . : ‘ ( ! )!( !( ! )) (A1) . . . ‘ ! 9 > = > ; ! a126a128a127 a129 a130 a131 a132a133 ‘ !( ! ) (M) ‘ (( !( ! ))!(( ! )!( ! )) (A2) ‘ ( ! )!( ! ) (M) . . . ‘ ! 9 > = > ; ! a126a128a127 a129 a130 a131 a132a133 ‘ ! (M) (Tr). 17 22 a34 ‘ : ! ( ! ) : (1) ‘ : !(: !: ) (A1) (2) ‘ (: !: )!( ! ) (A3) (3) ‘ : !( ! ) (Tr) 18 23 a34 1: ‘ :: ! 2: ‘ !:: 1: (1) ‘ :: !(: !::: ) ( ) (2) ‘ (: !::: )!(:: ! ) (A3) (3) ‘ :: !(:: ! ) (Tr)(1)(2) (4) ‘ (:: !(:: ! ))! (:: !:: )!(:: ! ) (A2) (5) ‘ (:: !:: )!(:: ! ) (M)(3)(4) (6) ‘ :: !:: ( 21) (7) ‘ :: ! (M)(5)(6) 19 23( ) a34 1: ‘ :: ! 2: ‘ !:: 2: (1) ‘ ::: !: (1:) (2) ‘ (::: !: )!( !:: ) (A3) (3) ‘ !:: (M) 20 a134a134a134 a116a116a116 a116a116a116 a116a116a116 1. N a32 a117 2. P ‘ a117 21 P 16 P a32 , P 1 ; 2 ; ; n ( ) n , i (1 i n), (1) i 2 a29 (2) i P a32 , (3) i a28 ( ) (M) . , ‘ P ‘ . 22 P \ " a32 a31 16 , a32 P a29 a32 a114 a31 16 , a32 a31 23 ‘ P (1) 2 , ‘ . (2) 0 , 0 ‘ , ‘ . (3) = ; , ; ‘ ‘ . 24 25 a34 f ; !( ! ) g ‘ ! : (1) (2) !( ! ) (A1) (3) ! (M)(1)(2) (4) !( ! ) (5) ( !( ! ))! (( ! )!( ! )) (A2) (6) ( ! )!( ! ) (M)(4)(5) (7) ! (M)(6)(3) a115 a34 a29 ‘? 25 p.508(p.101). 14(1), (3), (4) 15(1), (2) 26 27 P 2 a31 3 a31 1 a31 P a34 ‘ ? a115 a34 a29 a31 | a118a119 a120 a121 a23 | a122a123 N: P a135 a136a137 a138 a126a22 a20 28 10 [f g ‘ , ‘ ! . : 1 ; 2 ; ; n (= ) [f g a32 . : ! 1 ; ! 2 ; ; ! n (= ! ) : , , ! i (1 i n) ! i a32 . 29 | 1 i . (1) i = 1 , 1 a32 , 1 2 [f g. (1.1) 1 a32 , ! 1 : 1 !( ! 1 ) (A1) 1 ( ) ! 1 (M) 30 | 2 (1.2) 1 2 , (1.1) . (1.3) 1 , ! 1 ! . ‘ ! , ! P a32 , ! 1 , ! 1 a32 . 31 | 1 (2) ! i 1 a75 , ! i 1 ! i : (2:1) ( i ) (2:2) ( i 2 ) (2:3) ( i ) 9 > > > > > = > > > > > ; (1) . (2.4) i a28 j k (1 j; k < i) (M) , k j ! i . ! j a139 ! k a140 !( j ! i ) a141 ! i a142 a137 a143 a144 . 32 | 2 a28 , ! i 1 a75 . : . . . ! i 1 9 > = > ; ! i 1 ! i 33 | 2 a28 , ! i 1 a75 . : . . . ! j . . . ! i 1 9 > = > ; ! i 1 !( j ! i ) ! i 33-a | 2 a28 , ! i 1 a75 . : . . . ! j . . . ! i 1 9 > = > ; ! i 1 !( j ! i ) ( !( j ! i ))!(( ! j )!( ! i )) (A2) ( ! j )!( ! i ) (M) ! i (M) . 33-b 11 ‘ ! , [f g ‘ . : . . . ! 9 > > > > = > > > > ; a28 ! a32 ( ) (M) 34 26 a34 ‘ !(( ! )! ) : f ; ! g ‘ (1) (2) ! (3) (M) 2 a28 a34 ‘ !(( ! )! )a31 35 27 a34 ‘ ( ! )!(( ! )!( ! )) : f ! ; ! ; g ‘ (1) (2) ! (3) (M)(1)(2) (4) ! (5) (M)(3)(4) 36 28 a34 ‘ ( ! )!(: !: ) : f ! ; :: g ‘ :: (1) . . . :: ! 9 > = > ; ‘ :: ! (2) :: (3) (M)(1)(2) (4) ! (5) (M)(3)(4) (6) . . . !:: 9 > = > ; ‘ !:: (7) :: (M)(5)(6) 37 28( ) a34 ‘ ( ! )!(: !: ) : a28 f ! ; :: g ‘ :: ‘ ( ! )!(:: !:: ) a28 ‘ (:: !:: )!(: !: ) ‘ ( ! )!(: !: ) 38 29 a34 ‘ !(: !:( ! )) : (1) ‘ !(( ! )! ) ( 26) (2) ‘ (( ! )! ) !(: !:( ! )) ( 28) (3) ‘ !(: !:( ! )) (Tr) 39 30 a34 f !: ; ! ; g ‘ : (1) (2) ! (3) (M)(1)(2) (4) !: (5) : (M)(1)(2) . . . (6) : !( ! ) 22 (7) ! (M)(5)(6) (8) (M)(7)(3) a28 : ‘ ( ! )!(( !: )!( ! )): ‘ ( !: )!(( ! )!( ! )): 40 31 a34 f ! ; : ! g ‘ : (1) ( ! )!(: !: ) ( 28) (2) ! (3) : !: (M)(1)(2) (4) (: ! )!(: !:: ) ( 28) (5) : ! (6) : !:: (M)(4)(5) 41 31( ) a34 f ! ; : ! g ‘ (7) (: !: )! (: !:: )! (: !:( ! )) ! ( 30) (8) (: !:: )!(: !:( ! )) (M)(3)(7) (9) : !:( ! ) (M)(6)(8) (10) (: !:( ! ))!(( ! )! ) (A3) (11) ( ! )! (M)(9)(10) (12) (M)(2)(11) : ‘ ( ! )!((: ! )! ) 42 32 a34 ‘ (: ! )! : f: ! g ‘ : (1): !( !:(: ! )) ( 20) (2)(: !( !:(: ! )))! ((: ! )!(: !:(: ! ))) (A2) (3)((: ! )!(: !:(: ! ))) (M)(1)(2) (4): ! ( ) (5): !:(: ! ) (M)(3)(4) (6)(: !:(: ! ))!((: ! )! ) (A3) (7)(: ! )! (M)(5)(6) (8) (M)(4)(7) 43 32( ) a34 ‘ (: ! )! : (1) ‘ ( ! ) ! ((: ! ) ! ) ( 31) (2) ‘ ! ( 21) (3) ‘ (: ! ) ! (M) 44 33 a34 f: ! ; : !: g ‘ : (1) (: ! )!((: !: )! (: ! )) ( 30) (2) : ! ( ) (3) (: !: )!(: ! ) (M)(1)(2) (4) : !: ( ) (5) : ! (M)(3)(4) (6) (: ! )! ( 32) (7) (M)(5)(6) 45 34( ) a34 ‘ ! (: ! ) : a28 22 a34 ‘ : ! ( ! ). a28 11 a34 f: ; g ‘ . a28 a34 ‘ : ! . a28 a34 ‘ ! (: ! ). 46 12 ‘ 1 , ‘ 2 , , ‘ n , 1 ; 2 ; ; n ‘ , ‘ . : a28 1 ; 2 ; ; n ‘ , a28 : ‘ 1 ! 2 ! ! n ! . ‘ : 47 12( ) . . . ‘ 1 ! 2 ! ! n ! . . . 1 9 > = > ; ‘ 1 2 ! ! n ! . . . n ! . . . n 9 > = > ; ‘ n ‘ . 48 p.508(p.101). 14(2) 15(3), (4) 16(2), (3) [ ] P a34 (1) ( ! : ) ! : . (2) f ! ; !: g ‘ : 49 50