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

ほかの技術知識

 通信・暗号や電子回路の明細書を読んでいると、たまにブール代数や排他的論理和(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以上の数を表現するときは桁数を増やす。ビットシフトなどの演算についての説明は割愛する。

2進数と10進数の対応関係

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 」でない,ということは
「 A でない」かつ「 B でない」ということとと同じ

②「 A かつ B 」でない,ということは
「 A でない」または「 B でない」ということと同じ

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

① !(P || Q) == !P && !Q
② !(P && Q) == !P || !Q

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

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

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