論理学入門 講義ノート email: mitsu@abelardfletkeioacjp Copyright c 1995 by the author ll right reserved

1 1 3 2 5 3 7 31 7 32 9 33 13 4 29 41 33 42 38 5 45 51 45 52 47

3 1 19 [ 1] Begin at the beginning [ 2] [ 3] [ 4] 4 [ 5]

4 1 5

5 2 (Truth) (truth table) 1 and not not B and B not B and B and not or if, then and not or if, then,,, and not or if then and not ( ), B,, B 1

6 2 I II V I II I II 1 ( I II ) ( ) ( V ) 1 ( ) 2 (( ) ( ( ))) ( ( )) 3 UFO 4 UFO ( (UFO )) 2 4 UFO 2 4 5 6,, B 5 ( B) ( B)) ( ) 6 ( ), B, B,,,, ( ) 21 1 or ( ) 2 If, then B

7 3 31 31 ( ),,,, P, Q, R,, P 1, P 2,, 1 and or not if then if and only if true false ( ) 32 ( ( )) 1 2 3 ( ) 4, B ( B) ( B) ( B) ( B) 5 1, B,,,,,

8 3 (((P Q) ) ( R)) 1 P Q R 4 (P Q) 2 4 ((P Q) ) 3 ( R) 4 (((P Q) ) ( R)) (( R) ) P Q (P Q) ( P ) Q P P R Q (P (R Q)) (P R) Q ( P ) (R Q) (P R) Q P R Q P (R Q) 1 2 < < < ((P Q) ) ( R) (P Q) P Q (P Q ) ( R) Q (P Q ) R P Q R (P Q) ( R)

32 9 32 2 33 ( ) 1 (true) (true) 2 (false) (false) 3 P (true) (false) 4 B (true) (true) B (true) 5 B (true) (true) B (true) ( ) 6 (true) (false) ( ) 7 B (true) (true) B (true) (fasle) B (true) 8 B (true) B 4 8 true t false f 1 t t 2 f f 3 P t f P t f 4 2 (true) (false)

10 3 B B t t t t B t B t t f f t B f B f f t f f B t B f f f f f B f B f 5 B B t t t t B t B t t f t t B f B t f t t f B t B t f f f f B f B f 6 t f t f f t f t 7 B B t t t t B t B t t f f t B f B f f t t f B t B t f f t f B f B t 8 B B t t t t B t B t t f f t B f B f f t f f B t B f f f t f B f B t, 31 (1) P Q P P Q P Q P P Q P t t t f f t f f f t f t f t t f f f t t (2) R Q

32 11 Q R Q R Q f t t t t f t f t t f f t f f f f f f t (3) R P Q P Q R P Q R P Q t t t t t t t f t t t f t t t t f f t t f t t t t f t f t t f f t f f f f f f t 7 B B B B t t f t t f f f f t t t f f t t B B 34 ( ), = 32 1 t f t f t t 2 t f t t 3 ( B) ( B)

12 3 B B ( B) B B ( B) ( B) t t t f f f f t t f f t f t t t f t f t t f t t f f f t t t t t 4 ( B) ( B) B B B ( B) ( B) t t t f t t t f f f f t f t t t t t f f t t t t 31 1 ( ) 2 ( B) ( B) 3 ( ( B)) 4 ( ( B)) 32 1 ( B) ( B ) 2 ( ) B 3 ( B) 4 B ( B) 5 ( B) 6 ( B) ( B) 7 ( ( B)) 8 ( (B C)) (( B) C) 9 ( (B C)) (( B) ( C)) 33 1 B ( B) (B ) 2 B ( B) 3 B ( B)

33 13 33 P, Q, R,, P 1, P 2, P Q R P Q R (P Q) R ( ), B 1,, B n B 1,, B n P B 1,, B n P B 1,, B n B 1,, B n B i B j ( i j) ( ) ( ) B i B j 2 35 ( NK ) 0 1 (1 ) 1 ( I ) P 1 B P 2 C 1 C n P 1 D 1 D m B P 2 P 1 C 1 C n P 2 D 1 D m B 2 P 1 P 2 I P B P C 1 C n D 1 D m B B B P P 1 C 1,, C n P 2 D 1,, D m C 1,, C n, D 1,, D m I

14 3 2 ( ) ( E( ) ) B P 1 C 1,, C n P 1 P 1 C 1 C n B P 1 E( ) P P C 1 C n B E( ) P P 1 C 1,, C n 3 ( ) ( E( ) ) B P 1 C 1 C n P 1 P 1 C 1 C n B P 1 E ( ) P B P C 1 C n B B E( ) B P P 1 C 1,, C n 4 ( I ) B P 1,,,, C 1,, C n B P 1 ( ),,,, C 1,, C n,,, ( ) P 1 C 1 C n B I,, [] P B

33 15 P [] [] [] C 1 C n B B I B P C 1,, C n P 1,, [] [] I ( P ) P 1 ( ) [] [] ( I 1 ) P (P ) = (P 1 ) ( ) 5 ( E ) P 1 B P 2 C 1,, C n P 1 D 1,, D m B P 2 P 1 C 1 C n P 2 D 1 D m B 2 E P P C 1 C n D 1 D m B B P P 1 C 1,, C n P 2 E D 1,, D m C 1,, C n, D 1,, D m 6 ( I ) P 1,,,, B 1,, B n P 1 ( ),,,, B 1,, B n,,, ( ) P 1 B 1 B n P 1 I,, ( I ) P

16 3 P [] [] [] B 1 B n I P P 1,,,, B 1,, B n I,,, I B 1,, B n,, 7 ( E ) P 1 P 2 C 1,, C n P 1 D 1,, D m P 2 P 2 P 1 C 1 C n P 2 D 1 D m 2 P 1 P 2 E P P C 1 C n D 1 D m P P 1 C 1,, C n P 2 D 1,, D m C 1,, C n, D 1,, D n 8 ( ) ( I( ) ) P 1 E C 1,, C n P 1 P 1 C 1 C n P 1 I( ) P B P C 1 C n B I( ) B P P 1 C 1,, C n 9 ( )( I( ) ) B P 1 C 1,, C n P 1

33 17 P 1 C 1 C n B P 1 I( ) P B P C 1 C n B B I( ) B P P 1 C 1,, C n 10 ( E ) 3 (1) B P 1 (2) C P 2 (3) C P 3 (1) P 1 D 1 D n B (2) P 2 E 1 E m C (3) P 3 B B B G 1 G l C,,,, E 1,, E m P 2 B, B,, B, G 1,, G l P 3,,,, E 1,, E m,,, B, B,, B, G 1,, G l B, B,, B B ( ) 3 P 1 P 2 P 3 E P 2 P 3 B [] [B] P C D 1 D n P B [] [] [] E 1 E m C C [B] [B] [B] G 1 G l C P P 1, P 2 P 3 E I I E 1,, E m G 1,, G l B,, B,, B 11 ( E ) P 1 C 1,, C n E

18 3 P 1 C 1 C n P 1 E P P C 1 C n E P P 1 C 1,, C n 12 ( E ) P 1 C 1,, C n P 1 P 1 C 1 C n P 1 E P P C 1 C n E P P 1 C 1,, C n 36 ( ) 1 ( ) 1 I 2 B B B B I 2, 3 E B B E B B E 4 I B B

33 19 [] n B B I,n 5 E B B B B E 6 I (false) ( ) [] n I,n 7 E E 8, 9 I ( B) B B I B B I 10 E B B C C B [] n C C [B] n C E,n 11 E ( ) E 12 E E 33 ( ) 1 ( B) C B (C )

20 3 [( B) C] 1 [( B) C] 1 [( B) C] 1 B E E B C B E I C I B (C ) ( B) C B (C ) I,1 E E 2 ( (B C)) (B C) [( (B C)) ] 1 E [( (B C)) ] 1 (B C) B C ( (B C)) (B C) I,1 E E 3 ( B) ( B ) [] 1 [ B] 2 E [ B] 3 B E I,1 B I,3 ( B) ( B ) I,2 4 ( B) C B (C ) [( B) C] 1 [ B] 2 [] 3 C I [B] 3 B (C ) I B (C ) I B (C ) B (C ) ( B) C B (C ) I,1 E,3 [C] 2 C I B (C ) I E,2 5 ( B) C ( C) (B C) [( B) C] 1 [ B] 2 [ B] 2 E E B [C] 2 [C] 2 C I B C I C I B C I I ( C) (B C) ( C) (B C) I ( C) (B C) ( B) C ( C) (B C) I,1 E,2 6 ( C) (B C) ( B) C

33 21 [( C) (B C)] 1 C E [( C) (B C)] 1 E B C [] 2 [B] 3 I 3 B [C] ( B) C I ( B) C I ( B) C ( B) C ( C) (B C) ( B) C I,1 E,3 [C] 2 ( B) C I E,2 7 ( B) C ( C) (B C) [( B) C] 1 B E [( B) C] 1 [( B) C] 1 [] 2 E C [B] 2 C I I C B C ( C) (B C) I ( C) (B C) I ( C) (B C) ( B) C ( C) (B C) I,1 E,2 E 8 ( C) (B C) ( B) C [ C] 2 [B C] 2 E [ C] 2 E B [B C] 2 B I E C B I C [( C) (B C)] 1 I ( B) C ( B) C E,2 ( B) C ( C) (B C) ( B) C I,1 I E 9 ( ) [] 2 [ ] 1 E I,1 I,2 10 ( ) [ ] 1 E I,1 11 ( B) ( B) [] 1 B I [ ( B)] 3 I,1 E [B] 2 B I [ ( B)] 3 B I,2 I B ( B) ( B) I,3 E

22 3 12 ( B) ( B) [ B] 3 E [B] 1 [ B] 3 B [] [ B] 2 E E,1 ( B) I,2 ( B) ( B) I,3 E E 13 ( B) ( B) [] 1 [ B] 3 E B B I [ ( B)] 2 E I,1 B I [ ( B)] 2 ( B) I,2 E B ( B) ( B) I,3 E 14 ( B) ( B) [] 2 [ ] 1 E [ B] 3 B E [B] 1 B B I,2 ( B) ( B) I,3 E,1 15 ( ( B)) [ ] 1 [ ( B)] 2 B E E I,1 E [ ] 1 E ( ( B)) I,2 37 ( ) B 1,, B n B 1,, B n

33 23 31 ( (soundness)) 32 ( (completeness)) 34 32 35 1 ( B C) ( (B C)) 2 ( (B C)) ( B C) 3 ( B) (B ) 4 ( B C) (( C) (B C)) 36, B, C, on-off on-off ( ) ( ) B C (B ) ( C), B, C (Spec) ( ) B ( B) B 1

24 3 C B C B 2 ( ) 37 1 2 3 4 ( ) 38 1, 2 3

33 25 4 ( 1) ( 2) ( ) 39 1 2 2 2 ( ) 2 2 : (Proof-Normalization) B B (maximal ) ( ) B B I E B B I B E B I C [] C [B] C E B B I C [] C [B] C E [] B B I E B [] I E F

26 3 33 ( (Normalization Theorem)) β (β reduction rules) Reduction rules B B I E = B B I B E = B B I C [] C [B] C E = C B B I C [] C [B] C E = B C [] B B I E B = B [] I E = P P P ( n ) n n n P ( P n ) 1 P n 1 n 1 P 1 P 1 n P 1 P 1 P 1 n 1 < n n 34 ( (Strong Normalization Theorem)) β β ( )

33 27 34 ( B) β 23(2) ( B) B β 2 [ ( B)] 4 [] 1 B I [ ( B)] 3 I,1 E [B] 2 B I [ ( B)] 3 B ( B) B I,3 E B E ( B) I,4 B I,2 I E = [] 1 B I [ ( B)] 3 I,1 E [B] 2 B I [ ( B)] 3 B E ( B) I,3 B I,2 I E = [] 1 B I [ ( B)] 2 E I,1 ( B) I,2 310 [ ( )] 7 [] 1 [ ( )] 3 1 [ ] 2 [ ( )] 3 ( ) 3 2 [ ( )] 7 ( ) 7 [] 4 [ ( )] 6 4 [ ] 5 [ ( )] 6 ( ) 6 5

29 4 (first order predicate logic) P ( ) ( ) 1 n 1 ( ) ( ) ( ) ( ) x y L(x, y) L(, ) L(, ) x

30 4 x L(x, ) x L(x, ) x x x x xl(x, ) xl(x, ) 41 ( ) x, y, z,, x 1, x 2, c 1, c 2, c 3,,,,, 1 ( ) P ( ), Q(, ), R(,, ), ( ),, (, ), 2 n- S(,, ) }{{} n ( (universal quantifier) ), ( (existential quantifier) ) 3 s, t, t 0, t 1, t 2, 42 ( ( )) 1 S(,, ) n- t 1,, t n S(t 1,, t n ) (atomic formula) ( ) 2 B ( B) ( B) ( B) 3 ( ) 4 x ( x) ( x) 4 ( ) ( ) 1 2 P (x) x P Q(x, y) x y Q (x) x (x, y) x y 3 x x for all x x x for some x 4 P ( ) Q(x, y) (x) x (x) < <

31 ( xb) ( xb) B x ( x ) B x x x x x x x( x) B B x x x x( x) x( x) x ( ) (bound variable) (free variable) P (, x, y) xp (, x, y) x y xp (, x, y) zp (, z, y) x z x z B y (, y) x y (x, y) 1 y( Q(c 1, y) xp (x, y)) 1 (, y) 4 y (, y) 1 (x, y) 4 y (x, y) 4 x y (x, y) 1 Q(c 1, y), P (x, y) 3 Q(c 1, y) 4 xp (x, y) 2 Q(c 1, y) xp (x, y) 4 y( Q(c 1, y) xp (x, y)) y( xp (x, y) Q(y, x)) 3 y ( xp (x, y) Q(y, x)) 1 y (, y) y (, y) x (x, ) x y (x, y) y x (x, y)

32 4 y xp (x, y) Q(y, x) x P (x, y) P (x, y) y Q(y, x) y y P (x, y) x x Q(y, x) x y x z w z( wp (w, z) Q(z, x)) 3 y( xp (x, y) Q(y, x)) z ( wp (w, z) Q(z, x)) x w z( wp (w, z) Q(z, w)) 1 y x z z ( zp (z, z) Q(z, x)) 2 x w y x x ( wp (w, x) Q(x, x))

41 33 41 I }Πx (x) x(x) ( ) 2 x (x) Π(x) (open assumption) [B(x)] 1 C(x) B(x) C(x) ( I 1) x(b(x) C(x)) ( I) (41) B(x) C(x) (x) x B(x) C(x) x x Πx B(x) C(x) B(x) -I [B(x)] 1 x -I x(b(x) C(x)) [B(x)] 1 C(x) xc(x) ( I) B(x) xc(x) ( I 1) -I B(x) C(x) xc(x) ( I) (x) C(x) x C(x) x C(x) Πx B(x) 1 B(x) x B(x) -I 2 t y 1 -I x -I x (42)

34 4 C(x) yc(y) (42) B(x) x C(x) x (41) x(b(x) C(x)) (42) B(x) xc(x) x (x) xc(x) -I 2 B(x) xc(x) x x 1 -I (41) x x x x C(x) x xc(x) -I -I -I -I Ḍ Ḍ Ḍ Ḍ F (c 1 ) F (c 2 ) F (c 3 ) F (c i ) F (c 1 ) F (c 2 ) F (c 3 ) F (c i ) ( I) D F (c i ) c i D F (c 1 ), D F (c 2 ), x D F (x) F (c 1 ) F (c 2 ) F (c 3 ) xf (x) -I x F xf (x) E x(x) (t) t (first order term) x, y x y(y > x) y(y > x) x y(y > x) x(x > x) ( E) ( E) (43) (44)

41 35 (43) x y 3 (44) (44) -I t (t) I E (t) x(x) t (first order term) x(x) D (x) D ( ) (i) D x (ii) (x) -I ( ) 4 1 x 1 x D x x 1 C x 1 x C -E -E -E F (c 1 ) F (c 2 ) F (c i ) D F (c 1 ) D F (c 2 ) D F (c i ) D F (c 1 ) D,, F (c i ) D, x F (x) D F (c 1 ) F (c 2 ) F (c i ) xf (x) -E -E -E [ xf (x, b)] 1 ( E) F (a, b) y xf (x, y) yf (a, y) ( I) ( E 1 ) yf (a, y) x(x) y xf (x, y) (x) xf (x, b) D yf (a, y) x xf (x, b) b 3 x 2 4 (x) x D (x)

36 4 b yf (a, y) (i) yf (a, y) yf (a, y) b (ii) xl(x, ) [L(x, )] 1 yl(x, y) H(x) x( yl(x, y) H(x)) ( I) ( I) yl(x, y) H(x) ( E) H(x) ( E 1 ) L(x, y) x y H(x) x y( xl(y, x) H(y)) xl(x, )( 1 ) 5 x H(x)(x ) 6 (i) D H(x) x x 1 x x (i) (ii) xl(x, ) [L(x, )] 1 yl(x, y) zp (z) ( I) yl(x, y) P (x) P (x) zp (z) ( I) ( E 1 ) ( E) P (x) x yl(x, y) P (x) x x (ii) xl(x)( 1 ) P (x)( x ) x x x x (ii) 41 ( ) 1 x(x) x (x) 5 x x 6 x xl(x, ) x!

41 37 [ (x)] 1 x (x) I [ x (x)] 2 (x) I,1 E E (x) x(x) I [ x(x)] 3 x (x) I,2 E x (x) x(x) x (x) I,3 E 2 x y(x, y) x y (x, y) [ y(x, y)] 1 x y(x, y) I [ x y(x, y)] 2 E y(x, y) I,1 [(x, y)] 3 E y(x, y) y(x, y) I [ y(x, y)] 4 x y(x, y) I [ x y(x, y)] 5 E (x, y) I,3 x y(x, y) I,2 y (x, y) I E x y(x, y) x y (x, y) I E,4 x y (x, y) x y(x, y) x y (x, y) I,5 41 1 x (x) x(x) 2 x y (x, y) x y(x, y) 3 x (x) x(x) 4 x y(x, y) x y (x, y) 5 x(x) yb(x) z((z) B(z)) 6 x((x) B(x)) x(x) xb(x) 7 x((x) B(x)) x(x) xb(x) 8 x y((x) B(y)) ( x(x) yb(y)) 9 x y((x) B(y)) ( x(x) yb(y)) E

38 4 42 ( ) (Denotational semantics) t f t f t f t f ( ) ( D ) ( ) {t, f} ( ) ( ) D D ( ) 1 D 2 D D 3 1 P ( ) D P ( ) D 1 2 P (,, ) 3 (three place predicate symbol) P (,, ) D D D 4 7 P (c) c( c) (D ) P (D ) P (c) P (c) P (c 1, c 2, c 3 ) 5 P (x) ( x ) x a( a D ) P (x) (P (x)[a] ) P (x)[a] a P (D ) P (x 1, c 1, x 2 ) P (x 1, c 1, x 2 )[a, b] 6 B B B ( ) x 1,, x n a 1,, a n ( D) 7 x(y 1,, y n, x)[a 1,, a n ] ( y 1,, y n, x a 1,, a n y 1,, y n ) x(y 1,, y n )[a 1,, a n ] D b (y 1,, y n, x)[a 1,, a n, b] 7

42 39 8 x(y 1,, y n )[a 1,, a n ] D b (y 1,, y n, x)[a 1,, a n, b] (model) 43 ( ) D, φ D φ 1 c φ(c) D φ(c) c D c φ(c) c 2 n P (,,, ) }{{} n φ(p ) D D D }{{} n P (P P ) D, φ (x 1,, x n ) ( x 1,, x n ) x 1,, x n a 1,, a n ( D) (x 1,, x n ) a 1,, a n ( ) φ((x 1,, x n )[a 1,, a n ]) φ((x 1,, x n )[a 1,, a n ]) = t (x 1,, x n ) D, φ a 1,, a n D, φ = (x 1,, x n )[a 1,, a n ] D, φ = 44 ((x 1,, x n ) a 1,, a n ( )) 1 (x 1,, x n ) n- P (x 1,, x n ) P (x 1,, x n ) D, φ = P (x 1,, x n )[a 1,, a n ] a 1,, a n φ(p ) 2 (x 1,, x n ) B(x 1,, x n ) C(x 1,, x n ) D, φ = (B(x 1,, x n ) C(x 1,, x n ))[a 1,, a n ] D, φ = B(x 1,, x n )[a 1,, a n ] D, φ = C(x 1,, x n )[a 1,, a n ] 3 (x 1,, x n ) B(x 1,, x n ) C(x 1,, x n ) D, φ = (B(x 1,, x n ) C(x 1,, x n ))[a 1,, a n ] D, φ = B(x 1,, x n )[a 1,, a n ] D, φ = C(x 1,, x n )[a 1,, a n ] 4 (x 1,, x n ) B(x 1,, x n ) D, φ = B(x 1,, x n ) D, φ = B(x 1,, x n )[a 1,, a n ] ( D, φ = B(x 1,, x n )[a 1,, a n ] ) 8 5 (x 1,, x n ) yb(x 1,, x n, y) D, φ = yb(x 1,, x n, y) D b ( b D) D, φ = B(x 1,, x n, y)[a 1,, a n, b] 8 B B

40 4 6 (x 1,, x n ) yb(x 1,, x n, y) D, φ = yb(x 1,, x n, y) D b( b D) D, φ = B(x 1,, x n, y)[a 1,, a n, b] 42 D { } 5 ( ) (x) (x ) φ φ( ) = φ( ) = φ( ) = φ( ) = φ φ( ) = 4 D ( ) φ( ) = D φ( ) φ( ) = {, } D D, φ = ( ) ( D, φ ) D, φ =/ ( ) ( D, φ ) D, φ =/ ( ) ( D, φ ) ( )

42 41 ( ) ( ) ( ) (x) D 44 D, φ = (x)[ ] ( ) D, φ =/ (x)[ ] ( ) D, φ = (x)[ ] ( ) D, φ D φ D, φ = (valid) = D x(x) D, φ = x(x) D a D, φ = (x)[a] x(x) D, φ = x(x) D a D, φ = (x)[a] D D x (x) D x (x) D Man( ) x(man(x) (x)) x(man(x) (x)) ( ) x y x(man(x) (x)) x(man(x) (x)) x(x) x(x) 45 ( ) α, β, γ,, α 1, α 2, α α x α, y α, z α, x α 1, x α 2, α c α 1, c α 2, n- α 1,, α n n- P α1,,αn (,, ) }{{} n

42 4 P α 1,,α n (,, ) n- t 1,, t n α 1,, α n P α 1,,α n (t 1,, t n ) ( ) n α 1,, α n ( ) D, φ D α1,, D αn, φ D αi α i ( α i ) α i c α i φ(c α i ) D αi α i x α i a a D αi α 1,, α n n P α 1,,α n (,, ) }{{} n φ(p α 1,,α n (,, )) D }{{} α1 D αn n 41 ( (Completeness thorem)) = ( ) ( ) 42 < D, φ > = ( ) ( ) < D, φ > = ( ) ( ) < D, φ > = ( ( ) ( )) < D, φ > = x( (x)) < D, φ > = x( (x)) 43 1 2 3 4 ( ) 44 1 x (x)

42 43 2 x( (x) (x)) 3 x (x) 4 x( (x) (x)) ( ) x (x) 45 1, 2 3 4 ( 1) ( 2) ( ) 46 1 x( yl(x, y) H(x)) 2 y( xl(x, y) B(y)) 3 y(b(y) xl(x, y))

44 4 4 xb(x) y H(y) ( 1) x( yl(y, x) yl(x, y)) y(b(y) H(y)) ( 2) xbx x( yl(y, x) y L(x, y)) 47 1 2 2 2 ( ) 2 2 48 1 x( (x) (x)) 2 x( (x) (x)) 3 x( (x) (x)) ( ) x (x) 49 1 x( (x) (x)) 2 x( (x) (x)) 3 x (x) ( ) x( (x) (x))

45 5 51 ( ) ( ) (1) ( ) (2) ( ) (3) ( ) (1) (2) (3) (1) (2) (3) ( ) ( ) 51 ( ) (1) (1 ) (1 ) (2) (3) (1 ) ( ) ( ) ) ( ) ( [ ] 1 ( ) ( ) E I 1 E E

46 5 ( ) (1) (2) (3) (1) (2) (3) ( ) ((1) (2) (3) ) = ((1) (2) (3) ) (1) (2) (3) (1) (2) (3) (counter-model) (1) (2) (3) 1 ( ) 1 (1) (2) (3) (1) (2) (3) (1) (2) (1) (2) (3) (i) t t t f f f t (ii) t f f f t f t (iii) f t t t f t f (iv) f f t t t t t (i) (iv) (1) (2) (3) (i) (1) (2) (3) (1) (2) (iii) (iv) (1) (2) (3) (iii) (iii) ( ) ( ) (1) (2) {(1), (2), (3)} ( ) 2 1 (1) (2) (3) ( ) ( ) 2 ( )

52 47 52 babababababababababababababababababababab ( ) (B ) (C ) (D ) (E ) ( ) B ( ) D E C B E D ( ) D? ( ) x x x x y (x) (x) (x) (x) (x, y) 1 () (B) (C) (D) (E) 2 () 3 (B) 4 (D) 5 (E)

48 5 6 x( (x) (x)) 7 x( (x) (x)) 8 x( (x) (x)) 9 (D, ) 10 (B, E) 11 (, C) 12 x( (x) (x)) 13 x y( (x) (x, y) (y)) 14 x( (x) (x)) 15 (D) 7 8 ( ) x (x) x (x) 2 15 x (x) 1 x (x)? 2 15 x (x) 52 2 15 x (x) 2 15 x (x) 2 15 x (x) ( ) ( ) Γ Γ 53 ( ) x (x) 2 15 x (x) ( ) 2 15 x (x) 2 15 x (x) 54 x (x) x (x)!

52 49 55 x (x) ( ) 1 (a) x (x) 1 15 (b) () (C) (D) (c) E B (E) (B) (d) 1 15 E (E) (E) 56 (a) (b) imformal 57 (c) (d) 1 15 (d) ϕ 58 (E) (E) ( (E) (E) ) (a) (b) B E E 1 ( ) B E B (E ) 1 ( ) 16 x y( (x) (y) x y) = 2 = B E 17 B = E

50 5 59 1 15 17 (E) 51 ( ) (reflexivity) x(x = x) 1 (commmutativity) s = t t = s 2 (transitivity) s = t t = u s = u 3 s = t (t) (s) s t 1 510 511 ( )