命題論理

命題論理とは

命題論理は、数理論理学の基礎となる分野であり、命題全体を一つの記号で表し、論理演算子を用いて命題間の関係を分析することを目的とします。命題論理では、個々の命題の具体的な内容よりも、それらが「かつ」「ならば」といった論理演算子でどのように結びつくか、その結果どのような推論が可能になるかに重点が置かれます。これは、命題を構成する要素（主語や述語）を詳細に分析する述語論理とは対照的です。

概要

命題論理における命題の取り扱いは、通常、命題計算または文計算と呼ばれます。これは、命題変数を原子式とする形式的な推論体系によって行われます。命題論理の主な関心事は、個々の命題の意味そのものではなく、命題が論理演算子によって結びつけられた際に生じる推論のパターンです。

推論の性質に応じて、直観主義論理や様相論理など様々な種類の命題論理が存在しますが、一般的に「命題論理」という言葉は古典命題論理を指します。以下では、この古典命題論理を中心に解説します。

命題計算は、文法的に正しい表現（整式）の集合、それらから選ばれた公理の集合、そして表現空間における変形規則の集合によって構成される形式体系です。これらの規則は、表現が数学的に解釈される際に意味の同等性を保つように与えられます。特に論理体系として解釈される場合は、「意味の同等性」は論理的同等性を指します。

命題論理の言語は、命題変数（命題を表現する記号）と論理演算子（結合子）から構成されます。整式は、原子式や論理演算子の組み合わせとして形式的に定義されます。また、公理の集合は空[[集合]]でも、有限[[集合]]でも、可算無限集合でも構いません。さらに、意味論によって真偽の値付けが与えられ、どの整式が定理であるかを決定できるようになります。

文法

命題論理の言語は、以下の要素で構成されます。

命題変数: アルファベットの大文字で表され、原子式となります。
論理演算子:
¬ (否定): 「〜ではない」を表します。
∧ (連言): 「かつ」を表します。
∨ (選言): 「または」を表します。
→ (含意): 「ならば」を表します。
(使用できる文字が限られた環境では、チルダ「~」やアンパサンド「&」などの記号が代用されることがあります。)
括弧: ( )。式の結合順序を明確にするために使用します。

整式の集合は、以下の規則によって帰納的に定義されます。

1. 基本: アルファベットの大文字（命題変数）は整式です。
2. 帰納節 I: もしφが整式ならば、¬φも整式です。
3. 帰納節 II: もしφとψが整式ならば、(φ ∧ ψ)、(φ ∨ ψ)、(φ → ψ)も整式です。
4. 閉節: 上記以外は整式ではありません。

これらの規則を繰り返し適用することで、より複雑な整式を作成できます。例えば、A、¬A、B、(¬A ∨ B)などはすべて整式です。

計算

命題論理は、整式間の論理的関係を示すために用いられます。これは、利用可能な変形規則を使って「証明」や「展開」と呼ばれる手続きを行うことで実現されます。証明は、各行が論理式である複数行の記述によって表現されます。それぞれの行には、根拠や理由が示され、その論理式がどのように導かれたかを説明します。

公理と推論規則

ここでは、公理を持たない自然演繹体系を用いて説明します。この体系では、八つの推論規則を用いて、真と仮定された式から別の真の式を導出します。最初の六つは非仮定的規則、最後の二つは仮定的規則です。

非仮定的規則:

1. 二重否定の除去: ¬¬φ から φ を推論できます。
2. 論理積の導入: φ と ψ から (φ ∧ ψ) を推論できます。
3. 論理積の消去: (φ ∧ ψ) から φ と ψ をそれぞれ推論できます。
4. 論理和の導入: φ から (φ ∨ ψ) と (ψ ∨ φ) を推論できます。
5. 論理和の消去: (φ ∨ ψ)、(φ → χ)、(ψ → χ) から χ を推論できます。
6. モーダスポネンス: φ と (φ → ψ) から ψ を推論できます。

仮定的規則:

1. 条件付き証明: φ を仮定して ψ が導かれたら、(φ → ψ) を推論できます。
2. 背理法: φ を仮定して ψ と ¬ψ が導かれたら、¬φ を推論できます。

証明の例

例として、A → A を証明する手順は以下のようになります。

1. A (仮定)
2. A → A (条件付き証明、1より)

規則の健全性と完全性

命題論理の推論規則には、健全性と完全性という重要な性質があります。健全性は、規則が「正しい」推論のみを導くことを意味し、完全性は、すべての妥当な推論を規則によって導けることを意味します。

真理値の割り当て

真理値の割り当ては、命題変数に真(⊤)または偽(⊥)の値を割り当てる関数です。これにより、式がどのような場合に真になるかを定義できます。

命題変数Pが真のとき、Pは充足される。
φが充足されないとき、¬φは充足される。
φとψが両方充足されるとき、(φ ∧ ψ)は充足される。
φまたはψの少なくとも一方が充足されるとき、(φ ∨ ψ)は充足される。
φが充足されるにも関わらずψが充足されないことがないとき、(φ → ψ)は充足される。

健全性

もしφが整式の集合Sから統語的に導出されるならば、φはSから意味論的に帰結します。

完全性

もしφが整式の集合Sから意味論的に帰結するならば、φはSから統語的に導出されます。

別の論理計算の定式化

命題計算は、公理を定義し、推論規則を一つだけ持つ方法でも定式化できます。以下は、いくつかの異なる公理系と推論規則の例です。

公理系1 (クリーネ)

11の公理とモーダスポネンスのみを推論規則とする体系です。

(AND-1) (φ ∧ ψ) → φ
(AND-2) (φ ∧ ψ) → ψ
(AND-3) φ → (ψ → (φ ∧ ψ))
(OR-1) φ → (φ ∨ ψ)
(OR-2) ψ → (φ ∨ ψ)
(OR-3) (φ → χ) → ((ψ → χ) → ((φ ∨ ψ) → χ))
(IMP-1) (φ → ψ) → ((φ → (ψ → χ)) → (φ → χ))
(IMP-2) φ → (ψ → φ)
(NOT-1) (φ → ψ) → ((φ → ¬ψ) → ¬φ)
(NOT-2) ¬¬φ → φ
(NOT-3) φ ∨ ¬φ

公理系2 (ヒルベルト)

以下の3つの公理とモーダスポネンスを推論規則とする体系です。

φ → (χ → φ)
(φ → (χ → ψ)) → ((φ → χ) → (φ → ψ))
(¬ψ → ¬φ) → (φ → ψ)

公理系3

ヒルベルトの公理系2のうち、最初の2つの公理を以下の4つで置き換えたものです。

φ → (χ → φ)
(χ → (χ → φ)) → (χ → φ)
(φ → (χ → ψ)) → (χ → (φ → ψ))
(χ → ψ) → ((φ → χ) → (φ → ψ))

他の命題計算

命題計算は、他の論理計算の基礎となる最も単純な論理体系の一つです。命題計算を拡張することで、より複雑な推論を扱えるようになります。

一階述語論理: 命題論理の「原始的叙述」を項、変数、述語、量化子に分解し、より詳細な分析を可能にします。例：すべての猫は哺乳類である、から、たまが猫なら、たまは哺乳類である、を推論できる。
様相論理: 必然性や可能性などの様相概念を扱えるように拡張したものです。例えば、ρが必然的である、からρを推論できる。
* 多値論理: 真偽以外の真理値を許容する論理体系です。

もう一度検索