述語論理

トップページ研究分野と周辺記号論理

命題論理は例えば「AはBだ」という命題をp等の論理記号で表現し、それを要素命題として扱った。
述語論理(記述論理ともいう)は、その内部構造を明示するため、「AはBだ」といった述語を用いた命題を、述語記号と項(変数又は定数)で表現する。
日本語では「AのB」といった表現でよく表される、命題ではない複合概念は、関数記号で表現する。
また量化記号を使い、日本語の「全てのA」「或るA」といった概念を記号で表現出来るのも特長だ。量化記号を変数にのみ用いる述語論理を一階述語論理という。
命題論理の拡張なので、「否定」「連言」「選言」「含意」の論理記号も使用する。
量化記号を述語や関数にも用いる論理を二階以上の高階述語論理というが、論理的に完全ではないとされる。ここでは一階述語論理について述べる。

項と述語記号・関数記号

例えば「ソクラテス」をsという項で表現し、Pは「人間である」の述語記号とすると、P(s)で「ソクラテスは人間である」という真偽を持つ論理式になる。
項には定数と変数がある。定数は「ソクラテス」のような個々の対象を指し、変数は「人間」のように様々な異なる定数が代入され得る概念を指す。
定数を小文字の列(socrates等)、変数を最初は大文字、或いはアンダーバーを付ける(Human,_human)等で区別する。
Fを「父」という関数記号とすると、F(a)は「aの父」という項になる。
述語記号(項)は、真偽の判断が可能な命題になるが、関数記号(項)は命題ではなく、一つの項になる。

量化記号(quantifier)

「全ての」に該当する記号を全称量化記号 (universal quantifier) といい、∀で表す。
∀は右に変数を取り、∀X(P(X)→Q(X))で「全ての人間は死ぬ」を表現出来る(Xは人間の変数、Pは「人間である」、Qは「死ぬ」の述語記号であるとする)。
「或る」に該当する記号を存在量化記号 (existential quantifier) といい、∃で表す。∃も右に変数を取る。
量化記号は¬と同じくすぐ右隣の変数にしか掛らないので、例えば∀XP(X)→Q(X)とすると、∀XはP(X)にしか掛らないので、Q(X)にも掛けるには括弧で∀X(P(X)→Q(X))とする。
量化記号の掛かっている変数を束縛変数、掛かっていない変数を自由変数という。
∀Xf(X)が真である事を確かめるには、変数Xに代入し得る全ての定数を当てはめて、全てのf(X)が真である事を確認しなければならない。
∃Xf(X)が真である事を確かめるには、一つでもf(X)が真となる定数が見つかればよい。
以下に∀Xと∃Xの違いを図で示す。変数Xに入り得る定数はa~eの5つしかない場合で、∃Xはp(c)だけが真の場合を示しているが、複数のp(定数)が真でもよい。

アリティnの述語・関数記号

例えば、P(x,y)によって、xとyがPの関係にある、といった命題を表す事がある。
述語や関数記号や変数を複数持つ事が出来、変数の数をアリティと呼ぶ。アリティがnの述語・関数をn変数述語(関数)等と呼ぶ。
なお、定数をアリティ0の関数記号と呼ぶ場合もある。

多重量化記号の並び順による違い

P(X,Y)を、「XがYをPする」という命題とする。∀X∃YP(X,Y)は、「全てのXは、或るYにPする」という意味になる。
全称と存在を入換えて、∃Y∀XP(X,Y)とすると、「或るYは、全てのXにPされる」という意味になる。
ここで、前者はXごとに違うYがあり得るのに対し、後者はYは一つに限定されるという違いがある。
また、∃X∀YP(X,Y)は、「或るXは、全てのYにPする」となる。最低一つのXが、全てのYにPするのだ。
∀Y∃XP(X,Y)は、「全てのYは、或るXにPされる」という意味になる。
P(X,Y)である以上、「XがYにPする」関係は変わらないが、量化記号が左にある方を主語と考え、「~する」「~される」と読み替えればよい。
この関係を図示すると、以下のようになる。

素論理式

Pが述語記号で、t1,t2,...tnが其々、項であれば、P(t1,t2,...tn)は素論理式となる。
これは命題論理の原子命題に該当するもので、解釈(真偽を決める)の単位となる。

述語論理の複合命題

命題論理と同様に、素論理式から、以下の法則で入れ子状に複合命題を構成する事が出来る。
・素論理式は、論理式である。
・pが論理式であれば、¬pは論理式である(命題論理と同じ)。
・pとqが論理式であれば、p∧q、p∨q、p→qも論理式である(命題論理と同じ)。
・pが論理式であり、xがpに含まれる自由変数であれは、∀xp(x)と∃xp(x)も論理式である。

述語論理の恒真式

命題論理の恒真式に加えて、述語論理では量化記号に係る以下の恒真式が成立する。
¬(∀XP(X))⇔∃X(¬P(X))。全てのXについてP(X)が成り立つ、が偽ならば、P(X)ではない或るXが存在する。かつ、その逆。
¬(∃XP(X))⇔∀X(¬P(X))。或るXはP(X)である、が偽(一つも無い)ならば、全てのXについてP(X)は偽。かつ、その逆。
これらを、否定記号の移動と言うこともある。
∀X(P(X))∧∀X(Q(X))⇔∀X(P(X)∧Q(X))も恒真となる。
∃X(P(X))∨∃X(Q(X))⇔∃X(P(X)∨Q(X))。⇔の左の論理式は、P(X)になるXが一つは存在するか又はQ(X)になるXが一つは存在する、を表し、右の論理式は、P(X)又はQ(X)になるXが一つは存在する、を表している。左の論理式で存在するXがP(X)になるものでも、Q(X)になるものでも、右の論理式は成立し、逆も成立する事が分かる。
これらを限定記号の分配律という。しかしながら、以下の分配律は恒真ではない。
∀X(P(X))∨∀X(Q(X))⇔∀X(P(X)∨Q(X))。⇔の左の論理式は、全てのXにP(X)が成立するか、又は全てのXにQ(X)が成立する事を述べている。右の論理式は、全てのXについて、P(X)又はQ(X)が成立する事を述べている。この違いを図で示すと、以下のようになる(右の方は一つの例を表示している)。

∃X(P(X))∧∃X(Q(X))⇔∃X(P(X)∧Q(X))の分配律も恒真ではない。これが成り立たない例も図で示す(こちらは左右とも一つの例を示している)。

述語論理の推論

命題論理の推論に加えて、述語論理では量化記号に係る以下の推論が成立する。
もし、定数aが変数Xに代入可能であれば、命題∀XP(X)が真であるとき、P(a)も真となる。
∀X(P(X)→Q(X))とP(s)が真である事が分かっているとき、Q(s)が真である事を推論する(「全ての人間は死ぬ」∧「ソクラテスは人間である」→「ソクラテスは死ぬ」)。