書記が数学やるだけ#953 健全性の証明-1

構文論と意味論をつなぐ上で重要な健全性の証明について。

問題

説明

数理論理学における「機械的な証明」と「意味的な真実」は、健全性と完全性によって完全に一致する。

2つのアプローチ
・構文論的アプローチ（⊢）：意味（真偽）を考えず、公理と推論規則による記号変形だけで機械的に「証明」すること。
・意味論的アプローチ（⊨） ：モデルや真値付値を考え、どのような解釈の下でもその論理式が「恒真である」ことを評価すること。

健全性と完全性の定義
・健全性（Soundness）：「Σ の定理はすべて Σ の論理的帰結である」（Σ⊢ϕ⟹Σ⊨ϕ） 形式的に証明できるものは、意味的にも常に正しいこと。
・完全性（Completeness）：「Σ の論理的帰結はすべて Σ の定理である」（Σ⊨ϕ⟹Σ⊢ϕ） 意味的に常に正しいものは、形式的に必ず証明できること。

解答

トートロジーである論理式 α→(β→α) が，原子命題の真偽の組み合わせ（4通り）に関わらず常に真になる（恒真）ことを真理値の割り当てから確認する。

任意のトートロジーが恒真であることを示すため，「モデルと状態における記号の充足関係（⊨）」と，それを全論理式に拡張した「真値付値関数（v_M,s ）」が完全に一致することを，論理式の組み立て（否定や含意）に沿って帰納的に証明する。

全称量化と存在量化の否定の同値性について，ドメイン D の要素 d について置き換えながら証明を進める。

全称量化子の含意への分配は，Modus Ponensを用いて示す。

自由出現の制限を伴う全称化について，自由変数として x を含まない論理式の真偽は変数 x の割り当てをどのように変更しても変化しないことから示せる。

等号「=」のセマンティクス（意味論）の定義により、τ1​=τ2​ が真となるのは、モデルのドメインにおいて s(τ1​) と s(τ2​) が集合論的に全く同じオブジェクト（要素）であるとき に限られる。

本記事のもくじはこちら：