Cálculo Proposicional

David Baños Abril

Este artículo lo dedicaremos al Cálculo Proposicional. La idea es convertir la Lógica de Proposiciones en un lenguaje formal exento de toda interpretación semántica. De esta manera haremos que la manipulación de proposiciones sea una operación mecánica.

La idea del cálculo

En el primer artículo de esta serie apuntamos a que el desarrollo de la lógica matemática moderna pasaba por distanciarse de conceptos oscuros como son los de «verdadero» o «evidente». La lógica debía distanciarse de los estériles debates acerca de cómo interpretar estos conceptos y centrarse en la simple manipulación de símbolos no interpretados. Las proposiciones se tornarían en símbolos, las operaciones con ellos se asemejarían a un cálculo mecánico siguiendo reglas firmes sin ninguna ambigüedad, y el lógico debería simplemente explorar las posibilidades de dicho cálculo.

El cálculo lógico nos permite generalizar la estructura de la lógica proposicional de manera que podamos más tarde interpretarlo de múltiples maneras.

La verdad bajo la perspectiva del cálculo

Anteriormente vimos cómo podía interpretarse las variables proposicionales, dotándolas de un valor de verdad. Logramos esto sin necesidad de vincular dichas variables con ninguna expresión del lenguaje ordinario como puede ser «el hombre es mortal». De hecho, esos valores de verdad ni siquiera tienen porqué asociarse a nuestra idea intuitiva de verdad.

Bajo la perspectiva del cálculo lógico, la verdad y falsedad se interpreta simplemente como una propiedad de las variables que asume dos posibles valores. Así, será equivalente si en vez de verdad/falsedad decimos 1/0, ω/ψ o cualquiera otra pareja de símbolos. Los únicos principios que deben respetarse es que sean dos valores dicotómicos e incompatibles: cuando una variable cualquiera p valga 1, no podrá valer 0 y viceversa.

Desde el cálculo lógico, entender así la propiedad de verdad obliga simplemente a limitar sus valores a solo dos. Existen sin embargo lógicas que generalizan este esquema a propiedades con más de dos valores. 

Cálculo Proposicional

A al luz del cálculo, entenderemos las expresiones del lenguaje de la Lógica Proposicional como conjuntos de símbolos, a los que llamaremos fórmulas.

Lenguaje Formal del Cálculo Proposicional

Como cualquier lenguaje formal, el lenguaje del Cálculo Proposicional estará formado por dos tipos de elementos: un alfabeto y una reglas gramaticales. La combinación de ellos dará lugar a fórmulas, que son simple conjuntos de signos. Las fórmulas las denotaremos con letras mayúsculas. Veamos los elementos de este lenguaje:

 – alfabeto: son simplemente un conjunto de símbolos. Serán siete: ∧, ∨, ¬, →, ↔, (, ), además de las letras minúsculas que representan variables (pqc, …).

 – reglas de formación: nuestra definición de fórmula es inductiva: comenzaremos estableciendo las bases de lo que se considera una fórmulas para más tarde establecer las reglas que nos permitan generar fórmulas más complejas. Consideramos que toda variable, por ejemplo p o q, es una fórmula. Se las conoce como fórmulas atómicas.  Uniendo fórmulas atómicas como estas podremos crear nuevas fórmulas más complejas, pero no esta permitida cualquier combinación. Si A y B son fórmulas cualesquiera, las posibilidades se ceñirán a las siguientes: (A ∧ B), (A ∨ B), (A → B), (A ↔ B) y ¬A. Estas fórmulas complejas podrán a su vez combinarse siguiendo la misma regla de forma indefinida.

Siguiendo estas reglas, obtendremos siempre fórmulas bien formadas, que es la designación en lógica para combinaciones de signos gramaticalmente correctas. Es evidente por tanto, que fórmulas como (p ↔ o (p ∧ ∧ q) no son fórmulas bien formadas.

Metalenguaje

Hemos usado letras mayúsculas para representar fórmulas cualesquiera de nuestro lenguaje de lógica proposicional. Se podrá comprobar como las letras mayúsculas no forman parte del alfabeto, y por tanto, las fórmulas donde aparecen NO son fórmulas de dicho lenguaje. Se trata pues de un metalenguaje que utilizamos para expresar fórmulas cualesquiera de nuestro lenguaje de lógica proposicional. Así por ejemplo, la expresión metalógica (A ∧ B) → B puede representar infinitas fórmulas de nuestro lenguaje lógico, tales como (p ∧ q) → q o también [(p ∧ m) ∧ (q ∧ m)] → (q ∧ m).

Dado que buscamos principios generales para muchas fórmulas lógicas, en este artículo y en los venideros, tenderemos a usar más este metalenguaje que al propio lenguaje lógico que estemos explorando.

Verdad de las fórmulas

En virtud de lo que hemos apuntado acerca de como formalizar la idea de verdad bajo el cálculo, estableceremos que todas las fórmulas tienen una propiedad que puede tomar solo uno de entre dos posibles valores  (que serán 0 y 1). Esto será así para fórmulas atómicas y complejas. El valor de verdad de estas últimas dependerá del valor de las fórmulas atómicas y de los conectores que las formen. El proceso para calcular dicho valor será el mismo que hemos visto en el artículo previo, mediante tablas de verdad. Este es un proceso completamente mecánico.

Axiomas del Cálculo Proposicional

Tenemos un alfabeto y un conjunto de reglas para distinguir fórmulas bien formadas. Por definición eso es todo lo necesario para tener una lenguaje formal. Pero queremos establecer un método axiomático: unas bases a partir de las cuales generar fórmulas no solo que sean gramáticamente correctas, sino también que cumplan una serie de propiedades.

Los axiomas

En la Antigua Grecia axioma era una verdad evidente, de la que no podía haber duda alguna. Actualmente se ha abandonado esta definición por implicar el polémico y oscuro fenómeno psicológico de la intuición. Axioma es simplemente un enunciado que se elige como sostén para un determinado sistema formal y que no tiene una demostración. Parece una definición bastante laxa. De hecho esta definición abre la puerta a que existan múltiples sistemas formales, cada uno con axiomas diferentes. Pero como cimientos de todo un sistema que son, elegir los axiomas no es cuestión baladí.

Los axiomas que buscamos tendrán una propiedad: la resolución de su valor de verdad dará siempre 1, independientemente de los valores de verdad que adopten sus fórmulas atómicas. Esto es análogo a las proposiciones válidas que hemos visto en el artículo previo.  Estos axiomas relejan pues, proposiciones siempre verdaderas. Toda fórmula F que sea válida se denotará como ⊨F.

Esquemas de Axiomas de la Lógica Proposicional

1: A → (B → A)

2: (A → B) → ((A → (B → C)) → (A → C))

3: A → (B → A ∧ B)

4a: A ∧ B → A

4b: A ∧ B → B

5a: A → A ∨ B

5b: B → A ∨ B

6: (A → C) → ((B → C) → (A ∨ B ∨ C)

7: (A → B) → ((A → ¬B) → ¬A)

8: ¬¬A → A

9: (A → B) → (B → A) → (A ↔ B)

10a: (A ↔ B) → (A → B)

10b: (A ↔ B) → (B → A)

Como puede verse, estamos utilizando letras mayúsculas para designar fórmulas cualesquiera de nuestra sistema lógico. Por ello, no se tratan de axiomas del Cálculo Lógico en el sentido preciso del término, sino de esquemas de axiomas que representan infinitas fórmulas posibles de la lógica proposicional. Algunos ya los hemos apuntado en la entrada de lógica proposicional. Los tres últimos por ejemplo, definen el conector bicondicional, mientras que el axioma 7 es el de reducción al absurdo. 

Deducción

Reglas de Inferencia

En un sistema formal, además de axiomas, se necesitarán una serie de principios que permitan la generación de nuevas fórmulas. Ese papel lo cumplen las reglas de inferencia, cuya aplicación transformará una expresión en otra.

Las reglas de inferencia que usaremos serán dos:

 – Regla de Sustitución: cualquier expresión bien formada puede ser sustituida por una variable proposicional y a la inversa, siempre y cuando esta sustitución afecte a todas las apariciones de la expresión.

 – Modus ponens: si tenemos una condicionalidad y contamos con la premisa, deducimos inequívocamente la implicación. [(A → B) ∧ A] → B

Consecuencia Lógica

El Modus Ponens es un esquema deductivo que expresa que cuando las premisas (A → B) y A sean verdaderas, entonces la consecuencia B es también verdadera. Cuando en una deducción siempre que las premisas sean ciertas la conclusión sea cierta, hablaremos de consecuencia lógica. Si hiciéramos una tabla de verdad, veríamos que en todos los casos en que las premisas valgan todas 1, la consecuencia valdrá también 1. En el ejemplo de antes decimos que B es una consecuencia lógica de (A → B) y de A. Veamos une ejemplo algo más extenso. Deduzcamos la expresión (A → A) recurriendo a los axiomas vistos y las reglas de inferencia:

F_{1}: A → (B → A)

Axioma 1

F_{2}: A → (A→ A)

Regla de Sustitución sobre el Axioma 1 de B por A

F_{3}: (A → B) → ((A → (B → C)) → (A → C))

Axioma 2

F_{4}: (A → (A → A) ) → ((A → ((A → A) → A)) → (A → A))

Regla de Sustitución sobre el Axioma 2 de B por (A → A) y de C por A

F_{5}: (A → ((A → A) → A)) → (A → A)

Modus Ponens con A_{2} y A_{3} como premisas.

F_{6}: A → ((A → A) → A)

Regla de Sustitución sobre el Axioma 1 de B por (A → A)

F_{7}: A → A

Modus Ponens sobre A_{5} y A_{6} como premisas.

Teoremas

Puede parecer engorroso de visualizar pero si se repasa detalladamente el esquema se podrá comprobar como no hemos usado otra cosa que los axiomas y las reglas de inferencia para acabar finalmente deduciendo A → A. Así, vemos que una deducción puede definirse también como una cadena finita de fórmulas F_{1}…F_{n} en la que la última cadena F_{n} es la fórmula que queremos deducir. Se conocen como teoremas a las fórmulas deducidas en un sistema formal. Son expresiones, por definición, demostrables en dicho sistema. Para expresar que F es un teorema, es decir, una fórmula demostrable, la notación sería ⊢F.

No es necesario que la deducción de teoremas comience a partir de axiomas siempre. Puede comenzar también a partir de otros teoremas siempre que estos hayan sido demostrados con anterioridad.

Solidez del Cálculo Proposicional

Aunque hemos escogido los axiomas en base a propiedades semánticas (son fórmulas válidas), el proceso de deducción es por completo mecánico, no es necesario analizar con tablas de verdad si las fórmulas resultantes son o no verdaderas. Es independiente de las propiedades de las fórmulas; se trata simplemente de un juego de manipulación simbólica.

Pero para nuestro propósito queremos que los teoremas sean también verdaderos ¿Cómo podemos asegurarnos que las nuevas fórmulas deducidas de tal modo resultan también válidas, siempre verdaderas?

El Modus Ponens

Buscamos que los teoremas hereden la propiedad de verdad que hemos aplicado en la selección de los axiomas. La regla de Modus Ponens se elige en base a este requerimiento. Veamos cómo:

 – Nuestros axiomas son válidos, eso significa que en cada interpretación de las variables que lo formen (las filas en las tablas de verdad) el valor resultado es siempre 1, verdadero.

 – Como la aplicación del Modus Ponens da un resultado verdadero cuando las premisas son verdaderas, para todas las interpretaciones de las fórmulas válidas la conclusión es siempre verdadera.

 – Por tanto, si las premisas son fórmulas válidas, toda conclusión es también una fórmula válida. En el avance a lo largo de la cadena de fórmulas F_{1}…F_{n}, toda fórmula es una fórmula siempre verdadera.

El Modus Ponens

Como toda conclusión no es más que una fórmula de una cadena, toda conclusión es también válida. La solidez es una propiedad de los sistemas formales que nos dice que siempre que las premisas sean verdades y el razonamiento sea una consecuencia lógica, las deducciones serán también verdades. Si esas verdades lo son para toda interpretación, toda fórmula deducible es también válida. Bajo el principio de solidez, demostrable implica siempre verdadero. En notación lógica decimos que si ⊢F, entonces ⊨F. Esta propiedad es de una importancia crucial en metalógica y lo retomaremos más de una vez en La Máquina Oráculo.

Lecturas Recomendadas

 – Delgado, V. M. (1972) Lecciones de lógica (I).

 – 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.

La Máquina Oráculo utiliza cookies para que usted tenga la mejor experiencia de usuario. Si continúa navegando está dando su consentimiento para la aceptación de las mencionadas cookies y la aceptación de nuestra política de cookies, pinche el enlace para mayor información.plugin cookies

ACEPTAR
Aviso de cookies