Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 153 vistas

    Satisfacibilidad Matemática

    Cargado por

    Yannira Aquino
    El documento define la satisfacibilidad en lógica proposicional como la capacidad de una fórmula de ser verdadera bajo alguna interpretación. Un problema es satisfacible si existe al menos una asignación de valores a las variables que lo hace verdadero, e insatisfacible si todas las asignaciones posibles lo hacen falso. Las tautologías son fórmulas verdaderas bajo toda interpretación, mientras que las contradicciones son fórmulas falsas bajo toda interpretación.

    Copyright:

    © All Rights Reserved
    Descargue como DOCX, PDF, TXT o lea en línea desde Scribd

    Satisfacibilidad Matemática

    Cargado por

    Yannira Aquino
    153 vistas2 páginas
    El documento define la satisfacibilidad en lógica proposicional como la capacidad de una fórmula de ser verdadera bajo alguna interpretación. Un problema es satisfacible si existe al menos una asignación de valores a las variables que lo hace verdadero, e insatisfacible si todas las asignaciones posibles lo hacen falso. Las tautologías son fórmulas verdaderas bajo toda interpretación, mientras que las contradicciones son fórmulas falsas bajo toda interpretación.

    Descripción original:

    Satisfacibilidad

    Título original

    SATISFACIBILIDAD MATEMÁTICA

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

    DOCX, PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    El documento define la satisfacibilidad en lógica proposicional como la capacidad de una fórmula de ser verdadera bajo alguna interpretación. Un problema es satisfacible si existe al menos una asignación de valores a las variables que lo hace verdadero, e insatisfacible si todas las asignaciones posibles lo hacen falso. Las tautologías son fórmulas verdaderas bajo toda interpretación, mientras que las contradicciones son fórmulas falsas bajo toda interpretación.

    Copyright:

    © All Rights Reserved
    Descargue como DOCX, PDF, TXT o lea en línea desde Scribd
    Descargar como docx, pdf o txt
    153 vistas2 páginas

    Satisfacibilidad Matemática

    Cargado por

    Yannira Aquino
    El documento define la satisfacibilidad en lógica proposicional como la capacidad de una fórmula de ser verdadera bajo alguna interpretación. Un problema es satisfacible si existe al menos una asignación de valores a las variables que lo hace verdadero, e insatisfacible si todas las asignaciones posibles lo hacen falso. Las tautologías son fórmulas verdaderas bajo toda interpretación, mientras que las contradicciones son fórmulas falsas bajo toda interpretación.

    Copyright:

    © All Rights Reserved
    Descargue como DOCX, PDF, TXT o lea en línea desde Scribd
    Descargar como docx, pdf o txt
    Está en la página 1de 2

    SATISFACIBILIDAD

    En lógica proposicional, la satisfacibilidad se define como la capacidad de una fórmula o


    conjunto de ellas en ser verdaderas. Decimos que una fórmula es satisfacible cuando después
    de analizarla bajo una interpretación dada afirmamos que tiene valor 1; o lo que es lo mismo,
    es verdadera.

    es válida es insatisfacible.
    es válida es satisfacible.
    es satisfacible ↛ es insatisfacible.
    es satisfacible
    I(p) = I(q) = 1
    es satisfacible
    I(p) = 1, I(q) = 0

     Un problema es satisfacible si existe al menos una asignación de valores a las variables del
    problema que lo hagan verdadero ( ).

     Un problema es insatisfacible si todas las posibles asignaciones de valores hacen el problema


    siempre falso ( ).

    TAUTOLOGÍAS Y CONTRADICCIONES

     Una fórmula se dice que es válida o tautología, si para toda interpretación .

     Una fórmula se dice inconsistente, insatisfacible o que es una contradicción,


    si para toda interpretación .

    Ejemplos:

    1. (p → q) ∨ (q → p) es una tautología.

    2. (p → q) ∧ ¬ (p → q) es una contradicción.

    3. p → q es contingente

    p q p→q q→p (p → q) ∨ (q → p) ¬(p → q) (p → q) ∧ ¬(p → q)


    1 1 1 1 1 0 0
    1 0 0 1 1 1 0
    0 1 1 0 1 0 0
    0 0 1 1 1 0 0
    TODAS LAS FÓRMULAS

    Tautologías Contingentes Contradicciones

    Verdadera en todas las Verdadera en algunas Falsa en todas las


    interpretaciones interpretaciones y falsa interpretaciones
    en otras
    (ej. p ∨ ¬p) (ej. p ∧ ¬p)
    (ej. p → q)

    SAFISFACIBLES INSATISFACIBLES

    TODAS LAS FÓRMULAS

    ¿Qué es un Algoritmo?

    En el contexto matemático, los algoritmos son una serie de normas o leyes específicas que
    hace posible la ejecución de actividades, cumpliendo una serie de pasos continuos que no le
    originen dudas a la persona que realice dicha actividad.

    Algoritmos para SAT y TAUT

     Tablas de verdad para |= (p ↔ q) ∨ (q ↔ p)


    p q (p ↔ q) (q ↔ p) (p ↔ q) ∨ (q ↔ p)
    1 1 1 1 1
    1 0 0 0 0
    0 1 0 0 0
    0 0 1 1 1

     Método de Quine para |= (p ↔ q) ∨ (q ↔ p)

    (p ↔ q) ∨ (q ↔ p)
    0 0 1 0 1 0 0

    1 0 0 0 0 0 1

    También podría gustarte