Prueba formal de una de las leyes de De Morgan

Question

¿Cómo dar una demostración formal de $\vdash \neg (p\land q)\to\neg p\lor \neg q$ en el sistema de prueba de deducción natural? Aquí está lo que tengo:

0.                         (sin premisas)
   1.¬(p y q)          (suposición)
      2.p                  (suposición) 
        .
        .
        .
      95.p y q       
      96.F                 (de 1,95)
   97.¬p               (de 2-96)
   98.¬p ∨ ¬q     (de 97)
99.¬(p y q)  ¬p ∨ ¬q

Pero no sé cómo obtener $F$ a partir de $p$... Intenté usar la ley del medio excluido pero no me ayudó.

Answer 1

Su estrategia de prueba nunca va a funcionar, porque $\neg p$ no es una consecuencia lógica de $\neg (p \land q)$. Entonces, no puedes llegar a la línea 97 desde la línea 1. Del mismo modo, $p \land q$ no es una consecuencia lógica de $\neg (p \land q)$ y $p$ ... así que no puedes llegar a la línea 95 desde las líneas 2 y 3.

En cambio, intenta usar una prueba por contradicción: asume $\neg (\neg p \lor \neg q)$, y muestra que eso lleva a una contradicción:

$1. \neg(p \land q)$

$2. \quad \neg (\neg p \lor \neg q) $

...

$95. \quad p \land q$

$96. \quad \bot$

$97. \neg \neg (\neg p \lor \neg q)$

$98. \neg p \lor \neg q$

¿Y cómo funciona eso? Bueno, intenta obtener $p$ y $q$ individualmente dentro de la subprueba:

$1. \neg(p \land q)$

$2. \quad \neg (\neg p \lor \neg q) $

...

$50 \quad p$

...

$94. \quad q$

$95. \quad p \land q$

$96. \quad \bot$

$97. \neg \neg (\neg p \lor \neg q)$

$98. \neg p \lor \neg q$

De acuerdo, pero ¿cómo se hace eso? ¡Nuevamente, prueba por contradicción!

$1. \neg(p \land q)$

$2. \quad \neg (\neg p \lor \neg q) $

$3. \quad \quad \neg p$

$4. \quad \quad \neg p \lor \neg q $

$5. \quad \quad \bot$

$6. \quad \neg \neg p$

$50 (=7) \quad p$

... (igual para $q$)

$94. \quad q$

$95. \quad p \land q$

$96. \quad \bot$

$97. \neg \neg (\neg p \lor \neg q)$

$98. \neg p \lor \neg q$

Answer 2

No(p) no es absoluto, así que no intentes probarlo.

Haz esto en su lugar:

0.                         (sin premisas)
  1. no(p y q)          (suposición)
    2. p                  (suposición) 
    .
    .
    .
    95. no(q)       
  96. p  → no(q)             (de 2-95)
    97. no(p)     (suposición)
  98. no (p) o no(q) (95 y 97)
99. no(p y q) → no(p) o no(q) (de 1 - 98)

Quizás un poco más claro:

0.
   1. no (p y q) (suposición)
   2. p o no(p)   (principio de tercero excluido)
         3. no (p)    (suposición)
   4. (sin declaración)
         5. p (suposición)
            6. q (suposición)
            7. p y q (5 y 6)
            8. F  (1 y 7 contradicción)
          9. no q (6 - 8)
   5. no (p) o no (q) (3 y 9)
6. no(p y q) → no(p) o no(q) (1-5)

Answer 3

Esta prueba es similar a la que proporcionó fleablood, excepto que usa un verificador de pruebas.

También utiliza la Ley del Tercero Excluido (LEM) al considerar primero $P$ y luego considerar $¬P$ para llegar a la conclusión deseada.