論理式 (数学)

数学、数理論理学、命題論理、述語論理などにおいて、論理式（ろんりしき、）とは、真理値を必要とする場所にあらわれる式のことであり、原子論理式や、それを論理演算子で結びあわせた式のことである共立『数学小辞典』「論理式」。

ここでは古典論理のものを例示するが、非古典論理をはじめ、他の多くの論理体系についても同様な議論は可能である。

 命題論理 
命題論理の論理式はとも呼ばれFirst-order logic and automated theorem proving, Melvin Fitting, Springer, 1996、例えば『』といった形で表現される。命題論理式は、と論理演算を表す記号と括弧で定義され、命題変数を表すアルファベットは論理演算記号や括弧を含まないものとされる。論理式はそれらを並べたものである。

論理式は次のように再帰的に定義される。
命題変数は、単独でも論理式である。
『』が論理式であるとき『』も論理式である。
『』と『』が論理式であるとき、二項結合子を『』で表すとすると『』も論理式である。一般には、『』『』『』『』といった記号が二項結合子として使われる。

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

（命題変数の有限集合）

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

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

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

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

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

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

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

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

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

次に原子論理式が定義される。
 t1 と t2 が項ならば、t1=t2 は原子論理式である。
 R がアリティ n の述語記号、t1、…、tn が項ならば、R(t1,…,tn) は原子論理式である。

最後に論理式は、原子論理式の集合を含む最小の集合として次のように定義される。
 任意の原子論理式は論理式である。
  が論理式ならば、 は論理式である。
  と  が論理式ならば、 と  は論理式である。
  が変数、 が論理式ならば、 は論理式である。
  が変数、 が論理式ならば、 は論理式である（ は  の省略形と定義することもできる）。

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

 原子論理式と開論理式 

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

量化子を伴わず、論理結合子のみを使って原子論理式を結合した論理式を「開論理式」と呼ぶこともあるHandbook of the history of logic, (Vol 5, Logic from Russell to Church), Tarski's logic by Keith Simmons, D. Gabbay and J. Woods Eds, p568.。

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

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

 語誌 
初期の数理論理学者の幾人かは、『』を「単なる記号列」、『』を「 のうち、正しい構成規則に従って作られた記号列」として区別しAlonzo Church, [1996] (1944), Introduction to mathematical logic, page 49、幾人かは単に「」と総称したHilbert, David; Ackermann, Wilhelm (1950) [1937], Principles of Mathematical Logic, New York: ChelseaHodges, Wilfrid (1997), A shorter model theory, Cambridge University Press, ISBN 978-0-521-58713-6Barwise, Jon, ed. (1982), Handbook of Mathematical Logic, Studies in Logic and the Foundations of Mathematics, Amsterdam: North-Holland, ISBN 978-0-444-86388-1Cori, Rene; Lascar, Daniel (2000), Mathematical Logic: A Course with Exercises, Oxford University Press, ISBN 978-0-19-850048-3。

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

とはいえある程度は意識される概念であり、 という句は様々な著作に見られるEnderton, Herbert [2001] (1972), A mathematical introduction to logic (2nd ed.), Boston, MA: Academic Press, ISBN 978-0-12-238452-3R. L. Simpson (1999), Essentials of Symbolic Logic, page 12Mendelson, Elliott [2010] (1964), An Introduction to Mathematical Logic (5th ed.), London: Chapman & Hall。

 脚注 

 参考文献 








 関連項目 
原子論理式

 外部リンク 

 Well-Formed Formula for First Order Predicate Logic - includes a short Java quiz.
 Well-Formed Formula at ProvenMath
 WFF N PROOF game site


*
Category:形式言語
Category:数理論理学
Category:述語論理
Category:数学に関する記事