出典は列挙するだけでなく、脚注などを用いてどの記述の情報源であるかを明記してください。記事の信頼性向上にご協力をお願いいたします。(2015年12月)
ブール代数(ブールだいすう、英: boolean algebra)またはブール束(ブールそく、英: boolean lattice)とは、ジョージ・ブールが19世紀中頃に考案した代数系の一つである。ブール代数の研究は束の理論が築かれるひとつの契機ともなった。ブール論理の演算はブール代数の一例であり、現実の応用例としては、組み合わせ回路(論理回路)はブール代数の式で表現できる。 ブール代数(ブール束)とは束論における可補分配束(complemented distributive lattice)のことである。 集合 L と L 上の二項演算 ∨(結び(join)と呼ぶ),∧(交わり(meet)と呼ぶ)の組 ⟨ L; ∨, ∧ ⟩ が以下を満たすとき分配束(distributive lattice)と呼ぶ。 さらに L の特別な元 0, 1 と単項演算 ¬ について、以下が成り立つとき組 ⟨ L; ∨, ∧, ¬, 0, 1 ⟩ を可補分配束(ブール束)と呼ぶ。 典型的な例は、台集合として特別な2つの元 0, 1 のみの2点集合 {0, 1} からなるものであり、コンピュータの動作原理の理論としても知られている。この代数の上では排他的論理和 (xor) や否定論理積(nand)など応用上重要な演算子が ∧、 ∨、 ¬ の組み合わせで記述される(∧ または ∨ も ¬ と残りの1つの組み合わせで記述される。)。 任意の元 x に対して 積の冪等則x2 = x を満たす単位的環 B をブール環(boolean ring)という。このとき単位的環の公理から−x=(−1)x=x(−1) さらに(−x)(−y)=xy が導かれ、それらと冪等則により x + x = 0 , x y = y x {\displaystyle x+x=0,\qquad xy=yx} を得る[注釈 2]。つまり(乗法が)冪等的かつ単位的な環は加法に関して全ての元の位数が高々2であるような可換環となる。したがって x ∧ y = x y , x ∨ y = x + y + x y , ¬ x = 1 + x {\displaystyle x\wedge y=xy,\qquad x\vee y=x+y+xy,\qquad \neg x=1+x} とおけば B はブール代数となる。また B がブール代数のとき x y = x ∧ y , x + y = ( x ∧ ¬ y ) ∨ ( ¬ x ∧ y ) {\displaystyle xy=x\wedge y,\qquad x+y=(x\wedge \neg y)\vee (\neg x\wedge y)} と[注釈 3]おけば B はブール環となる。この対応はブール代数とブール環の間の自然な一対一対応を定めるので、しばしばこの2つは同一視される。[1]。
定義
交換則: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)
補元則: x ∨ ¬x = 1, x ∧ ¬ x = 0。
ブール環
脚注[脚注の使い方]
注釈^ x ∧ x = x、x ∨ x = x と書かれる冪等則を要求する場合もあるが、これは吸収則により導かれる定理である。それでも明示するのは、 ∧ 、∨ のそれぞれのみに注目した半束においてはこれが特徴的な公理だからである。
^ 具体的には加法群の性質も用いて x = x2 = (− x) 2 = − xから x + x =0を得、これにより 0 = (x − y) − (x − y) 2 = xy + yx から xy = − yxを導くことで xy − yx = xy + xy = 0であると判り xy = yxを得る。
^ 2元からなるブール束から2元からなるブール環を構成するなら、この定義は積を論理積の真理値、和を排他的論理和の真理値と定める事と同値。また、位数2の非零環は(一意でありかつ)明らかに、上記の対応によりブール論理の真理値と同値となるようなブール環でもある(対応するのはあくまでも真理値であることに注意)。
出典^ Davey & Priestley 2002, p. 109