述語論理入門

はじめに

述語論理は、一階論理または述語計算としても知られ、オブジェクト、その属性、およびオブジェクト間の関係について推論することを可能にする命題論理の強力な拡張です。命題論理が陳述を原子単位として扱うのに対し、述語論理は陳述の内部を見てその内部構造を表現する能力を提供します。

この表現力により、述語論理は数学、コンピュータサイエンス、人工知能、言語学、形式検証にとって不可欠です。数学的構造の記述、データベースクエリ、ソフトウェア仕様、知識表現システムの論理的基礎を提供します。

命題論理の限界

命題論理は完全な陳述についての推論には有用ですが、一般化、オブジェクトの性質、または関係を表現する必要がある場合には重大な制限があります。命題論理では、「ソクラテスは人間である」と「プラトンは人間である」のような陳述は、共通の構造を共有しているにもかかわらず、別々の無関係な命題（PとQ）として表現しなければなりません。

命題論理は、「すべて」、「いくつか」、「すべての」、または「存在する」を含む陳述を表現できません。「すべての人間は死ぬ」と「ソクラテスは人間である」の間の論理的関係を捉えることができず、これらは論理的に「ソクラテスは死ぬ」を導くべきです。ここで述語論理が不可欠になります。

制限の例

「すべての人間は死ぬ」という陳述を考えてみましょう。命題論理では、これを単一の命題Hとしてしか表現できません。しかし、これは「すべての人間」と「死ぬ」という属性に関わる内部構造を捉えることができません。述語論理では、これをより正確に∀x (Human(x) → Mortal(x))と表現できます。

述語

述語は、1つ以上のオブジェクトに帰属させることができる性質または関係です。述語を、オブジェクトを入力として受け取り、真理値（真または偽）を出力として返す関数と考えてください。述語により、オブジェクトの性質とオブジェクト間の関係を表現できます。

述語は、大文字の後に括弧内の1つ以上の引数を続けて表記されます。例えば、P(x)は「xは性質Pを持つ」を表し、R(x, y)は「xは関係Rによってyと関連している」を表します。

述語の例

Human(x) - 「xは人間である」（単項述語、1つの引数）
GreaterThan(x, y) - 「xはyより大きい」（二項述語、2つの引数）
Between(x, y, z) - 「xはyとzの間にある」（三項述語、3つの引数）
Prime(n) - 「nは素数である」（単項述語）

量化子

量化子は、論議領域において述語が成り立つ標本の数を指定する特別な記号です。2つの基本的な量化子は次のとおりです：

全称量化子（∀）

述語が論議領域のすべての要素に対して成り立つことを表現します。考慮中の宇宙のすべてのオブジェクトについて主張します。

記法: ∀x P(x)（「すべてのxに対してP(x)が成り立つ」と読む）

例: ∀x (Human(x) → Mortal(x)) - 「すべてのxに対して、xが人間であればxは死ぬ」

存在量化子（∃）

述語が成り立つ要素が領域内に少なくとも1つ存在することを表現します。特定の性質を持つ何かの存在を主張します。

記法: ∃x P(x)（「P(x)となるxが存在する」と読む）

例: ∃x Prime(x) - 「素数である数が存在する」

述語論理の構造

述語論理表現にはいくつかの重要な構成要素があります：

項

定数（「ソクラテス」のような特定のオブジェクト）、変数（x、yのようなプレースホルダー）、関数（項を生成する演算）。

論理式

整形式（WFF）は、述語、量化子、変数、論理結合子を組み合わせた構文的に正しい表現です。

束縛変数と自由変数

量化子によって束縛された変数（例：∀xのx）対量化されていない自由変数。

例

述語論理の表現力を示すいくつかの例を以下に示します：

数学的陳述

∀x ∀y ((x > 0 ∧ y > 0) → (x + y > 0)) - 「すべての正の数xとyに対して、その和は正である」

関係

∀x (Parent(x, y) → ∃z Loves(x, z)) - 「すべてのxに対して、xがyの親であれば、xが愛するzが存在する」

複雑な陳述

∃x (Student(x) ∧ ∀y (Course(y) → Enrolled(x, y))) - 「すべてのコースに登録している学生が存在する」

量化子を含む論理的同値

命題論理に論理的同値があるように、述語論理にも量化子を含む重要な同値があります：

全称の否定: ¬(∀x P(x)) ≡ ∃x ¬P(x) - 「すべてのxが性質Pを持つわけではない」は「性質Pを持たないxが存在する」と同値
存在の否定: ¬(∃x P(x)) ≡ ∀x ¬P(x) - 「性質Pを持つxが存在しない」は「すべてのxに対して、xは性質Pを持たない」と同値
分配法則: ∀x (P(x) ∧ Q(x)) ≡ (∀x P(x)) ∧ (∀x Q(x)) - 全称量化子は連言に分配される

応用

述語論理は、コンピュータサイエンスと数学の多くの分野の基礎となっています：

データベース

SQLなどの関係データベースクエリ言語は述語論理の原則に基づいており、クエリはデータベースリレーションに対する述語を表現します。

形式検証

ソフトウェアとハードウェアシステムの形式検証は、正確性の性質を指定し証明するために述語論理に大きく依存しています。

人工知能

述語論理は、AIシステムにおける知識表現を可能にし、機械が自動計画やエキスパートシステムにおいてオブジェクト、その属性、関係について推論することを可能にします。

数学

ほぼすべての数学的陳述と証明は述語論理を使用しており、数の性質の定義から数学的構造に関する定理の表現まで及びます。

命題論理との関係

述語論理は命題論理の上に構築され、述語と量化子を追加します。命題論理のすべての論理結合子（¬、∧、∨、→、↔）は述語論理でも有効で、同じように機能します。違いは、原子命題を組み合わせる代わりに、述語と量化された表現を組み合わせることです。

すべての命題論理陳述は、述語や量化子が使用されていない述語論理の特殊なケースと見なすことができます。逆に、一般的な陳述ではなく特定のインスタンスを扱う場合、述語論理は命題論理に還元されます。

命題計算機の使用

この計算機は命題論理とブール代数に焦点を当てていますが、命題論理と述語論理の関係を理解することで、両方のシステムの理解を深めることができます。ここで使用する演算子と真理表は、より表現力豊かな述語論理の基礎を形成します。

命題論理用の論理計算機を試す→