Loading article…
数学において、ブール代数またはブール束は、補元付き分配束です。このタイプの代数構造は、集合演算と論理演算の両方の本質的な性質を捉えています。ブール代数は、冪集合代数または集合体の一般化と見なすことができ、その要素は一般化された真理値と見なすことができます。また、ド・モルガン代数およびクリーネ代数（対合付き）の特殊な場合でもあります。
すべてのブール代数はブール環を生み出し、その逆もまた同様である。環の乗算は論理積または相互演算∧に対応し、環の加算は排他的論理和または対称差（論理和∨ではない）に対応する。しかし、ブール環の理論には2つの演算子の間に固有の非対称性があるのに対し、ブール代数の公理と定理は双対性原理によって記述される理論の対称性を表現している。[ 1 ]
「ブール代数」という用語は、独学で数学を学んだイギリスの数学者ジョージ・ブール（1815～1864）にちなんで名付けられました。彼は、オーガスタス・ド・モルガンとウィリアム・ハミルトンの間で繰り広げられていた論争に応えて、1847年に出版された小冊子『論理の数学的分析』で最初に代数体系を紹介し、その後、1854年に出版されたより本格的な書籍『思考の法則』で紹介しました。ブールの定式化は、上記のものとはいくつかの重要な点で異なります。例えば、ブールでは論理積と論理和は双対演算ではありませんでした。ブール代数は、1860年代にウィリアム・ジェボンズとチャールズ・サンダース・パースが書いた論文で登場しました。
ブール代数と分配束の最初の体系的な説明は、1890 年のErnst SchröderのVorlesungenによるものです。英語でブール代数を初めて包括的に扱ったのは、 1898 年のAN WhiteheadのUniversal Algebraです。現代の公理的意味での公理的代数構造としてのブール代数は、1904 年のEdward V. Huntingtonの論文から始まります。[ 2 ]ブール代数は、1930 年代のMarshall Stoneの研究と、1940 年のGarrett BirkhoffのLattice Theoryによって本格的な数学として成熟しました。1960 年代には、Paul Cohen、Dana Scottらが、ブール代数の派生である強制法とブール値モデルを使用して、数理論理学と公理的集合論で深い新しい結果を発見しました。
ブール代数とは、2 つの二項演算 ∧ (「meet」または「and」と呼ばれる)、 ∨ (「join」または「or」と呼ばれる)、単項演算¬ (「complement」または「not」と呼ばれる)、およびAの2 つの要素0と1 (「bottom」と「top」、または「least」と「greatest」要素と呼ばれ、それぞれ記号⊥と⊤で表される) を備えた集合 A であり、Aのすべての要素a、b、cに対して次の公理が成り立つ: [ 3 ]
ただし、吸収法則や結合法則は他の公理から導き出せるため、公理の集合から除外できることに注意してください（証明された性質を参照）。
要素が1つしかないブール代数は、自明なブール代数または退化ブール代数と呼ばれます。（古い文献では、このケースを除外するために、0と1が異なる要素であることを要件とする著者もいました。）
上記の最後の３組の公理（同一性、分配性、補元）または吸収公理から、
これらの同値条件が満たされる場合、a ≤ bで定義される関係≤ は、最小要素 0 と最大要素 1 を持つ半順序です。2 つの要素の交わりa ∧ bと結合a ∨ bは、それぞれ ≤ に関して、それらの下限と上限に一致します。
最初の4組の公理は、有界束の定義を構成する。
最初の5組の公理から、任意の補集合は一意であることが導かれる。
公理の集合は、公理の中で∨を∧に、0を1に交換すると、結果が再び公理になるという意味で自己双対である。したがって、この操作をブール代数（またはブール束）に適用すると、同じ要素を持つ別のブール代数が得られる。これはその双対と呼ばれる。[ 4 ]
演算がe ∨ f := e + f − efおよびe ∧ f := ef で定義されると、ブール代数になります。
2 つのブール代数AとBの間の準同型写像は、すべてのa、b ∈ Aに対して次の式が成り立つような関数f : A → Bです。
したがって、すべてのa ∈ Aに対してf (¬ a ) = ¬ f ( a )が成り立つ。すべてのブール代数のクラスは、この射の概念とともに、束の圏の完全な部分圏を形成する。
2 つのブール代数AとBの間の同型写像とは、逆同型写像、すなわち、合成g ∘ f : A → AがA上の恒等関数であり、合成f ∘ g : B → BがB上の恒等関数であるような同型写像 f : A → B のことである。ブール代数の同型写像は、全単射である場合に限り同型写像となる。
すべてのブール代数( A、∧、∨)は、a + b := ( a ∧ ¬ b ) ∨ ( b ∧ ¬ a ) = ( a ∨ b ) ∧ ¬( a ∧ b ) (この演算は、集合の場合は対称差、論理の場合はXORと呼ばれます)およびa · b := a ∧ bを定義することにより、環 ( A、 +、· )を生成します。この環の零元はブール代数の 0 と一致し、環の乗法単位元はブール代数の1です。この環は、すべてのa ∈ Aに対してa · a = aという性質を持ちます。この性質を持つ環はブール環と呼ばれます。
逆に、ブール環Aが与えられた場合、x ∨ y := x + y + ( x · y )およびx ∧ y := x · yと定義することにより、ブール環をブール代数に変換できます。[ 5 ] [ 6 ]これらの 2 つの構成は互いに逆であるため、すべてのブール環はブール代数から生じ、その逆もまた同様であると言えます。さらに、写像f : A → Bは、ブール環の準同型である場合に限り、ブール代数の準同型です。ブール環とブール代数のカテゴリは同等です。[ 7 ]実際、カテゴリは同型です。
Hsiang (1985) は、任意の 2 つの式がすべてのブール環で同じ値を表すかどうかをチェックするルールベースのアルゴリズムを提示した。 [ 8 ]
より一般的には、Boudet、Jouannaud、およびSchmidt-Schauß（1989）[ 9 ]は、任意のブール環式間の方程式を解くアルゴリズムを与えた。ブール環とブール代数の類似性を利用して、両方のアルゴリズムは自動定理証明に応用されている。
ブール代数 A のイデアルとは、 Iのすべてのx、yに対して、 Iにおいてx ∨ yが成り立ち、 Aのすべてのaに対して、 Iにおいてa ∧ xが成り立つような、空でない部分集合I のことである。このイデアルの概念は、ブール環Aにおける環イデアルの概念と一致する。AのイデアルIは、 I ≠ Aであり、かつ、 Iにおいてa ∧ b が常にIにおいてaまたはb が成り立つならば、素イデアルと呼ばれる。さらに、すべてのa ∈ Aに対して、a ∧ − a = 0 ∈ Iが成り立ち、 I が素イデアルであれば、すべてのa ∈ Aに対して、I においてa ∈ Iまたは− a ∈ Iが成り立つ。AのイデアルIは、 I ≠ Aであり、かつ、 I を真に含む唯一のイデアルがA自身であるならば、極大イデアルと呼ばれる。イデアルIに対して、a ∉ Iかつ− a ∉ Iならば、I ∪ { a }またはI ∪ { − a }は別の真イデアルJに含まれる。したがって、そのようなIは極大イデアルではないため、素イデアルと極大イデアルの概念はブール代数において同値である。さらに、これらの概念は、ブール環Aにおける環論的な素イデアルと極大イデアルの概念と一致する。
イデアルの双対はフィルタである。ブール代数Aのフィルタは、空でない部分集合pであり、 pのすべてのx、yに対してpにx ∧ yが存在し、 Aのすべてのaに対してpにa ∨ x が存在する。ブール代数における極大(または素)イデアルの双対は超フィルタである。超フィルタは、 Aから2 要素ブール代数への2 値射として記述することもできる。ブール代数のすべてのフィルタは超フィルタに拡張できるという命題は超フィルタ補題と呼ばれ、ツェルメロ・フレンケル集合論(ZF) が無矛盾であれば、ZFでは証明できない。ZF 内では、超フィルタ補題は選択公理よりも厳密に弱い。超フィルター補題には多くの同値な定式化があります。すべてのブール代数には超フィルターがあり、ブール代数のすべてのイデアルは素イデアルに拡張できます、などです。
すべての有限ブール代数は、有限集合のすべての部分集合からなるブール代数と同型であることが示せる。したがって、すべての有限ブール代数の要素数は2のべき乗である。
ストーンのブール代数表現定理は、すべてのブール代数Aは、ある (コンパクトで完全に不連結なハウスドルフ) 位相空間内のすべてのクローペン集合のブール代数と同型であると述べている。 [ 10 ]
一般的にブール束/代数の最初の公理化は、1898 年にイギリスの哲学者で数学者のアルフレッド・ノース・ホワイトヘッドによって与えられました。 [ 11 ] [ 12 ]これは上記の公理に加えて、x ∨ 1 = 1およびx ∧ 0 = 0を含んでいました。1904 年に、アメリカの数学者エドワード・V・ハンティントン(1874–1952) は、∧、∨、¬に基づくおそらく最も簡潔な公理化を与え、結合法則も証明しました (ボックスを参照)。[ 13 ]彼はまた、これらの公理が互いに独立していることも証明しました。 [ 14 ]
1933年、ハンティントンはブール代数のための以下の洗練された公理化を提示した。[ 15 ]これは、1つの二項演算+と、補数と読み替えられる単項関数記号nのみを必要とし、これらは以下の法則を満たす。
ハーバート・ロビンスはすぐにこう尋ねた。ハンティントン方程式をその双対方程式に置き換えると、すなわち、
(1)、(2)、(4)はブール代数の基底を形成するのか？ (1)、(2)、(4)をロビンス代数と呼ぶと、問題は次のようになる。すべてのロビンス代数はブール代数なのか？ この問題（ロビンス予想として知られるようになった）は何十年も未解決のままであり、アルフレッド・タルスキとその弟子たちのお気に入りの問題となった。
1996年、アルゴンヌ国立研究所のウィリアム・マキューンは、ラリー・ウォス、スティーブ・ウィンカー、ボブ・ヴェロフによる以前の研究に基づいて、ロビンスの問いに肯定的に答えた。すなわち、すべてのロビンス代数はブール代数である。マキューンの証明において重要だったのは、彼が設計したコンピュータプログラムEQPであった。マキューンの証明の簡略化については、ダーン（1998）を参照のこと。[ 16 ]
公理の数を減らすためのさらなる研究が行われています。ブール代数の最小公理を参照してください。
ブール代数の公理から単位元の存在要件を取り除くと、「一般化ブール代数」が得られます。形式的には、分配束Bが一般化ブール束であるのは、最小要素0を持ち、 Bの任意の要素aとbに対してa ≤ bとなる要素xが存在し、 a ∧ x = 0かつa ∨ x = bとなる場合です。( a ∧ b ) ∨ x = aかつ( a ∧ b ) ∧ x = 0となる唯一のx をa \ bと定義すると、構造( B , ∧, ∨, \, 0)は一般化ブール代数であり、( B , ∨, 0)は一般化ブール半束であると言えます。一般化ブール束は、まさにブール束の理想形である。
ブール代数の公理のうち、分配法則の2つを除くすべての公理を満たす構造を直交補元束と呼ぶ。直交補元束は、可分ヒルベルト空間の閉じた線形部分空間の束として、量子論理において自然に現れる。
