Satisfacible: definición, ejemplo y equivalente en inglés
Una fórmula es satisfacible cuando al menos una asignación de valores a sus variables la hace verdadera. La asignación que lo consigue es su testigo, o asignación que satisface.
La satisfacibilidad es la propiedad útil más débil de una fórmula: solo pregunta si la fórmula puede ser verdadera, no si debe serlo. Toda tautología y toda contingencia son satisfacibles; la contradicción es el único tipo de fórmula que no lo es, así que insatisfacible y contradictoria significan lo mismo. Decidir la satisfacibilidad de fórmulas grandes es el problema SAT, el trabajo de un solucionador SAT, y el motor recurre a uno cuando una fórmula tiene más entradas de las que una comprobación exhaustiva puede enumerar.
El artefacto de esta página es la tabla de cuatro filas de (A OR B) AND NOT A. La columna de salida se lee falso, verdadero, falso, falso: la fórmula es verdadera solo en la fila 1. La comprobación de satisfacible se cumple con el testigo A = FALSE, B = TRUE, con el resumen de que f puede ser verdadera porque el testigo la hace verdadera. La comprobación de contradicción se viola con el mismo testigo, y la de tautología se viola con el contraejemplo A = FALSE, B = FALSE. Todo testigo mostrado se ha vuelto a evaluar antes de mostrarse.
En la práctica, la satisfacibilidad es la pregunta que hay detrás de la alcanzabilidad: ¿puede ejecutarse alguna vez esta rama, puede esta regla conceder acceso alguna vez, puede sonar esta alarma? Una regla que no es satisfacible es código muerto con etiqueta de negocio. El término se confunde con la validez, que es el extremo opuesto; una fórmula puede ser satisfacible y fallar en la mayoría de las filas, como este ejemplo, que falla en tres de cuatro.
Ejemplo
f := (A OR B) AND NOT A · salida
Comprobaciones exactas
Tabla de verdad (4 filas)
| # | A | B | f |
|---|---|---|---|
| 0 | FALSO | FALSO | FALSO |
| 1 | FALSO | VERDADERO | VERDADERO |
| 2 | VERDADERO | FALSO | FALSO |
| 3 | VERDADERO | VERDADERO | FALSO |
Lectura en lenguaje claro
Principiantef es verdadero exactamente cuando se cumplen las dos condiciones siguientes:
1. al menos uno entre A y B es verdadero (pueden serlo ambos)
2. A es falso
En todos los demás casos, f es falso.
Sobre los operadores:
- AND (Y) solo es verdadero cuando todas sus partes son verdaderas.
- OR (O) es inclusivo: es verdadero en cuanto al menos una parte es verdadera, también cuando lo son varias.
- NOT (NO) invierte un valor: lo verdadero pasa a ser falso y lo falso, verdadero.
Intermediof es verdadero exactamente cuando se cumplen las dos condiciones siguientes:
1. al menos uno entre A y B es verdadero (pueden serlo ambos)
2. A es falso
En todos los demás casos, f es falso.
Avanzadof es verdadero exactamente cuando se cumplen las dos condiciones siguientes [conjunción ∧]:
1. al menos uno entre A y B es verdadero (pueden serlo ambos) [disyunción inclusiva ∨]
2. A es falso [negación ¬]
En todos los demás casos, f es falso.
Notación formal: (A ∨ B) ∧ ¬A
El error habitual
Leer «satisfacible» como «normalmente verdadera» o «correcta». Significa verdadera en al menos una fila y nada más; (A OR B) AND NOT A es satisfacible y falsa en tres de sus cuatro filas. El testigo dice qué caso mirar, no cuán frecuente es.
Preguntas
¿Cómo muestra el motor que una fórmula es satisfacible?
Produciendo un testigo, una asignación en la que la fórmula se evalúa a VERDADERO, y volviéndolo a evaluar con el evaluador independiente antes de mostrarlo. Para una fórmula que no es satisfacible no hay testigo, y la comprobación informa de que ninguna asignación la hace verdadera.
Relacionado
Ejercicios
Véase también
- Testigo (asignación que satisface): definición, ejemplo y equivalente en inglés
- Contradicción: definición, ejemplo y equivalente en inglés
- Solucionador SAT: definición, ejemplo y equivalente en inglés
- Contingencia: definición, ejemplo y equivalente en inglés
- Generador de tablas de verdad: cualquier expresión booleana, hasta 12 variables, con columnas intermedias
- Premisas inconsistentes: A y NOT A demuestran cualquier cosa (validez vacua)
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.