ブール代数

出典: フリー百科事典『ウィキペディア(Wikipedia)』
2013年5月5日 (日) 09:56時点におけるRyuoujisinta (トーク)による版 (Ryuoujisinta (会話) による ID:47729434 の版を取り消し)
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
移動先: 案内検索

ブール代数(ブールだいすう、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つの組み合わせで記述される。)。

関連項目

参考文献

外部リンク

テンプレート:SEPテンプレート:Link GA

en:Boolean algebra (structure) fr:Algèbre de Boole (structure) he:אלגברה בוליאנית (מבנה אלגברי) ko:불 대수 zh:布尔代数