ブール代数

論理回路を構成する論理ゲートや論理式は、0と1という2値を扱います。この2値の計算を行う時のルールがブール代数です。ブール代数には、日常生活で扱う10進数の四則演算と同様のルールも存在しますが、2進数の計算特有のルールも存在します。
ブール代数は、主に論理回路や論理式の最適化に利用されます。論理回路の最適化とは、ある論理回路から冗長な回路を削減することを意味します。

基本演算
1変数の法則
複数変数の法則

基本演算

ブール代数の基本演算のルールは、表1のように基本ゲートの入出力の関係に対応します。具体的には、表1のNo.1がNOTゲート、No.2からNo.4がANDゲートとORゲートの入出力の関係に対応します。表中の”双対表現”は、0と1を入れ替えて、AND $(\cdot)$ とOR $(+)$ を入れ替えた演算も成り立つというルールです。例えば、表1 No.2では、左列の演算 $0 \cdot 0 = 0$ の0を1に置き換え、さらにANDをORに置き換えた右列の双対表現も成り立ちます。
表1 No.1の左列の演算と右列の双対表現を合わせたものがNOTゲートの真理値表と同じ意味を持ちます。また、表1 No.2からNo.4は、左列の演算部分がANDゲートの真理値表と同じ意味を持ち、右列の双対表現がORゲートの真理値表と同じ意味を持ちます。

表1 ブール代数の基本演算
No.	演算	意味	双対表現	意味
1	$\overset{―}{0} = 1$	NOT	$\overset{―}{1} = 0$	NOT
2	$0 \cdot 0 = 0$	AND	$1 + 1 = 1$	OR
3	$1 \cdot 1 = 1$	AND	$0 + 0 = 0$	OR
4	$0 \cdot 1 = 1 \cdot 0 = 0$	AND	$1 + 0 = 0 + 1 = 1$	OR

1変数の法則

表1の基本演算を基に、ある1つの変数を含む演算を行う場合の法則をまとめたものが表2です。表2ではAが変数です。

表2 ブール代数の法則（1変数）
No.	演算	双対表現
1	$A \cdot 1 = A$	$A + 0 = A$
2	$A \cdot 0 = 0$	$A + 1 = 1$
3	$A \cdot A = A$	$A + A = A$
4	$\overset{―}{\overset{―}{A}} = A$
5	$A \cdot \overset{―}{A} = 0$	$A + \overset{―}{A} = 1$

表2 No.1 〜No.5の意味は、次の通りです。

No.1: $A \cdot 1 = A$

「変数Aに1をかけた(Aと1のANDの)結果は、元のAと等しい」という法則です。これは、日常の積の演算で「ある数に1をかけたものは、元の数と等しい」という法則と同じです。Aに具体的な値を入れてみると、A=0のとき、 $0 \cdot 1 = 0$ となり、表1の基本演算のルールから、結果は元のAと同じ値0になります。また、A=1のときは $1 \cdot 1 = 1$ となり、基本演算のルールから、結果は元のAと同じ値1になります。
双対表現についても同様です。法則1の双対表現は、「変数Aに0を足した(Aと0のORの)結果は、元のAと等しい」という法則です。Aに具体的な値を入れてみると、A=0のとき、 $0 + 0 = 0$ になり、基本演算のルールから、結果は元のAと同じ値0になります。また、A=1のときは $1 + 0 = 1$ になり、基本演算のルールから結果は元のAと同じ1になります。

No.2: $A \cdot 0 = 0$

「変数Aに0をかけた(Aと0のANDの)結果は、0に等しい」という法則です。これは、日常の積の演算で「ある数に0をかけたものは、0に等しい」という法則と同じです。Aに具体的な値を入れてみると、A=0のとき、 $0 \cdot 0 = 0$ となり、表1の基本演算のルールから結果は0になります。また、A=1のときは $1 \cdot 0 = 0$ となり、基本演算のルールから結果は0になります。
双対表現についても同様です。法則2の双対表現は、「変数Aに1を足した(Aと1のORの)結果は、1に等しい」という法則です。Aに具体的な値を入れてみると、A=0のとき、 $0 + 1 = 1$ となり、基本演算のルールから結果は1になります。また、A=1のときは $1 + 1 = 1$ となり、基本演算のルールから結果は1になります。

No.3: $A \cdot A = A$

「変数AにAをかけた(AとAのANDの)結果は、元のAに等しい」という法則です。この法則は、日常の10進数の積の演算では成立しないブール代数特有の法則です(10進数でA=10のとき、10×10=100であり、結果は10でなない)。Aに具体的な値を入れてみると、A=0のとき、 $0 \cdot 0 = 0$ となり、表1の基本演算のルールから結果はAと同じ値0になります。また、A=1のときは $1 \cdot 1 = 1$ となり、基本演算のルールから結果はAと同じ値1になります。
双対表現についても同様です。法則3の双対表現は、「変数AにAを足した(AとAのORの)結果は、元のAに等しい」という法則です。Aに具体的な値を入れてみると、A=0のとき、 $0 + 0 = 0$ となり、基本演算のルールから結果は元のAと同じ値0になります。また、A=1のときは $1 + 1 = 1$ となり、基本演算のルールから結果は元のAと同じ値1になります。

No.4: $\overset{―}{\overset{―}{A}} = A$

「変数Aを2回否定した結果(2段のNOT)は、Aに等しい」という法則です。Aに具体的な値を入れてみると、A=0のとき、表1の基本演算のルールから $\overset{―}{\overset{―}{0}} = \overset{―}{1} = 0$ となり、結果は元のAと同じ値0になります。また、A=1のときは、基本演算のルールから $\overset{―}{\overset{―}{1}} = \overset{―}{0} = 1$ となり、結果は元のAと同じ値1になります。
法則4の双対表現はありません。

No.5: $A \cdot \overset{―}{A} = 0$

「変数Aとその反転値をかけた(AとNOT AのANDの)結果は、0に等しい」という法則です。Aに具体的な値を入れてみると、A=0のとき、表1の基本演算のルールから $0 \cdot \overset{―}{0} = 0 \cdot 1 = 0$ となり、結果は0になります。また、A=1のときは、基本演算のルールから $1 \cdot \overset{―}{1} = 1 \cdot 0 = 0$ となり、結果は0になります。
双対表現についても同様です。法則3の双対表現は、「変数Aとその反転値を足した(AとNOT AのORの)結果は、1に等しい」という法則です。Aに具体的な値を入れてみると、A=0のとき、基本演算のルールから $0 + \overset{―}{0} = 0 + 1 = 1$ となり、結果は1になります。また、A=1のときは、基本演算のルールから $1 + \overset{―}{1} = 1 + 0 = 1$ となり、結果は1になります。

複数変数の法則

表3は、2変数または3変数を扱う場合の法則です。表3のA,B,Cが変数を意味します。

表3 ブール代数の法則（複数変数）
No.	演算	双対表現	名称
1	$A \cdot B = B \cdot A$	$A + B = B + A$	交換則
2	$(A \cdot B) \cdot C = A \cdot (B \cdot C)$	$(A + B) + C = A + (B + C)$	結合則
3	$(A \cdot B) + (A \cdot C) = A \cdot (B + C)$	$(A + B) \cdot (A + C) = A + (B \cdot C)$	分配則
4	$A \cdot (A + B) = A$	$A + (A \cdot B) = A$	吸収則
5	$(A \cdot B) + (A \cdot \overset{―}{B}) = A$	$(A + B) (A + \overset{―}{B}) = A$	相殺則

表3の、No.1〜No.5の意味は、次の通りです。

No.1:交換則

10進数の演算の交換法則と同じです。「変数Aと変数Bをかけた(AとBのANDの)結果は、変数Bと変数Aをかけた結果に等しい」という法則です。
双対表現は、「変数Aと変数Bを足した結果は、変数Bと変数Aを足した結果に等しい」という意味になります。このように、AとBを交換しても演算の結果は同じになるというのが交換則です。

No.2:結合則

「変数A,変数B,変数Cをかけるとき、 $(A \cdot B)$ を先に計算してCをかけた結果と、 $(B \cdot C)$ を先に計算してAをかけた結果は等しい」という法則です。
双対表現は、「変数A,変数B,変数Cを足すとき、(A+B)を先に計算してCを足した結果と、(B+C)を先に計算してAを足した結果は等しい」という意味になります。このように、かっこ()の位置を変えても演算の結果は同じになるというのが結合則です。

No.3:分配則

10進数の演算の分配法則と同じです。表3の例の場合、式の左辺に含まれる変数Aは、右辺のように1つのAにまとめることができます。逆に、式の右辺のAは、左辺のように分配することができます。

No.4:吸収則

冗長な変数の削除に関する法則です。表3の例の場合、変数Bは冗長です。表3の $A \cdot (A + B) = A$ という式は、B=0とき、 $A \cdot (A + 0) = A \cdot A$ となります。表2のNo.3から $A \cdot A = A$ なので、この式はAと等しいことがわかります(変数Bは不要)。B=1のときは、 $A \cdot (A + B) = A \cdot (A + 1)$ となります。表2のNo.2からA+1=Aなので、 $A \cdot (A + 1) = A \cdot A = A$ となり、この式はAと等しいことがわかります(変数Bは不要)。
双対表現についても同様です。B=0のとき、 $A + (A \cdot B) = A + (A \cdot 0) = A + 0 = A$ となり、この式はAと等しいことがわかります(変数Bは不要)。また、B=1のときは、 $A + (A \cdot B) = A + (A \cdot 1) = A + A = A$ となり、この式はAと等しいことがわかります(変数Bは不要)。

No.5:相殺則

冗長な変数の削除に関する法則です。表3の例の場合、変数Bは冗長です。表3の $(A \cdot B) + (A \cdot \overset{―}{B})$ という式は、B=0のとき $(A \cdot 0) + (A \cdot 1) = A$ となり、Bは相殺されて結果はAになります。B=1のときは、 $(A \cdot B) + (A \cdot \overset{―}{B}) = (A \cdot 1) + (A \cdot 0) = A$ となり、Bは相殺されて結果はAになります。
双対表現についても同様です。B=0のとき、 $(A + B) (A + \overset{―}{B}) = (A + 0) (A + 1) = A (A + 1)$ となります。ここで、表2のNo.2とNo.3からA+1=A、また $A \cdot A = A$ なので、 $A (A + 1) = A \cdot A = A$ となり、Bは相殺されて結果はAになります。また、B=1のときは、 $(A + B) (A + \overset{―}{B}) = (A + 1) (A + 0) = (A + 1) A = A \cdot A = A$ となり、Bは相殺されて結果はAになります。