規則の健全性と完全性
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/08/01 09:50 UTC 版)
個々に挙げられた規則の重要な性質は健全性と完全性である。直感的には、これらの規則は正しくしかも他に必要な規則はないということである。これは以下のようにして形式化される。 真理値の割り当てを、命題変数に対して真( ⊤ {\displaystyle \top } )または偽( ⊥ {\displaystyle \bot } )の値を対応させる関数だと考えることにする。形式的でない言い方をすれば、真理値の割り当てとは、特定の叙述が真になり他は偽になるような「おきうる事態」(またはありうる世界)についての説明だと理解できる。その「事態」においてそれぞれの式が正しくなるのはどんなときかを定めることで式の意味論が定式化できる。 真理値の割り当て A {\displaystyle A} がどんなときに特定の整式を充足するか、ということを以下の規則によって定める。 A ( P ) = ⊤ {\displaystyle A(P)=\top } であるとき、およびそのときに限って A {\displaystyle A} は命題変数 P {\displaystyle P} を充足する A {\displaystyle A} が ϕ {\displaystyle \phi } を充足しないとき、およびそのときに限って A {\displaystyle A} は ¬ ϕ {\displaystyle \lnot \phi } を充足する A {\displaystyle A} が ϕ {\displaystyle \phi } と ψ {\displaystyle \psi } を充足するとき、およびそのときに限って A {\displaystyle A} は ( ϕ ∧ ψ ) {\displaystyle (\phi \land \psi )} を充足する A {\displaystyle A} が ϕ {\displaystyle \phi } か ψ {\displaystyle \psi } の少なくともどちらかを充足するとき、およびそのときに限って A {\displaystyle A} は ϕ ∨ ψ {\displaystyle \phi \lor \psi } を充足する A {\displaystyle A} が ϕ {\displaystyle \phi } を充足するのに ψ {\displaystyle \psi } を充足しないということがないとき、およびそのときに限って A {\displaystyle A} は ( ϕ → ψ ) {\displaystyle (\phi \rightarrow \psi )} を充足する この定義によって式 ϕ {\displaystyle \phi } が特定の式の集合 S {\displaystyle \mathbb {S} } から従うとはどういうことなのかを定式化できる。格式張らずにいえばこれは、 S {\displaystyle \mathbb {S} } の式が成り立っているようなすべての世界において ϕ {\displaystyle \phi } が成立していることだ、といえる。これは次のように形式化できる: S {\displaystyle \mathbb {S} } の式をすべて充足するような真理値の割り当てが必ず ϕ {\displaystyle \phi } を充足するとき、整式 ϕ {\displaystyle \phi } は S {\displaystyle \mathbb {S} } から意味論的に帰結する(または導かれる)、という。 最後に、統語的な帰結という関係を、 ϕ {\displaystyle \phi } が上に挙げた推論規則に従って有限の段階で S {\displaystyle \mathbb {S} } の式から導出されるとき、およびそのときに限って ϕ {\displaystyle \phi } は S {\displaystyle \mathbb {S} } から統語的に帰結する、として定める。これによって推論規則の集合が健全だとか完全だとかいうのはどういうことなのかを定式化できる。 健全性 もし ϕ {\displaystyle \phi } が整式の集合 S {\displaystyle \mathbb {S} } から統語的に帰結するなら ϕ {\displaystyle \phi } は S {\displaystyle \mathbb {S} } から意味論的に帰結する 完全性 もし ϕ {\displaystyle \phi } が S {\displaystyle \mathbb {S} } から意味論的に帰結するなら ϕ {\displaystyle \phi } は S {\displaystyle \mathbb {S} } から統語的に帰結する 上記の自然命題論理の規則の集合についてはこれらが成り立っている。
※この「規則の健全性と完全性」の解説は、「命題論理」の解説の一部です。
「規則の健全性と完全性」を含む「命題論理」の記事については、「命題論理」の概要を参照ください。
- 規則の健全性と完全性のページへのリンク