通信・暗号や電子回路の明細書を読んでいると、たまにブール代数や排他的論理和(XOR)の記号(島津藩の家紋みたいな〇に十字のやつ)が出てくる。知識の整理のために一冊読んでみたときのメモより抜粋。
ブール代数(Boolean Algebra)とは、「0」と「1」という「2つの値だけを使う数学」であって、数学というよりはパズルに近い。
0.ブール代数を学ぶ準備
ブール代数(0と1の数学)は、2進数(デジタル)の世界で使う数学だから、まずデジタルについて確認する。
アナログとデジタル
気温や信号の強さなどのモノが変化する量(変位量)を、最小単位があるやり方で表現する方法を「デジタル」方式という。対して、アナログ方式には最小単位がない。
② 多少のノイズが混じっても問題ない
例)遠く離れた場所に電圧1Vの電気信号を送る場合、ノイズによって強度が減衰し相手先についたときは0.8Vになったとする。「0」と「1」しか使わないデジタル方式では、受け取った側は「おそらく元々1Vだったのだろう」と判断できるが、アナログ方式では「もともと0.8Vだった」のか、それとも「1Vが減衰して0.8V」になったのか区別がつかない。
なお、この長所の裏返しとして「最小単位より小さなものは測れない」ということがある。
デジタルと2進数
デジタル方式でモノを考えるときは、すべて2進数で考える。普段生活の中で使う10進数が0~9までの10種類の数字を使うのに対し、2進数は「0」と「1」の2種類だけを使う。2以上の数を表現するときは桁数を増やす。ビットシフトなどの演算についての説明は割愛する。

1.ブール代数( 2進数の演算 )
2進数の演算をブール代数という。10進数の演算方法として、足し算・引き算・掛け算・割り算の4種類があるのに対して、2進数では「論理積」「論理和」「否定」の3種類しかない。
基本の演算
論理積(logical and) [・]
- 2つの数の両方が「1」のときのみ、「1」になる
- 例:0・0=0,1・0=0,1・1=1
論理和(logical or) [+]
- 2つの数のどちらかが「1」のときのみ、「1」になる
- 例:0・0=0,1・0=1,1・1=1
否定(not)[¬]
- 数字の前につけて、0と1を逆にした数を表す(「-」を数字の上につける表記もある)
- 例:¬0=1,¬1=0
アナロジーとして、2個のスイッチが付いたスイッチング回路を考えると(オン=1,オフ=0)、論理積は直列回路、論理和は並列回路になる。また、「否定」は、「押すとオフになる」ようなスイッチを考えて、1を「スイッチを押した状態」と考えればよい。
基本の法則
べき等則
- 同じ数同士で何回計算しても、答えは一緒になる
- 例: a+a=a , a・a=a
有界則
- ブール代数の演算の結果は、ブール代数の範囲内に収まる(常に0か1であって、-5とか2とかにならない)
- 例:a+1=1,a・0=0
吸収則
- ()がある場合の演算の法則①
- 例: a+(a・b)=a ,a・(a+b)=a
結合則
- ()がある場合の演算の法則②
- 例:(a+b)+c=a+(b+c),(a・b)・c=a・(b・c)
対合則
- 二重否定は肯定とおなじ
- 例:¬¬a=a
ド・モルガンの法則
「あるブール式の各変数を否定し、式の中の論理積と論理和を入れ替えた式は、全体を否定した式と同じ値をとる」
② ¬(a∧b)= ¬a∨¬b
日本語で説明するとこんな感じ
「 A でない」かつ「 B でない」ということとと同じ
②「 A かつ B 」でない,ということは
「 A でない」または「 B でない」ということと同じ
C言語風に書くとこんな感じ
② !(P && Q) == !P || !Q
ベン図で書くとこんな感じ

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

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