命題論理とは何か
命題論理では個々の命題が具体的に何について言及しているかを問題とせず、それらを単に真か偽のどちらかの値をとる変数とみなした上で、考察対象である推論を記号化します。
TABLE OF CONTENTS
目次
FORMULA
論理式
命題論理の基本単位である「論理式」と呼ばれる概念を形式的に定義します。
命題論理における論理式の定義
命題論理において命題変数や命題定数は単独で論理式とみなされます。また、それらに論理演算子を作用させて得られる式も論理式とみなされます。また、論理式に論理演算子を作用させて得られる式も論理式です。
INTERPRETATION OF FORMULA
論理式の解釈
論理式の真偽を判定する方法を解説します。
命題変数の解釈
任意の命題変数Pおよび命題定数T,Fは論理式です。命題変数Pは0または1を値としてとり得る一方、命題定数Tの値は常に1であり、命題定数Fの値は常に0です。
命題論理における否定
否定は入力された論理式に対して、それとは逆の値をとる論理式を出力する論理演算です。
命題論理における論理積
論理積∧は入力された論理式A,Bに対して、それらの値がともに1である場合にのみ1を値としてとる論理式A∧Bを出力する論理演算です。
命題論理における論理和
論理和∨は入力された論理式A,Bに対して、それらの少なくとも1つの値が1である場合にのみ1を値としてとる論理式A∨Bを出力する論理演算です。
命題論理における排他的論理和
排他的論理和は入力された2つの論理式に対して、それらのどちらか一方の値だけが1である場合にのみ1を値としてとる論理式を出力する論理演算です。
命題論理における含意
含意→は入力された論理式A,Bに対して、AとBの値がともに1である場合には1を値としてとり、A の値が0の場合にはBの値によらず常に1を値としてとる論理式A→Bを出力する論理演算です。
命題論理における同等
同等は入力された論理式 A,B に対して、A と B の値が一致する場合にのみ 1 を値としてとる論理式を出力する論理演算です。
命題論理における論理式の解釈
論理式が与えられたとき、その部分論理式をすべて特定できます。部分論理式の中には命題変数が含まれますが、命題変数の値が定まればこれまで定めた規則からすべての部分論理式の値が定まるため、結局、もとの論理式の値が定まります。つまり、論理式の値はそこに含まれる命題変数の値の組み合わせによって決まります。
真理値表の簡略化
命題論理において解釈しようとする論理式が長い場合、部分論理式も膨大であるため、通常の方法にしたがうと真理値表が大きくなってしまいます。そのような場合には、真理値表の1つの列に論理式を構成する文字や論理演算子を1つずつ入れていく形で真理値表を描けばスペースを省略できます。
TAUTOLOGY
恒真式
任意の解釈のもとで真になるような論理式を恒真式と呼びます。
命題論理における恒真式・恒偽式・事実式
論理式を構成する命題変数の値の組み合わせによらず、その論理式の値が常に 1 であるならば、その論理式を恒真式やトートロジーなどと呼びます。また、論理式を構成する命題変数の値の組み合わせによらず、その論理式の値が常に 0 であるならば、その論理式を恒偽式や矛盾式などと呼びます。恒真式や恒偽式ではない論理式を事実式と呼びます。
命題論理における必要条件と十分条件
論理式 A,B に関して含意 A→B が恒真式であるとき、B は A であるための必要条件と言い、A は B であるための十分条件と言います。
命題論理における必要十分条件
論理式 A,B に関して同等 A↔B が恒真式であるならば、A と B は論理的に同値であると言います。またこのとき、A と B はお互いに一方が他方であるための必要十分条件であると言います。
EQUIVALENCE TRANSFORMATION
論理的同値変形
与えられた論理式をそれと論理的に同値な別の論理式に交換することを同値変形と呼びます。
命題論理における同値変形
与えられた論理式をそれと論理的に同値な別の論理式に置き換えることを同値変形と呼びます。
命題論理におけるベキ等律
同じ論理式どうしの論理和と論理積はもとの論理式と同値です。論理積と論理和が満たすこの性質をベキ等律と呼びます。
命題論理における交換律
論理式どうしの論理和や論理積の値は、論理式の順序を入れ替えても変わりません。論理積と論理和が満たすこの性質を交換律と呼びます。
命題論理における結合律
3つの論理式の相対的な順番を変えないまま論理積をとるとき、論理積を作用させる順番とは関係なく最終的に得られる論理式は論理的に同値です。論理和についても同様です。
命題論理における分配律
論理積と論理和の間には分配律と呼ばれる関係が成り立ちます。つまり、論理和との論理積は論理積どうしの論理和と論理的に同値であり、論理積との論理和は論理和どうしの論理積と論理的に同値です。
命題論理における吸収律
論理式 A が与えられたとき、それと任意の論理式 B との論理積 A∧B をとります。その上で両者の論理和 A∨(A∧B) をとると A∧B が吸収されて A と同値な論理式へ戻ります。また、この命題において論理積と論理和の関係を入れ替えたものも成り立ちます。
命題論理におけるド・モルガンの法則
論理積の否定は否定の論理和と論理的に同値であり、論理和の否定は否定の論理積と論理的に同値です。これをド・モルガンの法則と呼びます。ド・モルガンの法則は任意個の論理式の関係としても拡張可能です。
命題論理における矛盾律
任意の論理式から矛盾律と呼ばれる恒偽式を構成できます。これは、論理式は任意の解釈において、真であると同時に偽であるような状況は起こりえないことを主張しています。
命題論理における排中律
任意の論理式から排中律と呼ばれる恒真式を構成できます。これは、論理式はそれぞれの解釈において真か偽のどちらか一方であるという主張です。状況によっては排中律が成り立たないように思われますが、この問題を解決する手法としてファジィ理論や述語論理などがあります。
命題論理における恒等律
論理演算において命題定数は零元や単位元としての性質を備えます。
命題論理における二重否定の法則
論理式 A の否定 ￢A もまた論理式であるため、さらにその否定 ￢(￢A) を考えることができます。これを ￢￢A で表し A の二重否定と呼びます。A とその二重否定 ￢￢A は論理的に同値です。
命題論理における論理演算の言い換え
含意、同等、排他的論理和はいずれも否定、論理積、論理和を用いて間接的に定義可能です。
命題論理における対偶律
論理式 A,B に対して、B→A を含意 A→B の逆と呼び、￢A→￢B を A→B の裏と呼び、￢B→￢A を A→B の対偶と呼びます。含意とその対偶は同値であり、含意の逆と裏は同値です。
命題論理における一様代入の法則
恒真式を構成する論理式を任意の論理式に置き換えた場合、得られる論理式もまた恒真式になることが保証されます。これを一様代入の法則と呼びます。
命題論理における双対原理
論理的に同値な2つの論理式が与えられたとき、それらの双対をとるとそれらもまた論理的に同値となります。これを双対原理と呼びます。
INFERENCE
推論
既知の事柄を前提とした上で、未知の事柄に関して結論を導き出すことを推論と呼びます。
命題論理における推論規則
既知の事柄を前提とした上で、未知の事柄に関して結論を導き出すことを推論と呼びます。また、前提がすべて真である場合に結論が必ず真であるならば、その推論は妥当であると言います。妥当な推論を推論式と呼びます。
命題論理における含意除去（モーダスポネンス）
論理式A,Bが任意に与えられたとき、「AならばBである」と「Aである」という2つの前提から「Bである」という結論を導く推論規則を含意除去やモーダスポネンスなどと呼びます。
命題論理における含意導入
論理式A,B,Cが任意に与えられたとき、前提がA,Bで結論がCであるような推論が妥当である場合、前提がAで結論がB→Cであるような推論もまた妥当になります。これは含意導入と呼ばれる推論規則です。
命題論理における連言除去
論理式 A,B が任意に与えられたとき、「AかつB」という前提から「Aである」という結論（もしくは「B」であるという結論）を導く推論規則を連言除去と呼びます。
命題論理における連言導入
論理式 A,B が任意に与えられたとき、「Aである」と「Bである」という2つの前提から「AかつB」という結論を導く推論規則を連言導入と呼びます。
命題論理における選言除去
論理式 A,B,C を任意に選んだとき、「AならばC」「BならばC」「AまたはB」という3つの前提から「Cである」という結論を導く推論規則を選言除去と呼びます。
命題論理における選言導入
論理式 A,B を任意に選んだとき、「Aである」（もしくは「Bである」）という前提から「AまたはB」という結論を導く推論規則を選言導入と呼びます。
命題論理における二重否定除去
論理式 A に対して、「Aではないことはない」という前提から「Aである」という結論を導く推論規則を二重否定除去と呼びます。
命題論理における二重否定導入
論理式 A が任意に与えられたとき、「Aは真である」という前提から「Aでないことはない」という結論を導く推論規則を二重否定導入と呼びます。
命題論理における否定除去
論理式 A とその否定 ￢A がともに真である場合には恒偽式が導かれます。これは否定除去と呼ばれる推論規則です。
命題論理における否定導入
論理式 A から恒偽式が導かれる場合には ￢A は必ず真になります。これは否定導入と呼ばれる推論規則です。否定導入は背理法と呼ばれる証明方法の根拠になります。
命題論理における後件否定
論理式 A,B について、「AならばB」と「Bではない」という前提から「Aではない」という結論を導く推論規則を後件否定やモーダストレンスなどと呼びます。
命題論理における選言三段論法
論理式 A,B について、「AまたはB」と「Aではない」という前提から「Bである」という結論を導く推論規則を選言三段論法と呼びます。
命題論理における仮言三段論法
論理式 A,B,C について、「AならばB」と「BならばC」という前提から「AならばC」という結論を導く推論規則を仮言三段論法と呼びます。
命題論理における構成的ジレンマ
論理式 A,B,C,D について、「AならばB」「CならばD」「AまたはC」という前提から「BまたはD」という結論を導く推論規則を構成的ジレンマと呼びます。
命題論理における破壊的ジレンマ
論理式 A,B,C,D について、「AならばB」「CならばD」「BでないかDでないかの少なくとも一方」という前提から「AでないかCでないかの少なくとも一方」という結論を導く推論規則を破壊的ジレンマと呼びます。
PROOF
証明
推論の妥当性を示すために、前提と出発点として推論規則を用いて結論を次々に導出し、最終的に結論を導出する手続きを証明と呼びます。
命題論理における証明
推論の妥当性を示すために、前提を出発点として同値変形の法則や推論規則を用いて結論を次々に導出し、最終的に当初の推論式の結論を導出する手法を証明や演繹などと呼びます。
命題論理における条件付き証明
推論を証明する際には、推論の前提とは異なる論理式を便宜的に真と仮定した上で、その論理式と推論の前提に対して推論規則を適用していく手法が時として有効です。仮定を利用する証明方法の代表的なものは条件付き証明です。
命題論理における背理法
推論の結論が論理式 Bとして表されるとき、その否定 ¬B が真であることを仮定した上で、これと推論の前提に対して推論規則を適用して最終的に恒偽式を導くことができれば、否定導入より ¬¬B すなわち B が真になるため、推論式が妥当であることが示されます。このような証明方法を背理法と呼びます。
命題論理における対偶法
推論の結論が偽であることを出発点として、推論の前提の少なくとも 1 つが偽であることを導くことができれば、対偶律よりもとの推論の妥当性が示されます。このような証明方法を対偶法と呼びます。
命題論理における消去法
結論が論理式 B,C を用いて B∨C で表される推論が与えられたとき、推論の前提に加えて ¬B が真であるということを出発点として C が真であることを示すことができれば、もとの推論が妥当であることを示したことになります。これを消去法と呼びます。
場合分け・総当たり法
与えられた推論が複雑である場合には、それをいくつかの単純な推論に分割した上で、得られた個々の推論の妥当性を示す場合分けと呼ばれる証明方法が有用です。
RELATED KNOWLEDGE
関連知識
REQUIRED KNOWLEDGE
前提知識
本節を学ぶ上で必要となる前提知識はありません。
ADVANCED KNOWLEDGE
発展知識
本節で得た知識は以下の分野を学ぶ上での基礎になります。
述語論理
命題論理の基本単位が命題変数であったのに対し、述語論理では命題関数と呼ばれる概念が基本単位となります。それにより扱うことのできる言明の範囲が広がるとともに、量化と呼ばれる操作が可能になります。
