論理結合子

一般的に使用される論理結合子には、次のものがあります。^{[ 1 ]}

• 否定（not）：${\displaystyle \neg }$、${\displaystyle \sim }$、${\displaystyle N}$（接頭辞）${\displaystyle \neg }$は最も近代的で広く使用されており、${\displaystyle \sim }$これもよくあることです。
• 接続詞（and）：${\displaystyle \wedge }$、${\displaystyle \&}$、${\displaystyle K}$（接頭辞）${\displaystyle \wedge }$最も近代的で広く使用されている。
• 論理和（または）：${\displaystyle \vee }$、${\displaystyle A}$（接頭辞）${\displaystyle \vee }$最も近代的で広く使用されている。
• 含意（もし…ならば）：${\displaystyle \to }$、${\displaystyle \supset }$、${\displaystyle \Rightarrow }$、${\displaystyle C}$（接頭辞）${\displaystyle \to }$は最も近代的で広く使用されており、${\displaystyle \supset }$これもよくあることです。
• 同値性（必要条件）：${\displaystyle \leftrightarrow }$、${\displaystyle \subset \!\!\!\supset }$、 ${\displaystyle \Leftrightarrow }$、${\displaystyle \equiv }$、${\displaystyle E}$（接頭辞）${\displaystyle \leftrightarrow }$は最も近代的で広く使用されており、${\displaystyle \subset \!\!\!\supset }$一般的に使用されるのは${\displaystyle \supset }$も使用されます。

例えば、 「雨が降っている」という文の意味は、${\displaystyle p}$）そして私は屋内にいます（${\displaystyle q}$）は、論理結合子で結合されると変換されます。

• 雨は降っていません（${\displaystyle \neg p}$);
• 雨が降っていて、私は屋内にいます（${\displaystyle p\wedge q}$);
• 雨が降っているか、屋内にいる（${\displaystyle p\lor q}$);
• 雨が降っている場合は、屋内にいます（${\displaystyle p\rightarrow q}$);
• 私が屋内にいる場合は、雨が降っています（${\displaystyle q\rightarrow p}$);
• 雨が降っている場合に限り屋内にいます（${\displaystyle p\leftrightarrow q}$)

常に真である式と常に偽である式を結合子とみなすこともよくあります（この場合、それらは空項です）。

• 真の公式：${\displaystyle \top }$、${\displaystyle 1}$、${\displaystyle V}$（接頭辞）または${\displaystyle \mathrm {T} }$;
• 誤った数式:${\displaystyle \bot }$、${\displaystyle 0}$、${\displaystyle O}$（接頭辞）または${\displaystyle \mathrm {F} }$。

この表は用語をまとめたものです。

• 否定：記号${\displaystyle \neg }$1930 年にHeytingに登場^{[ 2 ] [ 3 ]} (フレーゲのBegriffsschriftの記号 ⫟ と比較してください^{[ 4 ]} )。シンボル${\displaystyle \sim }$1908年にラッセルに登場した。^{[ 5 ]}別の表記法としては、数式の上に水平線を追加する方法がある。${\displaystyle {\overline {p}}}$別の表記法としては、プライム記号を使用する方法もあります。${\displaystyle p'}$。
• 接続詞：記号${\displaystyle \wedge }$1930年にヘイティングに登場した^{[ 2 ]}（ペアノによる集合論的交差記法の使用と比較せよ）。${\displaystyle \cap }$^{[ 6 ]}）記号${\displaystyle \&}$少なくとも1924年のシェーンフィンケルに登場した。 ^{[ 7 ]}そのシンボル${\displaystyle \cdot }$これは、ブールが論理を初等代数として解釈したことに由来する。
• 選言: 記号${\displaystyle \vee }$1908年にラッセルに登場した^{[ 5 ]}（ペアノによる集合論的和集合記法の使用と比較せよ）。${\displaystyle \cup }$）記号${\displaystyle +}$は、${\displaystyle +}$通常の初等代数の排他的または論理的に解釈すると2要素環になります。${\displaystyle +}$右下隅のドットとともに、パースによって使用された。^{[ 8 ]}
• 意味：シンボル${\displaystyle \to }$1918年にヒルベルト誌に掲載された。 ^{[ 9 ]： 76}${\displaystyle \supset }$1908年にラッセルによって使用された^{[ 5 ]}（ピーノのƆ、逆Cと比較）。${\displaystyle \Rightarrow }$1954年にブルバキに登場した。 ^{[ 10 ]}
• 等価性：記号${\displaystyle \equiv }$1879年にフレーゲで; ^{[ 11 ]}${\displaystyle \leftrightarrow }$1933年のベッカー（初めてではなく、これについては以下を参照）；^{[ 12 ]}${\displaystyle \Leftrightarrow }$1954年にブルバキに登場した。 ^{[ 13 ]}歴史の中で、他のシンボルが断続的に登場した。${\displaystyle \supset \subset }$Gentzenでは、^{[ 14 ]}${\displaystyle \sim }$シェーンフィンケル^{[ 7 ]}または${\displaystyle \subset \supset }$チャザルでは、^{[ 15 ]}
• 真: シンボル${\displaystyle 1}$これは、論理を2要素ブール代数上の初等代数として解釈したことに由来する。他の表記法には、${\displaystyle \mathrm {V} }$（ラテン語の「verum」の略語）は、1889年にペアノの著作に見られる。
• 偽: シンボル${\displaystyle 0}$はブールの論理を環として解釈したことにも由来する。他の表記法には以下のようなものがある。${\displaystyle \Lambda }$（回転）${\displaystyle \mathrm {V} }$1889年にペアノで発見された。

一部の著者は接続詞として文字を使用した。${\displaystyle \operatorname {u.} }$接続詞（ドイツ語の「und」は「and」）と${\displaystyle \operatorname {o.} }$ヒルベルトの初期作品（1904年）では、選言（ドイツ語の「oder」は「または」）を表す。^{[ 16 ]}${\displaystyle Np}$否定の場合、${\displaystyle Kpq}$接続詞として、${\displaystyle Dpq}$代替拒否の場合、${\displaystyle Apq}$選言の場合、${\displaystyle Cpq}$暗示として、${\displaystyle Epq}$1929年にウカシェヴィチで二条件付きで。

逆含意のような論理的接続詞${\displaystyle \leftarrow }$は実際には引数を入れ替えた実質条件文と同じであるため、逆含意の記号は冗長である。いくつかの論理計算（特に古典論理）では、本質的に異なる複合命題が論理的に同値である。冗長性のより自明でない例は、次の古典的な同値性である。${\displaystyle \neg p\vee q}$そして${\displaystyle p\to q}$したがって、古典論理システムでは条件演算子「${\displaystyle \to }$" もし "${\displaystyle \neg }$「（いいえ）そして」${\displaystyle \vee }$「（または）既に使用されているか、または使用する可能性がある」${\displaystyle \to }$「否定と選言を1つずつ持つ複合語の構文糖としてのみ使用される。」

入力の真偽値を関連付けるブール関数は16個あります。${\displaystyle p}$そして${\displaystyle q}$4桁のバイナリ出力を持つ。^{[ 17 ]}これらは、古典論理のバイナリ論理結合子の可能な選択肢に対応する。古典論理の異なる実装では、機能的に完全な結合子の異なる部分集合を選択できる。

一つのアプローチは、最小限の集合を選択し、上記の実質条件文の例のように、他の結合子を何らかの論理形式で定義することです。古典論理において、引数の数が2を超えない最小限の機能的に完全な演算子の集合は次のとおりです。

1つの要素

${\displaystyle \{\uparrow \}}$、${\displaystyle \{\downarrow \}}$。

2つの要素

${\displaystyle \{\vee ,\neg \}}$、${\displaystyle \{\wedge ,\neg \}}$、${\displaystyle \{\to ,\neg \}}$、${\displaystyle \{\gets ,\neg \}}$、${\displaystyle \{\to ,\bot \}}$、${\displaystyle \{\gets ,\bot \}}$、${\displaystyle \{\to ,\nleftrightarrow \}}$、${\displaystyle \{\gets ,\nleftrightarrow \}}$、${\displaystyle \{\to ,\nrightarrow \}}$、${\displaystyle \{\to ,\nleftarrow \}}$、${\displaystyle \{\gets ,\nrightarrow \}}$、${\displaystyle \{\gets ,\nleftarrow \}}$、${\displaystyle \{\nrightarrow ,\neg \}}$、${\displaystyle \{\nleftarrow ,\neg \}}$、${\displaystyle \{\nrightarrow ,\top \}}$、${\displaystyle \{\nleftarrow ,\top \}}$、${\displaystyle \{\nrightarrow ,\leftrightarrow \}}$、${\displaystyle \{\nleftarrow ,\leftrightarrow \}}$。

3つの要素

${\displaystyle \{\lor ,\leftrightarrow ,\bot \}}$、${\displaystyle \{\lor ,\leftrightarrow ,\nleftrightarrow \}}$、${\displaystyle \{\lor ,\nleftrightarrow ,\top \}}$、${\displaystyle \{\land ,\leftrightarrow ,\bot \}}$、${\displaystyle \{\land ,\leftrightarrow ,\nleftrightarrow \}}$、${\displaystyle \{\land ,\nleftrightarrow ,\top \}}$。

別のアプローチとしては、特定の便利で機能的に完全ではあるものの、最小ではない集合の、同等の権利を持つ結合子を用いる方法がある。このアプローチでは、より多くの命題公理が必要となり、論理形式間の各同値関係は、公理であるか、定理として証明可能でなければならない。

しかし、直観主義論理では状況はより複雑です。その5つの論理結合子{∧, ∨, →, ¬, ⊥}のうち、否定「¬」だけが他の論理結合子に還元できます（詳しくは「偽（論理）」§  「偽、否定、矛盾」を参照）。連言、選言、実質条件文はいずれも、他の4つの論理結合子から構成される同等の形式を持ちません。

論理演算子に対する真理関数的アプローチは、デジタル回路では論理ゲートとして実装されます。事実上すべてのデジタル回路（主な例外はDRAM ）は、 NAND、NOR、NOT、および伝送ゲートで構成されています。詳細については、「コンピュータサイエンスにおける真理関数」を参照してください。ビットベクトル（有限ブール代数に対応）上の論理演算子は、ビット単位の演算です。

しかし、コンピュータプログラミングにおける論理結合子のすべての使用法がブール意味論を持つわけではありません。たとえば、P ∧ QおよびP ∨ Qに対して遅延評価が実装される場合があるため、式PまたはQのいずれか、あるいは両方に副作用がある場合、これらの結合子は可換ではありません。また、ある意味で実質条件結合子に対応する条件文は、本質的に非ブールです。なぜなら、の場合、前件P が偽であれば後件Q は実行されないからです（ただし、複合式全体としては成功 ≈ 「真」となります）。これは、古典論理の見解よりも、実質条件文に関する直観主義や構成主義の見解に近いものです。if (P) then Q;  

論理結合子は、集合論の基本演算を定義するために使用され、^{[ 21 ]}次のように定義されます。

この集合の等価性の定義は、外延性の公理と同等である。