Desde http://www.cita.es/filosofar

Problema de lógica propuesto en clase y en sci.logic

Demostrar que (p <-> q) -> r <-> (p & q -> r) & ( ~p & ~q -> r)

Soluciones propuestas en sci.logic

Prueba 1

p q r  ((p <-> q) -> r)
-----------------------
v v v    v  v  v  v  v
v v F    v  v  v  F  F
v F v    v  F  F  v  v
v F F    v  F  F  v  F
F v v    F  F  v  v  v
F v F    F  F  v  v  F
F F v    F  v  F  v  v
F F F    F  v  F  F  F
                 (1)

p q r   (((p & q) -> r)  &  ((~p & ~q) -> r))
---------------------------------------------
v v v      v v v  v  v   v    F  F F   v  v
v v F      v v v  F  F   F    F  F F   v  F
v F v      v F F  v  v   v    F  F v   v  v
v F F      v F F  v  F   v    F  F v   v  F
F v v      F F v  v  v   v    v  F F   v  v
F v F      F F v  v  F   v    v  F F   v  F
F F v      F F F  v  v   v    v  v v   v  v
F F F      F F F  v  F   F    v  v v   F  F
                        (2)

(1) = (2) => (p <-> q) -> r <-> (p & q -> r) & ( ~p & ~q -> r)

Prueba 2:

 a) |- ((P <-> Q) -> R) -> (P & Q -> R) & (~P & ~Q -> R)


 b) |- (P & Q -> R) & (~P & ~Q -> R) -> ((P <-> Q) -> R).


 c) |- ((P <-> Q) -> R) <-> (P & Q -> R) & (~P & ~Q -> R)


a) |- ((P <-> Q) -> R) -> (P & Q -> R) & (~P & ~Q -> R)

1     (1) (P <-> Q) -> R)                 A
2     (2) P & Q                           A
2     (3) P                               2 &E
2     (4) Q                               2 &E
2     (5) Q -> P                          3 SI(S) "TC"
2     (6) P -> Q                          4 SI(S) "TC"
2     (7) P -> Q & Q -> P                 5,6 &I
2     (8) P <-> Q                         7 Df. <->
1,2   (9) R                               1,8 MPP
1    (10) P & Q -> R                      2,9 CP
11   (11) ~P & ~Q                         A
11   (12) ~P                              11 &E
11   (13) ~Q                              11 &E
11   (14) P -> Q                          12 SI(S) "FA"
11   (15) Q -> P                          13 SI(S) "FA"
11   (16) P -> Q & Q -> P                 14,15 &I
11   (17) P <-> Q                         16 Df. <->
1,11 (18) R                               1,17 MPP
1    (19) ~P & ~Q -> R                    11,18 CP
1    (20) (P & Q -> R) & (~P & ~Q -> R)   10,19 &I
     (21) ((P <-> Q) -> R) ->   
          (P & Q -> R) & (~P & ~Q -> R)   1,20 CP

b) |- (P & Q -> R) & (~P & ~Q -> R) -> ((P <-> Q) -> R)

1       (1) (P & Q -> R) & (~P & ~Q -> R)   A
2       (2) (P <-> Q)                       A
1       (3) P & Q -> R                      1 &E
1       (4) ~P & ~Q -> R                    1 &E
2       (5) (P -> Q) & (Q -> P)             2 Df. <->
2       (6) P -> Q                          5 &E
2       (7) Q -> P                          5 &E
        (8) P v ~P                          TI(S) "TND"
9       (9) P                               A
2,9    (10) Q                               6,9 MPP
2,9    (11) P & Q                           9,10 &I
1,2,9  (12) R                               3,11 MPP
13     (13) ~P                              A
2,13   (14) ~Q                              7,13 MTT
2,13   (15) ~P & ~Q                         13,14 &I
1,2,13 (16) R                               4,15 MPP
1,2    (17) R                               8,9,12,13,16 vE
1      (18) (P <-> Q) -> R                  2,17 CP
       (19) (P & Q -> R) & (~P & ~Q -> R)
            -> ((P <-> Q) -> R)             1,18 CP

c) |- ((P <-> Q) -> R) <-> (P & Q -> R) & (~P & ~Q -> R)

(1) ((P <-> Q) -> R) -> (P & Q -> R) & (~P & ~Q -> R)   TI (a)
(2) (P & Q -> R) & (~P & ~Q -> R) -> ((P <-> Q) -> R)   TI (b)
(3) (((P <-> Q) -> R) -> (P & Q -> R) & (~P & ~Q -> R))
  & ((P & Q -> R) & (~P & ~Q -> R) -> ((P <-> Q) -> R)) 1,2 &I
(4) ((P <-> Q) -> R) <-> (P & Q -> R) & (~P & ~Q -> R)  3 Df. <->


Prueba 3
1       (1) (P & Q -> R) & (~P & ~Q -> R)     A
2       (2) (P <-> Q)                         A
1       (3) (P & Q -> R)                      1 &E
1       (4) (~P & ~Q -> R)                    1 &E
2       (5) (P & Q) v (~P & ~Q)               2 SI(S) "Equiv"
6       (6) P & Q                             A
1,6     (7) R                                 3,6 MPP
8       (8) ~P & ~Q                           A
1,8     (9) R                                 4,8 MPP
1,2    (10) R                                 5,6,7,8,9 vE
1      (11) (P <-> Q) -> R                    2,10 CP
       (12) (P & Q -> R) & (~P & ~Q -> R)
             -> ((P <-> Q) -> R)              1,11 CP


Now IF "Equiv" were actually a primitive _rule of derivation_ of our system, we
could write down the 12-step proof (only consisting of "atomic steps"):


1       (1) (P & Q -> R) & (~P & ~Q -> R)     A
2       (2) (P <-> Q)                         A
1       (3) (P & Q -> R)                      1 &E
1       (4) (~P & ~Q -> R)                    1 &E
2       (5) (P & Q) v (~P & ~Q)               2 Equiv
6       (6) P & Q                             A
1,6     (7) R                                 3,6 MPP
8       (8) ~P & ~Q                           A
1,8     (9) R                                 4,8 MPP
1,2    (10) R                                 5,6,7,8,9 vE
1      (11) (P <-> Q) -> R                    2,10 CP
       (12) (P & Q -> R) & (~P & ~Q -> R)
             -> ((P <-> Q) -> R)              1,11 CP

Prueba 4 (incompleta)

   ----1 (p <-> q) -> r
   | --2 p & q
   | | 3 p <-> q  (porque (p<->q) <-> (p & q) |(~p & ~q) )
   | --4 r       (por 1)
   |   5 (p & q) -> r
   | --6 ~p & ~q
   | | 7 p <->q
   | --8 r
   |   9 (~p & ~q) ->r
   ---10 ((p & q) -> r) & ((~p & ~q) -> r)
      11 ((p <-> q) -> r) -> (((p & q) -> r) & ((~p & ~q) -> r))
 -----12 ((p & q) -> r) & ((~p & ~q) -> r)
 | ---13 (p <-> q)
 | |  14 (p & q) | (~p & ~q)
 | | -15 p & q
 | | |16 (p & q) -> r
 | | -17 r
 | | -18 ~p & ~q
 | | |19 (~p & ~q) -> r
 | | -20 r
 | |--21 r
 |----22 (p <-> q) -> r

Prueba 5 (incompleta)

1. (p <-> q) -> r
2. ~r -> ~(p <-> q)
3. ~r -> ~((p & q) V (~p & ~q))
4. ~r -> (~(p & q) & ~(~p & ~q))
5. (~r -> ~(p & q)) & (~r -> ~(~p & ~q))
6. ((p & q) -> r) & ((~p & ~q) -> r)

Supuestos aplicables:

p = Iraq had weapons of mass destruction
q = U.S. Administration is trustworthy
r = U.S. invasion of Iraq was justified

Bibliografía propuesta:

    Pudlak, P.: The Lengths of Proofs,
    in Buss, S.R. ed., Handbook of Proof
    Theory, Elsevier Science, 1998

    Bünning, H.K. and Lettmann, T.:
    Propositional Logic Deduction and
    Algorithms, Cambridge University
    Press, 1999

http://www.cita.es/filosofar