教材一覧
PROPOSITIONAL LOGIC

命題論理

OVERVIEW

命題論理とは何か?

命題論理の基本単位は「真または偽のどちらか一方であるような主張」であり、これを命題変数と呼ばれる概念として定式化します。その上で、より複雑な主張を生成する操作を命題変数どうしを組み合わせる操作として定式化し、そのような操作を行う際のルールを定めます。また、以上のルールを踏まえたときに、どのような推論規則が導かれるかを明らかにします。

TABLE OF CONTENTS

目次

SECTION 1

論理式

命題論理の基本単位である「論理式」と呼ばれる概念を形式的に定義します。

命題論理

命題論理の目的は、論理式を構成する個々の命題変数の真理値の組み合わせによってその論理式の真理値がどのように定まるかを規定するルールを定めた上で、そのルールを出発点としたときに推論に関して何が言えるかを明らかにすることです。

READ MORE »

命題論理における論理式

命題論理において命題変数や命題定数は単独で論理式とみなされます。また、それらに論理演算子を作用させて得られる式も論理式とみなされます。また、論理式に論理演算子を作用させて得られる式も論理式です。

READ MORE »
SECTION 2

論理式の解釈

論理式の真偽を判定する方法を解説します。

命題変数の解釈

論理式の真理値を評価する作業を真理値分析と呼びます。任意の命題変数はそれ自体が論理式ですが、命題変数の定義より、これは 0 または 1 を値として取り得ます。命題定数 T, F はそれ自体が論理式ですが、命題定数の定義より、T の値は常に 1 であり、F の値は常に 0 です。

Read More »

命題論理における論理和

論理和 ∨ は入力された論理式 A, B に対して、それらの少なくとも 1 つの値が 1 である場合にのみ 1 を値としてとる論理式 A∨B を出力する論理演算です。

Read More »

命題論理における含意

含意 → は入力された論理式 A,B に対して、A と B の値がともに 1 である場合には 1 を値としてとり、A の値が 0 の場合には B の値によらず常に 1 を値としてとる論理式 A→B を出力する論理演算です。

Read More »

命題論理における論理式の解釈

論理式が与えられたとき、その部分論理式をすべて特定できます。部分論理式の中には命題変数が含まれますが、命題変数の値が定まればこれまで定めた規則からすべての部分論理式の値が定まるため、結局、もとの論理式の値が定まります。つまり、論理式の値はそこに含まれる命題変数の値の組み合わせによって決まります。

Read More »
SECTION 3

恒真式

任意の解釈のもとで真になるような論理式を恒真式と呼びます。

恒真式・恒偽式・事実式

論理式を構成する命題変数の値の組み合わせによらず、その論理式の値が常に 1 であるならば、その論理式を恒真式やトートロジーなどと呼びます。また、論理式を構成する命題変数の値の組み合わせによらず、その論理式の値が常に 0 であるならば、その論理式を恒偽式や矛盾式などと呼びます。恒真式や恒偽式ではない論理式を事実式と呼びます。

Read More »

命題論理における必要十分条件

論理式 A,B に関して同等 A↔B が恒真式であるならば、A と B は論理的に同値であると言います。またこのとき、A と B はお互いに一方が他方であるための必要十分条件であると言います。

Read More »
SECTION 4

同値変形

与えられた論理式をそれと論理的に同値な別の論理式に交換することを同値変形と呼びます。

結合律

論理式 A,B,C が与えられたとき、隣り合う A,B に対して論理積 ∧ を作用させれば A∧B を得ます。これは論理式ですから、これと残された C に対して再び論理積 ∧ を作用させれば (A∧B)∧C という論理式を得ます。一方、最初に B,C に対して論理積 ∧ を作用させれば最終的に A∧(B∧C) という論理式を得ます。この 2 つの論理式の値が一致するというのが結合律の主張です。

Read More »

分配律

論理積と論理和の間には分配律と呼ばれる関係が成り立ちます。つまり、論理和との論理積は論理積どうしの論理和と論理的に同値であり、論理積との論理和は論理和どうしの論理積と論理的に同値です。

Read More »

吸収律

論理式 A が与えられたとき、それと任意の論理式 B との論理積 A∧B をとります。その上で両者の論理和 A∨(A∧B) をとると A∧B が吸収されて A と同値な論理式へ戻ります。また、この命題において論理積と論理和の関係を入れ替えたものも成り立ちます。

Read More »

ド・モルガンの法則

論理積の否定は否定の論理和と論理的に同値であり、論理和の否定は否定の論理積と論理的に同値です。これをド・モルガンの法則と呼びます。ド・モルガンの法則は任意個の論理式の関係としても拡張可能です。

Read More »

矛盾律

任意の論理式から矛盾律と呼ばれる恒偽式を構成できます。これは、論理式は任意の解釈において、真であると同時に偽であるような状況は起こりえないことを主張しています。

Read More »

排中律

任意の論理式から排中律と呼ばれる恒真式を構成できます。これは、論理式はそれぞれの解釈において真か偽のどちらか一方であるという主張です。状況によっては排中律が成り立たないように思われますが、この問題を解決する手法としてファジィ理論や述語論理などがあります。

Read More »

二重否定の法則

論理式 A の否定 ¬A もまた論理式ですから、さらにその否定 ¬(¬A) を考えることができます。これを ¬¬A で表し A の二重否定と呼びます。A とその二重否定 ¬¬A は論理的に同値です。

Read More »

対偶律

論理式 A,B に対して、B→A を含意 A→B の逆と呼び、¬A→¬B を A→B の裏と呼び、¬B→¬A を A→B の対偶と呼びます。含意とその対偶は同値であり、含意の逆と裏は同値です。

Read More »

双対原理

論理的に同値な 2 つの論理式が与えられたとき、それらの双対をとるとそれらもまた論理的に同値となります。これを双対原理と呼びます。

Read More »
SECTION 5

推論

既知の事柄を前提とした上で、未知の事柄に関して結論を導き出すことを推論と呼びます。

推論規則

既知の事柄を前提とした上で、未知の事柄に関して結論を導き出すことを推論と呼びます。また、前提がすべて真である場合に結論が必ず真であるならば、その推論は妥当であると言います。妥当な推論を推論式と呼びます。

Read More »

含意除去

論理式A,Bが任意に与えられたとき、「AならばBである」と「Aである」という2つの前提から「Bである」という結論を導く推論規則を含意除去やモーダスポネンスなどと呼びます。

Read More »

含意導入

論理式 A,B,C が任意に与えられたとき、前提が A と B で結論が C であるような推論が妥当である場合、前提が A で結論が B→C であるような推論もまた妥当になります。これは含意導入と呼ばれる推論規則です。

Read More »

連言除去

論理式 A,B が任意に与えられたとき、「AかつB」という前提から「Aである」という結論(もしくは「B」であるという結論)を導く推論規則を連言除去と呼びます。

Read More »

連言導入

論理式 A,B が任意に与えられたとき、「Aである」と「Bである」という2つの前提から「AかつB」という結論を導く推論規則を連言導入と呼びます。

Read More »

選言除去

論理式 A,B,C を任意に選んだとき、「AならばC」「BならばC」「AまたはB」という3つの前提から「Cである」という結論を導く推論規則を選言除去と呼びます。

Read More »

選言導入

論理式 A,B を任意に選んだとき、「Aである」(もしくは「Bである」)という前提から「AまたはB」という結論を導く推論規則を選言導入と呼びます。

Read More »

二重否定除去

論理式 A に対して、「Aではないことはない」という前提から「Aである」という結論を導く推論規則を二重否定除去と呼びます。

Read More »

二重否定導入

論理式 A が任意に与えられたとき、「Aは真である」という前提から「Aでないことはない」という結論を導く推論規則を二重否定導入と呼びます。

Read More »

否定除去

論理式 A とその否定 ¬A がともに真である場合には恒偽式が導かれます。これは否定除去と呼ばれる推論規則です。

Read More »

否定導入

論理式 A から恒偽式が導かれる場合には ¬A は必ず真になります。これは否定導入と呼ばれる推論規則です。否定導入は背理法と呼ばれる証明方法の根拠になります。

Read More »

後件否定

論理式 A,B について、「AならばB」と「Bではない」という前提から「Aではない」という結論を導く推論規則を後件否定やモーダストレンスなどと呼びます。

Read More »

選言三段論法

論理式 A,B について、「AまたはB」と「Aではない」という前提から「Bである」という結論を導く推論規則を選言三段論法と呼びます。

Read More »

仮言三段論法

論理式 A,B,C について、「AならばB」と「BならばC」という前提から「AならばC」という結論を導く推論規則を仮言三段論法と呼びます。

Read More »

構成的ジレンマ

論理式 A,B,C,D について、「AならばB」「CならばD」「AまたはC」という前提から「BまたはD」という結論を導く推論規則を構成的ジレンマと呼びます。

Read More »

破壊的ジレンマ

論理式 A,B,C,D について、「AならばB」「CならばD」「BでないかDでないかの少なくとも一方」という前提から「AでないかCでないかの少なくとも一方」という結論を導く推論規則を破壊的ジレンマと呼びます。

Read More »
SECTION 6

証明

推論の妥当性を示すために、前提と出発点として推論規則を用いて結論を次々に導出し、最終的に結論を導出する手続きを証明と呼びます。

証明

推論の妥当性を示すために、前提を出発点として推論規則を用いて結論を次々に導出し、最終的に当初の推論式の結論を導出する手法を証明や演繹などと呼びます。

Read More »

条件付き証明

推論を証明する際には、推論の前提とは異なる論理式を便宜的に真と仮定した上で、その論理式と推論の前提に対して推論規則を適用していく手法が時として有効です。仮定を利用する証明方法の代表的なものは条件付き証明です。

Read More »

背理法

推論の結論が論理式 Bとして表されるとき、その否定 ¬B が真であることを仮定した上で、これと推論の前提に対して推論規則を適用して最終的に恒偽式を導くことができれば、否定導入より ¬¬B すなわち B が真になるため、推論式が妥当であることが示されます。このような証明方法を背理法と呼びます。

Read More »

対偶法(間接証明)

推論の結論が偽であることを出発点として、推論の前提の少なくとも 1 つが偽であることを導くことができれば、対偶律よりもとの推論の妥当性が示されます。このような証明方法を対偶法と呼びます。

Read More »

消去法

結論が論理式 B,C を用いて B∨C で表される推論が与えられたとき、推論の前提に加えて ¬B が真であるということを出発点として C が真であることを示すことができれば、もとの推論が妥当であることを示したことになります。これを消去法と呼びます。

Read More »

場合分け・総当たり法

複数の論理式の論理和を前提とする推論が与えられたとき、前提を構成するそれぞれの論理式から結論をそれぞれ示すことができれば、もとの推論が妥当であることを示したことになります。これは場合分けと呼ばれる証明方法です。また、場合分けを逆手にとった証明方法が総当たり法です。

Read More »
RELATED KNOWLEDGE

関連知識

REQUIRED KNOWLEDGE

必須知識

本節を読む上で必須となる知識はありません。

ADVANCED KNOWLEDGE

発展知識

本節で得た知識は以下の分野を学ぶ上での土台になります。

述語論理

命題論理の基本単位が命題変数であったのに対し、述語論理では命題関数と呼ばれる概念が基本単位となります。それにより扱うことのできる言明の範囲が広がるとともに、量化と呼ばれる操作が可能になります。

READ MORE »

ワイズの理念とサービス

REGISTER

プレミアム会員登録

CONTACT

メールフォーム