等充足可能性

数理論理学（形式論理の分野のサブトピック）では、2つの式が等価満足可能とは、最初の式が2番目の式も常に満足可能である場合であり、その逆もまた同様である。言い換えれば、両方の式が満足可能であるか、両方とも満足不可能であるかのどちらかである。^[1]ただし、等価満足可能な式は、特定の変数の選択に対して一致しない可能性がある。結果として、等価満足可能性は論理的同値性とは異なり、2つの同等の式は常に同じモデルを持つ。一方、等価満足可能な式内では、式が課す基本命題のみが評価される。

等充足可能性は一般に数式の翻訳の文脈で使用され、元の数式と結果の数式が等充足可能であれば、翻訳が正しいと定義できます。等充足可能性を維持する翻訳の例としては、スコレム化や、ツェイチン変換などの連言標準形への翻訳があります。

命題論理から、すべての二項選言が に置き換えられた命題論理への変換（は新しい変数（置き換えられた選言ごとに 1 つ））は、充足可能性が保持される変換です。つまり、元の式と結果の式は等充足可能です。これら 2 つの式は同等ではないことに注意してください。最初の式には、が真であるのに対しと が偽であるモデルがあります（式の真理値とは無関係であることのモデルの真理値）。しかし、これは がこの場合真でなければならない 2 番目の式のモデルではありません。${\displaystyle a\vee b}$${\displaystyle ((a\vee n)\wedge (\neg n\vee b))}$${\displaystyle n}$${\displaystyle b}$${\displaystyle a}$${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$