ブール代数（ブールだいすう、）またはブール束（ブールそく、）とは、命題論理における二値的な論理演算、集合論における和集合・共通部分・補集合の演算、ならびにデジタル回路における論理ゲートの計算に共通する代数的構造である。束論の立場からは、ブール代数は可補分配束として特徴づけられる。ブール代数は代数論理、束論、位相空間論、集合論、計算機科学などにまたがる基礎理論であり、ストーンの表現定理やストーン双対性を通じて位相空間との深い関係をもつ。ブール論理の演算はブール代数の基本例であり、現実の応用例としては、組み合わせ回路（論理回路）はブール代数の式で表現できる。
歴史 ブール代数の起源は、ジョージ・ブールが1847年の The Mathematical Analysis of Logic および1854年の An Investigation of the Laws of Thought において展開した、論理の代数的取扱いにある。もっとも、現代的意味での抽象的なブール代数は、ブール自身の体系をそのまま現在の公理系として言い換えたものではない。19世紀後半にウィリアム・スタンレー・ジェヴォンズ、チャールズ・サンダース・パース、エルンスト・シュレーダーらが代数的論理を整備し、20世紀初頭にエドワード・ヴァーミリー・ハンティントンが公理化を与えたことで、現代的理論の骨格が確立した。
20世紀には、マーシャル・ストーンがブール代数の表現理論を築き、位相空間との深い関係を明らかにした。さらに、クロード・シャノンは1938年、継電器回路の解析にブール代数を適用できることを示し、これが後のスイッチング理論およびデジタル回路設計の理論的基礎となった。
定義 ブール代数（ブール束）とは、束論における可補分配束（complemented distributive lattice）のことである。
集合 L と L 上の二項演算 ∨（結び、join と呼ぶ）、∧（交わり、meet と呼ぶ）の組 〈 L; ∨, ∧ 〉 が以下を満たすとき分配束（distributive lattice）と呼ぶ。
交換則：x ∧ y = y ∧ x 、x ∨ y = y ∨ x 結合則：(x ∧ y) ∧ z = x ∧ (y ∧ z) 、(x ∨ y) ∨ z = x ∨ (y ∨ z) 吸収則：(x ∧ y) ∨ x = x 、(x ∨ y) ∧ x = x 分配則：(x ∨ y) ∧ z = (x ∧ z) ∨ (y ∧ z) 、(x ∧ y) ∨ z = (x ∨ z) ∧ (y ∧ z)
さらに L の特別な元 0, 1 と単項演算 ¬ について、以下が成り立つとき組 〈 L; ∨, ∧, ¬, 0, 1 〉 を可補分配束（ブール束）と呼ぶ。
補元則：x ∨ ¬x = 1，x ∧ ¬x = 0。
この定義は、二項演算 、単項演算 、および定数 をもつ代数系としての定義と同値であり、ブール代数は「有界分配束であって各元が補元をもつもの」ともいえる。
基本性質 ブール代数では、補元は一意に定まる。また、次の基本法則が成り立つ。
冪等律：x ∧ x = x、x ∨ x = x ド・モルガンの法則：¬(x ∨ y) = (¬x) ∧ (¬y)、¬(x ∧ y) = (¬x) ∨ (¬y) 二重否定律：¬¬x = x
また、
と定めると、これは同値に
とも書ける。この順序のもとで 0 は最小元、1 は最大元であり、∨ は上限、∧ は下限を与える。
ブール代数の等式論には重要な簡約があり、ある恒等式がすべてのブール代数で成り立つことと、それが 2 元ブール代数 {0, 1} で成り立つことは同値である。これは真理値表による論理式の検証と、抽象的ブール代数における恒等式の検証とを結びつける。
例 典型的な例は、台集合として特別な2つの元 0, 1 のみをもつ 2 点集合 {0, 1} からなるものであり、これはブール論理の真理値代数である。コンピュータの動作原理の理論としてよく知られている。
任意の集合 X の冪集合 は、和集合・共通部分・補集合を演算としてブール代数をなす。このとき 0 は空集合、1 は X 自身に対応する。これはブール代数の最も基本的な具体例であり、有限ブール代数の標準模型でもある。
この代数の上では排他的論理和（xor）や否定論理積（nand）など応用上重要な演算子が ∧、∨、¬ の組み合わせで記述される（∧ または ∨ も ¬ と残りの1つの組み合わせで記述される）。
有限ブール代数 有限ブール代数はつねに原子的であり、原子全体の集合を A とすると、そのブール代数は と同型である。したがって、有限ブール代数の元の個数は必ず の形になる。
自由生成元を n 個もつ有限自由ブール代数では、原子は 個存在するので、元の総数は となる。これは、n 個の命題変数から作られるすべての論理関数の個数に一致する。
原子と原子性 非零元 a が原子であるとは、0 < b ≤ a ならば b = a であることをいう。各非零元がある原子の上にあるとき、そのブール代数は原子的であるという。これに対し、原子をまったくもたないブール代数は無原子的である。
有限ブール代数はすべて原子的であるが、無限ブール代数には原子的なものと無原子的なものがある。たとえば、可算無限個の生成元をもつ自由ブール代数は無原子的である。
準同型・イデアル・フィルター ブール代数の準同型とは、∨、∧、¬、0、1 を保つ写像である。準同型の像はふたたびブール代数をなし、核に対応するイデアルによって商代数が構成される。
部分集合 I ⊆ B がイデアルであるとは、0 ∈ I、a, b ∈ I ならば a ∨ b ∈ I、さらに c ≤ a ∈ I ならば c ∈ I が成り立つことをいう。双対的に、部分集合 F ⊆ B がフィルターであるとは、1 ∈ F、a, b ∈ F ならば a ∧ b ∈ F、さらに a ∈ F ≤ c ならば c ∈ F が成り立つことをいう。
超フィルター フィルター U が超フィルターであるとは、真フィルターであって、任意の a ∈ B に対して
のいずれか一方が成り立つことである。これは極大フィルターであることと同値であり、補元写像を通じて素イデアルと対応する。
超フィルターは、ブール代数の表現理論において中心的役割を果たす。各元 a ∈ B に対して、a を含む超フィルター全体の集合を考えると、これがストーン空間の閉開集合を与える。
自由ブール代数 集合 X に対して、X から任意のブール代数への写像が一意的に準同型へ延長できるという普遍性をもつブール代数を、X 上の自由ブール代数という。これは一般代数学における自由代数の一例であり、命題論理の式の代数的理解とも深く関わる。
有限集合上の自由ブール代数は有限であるが、可算無限集合上の自由ブール代数は可算であり、しかも無原子的である。ストーン双対性の観点からは、自由ブール代数は二点離散空間の冪の閉開集合代数として具体化される。
ブール環 任意の元 に対して積の冪等則 を満たす単位的環 B をブール環（）という。
このとき単位的環の公理から
さらに
が導かれ、それらと冪等則により
を得る。つまり、乗法が冪等的かつ単位的な環は、加法に関してすべての元の位数が高々 2 であるような可換環となる。
したがって
とおけば B はブール代数となる。 また B がブール代数のとき
とおけば B はブール環となる。
この対応はブール代数とブール環の間の自然な一対一対応を定めるので、しばしばこの 2 つは同一視される。
論理との関係 ブール代数は、古典命題論理の代数的意味論を与える。命題 p, q に対し、p ∨ q、p ∧ q、¬p はそれぞれ論理和・論理積・否定に対応する。論理式を論理的同値で割った同値類全体は、いわゆるリンデンバウム＝タルスキ代数をなし、古典命題論理の場合にはブール代数となる。
この対応により、論理式の標準形、真理値表、論理的同値、推論の妥当性などは、ブール代数の恒等式や順序の問題として扱うことができる。
表現定理とストーン双対性 ストーンの表現定理によれば、任意のブール代数 B は、適当なストーン空間の閉開集合全体のなすブール代数と同型である。すなわち、抽象的なブール代数はつねに具体的な集合代数として実現できる。
この構成は超フィルターを用いて与えられる。各 a ∈ B に対し、a を含む超フィルター全体の集合を考えると、これが B の各元に対応する閉開集合となる。
さらに、ブール代数の圏と、コンパクト・Hausdorff・零次元空間の圏との間には反変同値が成り立つ。これをストーン双対性という。これは代数・位相・論理の深い結びつきを示す代表的な双対性理論である。
完備ブール代数 任意の部分集合に対して上限と下限が存在するブール代数を完備ブール代数という。有限ブール代数や冪集合代数は完備であるが、一般のブール代数は完備とは限らない。
完備ブール代数は、表現論だけでなく、集合論におけるブール値モデルや強制法において本質的役割を果たす。また、可算部分集合についてのみ上限・下限の存在を仮定する σ-完備性も、測度論などとの関係で重要となる。
測度代数 測度空間 において、零測度集合の差を無視して可測集合を同一視した同値類全体は、自然な演算のもとでブール代数をなす。これを測度代数という。測度代数では、集合そのものではなく、零集合を法として見た代数的構造が主役となる。
測度代数は、測度論、確率論、エルゴード理論、関数解析などにおいて重要であり、無原子的完備ブール代数の代表的供給源でもある。
ブール値モデルと強制法 完備ブール代数 B を真理値集合として用い、真偽を {0, 1} ではなく B の元で評価するモデルをブール値モデルという。量化の解釈に上限・下限を用いるため、ここでは完備性が本質的となる。
集合論では、完備ブール代数からブール値宇宙 を構成することができる。これはポール・コーエンの強制法を意味論的に記述する枠組みを与え、独立性証明の理論において重要である。半順序集合による強制法は、対応する完備ブール代数の言葉に移し替えることができる。
応用 回路理論と情報工学 論理回路では、AND・OR・NOT などのゲートがブール演算として表される。シャノンの解析以後、継電器回路や電子回路の設計はブール代数によって体系化され、論理式の簡約、スイッチング関数の最適化、デジタル計算機の設計へと応用されてきた。
数理論理学 ブール代数は、古典命題論理の代数化、リンデンバウム＝タルスキ代数、ブール値モデルなどを通じて、数理論理学の基本理論の一部をなす。
位相空間論・集合論 ストーン双対性によって、ブール代数は零次元コンパクト Hausdorff 空間の理論と深く結びつく。また、完備ブール代数は強制法・ブール値解釈・独立性証明に現れ、現代集合論において重要な役割を果たす。
脚注
注釈 x ∧ x = x、x ∨ x = x と書かれる冪等則を要求する場合もあるが、これは吸収則により導かれる定理である。それでも明示するのは、 のそれぞれのみに注目した半束においてはこれが特徴的な公理だからである。
具体的には加法群の性質も用いて
から
を得る。さらに
から
を導くが、上で を得ているので であり、したがって
を得る。
2 元からなるブール束から 2 元からなるブール環を構成するなら、この定義は積を論理積の真理値、和を排他的論理和の真理値と定めることと同値である。また、位数 2 の非零環は一意であり、上記の対応によりブール論理の真理値と同値となるようなブール環でもある。
出典
参考文献
- 1980年に槙書店から出版され、2015年に森北出版から復刊された。
関連項目
外部リンク