Esto debe ser clave y no logro entenderlo.
¿Se pueden agregar hipótesis como yo quiera? ¿Podría agregar la premisa \( p \) en la línea 64 y \( \neg p \) en la 119? ¿Bajo qué condiciones (si las hubiera) se pueden agregar hipótesis i.e. en nuestro caso, podría haber "sacado de la manga" las proposiciones \( Lc \), \( Cc \) y \( Mc \) y ponerlas donde yo quiera?
Por último, no entiendo "Para que la deducción sea válida en la última línea debes haber descartado todas las premisas que hayas introducido", ¿a qué te referís con "Descartar": haber operado con ellas al menos 1 vez?
Puedes agregar todas las hipótesis que quieras en mitad de la demostración (sí, cualquier fórmula que se te ocurra), pero para que sea válida la demostración las debes haber descartado todas al final. ¿Cómo se descartan las hipótesis? Mediante la aplicación o bien de la regla de introducción del implicador, o bien de la regla de eliminación de la disyunción.
Para demostrar una implicación como \( \phi \rightarrow \psi \) en deducción natural, lo que debes hacer es asumir \( \phi \) como hipótesis, a partir de ahí demostrar \( \psi \) (usando quizás las premisas de las que partes u otras fórmulas ya demostradas), y finalmente aplicar la regla de introducción del implicador para descartar la hipótesis y obtener una prueba de \( \phi \rightarrow \psi \).
De manera parecida, si tienes una disyunción \( \phi \vee \psi \) y quieres probar otra fórmula \( \chi \), puedes hacerlo suponiendo como hipótesis \( \phi \) y probando \( \chi \), y por otro lado suponiendo como hipótesis \( \psi \) y probando \( \chi \) (hay que usar dos ramas, es decir, no puedes suponer \( \phi \) y \( \psi \) a la vez). Entonces, usando la regla de eliminación del disyuntor obtienes una prueba de \( \chi \), sin hipótesis.
De todas maneras los detalles pueden cambiar según la presentación de la deducción natural. Por ejemplo, noisok no usa la eliminación de la disyunción en este sentido, aunque esencialmente es lo mismo. Fíjate lo que hace en las líneas 13-18 de su demostración: asume como hipótesis cada término de la disyunción \( Ac \vee Cc \vee Lc \) por separado y en los tres casos prueba que \( Cc \) se cumple. Él usa primero introducción del implicador y luego la regla del dilema para obtener una prueba de \( Ac \vee Cc \vee Lc \rightarrow Cc \). Con la versión de la eliminación de la disyunción que he dado antes, lo que harías es asumir \( Ac \) y probar \( Cc \), asumir \( Cc \) y probar \( Cc \) y asumir \( Lc \) y probar \( Cc \) y usar eliminación de la disyunción para obtener una prueba (sin hipótesis) de \( Cc \). (Si quieres ser estricto de hecho deberías usar dos veces eliminación de la disyunción, porque estrictamente hablando la regla vale para una disyunción de dos fórmulas, no de tres.)
En fin, la verdad es que hablar de los detalles concretos es un rollo, y como ya he dicho varias veces depende de qué versión concreta de deducción natural te hayan explicado o hayas estudiado. Si quieres detalles completos primero habría que ponerse de acuerdo en las reglas exactas que podemos usar. Pero espero que al menos se haya entendido la idea y la filosofía de la deducción natural, asumir hipótesis y descartarlas.
Pero a priori no conocíamos la demostración, así que no podíamos saber que necesitábamos de \( Pc \) y \( Tc \).
No, claro. Lo que digo es que puedes intentar de todas las formas que quieras dar una demostración de \( \exists x (Px \vee Tx \rightarrow Cx) \) a partir de las premisas, que te será totalmente imposible dar una demostración válida. Y la forma de demostrar que es imposible dar una demostración válida de \( \exists x(Px \vee Tx \rightarrow Cx) \) es dar un contraejemplo: construir un modelo donde las premisas sean verdaderas pero \( \exists x(Px \vee Tx \rightarrow Cx) \) sea falsa.
No entiendo por qué debe haber diferencias entre \( \vee \) y \( \wedge \), si ambas forman un sistema dual, como si \( p\wedge q=q\wedge p \) entonces la dual también vale i.e. \( p\vee q=q\vee p \). Es decir no entendí la frase "El problema es que si tienes \( Pc \vee Tc \) para demostrar \( Pc \vee Tc \rightarrow Cc \) necesitas primero asumir \( Pc \) y probar \( Cc \) (únicamente a partir de \( Pc \)) y luego asumir \( Tc \) y probar \( Cc \) (únicamente a partir de \( Cc \))".
Espero que ahora se entienda mejor la frase: lo que digo es que hay que usar la regla de eliminación de la disyunción para probar \( Cc \) a partir de \( Pc \vee Tc \).
Por otro lado, hay que tener cuidado con el tema de la dualidad. Desde luego que haya una dualidad entre \( \wedge \) y \( \vee \) no quiere decir para nada que si puedes demostrar una fórmula \( \phi \) entonces puedes demostrar la fórmula resultante de cambiar \( \wedge \) por \( \vee \) en \( \phi \). Por ejemplo, \( p \vee \neg p \) es una tautología, luego se puede demostrar, pero \( p \wedge \neg p \) no.
Fíjate que esto tiene perfecto sentido, intuitivamente: uno espera ser capaz de demostrar más cosas teniendo dos fórmulas de partida, que si solamente tienes una de las fórmulas (y además no sabe cuál de ellas, de manera que tienes que dar una demostración para cada una por separado).
La expresión de la dualidad entre \( \wedge \) y \( \vee \) son las reglas de De Morgan, y una consecuencia es que si \( \phi, \psi \) son fórmulas donde no aparecen implicaciones, entonces \( \phi \rightarrow \psi \) es equivalente a \( \psi^* \rightarrow \phi^* \), donde la estrella indica intercambiar \( \wedge \) y \( \vee \) (y si son fórmulas de primer orden también \( \forall \) y \( \exists \)). Además esto solo sirve para demostraciones sin premisas, si tienes premisas éstas también deben cambiar.
Seguramente tiene que ver con Gödel y su teorema
pero no logro identificar la similitud entre el teorema de adecuación y el de completitud. ¿Acaso uno implica al otro y viceversa?
La única relación con Gödel es que Gödel fue el primero en demostrar el teorema de completitud. Si estás pensando en los famosos teoremas de incompletitud de Gödel, no, no tienen mucho que ver.
Quizás sea mejor enunciarlo de una manera más formal. Si \( \phi \) es una fórmula y \( \Gamma \) es un conjunto de fórmulas, escribimos \( \Gamma \vdash \phi \) para denotar que existe una demostración de \( \phi \) con premisas en \( \Gamma \). De manera parecida, escibimos \( \Gamma \models \phi \) para denotar que en todo modelo donde cada fórmula de \( \Gamma \) es verdadera, \( \phi \) también lo es.
Fíjate que la relación \( \Gamma \vdash \phi \) es una relación puramente sintáctica, es decir, lo único que afirma es que existe un procedimiento mecánico para derivar \( \phi \) a partir de fórmulas en \( \Gamma \) usando una serie de reglas. Por el contrario, \( \Gamma \models \phi \) es una relación semántica, es decir, es lo que entendemos cuando decimos \( \phi \) se sigue de \( \Gamma \): que en toda situación que nos podamos imaginar en la que todas las fórmulas de \( \Gamma \) sean verdaderas, también es verdadera \( \phi \).
En matemáticas, o en lógica en general, lo que nos interesa realmente es la relación \( \Gamma \models \phi \), que es la que lleva contenido semántico. Pero comprobar que algo es verdadero en todos los modelos posibles es normalmente muy difícil, pues primero habría que saber construir todos los modelos donde un conjunto de fórmulas es verdadero, y esto muchas veces no es factible, pues hay infinitos modelos. Además muchas veces no es nada fácil saber si una fórmula es verdadera o no en un modelo dado, porque implica hacer infinitas comprobaciones.
Entonces nos inventamos una relación \( \Gamma \vdash \phi \) que es finitaria: una demostración de \( \phi \) a partir de \( \Gamma \) es un objeto finito, involucra un número finito de fórmulas. Pero por supuesto, estas demostraciones formales serían completamente inútiles si la relación \( \vdash \) no tuviera nada que ver con \( \models \). Fíjate que las reglas de la lógica ya están hechas pensando en la semántica. Cuando uno dice que de la fórmula \( p \wedge q \) se puede obtener \( p \) (que es una regla formal, es como si te digo que hay una reglaque dice que de la cadena de símbolos \( a*b \) se puede obtener \( a \)) está ya pensando en que en un modelo \( p \wedge q \) se interpretará como "tanto \( p \) como \( q \) son verdaderas en el modelo".
Entonces, la pregunta clave es ¿cuál es la relación entre \( \vdash \) y \( \models \)?
Aquí entran nuestros dos teoremas.
El teorema de adecuación dice que \( \Gamma \vdash \phi \) implica \( \Gamma \models \phi \). Es decir, esto nos dice esencialmente que nunca vamos a poder demostrar cosas falsas. Si existe una demostración de \( \phi \) a partir de fórmulas en \( \Gamma \), en cualquier modelo posible donde las fórmulas de \( \Gamma \) sean verdaderas, \( \phi \) también lo será.
Este teorema es bastante fácil de demostrar: simplemente basta comprobar que para cada regla de tu cálculo deductivo (por ejemplo, deducción natural), si las premisas de la regla son verdadera en un modelo, entonces la conclución de la regla también lo es.
El teorema de adecuación es simplemente una comprobación de que tu cálculo deductivo es "correcto". Si te inventas un cálculo deductivo y no cumple el teorema de adecuación, ya lo puedes tirar, pues si te permite demostrar cosas falsas no sirve para nada.
El teorema de completitud es mucho más interesante, Dice que si \( \Gamma \models phi \) entonces \( \Gamma \vdash \phi \). Esto es, que todo lo que es verdadero (en todo modelo) es demostrable. O usando el contrarecíproco, que si una fórmula no se puede demostrar, entonces existe algún modelo en el que es falsa. Este teorema es mucho más profundo, y su demostración es no trivial, a diferencia del teorema de adecuación.
Otro tema es que los que han puesto el problema nos podrían haber engañado y haber puesto varias opciones correctas, es decir, varias fórmulas que se deducen de las premisas que te dan. Para descartar este caso, en efecto hay que construir modelos donde las premisas sean verdaderas pero las conclusiones falsas. Yo lo hice más arriba con la fórmula de 1) en respuesta a feriva. Puedes probar a construir contraejemplos parecidos para 3) y 4). Si no me equivoco lo puedes hacer con un modelo con un único elemento, como el que usé yo para 1).
Bajo el supuesto de que hay más de 1 opción correcta, ¿no es que la tesis es lo mismo que la conclusión? O sea, no entiendo por qué decís "fórmulas que se deducen de las premisas" (entendiendo "fórmula válidas" como "tesis verdaderas") y luego "conclusiones falsas" (entendidas como "tesis falsas")
Esto no lo entiendo. Yo lo único que decía es que si no sabes de entrada que solamente una opción es correcta, para demostrar por ejemplo que no existe ninguna demostración de \( \exists x(Tx \vee Px \rightarrow Cx) \) a partir de las cuatro premisas que te dan, hay que constuir un modelo donde las premisas sean verdaderas y la fórmula \( \exists x(Tx \vee Px \rightarrow Cx) \) falsa.
En fin, espero que el rollo que te he soltado te sirva para aclararte un poco, y no para liarte más todavía.