「計算論理学」講義ノート - Keio University

1 Email: 1.. 1 3. 2 5. 3 7.. 7.. 9.. 13. 4 (Typed -calculus) 29.. 29.. 31. (N at ) .. 32. 5 37.. 41.. 46. 3. 1 .. 19 .. [ 1] Begin at the beginning.. [ 2] .. [ 3] .. [ 4] .. 4 . [ 5] .. 4 1 . 5 .. 5. 2 . (Truth) .. (truth table) 1 . and not . A not A.. A B A and B.. A not A A B A and B .. and not or if .. , then .. and not or . if .. , then .. , , , . and not or if .. then . and not ( .. ) A, B, .. A, 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 , . A, B .. 5. (A B) ( B)) ( A). 6. A ( A).. A, B . A, B, .. , , , .. ( ).. 1. A or B ( ) . 2. If A, then B . 7. 3 .. ( ). , , , , . P, Q, R, .. , P1 , P2.

2 , .. 1 . and . or . not . if .. then .. if and only if . true . f alse . ( ) .. ( ( )). 1.. 2.. 3. A ( A) . 4. A, B (A B) (A B) (A B) (A B) .. 5.. 1 A, B, .. , , , , .. 8 3 . (((P Q) ) ( R)) .. 1 P Q R . 4 (P Q) . 2 . 4 ((P Q) ) . 3 ( R) . 4 (((P Q) ) ( R)) . (( R) ) .. 1. (A ). 2. (( (A B)) B). 3. ( ((A B) A)).. 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) .. 1. ( ( ( ))). 2. (( (A B)) ( B)). 3. ((( (A B)) (A ( B))) (B )). 9.. 2 . ( ). 1. (true) (true) . 2. (false) (false) . 3. P (true) (false) . 4. A B (true) A (true) B (true) . 5. A B (true) A (true) B (true) ( . ) . 6. A (true) A (false) ( A ).

3 7. A B (true) A (true) B (true) . A (fasle) B (true) . 8. A B (true) A 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 . A B A B. t t t A t B t A B t t f f A t B f A B f f t f A f B t A B f f f f A f B f A B f 5. A B A B. t t t A t B t A B t t f t A t B f A B t f t t A f B t A B t f f f A f B f A B f 6. A A. t f A t A f f t A f A t 7. A B A B. t t t A t B t A B t t f f A t B f A B f f t t A f B t A B t f f t A f B f A B t 8. A B A B. t t t A t B t A B t t f f A t B f A B f f t f A f B t A B f f f t A f B f A B t , .. (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. 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.

4 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 A B A B . A B A A B. t t f t t f f f f t t t f f t t A B A B . ( ) , .. A A A A. 1. A A t f t f t t A A A. 2. A A t t f t 3. (A B) ( A B). A B A B (A B) A B A B (A B) ( A 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 12 3 . 4. (A B) ( A B). A B A B A A B (A B) ( A 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 . 1. A ( A). 2. (A B) ( A B). 3. ( A (A B)) A. 4. ( A (A B)) A.. 1. (A B) ( B A). 2. (A A) B. 3. (A B) A. 4. B (A B). 5. A (A B). 6. ( A B) (A B). 7. (A (A B)) A. 8. (A (B C)) ((A B) C). 9. (A (B C)) ((A B) (A C)). 1. A B (A B) (B A) . 2. A B ( A B) . 3. A B ( A B) .. 1. A, B t A B t.

5 2. A B t A t . A B A B A B A B. A B t B t . t t t t t 3. A B t A t B t t f f f t f t f t t 4. A t A B t f f f t f B t A B t .. 13.. P, Q, R, .. , P1 , P2 , .. P Q R P Q R (P Q) R .. ( ) .. A, B1 , .. , Bn B1 , .. , Bn A . P B1 , .. , Bn A P B1 , .. , Bn A B1 , .. , Bn .. Bi Bj ( i = j) . ( ) ( ) . Bi Bj . 2 .. ( NK ) . 0. A A A . 1 . A (1 ) . 1. ( I ) A P1 B P2 . C1 Cn A P1 D1 Dm B . P2 .. C1 Cn D1 Dm .. P1 .. P2 .. A B. 2 P1 P2 I P A B .. C1 Cn D1 Dm .. P .. A B. A B. I. A B P P1 C1 , .. , Cn P2 . D1 , .. , Dm C1 , .. , Cn , D1 , .. , Dm . 14 3 . 2. ( ) ( E( ) ) A B P1 . C1 , .. , Cn P1 .. C1 Cn .. P1 .. A B. P1 E( ) P A .. C1 Cn .. P.. A B. A. E( ). A P P1 C1 , .. , Cn . 3. ( ) ( E( ) ) A B P1 . C1 Cn P1.

6 C1 Cn .. P1 .. A B. P1 E ( ) P B .. C1 Cn .. P.. A B. B. E( ). B P P1 C1 , .. , Cn . 4. ( I ) B P1 . A, A, .. , A, C1 , .. , Cn B P1 ( ) . A, A, .. , A, C1 , .. , Cn A, A, .. , A A ( ).. A A A C1 Cn .. P1 .. B. I A, .. , A . [A] P A B .. [A] [A] [A] C1 Cn .. P .. B. I. A B. 15. A B P C1 , .. , Cn P1 . A, .. , A [A] .. [A] I . ( P ) P1 A. ( ) [A] .. [A] ( I . 1 ) . P . (P ) = (P1 ) ( A ).. 5. ( E ) A P1 A B P2 . C1 , .. , Cn A P1 D1 , .. , Dm A B P2 .. C1 Cn D1 Dm .. P1 .. P2 .. A A B. 2 E P .. C1 Cn D1 Dm .. P .. A A B. B. E. P P1 C1 , .. , Cn P2 . D1 , .. , Dm C1 , .. , Cn , D1 , .. , Dm . 6. ( I ) P1 . A, A, .. , A, B1 , .. , Bn P1 ( . ) A, A, .. , A, B1 , .. , Bn A, A, .. , A ( . ) .. A A A B1 Bn.

7 P1 .. P1 I A, .. , A . ( I ) P A .. [A] [A] [A] B1 Bn .. P .. I. A. 16 3 . P P1 A, A, .. , A, B1 , .. , Bn I. A, A, .. , A I . B1 , .. , Bn A A, .. , A .. 7. ( E ) A P1 A P2 . C1 , .. , Cn A P1 D1 , .. , Dm A. P2 P2 .. C1 Cn D1 Dm .. P1 .. P2 .. A A. 2 P1 P2 E P .. C1 Cn D1 Dm .. P .. A A.. E. P P1 C1 , .. , Cn P2 . D1 , .. , Dm C1 , .. , Cn , D1 , .. , Dn . 8. ( ) ( I( ) ) A P1 . C1 , .. , Cn P1 .. C1 Cn .. P1 .. A. P1 I( ) P A B .. C1 Cn .. P.. A. A B I( ). A B P P1 C1 , .. , Cn .. 9. ( )( I( ) ) B P1 . C1 , .. , Cn P1 .. C1 Cn .. P1 .. B. P1 I( ) P A B . 17.. C1 Cn .. P.. B. A B I( ). A B P P1 C1 , .. , Cn .. 10. ( E ) 3 . (1) A B P1. (2) C P2. (3) C P3. (1) (2) (3).. D1 Dn A A A E1 Em B B B G1 G l.

8 P1 .. P2 .. P3 .. A B C C. A, A, .. , A, E1 , .. , Em P2 B, B, .. , B, G1 , .. , Gl P3 A, A, .. , A, E1 , .. , Em . A, A, .. , A B, B, .. , B, G1 , .. , Gl B, B, .. , B A . B ( ) . 3 P1 P2 P3 E P2 . A P3 B . [A] [B] P C .. [A] [A] [A] E1 Em [B] [B] [B] G1 Gl . D1 Dn .. P .. A B.. C C. E. C. P P1 , P2 P3 E. I I . E1 , .. , Em A G1 , .. , Gl B . A, .. , A B, .. , B . 11. ( E ) P1 . C1 , .. , Cn .. C1 Cn .. P1 .. P1 E P A A .. 18 3 .. C1 Cn .. P.. A. E. P P1 C1 , .. , Cn . 12. ( E ) A P1 . C1 , .. , Cn P1 .. C1 Cn .. P1 .. A. P1 E P .. C1 Cn .. P.. A.. A. E. P P1 C1 , .. , Cn . ( ) 1 A A . ( ) .. 1. I 2 A B A B . A B I. A B. 2 , 3. E A B A . A B E. A B E. A B. 4. I A B A . A B . [A]n .. B I,n A B. 5. E A A B B.

9 19. A A B E. B. 6. I A (false) A A . A( A) . [A]n .. I,n A. 7. E A A . A A E.. 8 , 9. I A( B) A B . A I. B I. A B A B. 10. E A B A B C . C . [A]n [B]n .. A B C C E,n C. 11. E ( ) A . E. A. 12. E A A . A E. A. ( ) A A . B1 , .. , Bn A B1 , .. , Bn A .. ( ) I E . 1. A B B A . A B E. A B E. B A I. B A. 20 3 . 2. (A B) C B (C A) . (A B) C. E. (A B) C (A B) C A B E. E E. A B E C A I. B C A I. B (C A).. 1. A (B C) (A B) C . ( ) I, E . 1. A B B A. [A B]1 [A B]1. E E. B A I. B A I,1. A B B A. 2. (A (A B)) B. [A (A B)]1 [A (A B)]1. E E. A A B E. B I,1. (A (A B)) B. 3. (A B C) (A (B C)). [A]2 [B]1. I. A B [A B C]3. E. C I,1. B C I,2. A (B C). I,3. (A B C) (A (B C)).. 1. (A (B C)) (A B C). 2. (A (B C)) A (B C). 3.

10 (A B) ((B C) (A C)). ( ) I, E . 1. (A B) ( B A). 21. [A]1 [A B]2. E. B [ B]3. E. I,1. A I,3. B A I,2. (A B) ( B A). 2. A ( A). [A]2 [ A]1. E. I,1. A I,2. A A.. 1. A A. 2. (A C) (B C) (A B). ( ) I, E . 1. A B B A. [A]1 [B]1. I I. [A B]2 B A B A. E,1. B A I,2. A B B A. 2. (A C) (B C) (A B C). [(A C) (B C)]3 [(A C) (B C)]3. E E. [A]1 A C [B]1 B C. E E. [A B]2 C C. E,1. C I,2. (A B C). I,3. (A C) (B C) (A B C). 3. ( A B) (A B). [ A B]3 [ A B]3. E E. [A]1 A [B]1 B. E E. [A B]2 . E,1. I,2. (A B). I,3. ( A B) (A B). 4. (A B) ( A B). 22 3 . [A]1 [B]2. I I. A B [ (A B)] 3. A B [ (A B)]3. E E. I,1 I,2. A B I. A B I,3. (A B) ( A B).. 1. ( A B) (A B). 2. (A B) C B (C A). 3. (A B) C (A C) (B C). 4. (A C) (B C) (A B) C.