Tautología

Buen día.

Esta semana en la clase de verificación y validación de software estudiamos algunos elementos básicos de la lógica proposicional y como ejercicio, nos fue encargado encontrar una tautología con al menos 3 átomos y algunos conectivos lógicos.

Pero primera ¿Qué es una Tautología?

Según wikipedia:
"En lógica, una tautología es una fórmula bien formada de un sistema de lógica proposicional que resulta verdadera para cualquier interpretación."


Solución

Bueno ahora explicare como encontré una tautología con las características requeridas para el ejercicio en clase.
Lo primero que hice fue construir una tabla de verdad con las características que buscaba osea que tuviera tres átomos lógicos y que en la proposición osea F(A,B,C) cada entrada nos diera como salida "Verdadero" o "1", y a partir de ahí construí preposiciones modulares que sean verdaderas únicamente cuando la entrada es la que le corresponde en la tabla.

Una vez teniendo estos módulos de proposiciones los uní todos con conexiones "or"  o "|" para construir una proposición que con cualquier entrada posible siempre su salida sea verdadero.

F(A,B,C) = ¬A^¬B^¬C | ¬A^¬B^C | ¬A^B^¬C | ¬A^B^C | A^¬B^¬C | A^¬B^C | A^B^¬C | A^B^C



Pero como hacer una árbol con esta proposición hubiera sido muy pesado, decidí minimizarlo usando mapas de Karnaugh y usando términos como muestro a continuación:

.
    0         1         2         3        6         7       4        5
F(A,B,C) = ¬A^¬B^¬C | ¬A^¬B^C | ¬A^B^¬C | ¬A^B^C | A^¬B^¬C | A^¬B^C | A^B^¬C | A^B^C



       AB

    00 01 11 10

C 0  0  2  4  6

  1  1  3  5  7



       AB

    00 01 11 10

C 0 ___________

  1  1  1  1  1



       AB

    00 01 11 10

C 0  1  1  1  1

  1 ___________



a^b | ¬a^b = (a|¬a)^b =  b # formulas

a|b ^ ¬a|b = (a^¬a)|b =  0 # formulas



F(A,B,C) = (¬A^¬B | ¬A^B | A^¬B | A^B)^¬C | (¬A^¬B | ¬A^B | A^¬B | A^B)^C

F(A,B,C) = (¬A^¬B | ¬A^B | A^¬B | A^B) | (C^¬C)

F(A,B,C) = ( ¬A^(¬B|B) |  A^(¬B|B) ) | (C^¬C)

F(A,B,C) = ( ¬A^(¬B|B) |  A^(¬B|B) ) | (C^¬C)

F(A,B,C) = ( (¬A^A) | (¬B^B) ) | (C^¬C)

F(A,B,C) = (¬A^A) | (¬B^B) | (C^¬C)

Dando como resultado todo esto la siguiente proposición:

F(A,B,C) = (A|¬A) ^ (B|¬B) ^ (C|¬C)  
 
Y para terminar aquí esta la proposición estructurada como un árbol:

Referencias:
http://es.wikipedia.org/wiki/Tautolog%C3%AD