Solucionador SAT: definición, ejemplo y equivalente en inglés
Un solucionador SAT (demostrador SAT, SAT solver) es un programa que decide si una fórmula booleana es satisfacible, devolviendo una asignación que la satisface cuando existe, por búsqueda y no enumerando cada fila. El motor usa uno para fórmulas con más de 20 entradas.
El problema de satisfacibilidad booleana, SAT, pregunta si alguna asignación hace verdadera una fórmula. Un solucionador lo responde propagando valores forzados y retrocediendo sobre las elecciones, normalmente sobre una forma normal conjuntiva, y los solucionadores modernos manejan fórmulas con miles de variables que ninguna tabla de verdad podría listar. Toda comprobación exacta se reduce a SAT: una tautología es una fórmula cuya negación es insatisfacible, y dos fórmulas son equivalentes cuando su XOR es insatisfacible. La respuesta es exacta, pero una instancia difícil puede tardar, así que un solucionador también puede informar de que no terminó.
El artefacto de esta página es una fórmula que ninguna tabla puede mostrar: all_24, el AND de 24 variables x1 a x24, cuya tabla tendría más de dieciséis millones de filas; la página no tiene tabla de verdad y las comprobaciones no informan de recuento de filas. La comprobación de satisfacible se cumple con el testigo que pone las 24 variables en TRUE, la de contradicción se viola con esa misma asignación, y la de tautología se viola con el contraejemplo que pone las 24 en FALSE. Cada testigo se volvió a evaluar antes de mostrarse.
Los solucionadores SAT están detrás de la verificación de hardware, la planificación, la resolución de dependencias de paquetes y la comprobación de modelos de software, y los solucionadores SMT los extienden con aritmética; la exportación a SMT-LIB del motor entrega una fórmula a esas herramientas. El término se confunde con un generador de tablas de verdad (enumeración y no búsqueda), con un demostrador de teoremas para lógicas más ricas y con un simplificador. Un veredicto que el solucionador no alcanza se informa como «No determinado», nunca como aprobado.
Ejemplo
all_24 := x1 AND x2 AND x3 AND x4 AND x5 AND x6 AND x7 AND x8 AND x9 AND x10 AND x11 AND x12 AND x13 AND x14 AND x15 AND x16 AND x17 AND x18 AND x19 AND x20 AND x21 AND x22 AND x23 AND x24 · salida
Comprobaciones exactas
El error habitual
Leer el silencio de un solucionador como resultado. Cuando una comprobación no se decide dentro de su presupuesto, el motor dice «No determinado», que no es ni se cumple ni se viola; la página del error sobre los tiempos agotados explica por qué eso no es un aprobado. Solo un testigo o un barrido exhaustivo son evidencia.
Preguntas
¿La respuesta de un solucionador es menos fiable que la de una tabla de verdad?
No. Una asignación que satisface se comprueba evaluando la fórmula sobre ella, la misma reevaluación que recibe todo testigo en estas páginas. Un veredicto de insatisfacible descansa en que la búsqueda del solucionador fue completa, y el motor informa de una comprobación que no pudo terminar como no determinada en lugar de adivinar.
Relacionado
Véase también
- Satisfacible: definición, ejemplo y equivalente en inglés
- Comprobación exhaustiva: definición, ejemplo y equivalente en inglés
- Forma normal conjuntiva (FNC): definición, ejemplo y equivalente en inglés
- Lógica booleana en SMT-LIB: declare-const, assert y check-sat con Z3
- Un tiempo agotado no es un aprobado: resultados «No determinado»
- Testigo (asignación que satisface): definición, ejemplo y equivalente en inglés
Glosario
Generado a partir del motor de Tangibool, semántica tangibool-semantics/1, motor 1.0.0, compilación . Cada tabla, mapa, simplificación y veredicto de estas páginas lo calculó el motor de Tangibool al compilar el sitio, y cada afirmación la volvió a comprobar el mismo verificador exacto que usa la app. Los límites se indican donde aplican. © 2026 Foreranger LTD.