3.4. 述語論理

1. 述語理論（述語論理）とは

　述語理論（述語論理）とは、命題論理を拡張したもので、命題の内部構造を表現できる論理体系です。命題論理では「今日は雨が降っている」といった文全体を1つの命題として扱いますが、述語論理では「xは雨が降っている」というように対象（個体）と述語に分けて表現します。

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

命題論理

• 命題全体を真か偽かの2値で表現
• 命題の内部構造を分析しない
• 記号：P, Q, R など

述語論理

• 命題を「対象（個体）」と「述語」に分けて表現
• 命題の内部構造を分析する
• 記号：P(x), Q(x, y) など

3. 述語論理の基本要素

3.1. 個体

　述語論理で扱う対象のことを個体と呼びます。例えば「太郎」「りんご」「コンピュータ」などが個体です。個体は通常、小文字のアルファベット（a, b, c, …）や変数（x, y, z, …）で表します。

3.2. 述語

　個体がどのような性質を持つか、個体同士がどのような関係にあるかを表すものを述語と呼びます。述語は通常、大文字のアルファベット（P, Q, R, …）で表します。

例：

• P(x): 「xは人間である」
• Q(x, y): 「xはyより大きい」

3.3. 量化子（限量子）

　述語論理では、命題論理にはない「量化子」という概念が導入されます。量化子には以下の2種類があります。

• 全称量化子（∀）: 「すべての〜について」を表す
  • ∀x P(x): すべてのxについてP(x)が成り立つ
• 存在量化子（∃）: 「少なくとも1つの〜が存在する」を表す
  • ∃x P(x): P(x)を満たすxが少なくとも1つ存在する

3.4. 恒真式と矛盾式

• 恒真式（トートロジー）: 変数の値に関わらず常に真となる論理式
  • 例：P(x) ∨ ¬P(x)（排中律）
• 矛盾式: 変数の値に関わらず常に偽となる論理式
  • 例：P(x) ∧ ¬P(x)（矛盾律）

4. 述語論理の基本演算

　述語論理では、命題論理と同様に以下の論理演算子を使用します。

1. 否定（¬）: 「〜でない」
2. 論理積（∧）: 「かつ」
3. 論理和（∨）: 「または」
4. 含意（→）: 「ならば」
5. 同値（↔）: 「必要十分条件」

5. 述語論理の重要な変形ルール

5.1. 限量子の否定の移動

• ¬∀x P(x) ≡ ∃x ¬P(x)
  • 「すべてのxについてP(x)が成り立つわけではない」は「P(x)が成り立たないxが存在する」と同値
• ¬∃x P(x) ≡ ∀x ¬P(x)
  • 「P(x)を満たすxが存在しない」は「すべてのxについてP(x)は成り立たない」と同値

5.2. ド・モルガンの法則

　述語論理においても、命題論理と同様にド・モルガンの法則が成り立ちます。

• ¬(P ∧ Q) ≡ ¬P ∨ ¬Q
• ¬(P ∨ Q) ≡ ¬P ∧ ¬Q

5.3. 含意の変形

• P → Q ≡ ¬P ∨ Q

6. 述語論理と自然言語

　自然言語の文章を述語論理で表現することで、複雑な命題を形式的に扱うことができます。

例：

• 「すべての人間は死ぬ」: ∀x (人間(x) → 死ぬ(x))
• 「知恵のある人が存在する」: ∃x (人間(x) ∧ 知恵がある(x))

7. 述語論理の応用

　述語論理は、以下のような分野で応用されています。

1. 人工知能: 知識表現や推論エンジンの基礎
2. データベース: 関係代数（選択操作や射影操作など）の理論的基礎
3. プログラミング言語: 論理型プログラミング言語（Prologなど）の基礎

7.1. データベースと述語論理

データベースの関係代数と述語論理には密接な関係があります。

• 選択操作: 条件に合致する行を抽出する操作で、述語論理では論理積（∧）で表現
• 射影操作: 特定の属性（列）を取り出す操作で、述語論理では存在量化子（∃）を使って表現

8. 述語論理の問題例と解答

例題1: 基本的な述語論理の変形

問題： 次の述語論理式 ¬∀x (P(x) → Q(x)) を否定記号（¬）が述語にのみかかるように変形したとき、正しいものはどれか。

1. ∃x (¬P(x) ∧ ¬Q(x))
2. ∃x (P(x) ∧ ¬Q(x))
3. ∀x (P(x) ∧ ¬Q(x))
4. ∀x (¬P(x) ∨ Q(x))

例題2: 述語論理と自然言語

問題： 次の日本語の文を述語論理で表したとき、最も適切なものを選びなさい。

「すべてのプログラマはコンピュータを使う。賢い人の中にはプログラマがいる。」

ただし、P(x): xはプログラマである、C(x): xはコンピュータを使う、S(x): xは賢い

1. ∀x (P(x) → C(x)) ∧ ∃x (S(x) ∧ P(x))
2. ∀x (P(x) → C(x)) ∧ ∀x (S(x) → P(x))
3. ∃x (P(x) ∧ C(x)) ∧ ∃x (S(x) ∧ P(x))
4. ∀x (P(x) ∧ C(x)) ∧ ∃x (S(x) → P(x))

例題3: 限量子と推論

問題： 以下の前提から導き出される結論として妥当なものを選びなさい。

前提1: ∀x (P(x) → Q(x)) 前提2: ∃x (P(x) ∧ R(x))

1. ∃x (Q(x) ∧ R(x))
2. ∀x (P(x) → R(x))
3. ∃x (Q(x) → R(x))
4. ∀x (Q(x) ∧ R(x))

まとめ

　述語論理は命題論理を拡張し、より豊かな表現力を持つ論理体系です。個体と述語の概念、全称量化子と存在量化子による限量、そして基本的な論理演算を組み合わせることで、複雑な命題を形式的に扱うことができます。特に、人工知能やデータベース理論など情報科学の様々な分野での応用があり、情報処理技術者にとって重要な基礎知識となっています。

5. 参考情報

　より詳しく知りたい方は、以下のページをご参照下さい。