ブール代数

高等学校情報の既習が望ましい。

導入

ブール代数（Boolean algebra）またはブール束（boolean lattice）とは、平たく言えば二進数の世界における代数学である。関連分野として、ブール論理をはじめとする古典論理学、組み合わせ論理（論理回路）や順序回路を使用する情報工学・電気回路理論・電子工学などが挙げられる。

束論の立場からみると、ブール代数とは「可補分配束（complemented distributive lattice）」のことである。詳細は後述する。

まずは、ブール代数における演算則を見ていく。

基本演算

以下、このページで用いる変数（ブール変数）は次を満たすとする。

\mathbb {B} =\{0,1\}

^※

a,b,c,\cdots \in \mathbb {B}

※0, 1はそれぞれ論理学に於ける偽、真に対応する。記号は必ずしも0, 1でなくても良い（例えば甲, 乙でもよい）が、二進数との関連を考えて0, 1を用いることにする。また、

\mathbb {B}

をブール領域という。

論理和

2変数の少なくとも一方が1のときに1を返す二項演算を論理和(OR演算、sum)という。

論理和を表す記号として、 $+,\cup ,\lor ,\oplus$ などがある。ただし、 $\oplus$ はブール代数において別の意味でも用いられるので、あまり使用されない。本書では通常の加算記号 $+$ を用いる。

真理値表（truth table）で書くと以下のようになる。

論理和
a	b	a+b
0	0	0
0	1	1
1	0	1
1	1	1

論理積

2変数の両方が1のときのみ1を返す二項演算を論理積（AND演算、product）という。

論理積を表す記号として、 $\times ,\cdot ,\ast ,\cap ,\land ,\otimes$ などがある。もしくは、通常の乗算のように省略して書く。本書では通常の乗算記号 $\times ,\cdot$ を用いる。

真理値表で書くと以下のようになる。

論理積
a	b	a×b
0	0	0
0	1	0
1	0	0
1	1	1

否定

ある変数の補集合^※を返す単項演算を否定（NOT演算、nagation）または補数（complement）という。

※

\mathbb {B}

は元を二つしか持たないので、片方の元のみを要素とする集合の補集合はもう片方の元をただ一つの要素に持つ。

否定を表す記号として、 $\neg ,{\bar {}}$ がある。本書では ${\bar {}}$ を用いる。

真理値表で書くと以下のようになる。

否定
a	ā
0	1
1	0

ブール領域の元と論理和・論理積・否定で構成される数式をブール表現（Boolean expression）という。

基本法則

有界性
$0+a=a+0=a$

$1\cdot a=a\cdot 1=a$
恒等則（identity laws）
$1+a=a+1=1$

$0\cdot a=a\cdot 0=0$
交換則（commutative laws）
$a+b=b+a$

$a\cdot b=b\cdot a$
結合則（associative laws）
$(a+b)+c=a+(b+c)=a+b+c$

$(a\cdot b)\cdot c=a\cdot (b\cdot c)=a\cdot b\cdot c$
分配則（distributive laws）
$a\cdot (b+c)=(a\cdot b)+(b\cdot c)$

$a+(b\cdot c)=(a+c)\cdot (b+c)$
相補則（補元則, 可補束, complementary laws）
$a+{\bar {a}}=1$

$a\cdot {\bar {a}}=0$
再帰則(対合, reflexive law)
${\bar {\bar {a}}}=a$
吸収則(absorption laws)
$a+a\cdot b=a$

$a\cdot (a+b)=a$
等冪性
$a+a=a$

$a\cdot a=a$