WIIS

PREDICATE LOGIC

述語論理

OVERVIEW

述語論理とは何か

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

目次

FORMULA

論理式

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

述語論理とは何か

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

述語論理における議論領域

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

述語論理における論理式

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

閉論理式・開論理式

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

INTERPRETATION OF FORMULA

論理式の解釈

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

真理集合

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

命題関数の解釈

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

述語論理における否定

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

述語論理における論理積

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

述語論理における論理和

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

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

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

述語論理における含意

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

述語論理における同等

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

全称命題の解釈

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

存在命題の解釈

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

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

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

TAUTOLOGY

恒真式

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

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

述語論理において論理式が恒真式であるとは、任意の解釈のもとで、そこから得られる命題が真であることを意味します。また、論理式が恒偽式であるとは、任意の解釈のもとで、そこから得られる命題が偽であることを意味します。

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

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

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

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

EQUIVALENCE TRANSFORMATION

同値変形

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

述語論理における同値変形

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

述語論理におけるベキ等律

述語論理においてもベキ等律は成立します。つまり、同じ論理式どうしの論理和と論理積はもとの論理式と論理的に同値です。

述語論理における交換律

述語論理においても交換律が成り立ちます。つまり、論理式どうしの論理和や論理積の値は、論理式の順序を入れ替えても変わりません。

述語論理における結合律

述語論理においても結合律が成り立ちます。つまり、3つの論理式の相対的な順番を変えないまま論理積をとるとき、論理積を作用させる順番とは関係なく最終的に得られる論理式は論理的に同値です。論理和についても同様です。

述語論理における分配律

述語論理においても分配律が成り立ちます。つまり、論理和との論理積は論理積どうしの論理和と同値であり、論理積との論理和は論理和どうしの論理積と同値です。

述語論理における吸収律

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

述語論理におけるド・モルガンの法則

述語論理においてもド・モルガンの法則は成立します。つまり、論理積の否定は否定の論理和と論理的に同値であり、論理和の否定は否定の論理積と論理的に同値です。

述語論理における矛盾律

述語論理においても矛盾律は成立します。つまり、論理式とその論理式の否定の論理積をとると恒偽式になります。論理式から生成される命題が真であると同時に偽であるような状況は起こり得ないということです。

述語論理における排中律

述語論理においても排中律は成立します。つまり、論理式とその論理式の否定の論理和をとると恒真式になります。言い換えると、論理式から生成される命題は真か偽のどちらか一方であり、真かつ偽であるような状態は起こり得ません。

述語論理における恒等律

恒真式の否定と恒偽式は論理的に同値であり、恒偽式の否定と恒真式は論理的に同値です。また、任意の論理式と恒真式の和は恒真式となり、任意の論理式と恒偽式の論理積は恒偽式になります。さらに、任意の論理式と恒真式の論理積をとっても論理式として変わらず、任意の論理式と恒偽式の論理和をとっても論理式として変わりません。

述語論理における対偶律

述語論理においても対偶律が成り立ちます。つまり、含意とその対偶は論理的に同値であり、論理の逆と裏は論理的に同値です。

INFERENCE

推論

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

述語論理における推論規則

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

全称除去(普遍例化)

すべてのものに当てはまることは、そのカテゴリーに属する特定のものにも当てはまることを保証する推論規則を全称除去と呼びます。

全称導入(普遍汎化)

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

存在除去(存在例化)

ある性質を満たす対象が存在する場合には、その対象に新たな名前をつけてもよいことを保証する推論規則を存在除去と呼びます。

存在導入(存在汎化)

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

述語論理における含意除去(モーダスポネンス)

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

述語論理における含意導入

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

述語論理における選言除去

述語論理においても選言除去が成立します。つまり、論理式A,B,Cについて、A→CとB→CとA∨BからCを導くことができます。

述語論理における選言導入

述語論理においても選言導入が成り立ちます。つまり、論理式A,Bについて、Aから論理和A∨Bを導いたり、Bから論理和A∨Bを導くことができます。

述語論理における否定除去

論理式 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から得られる命題が真になることが保証されます。これは仮言三段論法と呼ばれる推論規則です。

PROOF

証明

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

述語論理における証明

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

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

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

述語論理における背理法

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

述語論理における対偶法

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

述語論理における消去法

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

構成的証明

変数xの自由な現れを持つ論理式A(x)に関する存在命題が真であることを示すために、命題A(x)が真になるような値xを具体的に提示する証明方法を構成的証明と呼びます。

反例による反証

変数xの自由な現れを持つ論理式A(x)に関する全称命題が偽であることを示すために、命題A(x)が偽になるような値xを具体的に提示する証明方法を反例による反証と呼びます。

RELATED KNOWLEDGE

関連知識

REQUIRED KNOWLEDGE

前提知識

本節を学ぶ上で以下の知識が役に立ちます。

命題論理

命題論理の基本単位は「真または偽のどちらか一方であるような主張」であり、これを命題変数と呼びます。その上で、より複雑な主張を生成する操作を命題変数どうしを組み合わせる操作として定式化します。

ADVANCED KNOWLEDGE

発展知識

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

集合

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

ワイズの理念とサービス

REGISTER

プレミアム会員登録

CONTACT

メールフォーム