Equivalencias Logicas Y Utilizaciones

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 los posibles 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 las secciones 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
VVV F F F V F V
VVF F F F F F F F
VFV V F V V V V V
VFF V F V F V V V
FVV F V V V V V V
FVF F V V V V V V
FFV V V V V V V V
FFF V V V V V V V

Dnde se puede observar que la última yla antepenúltima columnas son iguales.
Las equivalencias se relacionan 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 ≡ G entonces 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 la tabla de verdad de la bicondicional.

Tautologías Fundamentales
p ∨ ¬p Ley del medio excluido
¬ (p ^ ¬p) Ley de no contradicción
((p → q)^p) → q Modus ponendo ponens
((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 de las 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.

Equivalencias
¬(¬p) ≡ p Doble Negación
¬(p ∨ q) ≡ ¬p ^ ¬q Ley 1 de De Morgan
¬(p ∨ q) ≡ ¬p ^ ¬q Ley 2 de De Morgan
(p → q) ≡ (¬ p ∨ q) Condicional como cláusula
((p → q) ≡ (¬ q → ¬ p) Contrapositiva
¬(p → q) ≡ p ^ ¬q Negación de la Implicación

Ejemplo 2: p → q ≡ ¬p ∨ q

El árbol sintáctico es:
y en la tabla las columnas 3 y 5 son iguales
p q p → q ¬p ¬p ∨ q
VV V F V
VF F F F
FV V V V
FF V V V