論理演算

こんにちは。いつもお越しくださる方も、初めての方もご訪問ありがとうございます。

今回は論理演算の英語版Wikipediaの翻訳をします。翻訳のプロではありませんので、誤訳などがあるかもしれませんが、大目に見てください。

翻訳アプリDeepLやGoogle翻訳などを活用しています。

論理演算

論理学では、2つ以上の式を接続するための論理定数である論理結合子 logical connective （論理演算子 logical operator、文結合子、文演算子とも呼ばれる）を使用する。例えば、命題論理の構文では、二項結合子∨を使って2つの原子論理式PとQを結合し、複合論理式P∨Qを作ることができる。

※　翻訳している項目はlogical operationではなく、logical operatorもしくはlogical connectiveとなっています。日英のWikipedia版で微妙なズレがあります。英語版は演算子の説明、日本語版は演算の説明となります。connectiveは論理学で使用される場合は結合子、日常言語として使用する場合は接続詞と訳します。

※　logical connectiveの訳語として適切なものが何に当たるのか統一感がなく、日本では一般的にlogical operatorの訳語である論理演算子として表現しています。

※　論理演算で使用される用語は英語と日本語間で一対一の対応関係になっていないような印象を覚えます。

一般的な結合子には、否定、論理和（離接）、論理積（合接）、論理包含などがある。古典論理学の標準的な体系では、これらの結合子は真理関数として解釈されるが、非古典論理学ではさまざまな別の解釈がなされる。これらの古典的な解釈は、英語の 「not」、「or」、「and」、「if 」などの自然言語表現の意味と似ているが、同じではない。自然言語の接続詞と古典論理の接続詞との間の不一致は、自然言語の意味に対する非古典的なアプローチや、古典的な構成的意味論と堅牢な語用論とを組み合わせるアプローチの動機となっている。

※　Wikipediaでの演算子の日本語の呼び名が統一されておらず、様々な呼び名があります。たとえば、論理和と論理積という表現は解りやすくはありますが、disjunctionとconjunctionという外来語本来が持っている意味が消えています。直訳的には離接・合接となりますが、日本では論理和・論理積ほどには普及していない印象があります。

論理結合子は、プログラミング言語でよく使われる条件演算子と呼ばれる構文に似ているが、同等ではない。

概要

形式言語では、真理関数を曖昧さのない記号で表現する。これにより、論理的な記述が曖昧な形で理解されないようにすることができる。これらの記号は、論理結合子、論理演算子、命題演算子、あるいは古典論理学では真理関数結合子と呼ばれる。他の論理式を真理関数結合子で結合して新しい論理式を作ることができる規則については、「論理式」を参照すること。

論理結合子は2つ以上の文をつなぐために使用することができるので、n項論理結合子について説明できる。

一般的な論理結合子

一般的な論理的結合子の一覧

よく使われる論理的結合子には以下のものがある。：

否定（not）： ¬ 、N（接頭辞）、～
論理積（and）：∧、K（接頭辞）、＆、・
論理和（or）： ∨ 、A（接頭辞）
論理包含（if...then）： → 、C（接頭辞）、 ⇒ 、 ⊃
二条件一致（if and only if）： ↔ 、E（接頭辞） 、≡ 、=
二条件一致の別名は、iff（同値）、xnor（否定排他的論理和）、bi-implicationである。

※　ここではBiconditionalは「二条件一致」と訳します。以後意訳のために「同値」と訳す場合もあります。

例えば、雨が降っている。（Pで示される）と私は屋内にいる（Qで示される）という文が、論理的な接続詞で結合されると、その意味が変容する。

雨は降っていない。 （￢P）
雨が降っていて、私は屋内にいる。（P∧Q）
雨が降っていたり、屋内にいたりする。（P∨Q）
雨が降っているなら、私は屋内にいる。（P→Q）
屋内にいれば、雨が降っている。（Q→P）
雨が降っている場合に限り、私は室内にいる。（P↔Q）

また、常に真の式と常に偽の式を連結して考えるのが一般的である。

真の式（⊤、1、V [接頭辞]、またはT)
偽の式（⊥、0、O[接頭辞]、またはF)

表記法の歴史

否定：記号¬は1929年にハイティングに登場（フレーゲの概念記法における記号⫟と比較）。記号~は1908年にラッセルに登場。Pの上に横線を加える別の表記法；P'のようにプライム記号を用いる別の表記法もある。
論理積：記号∧は1929年にハイティングに登場（ペアノが集合論的な表記である共通部分∩を使用したのと比較）、記号&は少なくとも1924年にシェーンフィンケルに登場した。記号.はブールが論理学を初等代数として解釈したことに由来する。
論理和：記号∨は1908年にラッセルに登場（ペアノが集合論的な表記法である結合∪を使ったのと比較）。これは通常の初等代数の＋が排他的か2要素の環で論理的に解釈したときに曖昧であったにも関わらず、記号＋も使われた。歴史の中で時折、右下に点を付けた＋がパースPeirceによって使われている。
論理包含：記号→は1917年のヒルベルト、⊃は1908年のラッセル（ペアノの逆C表記と比較）、⇒はヴァクスVaxで使われた。
同値：記号≡は少なくとも1908年にラッセルが使っていた；↔は少なくとも1940年にタルスキが使っていた；⇔はヴァクスで使われていた；その他の記号はゲンツェンの⊃⊂、シェーンフィンケルの~、の⊂⊃のように、歴史の中で時間的に現れている。
真：記号1はブールが論理学を2要素のブール代数上の初等代数と解釈したことに由来する。他の表記としては∧（ピーノに見られる）がある。
誤：記号0はブールが論理学を環として解釈したことにも由来する。
歴史上、接続詞に文字を使った作家もいました。

※　論理演算で使用される記号の歴史は浅く、更にほとんど同じ意味を表す記号が各地域で異なる記号が用いていられています。度量衡が統一される前に各地域に多くの尺度が存在していたような、そんな感じでしょうか。数学で使用される記号がどのような歴史を辿ってきたのかということがまとめられた資料にほとんど触れたことがなかったので、ここで紹介されている歴史は個人的にはありがたいものです。

※　ざっと見た感じだと20世紀初頭に各地域の数学者が記号を発明し、その名残りが現在にも残っているという印象です。

ヒルベルト (1904)の初期の作品では、論理積をu. (ドイツ語で「und」は「and」)と論理和をo. (ドイツ語で「order」は「or」)で表したものがある。。

ウカシェヴィチ (1929)では、Npは否定、Kpqは論理積、Dpqは否定論理籍、Apqは論理和、Xpqは否定論理和、Cpqは論理包含、Epqは同値を表す。ポーランド語の表記法を参照。

冗長性

逆包含←のような論理結合子は、実際には引数を入れ替えた物質的な条件式と同じであるため、逆含意の記号は冗長である。古典論理をはじめとするいくつかの論理計算では、本質的に異なる複合文が論理的に等価であることがある。冗長な例としては、¬P∨QとP→Qの古典的な等価性がある。したがって、古典的な論理体系では、"¬"(not)と"∨"(or)がすでに使用されていれば、条件演算子"→"は必要ない。あるいは、1つの否定と1つの論理積を持つ合成の糖衣構文としてのみ「→」を使用することができる。

入力された真理値PとQを4桁の2進数で出力する16個のブール関数がある。これらは、古典論理における2進法の論理結合子の選択肢に対応している。古典論理の実装によって、結合子の機能的に完全な部分集合の選択が異なる。

一つの方法は、上記の物質的条件の例のように、最小限の集合を選択し、他の結合子を何らかの論理形式で定義することである。以下は、古典論理における演算子の機能的に完全な最小セットであり、その項は二を超えない。

一要素
｛↑｝、｛↓｝
二要素
｛∨,￢｝｛∧,￢｝｛→,￢｝｛←,￢｝｛→,⊥｝｛←,⊥｝｛→,↮｝｛←,↮｝｛←,↛｝
｛→,↚｝｛←,↛｝｛←,↚｝｛↛,￢｝｛↚,￢｝｛↛,⊤｝｛↚,⊤｝｛↛,↔｝｛↚,↔｝
三要素
｛∨,↔,⊥｝｛∨,↔,↮｝｛∨,↮,⊤｝｛∧,↔,⊥｝｛∧,↔,↮｝｛∧,↮,⊤｝

※　上記の記号の矢印の後のスラッシュは、本来記号の後ろではなく、記号自体を斜線で打消すような記号ですが、フォントの関係か、環境の関係か正しく出力されません。

もう一つのアプローチは、ある便利で機能的に完全な、しかし最小ではない集合の結合子を同等の権利で使用することである。この方法では、より多くの命題公理を必要とし、論理式間の各等価性は、公理であるか、定理として証明できるものでなければならない。

しかし、直観主義論理では状況はもっと複雑である。その5つの結合子{∧, ∨, →, ¬, ⊥}のうち、否定の「¬」だけが他の結合子に還元される（詳しくは 否定と矛盾を参照）。論理積、論理和、論理包含のいずれも、他の4つの論理結合子から構成される等価形を持たない。

自然言語

古典論理学の標準的な論理結合子は、自然言語の文法に大まかに相当するものがある。英語では、多くの言語と同様に、このような表現は通常、文法上の接続詞である。しかし、補語、動詞の接尾辞、助詞などの形をとることもある。自然言語の接続詞の意味は，自然言語の論理構造を研究する分野である形式意味論の主要な研究テーマである。

自然言語の接続詞の意味は，古典的な論理における最も近い等価物と正確には一致しない。特に、論理和は多くの言語で排他的な解釈が可能である。この事実を、自然言語の意味論が非古典的であることの証拠とする研究者もいる。しかし、他の研究者は、古典的な意味論を維持するために、非古典的であるかのように錯覚させる排他性のプラグマティックな説明を提唱している。このような説明では、排他性はスカラー含意として扱われる。関連した問題としては、自由選択の推論、ハーフォード論理和、代替質問における論理和の貢献などがある。

また、自然言語と古典論理学との間の明らかな矛盾として、論理包含のパラドックス、ロバのアナフォラ、反事実的条件式の問題などがある。これらの現象は、自然言語の条件式の表記を、厳密条件式、可変厳密条件式、および様々な動的演算子を含む論理演算子で識別するための動機付けとされている。

以下の表は、英語の接続詞の標準的な古典的定義可能な近似値である。

英単語 結合子 記号 論理ゲート
not negation "¬" NOT
and 論理積 "∧" AND
or 論理和 "∨" OR
if...then 論理包含 "→" IMPLY
...if 逆論理包含 "←"
if and only if 同値 "↔" XNOR
not both 否定論理積 "↑" NAND
neither...nor 否定論理和 "↓" NOR
but not 否定論理包含 "↛" NIMPLY

性質

論理結合子の中には、その結合子を含む定理で表現される性質を持つものがある。論理結合子が持つ特性には次のようなものがある。

結合性
同じ結合子を 2 つ以上並べた式では、オペランドの順序が変わらない限り、演算の順序は問題になりません。

交換性
結合子のオペランドを入れ替えても、元の式との論理的等価性が保たれる。

分配性
すべてのオペランド a, b, c に対して a - (b + c) = (a - b) + (a - c) である場合、- で示される接続式は + で示される別の結合子に分配される。

冪等性
演算のオペランドが同じであれば、その複合体はオペランドと論理的に等価である。

吸収性
結合子のペア∧, ∨は、すべてのオペランドa, bに対して、a∧(a∨b) = a を満たすとき、吸収性を満たす。

単調性
すべてのa1, ..., an, b1, ..., bn∈{0,1}に対して、f(a1, ..., an)≦f(b1, ..., bn)であれば、a1≦b1, a2≦b2,
..., an≦bnとなる。例：∨、∧、⊤、⊥

類似性
それぞれの変数は、演算の真理値に必ず違いをもたらすか、あるいは決して違いをもたらさない。例： ¬、↔、↮、⊤、⊥

双対性
演算の真理値の割り当てをその真理表の上から下に読むことは、同じまたは別の接続詞の表を下から上に読むことの補数を取ることと同じである。真理値表に頼らずに、g̃(¬a1, ..., ¬an) = ¬g(a1, ..., an)と定式化することもできる。例：¬

真理の保持
それらの引数がすべてトートロジーである複合式は、それ自体がトートロジーである。
例： ∨, ∧, ⊤, →, ↔, ⊂（有効性参照）。

虚偽の保持
引数がすべて矛盾である複合式は、それ自体が矛盾である。
例：∨、∧、↮, ⊥, ⊄, ⊅ (有効性参照)

非絶対性（単項接続詞の場合）
f(f(a)) = a.
例：古典論理の否定。

古典論理や直観主義論理では、「=」記号は、対応する論理複合の含意「...→...」と「...←...」がともに定理として証明できることを意味し、「≦」記号は、論理複合の「...→...」が、対応する命題変数の接続詞「...→...」の帰結であることを意味している。多値論理の中には、同値性と順序性（エンテイルメント）の定義に互換性がないものがある。

古典論理、多値論理、直観主義論理の多くの種類では、論理積と論理和の両方が結合的、交換的、冪等的である。また、論理和を越えた論理積の分配と論理積を越えた論理和の分配、および吸収法則についても真である。

古典論理といくつかの多値論理では、論理積と論理和は二元的であり、否定は自己二元的であり、後者は直観主義論理でも自己二元的である。

※　最後の方は翻訳がグダってしまっている感じがします。完全に私の能力不足です。

関連記事

最後に

最後までお付き合いいただきありがとうございました。もし記事を読んで面白かったなと思った方はスキをクリックしていただけますと励みになります。

今度も引き続き読んでみたいなと感じましたらフォローも是非お願いします。何かご感想・ご要望などありましたら気軽にコメントお願いいたします。

Twitterの方も興味がありましたら覗いてみてください。こちらよりも少し口が悪いですけれど気にしないでください。

今回はここまでになります。それではまたのご訪問をお待ちしております。