この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。(このテンプレートの使い方)
出典検索?: "命題論理"
命題論理(めいだいろんり、()英: propositional logic)とは、数理論理学(記号論理学)の基礎的な一部門であり[1]、命題全体を1つの記号に置き換えて単純化し、論理演算を表す記号(論理記号・論理演算子)を用いて、その命題(記号)間の結合パターンを表現・研究・把握することを目的とした分野のこと。ブール論理はブール代数で形式化され2値の意味論を与えられた命題論理とみることができる。
命題を1つの記号で大まかに置き換える命題論理に対して、命題の述語(P)と主語(S)を、関数のF(x)のように別記号で表現し、更に量化子で主語(S)の数・量・範囲もいくらか表現し分けることを可能にした、すなわちより詳細に命題の内部構造を表現できるようにしたものを、述語論理と呼ぶ。 命題論理の命題の取り扱いは普通、命題計算(めいだいけいさん)[注釈 1]、または文計算(ぶんけいさん)[注釈 2]と呼ぶ命題変数を原子式にするような形式的な推論の体系によってなされる。 命題論理において問題になるのは、個々の命題の「意味」よりも命題を「かつ」「ならば」などの論理演算子で関係づけたときにどんな推論ができるか、ということである。命題論理と違い主に個々の命題の意味を扱うのは述語論理などである。 推論の性質をいかなる形に考えるかによって、直観主義論理的な命題論理をはじめ様相論理や相関論理などさまざまな命題論理が考えられるが、通常、単に命題論理と呼んだ場合には、古典命題論理(こてんめいだいろんり)[注釈 3]を指す(古典論理)。従って、本項目では古典命題論理について主に解説することとする。 一般的にいえば、命題計算とは「文法的にきちんとした」統語的な表現(整式)の集合、その表現のいくつかからなる部分集合(公理の集合)、さらに加えて表現の空間上に二項関係を定義する変形規則の集合からなる形式的体系である。 普通、それぞれの表現が数学の表現として具体的に解釈されるとき、表現の変形規則が一定の意味同等性を保つように与えられる。特に表現が論理体系そのものとして解釈されるときには「意味同等性」が論理的同等性のことを指すように変形規則が与えられる。この設定のもとでは変形規則によって与えられた表現から論理的に等価な表現を導くことができる。こういった変形規則による別の表現の導出について、特別な例として表現を単純化すること、与えられた表現が前もって区別された特別な表現(普通、論理学の公理だと解釈される)のうちどれかと等価かどうか決定すること、などが問題にされる。 命題論理における言語は命題変数(命題をはめ込む枠)と文演算子(結合子)からなっている。形式文法によって帰納的にその言語の表現や整式が、原子式や文演算子の一定の組みあわせとして定義される。公理の集合は空集合でも、空でない有限集合でも、可算無限集合でもいいし、あるいは公理図式によって与えられてもいい。加えて、意味論によって真かどうかの値付け(または解釈)が定められる。それによってどの整式が正しい、つまり定理であるかを決めることができるようになる。 以下では標準的な命題論理の大筋を解説する。しかしこの他にも、ほぼ等価ではあるが、言語を構成している演算子や変数が違ったり、あるいは公理や推論規則が違ったりして、ここで説明するものと見かけが異なる方法も存在する。 言語の構成要素は 整式の集合は以下の規則によって帰納的に定義される。 これらを繰り返し適用することでより複雑な整式が作られる。例えば 命題論理は、主として整式同士の論理的関係性を示すために用いられる。このために、利用可能な(整式の)変形規則を使って、「証明」もしくは「展開」と呼ばれる手続きを行う。証明は、番号のついた複数の行からなる記述によって表現される。それぞれの行は、「根拠」もしくは「理由」をそえた、当該の整式を導き出すための単一の整式(論理式)とする。証明を行うために必要な仮定は、「前提」と注記し、証明のはじめの部分に置く。結論は最後の行に示す。すべての行の内容が、それ以前の行の内容に基づき、(整式の)変形規則を正しく適用して得られたものであるとき、証明が完了したとみなされる。(なお、タブローの方法という別の記述方法もある。) 本節では簡単のため、公理を持たない、あるいは同じことだが空な公理集合を持つ自然演繹体系を使うことにする。 ここでの命題計算では八つの推論規則を考える。これらの規則によって真だと仮定された式たちからほかの真な式を導くことができる。最初の六つは単に特定の整式をほかの整式から導けると述べている。一方で、最後の二つの前提では(まだ証明されていない)仮定を一時的に用いている。このことを指して、最初の六つの規則を非仮定的規則、最後の二つは仮定的規則であると言う。
概要
文法
アルファベットの大文字は命題変数を表す。これらは原子式である。
以下の結合子(または論理演算子)を表す記号:「 ¬ {\displaystyle \lnot } 」(否定) 「 ∧ {\displaystyle \land } 」(連言) 「 ∨ {\displaystyle \lor } 」(選言) 「 → {\displaystyle \rightarrow } 」(含意)。(「 P → Q {\displaystyle P\rightarrow Q} 」は「 ¬ P ∨ Q {\displaystyle \lnot P\lor Q} 」と等価だ、などとしていくつかを他のものの短縮形だと見なしてこれより少ない演算子(と記号)でやることもできる。)電子メールなど使用できる文字が限られた環境では、論理的否定を表すのにチルダ「~」を用いたり、論理積を表すのにアンパサンド「&」を用いたりといった記号の代用もよく見られる。
開き括弧 ( と閉じ括弧 )
基本:アルファベットの大文字は整式
帰納節 I: もし ϕ {\displaystyle \phi } が整式なら ¬ ϕ {\displaystyle \lnot \phi } も整式
帰納節 II: ϕ {\displaystyle \phi } と ψ {\displaystyle \psi } が整式なら ( ϕ ∧ ψ ) {\displaystyle (\phi \land \psi )} や ( ϕ ∨ ψ ) {\displaystyle (\phi \lor \psi )} 、 ( ϕ → ψ ) {\displaystyle (\phi \rightarrow \psi )} も整式
閉節:これ以外は整式でない
A {\displaystyle A} は整式
¬ A {\displaystyle \lnot A} は整式
B {\displaystyle B} は整式
( ¬ A ∨ B ) {\displaystyle (\lnot A\lor B)} は整式
計算
公理
推論規則
二重否定の除去
整式 ¬ ¬ ϕ {\displaystyle \lnot \lnot \phi } からは ϕ {\displaystyle \phi } を推論できる。
論理積の導入
整式 ϕ {\displaystyle \phi } と整式 ψ {\displaystyle \psi } からは ( ϕ ∧ ψ ) {\displaystyle (\phi \land \psi )} を推論できる。
論理積の消去
整式 ϕ ∧ ψ {\displaystyle \phi \land \psi } からは ϕ {\displaystyle \phi } と ψ {\displaystyle \psi } を推論できる。
論理和の導入
整式 ϕ {\displaystyle \phi } からは、どんな整式 ψ {\displaystyle \psi } についても ( ϕ ∨ ψ ) {\displaystyle (\phi \lor \psi )} と ( ψ ∨ ϕ ) {\displaystyle (\psi \lor \phi )} を推論できる。
論理和の消去
( ϕ ∨ ψ ) {\displaystyle (\phi \lor \psi )} と ( ϕ → χ ) {\displaystyle (\phi \rightarrow \chi )} 、 ( ψ → χ ) {\displaystyle (\psi \rightarrow \chi )} というかたちの整式からは χ {\displaystyle \chi } を推論できる。
Size:44 KB
出典: フリー百科事典『ウィキペディア(Wikipedia)』
担当:undef