ブール代数
出典: フリー百科事典『ウィキペディア(Wikipedia)』
ブール代数(ブールだいすう)あるいはブール環(ブールかん)とは、ジョージ・ブールが19世紀中頃に考案した論理数学の代表的な概念。ブール束ともいう。ブール代数の研究は代数的構造としての束の理論が築かれるひとつの契機ともなった。数学的に厳密な定義は後述する。
デジタル回路の設計には必須の知識である。デジタル回路は、電圧の H(High), L(Low) のみで情報を演算するため、基本的に組み合わせ回路はブール代数における論理式で書き表わすことができる(ただし、フリップフロップ等を用いた順序回路は、単純に一つの論理式で表わすことはできない)。
ブール代数の基本演算(論理演算)は 論理否定 ¬(not)、論理和 ∨(or)、論理積 ∧(and) の3つから成る。これらの合成から作られる演算で代表的なものに排他的論理和 (xor) がある。
ブール代数をブール束と呼ぶのは、∨, ∧ について分配的な束となるからである。つまり次の条件が満たされる:
- 冪等律:x ∧ x = x ∨ x = x 、
- 交換律: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) 。
さらに、ブール代数では次が成り立つ:
- 恒真 1 と恒偽(矛盾) 0 とをもち、各元 x に対して元 ¬x が存在して、x ∧ ¬x = 0, x ∨ ¬x = 1 をみたす。
数学的にはこれらの条件を公理として、それを満たす集合を一般に、ブール束あるいはブール代数と呼ぶ。