Equisatisfactibilidad

En lógica, dos fórmulas son equisatisfactibles si la primera fórmula es satisfactible siempre que la segunda fórmula lo fuera también, y viceversa. En otras palabras: o bien las dos fórmulas son satisfactibles o ninguna es. Dos fórmulas equisatisfactibles pueden tener diferentes modelos, ya que ninguna de ellas o ambas tienen un cierto estilo. Como resultado, tenemos que la equisatisfactibilidad es distinta de la equivalencia lógica porque dos fórmulas lógicamente equivalentes siempre tienen los mismos modelos.

En general, el concepto de equisatisfactibilidad se utiliza en la conversión de fórmulas, es decir, se puede afirmar que una conversión es correcta si la fórmula original y el resultante son equisatisfactibles. Los ejemplos de las conversiones que implican este concepto son Skolemización y algunas transformaciones para llegar a la forma normal conjuntiva.

Una conversión desde la lógica proposicional a la lógica proposicional en la que toda disyunción binaria ${\displaystyle a\vee b}$ es sustituida por ${\displaystyle ((a\vee n)\wedge (\neg n\vee b))}$, donde ${\displaystyle n}$ es una nueva variable (una para cada disyunción sustituida) es una transformación en la que se conserva la satisfactibilidad, o sea, la fórmula original y resultante son equisatisfiables. Tener en cuenta que estas dos fórmulas no son equivalentes: la primera fórmula tiene el modelo en el que ${\displaystyle b}$ es verdadera, mientras que ${\displaystyle a}$ y ${\displaystyle n}$ son falsas, y esto no es un modelo de la segunda fórmula, en la que ${\displaystyle n}$, en este caso, tiene que ser verdadera.