ブール代数

logic

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

基本演算

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

表1 ブール代数の基本演算
No. 演算 意味 双対表現 意味
1 \(\overline{0} = 1\) NOT \(\overline{1} = 0\) NOT
2 \(0 \bullet 0 = 0\) AND \(1 + 1 = 1\) OR
3 \(1 \bullet 1 = 1\) AND \(0 + 0 = 0\) OR
4 \(0 \bullet 1 = 1 \bullet 0= 0\) AND \(1 + 0 = 0 + 1= 1\) OR

1変数の法則

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

表2 ブール代数の法則(1変数)
No. 演算 双対表現
1 \(A \bullet 1 = A\) \(A + 0 = A\)
2 \(A \bullet 0 = 0\) \(A + 1 = 1\)
3 \(A \bullet A = A\) \(A + A = A\)
4 \(\overline{\overline{A}} = A\)
5 \(A \bullet \overline{A} = 0\) \(A + \overline{A} = 1\)

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

No.1:\(A \bullet 1 = A\)

「変数Aに1をかけた(Aと1のANDの)結果は、元のAと等しい」という法則です。これは、日常の積の演算で「ある数に1をかけたものは、元の数と等しい」という法則と同じです。Aに具体的な値を入れてみると、A=0のとき、\(0 \bullet 1 = 0\)となり、表1の基本演算のルールから、結果は元のAと同じ値0になります。また、A=1のときは\(1 \bullet 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 \bullet 0 = 0\)

「変数Aに0をかけた(Aと0のANDの)結果は、0に等しい」という法則です。これは、日常の積の演算で「ある数に0をかけたものは、0に等しい」という法則と同じです。Aに具体的な値を入れてみると、A=0のとき、 \(0 \bullet 0 = 0\)となり、表1の基本演算のルールから結果は0になります。また、A=1のときは\(1 \bullet 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 \bullet A = A\)

「変数AにAをかけた(AとAのANDの)結果は、元のAに等しい」という法則です。この法則は、日常の10進数の積の演算では成立しないブール代数特有の法則です(10進数でA=10のとき、10×10=100であり、結果は10でなない)。Aに具体的な値を入れてみると、A=0のとき、 \(0 \bullet 0 = 0\)となり、表1の基本演算のルールから結果はAと同じ値0になります。また、A=1のときは\(1 \bullet 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 \bullet \overline{A} = 0\)

「変数Aとその反転値をかけた(AとNOT AのANDの)結果は、0に等しい」という法則です。Aに具体的な値を入れてみると、A=0のとき、表1の基本演算のルールから\(0 \bullet \overline{0} = 0 \bullet 1 = 0\)となり、結果は0になります。また、A=1のときは、基本演算のルールから\(1 \bullet \overline{1} = 1 \bullet 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が変数を意味します。

表3 ブール代数の法則(複数変数)
No. 演算 双対表現 名称
1 \(A \bullet B = B \bullet A\) \(A + B = B + A\) 交換則
2 \((A \bullet B) \bullet C = A \bullet (B \bullet C)\) \((A + B) + C = A + (B + C)\) 結合則
3 \((A \bullet B) + (A \bullet C) = A \bullet (B + C)\) \((A + B) \bullet (A + C) = A + (B \bullet C)\) 分配則
4 \(A \bullet (A + B) = A\) \(A + (A \bullet B) = A\) 吸収則
5 \((A \bullet B) + (A \bullet \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 \bullet B) \)を先に計算してCをかけた結果と、\((B \bullet 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 \bullet (A + B) = A\)という式は、B=0とき、\(A \bullet (A + 0) = A \bullet A\)となります。表2のNo.3から\(A \bullet A = A\)なので、この式はAと等しいことがわかります(変数Bは不要)。B=1のときは、\(A \bullet (A + B) = A \bullet (A + 1)\)となります。表2のNo.2からA+1=Aなので、\(A \bullet (A + 1) = A \bullet A = A\)となり、この式はAと等しいことがわかります(変数Bは不要)。
双対表現についても同様です。B=0のとき、\(A + (A \bullet B) = A + (A \bullet 0) = A + 0 = A\)となり、この式はAと等しいことがわかります(変数Bは不要)。また、B=1のときは、\(A + (A \bullet B) = A + (A \bullet 1) = A + A = A\)となり、この式はAと等しいことがわかります(変数Bは不要)。

No.5:相殺則

冗長な変数の削除に関する法則です。表3の例の場合、変数Bは冗長です。表3の\((A \bullet B) + (A \bullet \overline{B})\)という式は、B=0のとき\((A \bullet 0) + (A \bullet 1) = A\)となり、Bは相殺されて結果はAになります。B=1のときは、\((A \bullet B) + (A \bullet \overline{B}) = (A \bullet 1) + (A \bullet 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 \bullet A = A\)なので、\(A(A+1) = A \bullet A = A\)となり、Bは相殺されて結果はAになります。また、B=1のときは、\((A + B)(A + \overline{B}) = (A + 1)(A + 0) = (A+1)A = A \bullet A = A\)となり、Bは相殺されて結果はAになります。

タイトルとURLをコピーしました