Tautología

Verificación y Validación de Software
Entrada 2

¿Qué es una Tautología?

Tautología es una fórmula de un sistema que resulta verdadera para cualquier interpretación. En otras palabras, se trata de una expresión lógica que es verdadera para todos los posibles valores de verdad de sus componentes atómicos.

Determinar si una fórmula es una tautología

Para determinar si una fórmula cualquiera es una tautología, basta con considerar todas las posibles interpretaciones de las fórmulas atómicas, y calcular el valor de verdad del todo. Esto se logra mediante una tabla de verdad.

Tarea

Encontrar por nosotros mismos una fórmula que resulte ser una tautología. Esta debe contener por lo menos 3 variables y 4 conectivos, que pueden ser operadores de negación, disyunción y conjunción.

Solución

La forma en que logre encontrar una tautología fue en un inicio a "prueba y error", ya que lo que estaba haciendo era escribir una fórmula cualquiera, creada con operadores al azar y luego probar mediante una tabla de verdad si esta daba como resultado siempre un valor "verdadero" o 1, pero resultaba ineficiente ya que era tardado probar con las 8 diferentes entradas de valores posibles, representadas en una tabla de verdad.

Entonces para no perder tiempo en verificar cada fórmula creada, decidí hacer un programa en python que me ayudara a verificar más rápidamente si mi fórmula daba verdadero para todas las diferentes y posibles entradas, según una tabla de verdad.

Programa tatutologia.py


Entonces lo que se hace es escribir mediante funciones, en el apartado de la variable formula, los operadores lógicos de la fórmula que se desea probar.

Una de las fórmulas que probé fue la siguiente:
F(A,B,C) = (A|¬B)^(C|¬C)

La cual escrita en el programa cambiaba la variable formula por:
formula = bool(conjuncion(disyuncion(A, negacion(B)) , disyuncion(C, negacion(C))))

Y el resultado que arrojo no fue una tautología ya que en más de una entrada dio como resultado False.

Luego hice unos cambios en la fórmula, y me resulto una tautología, y la fórmula usada fue:
F(A,B,C) = ((A|¬A) | ¬B) ^ (C|¬C)

Cuya fórmula escrita en mi programa es:
formula = bool(conjuncion(disyuncion(disyuncion(A, negacion(A)), negacion(B)) , disyuncion(C, negacion(C))))

Y la captura de pantalla de la ejecución donde se muestra que para la tabla de verdad dada, siempre da como resultado un True.

Árbol

P = ((A|¬A) | ¬B) ^ (C|¬C)

Tabla de verdad

Para comprobar con la tabla de verdad que todos los valores dan Verdadero, hacemos paso por paso, tal y como se desglosa en el árbol y vemos que obtenemos como resultado en la última columna los valores de 1 o Verdadero.

Nota: En el programa mostrado también se incluyeron funciones para comprobar fórmulas donde se incluyen el operador condicional y bicondicional, pero solo fueron para probar algunos ejemplos de tautologías encontradas en internet, y así verificar que el programa estaba haciendo lo correcto.

Referencias:
Definición de Tautología