Logica sat

Q es un sat :
Dada una formula proposicional en FNC para determinar si es es satisfactible
Existen varios algoritmos para poder resolver los problemas SAT se puede decir q el mas exacto es elmétodo de las tablas de verdad
Algoritmo de codificación SAT reducida:
Esta es una estructura en dfd de cómo poder hacer un programa q nos resuelva en nuestros problemas SAT

Variantes del problemaSAT:
Hay muchos tipos de variantes para resolver problemas SAT
La mayoría de problemas son reducibles en tiempo polinomial a SAT, esto no quiere decir q hay un algoritmo q transforma problemas a SAT yviceversa y tal algoritmo es polinomial
Estos problemas, tanto las variantes de SAT como los reducibles a SAT en tiempo polinomial, se pueden considerar equivalentes a SAT en el sentido de que unalgoritmo que trabaje eficientemente para SAT resolvería cualquiera de los problemas también eficientemente.
Algunos de las variantes y problemas equivalentes a SAT son las siguientes:
 ·         SAT(k) – Dada una fórmula en FNC con a lo sumo k literales por cláusula, determinar si esta es satisfactible.
·         SAT*(k) – Dada una fórmula en FNC con exactamente k literales por cláusula, determinar siesa es satisfactible.
·         SAT(3) – Dada una fórmula en FNC con a lo sumo 3 literales por cláusula, determinar si esta es satisfactible.
·         Vertex Cover – Dado un grafo G y un númeronatural k, determinar si hay un recubrimiento de vértices de G de tamaño k.
·         SUBSET-SUM – Dado un conjunto A, una función de peso w y un número natural k, determinar si existe un subconjunto Bde A tal que w(B) = A.
·         PARTICIÓN – Dado un conjunto A y una función de peso w, determinar si existe una partición de A {B,C} tal que w(B) = w(C).
·         3-COL – Determinar si un grafoes 3-coloreable.
·         HAM-PATH – Dado un grafo G y dos nodos x e y pertenecientes a G, determinar si existe un camino Hamiltoniano de x a y.
·         Tableros semánticos.
El...