本記事で学べること

・述語論理の基本

はじめに

プログラムは論理的に書かれています。ここでいう論理的とは、論理学で定められている規則にしたがっているということです。したがって、プログラムを書くにしても読むにしても、論理学の知識が多少なりとも必要になってきます。そこで今回は、命題論理を拡張した述語論理について解説したいと思います。

述語論理とは

述語論理は、論理学の分野の一つであり、数学的な表現と推論のための形式体系です。述語論理は、命題論理を拡張して、より複雑な表現や推論を扱うことができます。
述語論理では、命題を述語と変数を用いて表現します。変数は具体的な値を持つことができる未知の要素を表し、述語はその変数に対して真または偽の値を返します。述語は、特定の属性や関係を持つ対象を指定するために使用されます。
また、述語論理では、量化子として存在量化子（∃）と全称量化子（∀）を使用することもあります。存在量化子は、ある変数に対して、その値が存在することを主張する記号であり、全称量化子は、ある変数に対して、その値が全ての可能な値を網羅することを主張する記号です。

述語論理の語彙

述語論理では、個体変項、個体定項、述語記号、論理記号を用いて命題を表現します。
 

個体変項

述語記号の中に入れる、具体的な値が定まっていない項のことです。x や y を用いて表します。
 

個体定項

述語記号の中に入れる、具体的な値が定まっている項のことです。c や 固有名 などが用いられます。
 

述語記号

述語を表す記号のことです。P(∗), Q(∗1, ∗2) などが用いられます。∗ の数が n 個の述語記号をn-項述語記号と呼びます。P(∗) は1-項述語記号、Q(∗, ∗) は2-項述語記号です。
 

論理記号

存在量化子を ∃、全称量化子を ∀ で表します。例えば、 ∃x P(x) は ある x が P を成り立たせることを表し、∀xP(x) は 全ての x が P を成り立たせることを表します。

練習問題

それでは問題をいくつか解いてみましょう。
 

問題1

「∗1 は ∗2 を愛する」 を表す2-項述語記号を L(∗1, ∗2) 、太郎を a、花子を b として、「太郎は花子を愛する」を述語記号を用いて表せ。
 

解説

L(∗1, ∗2) の ∗1 を a 、 ∗2 を b に置き換えればよいので、答えは L(a, b) になります。
 

問題2

「全ての自然数には自身より大きい自然数が存在する」ということを述語記号を用いて表せ。なお、N を自然数の集合として、n, n’ ∈ N とする。
 

解説

この問題では、述語記号の指定がされていないので、自分で決めます。「∗1 < ∗2 」を表す述語記号を O(∗1, ∗2) としましょう。これと n を用いると、「全ての自然数には自身より大きい自然数が存在する」は、∀n∃n’O(n, n’) と表せます。

まとめ

本記事では、述語論理について学んできました。述語論理はプログラムの至るところで使われています。ぜひ本記事の内容をしっかりと理解し、今後の開発に活かしてください。