Equivalencias

Tema 1.9.1
Junto con las tautologías un concepto muy utilizado es el de equivalencia.
Definición: Dos fórmulas lógicas son equivalentes si tienen los mismos valores de verdad para todos losposibles valores de verdad de sus componentes atómicos.
Ejemplo 2: Las dos fórmulas siguientes son equivalentes:
(p → ¬q) ∨ (¬p ∨ r)          ¬p ∨ ¬q ∨ r
de manera similar a lo establecido en lassecciones anteriores, elaboramos el árbol sintáctico y la tabla

p | q | r | ¬q | ¬p | p → ¬q | ¬p ∨ r | (p → ¬q) ∨ (¬p ∨ r) | ¬ p ∨ ¬q | ¬p ∨ ¬q ∨ r |
V | V | V | F | F | F | V | V | F | V |
V |V | F | F | F | F | F | F | F | F |
V | F | V | V | F | V | V | V | V | V |
V | F | F | V | F | V | F | V | V | V |
F | V | V | F | V | V | V | V | V | V |
F | V | F | F | V | V | V | V | V |V |
F | F | V | V | V | V | V | V | V | V |
F | F | F | V | V | V | V | V | V | V |
donde se puede observar que la última yla antepenúltima columnas son iguales.
Las equivalencias serelacionan con las tautologías de la siguiente forma.
Teorema: Si dos fórmulas lógicas son eqivalentes entonces la fórmula que se obtiene al operarlas con la bicondiconal es una tautología.
Si F ≡ Gentonces F ⇔ G
La propiedad inversa también se cumple pues si una bicondicional es una tautología, las fórmulas que la componen son equivalentes. El teorema y su inverso se comprueban directamente de latabla de verdad de la bicondicional, ver sección 1.3.4

Tautologías Fundamentales |

p ∨ ¬p | Ley del medio excluido |
¬ (p ^ ¬p) | Ley de no contradicción |
((p → q)^p) → q | Modus ponendoponens |
((p → q)^ ¬ q) → ¬ p | Modus tollendo tollens |
((p ∨ q) ∧ ¬ p) → q | Silogismo Disyuntivo |
((p → q) ∧ (q → r)) → (p → r) | Silogismo Hipotético |

La comprobación de cualquiera delas tautologías anteriores es directa, es suficiente hacer la tabla de verdad y se obtendrá la columna correspondiente a la fórmula con valores verdaderos únicamente, como se mencionó en el Tema 1.9...