論理式 (数学)

命題論理の論理式は命題論理式とも呼ばれ^[2]、例えば『(A∧(B∨C))』といった形で表現される。命題論理式は、命題変数と論理演算を表す記号と括弧で定義され、命題変数を表すアルファベットは論理演算記号や括弧を含まないものとされる。論理式はそれらを並べたものである。

論理式は次のように再帰的に定義される。

• 命題変数は、単独でも論理式である。
• 『φ』が論理式であるとき『¬φ』も論理式である。
• 『φ』と『ψ』が論理式であるとき、二項結合子を『•』で表すとすると『(φ•ψ)』も論理式である。一般には、『∨』『∧』『→』『↔』といった記号が二項結合子として使われる。

この定義をバッカス・ナウア記法で形式文法として記述することもできる。変数の種類は有限とすると、次のようになる。

⟨alpha set⟩ ::= p|q|r|s|t|u|…（命題変数の有限集合）

⟨form⟩ ::= ⟨alpha set⟩ | ¬ ⟨form⟩ | (⟨form⟩ ∧ ⟨form⟩) | (⟨form⟩ ∨ ⟨form⟩) | (⟨form⟩ → ⟨form⟩) | (⟨form⟩ ↔ ⟨form⟩)

この文法を使って次のような記号列が記述できる。

(((p→q)∧(r→s))∨(¬q∧¬s))

これは、文法的に正しいので論理式である。一方、

((p→q)→(qq))p))

こちらは文法に従っていないので論理式ではない。

複雑な論理式、特に括弧を多用した論理式は理解するのが難しい。この問題を緩和するため、数学における演算子の優先順位のように結合子間の優先順位を設けることもできる。例えば、優先される順に『¬』『→』『∧』『∨』とする。すると

(((p→q)∧(r→s))∨(¬q∧¬s))

という論理式は次のようにも表現できる。

p→q∧r→s∨¬q∧¬s

ただし、これは論理式の記述を簡略化するための単なる取り決めである。したがって例えば、左結合性で優先順を『¬』『∧』『∨』『→』と取り決めれば、上の括弧のない論理式は次のように解釈される。

(p→(q∧r))→(s∨((¬q)∧(¬s)))

Summarize Timeline Fact Check

一階述語論理 ${\displaystyle {\mathcal {QS}}}$ における論理式の定義は、その理論のシグネチャ（英語版）に左右される。シグネチャとは、当該理論の非論理記号である定数記号、述語記号、関数記号を指定するもので、同時に関数記号や述語記号のアリティ（引数の数）の定義もシグネチャに含まれる。

シグネチャ${\textstyle \Sigma }$を指定したうえで、項を以下によって再帰的に定義する。項とは、議論領域の対象物を表現したものである。

1. 任意の変数は項である。
2. シグネチャ${\textstyle \Sigma }$に含まれる任意の定数記号は項である。
3. t₁、…、t_n が項、f がアリティ n の関数記号ならば、f(t₁,…,t_n) は項である。

次に原子論理式が定義される。

1. t₁ と t₂ が項ならば、t₁=t₂ は原子論理式である。
2. R がアリティ n の述語記号、t₁、…、t_n が項ならば、R(t₁,…,t_n) は原子論理式である。

最後に論理式は、原子論理式の集合を含む最小の集合として次のように定義される。

1. 任意の原子論理式は論理式である。
2. ${\displaystyle \ \phi }$ が論理式ならば、${\displaystyle \neg \phi }$ は論理式である。
3. ${\displaystyle \ \phi }$ と ${\displaystyle \ \psi }$ が論理式ならば、${\displaystyle (\phi \land \psi )}$ と ${\displaystyle (\phi \lor \psi )}$ は論理式である。
4. ${\displaystyle \ x}$ が変数、${\displaystyle \ \phi }$ が論理式ならば、${\displaystyle \exists x\,\phi }$ は論理式である。
5. ${\displaystyle \ x}$ が変数、${\displaystyle \ \phi }$ が論理式ならば、${\displaystyle \forall x\,\phi }$ は論理式である（${\displaystyle \forall x\,\phi }$ は ${\displaystyle \neg \exists x\,\neg \phi }$ の省略形と定義することもできる）。

何らかの変数 ${\displaystyle \ x}$ があるとき、${\displaystyle \exists x}$ あるいは ${\displaystyle \forall x}$ が全く出現しない論理式は量化子のない論理式と呼ばれる。量化子のない論理式の前に存在量化がある論理式を存在論理式と呼ぶ。

原子論理式と開論理式

→詳細は「原子論理式」を参照

原子論理式とは、論理結合子や量化子を含まない論理式、あるいは厳密な部分論理式を持たない論理式である。原子論理式の厳密な形式は、どんな形式体系のものかで変わってくる。例えば命題論理での原子論理式は命題変数である。一階述語論理では、項である引数を伴った述語記号が原子論理式である。

量化子を伴わず、論理結合子のみを使って原子論理式を結合した論理式を「開論理式」と呼ぶこともある^[3]。

閉論理式

閉論理式または文とは、自由変数がない論理式を指す。一階述語論理の論理式に変数が出現する場合、閉論理式とするためにはそれぞれの変数に対応して束縛作用素（量化子など）を前置する必要がある。

• 言語 ${\displaystyle {\mathcal {Q}}}$ における論理式が「妥当」であるとは、${\displaystyle {\mathcal {Q}}}$ のあらゆる解釈において真であることを意味する。
• 言語 ${\displaystyle {\mathcal {Q}}}$ における論理式が「充足可能（英語版）」であるとは、${\displaystyle {\mathcal {Q}}}$ のある解釈で真であることを意味する。
• A が 算術 における論理式で、それが「決定可能」であるとは、それが決定可能集合を表している場合、すなわち A に出現する自由変数に値を代入したとき、その真偽を判定する実効的方法がある場合である。

初期の数理論理学者の幾人かは、『formula』を「単なる記号列」、『well-formed formula』を「formula のうち、正しい構成規則に従って作られた記号列」として区別し^[4]、幾人かは単に「formula」と総称した^[5][6][7][8]。

いずれにせよ形式言語という考え方が定着した現代では、わざわざ断ることなどなく、整式のみが議論の対象である。すなわち、定められている構文規則に従った記号の並び（たとえば数式であれば 1 * (2 + 3) といったような）のみが議論の対象となる式であり、同様の記号を使っていても、単なるデタラメに並べたものにしか見えないようなもの（たとえば数式であれば * + ) 3 5 / といったような）は、何か変な議論を仕掛けようとしている哲学者などでもない限り、単に、議論の対象から外すだけである（オッカムの剃刀）。

とはいえある程度は意識される概念であり、well-formed formula という句は様々な著作に見られる^[9][10][11]。