2要素ブール代数

数学および抽象代数学において、2要素ブール代数とは、基礎となる集合（または宇宙、あるいはキャリア）Bがブール領域であるブール代数のことである。慣例として、ブール領域の要素は1と0であり、B = {0, 1}となる。ポール・ハルモスがこの代数に付けた「2」という名称は文献で広く用いられており、本稿でもこの名称を用いる。   

Bは半順序集合であり、 Bの要素は同時にその境界でもある。

項数nの演算は、 B ⁿからBへの写像です。ブール代数は、2 つの二項演算と単項補数から構成されます。二項演算はさまざまな方法で命名および表記されています。ここでは、それぞれ「和」と「積」と呼ばれ、中置記法「+」と「∙」で表記されます。和と積は、通常の実数代数と同様に、可換かつ結合します。演算の順序に関しては、括弧が存在する場合はそれが決定的な要素となります。そうでない場合は、「∙」が「+」の前に来ます。したがって、A ∙ B + Cは( A ∙ B ) + Cと解析され、 A ∙ ( B + C)とは解析されません。補数は、引数の上にオーバーバーを記述することで表されます。X の補数の数値アナログは1 − Xです。普遍代数の言語では、ブール代数は${\displaystyle \langle B,+,}$・${\displaystyle ,{\overline {..}},1,0\rangle }$型の代数${\displaystyle \langle 2,2,1,0,0\rangle }$。

{0,1} と { True , False }の間の一対一対応は、いずれも等式形式の古典的な二値論理を生み出し、補数はNOTと読みます。1 がTrueと読み取られる場合、'+' はORと読み取られ、'∙' はANDと読み取られます。1 がFalseと読み取られる場合はその逆です。これらの 2 つの操作は、ブール半環として知られる可換半環を定義します。

2は、以下の自明な「ブール」演算に基づいていると見なすことができる。

${\displaystyle {\begin{aligned}&1+1=1+0=0+1=1\\&0+0=0\\&0\cdot 0=0\cdot 1=1\cdot 0=0\\&1\cdot 1=1\\&{\overline {1}}=0\\&{\overline {0}}=1\end{aligned}}}$

ご了承ください：

• '+' と '∙' は、1+1=1 という点を除いて、数値演算とまったく同じように機能します。'+' と '∙' は数値演算から類推によって導き出されたもので、ゼロ以外の数値を単純に 1 に設定するだけです。
• 0と1、そして「+」と「∙」を入れ替えても真理は保たれる。これが、すべてのブール代数に共通する双対性の本質である。

このブール演算は、各変数への0と1のあらゆる可能な割り当てを調べることによって、公理を含む2の任意の方程式を検証するのに十分です（決定手順を参照）。

以下の式が検証できる。

${\displaystyle {\begin{aligned}&A+A=A\\&A\cdot A=A\\&A+0=A\\&A+1=1\\&A\cdot 0=0\\&{\overline {\overline {A}}}=A\end{aligned}}}$

'+'と'∙'はそれぞれ、互いに分配関係にある。

• ${\displaystyle \ A\cdot (B+C)=A\cdot B+A\cdot C;}$
• ${\displaystyle \ A+(B\cdot C)=(A+B)\cdot (A+C).}$

「∙」が「+」に対して分配法則を満たすことは初等代数と一致しますが、「+」が「∙」に対して分配法則を満たすことは一致しません。このような理由などから、積の和（ NAND演算につながる）は、和の積（ NOR演算につながる）よりも一般的に用いられます。

'+'と'∙'はそれぞれ、互いの関係と補数を用いて定義することができる。

• ${\displaystyle A\cdot B={\overline {{\overline {A}}+{\overline {B}}}}}$
• ${\displaystyle A+B={\overline {{\overline {A}}\cdot {\overline {B}}}}.}$

必要なのは二項演算が 1 つだけで、連結でそれを表せば十分です。したがって、連結とオーバーバーで2 を表記できます。この表記法は、クワインのブール項スキーマの表記法でもあります。( X ) をXの補集合とし、"()" を 0 または 1 のいずれかとすると、G. スペンサー・ブラウンの『形式の法則』の基本的な代数の構文が得られます。

2の基底とは、公理と呼ばれる一連の方程式であり、そこから上記のすべての方程式（およびそれ以上の方程式）を導出できます。すべてのブール代数、したがって2に対しては、多くの既知の基底が存在します。連結とオーバーバーのみを使用して表記された簡潔な基底は次のとおりです。

1. ${\displaystyle \ ABC=BCA}$（連結通勤、関連）
2. ${\displaystyle {\overline {A}}A=1}$（2は補数格子であり、上限は1である）
3. ${\displaystyle \ A0=A}$（0は下限値です。）
4. ${\displaystyle A{\overline {AB}}=A{\overline {B}}}$（2は分配束である）

連結条件がORの場合、1は真、0は偽、またはANDの場合、1は偽、0は真となります。（どちらの場合も、上付きバーは否定を表します。）

0=1の場合、(1)～(3)はアーベル群の公理である。

（１）は連結が可換かつ結合的であることを証明するだけです。まず、（１）が左または右のどちらかから結合すると仮定し、次に可換性を証明します。次に反対方向からの結合を証明します。結合性とは、左と右からの結合を組み合わせたものです。

この基礎により、証明への容易なアプローチが可能になり、これは「形式の法則」では「計算」と呼ばれ、公理（2）～（4）および基本恒等式を呼び出し、式を0または1に単純化することによって進められます。${\displaystyle AA=A,{\overline {\overline {A}}}=A,1+A=1}$そして分配法則。

ド・モルガンの定理は、任意のブール関数に対して、以下の操作をこの順序で行うと、次のようになると述べています。

• すべての変数を補完する。
• '+'演算子と'∙'演算子を入れ替えます（演算順序が同じになるように括弧を追加することに注意してください）。
• 結果を補完し、

その結果は、論理的には元の状態と等価です。関数の各部分にド・モルガンの定理を繰り返し適用することで、すべての補数を個々の変数にまで絞り込むことができます。

強力かつ非自明なメタ定理によれば、2の任意の恒等式はすべてのブール代数に対して成り立つ。^{[ 1 ]}逆に、任意の非自明なブール代数に対して成り立つ恒等式は2でも成り立つ。したがって、ブール代数のすべての恒等式は2によって捉えられる。この定理は、2の任意の方程式を決定手続きによって検証できるため有用である。論理学者はこの事実を「 2は決定可能である」と呼ぶ。既知のすべての決定手続きは、検証対象の方程式に現れる変数の数Nの指数関数であるステップ数を必要とする。ステップ数がNの多項式関数である決定手続きが存在するかどうかは、P = NP予想の対象となる。

上記のメタ定理は、原子的な正の等式だけでなく、より一般的な一階述語論理式の妥当性を考慮すると成り立ちません。例として、式( x = 0) ∨ ( x = 1)を考えてみましょう。この式は、2要素ブール代数では常に真です。定義域が の冪集合である4要素ブール代数では、${\displaystyle \{0,1\}}$⁠、この式はステートメント( x = ∅) ∨ ( x = {0,1})に対応し、 x が⁠の場合には偽となります${\displaystyle \{1\}}$⁠ 。多くのクラスのブール代数の1階理論の決定可能性は、量化子消去法または小さなモデル特性（定義域のサイズは式の関数として計算され、一般に2より大きい）を使用して示すことができます。

• ブール代数
• 有界集合
• 格子（順序）
• 秩序理論

コンピュータ時代の初期には、ブール代数に関する多くの入門書が出版されました。その中でもおそらく最も優れたものの一つであり、現在も出版されているのが以下のものです。

• メンデルソン、エリオット、1970年。『シャウムのブール代数概論』マグロウヒル。

以下の項目は、2要素ブール代数が数学的に非自明であることを示している。

• スタンフォード哲学百科事典：「ブール代数の数学」、J.ドナルド・モンク著。
• Burris, Stanley N.、および HP Sankappanavar, HP、1981 年。『普遍代数学入門』。Springer -Verlag。ISBN 3-540-90578-2。