Conceptos Fundamentales de Lógica Proposicional: Tablas de Verdad, Tautologías y Consecuencia Lógica

Conceptos Fundamentales de Lógica Proposicional

1. Tabla de Verdad: Definición, Construcción y Significado

Una tabla de verdad de una fórmula A es una tabla en la que se calculan los valores de verdad que las distintas valuaciones dan a la fórmula A en función de los valores asignados a las variables proposicionales que aparecen en A. En la tabla reflejamos todas las posibles combinaciones de valores de verdad que se pueden dar a las variables proposicionales de A. A partir de ahí, vamos calculando los valores que en cada una de esas posibilidades corresponden a cada una de las subfórmulas de A, yendo de más simples a más complejas hasta llegar a A.

Procedimiento:

1. Escribimos en una línea todas las subfórmulas de menor a mayor complejidad.
2. Calculamos las combinaciones de valores de verdad que pueden darse para las variables proposicionales, que nos dará lugar a las líneas que debemos añadir.
3. En cada línea escribimos las posibles combinaciones de valores de verdad de las fórmulas atómicas.
4. Debajo de cada subfórmula de A escribimos el valor de verdad que le corresponde.

2. Tautología y Contradicción: Definiciones

Las tautologías son fórmulas válidas de la lógica proposicional clásica cuya propiedad es que todas las valuaciones hacen verdadera a la fórmula. Las fórmulas son verdaderas en todas las interpretaciones posibles. Son verdaderas en virtud de su estructura, independientemente de su contenido. Son verdades "triviales". Las tautologías representan las leyes de la lógica que nos ocupa hasta el punto de que todas las relaciones de consecuencia de esta lógica se pueden reducir a tautologías.

Cuando la tabla de verdad de una fórmula muestra que es falsa para cualquier valuación que consideremos, esto es una contradicción. Además, la negación de una tautología es una contradicción.

3. Relación de Consecuencia en Lógica Proposicional

Una relación de consecuencia es una relación que se da entre un conjunto de premisas Γ y una conclusión A cuando para cualquier interpretación que consideremos resulta que si las premisas son verdaderas, la conclusión también lo es. Se da la relación de consecuencia entre Γ y A cuando no es posible encontrar una interpretación que haga verdaderas las premisas pero no la conclusión.

4. Teorema Semántico de la Deducción: Enunciado y Demostración

Para cualesquiera Γ, A, B, se cumple que Γ, A╞B syss Γ╞A→B.

Demostración: Hay que demostrar que las dos relaciones de consecuencia, Γ, A╞B y Γ╞A→B, se dan en los mismos casos o que no se dan en los mismos casos. Γ, A╞B syss Γ╞A→B.

• Γ, A╞B syss hay una valuación que hace verdaderas a las fórmulas de A y Γ pero hace falsa a B.
• Γ╞A→B syss hay una valuación que hace verdaderas a las fórmulas de Γ y falsa a A→B, es decir, que hace verdadera a A y falsa a B.

Con esto llegamos a que cualquier relación de consecuencia con un conjunto finito de premisas se puede reducir a una tautología.

5. Teorema de Compacidad: Enunciado

Para cualesquiera Γ y A, Γ╞A syss existe un subconjunto finito Γ' de Γ tal que Γ'╞A. Este teorema permite afirmar que toda consecuencia entre fórmulas se corresponde con una tautología. Con este teorema podemos saber que no necesitamos infinitas premisas para establecer una conclusión.