Hemos llegado, dentro de nuestro estudio de la lógica, a un punto de inflexión, porque aquí iniciamos la revisión de los Sistemas Deductivos de la Lógica Proposicional. Aquí es donde todo lo que hemos visto comienza a volverse operativo y ve la luz el verdadero espíritu de la lógica, porque estudiaremos la esencia de las demostraciones. En este punto se asume que ya has visto cómo escribir expresiones y entiendes de qué va la lógica proposicional; y si no lo tienes del todo claro, es recomendable que revises las clases previas a esta.

Hecho esto, lo que sigue ahora es revisar la forma en que las expresiones de la lógica proposicional se relacionan entre si para formar una deducción. El mecanismo a través del cual se construyen esas relaciones es el sistema deductivo formal.

¿Qué es un Sistema Deductivo Formal?

Los sistemas deductivos formales, o sistemas de cálculo deductivo, tienen tres componentes elementales:

1. Un Lenguaje Formal.
2. Un Esquema Axiomático.
3. Reglas de Inferencia Elementales.

Ya hemos revisado todo lo relacionado a los lenguajes formales. Ahora nos toca introducir los esquemas axiomáticos y las reglas de inferencia elemental.

Para la construcción del sistema deductivo del cálculo proposicional partiremos armando el sistema deductivo a partir de los Axiomas de Łukasiewicz, y por regla de inferencia elemental usaremos el Modus Ponens.

Los Axiomas de Łukasiewicz para la Lógica Proposicional

Si \alpha, \beta y \gamma son expresiones del cálculo proposicional, entonces los siguientes son axiomas del cálculo proposicional:

El Modus Ponens: El motor deductivo del cálculo proposicional

Si \alpha y \beta son expresiones válidas del cálculo proposicional, entonces el modus ponens establece que a partir de \alpha y (\alpha \rightarrow \beta) se deduce \beta. En forma de razonamiento esto se escribe de la siguiente manera:

Aquí se ha abreviado representado el Modus Ponens entre los pasos (1) y (2) a través de la escritura «MP(1,2)», y la síntesis de todo esto se representa a través de la notación:

Por lo tanto \{\alpha, (\alpha \rightarrow \beta)\}\vdash \beta

Pronto veremos que a partir de los axiomas de Łukasiewicz y el Modus Ponens se pueden construir todas las técnicas de deducción del cálculo proposicional, las cuales sintetizan las reglas básicas del razonamiento usual y sirve de base fundacional para la lógica clásica.

Razonamientos, teoremas y premisas

En el sistemas deductivos de a la lógica proposicional se ejecutan razonamientos (o deducciones), y estos son cualquier sucesión de expresiones en donde cada una de ellas es, o una premisa o una expresión obtenida a partir de las premisas utilizando sólo los axiomas de Łukasiewicz y el modus ponens. Un teorema es el resultado de una deducción sin premisas. Una premisa puede ser cualquier expresión que ni es un axioma ni se deduce a partir de ellos. En general, cuando tenemos un conjunto de premisas \Gamma y una expresión \alpha que se obtiene utilizando algún elemento de \Gamma, los axiomas y el modus ponens, se escribe «\Gamma \vdash \alpha» y decimos que

de \Gamma se deduce \alpha

Si \Gamma es un conjunto vacío, entonces en lugar de escribir «\emptyset\vdash \alpha» se escribe « \vdash \alpha . » Esto se lee «\alpha es un teorema». Esta forma de representar los teoremas se puede extender para la representación de los axiomas de modo que, si \alpha y \beta y \gamma son expresiones, entonces los axiomas de Łukasiewicz se pueden escribir de la forma

Es a partir esto que se dice que los axiomas son afirmaciones evidentes por si mismas, o que los teoremas son expresiones que se infieren a partir de vacío, o que axiomas y teoremas son propiedades del cálculo proposicional.

¿Cómo se ejecuta una demostración en la lógica proposicional?

En este punto dejaremos de hablar de teoría y pasaremos a la práctica. Y es que sobre la ejecución de una demostración se pueden decir muchas cosas; pero por más que se digan cosas brillantes sobre los sistemas deductivos y la lógica proposicional, y todas sean entendidas, esto no implicará que por necesidad que se estén desarrollando las competencias necesarias para ejecutar una demostración. Por este motivo, para enseñar la forma en que se hacen las demostraciones revisaremos la demostración de un teorema sencillo.

Teorema

Si \alpha es una expresión de la lógica proposicional, entonces se cumple que

\vdash (\alpha\rightarrow \alpha)

Demostración

Por lo tanto \vdash (\alpha\rightarrow\alpha)

Fin de la demostración.

Como se puede ver, en los sistemas deductivos y la lógica proposicional las demostraciones no tienen nada de trivial, pero una vez construidas son fáciles de replicar.

Ahora, antes de tirarnos de cabeza a hacer deducciones con estas técnicas, primero vamos a desarrollar algunas propiedades y definiciones que nos serán extremadamente útiles para esta labor, porque si razonamos sólo con esto nos toparemos con terribles problemas.

El concepto de equivalencia probada

Si \alpha y \beta son expresiones cualesquiera y se  cumple al mismo tiempo que \{\alpha\}\vdash \beta y \{\beta\} \vdash \alpha, entonces se dice que \alpha y \beta son probadas equivalentes y se escribirá \alpha \dashv \vdash \beta. Esto se resume simbólicamente como:

\left(\{\alpha\}\vdash\beta \wedge \{\beta\}\vdash\alpha \right) \Leftrightarrow \left(\alpha\dashv\vdash\beta\right)

Esto se lee: de \alpha se infiere \beta, y de \beta se infiere \alpha si y sólo si \alpha y \beta son probados equivalentes.

Esto es una meta-propiedad de la lógica proposicional

El (meta)Teorema de Deducción

Si \alpha y \beta son expresiones del cálculo proposicional, y \Gamma es un conjunto de premisas; entonces se tiene que si de \Gamma \cup \{\alpha\}se deduce \beta, entonces a partir de \Gamma se deduce (\alpha \rightarrow \beta). Simbólicamente esto quedaría expresado como:

\left(\Gamma \cup \{\alpha\}\vdash \beta \right) \Rightarrow \left( \Gamma\vdash(\alpha\rightarrow\beta)\right)

Demostración:

Para que se cumpla \Gamma \cup \{\alpha\}\vdash \beta, es necesario tener una deducción de la forma

Por lo tanto \Gamma\cup\{\alpha\} \vdash \beta

Para que ésto sea posible, es necesario que por lo menos una de las expresiones \gamma_1, \cdots \gamma_n,\overline{\gamma_1},\cdots,\overline{\gamma_m} sea de la forma (\alpha\rightarrow \beta), pero todas esas líneas sólo involucran elementos de \Gamma y los axiomas de Łukasiewicz en su deducción, por lo tanto debe cumplirse que \Gamma\vdash (\alpha \rightarrow \beta). Quedando por lo tanto demostrado el teorema

Fin de la demostración.

El Recíproco del Teorema de Deducción

En las mismas condiciones que el teorema de deducción, se tendrá que

\left(\Gamma\vdash(\alpha \rightarrow \beta)\right) \Rightarrow \left( \Gamma \cup \{\alpha\}\vdash \beta \right)

Demostración:

Si se cumple que \Gamma\vdash (\alpha\rightarrow \beta), entonces se tiene una deducción de la forma

Ahora, si agregamos \alpha como premisa a este razonamiento, entonces tendremos las siguientes líneas

Por lo tanto \Gamma \cup \{\alpha\} \vdash \beta

Que es lo que se quería demostrar.

Fin de la demostración.

Deducciones sobre Expresiones y Deducciones sobre Deducciones

Demostraciones como la que se hizo antes para llegar al resultado \vdash (\alpha\rightarrow \alpha) son casos de deducciones a base de expresiones, porque cada paso contiene una expresión en concreto. De forma análoga es posible hacer deducciones en base a otras deducciones, donde cada paso es una deducción en si misma. En la práctica, ambas cosas se hacen de forma análoga, pero la segunda nos permite hacer uso del teorema de deducción y su recíproco, dando gran flexibilidad a la técnica de razonar. Para ver esto, demostremos nuevamente que \vdash (\alpha \rightarrow \alpha), pero ahora usando deducciones en lugar de expresiones. Una alternativa para ello es la siguiente:

Notemos que este razonamiento no es más corto que el que habíamos realizado antes, pero si mucho más fácil de realizar, sólo nos bastamos del teorema de deducción, de su recíproco y del esquema axiomático A1 para construir la demostración.

En apariencia, en el desarrollo que acabamos de hacer utilizamos un solo axioma de Łukasiewicz y nos olvidamos tanto de otros axiomas como del modus ponens. ¿Implica esto que por razonar de esta forma nos olvidamos de los demás axiomas y del modus ponens? La respuesta es un si y un no. Por un lado podemos hacer como si nos olvidásemos de algunos axiomas y del modus ponens sólo porque no los estamos usando de forma explícita, sin embargo, debe recordarse que tanto el teorema de deducción como su recíproco son consecuencia precisamente de los axiomas de Łukasiewicz y del modus ponens, lo cual implica que, al hacer uso de éstos, como se hizo en el razonamiento que acabamos de ver, estamos haciendo un uso implícito de ellos.

Regla de Monotonía

Si \tau es un teorema, entonces se tendrá que, dada cualquier expresión \beta, se cumplirá que

\{\beta\}\vdash\tau

Esto es en realidad una regla muy fácil de probar, ya que al ser \tau un teorema se cumplirá que \vdash \tau. Es decir, que existe un razonamiento que sin la necesidad de agregar premisas conduce a la expresión \tau, por lo que agregar una expresión adicional a las premisas (vacía) no creará diferencia.

De forma similar a esto se puede plantear el siguiente resultado: si de un conjunto de premisas \Gamma se infiere \gamma, entonces se cumplirá que

\Gamma\cup\{\alpha\}\vdash\gamma

Donde \alpha es una expresión cualquiera.

Síntesis y Reflexiones sobre Sistemas Deductivos y la Lógica Proposicional

Cuando proporcionamos al lenguaje de la lógica proposicional una regla de inferencia y expresiones de base: El Modus Ponens y los Axiomas de Łukasiewicz, lo que hacemos es análogo a armar una «máquina deductiva» y un «motor que le proporciona energía para entrar en movimiento». A partir de aquí es que comienzan a emerger de forma natural todas las reglas básicas de deducción y que comenzaremos a revisar en las entregas inmediatamente posterior a esta.

Otro detalle más. Las expresiones de la lógica proposicional son en realidad meta-expresiones del lenguaje de dos símbolos que vimos antes. Recordemos que la gracia de estas meta-expresiones es que nos permiten sustituir sus meta-variables por cualquier expresión del lenguaje para obtener una nueva que satisface tal estructura. Cuando dotamos al lenguaje de lógica proposicional de esquemas axiomáticos y reglas de inferencias, construimos el Sistemas Deductivos de la lógica proposicional que permite generar deducciones que conectan expresiones. Como resultado tenemos un esquema deductivo capaz de englobar infinitas deducciones: todas las que podemos obtener remplazando meta-variables por las expresiones que queramos. El poder de la lógica se desata, en realidad, cuando nos damos cuenta de que además de esas expresiones del lenguaje de dos símbolos que utiliamos al principio, observamos lo que ocurre cuando en su lugar remplazamos expresiones de nuestra lengua usual.