martes, 14 de agosto de 2012

Tarea 2: Tautología

Para la Tarea 1, debemos crear una expresión lógica que sea una tautología y que ademas cumpliera con ciertos requisitos. Los requisitos a cumplir son:



  • Que cuente por lo menos con 3 variables.
  • Usar por lo menos 4 ocurrencias conectivas ( ands, ors)
  • Tener por lo menos un ^(and), un v(or), y un ¬(not).


  • Tautología

    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; es decir, para cualquier asignación de valores de verdad que se haga a sus fórmulas.

    Un ejemplo sencillo de una tautología es la expresión (p ^ q) -> p, como se puede ver:



    "Mi Tautología"

    La tautología que encontré fue:

    ¬(a ^ (b v c)) v (a v b)  

    Para encontrarla, inicie con una expresión sencilla, y fui agregando más términos hasta completar con las restricciones, despúes comprobé con la tabla de verdad si era o no tautología. Inicialmente no lo fue, ya que mis primeros intentos no arrojaban verdadero para todas las combinaciones, pero modificando poco a poco la expresión, logré convertirla en tautología.

    Diagrama de Árbol

    Estructurando la expresión como un árbol:
    Tabla de Verdad

    La tabla de verdad de la expresión anterior es la siguiente:

     a    b    c     b v c   a ^ (b v c)     ¬(a ^ (b v c)     a v b     ¬(a ^ (b v c)) v (a v b)    
     0  0  0 0 0101
    00110101
    01010111
    01110111
    10000111
    10111011
    11011011
    11111011


    Entonces sí S = ¬(a ^ (b v c)) v (a v b) es verdadera en todas las combinaciones posibles, podemos comprobar que:

      \vDash S 
    (S es una tautología)

    Referencias:

    1 comentario: