Fundamentos de lógica proposicional

Fundamentos de lógica proposicional

La lógica proposicional es la rama de la lógica que estudia las proposiciones declarativas y sus relaciones mediante conectores lógicos. En este curso aprenderás los conceptos clave que aparecen en los exámenes típicos de informática, como implicaciones, negaciones, operadores de exclusión, precedencia de operadores y leyes de equivalencia.

1. Implicación (p ⇒ q)

Una 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 cuando p es verdadera y q es falsa.

• Condición necesaria para falsedad: p verdadera y q falsa.

En la práctica, esto significa que una regla del tipo "si ocurre A, entonces ocurre B" solo se viola cuando A ocurre y B no ocurre.

2. Negación (¬p)

La negación invierte el valor de verdad de una proposición. Si p es falsa (F), su negación ¬p será verdadera (V).

• Valor de verdad de ¬p cuando p es falsa: Verdadera.

Esta operación es fundamental para construir expresiones más complejas y para aplicar las leyes de De Morgan.

3. Conectivo exclusivo (p ⊕ q)

El operador XOR (⊕) es verdadero únicamente cuando sus operandos tienen valores diferentes. En otras palabras, p ⊕ q es verdadero si p es verdadera y q es falsa, o viceversa.

• Resultado verdadero: Cuando p y q tienen valores diferentes.

Este conectivo es útil en circuitos digitales y en problemas donde se requiere una diferencia lógica entre dos condiciones.

4. Precedencia de operadores

Al evaluar una expresión lógica, algunos operadores tienen mayor prioridad que otros. La jerarquía típica es:

1. Negación (¬)
2. Conjunción (∧)
3. Disyunción (∨)
4. Implicación (⇒) y equivalencia (⇔)

En la expresión ¬p ∧ q ∨ r, el operador con mayor precedencia es la negación (¬), por lo que se evalúa primero ¬p, luego la conjunción ∧ y finalmente la disyunción ∨.

5. Leyes de De Morgan

Las leyes de De Morgan permiten transformar negaciones de conjunciones y disyunciones en expresiones equivalentes:

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

En nuestro quiz, la equivalencia correcta es ¬p ∨ ¬q. Estas leyes son esenciales para simplificar fórmulas y para diseñar circuitos lógicos.

6. Tautologías

Una tautología es una fórmula que siempre resulta verdadera, sin importar los valores de sus variables. El ejemplo clásico es la ley del tercero excluido:

• p ∨ ¬p – siempre verdadera.

Otras expresiones como p ∧ ¬p (contradicción) o p ⊕ p (siempre falsa) no son tautologías.

7. Terminología de la implicación

En una implicación p ⇒ q, la proposición p se denomina hipótesis (o antecedente) y q es la consecuencia (o consecuente). Conocer estos términos ayuda a leer y redactar argumentos lógicos correctamente.

8. Tablas de verdad y número de filas

Para una fórmula con n variables distintas, la tabla de verdad contiene 2ⁿ filas, ya que cada variable puede ser verdadera o falsa.

• Con 3 variables distintas, la tabla tiene 8 filas (2³ = 8).

Esta regla es fundamental para planificar el análisis de cualquier expresión proposicional.

9. Resumen de conceptos clave

• Implicación: falsa solo cuando p es verdadera y q es falsa.
• Negación: invierte el valor de verdad.
• XOR: verdadero cuando los operandos difieren.
• Precedencia: ¬ > ∧ > ∨ > ⇒.
• De Morgan: ¬(p ∧ q) ≡ ¬p ∨ ¬q.
• Tautología: p ∨ ¬p.
• Hipótesis: antecedente de una implicación.
• Tablas de verdad: 2ⁿ filas para n variables.

10. Preguntas de práctica

Para consolidar lo aprendido, intenta responder las siguientes preguntas sin consultar la solución:

1. ¿Qué valor de verdad tiene la expresión ¬(p ∨ ¬q) cuando p es falsa y q es verdadera?
2. En la expresión p ∧ ¬q ∨ r, ¿qué operador se evalúa primero?
3. ¿Cuántas filas tendría la tabla de verdad de una fórmula con 4 variables distintas?

Revisa tus respuestas comparándolas con los conceptos explicados en cada sección.