完全性とは？
かんぜんせい
完全性とは、意味論的に真であるすべての命題を、形式的な体系の中で証明できるという性質のことです。
完全性（completeness）とは、論理体系が持つ重要な性質の一つで、「意味論的に妥当（すべての解釈のもとで真）なすべての命題は、その体系の推論規則だけを用いて証明できる」ことを意味します。形式的には「⊨φならば⊢φ」と書き表されます。
完全性は、体系の「表現力」と「推論能力」が一致していることを保証します。完全でない体系では、真であるにもかかわらず証明できない命題が存在することになり、体系として不十分です。
論理学史上の大きな成果として、ゲーデルの完全性定理（1930年）があります。これは一階述語論理が完全であることを示した定理で、意味論的に妥当な任意の式は有限ステップの証明で導けることを保証しました。この定理は数理論理学の基礎を固める画期的な成果でした。
一方、有名なゲーデルの不完全性定理（1931年）は、ペアノ算術のような十分に豊かな算術体系においては、真であるが証明できない命題が必ず存在することを示しています。これは完全性定理とは異なる文脈で語られる結果で、「どんな無矛盾な公理系も完全にはなれない」という深い限界を表しています。
命題論理の完全性は、真理値表を用いた方法（真理値表による決定手続き）でも確認でき、比較的初歩的なレベルで扱われます。
使い方・例文
古典命題論理では、トートロジー（常に真の論理式）はすべて推論規則から証明できます。たとえば「P∨¬P」（排中律）のようなトートロジーは、体系内で必ず証明可能であることが完全性によって保証されます。
この用語をシェア
最終更新: