Equivalencias Lógicas y Demostraciones

• Las demostraciones lógicas utilizan equivalencias lógicas para transformar proposiciones y llegar a una conclusión válida.
• Una equivalencia lógica es una relación entre dos proposiciones que son verdaderas o falsas simultáneamente.

Equivalencias Lógicas

• Doble negación: ¬(¬p) ≡ p (La negación de la negación de una proposición es la proposición original).
• Leyes de idempotencia: p ∨ p ≡ p, p ∧ p ≡ p (Una proposición unida a sí misma por "o" o "y" es equivalente a la proposición misma).
• Leyes conmutativas: p ∨ q ≡ q ∨ p, p ∧ q ≡ q ∧ p (El orden de las proposiciones no altera el resultado de la disyunción o conjunción).
• Leyes asociativas: (p ∨ q) ∨ r ≡ p ∨ (q ∨ r), (p ∧ q) ∧ r ≡ p ∧ (q ∧ r) (La agrupación de proposiciones no afecta el resultado).
• Leyes distributivas: p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r), p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) (Distribución de "o" sobre "y" y viceversa).
• Leyes de absorción: p ∨ (p ∧ q) ≡ p, p ∧ (p ∨ q) ≡ p (Una proposición absorbe una conjunción o disyunción que la incluye).
• Leyes de De Morgan: ¬(p ∨ q) ≡ ¬p ∧ ¬q, ¬(p ∧ q) ≡ ¬p ∨ ¬q (La negación de una disyunción es la conjunción de las negaciones, y viceversa).
• Ley de la condicional: p → q ≡ ¬p ∨ q (Una implicación es equivalente a la negación del antecedente o el consecuente).
• Ley del bicondicional: p ↔ q ≡ (p → q) ∧ (q → p) (Un bicondicional es equivalente a la conjunción de las dos implicaciones).
• Otras equivalencias: p ∨ ¬p ≡ T (tautología), p ∧ ¬p ≡ F (contradicción) (Una proposición o su negación siempre es verdadera, una proposición y su negación siempre es falsa).

Propiedades de la Implicación

• Modus Ponens: Si p → q es verdadera y p es verdadera, entonces q es verdadera.
• Modus Tollens: Si p → q es verdadera y q es falsa, entonces p es falsa.
• Silogismo Hipotético: Si p → q es verdadera y q → r es verdadera, entonces p → r es verdadera.
• Adición: Si p es verdadera, entonces p ∨ q es verdadera.
• Simplificación: Si p ∧ q es verdadera, entonces p es verdadera y q es verdadera.
• Conjunción: Si p es verdadera y q es verdadera, entonces p ∧ q es verdadera.
• Silogismo Disyuntivo: Si p ∨ q es verdadera y p es falsa, entonces q es verdadera.

Leyes de De Morgan

• ¬(p ∨ q) ≡ ¬p ∧ ¬q: La negación de una disyunción (p o q) es equivalente a la conjunción de las negaciones de p y q (no p y no q). En términos de conjuntos, el complemento de una unión es la intersección de los complementos.
• ¬(p ∧ q) ≡ ¬p ∨ ¬q: La negación de una conjunción (p y q) es equivalente a la disyunción de las negaciones de p y q (no p o no q). En términos de conjuntos, el complemento de una intersección es la unión de los complementos.

Demostraciones Directas

• Se parte de las premisas y se aplican reglas de inferencia y equivalencias lógicas para llegar a la conclusión deseada.
• Se asume que las premisas son verdaderas.
• Se deduce la conclusión aplicando las reglas lógicas.
• Ejemplo:
  • Premisa 1: p → q
  • Premisa 2: p
  • Conclusión: q (por Modus Ponens)

Demostraciones Indirectas

• Demostración por Contraposición: Para demostrar p → q, se demuestra ¬q → ¬p.
  • Se asume la negación de la conclusión (¬q).
  • Se deduce la negación de la premisa (¬p).
  • Si se logra, entonces p → q es verdadera.
• Demostración por Contradicción (Reductio ad Absurdum): Para demostrar p, se asume ¬p y se deriva una contradicción.
  • Se asume la negación de la proposición a demostrar (¬p).
  • Se deducen consecuencias lógicas de ¬p.
  • Si se llega a una contradicción (q ∧ ¬q), entonces ¬p es falsa y, por lo tanto, p es verdadera.

Teoremas Fundamentales de la Lógica

• Teorema de la Deducción: Si Γ ∪ {p} ⊢ q, entonces Γ ⊢ p → q (Si de un conjunto de premisas Γ junto con p se deduce q, entonces de Γ se deduce p → q).
• Teorema de la Completitud: Si una fórmula es lógicamente válida, entonces existe una demostración formal de ella.
• Teorema de la Solidez: Si existe una demostración formal de una fórmula, entonces la fórmula es lógicamente válida.
• Teorema de Löwenheim-Skolem: Si una teoría de primer orden tiene un modelo infinito, entonces tiene un modelo de cada cardinalidad infinita.
• Teorema de la Indecidibilidad de Gödel: Para cualquier sistema axiomático formal suficientemente poderoso para describir la aritmética de los números naturales, existen proposiciones verdaderas sobre los números naturales que no pueden ser probadas dentro del sistema. Además, ningún sistema de este tipo puede probar su propia consistencia.