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

                                          A2 Level OCR: Communication & Homeostasis
                                          Ollie O'Keeffe
                                          History of Psychology
                                          Reuben Caruana
                                          Biological molecules
                                          sadiaali363
                                          Hitler's Chancellorship
                                          c7jeremy
                                          Physics P2
                                          Phoebe Drew
                                          AQA AS Biology Unit 2 The Variety of Life
                                          elliedee
                                          Strength and Limitations of research methods
                                          Isobel Wagner
                                          Maths GCSE - What to revise!
                                          livvy_hurrell
                                          Characters in "An Inspector Calls"
                                          Esme Gillen
                                          TOK mindmap “Without application in the world, the value of knowledge is greatly diminished.”
                                          Gabriela Serpa
                                          APUSH End-of-Year Cram Exam: Set 1
                                          Nathaniel Rodriguez