論理式 (数学)

論理式とは

数学、数理論理学、特に命題論理や述語論理において、論理式は真偽を判定できる式のことを指します。これらは、原子論理式と呼ばれる最も基本的な要素や、それらを論理演算子で結合した複合的な式で構成されています。古典論理を基本としますが、非古典論理など他の論理体系でも同様の概念が適用できます。

命題論理

命題論理における論理式は命題論理式とも呼ばれ、例えば `(A∧(B∨C))` のように表現されます。命題論理式は、命題変数（アルファベットで表される）と論理演算を表す記号（¬、∧、∨、→、↔など）と括弧によって定義されます。これらの要素を組み合わせることで、様々な複雑な論理式を表現できます。

論理式は再帰的に定義されます。

1. 命題変数はそれ自体が論理式です。
2. `φ` が論理式ならば `¬φ` も論理式です。
3. `φ` と `ψ` が論理式ならば `(φ•ψ)` も論理式です（ここで `•` は二項結合子を表し、通常は `∨`、`∧`、`→`、`↔` などが用いられます）。

これらの定義はバッカス・ナウア記法で形式的に記述することもできます。例えば、命題変数の集合を `` として、次のように定義できます。


::= p|q|r|s|t|u|...

::= | ¬ | ( ∧ ) | ( ∨ ) | ( → ) | ( ↔ )


この文法に従えば、 `(((p→q)∧(r→s))∨(¬q∧¬s))` のような複雑な論理式も記述できますが、`((p→q)→(qq))p))` のように文法に合わないものは論理式ではありません。

複雑な論理式を理解しやすくするために、演算子の優先順位を定めることがあります。例えば、¬、→、∧、∨ の順に優先度を設定すると、上記の論理式は `p→q∧r→s∨¬q∧¬s` と簡略化して記述できます。ただし、これは単なる表記上の取り決めに過ぎず、優先順位の解釈によって式の意味が変わることがあります。

述語論理

述語論理における論理式の定義は、その理論のシグネチャに依存します。シグネチャとは、定数記号、述語記号、関数記号とそのアリティ（引数の数）を定義するものです。

項は、議論領域の対象物を表現したものであり、以下のように再帰的に定義されます。

1. 任意の変数は項です。
2. シグネチャに含まれる任意の定数記号は項です。
3. `t1`, ..., `tn` が項で、`f` がアリティ `n` の関数記号ならば、 `f(t1,...,tn)` は項です。

原子論理式は以下のように定義されます。

1. `t1` と `t2` が項ならば、`t1=t2` は原子論理式です。
2. `R` がアリティ `n` の述語記号で、 `t1`, ..., `tn` が項ならば、 `R(t1,...,tn)` は原子論理式です。

論理式は、原子論理式を含む最小の集合として、再帰的に定義されます。

1. 任意の原子論理式は論理式です。
2. `φ` が論理式ならば `¬φ` も論理式です。
3. `φ` と `ψ` が論理式ならば、 `(φ∧ψ)` と `(φ∨ψ)` も論理式です。
4. `x` が変数で、`φ` が論理式ならば、 `∃xφ` も論理式です（存在量化子）。
5. `x` が変数で、`φ` が論理式ならば、 `∀xφ` も論理式です（全称量化子）。`∀xφ` は `¬∃x¬φ` の省略形として定義することもできます。

量化子 (`∃x`, `∀x`) を含まない論理式は量化子のない論理式と呼ばれ、その前に存在量化子がある論理式は存在論理式と呼ばれます。

原子論理式は、論理結合子や量化子を含まない最も基本的な論理式です。例えば、命題論理における命題変数や、述語論理における項を伴う述語記号がこれにあたります。量化子を含まず、論理結合子のみを使って原子論理式を結合したものを「開論理式」と呼ぶこともあります。

閉論理式

閉論理式（または文）は、自由変数を含まない論理式です。述語論理式において変数が現れる場合、閉論理式とするには、各変数に対応する束縛作用素（量化子など）を前置する必要があります。

論理式の属性

論理式が「妥当」であるとは、その言語におけるあらゆる解釈において真であることを意味します。一方、「充足可能」であるとは、ある解釈において真であることを意味します。算術における論理式が「決定可能」であるとは、自由変数に値を代入した際に、その真偽を判定する実効的な方法が存在することを指します。

語誌

初期の数理論理学者の中には、『formula』を単なる記号列、『well-formed formula』を正しい構成規則に従って作られた記号列として区別していた人もいますが、現代では、形式言語という概念が定着したため、整式のみが議論の対象となっています。しかし、well-formed formula という言葉は依然として多くの文献に見られます。

まとめ

論理式は、数理論理学において真偽を扱うための基本的な要素であり、命題論理や述語論理において様々な形で使用されます。論理式の正確な定義を理解することで、より複雑な論理構造や推論を理解する基礎となります。

もう一度検索