Pruebas axiomáticas en lógica proposicional

Question

Tengo que utilizar estos tres axiomas

(A1) $P \to (Q \to P)$

(A2) $(P \to (Q \to R)) \to ((P \to Q) \to (P \to R))$

(A3) $(\neg Q \to \neg P) \to ((\neg Q \to P) \to Q)$

junto con el Modus Ponens para demostrar :

1. $(\neg\neg P \to \neg Q) \vdash (Q \to \neg P)$

2. $\neg(\neg \neg P \to \neg Q), (\neg \neg P \to \neg Q) \vdash P$

Entiendo el proceso de creación de la prueba, pero he intentado muchas cosas y me he devanado los sesos en vano. Cualquier ayuda será apreciada, gracias.

Answer 1

Para el primero: Si se permite utilizar el Teorema de la Deducción, es bastante sencillo. Primero, demostremos $\neg \neg P \to \neg Q, Q \vdash \neg P$ :

$1 \ \neg \neg P \to \neg Q \ Assumption$

$2 \ Q \ Assumption$

$3 \ Q \to (\neg \neg P \to Q) \ Axiom \ 1$

$4 \ \neg \neg P \to Q \ MP \ 2,3$

$5 \ (\neg \neg P \to \neg Q) \to ((\neg \neg P \to Q) \to \neg P) \ Axiom \ 3$

$6 \ (\neg \neg P \to Q) \to \neg P \ MP \ 1,5$

$7 \ \neg P \ MP \ 4,6$

Bien, ahora que tenemos $\neg \neg P \to \neg Q, Q \vdash \neg P$ , simplemente utilizamos el Teorema de la Deducción, y obtenemos $\neg \neg P \to \neg Q \vdash Q \to \neg P$

Si no se le permite utilizar el Teorema de la Deducción, entonces esto se vuelve un poco más desagradable:

$1 \ \neg \neg P \to \neg Q \ Assumption$

$2 \ (\neg \neg P \to \neg Q) \to (Q \to (\neg \neg P \to \neg Q)) \ Axiom \ 1$

$3 \ Q \to (\neg \neg P \to \neg Q) \ MP \ 1,2$

$4 \ Q \to (\neg \neg P \to Q) \ Axiom \ 1$

$5 \ (\neg \neg P \to \neg Q) \to ((\neg \neg P \to Q) \to \neg P) \ Axiom \ 3$

$6 \ ((\neg \neg P \to \neg Q) \to ((\neg \neg P \to Q) \to \neg P)) \to (Q \to ((\neg \neg P \to \neg Q) \to ((\neg \neg P \to Q) \to \neg P))) \ Axiom \ 1$

$7 \ Q \to ((\neg \neg P \to \neg Q) \to ((\neg \neg P \to Q) \to \neg P)) \ MP \ 5,6$

$8 \ (Q \to ((\neg \neg P \to \neg Q) \to ((\neg \neg P \to Q) \to \neg P))) \to ((Q \to (\neg \neg P \to \neg Q)) \to (Q \to ((\neg \neg P \to Q) \to \neg P))) \ Axiom \ 2$

$9 \ (Q \to (\neg \neg P \to \neg Q)) \to (Q \to ((\neg \neg P \to Q) \to \neg P)) \ MP \ 7,8$

$10 \ Q \to ((\neg \neg P \to Q) \to \neg P) \ MP \ 3,9$

$11 \ (Q \to ((\neg \neg P \to Q) \to \neg P)) \to ((Q \to (\neg \neg P \to Q)) \to (Q \to \neg P)) \ Axiom \ 2$

$12 \ (Q \to (\neg \neg P \to Q)) \to (Q \to \neg P) \ MP \ 10, 11$

$13 \ Q \to \neg P \ MP \ 4,12$

La segunda es de la forma $\neg Q, Q \vdash P$ y eso es realmente fácil de probar:

$1 \ \neg Q \ Assumption$

$2 \ Q \ Assumption$

$3 \ \neg Q \to (\neg P \to \neg Q) \ Axiom \ 1$

$4 \ \neg P \to \neg Q \ MP \ 1,3$

$5 \ Q \to (\neg P \to Q) \ Axiom \ 1$

$6 \ \neg P \to Q \ MP \ 2,5$

$7 \ (\neg P \to \neg Q) \to ((\neg P \to Q) \to P) \ Axiom 3$

$8 \ (\neg P \to Q) \to P \ MP \ 4,7$

$9 \ P \ MP \ 6,8$

Así, en lugar de $Q$ Utilizar $\neg \neg P \to \neg Q$ en la prueba anterior, y ya está. Aquí hay una prueba verificada por ordenador: