教材一覧
教材検索
PREDICATE LOGIC

述語論理

OVERVIEW

述語論理とは何か?

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

TABLE OF CONTENTS

目次

SECTION 1

論理式

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

述語論理

変数を含む文や式は変数に具体的な値を代入することによりはじめて命題となり、その正しさを判定できるようになります。一般に、変数を含む文や式を命題関数と呼びます。命題関数は述語論理の対象となる最小単位の概念です。

READ MORE »

議論領域

変数とは様々な値を取り得る記号です。変数が取り得る値の範囲を定義域と呼びます。議論の対象となるすべての変数と、それらの変数の定義域をあわせて議論領域と呼びます。

READ MORE »

述語論理における論理式

述語論理において議論の対象となる最小概念は原子論理式です。原子論理式は命題関数を内包する概念です。原子論理式は単独で論理式とみなされます。また、原子論理式に論理演算子や量化記号を作用させて得られる式も論理式とみなされます。また、論理式に論理演算子や量化記号を作用させて得られる式も論理式です。

READ MORE »

閉論理式・開論理式

述語論理において論理式は閉論理式と開論理式とに分類されます。変数の自由な現れを持たない論理式が閉論理式であり、変数の自由な現れを持つ論理式が開論理式です。

READ MORE »
SECTION 2

論理式の解釈

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

真理集合

論理式が与えられたとき、議論領域と関数の形状、そして変数に代入する値をそれぞれ具体的に定めれば、1または0を値としてとる命題が得られます。また、論理式の値が1になるような変数の値からなる集まりを真理集合と呼びます。

Read More »

命題関数の解釈

命題関数が与えられたとき、議論領域(変数の定義域)と関数の形状、そして変数の自由な現れに代入する値をそれぞれ具体的に定めれば、1または0を値としてとる命題が得られます。以上が命題関数の解釈です。

Read More »

述語論理における否定

論理式 A に論理演算子 ¬ を作用させることで得られる ¬A もまた論理式です。¬は否定と呼ばれる論理演算子であり、論理式 ¬A を A の否定と呼びます。

Read More »

述語論理における論理積

論理式 A,B に論理演算子 ∧ を作用させることで得られる A∧B もまた論理式です。∧ は論理積と呼ばれる論理演算子であり、論理式 A∧B を A と B の論理積と呼びます。

Read More »

述語論理における論理和

論理式 A,B に論理演算子 ∨ を作用させることで得られる A∨B もまた論理式です。∨ は論理和と呼ばれる論理演算子であり、論理式 A∨B )を A と B の論理和と呼びます。

Read More »

述語論理における排他的論理和

論理式 A,B に論理演算子 ⊻ を作用させることで得られる A⊻B もまた論理式です。⊻ は排他的論理和と呼ばれる論理演算子であり、論理式 A⊻B を A と B の排他的論理和と呼びます。

Read More »

述語論理における含意

論理式 A,B に論理演算子 → を作用させることで得られる A→B もまた論理式です。→ は含意と呼ばれる論理演算子であり、論理式 A→B を A から B への含意と呼びます。

Read More »

述語論理における同等

論理式 A,B に論理演算子 ↔ を作用させることで得られる A↔B は論理式です。↔ は同等と呼ばれる論理演算子であり、論理式 A↔B を A と B の同等と呼びます。

Read More »

全称命題の解釈

論理式 A と変数 x∈X に対して量化記号 ∀ を作用させることで得られる ∀x∈X A もまた論理式です。∀ は全称記号と呼ばれる量化記号であり、量化記号を作用して得られる ∀x∈X A を全称命題と呼びます。

Read More »

存在命題の解釈

論理式 A と変数 x∈X に対して量化記号 ∃ を作用させることで得られる ∃x∈X A もまた論理式です。∃ は存在記号と呼ばれる量化記号であり、量化記号 ∃ を作用して得られる ∃x∈X A を存在命題と呼びます。

Read More »

述語論理における論理式の解釈

述語論理において論理式の値を特定するためには、変数の定義域を特定し、論理式に含まれるすべての命題関数の形状を特定し、さらに(開論理式の場合には)変数の自由な現れに代入する値を指定する必要があります。以上の 3 つの要素の組を論理式の解釈と呼びます。

Read More »
SECTION 3

恒真式

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

述語論理における恒真式・恒偽式・事実式

述語論理において論理式が恒真式であるとは、任意の解釈においてその論理式の値が真であることを意味します。また、論理式が恒偽式であるとは、任意の解釈においてその論理式の値が偽であることを意味します。恒真式や恒偽式ではない論理式を事実式と呼びます。

Read More »

述語論理における必要条件と十分条件

論理式 A,B に関する含意 A→B が恒真式であるとき、つまり、任意の解釈において A→B から得られる命題が真であるならば、B は A であるための必要条件であると言い、A は B であるための必要条件であると言います。

Read More »

述語論理における必要十分条件

論理式 A,B について A↔B が恒真式であるならば、すなわち、任意の解釈のもとで A↔B の値が 1 であるならば、A と B はお互いに一方が他方であるための必要十分条件であると言います。

Read More »
SECTION 4

同値変形

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

同値変形

与えられた論理式をそれと同値な別の論理式に交換することを同値変形と呼びます。述語論理においても論理的に同値であることを表す二項関係は反射律、対称律、推移律を満たす同値関係になります。

Read More »

交換律

論理式どうしの論理和や論理積の値は、論理式の順序を入れ替えても変わりません。論理積と論理和が満たすこの性質を交換律と呼びます。

Read More »

結合律

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

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 »

量化記号と論理積

全称命題の論理積は論理積に対する全称命題と同値です。一方、存在命題の論理積は論理積に関する存在命題と同値ではありません。

Read More »

量化記号と論理和

存在命題の論理和は論理和に対する存在命題と同値です。一方、全称命題の論理和は論理和に関する全称命題と同値ではありません。

Read More »

量化記号の置換

論理式中の全称記号どうし、存在記号どうしを入れ替えて得られる論理式はもとの論理式と同値です。一方、論理式中の全称記号と存在記号を入れ替えて得られる論理式はもとの論理式と同値であるとは限りません。

Read More »
SECTION 5

推論

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

構成的ジレンマ

論理式 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 »

推論規則

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

Read More »

含意除去

述語論理においても含意除去(モーダスポネンス)は成り立ちます。つまり、論理式A,Bが与えられたとき、A→Bから得られる命題とAから得られる命題がともに真であるような任意の解釈のもとでBから得られる命題は必ず真になります。

Read More »

含意導入

論理式 A,B がともに真であるような任意の解釈において論理式 C が真であることが示された場合には、A が真であるような任意の解釈のもとで B→C が真であることを示したことになります。これは含意導入と呼ばれる推論規則です。

Read More »

連言導入

論理式 A,B がともに真であるような任意の解釈において論理式 A∧Bは必ず真になります。これは連言導入と呼ばれる推論規則です。

Read More »

連言除去

論理式 A∧B が真であるような任意の解釈のもとで A や B は必ず真になります。これは連言除去と呼ばれる推論規則です。

Read More »

選言導入

論理式 A が真であるような任意の解釈や、論理式 B が真であるような任意の解釈のもとでは A∨B は必ず真になります。これは選言導入と呼ばれる推論規則です。

Read More »

選言除去

論理式 A,B,C について、A→C, B→C, A∨B がすべて真であるような任意の解釈のもとで C は必ず真になります。これは選言除去と呼ばれる推論規則です。

Read More »

二重否定導入

論理式 A が真であるような任意の解釈のもとで ¬(¬A) は必ず真になります。これは二重否定導入と呼ばれる推論規則です。

Read More »

二重否定除去

論理式 A について、¬(¬A) が真である場合には A は必ず真になります。これは二重否定除去と呼ばれる推論規則です。

Read More »

否定導入

論理式 A と恒偽式 ⊥ について、A→⊥ が真であるような任意の解釈のもとで ¬A は必ず真になります。これは否定導入と呼ばれる推論規則です。

Read More »

否定除去

論理式 A と恒偽式 ⊥ について、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 »

全称導入(普遍汎化)

カテゴリーの中から任意に選んだものは同種のものを代表しているため、それが満たす性質は他のすべてのものも共通して持っていることを保証する推論規則を全称導入と呼びます。

Read More »

存在導入(存在汎化)

ある性質を満たす特定の対象から、その性質を満たす対象が存在することを導く推論規則を存在導入と呼びます。つまり、具体的に述べられたことは抽象的にも表現可能であるということです。

Read More »
SECTION 6

証明

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

述語論理における証明

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

Read More »

述語論理における条件付き証明

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

Read More »

述語論理における背理法

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

Read More »
RELATED KNOWLEDGE

関連知識

REQUIRED KNOWLEDGE

必須知識

以下の分野の知識があれば本節を円滑に理解できます。

命題論理

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

READ MORE »
ADVANCED KNOWLEDGE

発展知識

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

集合

集合に関するテキストと演習問題です。集合、写像、同値関係、集合の濃度などについて解説します。

READ MORE »

ワイズの理念とサービス

REGISTER

プレミアム会員登録

CONTACT

メールフォーム