PREDICATE LOGIC

述語論理

OVERVIEW

述語論理とは何か

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

OUTLINE

TABLE OF CONTENTS

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

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

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

述語論理における論理式の定義

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

閉論理式・開論理式

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

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 に戻ります。この命題において論理積と論理和の関係を入れ替えた主張も成り立ちます。以上を吸収律と呼びます。

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

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

述語論理における矛盾律

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

述語論理における排中律

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

述語論理における恒等律

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