GsMATH

数学に関する記事を書きます。

述語論理とは

f:id:gs_blog:20190706052145j:plain
Friedrich Ludwig Gottlob Frege (1848 - 1925)
ドイツ人、フリードリヒ・ルートヴィヒ・ゴットロープ・フレーゲ。述語論理の発案者。まず変数の量化を発案し、その後公理的な述語論理の体系を完成させた。

この記事では、数学を理解するために最低限必要なレベルで述語論理について書いています。

述語論理を一言で言うと、「命題の中身に踏み込んだ論理学」ということができると思います。

述語論理とは

述語

定義(命題関数(述語)、変数)

(1)何らかの $ x_1,x_2\dots$(無限個でもよい)に関する文章で、$ x_1,x_2,\dots$ たち全てが具体的に定まると命題になる文章を $ P(x_1,x_2\dots)$ のように表し、$ x_1,x_2,\dots$ についての命題関数あるいは述語といいます。

(2)(1)における $ x_i$ たちを変数といいます。また、変数の範囲はあらかじめ指定されているものとします。

「$ 2$ は自然数である」という文章は、誰しもが正しいと認める文章なので命題です。しかし、$ x$ が何であるかは定めないままで

$ P(x)$:「$ x$ は自然数である」

という文章を考えると、この状態では真偽が不明です。この $ P(x)$ のような文章が命題関数です。変数を具体的な対象に指定することで初めて、命題関数が命題となり真偽が確定します。例えば、$ P(2)$ は真、$ P(\sqrt{3})$ は偽です。

また、命題関数 $ P(x)$ の $ x$ の範囲は、明示的には言及されていませんが*1明らかに「数」に関する文章なので、$ x$ が取りうる値としては通常数と呼ばれるもの(実数や複素数)の範囲であると考えられます。

命題論理と述語論理の違い

命題論理は、複数の命題の間の関係性について調べるものでした。例えばいかなる命題 $ P$、$ Q$ に対しても

対偶律: $ (P\rightarrow Q)\leftrightarrow (\lnot Q\rightarrow \lnot P)$

が成り立つことなどは命題論理の結果です。それに対して、述語論理は命題自体、つまり命題の内容がもつ性質について考察します。

量化

述語論理を特徴づけるのが量化概念です。述語を定義するにあたって変数という概念を考えましたが、変数は量化によりその範囲が定められます。

全称量化(全ての~)

定義(全称量化子)

$ x$ を変数とします。記号で $ \forall x$ と表したとき、これが「全ての $ x$ が」という文章と同じであると定義します。$ \forall$ を全称量化子といいます。

存在量化(ある~)

定義(存在量化子)

$ x$ を変数とします。記号で $ \exists x$ と表したとき、これが「ある $ x$ が」という文章と同じであると定義します。$ \exists$ を存在量化といいます。

公理

述語論理のド・モルガンの法則

定理(述語論理のド・モルガンの法則)

$ P(x)$ を $ x_1,x_2,\dots,x_n$(有限個)のうちいずれかになる変数 $ x$ に関する命題関数とします。このとき、次が成り立ちます。

(1)$ (\lnot(\forall xP(x)))$ $ \leftrightarrow$ $( \exists x(\lnot P(x)))$

(2)$ (\lnot\exists x(P(x)))$ $ \leftrightarrow$ $ (\forall x(\lnot P(x)))$

証明

1:$ \lnot(\forall xP(x))$ $ \Leftrightarrow$ $ \lnot(P(x_1)\land P(x_2)\land\dots\land P(x_n))$

2:$ \lnot(P(x_1)\land P(x_2)\land\dots\land P(x_n))$ $ \Leftrightarrow$ $ \lnot(P(x_1)\land( P(x_2)\land\dots\land P(x_n)))$

3:$ \lnot(P(x_1)\land( P(x_2)\land\dots\land P(x_n)))$ $ \Leftrightarrow$ $ \lnot P(x_1)\lor \lnot( P(x_2)\land\dots\land P(x_n))$

4:

証明を見ていただくとわかると思いますが、「有限個」の仮定は外すことはできません。 しかし、$ x$ が取りうる値の可能性が無限個であったとしても上のルールは成り立つと考えたい *2 です。したがって個数の制限を取り払った次の公理を採用します。

公理(述語論理のド・モルガンの法則)

$ x$ を変数、$ P(x)$ を $ x$ に関する命題関数とします。このとき、

(1)$(\lnot(\forall xP(x)))\leftrightarrow(\exists x(\lnot P(x)))$

(2)$(\lnot(\exists xP(x)))\leftrightarrow(\forall x(\lnot P(x)))$

が成り立ちます。

(おわり)

*1:厳密には $ P(x)$ を「実数 $ x$ は自然数である」のような文章として定義するべきですが、文脈上 $ x$ の範囲が明らかなときはこうした省略がよく行われます。

*2:例えば、もし $ x$ の取りうる値が無限個あるときに限り $ (\lnot(\forall xP(x) ) )$ $ \rightarrow$ $ (\exists x(\lnot P(x) ) )$ が成り立たないと仮定すると、このとき $ \exists x(\lnot P(x) )$が偽、つまり $ \lnot(\exists x(\lnot P(x) ) )$ が真にならなければなりません。このことを文章にすると、「無限個の $ x$ 全てが $ P(x)$ を満たさないならば、 $ P(x)$ を満たさない $ x$ が存在しない」という意味不明な文章が正しいことになってしまいます。普通に考えてこれは変なので、$ x$ の取りうる値が無限個であったとしてもド・モルガンの法則は成り立つと考えたくなります。