ブール代数

提供: miniwiki
移動先:案内検索

ブール代数(ブールだいすう、: boolean algebra)またはブール束(ブールそく、: boolean lattice)とは、ジョージ・ブールが19世紀中頃に考案した代数系の一つである。ブール代数の研究はの理論が築かれるひとつの契機ともなった。ブール論理の演算はブール代数の一例であり、現実の応用例としては、組み合わせ回路(論理回路#組み合わせ回路)はブール代数の式で表現できる。

定義

ブール代数ブール束)とは束論における可補分配束(complemented distributive lattice)のことである。

集合 LL 上の二項演算 ∨(結び(join)と呼ぶ),∧(交わり(meet)と呼ぶ)の組 〈 L; ∨, ∧ 〉 が以下を満たすとき分配束(distributive lattice)と呼ぶ。

  • 冪等則:xx = xx = x
  • 交換則:xy = yxxy = yx
  • 結合則:(xy)∧ z = x ∧(yz) 、(xy)∨ z = x ∨(yz) 、
  • 吸収則:(xy)∨ x =x 、(xy)∧ x = x
  • 分配則:(xy)∧ z = (xz)∨(yz) 、(xy)∨ z = (xz)∧(yz) 、

さらに L の特別な元 0, 1 と単項演算 ¬ について、以下が成り立つとき組 〈 L; ∨, ∧, ¬, 0, 1 〉 を可補分配束ブール束)と呼ぶ。

  • 補元則: x ∨ ¬x = 1, x ∧ ¬ x = 0。

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

ブール環

任意の元 x に対して x2 = x を満たす単位的 Bブール環(boolean ring)という。このとき

[math] x \wedge y = xy, \qquad x \vee y = x + y + xy, \qquad \neg x = 1 + x [/math]

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

[math] xy= x \wedge y , \qquad x+y = (x \wedge \neg y) \vee (\neg x \wedge y)[/math]

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

脚注

  1. Davey & Priestley 2002, Excercise 4.27.

参考文献

関連項目

外部リンク

|CitationClass=citation }}