数学における論理式(ろんりしき: logical expression[1])とは、真理値を必要とする場所にあらわれる式で、原子論理式や、それを論理演算子で結びあわせた式である。ここでは古典論理のものを例示するが、非古典論理をはじめ、他の多くの論理体系についても同様な議論は可能である。 命題論理の論理式は命題論理式
命題論理
論理式は次のように再帰的に定義される。
命題変数は、単独でも論理式である。
『φ』が論理式であるとき『¬φ』も論理式である。
『φ』と『ψ』が論理式であるとき、二項結合子を『•』で表すとすると『(φ•ψ)』も論理式である。一般には、『∨』『∧』『→』『↔』といった記号が二項結合子として使われる。
この定義をバッカス・ナウア記法で形式文法として記述することもできる。変数の種類は有限とすると、次のようになる。⟨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))) 一階述語論理 Q S {\displaystyle {\mathcal {QS}}} における論理式の定義は、その理論のシグネチャ
述語論理
シグネチャ Σ {\textstyle \Sigma } を指定したうえで、項を以下によって再帰的に定義する。項とは、議論領域の対象物を表現したものである。
任意の変数は項である。
シグネチャ Σ {\textstyle \Sigma } に含まれる任意の定数記号は項である。
t1、…、tn が項、f がアリティ n の関数記号ならば、f(t1,…,tn) は項である。
次に原子論理式が定義される。
t1 と t2 が項ならば、t1=t2 は原子論理式である。
R がアリティ n の述語記号、t1、…、tn が項ならば、R(t1,…,tn) は原子論理式である。
最後に論理式は、原子論理式の集合を含む最小の集合として次のように定義される。
任意の原子論理式は論理式である。
ϕ {\displaystyle \ \phi } が論理式ならば、 ¬ ϕ {\displaystyle \neg \phi } は論理式である。
ϕ {\displaystyle \ \phi } と ψ {\displaystyle \ \psi } が論理式ならば、 ( ϕ ∧ ψ ) {\displaystyle (\phi \land \psi )} と ( ϕ ∨ ψ ) {\displaystyle (\phi \lor \psi )} は論理式である。
x {\displaystyle \ x} が変数、 ϕ {\displaystyle \ \phi } が論理式ならば、 ∃ x ϕ {\displaystyle \exists x\,\phi } は論理式である。
x {\displaystyle \ x} が変数、 ϕ {\displaystyle \ \phi } が論理式ならば、 ∀ x ϕ {\displaystyle \forall x\,\phi } は論理式である( ∀ x ϕ {\displaystyle \forall x\,\phi } は ¬ ∃ x ¬ ϕ {\displaystyle \neg \exists x\,\neg \phi } の省略形と定義することもできる)。
何らかの変数 x {\displaystyle \ x} があるとき、 ∃ x {\displaystyle \exists x} あるいは ∀ x {\displaystyle \forall x} が全く出現しない論理式は量化子のない論理式と呼ばれる。量化子のない論理式の前に存在量化がある論理式を存在論理式と呼ぶ。
原子論理式と開論理式詳細は「原子論理式」を参照
原子論理式とは、論理結合子や量化子を含まない論理式、あるいは厳密な部分論理式を持たない論理式である。原子論理式の厳密な形式は、どんな形式体系のものかで変わってくる。例えば命題論理での原子論理式は命題変数(英語版)である。一階述語論理では、項である引数を伴った述語記号が原子論理式である。
量化子を伴わず、論理結合子のみを使って原子論理式を結合した論理式を「開論理式」と呼ぶこともある[3]。 閉論理式または文とは、自由変数がない論理式を指す。一階述語論理の論理式に変数が出現する場合、閉論理式とするためにはそれぞれの変数に対応して束縛作用素(量化子など)を前置する必要がある。
閉論理式
属性
言語 Q {\displaystyle {\mathcal {Q}}} における論理式が「妥当」であるとは、 Q {\displaystyle {\mathcal {Q}}} のあらゆる解釈において真であることを意味する。
言語 Q {\displaystyle {\mathcal {Q}}} における論理式が「充足可能