ブール代数

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

ブール代数(ブールだいすう、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;∨∧,¬> を可補分配束(ブール束)と呼ぶ。

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

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

関連項目[編集]

参考文献[編集]

  • ガーレット・バーコフ, ソンダース・マクレーン 『現代代数学概論』 白水社、1967年、改訂第3版。
  • 前田 周一郎 『束論と量子論理』 槙書店、1980年
  • Garrett Birkhoff (1979). Lattice Theory (3rd ed.). 
  • George Grätzer (1979). Universal Algebra (2nd ed.). 

外部リンク[編集]