Aprende 4 técnicas de deducción imprescindibles
Resumen:En esta clase se describen 4 técnicas de deducción de la lógica proposicional para enriquecer el cálculo proposicional rudimentario que se ha presentado hasta ahora. Se presenta la regla de presunción y su combinación con la regla de monotonía, así como el silogismo hipotético y dos formas de obtener esta regla de deducción. También se explican las equivalencias de doble negación y el contrapositivo de la implicancia.
Objetivos de Aprendizaje:
Al finalizar esta clase el estudiante será capaz de
- Recordar la estructura de un razonamiento y ejemplos sencillos.
- Comprender la regla de presunción y su relación con el teorema de deducción.
- Comprender la regla del silogismo hipotético y su relación con el modus ponens.
- Aplicar el teorema de deducción en la lógica proposicional.
- Aplicar la regla de monotonía en la deducción de expresiones.
- Comprender la equivalencias de doble negación y el contrapositivo de la implicancia de la lógica proposicional.
- Conocer las demostraciones de las técnicas de deducción y ser capaz de aplicarlas en la práctica.
INDICE DE CONTENIDOS
REGLA DE PRESUNCIÓN (PRE)
EL SILOGISMO HIPOTÉTICO (SH)
EQUIVALENCIAS DE DOBLE NEGACIÓN (DN)
EQUIVALENCIA DEL CONTRAPOSITIVO DE LA IMPLICANCIA (CPI)
Ya hemos visto cómo es la estructura de un razonamiento y ejemplos sencillos. Ahora pondremos a prueba ese conocimiento razonando con 4 técnicas de deducción de la lógica proposicional. A través de esto no solo veremos que estas cosas funcionan, sino que además comenzaremos a dar cierta riqueza de procedimientos que sacará del estado rudimentario en que se encuentra el cálculo proposicional que hasta ahora se ha presentado.
Si \alpha, \beta y \gamma son expresiones del cálculo proposicional, entonces es posible inferir las siguientes técnicas de deducción desde los fundamentos:
Regla de Presunción (Pre)
La regla de deducción más sencilla de todas es la de presunción. Esta se obtiene directamente al aplicar el recíproco del teorema de deducción sobre el teorema \vdash(\alpha\rightarrow\alpha). Si esto te ha sonado a lenguaje arcano, todo lo que necesitas saber está aquí.
\{\alpha\}\vdash \alpha
Combinada con la regla de monotonía, te permitirá agregar expresiones convenientes dentro de tus deducciones.
El Silogismo Hipotético (SH)
El silogismo hipotético, o transitividad de la implicación, es una suerte de evolución del modus ponens. Su formulación es la siguiente:
\{(\alpha\rightarrow\beta), (\beta\rightarrow\gamma)\}\vdash (\alpha\rightarrow\gamma)
Existen varias formas de obtener esta regla de deducción, veremos un par de ellas en breve.
Si razonamos a partir de expresiones, será sencillo construir el siguiente razonamiento:
| (1) | \alpha | ; Premisa |
| (2) | (\alpha \rightarrow \beta) | ; Premisa |
| (3) | (\beta\rightarrow \gamma) | ; Premisa |
| (4) | \beta | ; MP(1,2) |
| (5) | \gamma | ; MP(4,3) |
Por lo tanto \{\alpha,(\alpha\rightarrow\beta),(\beta\rightarrow\gamma)\}\vdash\gamma
Finalmente, aplicando el teorema de deducción sobre esta última expresión se tiene que:
\{(\alpha\rightarrow\beta),(\beta\rightarrow\gamma)\}\vdash(\alpha\rightarrow \gamma)
Otra forma de obtener la demostración de esta regla es razonando a partir de deducciones, construyendo a través de la presunción y la monotonía. Observe el siguiente razonamiento a partir de deducciones:
| (1) | \{\alpha, (\alpha\rightarrow \beta), (\beta\rightarrow\gamma)\}\vdash \alpha | ; Presunción y Monotonía |
| (2) | \{\alpha, (\alpha\rightarrow \beta), (\beta\rightarrow\gamma)\}\vdash (\alpha\rightarrow \beta) | ; Presunción y Monotonía |
| (3) | \{\alpha, (\alpha\rightarrow \beta), (\beta\rightarrow\gamma)\}\vdash (\beta\rightarrow\gamma) | ; Presunción y Monotonía |
| (4) | \{\alpha, (\alpha\rightarrow \beta), (\beta\rightarrow\gamma)\}\vdash \beta | ; MP(1,2) |
| (5) | \{\alpha, (\alpha\rightarrow \beta), (\beta\rightarrow\gamma)\}\vdash \gamma | ; MP(4,3) |
| (6) | \{(\alpha\rightarrow \beta), (\beta\rightarrow\gamma)\}\vdash (\alpha \rightarrow \gamma) | ; TD(5) |
Debes notar aquí que ambas demostraciones son identicas, sólo que se han desarrollado con estilos diferentes. En la practica puedes alternar entre ambos estilos según lo que te resulte más comodo.
Equivalencias de Doble Negación (DN)
Las equivalencias de doble negación reproduce la noción intuitiva de que la doble negación de una afirmación es equivalente a la misma afirmación. Esto, escrito de forma simbólica, será de la forma
\alpha\dashv\vdash\neg\neg\alpha
Veamos ahora una demostración:
| (1) | \vdash (\neg\neg \alpha \rightarrow (\neg\neg\neg\neg \alpha \rightarrow\neg\neg\alpha)) | ; A1 |
| (2) | \vdash ((\neg\neg\neg\neg\alpha \rightarrow \neg\neg\alpha)\rightarrow(\neg\alpha \rightarrow \neg\neg\neg\alpha)) | ; A3 |
| (3) | \vdash ((\neg\alpha \rightarrow \neg\neg\neg\alpha)\rightarrow(\neg\neg\alpha \rightarrow \alpha)) | ; A3 |
| (4) | \vdash ((\neg\neg\neg\neg\alpha \rightarrow \neg\neg\alpha)\rightarrow(\neg\neg\alpha \rightarrow \alpha)) | ; SH(2,3) |
| (5) | \{\neg\neg \alpha \} \vdash (\neg\neg\neg\neg \alpha \rightarrow\neg\neg\alpha) | ; RTD(1) |
| (6) | \{\neg\neg \alpha \} \vdash ((\neg\neg\neg\neg\alpha \rightarrow \neg\neg\alpha)\rightarrow(\neg\neg\alpha \rightarrow \alpha)) | ; Monotonía(4) |
| (7) | \{\neg\neg \alpha \} \vdash (\neg\neg\alpha \rightarrow \alpha) | ; MP(5,6) |
| (8) | \{\neg\neg \alpha \} \vdash \alpha | ; RTD(7) |
Por lo tanto\{\neg\neg \alpha \} \vdash \alpha
Para hacer la demostración en el otro sentido podemos hacer uso de ésta que acabamos de hacer readaptándola a través de una simple sustitución, obteniendo lo siguiente:
\{\neg\neg \neg \alpha \} \vdash \neg \alpha
Y a partir de ésto armamos la demostración en el otro sentido:
| (1) | \{\neg\neg \neg \alpha \} \vdash \neg \alpha | ; Lo que acabamos de Probar |
| (2) | \vdash(\neg\neg \neg \alpha\rightarrow \neg \alpha) | ; TD(1) |
| (3) | \vdash((\neg\neg \neg \alpha\rightarrow \neg \alpha) \rightarrow(\alpha \rightarrow\neg\neg\alpha)) | ; A3 |
| (4) | \vdash(\alpha \rightarrow\neg\neg\alpha) | ; MP(2,3) |
| (5) | \{\alpha\}\vdash\neg\neg\alpha | ; RTD(4) |
Por lo tanto \{\alpha \} \vdash \neg\neg \alpha
Finalmente, de estas dos demostraciones se tiene que \alpha \dashv\vdash \neg\neg \alpha .
Equivalencia del Contrapositivo de la Implicancia (CpI)
Esto corresponde a la siguientes equivalencias
(\alpha \rightarrow \beta) \dashv\vdash (\neg\beta \rightarrow \neg\alpha)
(\neg\alpha\rightarrow\beta)\dashv\vdash (\neg\beta\rightarrow\alpha)
(\alpha\rightarrow\neg\beta) \dashv\vdash (\beta\rightarrow\neg\alpha)
La demostración de ésta primera relación se hace de la siguiente manera:
De un lado, se obtiene directamente desde el tercer axioma
| (1) | \vdash ((\neg\beta\rightarrow \neg\alpha) \rightarrow (\alpha \rightarrow\beta)) | ; A3 |
| (2) | \{(\neg\beta\rightarrow \neg\alpha)\}\vdash (\alpha \rightarrow \beta) | ; RTD(1) |
Por lo tanto \{(\neg\beta\rightarrow \neg\alpha)\}\vdash (\alpha \rightarrow \beta)
Y en el otro sentido, la demostración se puede obtener desde el siguiente razonamiento:
| (1) | \neg\neg\alpha \dashv \vdash \alpha | ; DN |
| (2) | \vdash (\neg\neg \alpha \rightarrow \alpha) | ; TD(1) |
| (3) | \neg\neg\beta \dashv \vdash \beta | ; DN |
| (4) | \vdash (\beta \rightarrow \neg\neg \beta) | ; TD(3) |
| (5) | \{(\alpha \rightarrow \beta)\}\vdash (\neg\neg \alpha \rightarrow \alpha) | ; Mon(2) |
| (6) | \{(\alpha \rightarrow \beta)\}\vdash (\alpha \rightarrow \beta) | ; Pre |
| (7) | \{(\alpha \rightarrow \beta)\}\vdash (\neg\neg \alpha \rightarrow\beta) | ; SH(5,6) |
| (8) | \{(\alpha \rightarrow \beta)\} \vdash (\beta \rightarrow \neg\neg \beta) | ; Mon(4) |
| (9) | \{(\alpha \rightarrow \beta)\}\vdash (\neg\neg \alpha \rightarrow \neg\neg \beta) | ; SH(7,8) |
| (10) | \vdash (\neg\neg \alpha \rightarrow \neg\neg \beta) \rightarrow (\neg \beta \rightarrow \neg \alpha ) | ; A3 |
| (11) | \{(\alpha \rightarrow \beta)\}\vdash ((\neg\neg \alpha \rightarrow \neg\neg \beta) \rightarrow (\neg \beta \rightarrow \neg \alpha )) | ; Mon(10) |
| (11) | \{(\alpha \rightarrow \beta)\}\vdash (\neg \beta \rightarrow \neg \alpha ) | ; SH(10;11) |
Por lo tanto \{(\alpha \rightarrow \beta)\}\vdash (\neg \beta \rightarrow \neg \alpha )
Por lo tanto, de los dos razonamientos anteriores se tiene que
(\alpha \rightarrow \beta) \dashv\vdash (\neg \beta \rightarrow \neg \alpha )
Para demostrar la segunda podemos hacer los siguientes dos razonamientos:
| (1) | \beta \dashv\vdash \neg\neg\beta | ; DN |
| (2) | \neg\neg\neg\alpha \dashv\vdash \neg\alpha | ; DN |
| (3) | \vdash (\beta \rightarrow \neg\neg\beta) | ; TD(1) |
| (4) | \vdash (\neg\neg\neg\alpha \rightarrow \neg\alpha) | ; TD(2) |
| (5) | \{(\neg\alpha \rightarrow \beta)\}\vdash (\neg\alpha \rightarrow \beta) | ; Pre |
| (6) | \{(\neg\alpha \rightarrow \beta)\}\vdash (\beta \rightarrow \neg\neg\beta) | ; Mon(3) |
| (7) | \{(\neg\alpha \rightarrow \beta)\}\vdash (\neg\neg\neg\alpha \rightarrow \neg\alpha) | ; Mon(4) |
| (8) | \{(\neg\alpha \rightarrow \beta)\}\vdash (\neg\alpha \rightarrow \neg\neg\beta) | ; SH(5,6) |
| (9) | \{(\neg\alpha \rightarrow \beta)\}\vdash (\neg\neg\neg\alpha \rightarrow \neg\neg\beta) | ; SH(7,8) |
| (10) | \vdash (\neg\neg\neg\alpha \rightarrow \neg\neg\beta) \rightarrow (\neg\beta \rightarrow \neg\neg\alpha) | ; A3 |
| (11) | \{(\neg\alpha \rightarrow \beta)\}\vdash ((\neg\neg\neg\alpha \rightarrow \neg\neg\beta) \rightarrow (\neg\beta \rightarrow \neg\neg\alpha)) | ; Mon(10) |
| (12) | \{(\neg\alpha \rightarrow \beta)\}\vdash (\neg\beta \rightarrow \neg\neg\alpha) | ; MP(9,11) |
| (13) | \neg\neg \alpha \dashv \vdash \alpha | ; DN |
| (14) | \vdash (\neg\neg \alpha\rightarrow \alpha) | ; TD(13) |
| (15) | \{(\neg\alpha \rightarrow \beta)\} \vdash (\neg\neg \alpha\rightarrow \alpha) | ; Mon(14) |
| (16) | \{(\neg\alpha \rightarrow \beta)\} \vdash(\neg\beta \rightarrow \alpha) | ; SH(12,15) |
Por lo tanto \{(\neg\alpha \rightarrow \beta)\} \vdash(\neg\beta \rightarrow \alpha)
Ahora falta hacer la demostración en el sentido inverso. Lo podemos hacer a través del siguiente razonamiento:
| (1) | \alpha \dashv \vdash \neg\neg\alpha | ; DN |
| (2) | \vdash (\alpha \rightarrow \neg\neg\alpha) | ; TD(1) |
| (3) | \{(\neg\beta\rightarrow\alpha)\}\vdash (\neg\beta\rightarrow\alpha) | ; Pre |
| (4) | \{(\neg\beta\rightarrow\alpha)\}\vdash (\alpha \rightarrow \neg\neg\alpha) | ; Mon(2) |
| (5) | \{(\neg\beta\rightarrow\alpha)\}\vdash (\neg\beta\rightarrow\neg\neg\alpha) | ; SH(3,4) |
| (6) | \vdash (\neg\beta\rightarrow\neg\neg\alpha)\rightarrow (\neg\alpha \rightarrow \beta) | ; A3 |
| (7) | \{(\neg\beta\rightarrow\alpha)\}\vdash ((\neg\beta\rightarrow\neg\neg\alpha)\rightarrow (\neg\alpha \rightarrow \beta)) | ; Mon(6) |
| (8) | \{(\neg\beta\rightarrow\alpha)\}\vdash (\neg\alpha \rightarrow \beta) | ; MP(5,7) |
Por lo tanto \{(\neg\beta\rightarrow\alpha)\}\vdash (\neg\alpha \rightarrow \beta)
Finalmente, de estos dos razonamientos se concluye que (\neg\beta\rightarrow\alpha) \dashv \vdash (\neg\alpha \rightarrow \beta) , que es lo que se quería demostar.
La última equivalencia quedará como ejercicio. Para demostrarla puedes guiarte con las dos demostraciones que ya he dado. Esta es la mejor formda que existe para dominar las técnicas de deducción.