数学における論理式 (ろんりしき: logical expression[1] )とは、真理値 を必要とする場所にあらわれる式 で、原子論理式 や、それを論理演算子 で結びあわせた式である。ここでは古典論理 のものを例示するが、非古典論理 をはじめ、他の多くの論理体系についても同様な議論は可能である。
命題論理 の論理式は命題論理式 (英語版 ) とも呼ばれ[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)))
言語
Q
{\displaystyle {\mathcal {Q}}}
における論理式が「妥当 」であるとは、
Q
{\displaystyle {\mathcal {Q}}}
のあらゆる解釈 において真であることを意味する。
言語
Q
{\displaystyle {\mathcal {Q}}}
における論理式が「充足可能 (英語版 ) 」であるとは、
Q
{\displaystyle {\mathcal {Q}}}
のある解釈で真であることを意味する。
A が 算術 における論理式で、それが「決定可能」であるとは、それが決定可能集合 を表している場合、すなわち A に出現する自由変数に値を代入したとき、その真偽を判定する実効的方法がある場合である。
形式言語 を構成する統語論的実体の概念図。記号(英 : symbol )と記号列(英 : strings of symbols )は、その形式言語に含まれないものと含まれるもの(整式)に大別される。形式言語はその論理式の集合と等価と考えることができる(大袈裟な言いかたをしているだけで、コンピュータのプログラミング言語 で言えば要するに、構文規則に沿ってないソースコードは構文エラー(シンタックスエラー)である、というのと同じ話)。論理式の集合は定理 (theorem) とそうでないものに大別される。
初期の数理論理学 者の幾人かは、『formula 』を「単なる記号列」、『well-formed formula 』を「formula のうち、正しい構成規則に従って作られた記号列」として区別し[4] 、幾人かは単に「formula 」と総称した[5] [6] [7] [8] 。
いずれにせよ形式言語 という考え方が定着した現代では、わざわざ断ることなどなく、整式のみが議論の対象である。すなわち、定められている構文規則に従った記号の並び(たとえば数式であれば 1 * (2 + 3) といったような)のみが議論の対象となる式であり、同様の記号を使っていても、単なるデタラメに並べたものにしか見えないようなもの(たとえば数式であれば * + ) 3 5 / といったような)は、何か変な議論を仕掛けようとしている哲学者などでもない限り、単に、議論の対象から外すだけである(オッカムの剃刀 )。
とはいえある程度は意識される概念であり、well-formed formula という句は様々な著作に見られる[9] [10] [11] 。
Alonzo Church, [1996] (1944), Introduction to mathematical logic, page 49
Hilbert, David; Ackermann, Wilhelm (1950) [1937], Principles of Mathematical Logic, New York: Chelsea
Barwise, Jon, ed. (1982), Handbook of Mathematical Logic, Studies in Logic and the Foundations of Mathematics, Amsterdam: North-Holland, ISBN 978-0-444-86388-1 Cori, Rene; Lascar, Daniel (2000), Mathematical Logic: A Course with Exercises, Oxford University Press, ISBN 978-0-19-850048-3 Enderton, Herbert [2001] (1972), A mathematical introduction to logic (2nd ed.), Boston, MA: Academic Press, ISBN 978-0-12-238452-3 R. L. Simpson (1999), Essentials of Symbolic Logic, page 12
Mendelson, Elliott [2010] (1964), An Introduction to Mathematical Logic (5th ed.), London: Chapman & Hall
Allen, Layman E. (1965), “Toward Autotelic Learning of Mathematical Logic by the WFF 'N PROOF Games”, Mathematical Learning: Report of a Conference Sponsored by the Committee on Intellective Processes Research of the Social Science Research Council , Monographs of the Society for Research in Child Development 30 (1): 29–41
Boolos, George; Burgess, John; Jeffrey, Richard (2002), Computability and Logic (4th ed.), Cambridge University Press , ISBN 978-0-521-00758-0 (pb.)
Enderton, Herbert (2001), A mathematical introduction to logic (2nd ed.), Boston, MA: Academic Press, ISBN 978-0-12-238452-3
Gamut, L.T.F. (1990), Logic, Language, and Meaning, Volume 1: Introduction to Logic , University Of Chicago Press, ISBN 0-226-28085-3
Goble, Lou, ed. (2001), The Blackwell Guide to Philosophical Logic , Blackwell, ISBN 978-0-631-20692-7
Hofstadter, Douglas (1980), Gödel, Escher, Bach: An Eternal Golden Braid , Penguin Books, ISBN 978-0-14-005579-5
Kleene, Stephen Cole (2002) [1967], Mathematical logic , New York: Dover Publications , ISBN 978-0-486-42533-7 , MR 1950307
Rautenberg, Wolfgang (2010), A Concise Introduction to Mathematical Logic (3rd ed.), New York : Springer Science+Business Media, doi :10.1007/978-1-4419-1221-3 , ISBN 978-1-4419-1220-6 , http://www.springerlink.com/content/978-1-4419-1220-6/