ブール代数

ブール代数の起源は、ジョージ・ブールが1847年の The Mathematical Analysis of Logic および1854年の An Investigation of the Laws of Thought において展開した、論理の代数的取扱いにある。もっとも、現代的意味での抽象的なブール代数は、ブール自身の体系をそのまま現在の公理系として言い換えたものではない。19世紀後半にウィリアム・スタンレー・ジェヴォンズ、チャールズ・サンダース・パース、エルンスト・シュレーダーらが代数的論理を整備し、20世紀初頭にエドワード・ヴァーミリー・ハンティントンが公理化を与えたことで、現代的理論の骨格が確立した。^[3][4]

20世紀には、マーシャル・ストーンがブール代数の表現理論を築き、位相空間との深い関係を明らかにした。さらに、クロード・シャノンは1938年、継電器回路の解析にブール代数を適用できることを示し、これが後のスイッチング理論およびデジタル回路設計の理論的基礎となった。^[5][6]

ブール代数（ブール束）とは、束論における可補分配束（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)
• 吸収則^{[注釈 1]}：(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。

この定義は、二項演算 \(\vee,\wedge\)、単項演算 \(\neg\)、および定数 \(0,1\) をもつ代数系としての定義と同値であり、ブール代数は「有界分配束であって各元が補元をもつもの」ともいえる。^[1][7]

ブール代数では、補元は一意に定まる。また、次の基本法則が成り立つ。^[1][8]

• 冪等律：x ∧ x = x、x ∨ x = x
• ド・モルガンの法則：¬(x ∨ y) = (¬x) ∧ (¬y)、¬(x ∧ y) = (¬x) ∨ (¬y)
• 二重否定律：¬¬x = x

また、

${\displaystyle x\leq y\iff x\wedge y=x}$

と定めると、これは同値に

${\displaystyle x\vee y=y}$

とも書ける。この順序のもとで 0 は最小元、1 は最大元であり、∨ は上限、∧ は下限を与える。^[1]

ブール代数の等式論には重要な簡約があり、ある恒等式がすべてのブール代数で成り立つことと、それが 2 元ブール代数 {0, 1} で成り立つことは同値である。これは真理値表による論理式の検証と、抽象的ブール代数における恒等式の検証とを結びつける。^[1]

典型的な例は、台集合として特別な2つの元 0, 1 のみをもつ 2 点集合 {0, 1} からなるものであり、これはブール論理の真理値代数である。コンピュータの動作原理の理論としてよく知られている。^[1]

任意の集合 X の冪集合 \(\mathcal P(X)\) は、和集合・共通部分・補集合を演算としてブール代数をなす。このとき 0 は空集合、1 は X 自身に対応する。これはブール代数の最も基本的な具体例であり、有限ブール代数の標準模型でもある。^[1][5]

この代数の上では排他的論理和（xor）や否定論理積（nand）など応用上重要な演算子が ∧、∨、¬ の組み合わせで記述される（∧ または ∨ も ¬ と残りの1つの組み合わせで記述される）。

有限ブール代数はつねに原子的であり、原子全体の集合を A とすると、そのブール代数は \(\mathcal P(A)\) と同型である。したがって、有限ブール代数の元の個数は必ず \(2^n\) の形になる。^[7][1]

自由生成元を n 個もつ有限自由ブール代数では、原子は \(2^n\) 個存在するので、元の総数は \(2^{2^n}\) となる。これは、n 個の命題変数から作られるすべての論理関数の個数に一致する。^[8]

非零元 a が原子であるとは、0 < b ≤ a ならば b = a であることをいう。各非零元がある原子の上にあるとき、そのブール代数は原子的であるという。これに対し、原子をまったくもたないブール代数は無原子的である。^[1]

有限ブール代数はすべて原子的であるが、無限ブール代数には原子的なものと無原子的なものがある。たとえば、可算無限個の生成元をもつ自由ブール代数は無原子的である。^[1]

ブール代数の準同型とは、∨、∧、¬、0、1 を保つ写像である。準同型の像はふたたびブール代数をなし、核に対応するイデアルによって商代数が構成される。^[1][8]

部分集合 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 が成り立つことをいう。^[1]

集合 X に対して、X から任意のブール代数への写像が一意的に準同型へ延長できるという普遍性をもつブール代数を、X 上の自由ブール代数という。これは一般代数学における自由代数の一例であり、命題論理の式の代数的理解とも深く関わる。^[1][8]

有限集合上の自由ブール代数は有限であるが、可算無限集合上の自由ブール代数は可算であり、しかも無原子的である。ストーン双対性の観点からは、自由ブール代数は二点離散空間の冪の閉開集合代数として具体化される。^[1]

任意の元 x に対して積の冪等則 x² = x を満たす単位的環 B をブール環（英: Boolean ring）という。

このとき単位的環の公理から

${\displaystyle -x=(-1)x=x(-1)}$

さらに

${\displaystyle (-x)(-y)=xy}$

が導かれ、それらと冪等則により

${\displaystyle x+x=0,\qquad xy=yx}$

を得る^{[注釈 2]}。つまり、乗法が冪等的かつ単位的な環は、加法に関してすべての元の位数が高々 2 であるような可換環となる。

したがって

${\displaystyle x\wedge y=xy,\qquad x\vee y=x+y+xy,\qquad \neg x=1+x}$

とおけば B はブール代数となる。 また B がブール代数のとき

${\displaystyle xy=x\wedge y,\qquad x+y=(x\wedge \neg y)\vee (\neg x\wedge y)}$

と^{[注釈 3]}おけば B はブール環となる。

この対応はブール代数とブール環の間の自然な一対一対応を定めるので、しばしばこの 2 つは同一視される。^[9]

ブール代数は、古典命題論理の代数的意味論を与える。命題 p, q に対し、p ∨ q、p ∧ q、¬p はそれぞれ論理和・論理積・否定に対応する。論理式を論理的同値で割った同値類全体は、いわゆるリンデンバウム＝タルスキ代数をなし、古典命題論理の場合にはブール代数となる。^[1][10]

この対応により、論理式の標準形、真理値表、論理的同値、推論の妥当性などは、ブール代数の恒等式や順序の問題として扱うことができる。^[1]

ストーンの表現定理によれば、任意のブール代数 B は、適当なストーン空間の閉開集合全体のなすブール代数と同型である。すなわち、抽象的なブール代数はつねに具体的な集合代数として実現できる。^[5][1]

この構成は超フィルターを用いて与えられる。各 a ∈ B に対し、a を含む超フィルター全体の集合を考えると、これが B の各元に対応する閉開集合となる。^[1][5]

さらに、ブール代数の圏と、コンパクト・Hausdorff・零次元空間の圏との間には反変同値が成り立つ。これをストーン双対性という。これは代数・位相・論理の深い結びつきを示す代表的な双対性理論である。^[5][11]

任意の部分集合に対して上限と下限が存在するブール代数を完備ブール代数という。有限ブール代数や冪集合代数は完備であるが、一般のブール代数は完備とは限らない。^[1]

完備ブール代数は、表現論だけでなく、集合論におけるブール値モデルや強制法において本質的役割を果たす。また、可算部分集合についてのみ上限・下限の存在を仮定する σ-完備性も、測度論などとの関係で重要となる。^[1][7]

測度空間 \((X,\Sigma,\mu)\) において、零測度集合の差を無視して可測集合を同一視した同値類全体は、自然な演算のもとでブール代数をなす。これを測度代数という。測度代数では、集合そのものではなく、零集合を法として見た代数的構造が主役となる。^[1][12]

測度代数は、測度論、確率論、エルゴード理論、関数解析などにおいて重要であり、無原子的完備ブール代数の代表的供給源でもある。^[1][13]

完備ブール代数 B を真理値集合として用い、真偽を {0, 1} ではなく B の元で評価するモデルをブール値モデルという。量化の解釈に上限・下限を用いるため、ここでは完備性が本質的となる。^[1]

集合論では、完備ブール代数からブール値宇宙 \(V^B\) を構成することができる。これはポール・コーエンの強制法を意味論的に記述する枠組みを与え、独立性証明の理論において重要である。半順序集合による強制法は、対応する完備ブール代数の言葉に移し替えることができる。^[1][14]