#LyX 1.3 created this file. For more info see http://www.lyx.org/ \lyxformat 221 \textclass article \begin_preamble \usepackage{color} \usepackage{html} \usepackage{fitch} \usepackage{ae} \pagecolor{white} \end_preamble \language spanish \inputencoding auto \fontscheme default \graphics default \paperfontsize default \spacing single \papersize Default \paperpackage a4 \use_geometry 0 \use_amsmath 0 \use_natbib 0 \use_numerical_citations 0 \paperorientation portrait \secnumdepth 3 \tocdepth 3 \paragraph_separation indent \defskip medskip \quotes_language english \quotes_times 2 \papercolumns 1 \papersides 1 \paperpagestyle default \layout Title Introducción a la deducción natural \layout Author Daniel Clemente Laboreo \layout Date Agosto 2004 (revisado en Mayo 2005) \layout Standard \begin_inset LatexCommand \tableofcontents{} \end_inset \layout Section Antes de nada... \layout Standard Este tutorial está disponible en varios idiomas: \begin_inset ERT status Collapsed \layout Standard \backslash htmladdnormallinkfoot{español}{http://www.danielclemente.com/logica/dn.html} \backslash htmladdnormallink{(y PDF)}{http://www.danielclemente.com/logica/dn.pdf}, \backslash htmladdnormallinkfoot{esperanto}{http://www.danielclemente.com/logica/dn.eo.html} \backslash htmladdnormallink{(y PDF)}{http://www.danielclemente.com/logica/dn.eo.pdf}, \backslash htmladdnormallinkfoot{catalán}{http://www.danielclemente.com/logica/dn.ca.html} \backslash htmladdnormallink{(y PDF)}{http://www.danielclemente.com/logica/dn.ca.pdf}, e \backslash htmladdnormallinkfoot{inglés}{http://www.danielclemente.com/logica/dn.en.html} \backslash htmladdnormallink{(y PDF)}{http://www.danielclemente.com/logica/dn.en.pdf}. \layout Standard \layout Standard \end_inset \layout Standard Las fórmulas quedan mucho más bonitas en el PDF, pero si no te es posible usarlo, mira las páginas en HTML. \layout Subsection Quién soy \layout Standard Me llamo Daniel Clemente Laboreo, tengo 19 años (en el 2004), vivo en Gavà (Barcelona), y estudio informática en la \emph on FIB \emph default ( \emph on UPC \emph default ). Ahí, en la asignatura de \emph on ILO \emph default ( \emph on Introducción a la lógica \emph default ), es donde me enseñaron este tema. \layout Subsection Por qué escribo esto \layout Standard Por varias razones: \layout Itemize Hay un hueco importante al buscar \begin_inset Quotes eld \end_inset \emph on deducción natural \emph default \begin_inset Quotes erd \end_inset en Google. Yo mismo necesité estudiarlo antes del examen y no encontré nada útil que me ayudara. Lo mismo con \emph on natural deduction \emph default o \emph on nd \emph default : había algunos tutoriales, pero ninguno estaba bien hecho: o no se entendía, o los caracteres especiales no se veían bien, o daban todo por entendido. Así que me propuse aportar este tutorial que seguro que ayudará a mucha gente. \layout Itemize Es un tema que me gusta y se me da bien. \layout Itemize Hace pensar. Quizás no tenga mucha utilidad práctica, pero realmente hay que esforzarse y pasarse un buen rato para resolver algunos problemas muy simples. \layout Itemize Confieso que escribí esto para aprender a procesar textos con \begin_inset ERT status Collapsed \layout Standard \backslash LaTeX \end_inset . Cuesta mucho trabajo aprender, pero los resultados hacen que valga la pena. \layout Subsection A quién va dirigido \layout Standard En principio, a cualquiera que le guste la lógica, la informática, o las matemáticas. Quien quiera prepararse para las asignaturas de lógica de la universidad también ganará algunos conceptos útiles. \layout Standard Esto no pretende ser un curso completo sobre deducción natural, sino que seguirá siendo una introducción. Cuando aprenda más, la corregiré si hace falta, pero no le añadiré más secciones (las haría en documentos aparte). \layout Subsection Licencia \layout Standard Todo el documento es \begin_inset ERT status Collapsed \layout Standard \backslash htmladdnormallinkfoot{FDL}{http://www.gnu.org/licenses/fdl.html} \end_inset (como la GPL del software libre, pero para documentos). El código fuente está hecho con LyX ( \begin_inset ERT status Collapsed \layout Standard \backslash htmladdnormallinkfoot{dn.lyx}{http://www.danielclemente.com/logica/dn.lyx} \end_inset ), y usa las macros \begin_inset ERT status Collapsed \layout Standard \backslash htmladdnormallink{fitch.sty}{http://www.danielclemente.com/logica/fitch.sty} \end_inset de Johan W. Klüwer. He usado el programa \begin_inset ERT status Collapsed \layout Standard \backslash htmladdnormallink{latex2html}{http://www.danielclemente.com/linux/l2h.html} \end_inset (ligeramente parcheado) para hacer la web. \layout Standard Lo puedes modificar o traducir a otros idiomas que conozcas bien, además de poder redistribuirlo, venderlo, y muchas más cosas. \layout Section Conceptos básicos \layout Standard En esto de la lógica hay que tener perfectamente claro el significado de cada palabra. Me limitaré a recordar qué son y cómo se leen los símbolos raros que se usan en este documento. \layout Subsection Formalización \layout Standard \emph on Formalizar \emph default quiere decir escribir una expresión de una manera estándar que todos entiendan. \layout Standard Al trabajar con algoritmos lógicos, podemos estar pensando todo el rato en frases como \begin_inset Quotes eld \end_inset \emph on Si llueve y no tengo paraguas, entonces me mojo \emph default \begin_inset Quotes erd \end_inset . Se puede, pero es muy largo. Es mejor representar cada acción con una letra, y escribir la frase usando esas letras y palabras sencillas como \emph on y \emph default , \emph on o \emph default , \emph on no \emph default , o \emph on entonces \emph default . \layout Standard Ejemplo. Tenemos este vocabulario: \layout Standard \begin_inset Formula $L$ \end_inset : \emph on llover \layout Standard \begin_inset Formula $P$ \end_inset : \emph on tener paraguas \layout Standard \begin_inset Formula $M$ \end_inset : \emph on mojarse \layout Standard La frase \begin_inset Quotes eld \end_inset \emph on Si llueve y no tengo paraguas, entonces me mojo \emph default \begin_inset Quotes erd \end_inset queda mejor como \begin_inset Quotes eld \end_inset \emph on si \begin_inset Formula $L$ \end_inset y no \begin_inset Formula $P$ \end_inset , entonces \begin_inset Formula $M$ \end_inset \emph default \begin_inset Quotes erd \end_inset . \layout Standard En la deducción natural se usará sólo la versión de las letras, con estas condiciones: \layout Itemize Las letras (que se llaman \emph on letras proposicionales \emph default ) van en mayúsculas. \layout Itemize Se suelen usar las letras \begin_inset Formula $P$ \end_inset , \begin_inset Formula $Q$ \end_inset , \begin_inset Formula $R$ \end_inset , \begin_inset Formula $S$ \end_inset , ... aunque se puede usar cualquiera. \layout Itemize Se usan unos símbolos especiales para los operadores \emph on y \emph default , \emph on o \emph default , \emph on no \emph default e \emph on implicación \emph default . \layout Subsection Símbolos usados \layout Standard Para expresar las relaciones entre una acción y otra, hay varios dibujitos internacionales. Los operadores básicos que tienes que conocer son \begin_inset Formula $\vee$ \end_inset , \begin_inset Formula $\wedge$ \end_inset , \begin_inset Formula $\neg$ \end_inset , \begin_inset Formula $\Rightarrow$ \end_inset . Los otros son más complicados, pero los he mostrado todos para cuando haya que consultarlos. \layout Standard \begin_inset Tabular \begin_inset Text \layout Standard \series bold Símbolo \end_inset \begin_inset Text \layout Standard \series bold Se lee... \end_inset \begin_inset Text \layout Standard \series bold Descripción \end_inset \begin_inset Text \layout Standard \begin_inset Formula $\vee$ \end_inset \end_inset \begin_inset Text \layout Standard \emph on o \end_inset \begin_inset Text \layout Standard \begin_inset Formula $A\vee B$ \end_inset se cumple cuando uno de los dos, o los dos, es cierto. \end_inset \begin_inset Text \layout Standard \begin_inset Formula $\wedge$ \end_inset \end_inset \begin_inset Text \layout Standard \emph on y \end_inset \begin_inset Text \layout Standard Para que \begin_inset Formula $A\wedge B$ \end_inset se cumpla, tanto \begin_inset Formula $A$ \end_inset como \begin_inset Formula $B$ \end_inset tienen que ser ciertos. \end_inset \begin_inset Text \layout Standard \begin_inset Formula $\neg$ \end_inset \end_inset \begin_inset Text \layout Standard \emph on no \end_inset \begin_inset Text \layout Standard \begin_inset Formula $\neg A$ \end_inset se cumple sólo cuando \begin_inset Formula $A$ \end_inset es falso. \end_inset \begin_inset Text \layout Standard \begin_inset Formula $\Rightarrow$ \end_inset \end_inset \begin_inset Text \layout Standard \emph on implica \end_inset \begin_inset Text \layout Standard Indica una consecuencia. La expresión \begin_inset Formula $A\Rightarrow B$ \end_inset dice que cuando \begin_inset Formula $A$ \end_inset se cumple, \begin_inset Formula $B$ \end_inset también. Además, \begin_inset Formula $A\Rightarrow B$ \end_inset es cierto excepto para el caso \begin_inset Formula $A$ \end_inset cierto y \begin_inset Formula $B$ \end_inset falso. Para entenderlo, piensa en un \begin_inset Formula $A$ \end_inset que implique \begin_inset Formula $B$ \end_inset y pregúntate: \emph on ¿es posible que \begin_inset Formula $A$ \end_inset sea cierto y \begin_inset Formula $B$ \end_inset no? \emph default Tampoco te preocupes mucho por esto, no es importante ahora. \end_inset \begin_inset Text \layout Standard \begin_inset Formula $\Longleftrightarrow$ \end_inset \end_inset \begin_inset Text \layout Standard \emph on si y sólo si \end_inset \begin_inset Text \layout Standard \begin_inset Formula $A\Longleftrightarrow B$ \end_inset equivale a \begin_inset Formula $(A\Rightarrow B)\wedge(B\Rightarrow A)$ \end_inset . Quiere decir que de \begin_inset Formula $A$ \end_inset se puede deducir \begin_inset Formula $B$ \end_inset y viceversa, o sea, que son equivalentes. \end_inset \begin_inset Text \layout Standard \begin_inset Formula $\square$ \end_inset \end_inset \begin_inset Text \layout Standard \emph on falso \end_inset \begin_inset Text \layout Standard El cuadradito vacío representa a \emph on falso \emph default (el \emph on 0 \emph default binario). Más técnicamente, representa a \begin_inset Formula $\{\}$ \end_inset . \end_inset \begin_inset Text \layout Standard \begin_inset Formula $\blacksquare$ \end_inset \end_inset \begin_inset Text \layout Standard \emph on cierto \end_inset \begin_inset Text \layout Standard El cuadradito lleno representa a \emph on cierto \emph default (el \emph on 1 \emph default binario). Más técnicamente, representa a \begin_inset Formula $\{<>\}$ \end_inset . \end_inset \begin_inset Text \layout Standard \begin_inset Formula $\exists$ \end_inset \end_inset \begin_inset Text \layout Standard \emph on existe... \end_inset \begin_inset Text \layout Standard \begin_inset Formula $\exists xPx$ \end_inset se lee \emph on existe un \begin_inset Formula $x$ \end_inset tal que \begin_inset Formula $P$ \end_inset de \begin_inset Formula $x$ \end_inset \emph default . Si en nuestro dominio podemos encontrar un elemento (o más) tal que se cumpla la propiedad \begin_inset Formula $P$ \end_inset aplicada a ese elemento, la fórmula es cierta. \end_inset \begin_inset Text \layout Standard \begin_inset Formula $\forall$ \end_inset \end_inset \begin_inset Text \layout Standard \emph on para todo... \end_inset \begin_inset Text \layout Standard \begin_inset Formula $\forall xPx$ \end_inset se lee \emph on para todo \begin_inset Formula $x$ \end_inset , \begin_inset Formula $P$ \end_inset de \begin_inset Formula $x$ \end_inset \emph default . Si todos los elementos con los que trabajamos cumplen la propiedad \begin_inset Formula $P$ \end_inset , entonces la fórmula es cierta. \end_inset \begin_inset Text \layout Standard \begin_inset Formula $\vdash$ \end_inset \end_inset \begin_inset Text \layout Standard \emph on entonces \end_inset \begin_inset Text \layout Standard \begin_inset Formula $\vdash$ \end_inset es el símbolo del \emph on secuente \emph default , que es la forma de decir \begin_inset Quotes eld \end_inset \emph on cuando se cumple todo esto de la izquierda pasa también lo de la derecha \emph default \begin_inset Quotes erd \end_inset . Hay secuentes válidos, como \begin_inset Formula $P\wedge Q\vdash P$ \end_inset o como \begin_inset Formula $P\Rightarrow Q,\ Q\Rightarrow R,\ P\vdash P\wedge R$ \end_inset . También los hay inválidos, como \begin_inset Formula $P\Rightarrow Q,\ \neg P\vdash\neg Q$ \end_inset . El objetivo de la deducción natural es demostrar que un secuente es válido. \end_inset \begin_inset Text \layout Standard \begin_inset Formula $\vDash$ \end_inset \end_inset \begin_inset Text \layout Standard \emph on válido \end_inset \begin_inset Text \layout Standard \begin_inset Formula $\phi\vDash\varphi$ \end_inset sirve para decir que \begin_inset Formula $\varphi$ \end_inset es consecuencia lógica de \begin_inset Formula $\phi$ \end_inset , pero cuando se escribe \begin_inset Formula $A\vDash B$ \end_inset , lo que se quiere decir es que el secuente \begin_inset Formula $A\vdash B$ \end_inset es válido, o sea, que hemos podido demostrarlo de alguna manera, y ahora se considera cierto bajo cualquier interpretación de los símbolos de predicado. \end_inset \begin_inset Text \layout Standard \begin_inset Formula $\nvDash$ \end_inset \end_inset \begin_inset Text \layout Standard \emph on inválido \end_inset \begin_inset Text \layout Standard \begin_inset Formula $\phi\nvDash\varphi$ \end_inset quiere decir que \begin_inset Formula $\varphi$ \end_inset no es consecuencia lógica de \begin_inset Formula $\phi$ \end_inset . Si encuentras una serie de valores ( \emph on modelo \emph default ) que hacen cierto a \begin_inset Formula $\phi$ \end_inset pero falso a \begin_inset Formula $\varphi$ \end_inset , se demuestra la invalidez. \end_inset \begin_inset Text \layout Standard \begin_inset Formula $\Vdash$ \end_inset \end_inset \begin_inset Text \layout Standard \emph on satisfactible \end_inset \begin_inset Text \layout Standard Un conjunto de fórmulas es satisfactible si existe una serie de valores ( \emph on modelo \emph default ) que las haga ciertas a todas a la vez. \end_inset \begin_inset Text \layout Standard \begin_inset Formula $\nVdash$ \end_inset \end_inset \begin_inset Text \layout Standard \emph on insatisfactible \end_inset \begin_inset Text \layout Standard Un conjunto de fórmulas es insatisfactible si no hay ninguna combinación de variables ( \emph on modelo \emph default ) que las haga ciertas a todas a la vez. \end_inset \end_inset \layout Subsection Precedencia de los operadores \layout Standard Al ver una expresión, tienes que saber decir qué es. Por ejemplo: \begin_inset Formula $A\vee B\Rightarrow C$ \end_inset es una implicación (¡no una disyunción!), porque el \begin_inset Formula $\Rightarrow$ \end_inset es el último en evaluarse (tiene menor prioridad que el \begin_inset Formula $\vee$ \end_inset ). \layout Standard Aquí pongo los operadores, ordenados inversamente por prioridad. \layout Itemize \begin_inset Formula $\Longleftrightarrow$ \end_inset \layout Itemize \begin_inset Formula $\Rightarrow$ \end_inset \layout Itemize \begin_inset Formula $\vee$ \end_inset y \begin_inset Formula $\wedge$ \end_inset (tienen la misma prioridad) \layout Itemize \begin_inset Formula $\neg$ \end_inset \layout Standard Esto quiere decir que \begin_inset Formula $\neg$ \end_inset es el que más \begin_inset Quotes eld \end_inset \emph on se agarra \emph default \begin_inset Quotes erd \end_inset al símbolo que acompaña. Un ejemplo de cuándo y dónde hacen falta los paréntesis: \layout Standard \begin_inset Formula $P\vee\neg Q\Rightarrow R\wedge P\Longleftrightarrow\neg(R\vee S)\wedge A\Rightarrow B$ \end_inset es lo mismo que \begin_inset Formula $(\ (P\vee(\neg Q))\ \Rightarrow\ (R\wedge P)\ )\Longleftrightarrow(\ ((\neg(R\vee S))\wedge A)\Rightarrow B\ )$ \end_inset \layout Standard Tranquilo, no volveré a usar expresiones tan largas. \layout Section Deducción natural \layout Standard Ahora toca explicar qué es, cómo se hace, y si tiene alguna utilidad. \layout Subsection Para qué sirve \layout Standard La deducción natural sirve para intentar demostrar que un razonamiento es correcto ( \begin_inset Quotes eld \end_inset \emph on para comprobar la validez de un secuente \emph default \begin_inset Quotes erd \end_inset , dice la teoría). Ejemplo: \layout Standard Yo te digo: \begin_inset Quotes eld \end_inset \emph on En verano hace calor, y ahora estamos en verano, por eso hace calor \emph default \begin_inset Quotes erd \end_inset . Tú te pones a hacer cálculos, y respondes \begin_inset Quotes eld \end_inset \emph on Vale, puedo demostrar que el razonamiento que has hecho es correcto \emph default \begin_inset Quotes erd \end_inset . Para eso sirve la deducción natural. \layout Standard No siempre es tan fácil: \begin_inset Quotes eld \end_inset \emph on si suspendes una asignatura, la tienes que repetir. Si no estudias, la suspendes. Supongamos que no la repites. Entonces, o la estudias, o la suspendes, o las dos cosas a la vez \emph default \begin_inset Quotes erd \end_inset . Este razonamiento es válido y se puede demostrar con la deducción natural. \layout Standard Fíjate que no tienes que creerte ni entender lo que te cuente. Por ejemplo, yo te digo: \begin_inset Quotes eld \end_inset \emph on Los tiristores son pequeños y divertidos; un garbanzo no es pequeño, así que no es un tiristor \emph default \begin_inset Quotes erd \end_inset . Aunque no sepas de qué hablo o te parezca que es mentira o es una idiotez (que lo es), tienes que estar totalmente seguro de que el razonamiento es correcto. \layout Standard O sea, que, dada una suposición \begin_inset Quotes eld \end_inset \emph on si pasa esto entonces pasa esto otro \emph default \begin_inset Quotes erd \end_inset , la deducción natural permite decir \begin_inset Quotes eld \end_inset \emph on sí, así es \emph default \begin_inset Quotes erd \end_inset . En lenguaje lógico: si te dan un secuente \begin_inset Formula $A\vdash B$ \end_inset , puedes acabar concluyendo que es \begin_inset Formula $\vDash$ \end_inset ( \emph on válido \emph default ). Entonces se escribe \begin_inset Formula $A\vDash B$ \end_inset ( \begin_inset Formula $A$ \end_inset tiene como consecuencia a \begin_inset Formula $B$ \end_inset ). \layout Subsection Para qué no sirve \layout Standard No sirve para demostrar la \emph on invalidez \emph default de una suposición. Si digo \begin_inset Quotes eld \end_inset \emph on si es de día, no es de noche; y ahora es de día, por eso también es de noche \emph default \begin_inset Quotes erd \end_inset te podrás pasar un rato probando las reglas de la deducción natural, pero sin conseguir nada útil. Al cabo de un rato irás intuyendo que probablemente el razonamiento no sea válido, y es entonces cuando habría que probar otros métodos -que no son el de deducción natural- con el fin de demostrar la invalidez. Están explicados más adelante. \layout Standard O sea, que la deducción natural sirve sólo para demostrar la validez, pero no la invalidez. Qué pena, ¿no? \layout Standard Tampoco sirve para dar una buena respuesta a la pregunta \begin_inset Quotes eld \end_inset \emph on ¿Qué pasaría si...? \emph default \begin_inset Quotes erd \end_inset . Cuando piden demostrar la validez de \begin_inset Formula $A\vdash B$ \end_inset , hay que pensar en qué cosas pasarían si se cumpliera \begin_inset Formula $A$ \end_inset , y si descubrimos que una de esas cosas es \begin_inset Formula $B$ \end_inset , ya hemos acabado. Pero nunca podremos dar una lista finita de todas estas cosas. \layout Subsection Funcionamiento \layout Standard Se pide demostrar la validez de \begin_inset Formula $\Gamma\vdash S$ \end_inset , donde \begin_inset Formula $\Gamma$ \end_inset (se lee \emph on gamma \emph default ) es un grupo de fórmulas separadas por comas, y \begin_inset Formula $S$ \end_inset es una sola fórmula. \layout Standard Partimos de que todas las fórmulas de \begin_inset Formula $\Gamma$ \end_inset son ciertas, y, mediante 9 reglas concretas, podemos ir descubriendo qué más cosas son ciertas. Nuestra intención es ver que \begin_inset Formula $S$ \end_inset es cierta; una vez conseguido ya podemos acabar. \layout Standard A veces no podremos sacar verdades de ningún lado, y habrá que hacer suposicione s: \begin_inset Quotes eld \end_inset \emph on bueno, no estoy seguro de que \begin_inset Formula $A\wedge B$ \end_inset sea cierto siempre, pero si se cumple \begin_inset Formula $C$ \end_inset , seguro que lo es \emph default \begin_inset Quotes erd \end_inset . Entonces ya hemos descubierto otra cosa cierta: que \begin_inset Formula $C\Rightarrow A\wedge B$ \end_inset . \layout Standard Como ves, siempre hay que pensar hacia dónde queremos llegar, porque de otra forma podríamos adivinar un montón de cosas que son ciertas pero que no nos están pidiendo. Por ejemplo, con \begin_inset Formula $A\vee B,\ \neg A\vdash B$ \end_inset tenemos que llegar a que es cierto \begin_inset Formula $B$ \end_inset . Podemos descubrir que \begin_inset Formula $\neg(A\wedge B)$ \end_inset , \begin_inset Formula $A\vee B\vee C$ \end_inset , \begin_inset Formula $(A\vee B)\Rightarrow\neg A$ \end_inset , y muchas más cosas, pero lo que nos interesa es \begin_inset Formula $B$ \end_inset y ya está. O sea, que si no vas por el camino correcto, te puedes hacer un lío. \layout Subsection Notación \layout Standard Hay varias formas de escribir los esquemas de deducción natural. Yo usaré el estilo Fitch, porque es el que me enseñaron, es fácil de entender, y ocupa poco espacio. Es algo así: \layout Standard \begin_inset ERT status Collapsed \layout Standard \backslash [ \backslash begin{fitch} \layout Standard P \backslash Rightarrow Q \backslash \backslash \layout Standard Q \backslash Rightarrow R \backslash \backslash \layout Standard \backslash fh P & H \backslash \backslash \layout Standard \backslash fa Q & E$ \backslash Rightarrow$ 1,3 \backslash \backslash \layout Standard \backslash fa R & E$ \backslash Rightarrow$ 2,4 \backslash \backslash \layout Standard \backslash fa Q \backslash wedge R & I$ \backslash wedge$ 4,5 \backslash \backslash \layout Standard P \backslash Rightarrow Q \backslash wedge R & I$ \backslash Rightarrow$ 3,6 \layout Standard \backslash end{fitch} \backslash ] \end_inset \layout Standard Con esto se ha demostrado la validez de \begin_inset Formula $P\Rightarrow Q,\ Q\Rightarrow R\vdash P\Rightarrow Q\wedge R$ \end_inset . \layout Standard El esquema se va haciendo línea por línea, de arriba a abajo. Los números de la izquierda indican el número de línea, y siempre van en orden. \layout Standard Las primeras líneas contienen cada una de las fórmulas que hay en la parte izquierda del secuente. En este caso son dos: \begin_inset Formula $P\Rightarrow Q$ \end_inset y \begin_inset Formula $Q\Rightarrow R$ \end_inset . A partir de éstas tenemos que llegar a \begin_inset Formula $P\Rightarrow Q\wedge R$ \end_inset . \layout Standard En cada línea apuntamos qué cosa hemos descubierto que es cierta, y a la derecha explicamos de qué forma la hemos encontrado. Esos símbolos de la derecha (las \begin_inset Formula $E$ \end_inset e \begin_inset Formula $I$ \end_inset ) son las siglas que identifican a cada una de las 9 reglas. Por ejemplo, aquí salen la \emph on eliminación de la implicación \emph default ( \begin_inset Formula $E\Rightarrow$ \end_inset ), la \emph on introducción de la conjunción \emph default ( \begin_inset Formula $I\wedge$ \end_inset ), y la \emph on introducción de la implicación \emph default ( \begin_inset Formula $I\Rightarrow$ \end_inset ). Los numeritos que les acompañan dan información sobre de dónde se han sacado las fórmulas necesarias para aplicar la regla. Son números de línea, o sea, que para aplicar una regla hay que basarse en lo que ya hemos escrito. \layout Standard Por último, esa raya vertical que va de la línea 3 a la 6 es una hipótesis (por eso se ha puesto una \begin_inset Formula $H$ \end_inset a la derecha). Todo lo que hay ahí dentro no es cierto siempre, sino sólo cuando se cumple \begin_inset Formula $P$ \end_inset (el encabezamiento de la hipótesis, en la línea 3). Por eso, todo lo que hagamos dentro de la hipótesis no lo podemos usar fuera, porque no siempre se cumple. \layout Standard El procedimiento acaba cuando descubrimos que es cierto lo de la derecha del secuente, en este caso \begin_inset Formula $P\Rightarrow Q\wedge R$ \end_inset (sale en la última línea). \layout Section Las reglas \layout Standard Aquí están enunciadas y explicadas las nueve reglas básicas que se usan en la deducción natural. Indican cuándo y cómo podemos añadir nuevas fórmulas que sigan siendo ciertas. \layout Standard Los ejemplos (explicados) están en la siguiente sección. \layout Subsection Iteración \layout Standard Esta es una regla muy sencilla: \layout Standard \begin_inset ERT status Collapsed \layout Standard \backslash [ \backslash begin{fitch*} \layout Standard n & A \backslash \backslash \layout Standard \backslash hline \layout Standard & A & IT n \layout Standard \backslash end{fitch*} \backslash ] \end_inset \layout Standard Vale, escrito así queda muy raro, pero es para que sirva como definición. Lo que hay aquí arriba quiere decir que si en la línea número \begin_inset Formula $n$ \end_inset tenemos escrito \begin_inset Formula $A$ \end_inset (sea la expresión que sea) entonces podemos volver a escribir \begin_inset Formula $A$ \end_inset en la línea actual, y para justificarlo tenemos que escribir a la derecha \begin_inset Formula $IT\ n$ \end_inset . \layout Standard ¿Que para qué sirve esto? Pues de momento para nada, pero tendrá su utilidad cuando empecemos a hacer lo de las hipótesis. Como una hipótesis es \emph on cerrada \emph default , todas las reglas tendrán que trabajar con fórmulas que hay dentro de la hipótesis. Si una fórmula que queremos está justo fuera de esta hipótesis, la podemos meter dentro con lo de la \emph on iteración \emph default . \layout Standard Algunos creen que no es necesario gastar una línea así, pero queda mucho más claro cuando se usa. Lo que no se acepta es usarla sólo para \begin_inset Quotes eld \end_inset \emph on acercar \emph default \begin_inset Quotes erd \end_inset una fórmula que queda muchas líneas por arriba: no hace falta volver a escribir una línea si ya la tenemos arriba en la derivación actual. \layout Subsection Introducción de la conjunción \layout Standard La conjunción (que es la \emph on y \emph default ) la podemos crear fácilmente: \layout Standard \begin_inset ERT status Collapsed \layout Standard \backslash [ \backslash begin{fitch*} \layout Standard m & A \backslash \backslash \layout Standard n & B \backslash \backslash \layout Standard \backslash hline \layout Standard & A \backslash wedge B & I$ \backslash wedge$ m,n \layout Standard \backslash end{fitch*} \backslash ] \end_inset \layout Standard Entiende bien el funcionamiento de los dibujitos como éste. Cuando se pone una raya horizontal larga, normalmente es para separar las \emph on premisas \emph default (arriba) y la \emph on conclusión \emph default (abajo). Las premisas son las condiciones que tienen que cumplirse para aplicar la regla, y la conclusión (o \emph on resolvente \emph default ) el resultado de la aplicación de la regla. \layout Standard Esta regla dice que si en una línea tenemos escrita una cosa cierta, y en otra tenemos otra, también cierta, podemos dejar escrito en una sola línea que las dos cosas son ciertas. Tendremos que anotar a la derecha las líneas de las que hemos sacado la primera y la segunda fórmula. \layout Standard Esto es bastante lógico, ¿no? Si sabemos que es verdad que \emph on llueve \emph default , y que es verdad que \emph on hace sol \emph default , entonces no hay ningún problema en decir que \emph on llueve y hace sol \emph default (a la vez). Si algo no concuerda no es culpa nuestra sino de quien nos ha asegurado que \emph on llueve \emph default o que \emph on hace sol \emph default . \layout Standard Fíjate que eligiendo las líneas al revés puedes obtener \begin_inset Formula $B\wedge A$ \end_inset , y que cogiendo la misma línea puedes llegar a \begin_inset Formula $A\wedge A$ \end_inset y \begin_inset Formula $B\wedge B$ \end_inset , que también son ciertos. \layout Subsection Eliminación de la conjunción \layout Standard Esto es justo la operación contraria a la anterior. Tiene dos partes. La primera: \layout Standard \begin_inset ERT status Collapsed \layout Standard \backslash [ \backslash begin{fitch*} \layout Standard n & A \backslash wedge B \backslash \backslash \layout Standard \backslash hline \layout Standard & A & E$ \backslash wedge$ n \layout Standard \backslash end{fitch*} \backslash ] \end_inset \layout Standard Y la segunda, por si quieres sacar \begin_inset Formula $B$ \end_inset : \layout Standard \begin_inset ERT status Collapsed \layout Standard \backslash [ \backslash begin{fitch*} \layout Standard n & A \backslash wedge B \backslash \backslash \layout Standard \backslash hline \layout Standard & B & E$ \backslash wedge$ n \layout Standard \backslash end{fitch*} \backslash ] \end_inset \layout Standard O sea, que puedes separar en varias líneas los \emph on conjuntandos \emph default de una conjunción (sí, se usa esa palabreja). Por eso se le llama \emph on eliminación de la conjunción \emph default , porque de una línea que contiene símbolos de conjunción ( \begin_inset Formula $\wedge$ \end_inset ) sacas varias que ya no lo tienen, supuestamente en un intento por acercarte a lo quieres demostrar. \layout Subsection Introducción de la implicación \layout Standard Ésta es más interesante, porque permite hacer algo útil con las hipótesis (esas subdemostraciones que llevan una barra vertical a la izquierda). Es: \layout Standard \begin_inset ERT status Collapsed \layout Standard \backslash [ \backslash begin{fitch*} \layout Standard m & \backslash fh A & H \backslash \backslash \layout Standard n & \backslash fa B \backslash \backslash \layout Standard \backslash hline \layout Standard & A \backslash Rightarrow B & I$ \backslash Rightarrow$ m,n \layout Standard \backslash end{fitch*} \backslash ] \end_inset \layout Standard Y lo que quiere decir es que si hemos supuesto algo (llamémosle \begin_inset Formula $A$ \end_inset ), y hemos descubierto (mediante las reglas) que suponer \begin_inset Formula $A$ \end_inset hace cierto a \begin_inset Formula $B$ \end_inset (lo que sea), entonces tenemos una cosa clara: no podemos asegurar que \begin_inset Formula $B$ \end_inset siempre se cumple, pero sí que \begin_inset Formula $A$ \end_inset implica \begin_inset Formula $B$ \end_inset , que se escribe \begin_inset Formula $A\Rightarrow B$ \end_inset . \layout Standard Eso nos permite salir de la subdemostración y continuar con lo que estuviéramos haciendo. Recuerda que no puedes acabar la deducción natural dento de una subdemostración. \layout Subsection Eliminación de la implicación \layout Standard Esta regla es más sencilla ya que no tiene que ver con suposiciones sino con hechos: \layout Standard \begin_inset ERT status Collapsed \layout Standard \backslash [ \backslash begin{fitch*} \layout Standard m & A \backslash Rightarrow B \backslash \backslash \layout Standard n & A \backslash \backslash \layout Standard \backslash hline \layout Standard & B & E$ \backslash Rightarrow$ m,n \layout Standard \backslash end{fitch*} \backslash ] \end_inset \layout Standard Simplemente, si nos dicen que cuando pasa \begin_inset Formula $A$ \end_inset también pasa \begin_inset Formula $B$ \end_inset (que eso es lo que significa \begin_inset Formula $A\Rightarrow B$ \end_inset ), y también nos dicen que ahora pasa \begin_inset Formula $A$ \end_inset , entonces podemos asegurar que \begin_inset Formula $B$ \end_inset . \layout Standard A esta regla también le llaman \emph on modus ponens \emph default . \layout Subsection Introducción de la disyunción \layout Standard La disyunción (que es la \emph on o \emph default ) es muy fácil pero no es obvia: \layout Standard \begin_inset ERT status Collapsed \layout Standard \backslash [ \backslash begin{fitch*} \layout Standard n & A \backslash \backslash \layout Standard \backslash hline \layout Standard & A \backslash vee B & I$ \backslash vee$ n \layout Standard \backslash end{fitch*} \backslash ] \end_inset \layout Standard Bueno, para ser exacto, diré que también está con el otro orden: \layout Standard \begin_inset ERT status Collapsed \layout Standard \backslash [ \backslash begin{fitch*} \layout Standard n & A \backslash \backslash \layout Standard \backslash hline \layout Standard & B \backslash vee A & I$ \backslash vee$ n \layout Standard \backslash end{fitch*} \backslash ] \end_inset \layout Standard ¿Qué bonito, no? Si sabemos que \begin_inset Quotes eld \end_inset \emph on hoy es jueves \emph default \begin_inset Quotes erd \end_inset también sabemos que \begin_inset Quotes eld \end_inset \emph on hoy es jueves o las vacas vuelan \emph default \begin_inset Quotes erd \end_inset , \begin_inset Quotes eld \end_inset \emph on hoy es jueves o viernes \emph default \begin_inset Quotes erd \end_inset , o incluso \begin_inset Quotes eld \end_inset \emph on hoy es jueves... o no \emph default \begin_inset Quotes erd \end_inset . Todas son ciertas. \layout Standard Recuerda que, al hablar, se usa casi siempre el \emph on o exclusivo \emph default ( \emph on XOR \emph default ), que se cumple si uno de los \emph on disyuntandos \emph default es cierto pero no cuando los dos lo son a la vez. Para un lógico, la frase común \begin_inset Quotes eld \end_inset \emph on hoy es jueves o viernes \emph default \begin_inset Quotes erd \end_inset se cumple en tres casos: cuando \emph on hoy es jueves \emph default , cuando \emph on hoy es viernes \emph default , y cuando \emph on hoy es jueves y viernes a la vez \emph default (algo difícil en el mundo real, pero los matemáticos son capaces de hacer todo tipo de suposiciones...). \layout Subsection Eliminación de la disyunción \layout Standard Ésta es la regla más complicada, precisamente porque si nos dan una frase con \emph on o \emph default , como \begin_inset Quotes eld \end_inset \emph on hoy es jueves o viernes \emph default \begin_inset Quotes erd \end_inset , ¿qué podemos sacar de ahí? ¿Que \emph on hoy es jueves \emph default ? No, podría ser viernes. ¿Que \emph on hoy es viernes \emph default ? No, podría ser jueves. ¿Que \emph on hoy es jueves o viernes \emph default ? Ya, pero eso ya lo sabíamos... \layout Standard La regla (ahora la explico): \layout Standard \begin_inset ERT status Collapsed \layout Standard \backslash [ \backslash begin{fitch*} \layout Standard m & A \backslash vee B \backslash \backslash \layout Standard & \backslash fh A & H \backslash \backslash \layout Standard n & \backslash fa C \backslash \backslash \layout Standard & \backslash fh B & H \backslash \backslash \layout Standard p & \backslash fa C \backslash \backslash \layout Standard \backslash hline \layout Standard & C & E$ \backslash vee$ m,n,p \layout Standard \backslash end{fitch*} \backslash ] \end_inset \layout Standard Necesitamos más información aparte de un \begin_inset Formula $A\vee B$ \end_inset . Si, por casualidad, sabemos que \begin_inset Formula $A\Rightarrow C$ \end_inset , y que también \begin_inset Formula $B\Rightarrow C$ \end_inset , entonces sí que podemos saber qué pasa cuando \begin_inset Formula $A\vee B$ \end_inset : tanto una opción como la otra nos llevan a \begin_inset Formula $C$ \end_inset , así que \begin_inset Formula $C$ \end_inset es cierto. \layout Standard Estas cosas sólo pasan cuando el ejercicio está preparado para que salga una \emph on eliminación de la disyunción \emph default , o cuando \begin_inset Formula $A$ \end_inset y \begin_inset Formula $B$ \end_inset se parecen mucho (entonces encontraremos una \begin_inset Formula $C$ \end_inset tal que los dos la impliquen). \layout Standard Un ejemplo: cuando contraté el acceso a Internet por ADSL, fue con \emph on Telefónica \emph default o \emph on Terra \emph default , pero no sé exactamente con quién (ni ellos mismos lo sabían). Cualquier opción era lenta, carísima, y llena de problemas (a todo esto le llamaré \begin_inset Formula $M$ \end_inset ), por tanto cualquier compañía era una \begin_inset Formula $M$ \end_inset . En concreto, sabemos que \begin_inset Formula $Telefonica\Rightarrow M$ \end_inset , y que \begin_inset Formula $Terra\Rightarrow M$ \end_inset , así que no hay dudas sobre la calidad de mi conexión ADSL: también era una \begin_inset Formula $M$ \end_inset , tanto si la tengo en una como en la otra. Y encima me costó 9 meses darme de alta... Suerte que eso fue hace ya muchos años. \layout Standard A esta regla se le llama \emph on prueba por casos \emph default , porque hay que probar cada posible caso para comprobar que llevan a la misma conclusión. \layout Subsection Introducción de la negación \layout Standard Ésta es muy bonita e interesante: \layout Standard \begin_inset ERT status Collapsed \layout Standard \backslash [ \backslash begin{fitch*} \layout Standard m & \backslash fh A & H \backslash \backslash \layout Standard n & \backslash fa B \backslash \backslash \layout Standard p & \backslash fa \backslash neg B \backslash \backslash \layout Standard \backslash hline \layout Standard & \backslash neg A & I$ \backslash neg$ m,n,p \layout Standard \backslash end{fitch*} \backslash ] \end_inset \layout Standard Si al suponer que \begin_inset Formula $A$ \end_inset , has llegado a la conclusión de que son ciertas \begin_inset Formula $B$ \end_inset y \begin_inset Formula $\neg B$ \end_inset a la vez, no estás perdido, ya que acabas de descubrir una cosa cierta: que no es posible que \begin_inset Formula $A$ \end_inset sea cierto, o sea, que \begin_inset Formula $\neg A$ \end_inset es cierto. \layout Standard Por ejemplo, confieso que \emph on si uso Windows, no aprovecho el tiempo que estoy con el ordenador \emph default . Desde hace años \emph on sí que lo aprovecho \emph default , por lo tanto la conclusión es que \emph on no uso Windows \emph default . Para llegar a esa conclusión, el camino que habrías seguido (puede que sin pensarlo) es precisamente el que pide esta regla: supongamos que \emph on sí que uso Windows \emph default , en ese caso \emph on no aprovecharía mi ordenador \emph default . Pero digo que \emph on sí que lo aprovecho \emph default , así que esa suposición tiene que ser equivocada. \layout Standard A este procedimiento se le llama \emph on reducción al absurdo \emph default ( \emph on reductio ad absurdum \emph default ): suponer una cosa para llegar a una contradicción y poder afirmar que lo que se ha supuesto es falso. Va muy bien si empiezas suponiendo \emph on lo contrario \emph default de lo que quieres demostrar: si llegas a una contradicción ya está casi todo hecho. \layout Standard Tengo que avisar de que éste es un \emph on abuso de notación \emph default : resulta que para que cuadren los teoremas de la lógica, toda subdemostración ha de tener \emph on una \emph default conclusión (no dos); y en esta hipótesis que sale en la regla de arriba, no queda claro cuál es la conclusión (si \begin_inset Formula $B$ \end_inset o \begin_inset Formula $\neg B$ \end_inset ). La forma correcta de escribirlo sería usar la \emph on introducción de la conjunción \emph default para decir que \begin_inset Formula $B\wedge\neg B$ \end_inset , y ésta es la conclusión que nos hace ver que la hipótesis inicial era errónea. Mis profesores se ahorraban esta línea. \layout Subsection Eliminación de la negación \layout Standard Ésta es muy sencilla, pero hay que decirla: \layout Standard \begin_inset ERT status Collapsed \layout Standard \backslash [ \backslash begin{fitch*} \layout Standard n & \backslash neg \backslash neg A \backslash \backslash \layout Standard \backslash hline \layout Standard & A & E$ \backslash neg$ n \layout Standard \backslash end{fitch*} \backslash ] \end_inset \layout Standard O sea, que cuando veamos la negación de la negación de algo, podemos quitar esas dos negaciones seguidas. \layout Standard Recuerda que la negación de \begin_inset Quotes eld \end_inset \emph on esto es blanco \emph default \begin_inset Quotes erd \end_inset no es \begin_inset Quotes eld \end_inset \emph on esto es negro \emph default \begin_inset Quotes erd \end_inset sino \begin_inset Quotes eld \end_inset \emph on esto no es blanco \emph default \begin_inset Quotes erd \end_inset . \layout Subsection No hay más reglas \layout Standard Pues ya está, no hay más reglas básicas. Aún hay otras para \emph on cuantificadores \emph default y dos de \emph on cierto \emph default y \emph on falso \emph default , que explico más adelante, pero con estas nueve ya se puede intentar demostrar la validez de cualquier secuente de este documento (excepto los de cuantificado res...). \layout Standard Recuerda otra vez que no hay más reglas: no puedes cambiar de \begin_inset Formula $A\vee\neg A$ \end_inset a \begin_inset Formula $\blacksquare$ \end_inset ( \emph on cierto \emph default ) directamente, ni de \begin_inset Formula $\neg(A\vee B)$ \end_inset a \begin_inset Formula $\neg A\wedge\neg B$ \end_inset , ni usar la propiedad distributiva, asociativa, o conmutativa. Lo tienes que hacer todo paso por paso; no se permiten ni siquiera los cambios sencillos (de momento). ¿Por qué? Porque quizás no son tan sencillos como crees: ya lo verás cuando te toque demostrar que \begin_inset Formula $A\vee\neg A$ \end_inset es siempre cierto... (está en la siguiente sección). \layout Section Ejercicios explicados \layout Standard Ejercicios de varios niveles explicados paso a paso. Si quieres aún más ejemplos (sin comentar), mira la última sección. Lo que intento explicar no son las reglas, sino el cómo hay que pensar para que se te ocurra la idea mágica que lo soluciona. \layout Standard Esto es lo que más eché en falta cuando tenía que estudiar deducción natural. \layout Subsection Uno muy sencillo. \begin_inset Formula $P,\ P\Rightarrow Q\vdash P\wedge Q$ \end_inset \layout Standard La solución a \begin_inset Formula $P,\ P\Rightarrow Q\vdash P\wedge Q$ \end_inset es: \layout Standard \begin_inset ERT status Collapsed \layout Standard \backslash [ \backslash begin{fitch} \layout Standard P \backslash \backslash \layout Standard P \backslash Rightarrow Q \backslash \backslash \layout Standard Q & E$ \backslash Rightarrow$ 2,1 \backslash \backslash \layout Standard P \backslash wedge Q & I$ \backslash wedge$ 1,3 \layout Standard \backslash end{fitch} \backslash ] \end_inset \layout Standard Aquí no hay que pensar mucho, simplemente hay que usar bien las reglas y justificaciones. \layout Standard Lo primero, entender lo que nos han dicho: nos dicen que ahora pasan \emph on dos \emph default cosas, la primera es que \begin_inset Formula $P$ \end_inset y la segunda es que \begin_inset Formula $P\Rightarrow Q$ \end_inset (son las dos fórmulas que hay a la izquierda del \begin_inset Formula $\vdash$ \end_inset ). Estas dos cosas nos las tenemos que apuntar, una en cada línea, porque en esta demostración serán siempre ciertas (nos guste o no). \layout Standard El objetivo de esta demostración es saber que \begin_inset Formula $P\wedge Q$ \end_inset también es cierto, porque nos han contado que cuando \begin_inset Formula $P$ \end_inset y \begin_inset Formula $P\Rightarrow Q$ \end_inset son ciertos, entonces \begin_inset Formula $P\wedge Q$ \end_inset también, y queremos comprobar si es verdad. Al final se ha conseguido, porque en la última línea sale el \begin_inset Formula $P\wedge Q$ \end_inset escrito. \layout Standard ¿Cómo seguimos ahora? Hay que fijarse en a dónde queremos llegar. Si \begin_inset Formula $P\wedge Q$ \end_inset tiene que ser cierto, entonces tanto \begin_inset Formula $P$ \end_inset como \begin_inset Formula $Q$ \end_inset tendrán que ser ciertos; vamos a preocuparnos por demostrar que lo son. \layout Standard \begin_inset Formula $P$ \end_inset es cierto, porque nos lo han dicho, y lo tenemos apuntado en la línea 1. \layout Standard Pero no nos han dicho que \begin_inset Formula $Q$ \end_inset lo sea. ¿Qué han dicho sobre \begin_inset Formula $Q$ \end_inset ? Buscándola en las líneas 1 y 2, lo único que conocemos es que \begin_inset Formula $Q$ \end_inset es cierta cuando pasa \begin_inset Formula $P$ \end_inset (lo pone en la 2). Y como \begin_inset Formula $P$ \end_inset es cierta, podemos usar una de las reglas para deducir \begin_inset Formula $Q$ \end_inset a partir del \begin_inset Formula $P\Rightarrow Q$ \end_inset y de \begin_inset Formula $P$ \end_inset . Fíjate en qué es lo más importante que ha pasado al cambiar de \begin_inset Formula $P\Rightarrow Q$ \end_inset a \begin_inset Formula $Q$ \end_inset : se ha dejado de usar el símbolo de la implicación; así que la regla que necesitamos se llama \emph on eliminación de la implicación \emph default . \layout Standard Para usar esta regla, miramos la definición, y vemos que tenemos que poner en una nueva línea la \begin_inset Formula $Q$ \end_inset , y como justificación hay que escribir \begin_inset Formula $E\Rightarrow\ 2,1$ \end_inset . La \begin_inset Formula $E$ \end_inset viene de \emph on eliminación \emph default , el \begin_inset Formula $\Rightarrow$ \end_inset es por \emph on implicación \emph default , el primer número es el de la línea que contiene implicación ( \begin_inset Formula $P\Rightarrow Q$ \end_inset ), y el segundo número es el de la línea que contiene la verdad conocida ( \begin_inset Formula $P$ \end_inset ). Es incorrecto ponerlos al revés ( \begin_inset Formula $E\Rightarrow\ 1,2$ \end_inset ), porque en la definición de la regla pone que la línea que tiene la implicació n tiene que ser citada en primer lugar. \layout Standard Ya hemos aplicado la regla, y ya sabemos tres cosas que son ciertas: que \begin_inset Formula $P$ \end_inset , que \begin_inset Formula $P\Rightarrow Q$ \end_inset , y que \begin_inset Formula $Q$ \end_inset . Todas son igual de ciertas. Ahora estamos más cerca del objetivo, \begin_inset Formula $P\wedge Q$ \end_inset , porque ya sabemos que \begin_inset Formula $P$ \end_inset y \begin_inset Formula $Q$ \end_inset son ciertas, así que \begin_inset Formula $P\wedge Q$ \end_inset también tiene que serlo (es obvio). En la fórmula que buscamos hay un signo de conjunción ( \begin_inset Formula $\wedge$ \end_inset ) que no tenemos, así que hay que usar la \emph on introducción de la conjunción \emph default para afirmar que \begin_inset Formula $P\wedge Q$ \end_inset es cierto porque \begin_inset Formula $P$ \end_inset lo es y \begin_inset Formula $Q$ \end_inset también. Como justificación ponemos \begin_inset Formula $I\wedge\ 1,3$ \end_inset (la línea donde pone que \begin_inset Formula $P$ \end_inset , y la que pone que \begin_inset Formula $Q$ \end_inset ). No vale poner \begin_inset Formula $I\wedge\ 3,1$ \end_inset , eso sería para asegurar que \begin_inset Formula $Q\wedge P$ \end_inset , que no es lo que piden demostrar. \layout Standard Entonces ya sabemos que 4 cosas son ciertas: \begin_inset Formula $P$ \end_inset , \begin_inset Formula $P\Rightarrow Q$ \end_inset , \begin_inset Formula $Q$ \end_inset , y \begin_inset Formula $P\wedge Q$ \end_inset . Podríamos seguir descubriendo más cosas ciertas, pero es que ya hemos acabado, porque nos pedían demostrar que \begin_inset Formula $P\wedge Q$ \end_inset es cierto y ya lo hemos conseguido (en la línea 4). Por lo tanto, ésta será la última línea, y no hay que escribir nada más. \layout Standard Ah, un ejemplo de esto con palabras: \begin_inset Quotes eld \end_inset \emph on ahora es verano, y en verano hace calor. Por eso ahora es verano y hace calor \emph default \begin_inset Quotes erd \end_inset . \layout Subsection Algo más complicado. \begin_inset Formula $P\wedge Q\Rightarrow R,\ Q\Rightarrow P,\ Q\vdash R$ \end_inset \layout Standard Intenta hacer tú solo el \begin_inset Formula $P\wedge Q\Rightarrow R,\ Q\Rightarrow P,\ Q\vdash R$ \end_inset . Después mira la solución: \layout Standard \begin_inset ERT status Collapsed \layout Standard \backslash [ \backslash begin{fitch} \layout Standard P \backslash wedge Q \backslash Rightarrow R \backslash \backslash \layout Standard Q \backslash Rightarrow P \backslash \backslash \layout Standard Q \backslash \backslash \layout Standard P & E$ \backslash Rightarrow$ 2,3 \backslash \backslash \layout Standard P \backslash wedge Q & I$ \backslash wedge$ 4,3 \backslash \backslash \layout Standard R & E$ \backslash Rightarrow$ 1,5 \layout Standard \backslash end{fitch} \backslash ] \end_inset \layout Standard La única forma que hay de llegar a \begin_inset Formula $R$ \end_inset es usando la primera fórmula, \begin_inset Formula $P\wedge Q\Rightarrow R$ \end_inset , pero sólo la podemos usar cuando \begin_inset Formula $P\wedge Q$ \end_inset es cierto, así que vamos a por esto. \layout Standard Sabemos que \begin_inset Formula $Q\Rightarrow P$ \end_inset (línea 2) y que \begin_inset Formula $Q$ \end_inset (línea 3), así que deducimos que \begin_inset Formula $P$ \end_inset . Como ahora \begin_inset Formula $P$ \end_inset es cierto y \begin_inset Formula $Q$ \end_inset también, \begin_inset Formula $P\wedge Q$ \end_inset también. Hasta aquí es parecido al ejercicio anterior. \layout Standard Por último, tenemos que \begin_inset Formula $P\wedge Q\Rightarrow R$ \end_inset , y sabemos que \begin_inset Formula $P\wedge Q$ \end_inset , así que acabamos diciendo que \begin_inset Formula $R$ \end_inset . \layout Subsection Empezando a suponer cosas. \begin_inset Formula $P\Rightarrow Q,\ Q\Rightarrow R\vdash P\Rightarrow Q\wedge R$ \end_inset \layout Standard Éste, \begin_inset Formula $P\Rightarrow Q,\ Q\Rightarrow R\vdash P\Rightarrow Q\wedge R$ \end_inset , es más interesante: \layout Standard \begin_inset ERT status Collapsed \layout Standard \backslash [ \backslash begin{fitch} \layout Standard P \backslash Rightarrow Q \backslash \backslash \layout Standard Q \backslash Rightarrow R \backslash \backslash \layout Standard \backslash fh P & H \backslash \backslash \layout Standard \backslash fa Q & E$ \backslash Rightarrow$ 1,3 \backslash \backslash \layout Standard \backslash fa R & E$ \backslash Rightarrow$ 2,4 \backslash \backslash \layout Standard \backslash fa Q \backslash wedge R & I$ \backslash wedge$ 4,5 \backslash \backslash \layout Standard P \backslash Rightarrow Q \backslash wedge R & I$ \backslash Rightarrow$ 3,6 \layout Standard \backslash end{fitch} \backslash ] \end_inset \layout Standard Fíjate en los siguientes detalles: \layout Itemize No nos dan ninguna información sobre qué pasa ahora (ni han dado la fórmula \begin_inset Formula $P$ \end_inset , ni \begin_inset Formula $Q\wedge R$ \end_inset , etc.). Sólo nos dicen cosas como que \emph on si pasara \begin_inset Formula $P$ \end_inset , entonces también pasaría \begin_inset Formula $Q$ \end_inset \emph default . \layout Itemize De la misma forma, lo que hay que demostrar no es que \emph on ahora mismo pasa algo \emph default , sino que \emph on si pasara \begin_inset Formula $P$ \end_inset , entonces \begin_inset Formula $Q$ \end_inset y \begin_inset Formula $R$ \end_inset son ciertas \emph default . \layout Itemize \begin_inset Formula $P\Rightarrow Q\wedge R$ \end_inset es una implicación ( \emph on algo implica algo \emph default ), porque el operador \begin_inset Formula $\Rightarrow$ \end_inset tiene menos prioridad que el \begin_inset Formula $\wedge$ \end_inset . Es un error grave interpretar esa fórmula como \begin_inset Formula $(P\Rightarrow Q)\wedge R$ \end_inset . \layout Standard Como la fórmula que queremos es una implicación ( \begin_inset Formula $P\Rightarrow Q\wedge R$ \end_inset ), tendremos que usar la \emph on introducción de la implicación \emph default , pero esta regla requiere tener una subdemostración (consulta su definición). \layout Standard No es muy complicado entender por qué: \begin_inset Formula $P\Rightarrow Q\wedge R$ \end_inset dice que \emph on si pasa \begin_inset Formula $P$ \end_inset , entonces pasa \begin_inset Formula $Q\wedge R$ \end_inset \emph default , así que lo primero que habrá que hacer será suponer que sí que pasa \begin_inset Formula $P$ \end_inset . Entonces tendremos que sacar que, en ese caso en el que \begin_inset Formula $P$ \end_inset es cierto, también lo es \begin_inset Formula $Q\wedge R$ \end_inset . Cuando lo consigamos, aplicamos la regla, y lo dejamos bien escrito: \begin_inset Formula $P\Rightarrow Q\wedge R$ \end_inset . \layout Standard Por eso en la línea 3 se hace una hipótesis (justificada con la \begin_inset Formula $H$ \end_inset a la derecha): supongamos que \begin_inset Formula $P$ \end_inset es cierto. Ahora empezamos una subdemostración, en donde podemos usar las verdades que hay escritas en la demostración padre (líneas 1 y 2 en este caso), y también podemos usar \begin_inset Formula $P$ \end_inset como si fuera verdad. \layout Standard Hemos hecho esta hipótesis con el objetivo de saber que \begin_inset Formula $Q\wedge R$ \end_inset , así que lo deducimos igual que en los ejemplos anteriores. Fíjate en que usamos verdades de dentro y de fuera de la subdemostración, y que, mientras no la acabemos, hay que poner esa raya vertical a la izquierda. \layout Standard En la línea 6 ya tenemos que \begin_inset Formula $Q\wedge R$ \end_inset , que es lo que queríamos. Usando la regla de \emph on introducción de la implicación \emph default , podemos salir de esta subdemostración diciendo que \emph on si la hipótesis es cierta, entonces lo que hemos deducido a partir de ella también \emph default . Se deja de poner la rayita vertical, porque \begin_inset Formula $P\Rightarrow Q\wedge R$ \end_inset es cierto siempre (no depende de si \begin_inset Formula $P$ \end_inset es verdad o no). La justificación usada, \begin_inset Formula $I\Rightarrow\ 3,6$ \end_inset , dice que 3 es la línea donde hemos hecho la suposición, y 6 la línea en la que hemos descubierto algo interesante que pasa al hacer esa suposición. \layout Standard \begin_inset Formula $P\Rightarrow Q\wedge R$ \end_inset es lo que queríamos, así que ya hemos acabado. Acabamos de la misma forma que siempre, porque estamos fuera de la subdemostrac ión. \layout Subsection Usando la iteración. \begin_inset Formula $P\vdash Q\Rightarrow P$ \end_inset \layout Standard Éste es muy corto: \begin_inset Formula $P\vdash Q\Rightarrow P$ \end_inset . Solución: \layout Standard \begin_inset ERT status Collapsed \layout Standard \backslash [ \backslash begin{fitch} \layout Standard P \backslash \backslash \layout Standard \backslash fh Q & H \backslash \backslash \layout Standard \backslash fa P & IT 1 \backslash \backslash \layout Standard Q \backslash Rightarrow P & I$ \backslash Rightarrow$ 2,3 \layout Standard \backslash end{fitch} \backslash ] \end_inset \layout Standard El camino es directo: suponer \begin_inset Formula $Q$ \end_inset , y acabar viendo que, en ese caso, es cierto \begin_inset Formula $P$ \end_inset . El truco: \begin_inset Formula $P$ \end_inset es siempre cierto, tanto si suponemos \begin_inset Formula $Q$ \end_inset como si no. \layout Standard Habrá que usar la \emph on introducción de la implicación \emph default , pero eso requiere tener una hipótesis, y, líneas más abajo, el resultado de haber supuesto eso. Entonces es cuando podemos cerrar la hipótesis. \layout Standard Después de abrirla (línea 2), habrá que hacer algo para dejar escrito que \begin_inset Formula $P$ \end_inset . Como ya lo tenemos escrito en la línea 1, simplemente ponemos la \begin_inset Formula $P$ \end_inset otra vez y lo justificamos con \begin_inset Formula $IT\ 1$ \end_inset , que quiere decir \begin_inset Quotes eld \end_inset \emph on esto lo he copiado de la línea 1 \emph default \begin_inset Quotes erd \end_inset . El \begin_inset Formula $IT$ \end_inset es por \emph on iteración \emph default . \layout Standard Ya cumplimos los requisitos para aplicar la regla, así que la aplicamos, salimos de la subdemostración, y hemos acabado. \layout Subsection Reducción al absurdo. \begin_inset Formula $P\Rightarrow Q,\ \neg Q\vdash\neg P$ \end_inset \layout Standard Ésta es una técnica muy útil. La validez de \begin_inset Formula $P\Rightarrow Q,\ \neg Q\vdash\neg P$ \end_inset se demuestra con: \layout Standard \begin_inset ERT status Collapsed \layout Standard \backslash [ \backslash begin{fitch} \layout Standard P \backslash Rightarrow Q \backslash \backslash \layout Standard \backslash neg Q \backslash \backslash \layout Standard \backslash fh P & H \backslash \backslash \layout Standard \backslash fa Q & E$ \backslash Rightarrow$ 1,3 \backslash \backslash \layout Standard \backslash fa \backslash neg Q & IT 2 \backslash \backslash \layout Standard \backslash neg P & I$ \backslash neg$ 3,4,5 \layout Standard \backslash end{fitch} \backslash ] \end_inset \layout Standard A lo que hay que llegar es a \begin_inset Formula $\neg P$ \end_inset , que es \emph on la negación de algo \emph default , por eso habrá que usar la regla de \emph on introducción de la negación \emph default , conocida como \emph on reducción al absurdo \emph default . \layout Standard La forma de hacer esto será suponer lo contrario de \begin_inset Formula $\neg P$ \end_inset (que es \begin_inset Formula $P$ \end_inset ) y llegar a una contradicción. Al suponer \begin_inset Formula $P$ \end_inset llegaremos a \begin_inset Formula $Q$ \end_inset (por \emph on eliminación de la implicación \emph default ), y como también tenemos que \begin_inset Formula $\neg Q$ \end_inset , podremos aplicar la regla. Este \begin_inset Formula $\neg Q$ \end_inset habrá que meterlo dentro de la subdemostración con la regla de \emph on iteración \emph default , para que esté junto con la \begin_inset Formula $Q$ \end_inset y \emph on dentro \emph default de la subdemostración. Todo lo que hay dentro de la subdemostración es consecuencia de \begin_inset Formula $P$ \end_inset , así que es importante ver que tanto \begin_inset Formula $Q$ \end_inset como \begin_inset Formula $\neg Q$ \end_inset lo son. \layout Standard Para la \emph on introducción de la negación \emph default , la forma de justificar la regla es poniendo el número de línea donde empieza la suposición (errónea), y los números de las dos líneas donde hemos visto la contradicción. La conclusión de esta regla es lo contrario de lo que se había supuesto, en este caso \begin_inset Formula $\neg P$ \end_inset , por lo que se acaba el procedimiento. \layout Standard Este razonamiento se suele hacer sin pensar. En palabras sería algo así: \begin_inset Quotes eld \end_inset \emph on claro que \begin_inset Formula $\neg P$ \end_inset , porque si fuera \begin_inset Formula $P$ \end_inset entonces \begin_inset Formula $Q$ \end_inset , y me dicen que \begin_inset Formula $\neg Q$ \end_inset , así que no puede ser \begin_inset Formula $P$ \end_inset \emph default \begin_inset Quotes erd \end_inset . \layout Subsection Con subdemostraciones. \begin_inset Formula $P\Rightarrow(Q\Rightarrow R)\vdash Q\Rightarrow(P\Rightarrow R)$ \end_inset \layout Standard Se complican las cosas. La solución de \begin_inset Formula $P\Rightarrow(Q\Rightarrow R)\vdash Q\Rightarrow(P\Rightarrow R)$ \end_inset : \layout Standard \begin_inset ERT status Collapsed \layout Standard \backslash [ \backslash begin{fitch} \layout Standard P \backslash Rightarrow (Q \backslash Rightarrow R) \backslash \backslash \layout Standard \backslash fh Q & H \backslash \backslash \layout Standard \backslash fa \backslash fh P & H \backslash \backslash \layout Standard \backslash fa \backslash fa Q \backslash Rightarrow R & E$ \backslash Rightarrow$ 1,3 \backslash \backslash \layout Standard \backslash fa \backslash fa R & E$ \backslash Rightarrow$ 4,2 \backslash \backslash \layout Standard \backslash fa P \backslash Rightarrow R & I$ \backslash Rightarrow$ 3,5 \backslash \backslash \layout Standard Q \backslash Rightarrow (P \backslash Rightarrow R) & I$ \backslash Rightarrow$ 2,6 \layout Standard \backslash end{fitch} \backslash ] \end_inset \layout Standard Lo primero: aquí sólo usaremos las dos reglas que ayudan a poner y quitar implicaciones, porque es el único operador que tenemos. \layout Standard Queremos llegar a \begin_inset Formula $Q\Rightarrow(P\Rightarrow R)$ \end_inset , por lo que tendremos que hacer una hipótesis \begin_inset Formula $Q$ \end_inset dentro de la cual habrá que demostrar que \begin_inset Formula $P\Rightarrow R$ \end_inset . Hacemos eso para simplificar el problema: abrimos la subdemostración en la línea 2. No la cerraremos hasta que no se llegue a saber que \begin_inset Formula $P\Rightarrow R$ \end_inset es cierto. \layout Standard Ahora el problema es algo más fácil. Necesitamos comprobar que \begin_inset Formula $P\Rightarrow R$ \end_inset , y tenemos dos líneas con dos verdades: la primera dice que \begin_inset Formula $P\Rightarrow(Q\Rightarrow R)$ \end_inset , y la segunda pone que \begin_inset Formula $Q$ \end_inset . \layout Standard ¿Cómo podemos conseguir el \begin_inset Formula $P\Rightarrow R$ \end_inset ? Pues como siempre: hay que suponer que \begin_inset Formula $P$ \end_inset , y conseguir ver que \begin_inset Formula $R$ \end_inset , de alguna manera. Aunque no parezca fácil, es lo que hay hacer, porque la \emph on introducción de la implicación \emph default va así. Por lo tanto, vamos a abrir otra hipótesis, ahora suponiendo que \begin_inset Formula $P$ \end_inset , y a ver si llegamos a \begin_inset Formula $R$ \end_inset . Ésta será una hipótesis dentro de una hipótesis, pero no hay ningún problema en hacer eso. \layout Standard Después de escribir la línea 3, y, metidos dentro de una \emph on subsubdemostración \emph default , tenemos a nuestra disposición que \begin_inset Formula $P\Rightarrow(Q\Rightarrow R)$ \end_inset , que \begin_inset Formula $Q$ \end_inset , y que \begin_inset Formula $P$ \end_inset . Tenemos que probar que \begin_inset Formula $R$ \end_inset . Ya no parece muy difícil, ¿no? Si sabemos que \begin_inset Formula $P$ \end_inset , podemos usar la \emph on eliminación de la implicación \emph default en la línea 1, y así conseguiremos la fórmula cierta \begin_inset Formula $Q\Rightarrow R$ \end_inset . Como también es cierto \begin_inset Formula $Q$ \end_inset (línea 2), podemos volver a usar la misma regla para saber que \begin_inset Formula $R$ \end_inset . \layout Standard Hemos visto que el suponer \begin_inset Formula $P$ \end_inset nos ha llevado a la conclusión de que \begin_inset Formula $R$ \end_inset , así que podemos dejar escrito que \begin_inset Formula $P\Rightarrow R$ \end_inset , que es lo que andábamos buscando. Ahora ya hemos salido de la subsubdemostración, y sólo estamos metidos dentro de la suposición de que \begin_inset Formula $Q$ \end_inset es cierto. Como vemos que esta suposición implica la certeza de la fórmula \begin_inset Formula $P\Rightarrow R$ \end_inset , podemos salir de esta subdemostración concluyendo que \begin_inset Formula $Q\Rightarrow(P\Rightarrow R)$ \end_inset . \layout Standard \begin_inset Formula $Q\Rightarrow(P\Rightarrow R)$ \end_inset es precisamente lo que había que demostrar, así que ya se ha acabado. \layout Subsection Uno de prueba por casos. \begin_inset Formula $P\vee(Q\wedge R)\vdash P\vee Q$ \end_inset \layout Standard Habrá que usar la regla más complicada: la \emph on eliminación de la disyunción \emph default . \begin_inset Formula $P\vee(Q\wedge R)\vdash P\vee Q$ \end_inset solucionado: \layout Standard \begin_inset ERT status Collapsed \layout Standard \backslash [ \backslash begin{fitch} \layout Standard P \backslash vee (Q \backslash wedge R) \backslash \backslash \layout Standard \backslash fh P & H \backslash \backslash \layout Standard \backslash fa P \backslash vee Q & I$ \backslash vee$ 2 \backslash \backslash \layout Standard \backslash fh Q \backslash wedge R & H \backslash \backslash \layout Standard \backslash fa Q & E$ \backslash wedge$ 4 \backslash \backslash \layout Standard \backslash fa P \backslash vee Q & I$ \backslash vee$ 5 \backslash \backslash \layout Standard P \backslash vee Q & E$ \backslash vee$ 1,3,6 \layout Standard \backslash end{fitch} \backslash ] \end_inset \layout Standard Ya conoces las reglas, así que explico la forma de pensar de un humano que no entienda de deducción natural pero que piense un poquito: \layout Standard Necesitamos comprobar que \begin_inset Formula $P\vee Q$ \end_inset es cierto siempre. La expresión de la izquierda, \begin_inset Formula $P\vee(Q\wedge R)$ \end_inset , se puede cumplir por dos motivos: \layout Itemize si se cumple porque \begin_inset Formula $P$ \end_inset es cierto, entonces \begin_inset Formula $P\vee Q$ \end_inset es cierto. \layout Itemize si se cumple porque \begin_inset Formula $Q\wedge R$ \end_inset es cierto, es que \begin_inset Formula $Q$ \end_inset y \begin_inset Formula $R$ \end_inset son ciertas, así que \begin_inset Formula $P\vee Q$ \end_inset es cierto gracias a \begin_inset Formula $Q$ \end_inset . \layout Standard O sea, que de cualquier manera, \begin_inset Formula $P\vee Q$ \end_inset es cierto. \layout Standard Pues ahora lo único que hay hacer es traducir a lenguaje lógico, siguiendo el mismo orden en el que se ha pensado, y yendo poco a poco. \layout Standard Se empieza demostrando un camino, luego el otro, y por último se aplica la regla de \emph on eliminación de la disyunción \emph default . Para justificarla hay que escribir la línea donde está la disyunción, y las dos líneas de dentro de cada subdemostración donde se vea que tanto al suponer una cosa como al suponer la otra, el resultado es el mismo. \layout Standard Fíjate que, aunque averigüemos que \begin_inset Formula $P\Rightarrow P\vee Q$ \end_inset y que \begin_inset Formula $Q\wedge R\Rightarrow P\vee Q$ \end_inset , no hace falta usar la \emph on introducción de la implicación \emph default para dejar escrito eso. \layout Standard Lo más complicado de la \emph on prueba por casos \emph default suele ser decidir qué expresión vas a demostrar en ambos casos. ¡Tiene que ser la misma para los dos casos! \layout Subsection Uno para pensar. \begin_inset Formula $L\wedge M\Rightarrow\neg P,\ I\Rightarrow P,\ M,\ I\vdash\neg L$ \end_inset \layout Standard Intenta hacer \begin_inset Formula $L\wedge M\Rightarrow\neg P,\ I\Rightarrow P,\ M,\ I\vdash\neg L$ \end_inset de cabeza; luego escríbelo en papel. Queda: \layout Standard \begin_inset ERT status Collapsed \layout Standard \backslash [ \backslash begin{fitch} \layout Standard L \backslash wedge M \backslash Rightarrow \backslash neg P \backslash \backslash \layout Standard I \backslash Rightarrow P \backslash \backslash \layout Standard M \backslash \backslash \layout Standard I \backslash \backslash \layout Standard \backslash fh L & H \backslash \backslash \layout Standard \backslash fa L \backslash wedge M & I$ \backslash wedge$ 5,3 \backslash \backslash \layout Standard \backslash fa \backslash neg P & E$ \backslash Rightarrow$ 1,6 \backslash \backslash \layout Standard \backslash fa P & E$ \backslash Rightarrow$ 2,4 \backslash \backslash \layout Standard \backslash neg L & I$ \backslash neg$ 5,7,8 \layout Standard \backslash end{fitch} \backslash ] \end_inset \layout Standard Lo pongo con palabras: \begin_inset Quotes eld \end_inset \emph on si usas Linux y Mozilla como navegador, te evitas los problemas. En cambio, si usas Internet Explorer tendrás problemas. Ahora tú usas Mozilla, pero también Internet Explorer a veces. Por lo tanto, sé que no usas Linux \emph default \begin_inset Quotes erd \end_inset . \layout Standard A lo mejor te parece evidente: \begin_inset Quotes eld \end_inset \emph on claro, porque IE no está en Linux \emph default \begin_inset Quotes erd \end_inset , pero fíjate en que el \begin_inset Formula $I\Rightarrow\neg L$ \end_inset no sale por ningún lado. \layout Standard La forma en que deberías pensar mientras preparas el ejercicio es: \layout Enumerate Necesito demostrar \begin_inset Formula $\neg L$ \end_inset , que es la negación de algo. No se ve ninguna regla de la forma \emph on algo implica \begin_inset Formula $\neg L$ \end_inset \emph default que me permita obtenerlo directamente. Habrá que usar otra forma, por ejemplo la \emph on introducción de la negación \emph default ( \emph on reducción al absurdo \emph default ): supongamos que sí que uso Linux. \layout Enumerate En el caso de que uso Linux, usaría Linux y Mozilla, porque ya usaba Mozilla antes (es la tercera verdad que hay escrita en el enunciado). \layout Enumerate Al usar Linux y Mozilla, no tendría problemas informáticos, porque \begin_inset Formula $L\wedge M\Rightarrow\neg P$ \end_inset . \layout Enumerate Pero también usaba Internet Explorer (cuarta verdad), y como IE genera problemas , yo tendré problemas. \begin_inset Formula $P$ \end_inset . \layout Enumerate He llegado a una contradicción: \begin_inset Formula $\neg P$ \end_inset y \begin_inset Formula $P$ \end_inset . Por lo tanto, lo que pasa es que la suposición que he hecho de que uso Linux es incorrecta: resulta que \begin_inset Formula $\neg L$ \end_inset . \layout Standard Pues ahora sólo hay que seguir el mismo procedimiento, pero escribiéndolo paso por paso y usando las reglas. Lo que se obtiene es la figura que sale arriba, que casualmente tiene 5 líneas de procedimiento (las 4 primeras son sólo para copiar las verdades). Cada línea se corresponde con los pasos que he explicado aquí. \layout Subsection El lado izquierdo vacío. \begin_inset Formula $\vdash P\Rightarrow P$ \end_inset \layout Standard Demostrar \begin_inset Formula $\vdash P\Rightarrow P$ \end_inset es muy fácil y corto: \layout Standard \begin_inset ERT status Collapsed \layout Standard \backslash [ \backslash begin{fitch} \layout Standard \backslash fh P & H \backslash \backslash \layout Standard \backslash fa P & IT 1 \backslash \backslash \layout Standard P \backslash Rightarrow P & I$ \backslash Rightarrow$ 1,2 \layout Standard \backslash end{fitch} \backslash ] \end_inset \layout Standard Este caso no había salido aún: resulta que el lado izquierdo del secuente está vacío. Quiere decir que no nos dan ninguna verdad en la que basarnos para demostrar que \begin_inset Formula $P\Rightarrow P$ \end_inset . ¿Por qué? Pues porque \begin_inset Formula $P\Rightarrow P$ \end_inset es cierto siempre, sin importar el valor de \begin_inset Formula $P$ \end_inset o de las demás fórmulas. \layout Standard Es mucho más cómodo e interesante resolver una de estas demostraciones, porque empiezas a trabajar directamente en la fórmula a la que quieres llegar. Pero cuidado, que hay algunas \emph on verdades absolutas \emph default (de las que son ciertas siempre) muy difíciles y largas de demostrar. \layout Standard Apunta: siempre que el lado izquierdo esté vacío, hay que empezar con una hipótesis. (¿qué otra cosa se puede hacer?). \layout Standard Para conseguir probar que \begin_inset Formula $P\Rightarrow P$ \end_inset hacemos lo de siempre: suponemos que \begin_inset Formula $P$ \end_inset e intentamos llegar a ver que \begin_inset Formula $P$ \end_inset es cierto. Como lo hemos supuesto en la primera línea, usamos la regla de \emph on iteración \emph default para copiarlo dentro, y acabamos la subdemostración mediante la \emph on introducción de la implicación \emph default . Y ya está todo hecho, en tres líneas. \layout Standard Fíjate en que \begin_inset Formula $P\Rightarrow P$ \end_inset es cierto porque \begin_inset Formula $\blacksquare\Rightarrow\blacksquare$ \end_inset y \begin_inset Formula $\square\Rightarrow\square$ \end_inset . Ya de paso, te recuerdo que también \begin_inset Formula $\square\Rightarrow\blacksquare$ \end_inset , pero \begin_inset Formula $\blacksquare\nRightarrow\square$ \end_inset . \layout Subsection Suponer lo contrario. \begin_inset Formula $\vdash\neg(P\wedge\neg P)$ \end_inset \layout Standard Otro sencillo, \begin_inset Formula $\vdash\neg(P\wedge\neg P)$ \end_inset . Se hace así: \layout Standard \begin_inset ERT status Collapsed \layout Standard \backslash [ \backslash begin{fitch} \layout Standard \backslash fh P \backslash wedge \backslash neg P & H \backslash \backslash \layout Standard \backslash fa P & E$ \backslash wedge$ 1 \backslash \backslash \layout Standard \backslash fa \backslash neg P & E$ \backslash wedge$ 1 \backslash \backslash \layout Standard \backslash neg (P \backslash wedge \backslash neg P) & I$ \backslash neg$ 1,2 \layout Standard \backslash end{fitch} \backslash ] \end_inset \layout Standard Todos sabemos que no pueden pasar dos cosas contrarias a la vez, pero ¿cómo lo demostramos? Hay que usar la \emph on reducción al absurdo \emph default : \layout Standard Supongamos que sí que pasa \begin_inset Formula $P\wedge\neg P$ \end_inset . Entonces pasa \begin_inset Formula $P$ \end_inset y pasa \begin_inset Formula $\neg P$ \end_inset , las dos a la vez, lo que es una contradicción. Por tanto, la suposición que hemos hecho no puede ser cierta; o sea que es falsa. Así se demuestra que \begin_inset Formula $\neg(P\wedge\neg P)$ \end_inset . \layout Standard Cuando veas algo tan \emph on claro \emph default y \emph on obvio \emph default como \begin_inset Formula $\neg(P\wedge\neg P)$ \end_inset , entonces lo contrario será \emph on claramente \emph default falso y absurdo. Por lo tanto, no te costará mucho demostrar que no se aguanta y que se contradice él solo. Una vez hecho esto, podemos asegurar que la fórmula original es cierta ya que su contrario es falso. \layout Subsection Éste parece sencillo. \begin_inset Formula $\vdash P\vee\neg P$ \end_inset \layout Standard A ver si \begin_inset Formula $\vdash P\vee\neg P$ \end_inset es tan obvio como dicen: \layout Standard \begin_inset ERT status Collapsed \layout Standard \backslash [ \backslash begin{fitch} \layout Standard \backslash fh \backslash neg (P \backslash vee \backslash neg P) & H \backslash \backslash \layout Standard \backslash fa \backslash fh P & H \backslash \backslash \layout Standard \backslash fa \backslash fa P \backslash vee \backslash neg P & I$ \backslash vee$ 2 \backslash \backslash \layout Standard \backslash fa \backslash fa \backslash neg (P \backslash vee \backslash neg P) & IT 1 \backslash \backslash \layout Standard \backslash fa \backslash neg P & I$ \backslash neg$ 2,3,4 \backslash \backslash \layout Standard \backslash fa \backslash fh \backslash neg P & H \backslash \backslash \layout Standard \backslash fa \backslash fa P \backslash vee \backslash neg P & I$ \backslash vee$ 6 \backslash \backslash \layout Standard \backslash fa \backslash fa \backslash neg (P \backslash vee \backslash neg P) & IT 1 \backslash \backslash \layout Standard \backslash fa \backslash neg \backslash neg P & I$ \backslash neg$ 6,7,8 \backslash \backslash \layout Standard \backslash fa P & E$ \backslash neg$ 9 \backslash \backslash \layout Standard \backslash neg \backslash neg (P \backslash vee \backslash neg P) & I$ \backslash neg$ 1,5,10 \backslash \backslash \layout Standard P \backslash vee \backslash neg P & E$ \backslash neg$ 11 \layout Standard \backslash end{fitch} \backslash ] \end_inset \layout Standard Uno de los más simples y largos que he encontrado. Parece que no sea necesario demostrarlo, porque todo el mundo sabe que entre \begin_inset Quotes eld \end_inset \emph on hoy es jueves \emph default \begin_inset Quotes erd \end_inset y \begin_inset Quotes eld \end_inset \emph on hoy no es jueves \emph default \begin_inset Quotes erd \end_inset , una de las dos es cierta (no pueden ser falsas las dos a la vez). \layout Standard Podríamos empezar pensando en el método de \emph on prueba por casos \emph default , porque de \begin_inset Formula $P$ \end_inset podemos deducir \begin_inset Formula $P\vee\neg P$ \end_inset , y de \begin_inset Formula $\neg P$ \end_inset podemos deducir \begin_inset Formula $P\vee\neg P$ \end_inset , o sea, la misma fórmula. Pero esto no sirve de nada, porque la regla de \emph on prueba por casos \emph default es la de \emph on eliminación de la disyunción \emph default , y no tenemos ninguna disyunción por eliminar; de hecho, tampoco tenemos la fórmula cierta \begin_inset Formula $A\vee B$ \end_inset tal que \begin_inset Formula $A\Rightarrow C$ \end_inset y \begin_inset Formula $B\Rightarrow C$ \end_inset , como pide la regla. En realidad, no tenemos ninguna fórmula que sepamos que sea cierta (el lado izquierdo del secuente está vacío). \layout Standard Sabemos que hay que empezar con una hipótesis (no hay otra alternativa). Como queda bastante claro que \begin_inset Formula $P\vee\neg P$ \end_inset es cierto, también puede parecer fácil demostrar que su contrario, \begin_inset Formula $\neg(P\vee\neg P)$ \end_inset , es falso. Así que usaremos la \emph on reducción al absurdo \emph default : haciendo esa suposición en la línea 1, hay que intentar llegar a una contradic ción, la que sea. \layout Standard Yo me propuse llegar a la contradicción \begin_inset Formula $\neg P$ \end_inset y \begin_inset Formula $P$ \end_inset . Pero no tenemos ninguna de esas fórmulas; ¿cómo las sacamos? Pues volvemos a hacer \emph on reducción al absurdo \emph default : para ver que \begin_inset Formula $\neg P$ \end_inset , vamos a suponer que \begin_inset Formula $P$ \end_inset para llegar a una contradicción. Como otras veces, va muy bien aprovechar las posibilidades que da la \emph on introducción de la disyunción \emph default : al suponer que \begin_inset Formula $P$ \end_inset , podremos convertirlo en \begin_inset Formula $P\vee\neg P$ \end_inset para buscar la contradicción. Como tenemos el \begin_inset Formula $\neg(P\vee\neg P)$ \end_inset arriba del todo, lo podemos usar para acabar demostrando que \begin_inset Formula $\neg P$ \end_inset . Lo mismo haremos para demostrar que \begin_inset Formula $P$ \end_inset , pero esta vez suponiendo \begin_inset Formula $\neg P$ \end_inset . \layout Standard Al haber llegado a \begin_inset Formula $P$ \end_inset y \begin_inset Formula $\neg P$ \end_inset después de suponer \begin_inset Formula $\neg(P\vee\neg P)$ \end_inset , se ve que esta fórmula no puede ser cierta, así que su negación, \begin_inset Formula $\neg\neg(P\vee\neg P)$ \end_inset , lo es. Por \emph on eliminación de la negación \emph default , nos queda la fórmula que buscamos: \begin_inset Formula $P\vee\neg P$ \end_inset . \layout Standard Lo he hecho de esta manera para que quedara bastante simétrico, pero se puede hacer más corto buscando otra contradicción, por ejemplo \begin_inset Formula $P\vee\neg P$ \end_inset y \begin_inset Formula $\neg(P\vee\neg P)$ \end_inset . Quedaría así: \layout Standard \begin_inset ERT status Collapsed \layout Standard \backslash [ \backslash begin{fitch} \layout Standard \backslash fh \backslash neg (P \backslash vee \backslash neg P) & H \backslash \backslash \layout Standard \backslash fa \backslash fh P & H \backslash \backslash \layout Standard \backslash fa \backslash fa P \backslash vee \backslash neg P & I$ \backslash vee$ 2 \backslash \backslash \layout Standard \backslash fa \backslash fa \backslash neg (P \backslash vee \backslash neg P) & IT 1 \backslash \backslash \layout Standard \backslash fa \backslash neg P & I$ \backslash neg$ 2,3,4 \backslash \backslash \layout Standard \backslash fa P \backslash vee \backslash neg P & I$ \backslash vee$ 5 \backslash \backslash \layout Standard \backslash fa \backslash neg (P \backslash vee \backslash neg P) & IT 1 \backslash \backslash \layout Standard \backslash neg \backslash neg (P \backslash vee \backslash neg P) & I$ \backslash neg$ 1,6,7 \backslash \backslash \layout Standard P \backslash vee \backslash neg P & E$ \backslash neg$ 8 \layout Standard \backslash end{fitch} \backslash ] \end_inset \layout Subsection Uno interesante. \begin_inset Formula $P\vee Q,\ \neg P\vdash Q$ \end_inset \layout Standard Otro que también parece fácil: \begin_inset Formula $P\vee Q,\ \neg P\vdash Q$ \end_inset . A ver: \layout Standard \begin_inset ERT status Collapsed \layout Standard \backslash [ \backslash begin{fitch} \layout Standard P \backslash vee Q \backslash \backslash \layout Standard \backslash neg P \backslash \backslash \layout Standard \backslash fh P & H \backslash \backslash \layout Standard \backslash fa \backslash fh \backslash neg Q & H \backslash \backslash \layout Standard \backslash fa \backslash fa \backslash neg P & IT 2 \backslash \backslash \layout Standard \backslash fa \backslash fa P & IT 3 \backslash \backslash \layout Standard \backslash fa \backslash neg \backslash neg Q & I$ \backslash neg$ 4,5,6 \backslash \backslash \layout Standard \backslash fa Q & E$ \backslash neg$ 7 \backslash \backslash \layout Standard \backslash fh Q & H \backslash \backslash \layout Standard \backslash fa Q & IT 9 \backslash \backslash \layout Standard Q & E$ \backslash vee$ 1,8,10 \layout Standard \backslash end{fitch} \backslash ] \end_inset \layout Standard Es muy sencillo de entender por cualquiera: se cumple \begin_inset Formula $P\vee Q$ \end_inset , pero \begin_inset Formula $P$ \end_inset es falso, así que el cierto es \begin_inset Formula $Q$ \end_inset . \layout Standard Se puede hacer de varias formas, pero en algún momento tendrás que usar la \emph on eliminación de la disyunción \emph default para hacer algo con el \begin_inset Formula $P\vee Q$ \end_inset . Vamos a intentar probar que tanto \begin_inset Formula $P$ \end_inset como \begin_inset Formula $Q$ \end_inset llevan al mismo sitio, que será nuestra fórmula objetivo \begin_inset Formula $Q$ \end_inset (ya que se puede, vamos directamente a por \begin_inset Formula $Q$ \end_inset ). \layout Standard Abrimos la subdemostración suponiendo que \begin_inset Formula $P$ \end_inset , y tenemos que ver que \begin_inset Formula $Q$ \end_inset . No es muy difícil porque tenemos el \begin_inset Formula $\neg P$ \end_inset en la línea 2; eso ayuda a contradecir lo que queramos. Como lo que buscamos es \begin_inset Formula $Q$ \end_inset , suponemos \begin_inset Formula $\neg Q$ \end_inset y por \emph on reducción al absurdo \emph default obtenemos \begin_inset Formula $\neg\neg Q$ \end_inset , que es \begin_inset Formula $Q$ \end_inset . \layout Standard El otro camino, cuando se supone que \begin_inset Formula $Q$ \end_inset es cierto, lleva directamente a \begin_inset Formula $Q$ \end_inset . \layout Standard Por lo tanto, ambos caminos van a \begin_inset Formula $Q$ \end_inset y por la \emph on eliminación de la disyunción \emph default demostramos que \begin_inset Formula $Q$ \end_inset es cierto siempre. \layout Subsection Éste me lo pusieron en un examen. \begin_inset Formula $A\vee B,\ A\Rightarrow C,\ \neg D\Rightarrow\neg B\vdash C\vee D$ \end_inset \layout Standard En el examen final de \emph on ILO \emph default me pusieron \begin_inset Formula $A\vee B,\ A\Rightarrow C,\ \neg D\Rightarrow\neg B\vdash C\vee D$ \end_inset , y me pasé mucho, mucho rato hasta que lo conseguí: \layout Standard \begin_inset ERT status Collapsed \layout Standard \backslash [ \backslash begin{fitch} \layout Standard A \backslash vee B \backslash \backslash \layout Standard A \backslash Rightarrow C \backslash \backslash \layout Standard \backslash neg D \backslash Rightarrow \backslash neg B \backslash \backslash \layout Standard \backslash fh A & H \backslash \backslash \layout Standard \backslash fa C & E$ \backslash Rightarrow$ 2,4 \backslash \backslash \layout Standard \backslash fa C \backslash vee D & I$ \backslash vee$ 5 \backslash \backslash \layout Standard \backslash fh B & H \backslash \backslash \layout Standard \backslash fa \backslash fh \backslash neg D & H \backslash \backslash \layout Standard \backslash fa \backslash fa \backslash neg B & E$ \backslash Rightarrow$ 3,8 \backslash \backslash \layout Standard \backslash fa \backslash fa B & IT 7 \backslash \backslash \layout Standard \backslash fa \backslash neg \backslash neg D & I$ \backslash neg$ 8,9,10 \backslash \backslash \layout Standard \backslash fa D & E$ \backslash neg$ 11 \backslash \backslash \layout Standard \backslash fa C \backslash vee D & I$ \backslash vee$ 12 \backslash \backslash \layout Standard C \backslash vee D & E$ \backslash vee$ 1,6,13 \layout Standard \backslash end{fitch} \backslash ] \end_inset \layout Standard Fíjate en que el resultado que buscamos, \begin_inset Formula $C\vee D$ \end_inset , es una disyunción. Como ya conoces la \emph on introducción de la disyunción \emph default , podrías buscar simplemente que \begin_inset Formula $C$ \end_inset , y luego utilizar esta regla para sacar \begin_inset Formula $C\vee D$ \end_inset . Si no encontraras que \begin_inset Formula $C$ \end_inset es cierta, pues podrías probar con \begin_inset Formula $D$ \end_inset , porque si \begin_inset Formula $D$ \end_inset es cierta entonces \begin_inset Formula $C\vee D$ \end_inset lo es y ya hemos acabado. \layout Standard Desgraciadamente, \begin_inset Formula $C$ \end_inset no es cierta siempre, y \begin_inset Formula $D$ \end_inset tampoco es cierta siempre (en cambio \begin_inset Formula $C\vee D$ \end_inset sí que lo es siempre, y eso es lo que queremos demostrar). Después de comprobar esto, habrá que buscar otro método que trabaje con las dos fórmulas \begin_inset Formula $C$ \end_inset y \begin_inset Formula $D$ \end_inset , a la vez, porque parece que si cogemos una sola sin mirar la otra, no proporciona mucha información. \layout Standard Para usar el \begin_inset Formula $A\vee B$ \end_inset habrá que usar la \emph on prueba por casos \emph default . Intentaremos llegar a que tanto \begin_inset Formula $A$ \end_inset como \begin_inset Formula $B$ \end_inset llevan a \begin_inset Formula $C\vee D$ \end_inset , porque si lo conseguimos ya habremos acabado. \layout Standard \begin_inset Formula $A$ \end_inset implica \begin_inset Formula $C$ \end_inset , y si \begin_inset Formula $C$ \end_inset es cierto también lo es \begin_inset Formula $C\vee D$ \end_inset , así que \begin_inset Formula $A$ \end_inset implica \begin_inset Formula $C\vee D$ \end_inset . \layout Standard Con \begin_inset Formula $B$ \end_inset , lo que sabemos no la relaciona con la \begin_inset Formula $C$ \end_inset sino con la \begin_inset Formula $D$ \end_inset . Queremos \begin_inset Formula $C\vee D$ \end_inset . Difícilmente conseguiremos que \begin_inset Formula $C\vee D$ \end_inset se cumpla gracias a \begin_inset Formula $C$ \end_inset , así que intentaremos que sea \begin_inset Formula $D$ \end_inset la cierta. Para ello, usamos \emph on reducción al absurdo \emph default : supongamos que \begin_inset Formula $D$ \end_inset es falso, entonces se cumple \begin_inset Formula $\neg B$ \end_inset por la fórmula de la línea 3. Pero estábamos dentro de la suposición de que \begin_inset Formula $B$ \end_inset era cierto, así que nuestra hipótesis \begin_inset Formula $\neg D$ \end_inset no puede ser cierta, luego \begin_inset Formula $D$ \end_inset es cierta, y por tanto \begin_inset Formula $C\vee D$ \end_inset también. \layout Standard Como \begin_inset Formula $A\vee B$ \end_inset es cierto, y los dos caminos nos llevan a \begin_inset Formula $C\vee D$ \end_inset , acabamos viendo que \begin_inset Formula $C\vee D$ \end_inset siempre es cierto. \layout Standard Si tienes práctica trabajando con fórmulas lógicas, habrás visto que \begin_inset Formula $\neg D\Rightarrow\neg B$ \end_inset es \begin_inset Formula $B\Rightarrow D$ \end_inset . Eso simplifica mucho el problema y ayuda a entenderlo antes. De todas formas, no puedes cambiar \begin_inset Formula $\neg D\Rightarrow\neg B$ \end_inset por \begin_inset Formula $B\Rightarrow D$ \end_inset directamente, sino que hay que hacerlo paso a paso. \layout Subsection Uno \begin_inset Quotes eld \end_inset corto \begin_inset Quotes erd \end_inset . \begin_inset Formula $A\Longleftrightarrow B\vdash(A\wedge B)\vee(\neg A\wedge\neg B)$ \end_inset \layout Standard Parece fácil: si dos expresiones son equivalentes, es porque son las dos ciertas, o son las dos falsas. He podido demostrar la validez de \begin_inset Formula $A\Longleftrightarrow B\vdash(A\wedge B)\vee(\neg A\wedge\neg B)$ \end_inset así: \layout Standard \begin_inset ERT status Collapsed \layout Standard \backslash [ \backslash begin{fitch} \layout Standard (A \backslash Rightarrow B) \backslash wedge (B \backslash Rightarrow A) \backslash \backslash \layout Standard \backslash fh \backslash neg (A \backslash vee \backslash neg A) & H \backslash \backslash \layout Standard \backslash fa \backslash fh A & H \backslash \backslash \layout Standard \backslash fa \backslash fa A \backslash vee \backslash neg A & I$ \backslash vee$ 3 \backslash \backslash \layout Standard \backslash fa \backslash fa \backslash neg (A \backslash vee \backslash neg A) & IT 2 \backslash \backslash \layout Standard \backslash fa \backslash neg A & I$ \backslash neg$ 3,4,5 \backslash \backslash \layout Standard \backslash fa A \backslash vee \backslash neg A & I$ \backslash vee$ 6 \backslash \backslash \layout Standard \backslash fa \backslash neg (A \backslash vee \backslash neg A) & IT 2 \backslash \backslash \layout Standard \backslash neg \backslash neg (A \backslash vee \backslash neg A) & I$ \backslash neg$ 2,7,8 \backslash \backslash \layout Standard A \backslash vee \backslash neg A & E$ \backslash neg$ 9 \backslash \backslash \layout Standard \backslash fh A & H \backslash \backslash \layout Standard \backslash fa A \backslash Rightarrow B & E$ \backslash wedge$ 1 \backslash \backslash \layout Standard \backslash fa B & E$ \backslash Rightarrow$ 12,11 \backslash \backslash \layout Standard \backslash fa A \backslash wedge B & I$ \backslash wedge$ 11,13 \backslash \backslash \layout Standard \backslash fa (A \backslash wedge B) \backslash vee ( \backslash neg A \backslash wedge \backslash neg B) & I$ \backslash vee$ 14 \backslash \backslash \layout Standard \backslash fh \backslash neg A & H \backslash \backslash \layout Standard \backslash fa \backslash fh B & H \backslash \backslash \layout Standard \backslash fa \backslash fa B \backslash Rightarrow A & E$ \backslash wedge$ 1 \backslash \backslash \layout Standard \backslash fa \backslash fa A & E$ \backslash Rightarrow$ 18,17 \backslash \backslash \layout Standard \backslash fa \backslash fa \backslash neg A & IT 16 \backslash \backslash \layout Standard \backslash fa \backslash neg B & I$ \backslash neg$ 17,19,20 \backslash \backslash \layout Standard \backslash fa \backslash neg A \backslash wedge \backslash neg B & I$ \backslash wedge$ 16,21 \backslash \backslash \layout Standard \backslash fa (A \backslash wedge B) \backslash vee ( \backslash neg A \backslash wedge \backslash neg B) & I$ \backslash vee$ 22 \backslash \backslash \layout Standard (A \backslash wedge B) \backslash vee ( \backslash neg A \backslash wedge \backslash neg B) & E$ \backslash vee$ 10,15,23 \layout Standard \backslash end{fitch} \backslash ] \end_inset \layout Standard Lo primero: no podemos poner \begin_inset Formula $A\Longleftrightarrow B$ \end_inset porque no tenemos reglas para el \begin_inset Formula $\Longleftrightarrow$ \end_inset . Como casi no se usa, cuando sale un \begin_inset Formula $\Longleftrightarrow$ \end_inset se permite cambiarlo por \begin_inset Formula $(A\Rightarrow B)\wedge(B\Rightarrow A)$ \end_inset , que es lo mismo. \layout Standard Bueno, esto es lo único que se me ha ocurrido... Te dejo como ejercicio el buscar una forma más corta (si es que la hay). Lo que yo he hecho es dejar escrito que \begin_inset Formula $A\vee\neg A$ \end_inset es cierto (este ejercicio ya salió, aquí he repetido los mismos pasos). Una vez sé que se cumple \begin_inset Formula $A\vee\neg A$ \end_inset , veo que tanto el caso \begin_inset Formula $A$ \end_inset como el caso \begin_inset Formula $\neg A$ \end_inset llevan a la misma fórmula, que es la solución. \layout Section Cosas incorrectas \layout Standard Errores comunes que no debes hacer. Recuerda que un profesor de lógica corregirá tus ejercicios con un \emph on cierto \emph default o un \emph on falso \emph default , así que aprende a hacerlo perfecto. \layout Subsection Introducción y eliminación de \emph on \begin_inset Quotes eld \end_inset lo que me venga bien \begin_inset Quotes erd \end_inset \layout Standard Las reglas de \emph on introducción \emph default y \emph on eliminación \emph default no son para que puedas escribir lo que tú quieras, sino para ayudarte a utilizar o generar una fórmula con un operador concreto. \layout Standard Por eso, si tienes \begin_inset Formula $P$ \end_inset no puedes decir \begin_inset Quotes eld \end_inset \emph on pues ahora hago \emph default introducción de negación \emph on y consigo \begin_inset Formula $\neg P$ \end_inset , que es lo que me hacía falta \emph default \begin_inset Quotes erd \end_inset . Hay unos cuantos requisitos para cada regla, y si no se cumplen no las puedes aplicar. \layout Standard Ejemplo: la regla de \emph on eliminación de la implicación \emph default no permite acceder así a las fórmulas de la primera línea. \layout Standard \begin_inset ERT status Collapsed \layout Standard \backslash [ \backslash begin{fitch} \layout Standard P \backslash Rightarrow Q \backslash wedge R \backslash \backslash \layout Standard Q \backslash wedge R & E$ \backslash Rightarrow$ 1,1 \layout Standard \backslash end{fitch} { \backslash textcolor{red}{ \backslash bigotimes INCORRECTO \backslash bigotimes}} \backslash ] \end_inset \layout Standard Para poder hacerlo, haría falta estar seguros de que \begin_inset Formula $P$ \end_inset es cierto siempre; entonces se podría aplicar la regla, escribiendo bien los números de línea. \layout Subsection Iterar algo de una subdemostración no accesible \layout Standard Dentro de la demostración principal (la que va de la primera a la última línea), podemos abrir \emph on demostraciones hijas \emph default ( \emph on subdemostraciones \emph default ). Dentro de una subdemostración también podemos tener una \emph on subsubdemostración \emph default , que tendría como padre a la subdemostración y como abuelo a la demostración principal. \layout Standard Para ilustrar, pongo el ejemplo de \begin_inset Formula $A\vee B,\ A\Rightarrow C,\ \neg D\Rightarrow\neg B\vdash C\vee D$ \end_inset : \layout Standard \begin_inset ERT status Collapsed \layout Standard \backslash [ \backslash begin{fitch} \layout Standard A \backslash vee B \backslash \backslash \layout Standard A \backslash Rightarrow C \backslash \backslash \layout Standard \backslash neg D \backslash Rightarrow \backslash neg B \backslash \backslash \layout Standard \backslash fh A & H \backslash \backslash \layout Standard \backslash fa C & E$ \backslash Rightarrow$ 2,4 \backslash \backslash \layout Standard \backslash fa C \backslash vee D & I$ \backslash vee$ 5 \backslash \backslash \layout Standard \backslash fh B & H \backslash \backslash \layout Standard \backslash fa \backslash fh \backslash neg D & H \backslash \backslash \layout Standard \backslash fa \backslash fa \backslash neg B & E$ \backslash Rightarrow$ 3,8 \backslash \backslash \layout Standard \backslash fa \backslash fa B & IT 7 \backslash \backslash \layout Standard \backslash fa \backslash neg \backslash neg D & I$ \backslash neg$ 8,9,10 \backslash \backslash \layout Standard \backslash fa D & E$ \backslash neg$ 11 \backslash \backslash \layout Standard \backslash fa C \backslash vee D & I$ \backslash vee$ 12 \backslash \backslash \layout Standard C \backslash vee D & E$ \backslash vee$ 1,6,13 \layout Standard \backslash end{fitch} \backslash ] \end_inset \layout Standard Pues bien, una demostración cualquiera sólo puede acceder a las fórmulas de dentro de sí misma, a las de su padre, a las del padre de su padre, a las del padre del padre del padre, ... Me parece que a todos esos se les llama \emph on ancestros \emph default , así que: \emph on una demostración puede acceder a sí misma y a sus ancestros \emph default . \layout Standard Por ejemplo, si estamos en la línea 10, las reglas pueden usar fórmulas de los siguientes sitios: \layout Itemize de la demostración actual (líneas 8 y 9 por ahora). \layout Itemize de la demostración padre de la 8-10, o sea, de la línea 7. \layout Itemize de la demostración padre de la que empieza en la 7, o sea, líneas 1 a 3. \layout Standard En ningún caso puede usar las fórmulas de las líneas 4 a 6, que es la demostraci ón \emph on tía \emph default de la actual (hermana del padre), porque toda esa demostración se basa en la hipótesis de que \begin_inset Formula $A$ \end_inset (línea 4), y ya hemos dejado de hacer esa suposición. \layout Standard En lenguaje lógico, se dice que una fórmula \begin_inset Formula $A$ \end_inset es \emph on actual \emph default en la fórmula \begin_inset Formula $B$ \end_inset si estando en \begin_inset Formula $B$ \end_inset se puede usar \begin_inset Formula $A$ \end_inset . Para que esto se cumpla, \begin_inset Formula $A$ \end_inset tiene que haberse escrito antes que \begin_inset Formula $B$ \end_inset , y algún ancestro de \begin_inset Formula $B$ \end_inset tiene que ser padre de \begin_inset Formula $A$ \end_inset . \layout Standard O sea, que para demostrar \begin_inset Formula $P\wedge Q$ \end_inset no se puede hacer esto: \layout Standard \begin_inset ERT status Collapsed \layout Standard \backslash [ \backslash begin{fitch} \layout Standard \backslash fh P & H \backslash \backslash \layout Standard \backslash fa \backslash fh Q & H \backslash \backslash \layout Standard \backslash fa \backslash fa P \backslash wedge Q & I$ \backslash wedge$ 1,2 \backslash \backslash \layout Standard P \backslash wedge Q & IT 3 \layout Standard \backslash end{fitch} { \backslash textcolor{red}{ \backslash bigotimes INCORRECTO \backslash bigotimes}} \backslash ] \end_inset \layout Subsection Colocar mal los paréntesis \layout Standard Cuando he escrito las definiciones de las reglas, he usado las letras \begin_inset Formula $A$ \end_inset y \begin_inset Formula $B$ \end_inset , pero éstas pueden representar a cualquier expresión. \layout Standard Por ejemplo, aquí se hace la \emph on introducción de la negación \emph default , en la que -según la regla- se supone una fórmula \begin_inset Formula $A$ \end_inset , se llega a una contradicción, y se concluye que \begin_inset Formula $\neg A$ \end_inset , o sea, la fórmula original, pero negada. Veamos: \layout Standard \begin_inset ERT status Collapsed \layout Standard \backslash [ \backslash begin{fitch*} \layout Standard 1 & \backslash fh P \backslash Rightarrow Q & H \backslash \backslash \layout Standard \backslash ldots & \backslash fa \backslash ldots \backslash \backslash \layout Standard 7 & \backslash neg P \backslash Rightarrow Q & I$ \backslash neg$ 1, \backslash ldots \layout Standard \backslash end{fitch*} { \backslash textcolor{red}{ \backslash bigotimes INCORRECTO \backslash bigotimes}} \backslash ] \end_inset \layout Standard Supongo que queda claro que el \begin_inset Formula $A$ \end_inset que sale en la regla representa a \begin_inset Formula $P\Rightarrow Q$ \end_inset en este ejemplo. El problema viene cuando hacemos el \begin_inset Formula $\neg A$ \end_inset . La negación de \begin_inset Formula $P\Rightarrow Q$ \end_inset no es \begin_inset Formula $\neg P\Rightarrow Q$ \end_inset , sino \begin_inset Formula $\neg(P\Rightarrow Q)$ \end_inset . Es necesario el paréntesis porque si no se pone, sólo afecta a \begin_inset Formula $P$ \end_inset . \layout Standard Si no sabes cuándo poner paréntesis, ponlos siempre y luego quita los que no hagan falta. Por ejemplo, si tienes que escribir que \begin_inset Formula $\neg P\vee R$ \end_inset implica a \begin_inset Formula $R\wedge Q$ \end_inset , encierra cada expresión entre paréntesis y escribe \begin_inset Formula $(\neg P\vee R)\Rightarrow(R\wedge Q)$ \end_inset . Así no te has equivocado. Ahora aprende cuándo es posible quitar los paréntesis, y quita todos los que puedas. En este caso, los dos se pueden quitar y queda \begin_inset Formula $\neg P\vee R\Rightarrow R\wedge Q$ \end_inset . \layout Subsection Acabar dentro de una subdemostración \layout Standard No puedes acabar la deducción dentro de una subdemostración. La última línea no tiene que tener ninguna rayita vertical a la izquierda. \layout Standard La razón es que todo lo de dentro de la subdemostración es válido sólo cuando se cumple la suposición, y lo que nos piden en el enunciado es demostrar que lo que hay a la derecha del \begin_inset Formula $\vdash$ \end_inset se cumple \emph on siempre \emph default . \layout Standard Ejemplo de alguien con mucha cara que intenta demostrar \begin_inset Formula $P\wedge Q$ \end_inset : \layout Standard \begin_inset ERT status Collapsed \layout Standard \backslash [ \backslash begin{fitch} \layout Standard \backslash fh P & H \backslash \backslash \layout Standard \backslash fa \backslash fh Q & H \backslash \backslash \layout Standard \backslash fa \backslash fa P \backslash wedge Q & I$ \backslash wedge$ 1,2 \layout Standard \backslash end{fitch} { \backslash textcolor{red}{ \backslash bigotimes INCORRECTO \backslash bigotimes}} \backslash ] \end_inset \layout Standard Se ha supuesto que \begin_inset Formula $P$ \end_inset , y también que \begin_inset Formula $Q$ \end_inset . En ese caso, claro que es cierto que \begin_inset Formula $P\wedge Q$ \end_inset , pero sólo en ese caso. No podemos asegurar a nadie que \begin_inset Formula $P\wedge Q$ \end_inset sea cierto siempre. Por tanto, hay que ir cerrando las dos demostraciones (primero la de dentro, luego la de fuera) para sacar alguna conclusión que sea válida siempre. \layout Standard Tampoco se podría hacer eso de \emph on iterar \emph default en la línea 4. Ya lo he explicado hace algunos apartados. \layout Subsection Saltarse pasos \layout Standard Aunque conozcas equivalencias entre fórmulas, es mucho mejor si no las usas. Por ejemplo, si te toca escribir la negación de \begin_inset Formula $\neg P$ \end_inset , no puedes escribir \begin_inset Formula $P$ \end_inset directamente, sino que tienes que poner \begin_inset Formula $\neg\neg P$ \end_inset . \layout Standard Piensa que no todo es tan obvio, y que te pueden pedir demostrar cosas como \begin_inset Formula $P\vdash\neg\neg P$ \end_inset , en donde si pudieras usar las simplificaciones, no habría que trabajar casi nada. \layout Standard Por ejemplo, pasar de tener \begin_inset Formula $\neg(A\vee B)$ \end_inset en una línea a tener \begin_inset Formula $\neg A\wedge\neg B$ \end_inset en la siguiente no se puede justificar con ninguna de las 9 reglas. Pero si consigues demostrar y entender que \begin_inset Formula $\neg(A\vee B)\vdash\neg A\wedge\neg B$ \end_inset , podrías añadírtelo como un regla más para usarla en futuras demostraciones. Doy varias de éstas en la siguiente sección. \layout Section Complicándolo un poco más \layout Standard Aquí acabo de explicar todo lo que me enseñaron (aunque no lo usamos mucho). Lo de los cuantificadores es importante pero más lioso. \layout Subsection Reglas de cierto y falso \layout Standard Podemos trabajar directamente con los valores \begin_inset Formula $\blacksquare$ \end_inset ( \emph on cierto \emph default ) y \begin_inset Formula $\square$ \end_inset ( \emph on falso \emph default ), y también meterlos o sacarlos de nuestra demostración con reglas sencillas. \layout Subsubsection Introducción de cierto \layout Standard Ésta es la más fácil que hay: \layout Standard \begin_inset ERT status Collapsed \layout Standard \backslash [ \backslash begin{fitch*} \layout Standard \backslash hline \layout Standard & \backslash blacksquare & I$ \backslash blacksquare$ \layout Standard \backslash end{fitch*} \backslash ] \end_inset \layout Standard O sea, que siempre, y sin ningún requisito, podemos dejar escrito que \begin_inset Formula $\blacksquare$ \end_inset es cierto, porque siempre lo es. \layout Subsubsection Eliminación de falso \layout Standard Una regla muy divertida: \layout Standard \begin_inset ERT status Collapsed \layout Standard \backslash [ \backslash begin{fitch*} \layout Standard n & \backslash square \backslash \backslash \layout Standard \backslash hline \layout Standard & A & E$ \backslash square$ n \layout Standard \backslash end{fitch*} \backslash ] \end_inset \layout Standard Explicación: si hemos llegado a la conclusión de que \begin_inset Formula $\square$ \end_inset es cierto, entonces ya hemos llegado al extremo en el que podemos inventarnos lo que queramos y decir que es cierto; al menos tan cierto como que \begin_inset Formula $\square$ \end_inset ( \emph on falso \emph default ) es cierto. \layout Standard A esta regla le llaman \emph on ex falso quodlibet sequitur \emph default , algo como \begin_inset Quotes eld \end_inset \emph on de falso puede salir cualquier cosa \emph default \begin_inset Quotes erd \end_inset . \layout Subsection Reglas de cuantificadores \layout Standard Estamos muy limitados si sólo podemos usar \begin_inset Formula $P$ \end_inset , \begin_inset Formula $Q$ \end_inset , \begin_inset Formula $R$ \end_inset , ... para traducir frases a lenguaje lógico. Los cuantificadores nos dejarán hacer muchas más cosas. \layout Subsubsection Qué es eso \layout Standard No podré explicarlo todo porque hace falta entender muchos conceptos previos, pero lo digo por encima. Primero, unos cambios: \layout Standard Ahora no sólo hablaremos de cosas generales ( \emph on llueve \emph default , \emph on hace calor \emph default , etc.), sino que tendremos un \emph on dominio \emph default de cosas conocidas, y tendremos que decir qué propiedad es cierta para cada elemento. \layout Standard Ejemplo: tenemos el dominio \begin_inset Formula $\{ p,\ t,\ r\}$ \end_inset , que representan a la pantalla, el teclado, y el ratón de un ordenador. \layout Standard Añadimos una \emph on letra de predicado \emph default (ya no se llaman \emph on letras proposicionales \emph default ) \begin_inset Formula $E$ \end_inset , tal que cuando ponemos \begin_inset Formula $Ex$ \end_inset (leído \begin_inset Quotes eld \end_inset \emph on \begin_inset Formula $E$ \end_inset de \begin_inset Formula $x$ \end_inset \emph default \begin_inset Quotes erd \end_inset , escrito todo junto) queremos decir que \emph on \begin_inset Formula $x$ \end_inset es un dispositivo de entrada \emph default . También tenemos \begin_inset Formula $Sx$ \end_inset para decir que \emph on \begin_inset Formula $x$ \end_inset es un dispositivo de salida \emph default , y \begin_inset Formula $Tx$ \end_inset que significa \emph on \begin_inset Formula $x$ \end_inset necesita tinta para funcionar \emph default . \layout Standard Ahora sabemos que se cumplen \begin_inset Formula $Et$ \end_inset , \begin_inset Formula $Er$ \end_inset , \begin_inset Formula $Sp$ \end_inset y ninguna más. \layout Standard Los cuantificadores nos permitirán escribir verdades que hagan referencia a algunos elementos del dominio. Hay dos cuantificadores: \layout Itemize El cuantificador universal: \begin_inset Formula $\forall$ \end_inset . Cuando se pone \begin_inset Formula $\forall xPx$ \end_inset ( \begin_inset Quotes eld \end_inset \emph on para todo \begin_inset Formula $x$ \end_inset , \begin_inset Formula $P$ \end_inset de \begin_inset Formula $x$ \end_inset \emph default \begin_inset Quotes erd \end_inset ), se quiere decir que todos los elementos del dominio cumplen la propiedad \begin_inset Formula $P$ \end_inset . \layout Itemize El cuantificador existencial: \begin_inset Formula $\exists$ \end_inset . \begin_inset Formula $\exists xPx$ \end_inset ( \begin_inset Quotes eld \end_inset \emph on existe un \begin_inset Formula $x$ \end_inset tal que \begin_inset Formula $P$ \end_inset de \begin_inset Formula $x$ \end_inset \emph default \begin_inset Quotes erd \end_inset ) quiere decir que al menos un elemento del dominio cumple la propiedad \begin_inset Formula $P$ \end_inset . \layout Standard Por ejemplo, aquí son ciertas las siguientes fórmulas: \begin_inset Formula $\forall x(Ex\vee Sx)$ \end_inset , \begin_inset Formula $\neg\exists xTx$ \end_inset , \begin_inset Formula $\forall x(Tx\Rightarrow\neg Ex)$ \end_inset , \begin_inset Formula $\exists xEx\wedge\exists xSx$ \end_inset y muchas más. Los cuantificadores tienen tanta prioridad como el \begin_inset Formula $\neg$ \end_inset . \layout Standard Las reglas explicadas aquí trabajarán con \emph on sustituciones libres \emph default . Lo siento por no decir qué es, pero es que no quiero salirme del tema. \layout Subsubsection Introducción del existencial \layout Standard Si vemos una prueba de su existencia, podemos decir que una propiedad se cumple para algún elemento: \layout Standard \begin_inset ERT status Collapsed \layout Standard \backslash [ \backslash begin{fitch*} \layout Standard n & A \backslash {t/x \backslash } \backslash \backslash \layout Standard \backslash hline \layout Standard & \backslash exists x A & I$ \backslash exists$ n,t \layout Standard \backslash end{fitch*} \backslash ] \end_inset \layout Standard Lo de \begin_inset Formula $A\{ t/x\}$ \end_inset es una \emph on sustitución \emph default (se lee \begin_inset Quotes eld \end_inset \emph on \begin_inset Formula $t$ \end_inset sobre \begin_inset Formula $x$ \end_inset \emph default \begin_inset Quotes erd \end_inset y consiste en cambiar \begin_inset Formula $x$ \end_inset por \begin_inset Formula $t$ \end_inset ). \layout Standard Esta regla quiere decir que si vemos \begin_inset Formula $At$ \end_inset , donde \begin_inset Formula $t$ \end_inset es un elemento, podemos decir que \begin_inset Formula $\exists xAx$ \end_inset , porque sabemos que cuando \begin_inset Formula $x$ \end_inset es \begin_inset Formula $t$ \end_inset sí que se cumple. \layout Subsubsection Eliminación del existencial \layout Standard Sacar algo cierto de un \begin_inset Formula $\exists xPx$ \end_inset cuesta, pero se hace así: \layout Standard \begin_inset ERT status Collapsed \layout Standard \backslash [ \backslash begin{fitch*} \layout Standard m & \backslash exists x A \backslash \backslash \layout Standard n & \backslash fh A \backslash {a/x \backslash } & H \backslash \backslash \layout Standard p & \backslash fa B \backslash \backslash \layout Standard \backslash hline \layout Standard & B & E$ \backslash exists$ m,n,p,a \layout Standard \backslash end{fitch*} \backslash ] \end_inset \layout Standard O sea, que si uno de los \begin_inset Formula $A$ \end_inset implica \begin_inset Formula $B$ \end_inset , entonces sabemos que \begin_inset Formula $B$ \end_inset , porque sabemos que uno de los \begin_inset Formula $A$ \end_inset es cierto. No debe aparecer ninguna \begin_inset Formula $a$ \end_inset en \begin_inset Formula $B$ \end_inset ni en ninguna hipótesis accesible (perdón por las frases crípticas; son parte de la teoría). \layout Subsubsection Introducción del universal \layout Standard Ésta es bastante fácil: \layout Standard \begin_inset ERT status Collapsed \layout Standard \backslash [ \backslash begin{fitch*} \layout Standard n & A \backslash \backslash \layout Standard \backslash hline \layout Standard & \backslash forall x A & I$ \backslash forall$ n \layout Standard \backslash end{fitch*} \backslash ] \end_inset \layout Standard O sea, que si \begin_inset Formula $A$ \end_inset se cumple siempre, se cumple para cualquier valor de \begin_inset Formula $x$ \end_inset . No puede haber ninguna \begin_inset Formula $x$ \end_inset \emph on libre \emph default en ninguna hipótesis accesible. \layout Subsubsection Eliminación del universal \layout Standard Otra fácil de entender: \layout Standard \begin_inset ERT status Collapsed \layout Standard \backslash [ \backslash begin{fitch*} \layout Standard n & \backslash forall x A \backslash \backslash \layout Standard \backslash hline \layout Standard & A \backslash {t/x \backslash } & E$ \backslash forall$ n,t \layout Standard \backslash end{fitch*} \backslash ] \end_inset \layout Standard Si sabemos que \begin_inset Formula $A$ \end_inset se cumple para cualquier elemento, entonces podemos elegir un elemento cualquiera y sabemos que se cumple \begin_inset Formula $A$ \end_inset en ese elemento. \layout Subsubsection Ejemplos \layout Standard En la última sección hay algún ejemplo con cuantificadores, pero sin explicar. Supongo que tendrás que mirar algún libro de lógica si te interesa entenderlos. \layout Subsection Reglas derivadas \layout Standard En muchos libros y tutoriales se acepta tener otras reglas (aparte de las 9 básicas) que permiten manejar las fórmulas más fácilmente. Representan una abstracción: dejar de pensar en los detalles para dedicarse a problemas más complicados (es como lo de los lenguajes de programación de \emph on alto nivel \emph default ). \layout Standard Si decides usarlas, te perderás muchas cosas interesantes por hacer, pero acabarás antes. Mi consejo es que uses una regla sólo si sabes demostrar su validez mediante las 9 básicas. \layout Standard Algunas de las que he encontrado por ahí son: \layout Itemize \emph on Ley de doble negación \emph default : permite pasar de \begin_inset Formula $A$ \end_inset a \begin_inset Formula $\neg\neg A$ \end_inset y viceversa. \layout Itemize \emph on Modus Tollens \emph default : si tienes \begin_inset Formula $A\Rightarrow B$ \end_inset y \begin_inset Formula $\neg B$ \end_inset , entonces \begin_inset Formula $\neg A$ \end_inset . \layout Itemize \emph on Silogismo disyuntivo \emph default : si \begin_inset Formula $A\vee B$ \end_inset y \begin_inset Formula $\neg A$ \end_inset , entonces \begin_inset Formula $B$ \end_inset . Y si \begin_inset Formula $A\vee B$ \end_inset y \begin_inset Formula $\neg B$ \end_inset , entonces es que \begin_inset Formula $A$ \end_inset . \layout Itemize \emph on Eliminación de \begin_inset Formula $\neg$ \end_inset \begin_inset Formula $\Rightarrow$ \end_inset \emph default : si tienes \begin_inset Formula $\neg(A\Rightarrow B)$ \end_inset , entonces pasan tanto \begin_inset Formula $A$ \end_inset como \begin_inset Formula $\neg B$ \end_inset . \layout Itemize \emph on Eliminación de \begin_inset Formula $\neg$ \end_inset \begin_inset Formula $\vee$ \end_inset \emph default : si tienes \begin_inset Formula $\neg(A\vee B)$ \end_inset , entonces \begin_inset Formula $\neg A$ \end_inset , y también \begin_inset Formula $\neg B$ \end_inset . \layout Itemize \emph on Eliminación de \begin_inset Formula $\neg\wedge$ \end_inset \emph default : si tienes \begin_inset Formula $\neg(A\wedge B)$ \end_inset , entonces \begin_inset Formula $\neg A\vee\neg B$ \end_inset . \layout Itemize \emph on Teoremas que puedes incorporar cuando quieras \emph default : \begin_inset Formula $A\Rightarrow A$ \end_inset , \begin_inset Formula $A\vee\neg A$ \end_inset , \begin_inset Formula $\neg(A\wedge\neg A)$ \end_inset y más. \layout Itemize \emph on Cambio de fórmulas equivalentes \emph default : si \begin_inset Formula $A\Longleftrightarrow B$ \end_inset , entonces donde veas \begin_inset Formula $A$ \end_inset puedes poner \begin_inset Formula $B$ \end_inset y viceversa. \layout Standard Hay muchas más; pero si te piden un ejercicio ya te dirán qué reglas están permitidas y cuáles no (por ejemplo, a nosotros nos hacían usar sólo las básicas). \layout Section Extra \layout Standard Si ya sabías todo lo que he explicado, o tienes dudas que no tienen que ver con el cómo se hace, mira esta sección. \layout Subsection ¿Por qué se llama deducción natural? \layout Standard Porque los procedimientos que hay que usar son los mismos que los que hace la gente al pensar. \layout Standard Fíjate en los ejercicios resueltos. Expresa los secuentes en forma de palabras, díselos a alguien, y acabará diciéndote que \begin_inset Quotes eld \end_inset \emph on claro que es así, porque ... \emph default \begin_inset Quotes erd \end_inset . Verás que cualquiera es capaz de contarte cómo se usan algunas de las 9 reglas, aunque no sepan su nombre o si existen. \layout Standard Por eso, para descubrir cómo hacer un ejercicio de deducción natural, olvídate de reglas de \emph on introducción \emph default y \emph on eliminación \emph default , y piensa de forma normal, cambiando las letras por acciones sencillas. Va muy bien pensar en eso de \emph on llueve \emph default , \emph on no llueve \emph default , \emph on hace sol \emph default , \emph on no me mojo \emph default , ... porque son palabras cortas y además todos tienen muy claro qué pasa cuando llueve, y relacionan rápidamente el \emph on no mojarse \emph default con el \emph on hacer sol y no llover \emph default , o incluso con fórmulas más complicadas. \layout Subsection ¿La solución es única? \layout Standard No. Cuanto más complicado es el ejercicio, más formas correctas hay de hacerlo. En la sección de los ejercicios explicados, hay alguno para el que doy varias versiones. \layout Standard Naturalmente, puedes empezar a deducir cosas que no te sirvan de nada, y conseguirás una solución diferente a la de los demás. Pero es mejor intentar hacer cada ejercicio lo más corto posible. \layout Subsection Otras formas de demostrar validez \layout Standard La deducción natural es una forma de demostrar la validez de un secuente, pero hay más. Otras son: \layout Subsubsection Fuerza bruta \layout Standard Podemos listar todas las posibles combinaciones de valores para cada variable, y comprobar que, para cada una, si la parte izquierda del secuente se cumple entonces la parte derecha también. \layout Standard Si hay \begin_inset Formula $n$ \end_inset variables, hará falta comprobar \begin_inset Formula $2^{n}$ \end_inset casos. \layout Standard Lo malo es si hay cuantificadores, porque ahí ya hay un dominio implicado. Y no podemos listar algunos de los posibles dominios existentes, porque un dominio puede contener infinitos elementos. \layout Subsubsection Teorema de refutación \layout Standard El teorema de refutación dice que \begin_inset Formula $\Gamma\vDash A\Longleftrightarrow\ \nVdash\Gamma,\neg A$ \end_inset . \layout Standard En palabras: el conjunto de fórmulas \begin_inset Formula $\Gamma$ \end_inset ( \emph on gamma \emph default ) tiene como consecuencia a \begin_inset Formula $A$ \end_inset \emph on si y sólo si \emph default el sistema formado por \begin_inset Formula $\Gamma$ \end_inset junto con \begin_inset Formula $\neg A$ \end_inset es insatisfactible