ブール代数
ブール代数(ブール束)とは束論における可補分配束(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。
典型的な例は、台集合として特別な2つの元 0, 1 のみの2点集合 {0, 1} からなるものであり、コンピュータの動作原理の理論としても知られている。 この代数の上では排他的論理和 (xor) や否定論理積(nand)など応用上重要な演算子が ∧、 ∨、 ¬ の組み合わせで記述される(∧ または ∨ も ¬ と残りの1つの組み合わせで記述される。)。