ブール代数とド・モルガンの法則

　通信・暗号や電子回路の明細書を読んでいると、たまにブール代数や排他的論理和（XOR）の記号（島津藩の家紋みたいな〇に十字のやつ）が出てくる。知識の整理のために一冊読んでみたときのメモより抜粋。

　ブール代数（Boolean Algebra）とは、「０」と「１」という「２つの値だけを使う数学」であって、数学というよりはパズルに近い。

０．ブール代数を学ぶ準備

　ブール代数（０と１の数学）は、２進数（デジタル）の世界で使う数学だから、まずデジタルについて確認する。

アナログとデジタル

　気温や信号の強さなどのモノが変化する量（変位量）を、最小単位があるやり方で表現する方法を「デジタル」方式という。対して、アナログ方式には最小単位がない。

例）遠く離れた場所に電圧１Ｖの電気信号を送る場合、ノイズによって強度が減衰し相手先についたときは0.8Ｖになったとする。「０」と「１」しか使わないデジタル方式では、受け取った側は「おそらく元々１Ｖだったのだろう」と判断できるが、アナログ方式では「もともと0.8Ｖだった」のか、それとも「１Ｖが減衰して0.8Ｖ」になったのか区別がつかない。

なお、この長所の裏返しとして「最小単位より小さなものは測れない」ということがある。

デジタルと2進数

　デジタル方式でモノを考えるときは、すべて２進数で考える。普段生活の中で使う１０進数が０～９までの10種類の数字を使うのに対し、２進数は「０」と「１」の２種類だけを使う。２以上の数を表現するときは桁数を増やす。ビットシフトなどの演算についての説明は割愛する。

１．ブール代数（ 2進数の演算 ）

　2進数の演算をブール代数という。10進数の演算方法として、足し算・引き算・掛け算・割り算の４種類があるのに対して、２進数では「論理積」「論理和」「否定」の３種類しかない。

基本の演算

論理積（logical and） ［・］

• ２つの数の両方が「１」のときのみ、「１」になる
• 例：０・０＝０，１・０＝０，１・１＝１

論理和（logical or） ［+］

• ２つの数のどちらかが「１」のときのみ、「１」になる
• 例：０・０＝０，１・０＝１，１・１＝１

否定（not）[￢]

• 数字の前につけて、０と１を逆にした数を表す（「－」を数字の上につける表記もある）
• 例：￢０＝１，￢１＝０

アナロジーとして、２個のスイッチが付いたスイッチング回路を考えると（オン＝１，オフ＝０）、論理積は直列回路、論理和は並列回路になる。また、「否定」は、「押すとオフになる」ようなスイッチを考えて、１を「スイッチを押した状態」と考えればよい。

基本の法則

べき等則

• 同じ数同士で何回計算しても、答えは一緒になる
• 例： ａ＋ａ＝ａ ， ａ・ａ＝ａ

有界則

• ブール代数の演算の結果は、ブール代数の範囲内に収まる（常に０か１であって、－５とか２とかにならない）
• 例：ａ＋１＝１，ａ・０＝０

吸収則

• （）がある場合の演算の法則①
• 例： ａ＋（ａ・ｂ）＝ａ ，ａ・（ａ＋ｂ）＝ａ

結合則

• （）がある場合の演算の法則②
• 例：（ａ＋ｂ）＋ｃ＝ａ＋（ｂ＋ｃ），（ａ・ｂ）・ｃ＝ａ・（ｂ・ｃ）

対合則

• 二重否定は肯定とおなじ
• 例：￢￢ａ＝ａ

ド・モルガンの法則

「あるブール式の各変数を否定し、式の中の論理積と論理和を入れ替えた式は、全体を否定した式と同じ値をとる」

日本語で説明するとこんな感じ

C言語風に書くとこんな感じ

ベン図で書くとこんな感じ

真理値表にするとこんな感じ

実際に計算するとこんな感じ