二元ブール代数

数学および抽象代数学において、二元ブール代数（にげんブールだいすう、テンプレート:Lang-en-short）とは、基礎集合（または宇宙または台集合）B がブール領域であるようなブール代数のことである。ブール領域の要素は慣例により 1 と 0 であり、したがって B = {0, 1}。ポール・ハルモスがこの代数に付けた名前「2」は文献においてある程度用いられており、本記事でもこれを採用する。

定義

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

アリティ n の演算は Bⁿ から B への写像である。ブール代数は二つの二項演算と単項の補元演算から成る。二項演算はさまざまな方法で名付けられ記号化されてきた。本記事ではそれらを「和」と「積」と呼び、中置記号「+」と「∙」でそれぞれ表す。和と積は通常の実数の代数と同様に交換則と結合則を満たす。演算の優先順位については、括弧があればそれが優先される。括弧がない場合は「∙」が「+」より先に計算される。したがって テンプレート:Math は テンプレート:Math と解釈され、テンプレート:Math とは解釈されない。補元はその引数の上に横棒を引いて表す。テンプレート:Mvar の補元の数値的な類比は テンプレート:Math である。普遍代数学の言語において、ブール代数は型 $⟨2,2,1,0,0⟩$ の $⟨B,+,$∙$,\overline{\mathrm{..}},1,0⟩$ 代数である。

{0,1} と {真,偽} の間の全単射のいずれかにより、補元をNOTとして読むことで、等式の形による古典的な二値論理が得られる。1 を 真、「+」をOR、「∙」をANDとして読む場合と、1 を 偽 として読む場合の逆の対応がある。これら二つの演算はブール半環と呼ばれる可換な半環を定義する。

基本的な等式

2 は次の自明な「ブール」算術に基礎を置くとみなすことができる。

$\begin{array}{cc}& 1+1=1+0=0+1=1\\ & 0+0=0\\ & 0\cdot 0=0\cdot 1=1\cdot 0=0\\ & 1\cdot 1=1\\ & \bar{1}=0\\ & \bar{0}=1\end{array}$

注目すべき点:

• 「+」と「∙」は 1+1=1 を除いて通常の数値算術とまったく同様に機能する。「+」と「∙」は数値算術との類比から導かれたものであり、単にゼロでない任意の数を 1 に設定すればよい。
• 0 と 1、「+」と「∙」を入れ替えても真理が保たれる。これはすべてのブール代数に浸透している双対性の本質である。

このブール算術は、各変数に 0 と 1 のすべての可能な割り当てを検証することにより（決定手続き参照）、2 の任意の等式（公理を含む）を検証するのに十分である。

次の等式が成り立つことを確認できる。

$\begin{array}{cc}& A+A=A\\ & A\cdot A=A\\ & A+0=A\\ & A+1=1\\ & A\cdot 0=0\\ & \overline{\stackrel{‾}{A}}=A\end{array}$

「+」と「∙」はそれぞれ互いに対して分配則を満たす。

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

「∙」が「+」に対して分配則を満たすのは初等代数学と同様であるが、「+」が「∙」に対して分配則を満たす点は異なる。この点および他の理由から、積の和（NAND合成に至る）の方が、和の積（NOR合成に至る）よりも一般に用いられる。

「+」と「∙」はそれぞれ相手と補元を用いて定義できる。

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

二項演算は一つだけで済み、連結でそれを表すのに十分である。したがって連結と横棒で 2 を記号化するのに十分である。この記号はまたクワインのブール項スキーマの記号でもある。(X) を X の補元、"()" を 0 または 1 のいずれかとすることで、G. スペンサー-ブラウンの『形式の法則』の第一代数の構文が得られる。

2 の基底とは公理と呼ばれる等式の集合であり、そこから上記の等式（およびそれ以上のもの）が導かれる。すべてのブール代数したがって 2 についての多くの既知の基底が存在する。連結と横棒のみを用いて記号化された優雅な基底は次の通りである。

1. $ABC=BCA$（連結は交換則・結合則を満たす）
2. $\bar{A}A=1$（2 は上界 1 を持つ補元束）
3. $A0=A$（0 は下界）
4. $A\overline{AB}=A\bar{B}$（2 は分配束）

ここで連結 = OR、1 = 真、0 = 偽、または連結 = AND、1 = 偽、0 = 真（横棒はいずれの場合も否定）。

0=1 とすると、(1)〜(3) はアーベル群の公理となる。

(1) は専ら連結が交換則と結合則を満たすことを証明するためにある。まず(1)が左または右から結合則を満たすと仮定し、交換則を証明する。次にもう一方の方向からの結合則を証明する。結合律は左と右双方からの結合の組み合わせに過ぎない。

この基底は「計算」と呼ばれる証明への容易なアプローチを可能にする。これは『形式の法則』で用いられた方法であり、公理(2)〜(4)と基本的な等式 $AA=A,\overline{\stackrel{‾}{A}}=A,1+A=1$、および分配律を呼び起こすことによって、式を 0 または 1 に単純化することで進む。

メタ理論

ド・モルガンの定理によれば、任意のブール関数に対して以下の操作を所定の順序で行うと：

• すべての変数を補元に取る。
• 演算子「+」と「∙」を入れ替える（演算の順序が変わらないよう括弧を加えるよう注意する）。
• 結果を補元に取る。

得られる結果は元の関数と論理的同値である。関数の一部にド・モルガンの定理を繰り返し適用することで、すべての補元を個々の変数まで追い落とすことができる。

強力かつ非自明なメタ定理として、2 の任意の等式はすべてのブール代数に対して成り立つというものがある。 逆に、任意の非自明なブール代数について成り立つ等式は 2 においても成り立つ。したがってブール代数のすべての等式は 2 によって捕捉される。このメタ定理は、2 における任意の等式が決定手続きによって検証できるため有用である。論理学者はこの事実を「2 は決定可能である」と表現する。既知の決定手続きはいずれも、検証される等式に現れる変数の個数 N の指数関数に比例するステップ数を要する。ステップ数が N の多項式関数であるような決定手続きが存在するかどうかは P = NP 予想の下に含まれる。

上記のメタ定理は、原子的な正の等式のみならず、より一般的な一階述語論理の論理式の妥当性を考慮する場合には成り立たない。例として テンプレート:Math という論理式を考えよう。この論理式は二元ブール代数では常に真である。テンプレート:Tmath の冪集合を領域とする4元ブール代数では、この論理式は テンプレート:Math という命題に対応し、x が テンプレート:Tmath のとき偽となる。多くのクラスのブール代数の一階論理理論の決定可能性は、量化子消去または小モデル性質（論理式の関数として計算され、一般に 2 より大きい領域サイズで）を用いて引き続き示すことができる。

関連項目

• ブール代数
• 有界集合
• 束 (数学)
• 順序論

参考文献

初期のコンピュータ時代には多くの入門的なブール代数のテキストが出版された。そのなかで最も優れており、今なお入手可能なものとして以下が挙げられる。

• Mendelson, Elliot, 1970. Schaum's Outline of Boolean Algebra. McGraw–Hill.

以下の文献は二元ブール代数が数学的に非自明であることを明らかにしている。

• スタンフォード哲学百科事典: "The Mathematics of Boolean Algebra," by J. Donald Monk.
• Burris, Stanley N., and H.P. Sankappanavar, H. P., 1981. A Course in Universal Algebra. Springer-Verlag. テンプレート:ISBN.