null
US
Sign In
Sign Up for Free
Sign Up
We have detected that Javascript is not enabled in your browser. The dynamic nature of our site means that Javascript must be enabled to function properly. Please read our
terms and conditions
for more information.
Next up
Copy and Edit
You need to log in to complete this action!
Register for Free
12482293
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.
Mind Map by
belyy volk
, updated more than 1 year ago
More
Less
Created by
belyy volk
over 6 years ago
38
0
0
Resource summary
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.
Show full summary
Hide full summary
Want to create your own
Mind Maps
for
free
with GoConqr?
Learn more
.
Similar
Lord of the Flies
lmg719
Creando un conjunto de fichas
PatrickNoonan
A-Level Chemistry: Atomic Structure
cian.buckley+1
English Language Techniques
Zakiya Tabassum
Quick tips to improve your Exam Preparation
James Timpson
Globalisation Case Studies
annie
exothermic and endothermic reactions
janey.efen
1PR101 2.test - Část 2.
Nikola Truong
1PR101 2.test - Část 5.
Nikola Truong
Unit 1.1 Systems Architecture
Mathew Wheatley
Účto Fífa 1/6
Bára Drahošová
Browse Library