null
US
Iniciar Sesión
Regístrate Gratis
Registro
Hemos detectado que no tienes habilitado Javascript en tu navegador. La naturaleza dinámica de nuestro sitio requiere que Javascript esté habilitado para un funcionamiento adecuado. Por favor lee nuestros
términos y condiciones
para más información.
Siguiente
Copiar y Editar
¡Debes iniciar sesión para completar esta acción!
Regístrate gratis
12482293
Saber si una fórmula (µ) es satisfacible o no
Descripción
Mapa Mental sobre Saber si una fórmula (µ) es satisfacible o no, creado por belyy volk el 25/02/2018.
Mapa Mental por
belyy volk
, actualizado hace más de 1 año
Más
Menos
Creado por
belyy volk
hace más de 6 años
37
0
0
Resumen del Recurso
Saber si una fórmula (µ) es satisfacible o no
Tabla de verdad
El número de la tabla crece exponencialmente según el numero de variables.
1.Según el número de variables, se enlistan todas las combinaciones posibles de valores de verdad.
2.Dichas combinaciones se evalúan en la fórmula.
3.Cada fila de la tabla escupe que valor de verdad que toma la fórmula según el estado de las variables.
Sí todas las casillas que correspondientes a la formula están evaluadas a verdadero.
Si todas se evalúan a falso.
Otro caso.
Es satisfacible, pues sabemos que existe aunque sea un modelo.
Es contradicción y no es satisfacible.
Es una tautología y la fórmula es satisfacible.
Tableau
Negamos la fórmula
Eliminamos equivalencias e implicaciones
Se construye en forma de árbol.
Si tenemos una conjunción el árbol crece 2 ramas hacia abajo.
Si tenemos una disyunción se desglosa en 2 ramas.
Buscamos cerrar ramas encontrando contradicciones.
Si logramos cerrar todas las ramas o algunas, µ es satisfacible.
En otro caso no lo es.
Resolución binaria
Se lleva a µ a su forma normal conjuntiva
Una vez hecho esto se enlistan las cláusulas
Y usando la reducción Binaria de Robinson se busca llegar a tener una literal y su complemento.
Si esto ocurre, la cláusula vacía nos dice que µ es insatisfacible.
Si no se puede llegar a la cláusula vacía µ es satisfacible.
Puede usarse refutación
Interpretaciones
Se propone que el valor de verdad de la fórmula es verdadero.
Se busca encontrar una combinación de valores de verdad en las variables.
Tal que dicha combinación sea un modelo en µ
Si es posible dar con el modelo, entonces µ es satisfacible, en otro caso es una contradicción.
Equivalencias
Dadas ciertas reglas descomponemos una formula a expresiones más sencillas
buscamos hacer la fórmula lo mas pequeña posible
logrado eso, si tenemos T ó una fórmula es satisfacible
Si llegamos a una contradicción no es satisfacible.
Mostrar resumen completo
Ocultar resumen completo
¿Quieres crear tus propios
Mapas Mentales
gratis
con GoConqr?
Más información
.
Similar
La Química
maya velasquez
Lenguas que influyen en el español
dorydan01
Primera Guerra Mundial
Diego Santos
MODELOS PEDAGÓGICOS
wfas197
ESTRUCTURA DEL ESTADO COLOMBIANO
eduardo cuellar
Integración del Personal
Freddy López8597
Sistema Óseo
Valerie Argueta
Literatura Barroca y Neoclásica
Jose Lopez
CAPAS de la TIERRA
Ulises Yo
ANATOMÍA...
Ulises Yo
EL IMPERIALISMO
andrea acosta
Explorar la Librería