Fundamentos de lógica proposicional

Introducción a la lógica proposicional

La lógica proposicional es la rama de la lógica que estudia las relaciones entre enunciados que pueden ser verdaderos o falsos. Se utiliza como base para el razonamiento formal en informática, matemáticas y filosofía. En este curso revisaremos los conceptos esenciales que aparecen en los cuestionarios de evaluación, proporcionando ejemplos claros y explicaciones detalladas.

¿Qué es una proposición?

Una proposición es cualquier enunciado que tiene un valor de verdad bien definido. No todas las frases son proposiciones; aquellas que dependen de información externa o que son preguntas no califican.

• Ejemplo de proposición: "París es la capital de Francia" (verdadera).
• Ejemplo que NO es proposición: "¿Qué día de la semana es hoy?" (no tiene valor de verdad).

Identificar correctamente las proposiciones es el primer paso para construir fórmulas lógicas.

Tipos de fórmulas según su valor de verdad

Tautología

Una fórmula es tautología cuando es verdadera bajo todas las interpretaciones posibles. Por ejemplo, la ley de la doble negación ¬¬p ⇔ p siempre es verdadera, al igual que p ∨ ¬p (principio del tercio excluido).

Contradicción

Una contradicción es lo opuesto: nunca puede ser verdadera. Un caso típico es p ∧ ¬p, cuya tabla de verdad muestra que ninguna fila resulta verdadera.

Contingencia

Una fórmula que es verdadera en algunas interpretaciones y falsa en otras se denomina contingencia. La mayoría de las expresiones compuestas, como p ∨ (q ∧ r), son contingentes.

Construcción y análisis de tablas de verdad

La tabla de verdad es una herramienta fundamental para determinar el valor de una fórmula bajo todas las combinaciones posibles de sus variables.

Veamos el ejemplo p ∨ (q ∧ r) con p = V, q = V y r = F:

• Primero evaluamos q ∧ r: V ∧ F = F.
• Luego p ∨ (resultado): V ∨ F = V.

El resultado es verdadero. Este proceso se repite para cada combinación de valores y permite identificar tautologías, contradicciones y contingencias.

Leyes de De Morgan y su aplicación

Las leyes de De Morgan son reglas de transformación que facilitan la negación de expresiones compuestas:

• ¬(p ∨ q) ⇔ ¬p ∧ ¬q
• ¬(p ∧ q) ⇔ ¬p ∨ ¬q

En el cuestionario, la negación de (p ∨ q) corresponde a ¬p ∧ ¬q. Estas equivalencias son esenciales para simplificar argumentos y para el método de árbol.

Implicación lógica y razonamiento condicional

La implicación p ⇒ q se interpreta como "si p entonces q". Su tabla de verdad muestra que la única combinación que la hace falsa es p = V y q = F. Cuando una premisa de una implicación es falsa, la implicación completa es verdadera por definición.

Ejemplo del cuestionario: si p ⇒ (q ⇒ r) es verdadera y q es falsa, el valor de r no afecta la verdad de la implicación, por lo que r puede ser verdadero o falso.

Método de árbol (semantic tableau)

El método de árbol es una técnica visual para probar la validez de argumentos lógicos. Consiste en descomponer premisas y conclusión en sus componentes básicos hasta que se llegue a una contradicción o a una rama abierta.

Un paso crucial es negar la conclusión antes de iniciar la construcción del árbol. Al hacerlo, buscamos una contradicción entre las premisas y la negación de la conclusión; si todas las ramas se cierran, el argumento es válido.

Esta estrategia permite transformar la prueba de validez en una búsqueda de inconsistencia, simplificando el proceso de razonamiento.

Reglas de simplificación en lógica de ordenadores

En la lógica de ordenadores, se utilizan reglas de inferencia para reducir expresiones sin cambiar su valor de verdad. Algunas de las más comunes son:

• Regla de absorción: A ∧ (A ∨ B) ⇔ A. Permite simplificar A ∧ B a A cuando B está contenido dentro de una disyunción con A.
• Regla de idempotencia: A ∧ A ⇔ A y A ∨ A ⇔ A.
• Regla de distribución: A ∧ (B ∨ C) ⇔ (A ∧ B) ∨ (A ∧ C).

En el cuestionario, la simplificación de A ∧ B a A corresponde a la regla de absorción, que es válida en sistemas de lógica proposicional y de ordenadores.

Ejercicios prácticos y su solución paso a paso

1. Identificar proposiciones

Determine cuál de los siguientes enunciados no es una proposición:

• París es la capital de Francia.
• El número 5 es un número primo.
• La programación es esencial para el desarrollo de software.
• ¿Qué día de la semana es hoy?

La respuesta correcta es la última, ya que es una pregunta y no posee un valor de verdad definido.

2. Determinar si una fórmula es tautología

Si una fórmula es verdadera bajo todas las interpretaciones, se denomina tautología. Por ejemplo, p ∨ ¬p siempre es verdadera.

3. Evaluar una fórmula compuesta

Calcule el valor de p ∨ (q ∧ r) con p = V, q = V y r = F. El proceso se muestra arriba y el resultado es verdadero.

4. Analizar la tabla de verdad de p ∧ ¬p

Esta tabla tiene una única fila para cada valor de p. En ambas filas, el resultado es falso, por lo que p ∧ ¬p es una contradicción y no tiene filas verdaderas.

5. Aplicar De Morgan

Negar (p ∨ q) produce ¬p ∧ ¬q. Esta equivalencia es fundamental para simplificar expresiones lógicas en pruebas formales.

6. Inferir sobre r en una implicación

Con p ⇒ (q ⇒ r) verdadera y q falsa, la implicación q ⇒ r es verdadera sin importar r. Por tanto, r puede ser verdadero o falso.

7. Justificar la negación de la conclusión en el método de árbol

Negar la conclusión permite buscar una contradicción entre premisas y conclusión negada. Si todas las ramas se cierran, el argumento es válido; de lo contrario, existe una interpretación que lo invalida.

8. Simplificar A ∧ B a A

Esta simplificación se basa en la regla de absorción, que es válida cuando B está implícitamente contenido en una conjunción mayor.

Conclusión

Dominar los conceptos básicos de la lógica proposicional —proposiciones, tautologías, contradicciones, tablas de verdad, leyes de De Morgan, implicación y métodos de prueba como el árbol— es esencial para cualquier estudiante de informática o matemáticas. Estos fundamentos no solo facilitan la resolución de ejercicios académicos, sino que también son la base de algoritmos de verificación, lenguajes de programación y sistemas de inteligencia artificial.

Al practicar con los ejemplos presentados y aplicar las reglas de simplificación de forma sistemática, mejorarás tu capacidad de razonamiento lógico y estarás mejor preparado para enfrentar desafíos más avanzados en teoría de la computación y lógica formal.