ブール代数の標準的な定義

ブール代数は 2 つの値の方程式理論のモデルです。この定義は、格子と環の定義と同等です。

ブール代数は、抽象代数の数学的に豊かな分野です。スタンフォード哲学百科事典では、ブール代数を「文的接続詞のみを持つ2値論理の代数、またはそれと同等の、和集合と補集合の代数の代数」と定義しています。^[1]群論が群を、線型代数がベクトル空間を扱うのと同じように、ブール代数は、2つの値0と1の方程式理論のモデルです（その解釈は数値的である必要はありません）。ブール代数、群、ベクトル空間に共通するのは、代数構造、つまり特定の方程式を満たすいくつかの演算の下で閉じた集合の概念です。^[2]

整数の群やn個のオブジェクトの順列の対称群S _{n など}のグループの基本的な例があるように、次のようなブール代数の基本的な例もあります。 ${\displaystyle \mathbb {Z} }$

• 論理和、論理積、否定などの論理演算による2進数またはビット 0 と 1 の代数。応用分野には命題計算やデジタル回路の理論などがあります。
• 和集合、積集合、補集合を含む集合演算による集合の代数。集合論は数学の標準的な基礎であるため、その応用範囲は広範囲にわたります。

したがって、ブール代数は抽象代数の手法を数理論理学やデジタル論理に適用することを可能にします。

有限位数の群は複雑性と多様性を示し、その一階理論は特殊な場合にのみ決定可能ですが、それとは異なり、すべての有限ブール代数は同じ定理を共有し、決定可能な一階理論を持ちます。代わりに、ブール代数の複雑さは、無限代数の構造とその構文構造のアルゴリズムの複雑さに分かれています。

ブール代数は、ブールプロトタイプと呼ばれる最大2要素有限代数の方程式理論と、ブール代数と呼ばれるその理論のモデルを扱います。^[3]これらの用語は次のように定義されます。

代数は、代数の基礎集合と呼ばれる集合に対する演算の 集合です。ブールプロトタイプの基礎集合を {0,1} とします。

代数は、その各演算が有限個の引数のみを取る場合、有限代数です。プロトタイプでは、演算の各引数は0または1 のいずれかであり、演算の結果も同様です。このような代数の最大値は、{0,1} 上のすべての有限演算で構成されます。

各演算で取られる引数の数は、演算の引数数と呼ばれます。引数数nの {0,1} に対する演算、つまりn項演算は、 n 個の引数の2 ^{n 個}の可能な値のいずれかに適用できます。引数の選択ごとに、演算は0または1 を返すため、 2 ^{2 n} n項演算 が存在します。

したがって、プロトタイプには、ゼロ項演算またはヌル項演算と呼ばれる、引数を取らない 2 つの演算、つまり 0 と 1 があります。単項演算は 4 つあり、そのうち2つは定数演算、もう 1 つは恒等演算、最もよく使用される演算は否定と呼ばれ、引数の反対を返します ( 0 の場合は1、1の場合は0 )。2項演算は 16 個あり、やはり 2 つは定数、もう 1 つは最初の引数を返し、さらにもう 1 つは 2 番目の引数を返します。1 つは結合と呼ばれ、両方の引数が 1 の場合は 1 を返し、それ以外の場合は 0 を返します。もう 1 つは分離と呼ばれ、両方の引数が 0 の場合は 0 を返し、それ以外の場合は 1 を返します。以下同様に続きます。プロトタイプの( n +1)項演算の数は、 n項演算の数の 2 乗であるため、3 項演算は16 ² = 256 個、4 項演算は256 ² = 65,536 個、というようになります。

族はインデックスセットによってインデックス付けされる。代数を形成する演算の族の場合、インデックスは演算記号と呼ばれ、その代数の言語を構成する。各記号によってインデックス付けされる演算は、その記号の表示または解釈と呼ばれる。各演算記号は、その解釈のアリティを指定するため、記号のすべての可能な解釈は同じアリティを持つ。一般に、代数は異なる記号を同じ演算で解釈することができるが、プロトタイプの場合はそうではなく、その記号はその演算と一対一で対応する。したがって、プロトタイプには2 ^{2 n} n項演算記号があり、これらはブール演算記号と呼ばれ、ブール代数の言語を形成する。否定を表す¬、論理積を表す∧、論理和を表す∨など、慣用的な記号を持つ演算はごくわずかである。^{[4]真理値表のセクションで後述するように、} i番目のn項記号をⁿ f _iと見なすと便利である。

特定の言語における方程式理論は、その言語の記号を使用して変数から構築された項間の方程式で構成されます。ブール代数言語の一般的な方程式は、 x ∧ y = y ∧ x、x ∧ x = x、x ∧¬ x = y ∧¬ y、およびx ∧ y = xです。

代数は、演算記号がその代数で指定されたとおりに解釈されるときに、その代数内の変数のすべての可能な値に対して方程式が成り立つとき、方程式を満たします。ブール代数の法則は、プロトタイプによって満たされるブール代数の言語の方程式です。上記の例の最初の 3 つはブール法則ですが、1∧0 ≠ 1であるため、4 番目はブール法則ではありません。

代数の方程式理論は、代数が満たすすべての方程式の集合です。したがって、ブール代数の法則はブール原型の方程式理論を構成します。

理論のモデルは、理論の言語で演算記号を解釈し、理論の方程式を満たす代数です。

ブール代数は、ブール代数の法則のモデルです。

つまり、ブール代数とは、ブール演算記号を解釈し、ブールプロトタイプと同じ法則を満たす集合とその上の演算族である。^[5]

代数のホモログをその代数の方程式理論のモデルとして定義すると、ブール代数はプロトタイプの任意のホモログとして定義できます。

例 1。ブールプロトタイプはブール代数です。なぜなら、それはそれ自身の法則を自明に満たしているからです。したがって、これはプロトタイプのブール代数です。定義が循環的になるのを避けるために、最初はそれをそのように呼びませんでした。

演算はすべて明示的に記述する必要はありません。基底とは、残りの演算を合成によって取得できる任意の集合です。「ブール代数」は、いくつかの異なる基底のいずれかから定義できます。ブール代数の基底として一般的に使用されているのは、格子基底、環基底、およびシェファー ストロークまたは NAND 基底の 3 つです。これらの基底は、それぞれ論理的、算術的、および簡潔な特性を対象に加えます。

• 格子基底は、論理的思考プロセスの代数的形式化を模索したブール、パースらの研究によって 19 世紀に始まりました。
• 環基底は20世紀にジェガルキンとストーンの研究で登場し、抽象代数学のバックグラウンドを持つ代数学者が好んで用いる基底となった。ブール代数の扱いのほとんどは格子基底を前提としているが、注目すべき例外はハルモス[1963]で、彼は明らかに線型代数学のバックグラウンドから環基底に魅了されていた。^[6]
• {0,1} 上のすべての有限演算はシェファーストロークNAND (またはそのデュアル NOR)に基づいて定義できるため、結果として得られる経済的な基底は、デジタル回路、特にデジタル電子機器のゲートアレイを解析するための選択の基底となっています。

格子基底と環基底の共通要素は、定数 0 と 1、結合的 可換 二項演算で、格子基底ではmeet x ∧ y、環基底では乗算 xy と呼ばれます。この区別は用語上のものです。格子基底には、さらにjoin、x ∨ y、およびcomplement、¬ xという演算があります。環基底には、代わりに加算の算術演算x ⊕ y があります ( + には join のブール読みが与えられることがあるため、 記号⊕が+よりも優先して使用されます)。

基底であるということは、他のすべての演算を合成によって生み出すことであり、したがって任意の 2 つの基底は相互に変換可能でなければなりません。格子基底は、 x ∨ y を環基底に x ⊕ y ⊕ xy として、 ¬ x を x ⊕1 として変換します。逆に、環基底はx ⊕ yを格子基底に( x ∨ y ) ∧¬ ( x ∧ y )として変換します。

これら両方の基底により、ブール代数はブール演算の等式特性のサブセットを介して定義できます。 格子基底の場合、ブール代数をx ∧¬ x = 0およびx ∨¬ x = 1 を満たす分配格子として定義するだけで十分です。これは補分配格子と呼ばれます。 環基底はブール代数をブール環、つまりx ² = x を満たす環に変換します。

エミール・ポストは、演算のセットが非ゼロのブール演算の基底となるための必要十分条件を示した。非自明な特性とは、基底を構成する演算の一部に共有されるが、すべての演算に共有されるわけではない特性である。ポストは、5 つのポストのクラスで識別可能で、それぞれが合成によって保持される演算の 5 つの非自明な特性をリストし、各特性について、そのセットにその特性を持たない演算が含まれる場合、演算のセットが基底を形成することを示した。(ポストの定理の逆、つまり「 の場合」を「の場合に限り」に拡張すると、候補基底のすべての演算が成り立つこれら 5 つの特性のうちの 1 つが、その候補から合成されたすべての演算も成り立つという簡単な観察となり、その特性の非自明性により、候補は基底ではなくなる。) ポストの 5 つの特性は以下のとおりである。

• 単調、0-1 入力遷移によって 1-0 出力遷移が発生することはありません。
• アフィン、双線型項または高次の項を持たないZhegalkin 多項式で表現可能（例：x ⊕ y ⊕1だがxyではない） 。
• 自己双対なので、 x、または中央値演算子 xy ⊕ yz ⊕ zx、またはそれらの否定のように、すべての入力を補完すると出力が補完されます。
• 厳密（すべてゼロの入力をゼロにマッピングします）
• costrict (すべて 1 を 1 にマッピング)。

NAND (デュアル NOR) 演算にはこれらすべてが欠けているため、それ自体が基礎を形成します。

{0,1} に関する有限演算は、0 と 1 を真理値falseとtrueと考えると、真理値表として表すことができます。^[7]これらは、アプリケーションに依存しない統一された方法で配置することができ、個別に名前を付けたり、少なくとも番号を付けたりすることができます。^{[8]これらの名前は、ブール演算の便利な省略形を提供します。} n項演算の名前は、 2 ⁿビットの 2 進数です。このような演算は2 ^{2 n}通りあるため、これ以上簡潔な命名法は考えられません。各有限演算はスイッチング関数と呼ぶことができることに注意してください。

このレイアウトと関連する演算の命名が、0 から 2 までの引数について完全にここに示されています。

これらの表は、より高い引数で継続され、引数nで2 ⁿ行となり、各行はn変数x ₀、... x _{n −1の評価またはバインディングを示し、} ⁿ f _iという見出しの各列は、その評価でのi番目のn引数演算の値ⁿ f _i ( x ₀、...、x _{n −1} )を示します。演算には変数が含まれます。たとえば、¹ f _{2 は}x ₀ですが、² f ₁₀はx ₀ (単項演算の 2 つのコピーとして)、² f _12はx ₁ (単項演算なし)です。否定または補数¬ x _{0 は}¹ f ₁として、また² f _{5として現れ、} ² f ₃ ( ¬ x ₁、これはアリティ 1 には現れなかった)とともに現れ、選言または和集合x ₀ ∨ x ₁は² f ₁₄、連言または積集合x ₀ ∧ x ₁は² f ₈、含意x ₀ → x _1は² f ₁₃、排他的論理和対称差x ₀ ⊕ x ₁ は² f ₆、集合差x ₀ − x _1は² f ₂、など として現れます。

内容よりも形式の方が重要な細かい点として、代数の演算は伝統的にリストとして整理されます。ここではブール代数の演算を {0,1} の有限演算でインデックスしていますが、上記の真理値表の表現では、まず演算をアリティで、次に各アリティの表のレイアウトで順序付けています。これにより、すべてのブール演算のセットを従来のリスト形式で整理できます。特定のアリティの演算のリスト順序は、次の 2 つの規則によって決まります。

(i)表の左半分のi番目の行は、最下位ビットまたは0番目のビットが左側にあるiのバイナリ表現です (「リトルエンディアン」順序は、もともとアランチューリングによって提案されたため、チューリング順序と呼んでも不合理ではありません)。

(ii)表の右半分のj番目の列は、 jのバイナリ表現であり、これもリトルエンディアン順です。実際には、演算の添え字はその演算の真理値表です。計算可能関数のゲーデル番号付けと類似して、ブール演算のこの番号付けをブール番号付けと呼ぶこともできます。

CやJavaでプログラミングする場合、ビット論理和は次のように表されます。x | y、接続詞xとy、および否定~ ×したがって、プログラムはこれらの言語で例えばx∧ ( y∨z )という演算を次のように表現できる。x &( y | z ) の、以前に設定したx  = 0xaa、y  = 0xcc、 そして 0xf0 の倍数（「0x" は、次の定数が 16 進数または基数 16 で読み取られることを示します。これは、変数に割り当てるか、マクロとして定義することによって行われます。これらの 1 バイト (8 ビット) の定数は、上記の表を 3 つの変数に拡張した場合の入力変数の列に対応します。この手法は、ラスター グラフィックス ハードウェアでほぼ普遍的に使用されており、画像を結合およびマスクするさまざまな方法を柔軟に提供します。一般的な操作は 3 値であり、ソース ビット、宛先ビット、およびマスク ビットに対して同時に作用します。

例 2。与えられた長さのすべてのビット ベクトルは「点ごとに」ブール代数を形成します。つまり、任意のn項ブール演算をnビット ベクトルの 1 ビット位置ごとに適用できます。たとえば、それぞれ長さ 4 の 3 つのビット ベクトルの 3 項 OR は、4 つのビット位置のそれぞれで 3 ビットを OR して形成される長さ 4 のビット ベクトルであり、したがって0100∨1000∨1001 = 1101です。もう 1 つの例は、上記のn項演算の真理値表です。この表の列はすべて長さ2 ⁿのビット ベクトルであり、したがって点ごとに組み合わせることができ、n項演算はブール代数を形成します。^[9] これは有限長と無限長のビット ベクトルに対して同様に機能します。唯一のルールは、「対応する位置」が明確に定義されるように、すべてのビット位置が同じセットでインデックス付けされることです。

このような代数のアトムは、正確に 1 つの 1 を含むビット ベクトルです。一般に、ブール代数のアトムは、x ∧ y がxまたは0の2 つの値のみを持つような要素xです。

例 3。 べき集合代数、与えられた集合Wのすべての部分集合の集合2 ^W。^[10]これは例 2 を変形したもので、Wはビット位置のインデックスとして機能します。Wの任意の部分集合X は、 Xの要素によってインデックスされたビット位置にのみ 1 を持つビットベクトルとして見ることができます。したがって、すべてゼロのベクトルはWの空の部分集合であり、すべて 1 のベクトルはW自体であり、これらはそれぞれべき集合代数の定数 0 と 1 です。選言x ∨ yに対応するものは和集合X ∪ Yであり、連言x ∧ yに対応するものは積集合X ∩ Yです。否定¬ x はWに対する補集合である~ Xになります。集合差X \ Y  = X ∩~ Y、対称差( X \ Y )∪( Y \ X )、三元和X ∪ Y ∪ Zなども存在します。ここでのアトムはシングルトン、つまり要素が 1 つだけのサブセットです。

例 2 と 3 は、ブール代数だけでなく、群、環などを含むすべての種類の代数に適用できる、直積と呼ばれる一般的な代数の構成要素の特殊なケースです。 iが何らかの添字集合I (必ずしも有限または可算ではない)にわたるブール代数の任意の族B _{iの直積は、} i番目の要素がB _iから取られるすべてのI組(... x _i、...)で構成されるブール代数です。直積の演算は、それぞれの座標内で作用する構成代数の対応する演算です。特に、積の演算ⁿ f _jは、 I内のすべてのiに対して、 B _iの演算ⁿ f _jをn組のi番目の座標にあるn要素に適用することにより、n I組に作用します。

このように掛け合わせた代数がすべて同じ代数Aである場合、その直積をAの直累乗と呼びます。すべての 32 ビット ビット ベクトルのブール代数は、2 要素ブール代数の 32 乗、つまり 32 要素セットのべき集合代数であり、2 ³²と表記されます。すべての整数セットのブール代数は2 ^Zです。これまでに示したブール代数はすべて、2 要素ブール代数の直累乗であり、「べき集合代数」という名前にふさわしいものです。

すべての有限ブール代数は、何らかのべき集合代数と同型であることが示されます。 ^[11]したがって、有限ブール代数の濃度（要素の数）は2のべき乗、つまり1、2、4、8、...、2n ^、 ...のいずれかです。これは、有限ブール代数をべき集合代数として表現することにより、有限ブール代数の性質を理解するのに役立つため、表現定理と呼ばれます。

この表現定理は無限ブール代数には拡張されません。すべての冪集合代数はブール代数ですが、すべてのブール代数が冪集合代数と同型である必要はありません。特に、可算無限冪集合代数は存在しませんが (最小の無限冪集合代数は自然数の集合の冪集合代数2 ^Nであり、カントールによって無数であることが示されています)、さまざまな可算無限ブール代数が存在します。

冪集合代数を超えるには、別の構成が必要です。代数Aの部分代数とは、 Aの演算に関して閉じたAの任意の部分集合です。ブール代数Aのすべての部分代数は、 Aが保持する方程式を満たしている必要があります。これは、違反があればA自体の違反となるためです。したがって、ブール代数のすべての部分代数はブール代数です。^[12]

冪集合代数の部分代数は集合体と呼ばれる。同様に、集合体とは、空集合とWを含むある集合Wの部分集合の集合であり、 Wに関して有限和と有限補集合の下で閉じている（したがって有限積の下でも閉じている）。ブール代数に対するバーコフ [1935] の表現定理は、すべてのブール代数は集合体に同型であると述べている。多様体に対するバーコフの HSP 定理は、代数クラスCの等式理論のモデルのすべてのクラスは、 Cの代数の直積の部分代数の準同型像であると述べることができる。通常は H、S、P の 3 つすべてが必要であるが、これら 2 つのバーコフの定理の最初のものが示すのは、ブール代数多様体の特殊なケースでは、準同型性は同型性で置き換えられるということである。したがって、一般の多様体に対するバーコフの HSP 定理は、ブール代数多様体に対するバーコフの ISP 定理になります。

自然数の集合Xについて語るときは、それをビットの列x ₀、x ₁、x ₂、...とみなすと便利である。ここで、 x _i  = 1となるのはi ∈ Xの場合のみである。この観点により、冪集合代数2 ^Nの部分代数について語ることが容易になり、この観点により、この部分代数はすべてのビット列のブール代数となる。^[13]これは真理値表の列にもよく当てはまる。列を上から下に読むと、ビットの列が構成されるが、同時に、その列で表される関数が 1 に評価される値 (表の左半分の変数への割り当て) の集合として見ることもできる。

例 4。究極的に定数なシーケンス。究極的に定数なシーケンスのブール結合はどれも究極的に定数であるため、これらはブール代数を形成します。究極的にゼロのシーケンスを非負の 2 進数 (シーケンスのビット0が下位ビット) と見なし、究極的に 1 のシーケンスを負の 2 進数 (すべて 1 のシーケンスが−1である2 の補数演算を考えてみます) と見なすことで、これらを整数と同一視できます。これにより、整数はブール代数になり、和集合はビット単位の OR で、補集合は−x−1になります。整数は可算個しかないため、この無限ブール代数は可算です。アトムは 2 の累乗、つまり 1、2、4、... です。この代数を別の方法で記述すると、自然数の有限集合と余有限集合の集合となり、究極的にすべて 1 のシーケンスは余有限集合に対応し、それらの集合からは有限個の自然数のみが省略されます。

例 5。周期的数列。ある数列が周期的であるとは、周期性の証拠と呼ばれる数n > 0が存在し、すべてのi ≥ 0に対してx _i  = x _{i + n が}成り立つときです。周期的数列の周期はその最小の証拠です。否定は周期を変えませんが、2 つの周期的数列の論理和は周期的であり、周期は最大でも 2 つの引数の周期の最小公倍数になります (任意の数列とその補数の和の場合と同様に、周期は1まで小さくなることがあります)。したがって、周期的数列はブール代数を形成します。

例 5 は可算であるという点で例 4 に似ていますが、原子がないという点で異なります。後者は、任意の非ゼロ周期シーケンスx と互いに素な周期 (1 より大きい) のシーケンスとの結合が0でもxでもないためです。すべての可算無限の原子のないブール代数は同型であることが示されます。つまり、同型性を除いて、そのような代数は 1 つしかありません。

例 6。周期が 2 のべき乗である周期列。これは例 5 の適切な部分代数です(適切な部分代数は、それ自身とその代数の共通部分に等しい)。これらは有限演算として理解でき、そのような列の最初の周期は、それが表す演算の真理値表を示します。たとえば、2 項演算の表にあるx _{0の真理値表、つまり}² f ₁₀は、 2 項演算のうち 12 個が周期4であるにもかかわらず、周期2です(したがって、最初の変数のみを使用していると認識できます) 。周期が2 ⁿのとき、演算は最初のn 個の変数のみに依存し、その意味で演算は有限です。この例は、可算無限の原子のないブール代数でもあります。したがって、例 5 は、それ自身の適切な部分代数と同型です。例 6、つまり例 5 は、可算な数のジェネレータ上の自由ブール代数を構成します。つまり、可算無限個のジェネレータまたは変数の集合上のすべての有限演算のブール代数を意味します。

例 7。究極的に周期的なシーケンス、つまり、最初の有限の不法行為の後に周期的になるシーケンス。これらは、例 5 の適切な拡張 (つまり、例 5 は例 7 の適切な部分代数) を構成し、また、定数シーケンスが周期 1 で周期的であるため、例 4 の適切な拡張を構成します。シーケンスが落ち着くタイミングは異なる場合がありますが、シーケンスの有限セットはすべて、最も遅く落ち着くメンバーよりも遅くないうちに最終的に落ち着きます。したがって、最終的に周期シーケンスはすべてのブール演算に対して閉じており、ブール代数を形成します。この例は、例 4 と同じアトムとコアトムを持っているため、アトムレスではなく、したがって例 5/6 と同型ではありません。ただし、無限のアトムレス部分代数、つまり例 5 が含まれているため、例 4 と同型ではありません。そのすべての部分代数は、有限セットとその補集合のブール代数でなければならず、したがってアトミックです。この例は例 4 と例 5 の直積と同型であり、別の説明を提供します。

例 8。周期列 (例 5) と任意の有限だが自明でないブール代数の直積。(自明な 1 要素ブール代数は、唯一の有限な原子なしブール代数です。) これは、原子と原子なし部分代数の両方を持つ点で例 7 に似ていますが、原子の数が有限である点が異なります。例 8 は、実際には、原子の可能な有限数ごとに 1 つずつ、無限の例の族です。

これらの例は、ブール代数、さらには可算な代数も含め、すべての可能なブール代数を網羅しているわけではありません。実際、非同型の可算ブール代数は無数に存在し、Jussi Ketonen [1978] はこれを、特定の遺伝的可算集合によって表現可能な不変量の観点から完全に分類しました。

n項ブール演算自体は、 W がn 個の入力の2 ^{n 個}の評価の集合であるとすると、べき集合代数2 ^{W を構成します。演算の命名システムn} f _iに関して、バイナリのiは真理値表の列であり、列は任意の項数のブール演算と組み合わせて、表にある他の列を生成することができます。つまり、任意のm個の項数のブール演算をm個の項数のブール演算nに適用して、任意のmおよびnに対して項数nのブール演算を生成できます。

ソフトウェアとハ​​ードウェアの両方にとってこの規則の実際的な意義は、n項ブール演算を適切な長さのワードとして表現できることです。たとえば、256 個の 3 項ブール演算はそれぞれ、符号なしバイトとして表現できます。AND や OR などの利用可能な論理演算を使用して、新しい演算を作成できます。x、y、z を（今は添え字付き変数は省略して）それぞれ10101010、11001100、11110000（10 進数では 170、204、240、16 進数では0xaa、0xcc、0xf0 ）とすると、それらの対の論理積はx ∧ y  = 10001000、y ∧ z  = 11000000、z ∧ x  = 10100000となり、それらの対の論理和はx ∨ y  = 11101110、y ∨ z  = 11111100、z ∨ x  = 11111010となります。 3つの連言の論理和は11101000であり、これは3つの連言の論理和でもある。したがって、バイトに対する12回ほどの論理演算で、2つの3項演算が

${\displaystyle (x\land y)\lor (y\land z)\lor (z\land x)}$

そして

${\displaystyle (x\lor y)\land (y\lor z)\land (z\lor x)}$

は実際には同じ操作です。つまり、等式恒等式が証明されました。

${\displaystyle (x\land y)\lor (y\land z)\lor (z\land x)=(x\lor y)\land (y\lor z)\land (z\lor x)}$、

2 要素ブール代数の場合。「ブール代数」の定義により、この恒等式はすべてのブール代数で成立するはずです。

偶然にも、この三項演算は Grau [1947] の三項ブール代数の基礎となり、彼はこの演算と否定を用いて三項ブール代数を公理化した。この演算は対称的である。つまり、その値は引数の3! = 6通りの順列のいずれにも依存しない。その真理値表11101000の両半分は、 ∨、1110と∧、1000の真理値表なので、この演算は、if z then x ∨ y else x ∧ y と表現できる。 対称 的 であるため 、 if x then y ∨ z else y ∧ z としても、 if y then z ∨ x else z ∧ xとしても同じように表現できる。 8 頂点 3 次元立方体のラベル付けとして見ると、上半分は 1、下半分は 0 とラベル付けされます。このため、これは中央値演算子と呼ばれ、任意の奇数の変数に一般化できることが明白です (奇数なのは、ちょうど半分の変数が 0 になるという同点を避けるためです)。

ブール代数の恒等式を証明するために使用した手法は、ブール論理の等式法則の健全かつ完全な公理化、または公理システムとして捉えられる体系的な方法で、すべての恒等式に一般化できます。公理システムの慣例的な定式化は、いくつかの初期恒等式で「ポンプを始動させる」公理のセットと、公理および以前に証明された恒等式から残りの恒等式を推論するための推論規則のセットで構成されます。原則として、公理の数は有限であることが望ましいですが、実際問題として、それは必須ではありません。なぜなら、証明に使用されたときにそれぞれが正当なインスタンスであることが容易に検証できる、無限の数のインスタンスを持つ有限公理スキーマを持つことも同様に効果的であり、ここで採用しているアプローチです。

ブール恒等式は、 s  = tという形式の表明です。ここで、sとt はn項であり、ここでは変数がx ₀からx _n-1までに制限されている項を意味します。n項は、アトムまたはアプリケーションのいずれかです。アプリケーション^m f _i ( t ₀ ,..., t _{m -1} )は、 m項演算^m f _iと、オペランドと呼ばれるm個のn項のリストまたはmタプル( t ₀ ,..., t _{m -1} )で構成されるペアです。

各項には、その高さと呼ばれる自然数が関連付けられています。アトムの高さはゼロですが、アプリケーションの高さは 1 に最高位のオペランドの高さを加えた値になります。

では、アトムとは何でしょうか。慣例的に、アトムは定数 (0 または 1) または変数x _i (0 ≤ i < n)のいずれかです。ここでの証明手法では、アトムをn項演算ⁿ f _iとして定義すると便利です。ここではアトムとして扱われますが、正確な形式ⁿ f _i ( x ₀ ,..., x _{n -1} )の通常の項と同じ意味を持ちます(変数は、繰り返しや省略なく、示された順序でリストする必要があるという点で正確です)。これは制限ではありません。なぜなら、この形式の原子には、通常の原子、つまり定数 0 と 1 がすべて含まれ、これらは各nに対してn項演算ⁿ f ₀とⁿ f ₋₁ ( 2 ^{2 n} −1を−1に省略) として現れます。また、変数x ₀、...、x _{n -1}も含まれ、真理値表を見ると、x _{0 は}単項演算¹ f ₂と二項演算² f ₁₀の両方として現れ、x _{1 は}² f ₁₂として現れます。

次の公理スキーマと 3 つの推論規則は、 n項 のブール代数を公理化します。

A1 . ^m f _i ( ⁿ f _{j 0} ,..., ⁿ f _{j m -1} ) = ⁿ f _{i o ĵ}ただし( i o ĵ ) _v  = i _{ĵ v}であり、ĵ はj転置で、 ( ĵ _v ) _u  = ( j _u ) _vで定義されます。

R1 . 前提がない場合、t  = tと推論します。

R2 . s  = uおよびt  = uからs  = t を推論します。ここでs、t、およびuはn項です。

R3 . s ₀  = t ₀  , ... ,  s _{m -1}  = t _{m -1から、} ^m f _i ( s ₀ ,..., s _{m -1} ) = ^m f _i ( t ₀ ,..., t _{m -1} )が推論されます。ここで、すべての項s _i、t _iはn項です。

A1の副次条件の意味は、i o ĵは、 v番目のビットがiのĵ _v番目のビットである2 ⁿビットの数であり、各量の範囲はu : m、v : 2 ⁿ、j _u : 2 ^{2 n}、およびĵ _v : 2 ^mであるということです。(したがって、jは2 ⁿビットの数のm組であり、 jの転置である ĵ はmビットの数の2 ⁿ組です。したがって、 jとĵの両方にm 2 ⁿビット が含まれます。)

A1 は、メタ変数、つまりm、i、n、およびj ₀からj _m-1を含むため、公理ではなく公理スキーマです。公理化の実際の公理は、メタ変数を特定の値に設定することで得られます。たとえば、m  = n  = i  = j ₀  = 1とすると、 i ₁  = 0およびi ₀  = 1からi o ĵの 2 ビットを計算できるため、i o ĵ  = 2 (または、 2 ビット数として記述する場合は10 ) になります。結果のインスタンス、つまり¹ f ₁ ( ¹ f ₁ ) = ¹ f _{2 は}、二重否定のよく知られた公理¬¬ x  = xを表します。規則R3により、s ₀を¹ f ₁ ( ¹ f ₁ )または¬¬ x ₀、t ₀を¹ f ₂またはx ₀、^m f _{i を}¹ f ₁または¬とすることで、¬¬¬ x  = ¬ x を推論できます。

各mとnに対して、 A1をインスタンス化する公理は有限個、つまり2 ^{2 m} × (2 ^{2 n} ) ^mしかありません。各インスタンスは2 ^m + m 2 ⁿビットで指定されます。

R1は前提を持たない点で公理に似ていますが、推論規則として扱います。なぜなら、 R1 は、群、環、またはその他の種類のすべての等式公理化に共通するR2およびR3とともに、ドメインに依存しない規則だからです。ブール代数に固有の唯一のエンティティは、公理スキーマA1です。このようにして、さまざまな等式理論について話すときに、規則を特定の理論から独立しているものとして脇に押しやり、特定の等式理論を特徴付ける公理システムの唯一の部分として公理に注意を向けることができます。

この公理化は完全であり、すべてのブール法則s  = tはこのシステムで証明可能であることを意味します。まず、sの高さに関する帰納法によって、 tがアトミックであるすべてのブール法則が証明可能であることが示されます。これには、基本ケースにR1 (異なるアトムが等しくなることはないため)、帰納ステップ ( s の適用)にA1とR3 を使用します。この証明戦略は、 s を評価してアトムを生成する再帰的手順になります。次に、 t が適用である可能性のある一般的なケースでs  = t を証明するには、 s  = tが恒等式である場合にsとt は同じアトムに評価される必要があるという事実を使用し、これをuと呼びます。したがって、まず上記のようにs  = uおよびt  = u を証明します。つまり、 A1、R1、およびR3 を使用してsとt を評価し、次にR2 を呼び出してs  = t を推論します。

A1で、数n ^{m を}関数型m → n、m _{n を}適用m ( n )と見なすと、数i、j、ĵ、およびi o ĵを、型i : ( m →2)→2、j :  m →(( n →2)→2)、ĵ : ( n →2)→( m →2)、およびi o ĵ : ( n →2 )→2の関数として再解釈できます。すると、 A1の定義( i o ĵ ) _v  = i _{ĵ v}は、 ( i o ĵ )( v ) = i ( ĵ ( v ))に変換されます。つまり、 i o ĵは、関数として理解されるiとĵの合成として定義されます。したがって、 A1の内容は、mタプルj を転置して型を合成に適切に一致させる必要があることを除けば、項適用を本質的に合成として定義することに相当します。この合成は、Lawvere が以前に述べたべき集合とその関数のカテゴリの合成です。このようにして、ブール代数の等式理論としてのそのカテゴリの可換図を、その特定の合成法則の論理的表現としてのA1の等式の結果に変換しました。

すべてのブール代数Bの基礎となるのは、半順序集合またはposet ( B ,≤)です。半順序関係は、 x  = x ∧ yのとき、またはそれと同等にy  = x ∨ yのとき、 x ≤ yによって定義されます。ブール代数の要素の集合Xが与えられた場合、 Xの上限は、Xのすべての要素xに対してx ≤ yとなる要素yであり、 Xの下限は、Xのすべての要素xに対してy ≤ xとなる要素yです。

XのsupはXの最小上限、つまりXのすべての上限と等しいかそれ以下のXの上限です。双対的に、XのinfはXの最大下限です。 xとyの sup は、ブール代数の基になる poset に常に存在し、x ∨ yとなり、同様に inf も存在し、つまりx ∧ yとなります。空の sup は 0 (一番下の要素) で、空の inf は 1 (一番上の要素) です。したがって、すべての有限集合には sup と inf の両方が存在します。ブール代数の無限部分集合には、sup や inf がある場合とない場合があります。冪集合代数では常に存在します。

すべての要素x、yのペアが sup と inf の両方を持つような任意の poset ( B、≤)は、 latticeと呼ばれます。supはx ∨ y 、inf はx ∧ yと書きます。ブール代数の基礎となる poset は常に lattice を形成します。x ∧ ( y ∨ z ) = ( x ∧ y )∨( x ∧ z )、または同等にx ∨( y ∧ z ) = ( x ∨ y )∧( x ∨ z )のとき、格子は分配的であると言われます。これは、格子ではどちらかの法則が他方を意味するためです。これらはブール代数の法則であり、ブール代数の基礎となる poset は分配格子を形成します。

ボトム要素 0 とトップ要素 1 を持つ格子が与えられたとき、要素のペアx、y は、 x ∧ y  = 0かつx ∨ y  = 1 のときに相補的であると呼ばれ、 y はxの補集合であると言われ、その逆も同様です。上部と下部を持つ分配格子の任意の要素x は、最大で 1 つの補集合を持つことができます。格子のすべての要素に補集合がある場合、その格子は相補的であると呼ばれます。したがって、相補分配格子では、要素の補集合が常に存在し、一意であるため、相補は単項演算になります。さらに、すべての相補分配格子はブール代数を形成し、逆にすべてのブール代数は相補分配格子を形成します。これにより、ブール代数の別の定義、つまり任意の相補分配格子としての定義が提供されます。これら 3 つの特性はそれぞれ有限個の方程式で公理化することができ、これらの方程式を合わせるとブール代数の方程式理論の有限公理化が構成されます。

一連の方程式のすべてのモデルとして定義される代数のクラスでは、通常、クラスの代数が、クラスに適格となるために必要な方程式よりも多くの方程式を満たします。ブール代数のクラスは、1 つの例外を除いて、すべてのブール代数がブール恒等式を正確に満たし、それ以上は満たさないという点で異なります。例外は 1 要素ブール代数で、これは必然的にすべての方程式 ( x  = yも含む) を満たすため、矛盾したブール代数と呼ばれることがあります。

ブール準同型とは、ブール代数A、B間の関数h : A → Bであり、任意のブール演算^m f _iに対して次のようになる。

$${\displaystyle h(^{m}\!f_{i}(x_{0},...,x_{m-1}))={}^{m}\!f_{i}(h(x_{0},...,x_{m-1}))}$$

ブール代数のカテゴリBool は、 すべてのブール代数をオブジェクトとして持ち、それらの間のブール準同型を射として持ちます。

2 要素ブール代数2からあらゆるブール代数への一意の準同型が存在します。これは、準同型では 2 つの定数が保存される必要があり、それらが2の唯一の要素であるためです。この特性を持つブール代数は初期ブール代数と呼ばれます。任意の 2 つの初期ブール代数は同型であることが示され、したがって同型2までは初期ブール代数です。

反対方向には、ブール代数Bから2への準同型が多数存在する可能性があります。そのような準同型はいずれも、B を1 にマップされる要素と 0 にマップされる要素に分割します。前者で構成されるBのサブセットは、Bのウルトラフィルターと呼ばれます。Bが有限の場合、そのウルトラフィルターはその原子とペアになります。つまり、1 つの原子は 1 にマップされ、残りは 0 にマップされます。したがって、 Bの各ウルトラフィルターは、 Bの原子とその上のすべての要素で構成されます。したがって、Bの要素のちょうど半分がウルトラフィルターに含まれ、原子の数と同じ数のウルトラフィルターが存在します。

無限ブール代数の場合、超フィルターの概念は、かなり繊細になります。原子以上の要素は常に超フィルターを形成しますが、他の多くの集合も同様です。たとえば、整数の有限集合と余有限集合のブール代数では、余有限集合は、そのいずれも原子ではないにもかかわらず、超フィルターを形成します。同様に、整数のべき集合には、その超フィルターの中に、特定の整数を含むすべての部分集合の集合があります。これらの「標準」超フィルターは可算数個あり、整数自体と同一視できますが、「非標準」超フィルターは、さらに無数に多くあります。これらは、非標準解析の基礎を形成し、無限小やデルタ関数などの古典的に矛盾するオブジェクトの表現を提供します。

ブール代数の基底となる半順序に関する上記のセクションの sup と inf の定義を思い出してください。完全ブール代数とは、すべての部分集合に sup と inf の両方があり、無限部分集合であってもその部分集合に含まれます。Gaifman [1964] とHales [1964] は、それぞれ独立して、無限自由完全ブール代数は存在しないことを示しました。 これは、有限演算の論理に無限に多くの項がある可能性があるのと同様に、セットサイズの無限演算の論理にクラス多数の項がある可能性があることを示唆しています。

ただし、無限ブール演算を導入する別の方法があります。ブール代数の定義から「有限」を単に削除するだけです。モデルの基数までのアリティ {0,1} のすべての演算の代数の方程式理論のモデルは、完全なアトミックブール代数、またはCABAと呼ばれます。(この厄介なアリティ制限の代わりに、任意のアリティを許可することもできますが、その場合、署名が任意のセット、つまり適切なクラスよりも大きくなるという別の厄介さにつながります。後者の方法の利点の 1 つは、異なる基数の CABA 間の準同型性の定義を簡素化することです。 ) このような代数は、アトミックな完全なブール代数として同等に定義できます。つまり、すべての要素は、何らかのアトムのセットの sup です。自由 CABA は、生成子の集合Vのすべての基数、つまり冪集合代数2 ^{2 V}に対して存在し、これは有限自由ブール代数の明らかな一般化です。これにより、無限ブール論理は、ガイフマン-ヘイルズの結果によって運命づけられたように思われた運命から、巧みに救出されます。

自由 完全ブール代数が存在しない理由は、ブール論理の方程式を無限連言と選言に当てはまるすべての法則に適切に拡張できなかったこと、特に完全ブール代数の定義で分配性を無視したことに起因します。完全ブール代数は、任意の連言が任意の選言に分配される場合、完全に分配的であると呼ばれ、その逆も同様です。ブール代数は、完全かつ完全に分配的である場合に限り CABA であり、これが CABA の 3 番目の定義となります。4 番目の定義は、冪集合代数と同型の任意のブール代数です。

完全準同型とは、有限の超集合だけでなく、存在するすべての超集合を保存するもので、無限集合についても同様です。すべての CABA とその完全準同型のカテゴリCABAは、集合とその関数のカテゴリと双対であり、つまり、そのカテゴリの反対（すべての射を逆にした結果のカテゴリ）に相当します。ブール代数とその準同型のカテゴリBoolについては、事態はそれほど単純ではありません。マーシャル・ストーンは、実際には（双対性を明確にするための言語と概念的枠組みの両方を欠いていましたが）完全に分離した コンパクト ハウスドルフ空間（後にストーン空間と呼ばれる）のカテゴリと双対であることを示しました。

ブール代数と完全ブール代数の中間にあるもう一つの無限クラスは、シグマ代数の概念です。これは完全ブール代数と同様に定義されますが、supとinfは可算なアリティに制限されます。つまり、シグマ代数は、すべての可算な sup と inf を持つブール代数です。sup と inf は有界な基数であるため、完全ブール代数の場合とは異なり、ガイフマン-ヘイルズの結果は適用されず、自由 シグマ代数が存在します。ただし、CABA の場合とは異なり、自由可算生成シグマ代数はべき集合代数ではありません。

ブール代数の定義は、2 要素代数の方程式理論のモデル、補完分配格子、ブール環、特定のカテゴリ (Lawvere) からの積保存関数など、すでにいくつか紹介しました。さらに、言及する価値のある定義を 2 つ紹介します。

ストーン（1936）

ブール代数は、位相空間のすべての閉開集合の集合です。空間が完全に分離したコンパクトなハウスドルフ空間、またはストーン空間である必要はありません。つまり、同型性を除いて、すべてのブール代数はこのようにして生じます。さらに、2 つのストーン空間の閉開集合として形成される 2 つのブール代数が同型である場合、ストーン空間自体も同型になりますが、任意の位相空間ではそうではありません。これは、ブール代数からストーン空間への前述の双対性の逆方向です。この定義は、次の定義によって具体化されます。

ジョンストン（1982）

ブール代数は、有限ブール代数のフィルタリングされた余極限です。

(この定義の循環性は、「有限ブール代数」を、冪集合に対して標準的に解釈されるブール演算を備えた「有限冪集合」に置き換えることによって解消できます。)

これを大局的に見ると、無限集合は有限集合のフィルターされた余極限として、無限 CABA は有限冪集合代数のフィルターされた極限として、無限ストーン空間は有限集合のフィルターされた極限として生じます。したがって、有限集合から始めて、これらが無限オブジェクトに一般化する方法を求める場合、2 つの方法があります。「追加」すると通常の集合または帰納的集合が得られ、「乗算」するとストーン空間またはプロ有限集合が得られます。有限冪集合代数には、有限集合の双対と同じ選択肢があります。つまり、加算すると帰納的オブジェクトとしてブール代数が得られ、乗算するとプロ有限オブジェクトとして CABA または冪集合代数が得られます。

特徴的な区別点は、そのように構築されたオブジェクトの基礎となる位相が、ハウスドルフとして定義される場合、帰納的オブジェクトに対しては離散的であり、プロ有限オブジェクトに対してはコンパクトであることです。有限ハウスドルフ空間の位相は常に離散的かつコンパクトですが、無限空間の場合、「離散的」と「コンパクト」は相互に排他的です。したがって、有限代数 (ブール代数だけでなく、あらゆる種類の) を無限代数に一般化する場合、「離散的」と「コンパクト」は分離し、どちらを保持するかを選択する必要があります。有限代数と無限代数の両方に対する一般的な規則は、有限代数は離散的であるのに対し、その双対はコンパクトで無限演算を特徴とすることです。これら 2 つの極端な状態の間には、位相が離散的でもコンパクトでもない中間の無限ブール代数が多数存在します。

• バーコフ、ギャレット( 1935)。「抽象代数の構造について」。ケンブリッジ哲学協会数学紀要。31 (4): 433–454。Bibcode  : 1935PCPS ...31..433B。doi : 10.1017/s0305004100013463。ISSN 0008-1981。S2CID 121173630  。
• ブール、ジョージ（2003）[1854]。思考の法則の調査。プロメテウスブックス。ISBN 978-1-59102-089-9。
• フィリップ・ドウィンガー (1971)。ブール代数の紹介。ヴュルツブルク：フィジカ・フェルラーク。
• ハイム、ガイフマン (1964)。 「無限ブール多項式、I」。数学の基礎。54 (3): 229–250。土井：10.4064/fm-54-3-229-250。ISSN  0016-2736。
• Givant, Steven; Halmos, Paul (2009)。『ブール代数入門』。『学部生向け数学テキスト』。Springer。ISBN 978-0-387-40293-2。
• Grau, AA (1947). 「三元ブール代数」. Bull. Am. Math. Soc . 33 (6): 567–572. doi : 10.1090/S0002-9904-1947-08834-0 .
• ヘイルズ、アルフレッド W. (1964)。「自由完全ブール代数の非存在について」。Fundamenta  Mathematicae。54 : 45–66。doi : 10.4064 / fm -54-1-45-66。ISSN 0016-2736。
• ハルモス、ポール(1963)。ブール代数に関する講義。ヴァン・ノストランド。ISBN 0-387-90094-2。
• ギヴァント、スティーブン、ハルモス、ポール (1998)。代数としての論理。ドルチアーニ数学解説。アメリカ数学協会。ISBN 978-0-883-85327-6。
• ジョンストン、ピーター T. (1982)。『Stone Spaces』ケンブリッジ、イギリス：ケンブリッジ大学出版局。ISBN 978-0-521-33779-3。
• ケトネン、ユッシ (1978)。「可算ブール代数の構造」。数学年報。108 ( 1 ) : 41–89。doi : 10.2307/1970929。JSTOR  1970929。
• Koppelberg, Sabine (1989)「ブール代数の一般理論」、Monk, J. Donald、Bonnet, Robert 編、 『ブール代数ハンドブック』第 1 巻。ノースホランド。ISBN 978-0-444-70261-6。 
• Peirce, CS (1989) 『チャールズ・S・ピアーズの著作：年代順版：1879-1884 』 Kloesel, CJW 編、インディアナポリス：インディアナ大学出版局。ISBN 978-0-253-37204-8。 
• Lawvere, F. William (1963). 「代数理論の関数的意味論」.米国科学アカデミー紀要. 50 (5): 869–873. Bibcode :1963PNAS...50..869L. doi : 10.1073 /pnas.50.5.869 . PMC  221940. PMID  16591125.
• シュレーダー、エルンスト（1890–1910）。Vorlesungen über die Algebra der Logik (exakte Logik)、I–III。ライプツィヒ：BG・トイブナー。
• シコルスキー、ローマン(1969)。ブール代数(第 3 版)。ベルリン: Springer-Verlag。ISBN 978-0-387-04469-9。
• ストーン、MH ( 1936)。「ブール代数の表現理論」。 アメリカ数学会誌。40 (1): 37–111。doi :10.2307/1989664。ISSN 0002-9947。JSTOR 1989664  。
• Tarski, Alfred (1983) 。Logic, Semantics, Metamathematics、Corcoran, J.、編。Hackett。1956年第1版、JH Woodger編集・翻訳、Oxford Uni. Press。次の2つの記事の英訳が含まれています。
  • アルフレッド、タルスキ(1929)。 「特別な授業は、確実な操作により関係を終了します。」数学の基礎。16 : 195–97。ISSN  0016-2736。
  • アルフレッド、タルスキー(1935)。 「Zur Grundlegung der Booleschen Algebra, I」。数学の基礎。24 : 177–9​​8。土井：10.4064/fm-24-1-177-198。ISSN  0016-2736。
• ウラジミロフ、DA (1969)。булевы алгебры (ブール代数、ロシア語、ドイツ語訳 Boolesche Algebren 1974)。 Nauka (ドイツ語翻訳Akademie-Verlag)。