意味論的帰結と充足不能性の関係の補題
タイトルの補題名は一般的なものではないmrsekut.icon
補題
いかなる論理式の集合$ \Gammaと論理式$ \varphiについても、以下が成り立つ
$ \Gamma\vDash\varphi\Leftrightarrow \Gamma\cup\{\lnot\varphi\}は充足可能ではない 意味論的に矛盾
証明
$ \Rightarrow側
$ \Gamma\vDash\varphiということは、$ \Gammaのモデル$ Mに対し、$ M\vDash\varphiだということ。
$ \Rightarrow$ M\nvDash\lnot\varphiになる
$ \Rightarrow$ \Gamma\cup\{\lnot\varphi\}は充足可能でない
こっちはそれほどだねmrsekut.icon
$ \Leftarrow側
$ \Gamma\cup\{\lnot\varphi\}の充足する真理値割り当てが存在しない
$ \Rightarrow$ \Gammaを充足し、$ \varphiを偽にする真理値割り当てが存在しない
$ \Rightarrow$ \Gamma\vDash\varphi
こっちがわからんくなるmrsekut.icon
参考
対偶を証明している