Skip to main content

Section 3.4 述語論理

命題論理を拡張し、「すべて」「ある」などを扱えるようにした枠組みを述語論理(predicate logic)という。

Subsection 3.4.1 命題関数

命題論理では、文を命題という単位で扱い、命題を組み合わせてより複雑な命題を表した。 命題には、「2は自然数である」「3は自然数である」「4は自然数である」のように、大半が同じで一部分のみが異なる命題がある。 これらの命題をまとめて表すために、命題関数(propositional function)を定義する。

定義 3.29. 命題関数.
変数\(x\)に値を代入すれば命題になり真偽が定まるものを命題関数(propositional function)といい、\(P\)という名前をつけた命題関数を\(P(x)\)のように表す。 2つの変数\(x, y\)に値を代入すれば真偽が定まる命題関数についても同様に、\(P(x, y)\)のように表す。
\(P(x)\)を「\(x\)は自然数である」とすると、\(P(1)\)は「1は自然数である」、\(P(2)\)は「2は自然数である」、\(P(2.5)\)は「2.5は自然数である」となり、いずれも命題である。 このうち、\(P(1), P(2)\)は真、\(P(2.5)\)は偽である。 また、\(Q(x, y)\)を「\(x + y\)は自然数である」とすると、\(Q(1, 2)\)は「\(1 + 2\)は自然数である」となり、命題である。 \(Q(1, 2), Q(2, 0)\)は真、\(Q(2, 0.5), Q(-3, 1)\)は偽である。 \(P(x), Q(x, y)\)を数式で表すと、次のようになる。
\begin{align*} P(x) & = \begin{cases} T & (x \in \mathbb{N}) \\ F & (\text{otherwise}) \end{cases}\\ Q(x, y) & = \begin{cases} T & (x + y \in \mathbb{N}) \\ F & (\text{otherwise}) \end{cases} \end{align*}

命題関数を用いると、命題関数\(P(x)\)が真になる\(x\)の集合は、内包的な表記で\(\{ x | P(x) \}\)と表せる。

Subsection 3.4.2 「すべて」「ある」

命題には、「2は整数である」のように具体的な数についての命題もあれば、「自然数は整数である」のように、数の集合についての命題もある。 「自然数は整数である」という命題は、自然数という集合の要素を書き並べると、「1は整数である」かつ「2は整数である」かつ「3は整数である」かつ…となり、「\(x\)は整数である」という形の文を「かつ」でつなげた命題と同値だといえる。 \(P(x)\)を「\(x\)は整数である」とすると、次のように表せる。

\begin{align*} \text{自然数は整数} &= 1\text{は整数} \land 2\text{は整数} \land 3\text{は整数} \land \cdots\\ &= P(1) \land P(2) \land P(3) \land \cdots = \bigwedge_{x \in \mathbb{N}} P(x) \end{align*}

この命題は、自然数\(x\)について\(P(x)\)が常に成り立つときに真、そうでないときに偽となる。

定義 3.31. 「すべて」.
集合\(X\)のすべて(all)の要素\(x\)について\(P(x)\)が真であるという命題を\(\forall x \in X, P(x)\)と表す。 この記号\(\forall\)は全称量化子といい、「for all」または「any」の頭文字である「A」を逆さにした記号である。
\begin{gather*} \forall x \in X, P(x) \iff \bigwedge_{x \in X} P(x) \end{gather*}
\(\forall x \in X\)は、「集合\(X\)の任意(any)の要素\(x\)について」「集合\(X\)のどの要素\(x\)についても」などともいう。

「すべて」が「かつ」に対応していると考えたとき、次のように文を「または」でつなげた命題を考えることができる。 「\(x\)は整数である」という形の文を「または」でつなげた命題は、次のように表せる。

\begin{gather*} P(1) \lor P(2) \lor P(3) \lor \cdots = \bigvee_{x \in \mathbb{N}} P(x) \end{gather*}

この命題は、自然数のうちに\(P(x)\)が成り立つ\(x\)が存在するときに真、そうでないときに偽となる。

定義 3.32. 「ある」.
集合\(X\)のある(some)要素\(x\)について\(P(x)\)が真であるという命題を\(\exists x \in X, P(x)\)と表す。 この記号\(\exists\)は存在量化子といい、「exist」の頭文字である「E」を逆さにした記号である。
\begin{gather*} \exists x \in X, P(x) \iff \bigvee_{x \in X} P(x) \end{gather*}
\(\exists x \in X\)は、「集合\(X\)の少なくとも1つの要素\(x\)について」「集合\(X\)のいずれかの要素\(x\)について」「〜が成り立つ集合\(X\)の要素\(x\)が存在(exist)する」ともいう。

Subsection 3.4.3 「すべて」「ある」の否定

「すべて」と「ある」を含む命題は、一方が他方の否定になるという関係がある。これは、英語における「any」と「some」の関係と同様である。

命題「すべての\(x\)について\(P(x)\)が成り立つ(\(\forall x \in X, P(x)\))」の否定は「ある\(x\)について\(P(x)\)が成り立たない(\(\exists x \in X, \overline{P(x)}\))」(部分否定)であり、「すべての\(x\)について\(P(x)\)が成り立たない(\(\forall x \in X, \overline{P(x)}\))」(全否定)ではないことに注意が必要である。 また、命題「ある\(x\)について\(P(x)\)が成り立つ(\(\exists x \in X, P(x)\))」の否定は「すべての\(x\)について\(P(x)\)が成り立たない(\(\forall x \in X, \overline{P(x)}\))」であり、「ある\(x\)について\(P(x)\)が成り立たない(\(\exists x \in X, \overline{P(x)}\))」ではない。

\begin{align*} \overline{\forall x \in X, P(x)} &= \overline{\bigwedge_{x \in X} P(x)}\\ &= \bigvee_{ x \in X} \overline{P(x)} (\text{de Morganの法則})\\ &= \exists x \in X, \overline{P(x)}\\ \overline{\exists x \in X, P(x)} &= \overline{\bigvee_{ x \in X} P(x)}\\ &= \bigwedge_{x \in X} \overline{P(x)} (\text{de Morganの法則})\\ &= \forall x \in X, \overline{P(x)} \end{align*}

この関係は、命題論理におけるde Morganの法則に対応している。 ただし、集合\(X\)の要素が有限個ではない(無限集合である)場合には、de Morganの法則が成り立つかどうかは明らかではない。 そのため、述語論理におけるde Morganの法則は定理ではなく公理として扱い、de Morganの法則が成り立つという前提で議論することが多い。