Saber si una fórmula (µ) es satisfacible o no

Description

Mind Map on Saber si una fórmula (µ) es satisfacible o no, created by belyy volk on 25/02/2018.
belyy volk
Mind Map by belyy volk, updated more than 1 year ago
belyy volk
Created by belyy volk over 6 years ago
37
0

Resource summary

Saber si una fórmula (µ) es satisfacible o no
  1. Tabla de verdad
    1. El número de la tabla crece exponencialmente según el numero de variables.
      1. 1.Según el número de variables, se enlistan todas las combinaciones posibles de valores de verdad.
        1. 2.Dichas combinaciones se evalúan en la fórmula.
          1. 3.Cada fila de la tabla escupe que valor de verdad que toma la fórmula según el estado de las variables.
            1. Sí todas las casillas que correspondientes a la formula están evaluadas a verdadero.
              1. Si todas se evalúan a falso.
                1. Otro caso.
                  1. Es satisfacible, pues sabemos que existe aunque sea un modelo.
                  2. Es contradicción y no es satisfacible.
                  3. Es una tautología y la fórmula es satisfacible.
          2. Tableau
            1. Negamos la fórmula
              1. Eliminamos equivalencias e implicaciones
              2. Se construye en forma de árbol.
                1. Si tenemos una conjunción el árbol crece 2 ramas hacia abajo.
                  1. Si tenemos una disyunción se desglosa en 2 ramas.
                    1. Buscamos cerrar ramas encontrando contradicciones.
                      1. Si logramos cerrar todas las ramas o algunas, µ es satisfacible.
                        1. En otro caso no lo es.
                        2. Resolución binaria
                          1. Se lleva a µ a su forma normal conjuntiva
                            1. Una vez hecho esto se enlistan las cláusulas
                              1. Y usando la reducción Binaria de Robinson se busca llegar a tener una literal y su complemento.
                                1. Si esto ocurre, la cláusula vacía nos dice que µ es insatisfacible.
                                  1. Si no se puede llegar a la cláusula vacía µ es satisfacible.
                                    1. Puede usarse refutación
                          2. Interpretaciones
                            1. Se propone que el valor de verdad de la fórmula es verdadero.
                              1. Se busca encontrar una combinación de valores de verdad en las variables.
                                1. Tal que dicha combinación sea un modelo en µ
                                  1. Si es posible dar con el modelo, entonces µ es satisfacible, en otro caso es una contradicción.
                                  2. Equivalencias
                                    1. Dadas ciertas reglas descomponemos una formula a expresiones más sencillas
                                      1. buscamos hacer la fórmula lo mas pequeña posible
                                        1. logrado eso, si tenemos T ó una fórmula es satisfacible
                                          1. Si llegamos a una contradicción no es satisfacible.
                                          Show full summary Hide full summary

                                          Similar

                                          Physics - Energy, Power & Work
                                          dominique22
                                          Cell Parts & Genetics
                                          Selam H
                                          9 History- The Treaty of Versailles
                                          melgallagher
                                          B5 - Growth and Deveolopment
                                          blairzy123
                                          AQA - English Language Unit 1
                                          Alice Love
                                          Edexcel Additional Science Chemistry Topics 1+2
                                          El Smith
                                          Regular Verbs Spanish
                                          Oliver Hall
                                          Performance y Planificación de Vuelo
                                          Adriana Forero
                                          Creating Mind Maps with GoConqr
                                          Sarah Egan
                                          1PR101 2.test - Část 6.
                                          Nikola Truong
                                          The Children Act 2004
                                          Carina Storm