回路計算 - ブール代数

概要

ブール代数は、19世紀にジョージ・ブールによって考案された数学的体系であり、論理演算の基礎となる重要な代数体系である。

ブール代数の概念は、値として0 (偽)と 1 (真) のみを扱い、これらの値に対して論理演算を適用することである。
主要な演算として、論理和 (OR、+で表記)、論理積 (AND、・で表記)、否定 (NOT、上線で表記) がある。
これらの演算を組み合わせることにより、複雑な論理関係を表現することができる。

交換則、結合則、分配則等があり、これらの法則を適用することにより、複雑な論理式を簡単化、等価な式に変換することができる。
例えば、$A+A\cdot B=A$ という吸収則を用いる場合、冗長な論理式を簡略化することができる。

ブール代数の応用例として、デジタル回路の設計がある。
論理ゲート (AND、OR、NOT等) を組み合わせることで、加算器や記憶素子 (RS-FF) 等の複雑な回路を構築することができる。

例えば、半加算器は次の論理式で表現できる。

• $S=A\oplus B$ (和)
• $C=A\cdot B$ (桁上げ)

また、プログラミングにおいても、条件分岐や真偽値の判定にブール代数の概念が使用されているす。
データベースの検索条件の組み立てや正規表現のパターンマッチング等も、ブール代数の原理に基づいている。

ブール代数の重要な概念として、双対性がある。
任意のブール式において、ANDとORを入れ替え、0と1を入れ替えると、等価な式が得られる。
これはド・モルガンの法則 ${\overline {A+B}}={\overline {A}}\cdot {\overline {B}}$ に代表される性質である。

カルノー図やクワイン・マクラスキー法等のブール式の簡単化手法も開発されており、
これらの手法を使用することで、複雑な論理回路を最適化してハードウェアの実装コストを削減することができる。

双対論理式

双対論理式は、元の論理式に対して、以下に示す変換を行って得られる式である。

• 全ての0と1を入れ替える。

  $0\rightarrow 1,\,\,1\rightarrow 0$
  

• 全ての論理和 (+) と 論理積 (・) を入れ替える。

  $\cdot \rightarrow +,\,\,+\rightarrow \cdot$
  

• 変数 (A, B, C等) はそのままにする。

式 $X$ の双対論理式は $X^{d}$ と表す。

例えば、$(x+y)\cdot z$ の双対論理式は、$x\cdot y+z$ になる。

例題 1:

次の論理式について考える。
$X=A+A\cdot B$

この式の双対論理式は、$X^{d}=A\cdot (A+B)$ となる。

これは吸収則により、どちらもAに簡単化できる。

例題 2:

$X=(A+B)\cdot (A+C)+1$

この式の双対論理式は、$X^{d}=(A\cdot B)+(A\cdot C)\cdot 0$

ある論理式が恒真 (常に1) であれば、その双対論理式は恒偽 (常に0) となる。
これは、双対性の重要な性質の1つである。

ド・モルガンの法則も双対性の観点から理解することができる。
これらの式は互いに双対の関係にあり、片方が成り立てば必然的にもう片方も成り立つ。

• ${\overline {A+B}}={\overline {A}}\cdot {\overline {B}}$
• ${\overline {A\cdot B}}={\overline {A}}+{\overline {B}}$

実際の回路設計では、この双対性を利用することにより、NANDゲートのみで構成された回路をNORゲートのみの回路に変換することや、その逆を行うことができる。
これは製造プロセスや性能要件に応じて、最適なゲート構成を選択する場合に役立つ。

双対定理

双対定理は、ブール式において、AND (論理積) と OR (論理和)、0と1を互いに置き換えることで得られる式が等価であることを示す定理である。

元の式から以下に示す変換を行うことにより、双対な式が得られる。

• ANDをORに
• ORをANDに
• 0を1に
• 1を0に
• 変数はそのままにする。

例:
$A\cdot B=B\cdot A$

上式の双対は
$A+B=B+A$

この双対定理は、1つの定理を証明すれば、その双対も自動的に証明されたことになる。
これにより、ブール代数の法則や定理の導出を効率的に行うことができる。

重要な例として、ド・モルガンの法則がある。
${\overline {(}}A\cdot B)={\overline {A}}OR{\overline {B}}$
この双対は、${\overline {A+B}}={\overline {A}}\cdot {\overline {B}}$ となる。

双対定理は、集合論においても同様の形で成り立つ。
集合の和集合と積集合、全体集合と空集合が、それぞれブール代数におけるORとAND、1と0に対応する。

例題 1:

$A+{\overline {A}}\cdot B=A+B$ を示せ。

一般的な方法:
${\begin{aligned}A+{\overline {A}}\cdot B&=A+A\cdot B+{\overline {A}}\cdot B\qquad {\mbox{(分  配  則  )}}\\&=A+(A+{\overline {A}})\cdot B\qquad {\mbox{(吸  収  則  )}}\\&=A+B\qquad {\mbox{(補  元  則  +  恒  等  則  )}}\end{aligned}}$

双対定理を用いた方法:
$A+{\overline {A}}\cdot B=A+B$ に対して双対定理を使用すると、$A({\overline {A}}+B)=A\cdot B$ となる。

${\begin{aligned}A\cdot ({\overline {A}}+B)&=A\cdot {\overline {A}}+A\cdot B\qquad {\mbox{(分  配  則  )}}\\&=A\cdot B\qquad {\mbox{(補  元  則  +  恒  等  則  )}}\end{aligned}}$

ブール代数の公式

交換則	$A+B=B+A$ $A\cdot B=B\cdot A$
結合則	$A+(B+C)=(A+B)+C$ $A\cdot (B\cdot C)=(A\cdot B)\cdot C$
分配則	$A(B+C)=AB+AC$ $A+BC=(A+B)(A+C)$
恒等則	$A+1=1$ $A\cdot 1=A$ $A+0=A$ $A\cdot 0=0$
同一則	$A\cdot A=A$ $A+A=A$
補元則	$A\cdot {\overline {A}}=0$ $A+{\overline {A}}=1$
吸収則	$A+A\cdot B=A$ $A\cdot (A+B)=A$
ド・モルガンの法則	${\overline {A+B}}={\overline {A}}\cdot {\overline {B}}$ ${\overline {A\cdot B}}={\overline {A}}+{\overline {B}}$