Sistemas Deductivos
David Baños Abril
Los Sistemas Deductivos nos permiten generar Sistemas Lógicos formados por un conjunto de fórmulas. Dada las dificultades que plantea la Semántica de Primer Orden, estos métodos se deben exclusivamente a reglas de inferencia que transforman las fórmulas por simple manipulación de sus símbolos.
El objetivo de los Sistemas Deductivos
Repasemos. Hasta ahora hemos establecido una definición de Lenguaje o Sintaxis de Primer Orden que nos ha permitido distinguir fórmulas bien formadas de aquellas que no son gramaticalmente correctas. Además, hemos visto la Semántica de Primer Orden que nos presenta un método mecánico para determinar la veracidad de una fórmula a partir de un lenguaje y una interpretación.
Buscamos ahora dar con un sistema que pueda generar todo un conjunto de nuevas fórmulas. Hemos visto en el artículo previo que, comprobar la veracidad de una fórmula siguiendo el método semántico puede resultar en una tarea infinita dependiendo de la interpretación. Necesitamos pues un procedimiento para generar fórmulas que no dependa de interpretaciones semánticas, sino de simples reglas combinatorias de sintaxis. A estos procedimientos los denominamos Sistemas Deductivos.
La deducción Lógica
La idea de la deducción lógica es superar las limitaciones del concepto de consecuencia lógica que hemos visto en el artículo previo. Recordamos que consecuencia lógica ligaba dos fórmulas por su propiedad de verdad: una fórmula es una conclusión lógica cuando es verdadera en toda interpretación en la que sean verdaderas las premisas. Las dificultades para comprobar las infinitas posibles interpretaciones resultaban en que este procedimiento era inviable.
Sin embargo, la deducción lógica nos permite tomar un atajo. Para ello debemos tomar un esquema de fórmula de la Lógica de Proposicional que cumpla la siguiente propiedad: siempre que las premisas sean verdaderas, lo será el consecuente. Existen muchos esquemas que cumpla esto, pero el más habitual es el modus ponens: ((A → B) ∧ A) → B
El número en los símbolos de arriba indica el orden de resolución de esta tabla de verdad. La columna azul indica el símbolo principal que resuelve la fórmula al completo.
Equivalencia entre Deducción y Consecuencia
Como vemos, independiente de las fórmulas que sean, solo cuando ambas, A y B, son ciertas, la fórmula al completo es verdadera. Esto es exactamente lo que establecía la conclusión lógica, pero evitando el método semántico. Gracias a este esquema, si suponemos que las premisas A y A → B sean ciertas, podemos deducir inequívocamente B sin tener que comprobar cada interpretación semántica. El presupuesto de que las premisas sean ciertas, bien puede venir de que sean axiomas o hipótesis de trabajo.
Existen varios Sistemas Deductivos que parte de esta idea de deducción. Aun siendo diferentes, todos ellos precisan de un lenguaje formalizado que distinga fórmulas bien formadas. Puede usarse otros lenguajes, pero puesto que queremos expresar la Lógica de Primer Orden, utilizaremos un Lenguaje de Primer Orden.
Sistema de Hilbert
El modelo de Hilbert es uno de los primeros en pretender totalizar todas las ramas de la matemática bajo un mismo procedimiento. Su formalización se debe al gran matemático de principios del siglo XX, David Hilbert, aunque existen antecedentes. El uso de axiomas como bases de una teoría matemática ya podemos encontrarlo en el geómetra griego Euclides. Lo hemos estado viendo a lo largo de esta serie.
Su planteamiento es el conocido como axiomatización: dado un lenguaje formalizado, establecemos un conjunto de axiomas (realmente esquemas de axiomas). A partir de estos axiomas podemos deducir teoremas aplicando unas reglas de inferencia.
Esquemas de Axiomas de Primer Orden
Los esquemas de axiomas actúan como modelos de infinitas posibles fórmulas. Recordar que no son fórmulas de un Lenguaje de Primer Orden, sino de un meta-lenguaje que utiliza símbolos como A o B para representar fórmulas cualesquiera de ese Lenguaje de Primer Orden. Comprobaremos como, la mayoría de estos esquemas provienen de la Lógica Proposicional.
1) A → (B → A)
2) (A → (B → C)) → ((A → B) → (A → C))
3) A → (B → (A ∧ B))
4) (A ∧ B) → A; (A ∧ B) → b
5) (A → C) → ((B → C) → ((A ∧ B) → C))
6) A → (A ∨ B); B → (A ∨ B)
7) (A → B) → ((A → ¬B) → ¬A)
8) ¬¬A → A
9) ∀x[A(x)] → A(t)
10) A(t) → ∃x[A(x)]
Solo los dos últimos axiomas son exclusivos de la Lógica de Primer Orden. Vienen a decir que “cuando una fórmula es verdadera para todo valor asumible por la variable, es verdadera para un valor cualquiera” y también “cuando una fórmula es verdadera para un valor determinado implica que es verdadera para al menos uno de los valores que asuma la variable”.
Reglas de Inferencia
Las reglas de inferencia nos permiten transformar unas fórmulas en otras. Aunque la selección de las reglas de inferencia responde a un criterio semántico – siempre que las premisas sean verdaderas lo será la conclusión- lo cierto es que no será necesario recurrir a ninguna consideración semántica para su aplicación.
La primer regla ya la hemos visto antes, es el modus ponens. La segunda es exclusiva del Sistema Deductivo de Hilbert y se llama regla de generalización. Esta regla se deriva simplemente de la definición de cuantificador universal: si A(x) es verdadera (esto es, para todo valor del universo que asuma x, la fórmula es verdadera), entonces ∀x[A(x)] es también verdadera. Es aplicable solo porque los axiomas son leyes lógicas, verdades bajo todo valor de las variables de toda interpretación.
Deducción
Con los axiomas y las reglas de inferencia podemos proceder a la deducción. Bajo el Sistema de Hilbert, se conoce como deducción a un conjunto de fórmulas A_{1}, A_{2}, … A_{n}, B tales que la última de las fórmulas (B) es el resultado de aplicar las reglas de inferencia sobre las anteriores. Esta última fórmula se denomina teorema. Para distinguirlo de la conclusión lógica, se utiliza el símbolo ⊢ para denotar le deducción.
Esas fórmulas previas A_{1}… A_{n} o bien son axiomas, o bien son el resultado de la aplicación de las reglas de inferencia sobre dichos axiomas, es decir, otros teoremas.
Por la propiedad de la deducción, que devuelve siempre verdadero si las premisas son ciertas, toda aplicación de la regla de inferencia sobre fórmulas válidas resultará en fórmulas también válidas. Es decir, dado que los axiomas son siempre verdaderos, toda fórmula deducible será también siempre verdadera. Así, la veracidad se conserva a lo largo de todo el proceso deductivo.
Variantes
Los axiomas que hemos propuestos son todos fórmulas válidas, es decir, se han elegido en base a un criterio semántico. Eso rompe con nuestro intento de descontextualizar lo posible los Sistemas Deductivos. Sin embargo, existen otras listas de esquemas de axiomas igualmente equivalentes.
El criterio sintáctico utilizado para seleccionar axiomas según el Sistema de Hilbert es el cumplimiento de una serie de meta-propiedades del sistema resultante, tales como la consistencia o la completitud. Se buscará escoger cualquier lista de axiomas que resulte en un sistema que manifieste dichas propiedades, siendo todas ellas, listas equivalentes.
Teorema de la Deducción
El Teorema de la Deducción es una meta-propiedad de los Sistemas Lógicos y afirma que, para un conjunto de fórmulas:
El Teorema de la Deducción nos dice que el propio Sistema Lógico puede expresar mediante la implicación el vínculo deductivo existente entre dos fórmulas (que no es una expresión perteneciente al sistema). Este Teorema de la Deducción, cuya demostración no apuntaremos aquí, permite la generación de nuevas formas de razonamiento mucho más versátiles que las que ofrece el uso exclusivo del modus ponens o la regla de generalización.
Deducción Natural
Otro de los Sistemas Deductivos más utilizados es la llamada técnica de Deducción Natural, formalizada por el lógico alemán Gerhard Gentzen también a comienzos del siglo XX. A diferencia del método de Hilbert, la Deducción Natural no establece ningún axioma, tan solo un conjunto de reglas de inferencia, derivadas del Teoremas de la Deducción. Este método pues es utilizado en los casos en los que se busque deducir a partir de hipótesis, propuestas de fórmulas cuya veracidad es desconocida. El método fue diseñado para acercarse a los usos habituales del razonamiento lógico que suelen darse en matemática y ciencias, de ahí el adjetivo de “natural”.
Las reglas de inferencia utilizadas en la deducción natural no son reglas como la del modus ponens. Aquí las premisas y conclusiones no serán fórmulas del sistema, sino meta-fórmulas que expresan relaciones de deducción lógica. Aún así, no dejan de ser reglas de inferencia: suponiendo que las premisas son verdaderas, nos vemos obligados a reconocer la verdad de la conclusión.
Reglas lógicas de la Deducción Natural
Las reglas de inferencia las escribimos con una línea que separa las premisas arriba y la deducción abajo. Para un conjunto de fórmulas A_{1}… A_{n} al que llamaremos Ψ para abreviar las reglas en la Deducción Natural son:
Para →
Ψ⊢ A ; Ψ⊢ (A → B)
Para ∧
Ψ ⊢ A; Ψ ⊢ B
Para ∨
Ψ, A ⊢ C ; Ψ, B ⊢ C
Para ¬
Ψ, A ⊢ B; Ψ, A ⊢ ¬B
Para ∀
Para ∃
Si quisiéramos demostrar la fórmula de abajo, tan solo sería necesario demostrar que las premisas son ciertas.
Conclusión
Los Sistemas Deductivos vistos, tanto el Sistema de Hilbert como la Deducción Natural son métodos igualmente equivalentes y ambos resultan en sistemas sólidos. Recordemos que llamábamos solidez a la propiedad de toda deducción sintáctica cuando es también una conclusión lógica desde el punto de vista semántico. Gracias a la deducción, siempre que exista un vínculo de deducción lógica, existirá un vínculo de consecuencia lógica.
Fijémonos en que la implicación es unidireccional: podrán darse casos de conclusión lógica si que sean deducibles por vía sintáctica.
Independientemente del método usado, ambos reproducen los patrones semánticos que tanta importancia tendrán en las propiedad metalógicas de la Lógica de Primer Orden.
Lecturas recomendadas
– Kolmogórov, A.N. y Dragalin, A.G. (2013) Introducción a la lógica matemática.
– de Swart, H. (2018) Philosophical and Mathematical Logic.
