命題論理

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

命題論理(めいだいろんり、propositional logic)とは命題と呼ぶ対象を扱う論理の体系である。現代では、数理論理学により形式化されている。ブール論理ブール代数で形式化され2値の意味論を与えられた命題論理とみることができる。

概要[編集]

命題論理の命題の取り扱いは普通、命題計算(めいだいけいさん、propositional calculus)、または文計算(ぶんけいさん、sentential calculus)と呼ぶ命題変数原子式にするような形式的な推論の体系によってなされる。

命題論理において問題になるのは、個々の命題の「意味」よりも命題を「かつ」「ならば」などの論理演算子で関係づけたときにどんな推論ができるか、ということである。命題論理と違い主に個々の命題の意味を扱うのは述語論理などである。

推論の性質をいかなる形に考えるかによって、直観主義論理的な命題論理をはじめ様相論理相関論理などさまざまな命題論理が考えられるが、通常、単に命題論理と呼んだ場合には、古典命題論理(こてんめいだいろんり、classical propositional logic)を指す(古典論理)。従って、本項目では古典命題論理について主に解説することとする。

一般的にいえば、命題計算とは「文法的にきちんとした」統語的な表現(整式)の集合、その表現のいくつかからなる部分集合公理の集合)、さらに加えて表現の空間上に二項関係を定義する変形規則の集合からなる形式的体系である。

普通、それぞれの表現が数学の表現として具体的に解釈されるとき、表現の変形規則が一定の意味同等性を保つように与えられる。特に表現が論理体系そのものとして解釈されるときには「意味同等性」が論理的同等性のことを指すように変形規則が与えられる。この設定のもとでは変形規則によって与えられた表現から論理的に等価な表現を導くことができる。こういった変形規則による別の表現の導出について、特別な例として表現を単純化すること、与えられた表現が前もって区別された特別な表現(普通、論理学の公理だと解釈される)のうちどれかと等価かどうか決定すること、などが問題にされる。

命題論理における言語は命題変数(命題をはめ込む枠)と文演算子(結合子)からなっている。形式文法によって帰納的にその言語の表現や整式が、原子式や文演算子の一定の組みあわせとして定義される。公理の集合は空集合でも、空でない有限集合でも、可算無限集合でもいいし、あるいは公理図式によって与えられてもいい。加えて、意味論によって真かどうかの値付け(または解釈)が定められる。それによってどの整式が正しい、つまり定理であるかを決めることができるようになる。

以下では標準的な命題論理の大筋を解説する。しかしこの他にも、ほぼ等価ではあるが、言語を構成している演算子や変数が違ったり、あるいは公理や推論規則が違ったりして、ここで説明するものと見かけが異なる方法も存在する。

文法[編集]

言語の構成要素は

  1. アルファベット大文字は命題変数を表す。これらは原子式である。
  2. 以下の結合子(または論理演算子)を表す記号:¬, ∧, ∨, →。(たとえばP → Qは¬P ∨ Qと等価だ、などとしていくつかを他のものの短縮形だと見なしてもっと少ない演算子(と記号)でやることもできる。)電子メールなど使用できる文字が限られた環境では、論理的否定を表すのにチルダ~を用いたり、論理積を表すのにアンパサンド&を用いたりといった記号の代用もよく見られる。
  3. 開き括弧 ( と閉じ括弧 )

整式の集合は以下の規則によって帰納的に定義される。

  1. 基本:アルファベットの大文字は整式
  2. 帰納節 I: もしφが整式なら¬φも整式
  3. 帰納節 II: φとψが整式なら(φ ∧ ψ)や(φ ∨ ψ)、(φ → ψ)も整式
  4. 閉節:これ以外は整式でない

これらを繰り返し適用することでより複雑な整式が作られる。例えば

  1. Aは整式
  2. ¬Aは整式
  3. Bは整式
  4. (¬A ∨ B)は整式

計算[編集]

簡単のため、公理を持たない、あるいは同じことだが空な公理集合を持つ自然演繹体系を使うことにする。

この計算による導出は、番号づけられた行のリスト(各行に一つの整式と正当化が書かれた)の形で展開・表現される。前提は正当化「p」とともに一番上におかれる。結論は最後の行に書かれる。導出は、すべての行が前のものから規則を正しく適用して得られているとき完全なものと見なされる。(対照的なアプローチについては証明木を参照のこと)

公理[編集]

公理集合は空集合を採用する。

推論規則[編集]

ここでの命題計算では八つの推論規則を考える。これらの規則によって真だと仮定された式たちからほかの真な式を導くことができる。最初の六つは単に特定の整式をほかの整式から導けると述べている。しかしながら、最後の二つの前提では、特定の式を導けるか見てみるために(まだ証明されていない)仮定もが推論された式の集合の一部として一時的に用いられるという意味で、仮定的な理由づけを用いている。最初の六つの規則はこれをやっていないので非仮定的規則と説明され、最後の二つは仮定的規則といわれる。

二重否定の除去
整式¬¬φからはφを推論できる。
論理積の導入
整式φと整式ψからは(φ ∧ ψ)を推論できる。
論理積の消去
整式(φ ∧ ψ)からはφとψを推論できる。
論理和の導入
整式φからは、どんな整式ψについても(φ ∨ ψ)と(ψ ∨ φ)を推論できる。
論理和の消去
(φ ∨ ψ)と(φ → χ)、(ψ → χ)というかたちの整式からはχを推論できる。
モーダスポネンス (前件肯定式、肯定式とも。la: modus ponens)
φと(φ → ψ)という形の整式からはψを推論できる。
条件付き証明
φを仮定して整式ψが導かれたら(φ → ψ)を推論できる。
背理法
φを仮定してψと¬ψが導かれたら¬φを推論できる。

規則の健全性と完全性[編集]

個々に挙げられた規則の重要な性質は健全性と完全性である。直感的には、これらの規則は正しくしかも他に必要な規則はないということである。これは以下のようにして形式化される。

真理値の割り当てを、命題変数に対してまたはの値を対応させる関数だと考えることにする。形式的でない言い方をすれば、真理値の割り当てとは、特定の叙述が真になり他は偽になるような「おきうる事態」(またはありうる世界)についての説明だと理解できる。その「事態」においてそれぞれの式が正しくなるのはどんなときかを定めることで式の意味論が定式化できる。

真理値の割り当てAがどんなときに特定の整式を充足するか、ということを以下の規則によって定める。

  • A(P) = 真であるとき、およびそのときに限ってAは命題変数Pを充足する
  • Aがφを充足しないとき、およびそのときに限ってAは¬φを充足する
  • Aがφとψを充足するとき、およびそのときに限ってAは (φ ∧ ψ) を充足する
  • Aがφかψの少なくともどちらかを充足するとき、およびそのときに限ってAは (φ ∨ ψ) を充足する
  • Aがφを充足するのにψを充足しないということがないとき、およびそのときに限ってAは (φ → ψ) を充足する

この定義によって式φが特定の式の集合 S から従うとはどういうことなのかを定式化できる。格式張らずにいえばこれは、Sの式が成り立っているようなすべての世界においてφが成立していることだ、といえる。これは次のように形式化できる:Sの式をすべて充足するような真理値の割り当てが必ずφを充足するとき、整式φはSから意味論的に帰結する(または導かれる)、という。

最後に、統語的な帰結という関係を、φが上に挙げた推論規則に従って有限の段階でSの式から導出されるとき、およびそのときに限ってφはSから統語的に帰結する、として定める。これによって推論規則の集合が健全だとか完全だとかいうのはどういうことなのかを定式化できる。

健全性
もしφが整式の集合Sから統語的に帰結するならφはSから意味論的に帰結する
完全性
もしφがSから意味論的に帰結するならφはSから統語的に帰結する

上記の自然命題論理の規則の集合についてはこれらが成り立っている。

別の論理計算の定式化[編集]

文法と論理演算子のほとんどを公理によって定め、推論規則を一つだけしか持たないような、他の方式の命題計算を定義することもできる。 以下、φ、χ、ψで整式を表すことにする。個々の整式自体はギリシャ文字を含まず、ローマ字と結合子と括弧のみからなっている。

公理系1[編集]

スティーブン・コール・クリーネによって導入された体系[1]では11の公理と一つの推論規則が用いられる。

  • THEN-1: φ → (χ → φ) (含意の導入、introduction of implication と一般的に呼ぶ)
  • THEN-2: (φ → (χ → ψ)) → ((φ → χ) → (φ → ψ)) (フレーゲの三段論法、Fregean syllogism と一般的に呼ぶ)
  • AND-1: φ ∧ χ → φ (単純化、simplificationと呼ぶ)
  • AND-2: φ ∧ χ → χ
  • AND-3: φ → (χ → (φ ∧ χ))
  • OR-1: φ → φ ∨ χ
  • OR-2: χ → φ ∨ χ
  • OR-3: (φ → ψ) → ((χ → ψ) → (φ ∨ χ → ψ))
  • NOT-1: (φ → χ) → ((φ → ¬χ) → ¬ φ)
  • NOT-2: φ → (¬φ → χ)
  • NOT-3: φ ∨ ¬φ

公理THEN-2は「含意の推移性」だと考えることができる。 公理AND-1と公理AND-2は「論理積の消去」に対応している。公理AND-1と公理AND-2の平行性は論理積の可換性を反映している。公理AND-3は「論理積の導入」に対応している。公理OR-1と公理OR-2は「論理和の導入」に対応している。公理OR-1と公理OR-2の平行性は論理和の可換性を反映している。公理NOT-1は「背理法」に対応している。公理NOT-2は「principle of explosion 矛盾からは何でも導出できる」ということを述べている。公理NOT-2になんらかの制限を加えて論理体系を構成する方法は矛盾許容論理と呼ぶ。公理NOT-3は「排中律」とよばれ命題式の意味論的値付けの可能性を反映している:式の真理値は真か偽のどちらかである。少なくとも古典的論理学においては第三の真理値という可能性は考慮されない。公理NOT-3を認めないで論理体系を構成する方法は直観主義論理と呼ぶ。

推論規則はモーダスポネンス、つまり

φと(φ → ψ)という形の整式からはψを推論できる

のみを規約する。上記の公理系とこの推論規則から#推論規則節で述べられたのと同じ演繹が可能になる。

公理系2[編集]

ダフィット・ヒルベルトによって定式化された公理系を以下に示す:

  • φ → (χ → φ)
  • (φ → (χ → ψ)) → ((φ → χ) → (φ → ψ))
  • (¬ψ → ¬φ)→(φ → ψ)

を採用し、推論規則はモーダス・ポネンス、すなわち「φと(φ → ψ)からψを推論できる」のみを規約する。

この公理系においては、「φ ∨ψ」、「φ ∧ψ」はそれぞれは「¬φ →ψ」、「¬(φ →¬ψ)」の略記とみなす。

公理系3[編集]

公理系2の、はじめの2つの公理を、以下の4つに置き換えたもの。

  • φ → (χ → φ)
  • (χ → (χ → φ)) → (χ → φ)
  • (φ → (χ → ψ)) → (χ → (φ → ψ))
  • (χ → ψ) → ((φ → χ) → (φ → ψ))

上の3つの公理は、シークエント計算における構造規則の弱化(Weakening)、縮約(Contraction)、転置(Permutation)に対応する。

他の命題計算[編集]

命題計算は、現在用いられている論理計算の中でも最も単純なものだと言える(アリストテレス三段論法(sylogism)は、後述の述語論理に吸収されるため、現代論理学では取り扱われることは少ないが、命題計算とくらべて、言語表現を忠実に分析するという意味では、より素朴な考え方だとも言える。また、推論形式が限定されている点で、形式的にも一見単純である。ただし、現代論理の立場から省みると、そのような推論形式の制限は、かえって理論を複雑にする。また、文構造を主語と述語に分け、量化の概念を導入するなど、より精密だと言える。)。いくつかのやり方で命題計算を拡張することができる。

より複雑な論理計算を作り上げるうえで最も直接的な方法は、用いられる式についてより細かいことが言えるような規則を導入することである。命題論理の「原始的叙述」を変数述語量化子に分解することを考えると一階論理、または一階述語論理と呼び、命題論理の規則をすべて保ちながらさらに新しい規則を加えたものを得る。(例えば「すべてのほ乳類である」から「たまが猫なら、たまはほ乳類である」を推論できる、など。)

一階論理の道具立てを使うと、公理あるいは推論規則によって様々な理論を定式化し、論理計算として取り扱えるようになる。最も有名な例は算術だが、ほかにも集合論メレオロジーが挙げられる。

様相論理は命題計算ではとらえきれないような様々な推論を可能にしている。様相論理では、例えば「ρは必然的である」からρを推論でき、ρからは「ρは可能である」が推論できる。

多値論理では文の真理値として真と偽以外のものも許容される。(例えば「真でもあり偽でもある」とか「真でも偽でもない」がよく追加される。またファジィ論理では真と偽の間の無限にこまかい「真実である度合い」が導入される。)これらの論理学ではしばしば命題計算とは異なった計算手法が必要になる。

関連項目[編集]

脚注[編集]

  1. ^ S.C. Kleene, Introduction to Metamathematics, North Holland (1967).