命題論理
命題論理の目的は、論理式を構成する個々の命題変数の真理値の組み合わせによってその論理式の真理値がどのように定まるかを規定するルールを定めた上で、そのルールを出発点としたときに推論に関して何が言えるかを明らかにすることです。
TABLE OF CONTENTS
目次
SECTION 1
論理式
命題論理の基本単位である「論理式」と呼ばれる概念を形式的に定義します。
命題論理における論理式
命題論理において命題変数や命題定数は単独で論理式とみなされます。また、それらに論理演算子を作用させて得られる式も論理式とみなされます。また、論理式に論理演算子を作用させて得られる式も論理式です。
SECTION 2
論理式の解釈
論理式の真偽を判定する方法を解説します。
命題変数の解釈
論理式の真理値を評価する作業を真理値分析と呼びます。任意の命題変数はそれ自体が論理式ですが、命題変数の定義より、これは 0 または 1 を値として取り得ます。命題定数 T, F はそれ自体が論理式ですが、命題定数の定義より、T の値は常に 1 であり、F の値は常に 0 です。
命題論理における論理和
論理和 ∨ は入力された論理式 A, B に対して、それらの少なくとも 1 つの値が 1 である場合にのみ 1 を値としてとる論理式 A∨B を出力する論理演算です。
命題論理における排他的論理和
排他的論理和は入力された 2 つの論理式に対して、それらのどちらか一方の値だけが 1 である場合にのみ 1 を値としてとる論理式を出力する論理演算です。
命題論理における含意
含意 → は入力された論理式 A,B に対して、A と B の値がともに 1 である場合には 1 を値としてとり、A の値が 0 の場合には B の値によらず常に 1 を値としてとる論理式 A→B を出力する論理演算です。
命題論理における論理式の解釈
論理式が与えられたとき、その部分論理式をすべて特定できます。部分論理式の中には命題変数が含まれますが、命題変数の値が定まればこれまで定めた規則からすべての部分論理式の値が定まるため、結局、もとの論理式の値が定まります。つまり、論理式の値はそこに含まれる命題変数の値の組み合わせによって決まります。
SECTION 3
恒真式
任意の解釈のもとで真になるような論理式を恒真式と呼びます。
恒真式・恒偽式・事実式
論理式を構成する命題変数の値の組み合わせによらず、その論理式の値が常に 1 であるならば、その論理式を恒真式やトートロジーなどと呼びます。また、論理式を構成する命題変数の値の組み合わせによらず、その論理式の値が常に 0 であるならば、その論理式を恒偽式や矛盾式などと呼びます。恒真式や恒偽式ではない論理式を事実式と呼びます。
命題論理における必要十分条件必要条件と十分条件
論理式 A,B に関して含意 A→B が恒真式であるとき、B は A であるための必要条件と言い、A は B であるための十分条件と言います。
命題論理における必要十分条件
論理式 A,B に関して同等 A↔B が恒真式であるならば、A と B は論理的に同値であると言います。またこのとき、A と B はお互いに一方が他方であるための必要十分条件であると言います。
SECTION 4
同値変形
与えられた論理式をそれと論理的に同値な別の論理式に交換することを同値変形と呼びます。
結合律
論理式 A,B,C が与えられたとき、隣り合う A,B に対して論理積 ∧ を作用させれば A∧B を得ます。これは論理式ですから、これと残された C に対して再び論理積 ∧ を作用させれば (A∧B)∧C という論理式を得ます。一方、最初に B,C に対して論理積 ∧ を作用させれば最終的に A∧(B∧C) という論理式を得ます。この 2 つの論理式の値が一致するというのが結合律の主張です。
分配律
論理積と論理和の間には分配律と呼ばれる関係が成り立ちます。つまり、論理和との論理積は論理積どうしの論理和と論理的に同値であり、論理積との論理和は論理和どうしの論理積と論理的に同値です。
吸収律
論理式 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 の対偶と呼びます。含意とその対偶は同値であり、含意の逆と裏は同値です。
SECTION 5
推論
既知の事柄を前提とした上で、未知の事柄に関して結論を導き出すことを推論と呼びます。
推論規則
既知の事柄を前提とした上で、未知の事柄に関して結論を導き出すことを推論と呼びます。また、前提がすべて真である場合に結論が必ず真であるならば、その推論は妥当であると言います。妥当な推論を推論式と呼びます。
含意除去
論理式A,Bが任意に与えられたとき、「AならばBである」と「Aである」という2つの前提から「Bである」という結論を導く推論規則を含意除去やモーダスポネンスなどと呼びます。
含意導入
論理式 A,B,C が任意に与えられたとき、前提が A と B で結論が C であるような推論が妥当である場合、前提が A で結論が B→C であるような推論もまた妥当になります。これは含意導入と呼ばれる推論規則です。
破壊的ジレンマ
論理式 A,B,C,D について、「AならばB」「CならばD」「BでないかDでないかの少なくとも一方」という前提から「AでないかCでないかの少なくとも一方」という結論を導く推論規則を破壊的ジレンマと呼びます。
SECTION 6
証明
推論の妥当性を示すために、前提と出発点として推論規則を用いて結論を次々に導出し、最終的に結論を導出する手続きを証明と呼びます。
条件付き証明
推論を証明する際には、推論の前提とは異なる論理式を便宜的に真と仮定した上で、その論理式と推論の前提に対して推論規則を適用していく手法が時として有効です。仮定を利用する証明方法の代表的なものは条件付き証明です。
背理法
推論の結論が論理式 Bとして表されるとき、その否定 ¬B が真であることを仮定した上で、これと推論の前提に対して推論規則を適用して最終的に恒偽式を導くことができれば、否定導入より ¬¬B すなわち B が真になるため、推論式が妥当であることが示されます。このような証明方法を背理法と呼びます。
対偶法（間接証明）
推論の結論が偽であることを出発点として、推論の前提の少なくとも 1 つが偽であることを導くことができれば、対偶律よりもとの推論の妥当性が示されます。このような証明方法を対偶法と呼びます。
消去法
結論が論理式 B,C を用いて B∨C で表される推論が与えられたとき、推論の前提に加えて ¬B が真であるということを出発点として C が真であることを示すことができれば、もとの推論が妥当であることを示したことになります。これを消去法と呼びます。
場合分け・総当たり法
複数の論理式の論理和を前提とする推論が与えられたとき、前提を構成するそれぞれの論理式から結論をそれぞれ示すことができれば、もとの推論が妥当であることを示したことになります。これは場合分けと呼ばれる証明方法です。また、場合分けを逆手にとった証明方法が総当たり法です。
RELATED KNOWLEDGE
関連知識
REQUIRED KNOWLEDGE
必須知識
本節を読む上で必須となる知識はありません。
ADVANCED KNOWLEDGE
発展知識
本節で得た知識は以下の分野を学ぶ上での土台になります。
述語論理
命題論理の基本単位が命題変数であったのに対し、述語論理では命題関数と呼ばれる概念が基本単位となります。それにより扱うことのできる言明の範囲が広がるとともに、量化と呼ばれる操作が可能になります。
