論理回路を構成する論理ゲートや論理式は、0と1という2値を扱います。この2値の計算を行う時のルールがブール代数です。ブール代数には、日常生活で扱う10進数の四則演算と同様のルールも存在しますが、2進数の計算特有のルールも存在します。
ブール代数は、主に論理回路や論理式の最適化に利用されます。論理回路の最適化とは、ある論理回路から冗長な回路を削減することを意味します。
基本演算
ブール代数の基本演算のルールは、表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ゲートの真理値表と同じ意味を持ちます。
| No. | 演算 | 意味 | 双対表現 | 意味 |
| 1 | \(\overline{0} = 1\) | NOT | \(\overline{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が変数です。
| 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 | \(\overline{\overline{A}} = A\) | |
| 5 | \(A \cdot \overline{A} = 0\) | \(A + \overline{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:\(\overline{\overline{A}} = A\)
「変数Aを2回否定した結果(2段のNOT)は、Aに等しい」という法則です。Aに具体的な値を入れてみると、A=0のとき、表1の基本演算のルールから\(\overline{\overline{0}} = \overline{1} = 0\)となり、結果は元のAと同じ値0になります。また、A=1のときは、基本演算のルールから\(\overline{\overline{1}} = \overline{0} = 1\)となり、結果は元のAと同じ値1になります。
法則4の双対表現はありません。
No.5:\(A \cdot \overline{A} = 0\)
「変数Aとその反転値をかけた(AとNOT AのANDの)結果は、0に等しい」という法則です。Aに具体的な値を入れてみると、A=0のとき、表1の基本演算のルールから\(0 \cdot \overline{0} = 0 \cdot 1 = 0\)となり、結果は0になります。また、A=1のときは、基本演算のルールから\(1 \cdot \overline{1} = 1 \cdot 0 = 0\)となり、結果は0になります。
双対表現についても同様です。法則3の双対表現は、「変数Aとその反転値を足した(AとNOT AのORの)結果は、1に等しい」という法則です。Aに具体的な値を入れてみると、A=0のとき、基本演算のルールから\(0 + \overline{0} = 0 + 1 = 1\)となり、結果は1になります。また、A=1のときは、基本演算のルールから\(1 + \overline{1} = 1 + 0 = 1\)となり、結果は1になります。
複数変数の法則
表3は、2変数または3変数を扱う場合の法則です。表3のA,B,Cが変数を意味します。
| 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 \overline{B}) = A\) | \((A + B)(A + \overline{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 \overline{B})\)という式は、B=0のとき\((A \cdot 0) + (A \cdot 1) = A\)となり、Bは相殺されて結果はAになります。B=1のときは、\((A \cdot B) + (A \cdot \overline{B}) = (A \cdot 1) + (A \cdot 0) = A\)となり、Bは相殺されて結果はAになります。
双対表現についても同様です。B=0のとき、\((A + B)(A + \overline{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 + \overline{B}) = (A + 1)(A + 0) = (A+1)A = A \cdot A = A\)となり、Bは相殺されて結果はAになります。