学ぶ › トピック 2
ブール代数：法則、ド・モルガンの定理、簡単化
読了時間：約 7 分 · bitGateLab チーム
ブール代数は、デジタル回路を記述し、変形するための言語です。式の一つひとつがゲートの組み合わせに対応していて、簡単化のために法則を一つ適用するたびに、その分だけゲートを節約できます。この記事では、公理、よく使う法則、ド・モルガンの定理をおさらいし、一手ごとに根拠を示しながら式を段階的に簡単化する方法を学びます。
変数と演算
ブール変数が取る値は 0 と 1 だけです。基本演算は三つあります。否定（A、NOT ゲート）、論理積（A·B または AB、AND ゲート）、論理和（A + B、OR ゲート）です。かっこがない場合の優先順位は、否定、積、和の順です。したがって A + BC は、ふつうの代数と同じく A + (B·C) を意味します。
公理
ブール代数全体は、いくつかの公理の上に成り立っています。和についてのものと積についてのものが、対になっていることに注目してください。
| 公理 | 和の形 | 積の形 |
|---|---|---|
| 同一則 | A + 0 = A | A · 1 = A |
| 交換則 | A + B = B + A | AB = BA |
| 分配則 | A + BC = (A + B)(A + C) | A(B + C) = AB + AC |
| 補元則 | A + A = 1 | A · A = 0 |
役に立つ法則と定理
公理からは次の規則が導かれます。簡単化でいちばんよく使うのはこれらです。
| 法則 | 和の形 | 積の形 |
|---|---|---|
| べき等則 | A + A = A | AA = A |
| 零則 | A + 1 = 1 | A · 0 = 0 |
| 対合則（二重否定） | A = A | |
| 結合則 | A + (B + C) = (A + B) + C | A(BC) = (AB)C |
| 吸収則 | A + AB = A | A(A + B) = A |
| 補元の吸収則 | A + AB = A + B | A(A + B) = AB |
| 隣接則 | AB + AB = A | (A + B)(A + B) = A |
| コンセンサスの定理 | AB + AC + BC = AB + AC | (A + B)(A + C)(B + C) = (A + B)(A + C) |
これらの法則はどれも、真理値表で確かめられます。二つの列がすべての行で一致すれば、その等式は正しいということです。たとえば A + AB = A の場合、A = 0 なら B に関係なく両辺とも 0、A = 1 なら両辺とも 1 です。補元の吸収則は、和の分配則を使って次のように証明できます。A + AB = (A + A)(A + B) = 1·(A + B) = A + B。
ド・モルガンの定理
この二つの定理は、長いバーの「切り方」を教えてくれます。
- A · B = A + B（積の否定は、それぞれの否定の和になる）。
- A + B = A · B（和の否定は、それぞれの否定の積になる）。
実用的な覚え方はこうです。バーを切るときは、その下にあった演算を入れ替え（· を + に、+ を · に）、各項を否定します。変数がいくつあっても成り立ちます。ABC = A + B + C。
| A | B | AB | A + B | A + B | AB |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 0 | 0 |
| 1 | 0 | 1 | 1 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 | 0 |
回路で考えると、ド・モルガンの定理は、NAND が「入力に丸印の付いた OR」と等価であり、NOR が「入力に丸印の付いた AND」と等価であることを示しています。これは、どんな設計でも NAND だけ、または NOR だけの回路に変換するための基礎で、論理ゲートの記事で説明しています。
例 1：ド・モルガンの定理を使う。 F = AB + C を簡単化します。
- 長いバーは和全体にかかっています。AB + C = AB · C。
- 積にかかるバーを切ります。AB = A + B。
- 結果：F = (A + B)C = AC + BC。
A = 1、B = 1、C = 0 で検算します。元の式は 1 + 0 = 0、結果の式は (0 + 0)·1 = 0 です。A = 0、B = 1、C = 0 では、元の式が 0 + 0 = 1、結果の式が (1 + 0)·1 = 1 です。
代数的な簡単化を一歩ずつ
簡単化とは、項の数とリテラル（否定の有無にかかわらず、変数が現れる一つひとつの箇所）の数を減らすことです。リテラルが減れば、ゲートの入力も減ります。代数だけで解く場合、決まった一つのアルゴリズムはありませんが、次の作戦はほとんどの場合に有効です。
- 一つの変数だけが異なる項のペアを探し、隣接則を適用する。
- 共通因数をくくり出し、隠れている A + A = 1 を探す。
- ある項が別の項に含まれていれば、吸収則で消す。
- 一つの項を複製して（べき等則）、異なる二つの隣の項とそれぞれ組み合わせてもよい。
例 2。 F = AB + AB + AB を簡単化します。
- 最初の二項をくくります。AB + AB = A(B + B) = A·1 = A。
- F = A + AB が残ります。
- 補元の吸収則：A + AB = A + B。
F = A + B です。AND ゲート三つ、3 入力 OR 一つ、インバータ二つの回路が、OR 一つになりました。
例 3：多数決関数。 F = ABC + ABC + ABC + ABC を簡単化します。
- べき等則により、ABC = ABC + ABC + ABC です。コピーを三つ書いて、それぞれを隣の項と組み合わせます。
- ABC + ABC = BC(A + A) = BC。
- ABC + ABC = AC(B + B) = AC。
- ABC + ABC = AB(C + C) = AB。
F = AB + AC + BC です。三つの入力のうち少なくとも二つが 1 のときに 1 になる、多数決回路です。これは全加算器のキャリー出力でもあることを、あとで学びます。
例 4：和の分配則。 F = (A + B)(A + C) を簡単化します。
- 展開します。AA + AC + AB + BC = A + AC + AB + BC。
- A でくくります。A(1 + C + B) + BC。
- 零則：1 + C + B = 1 なので、A + BC が残ります。
これはまさに、公理である和の分配則を逆向きに読んだものです。
よくある間違い
- 演算を入れ替えずにド・モルガンの定理を使う。AB は AB ではなく、A + B です。
- ふつうの代数のように項を「消去」する。ブール代数には引き算も割り算もありません。A + B = A + C から B = C は導けません。
- 優先順位を忘れる。A + BC は (A + B)C ではありません。
- 長いバーの一部だけを切る。AB + C のバーは和全体にかかっています。いちばん外側のバーから内側へ向かって処理しましょう。
- 早く止めすぎる。一手進めるたびに、吸収できる項や、冗長なコンセンサス項が残っていないかを確認しましょう。
シミュレータで試してみよう
正しく簡単化できていれば、できあがる回路の真理値表は元の回路とまったく同じになります。シミュレータを使えば、表を手で書かなくても確かめられます。
- 例のどれか、たとえば AB + AB + AB の元の回路を、入力と出力を付けてエディタで組みます。
- その真理値表を生成して、書き留めます。
- 同じキャンバスの別の出力として、簡単化した回路（A + B）を同じ入力につないで組みます。
- 入力をすべての組み合わせに切り替え、二つの出力が常に一致することを確かめます。
- 真理値表から簡単化した式を求め、手で導いた式と比べます。
練習問題
- F = AB + AB + AB を簡単化してください。
解答
AB + AB = A です。次に A + AB = A + B（補元の吸収則）。F = A + B = AB となり、これは NAND です。
- F = A + B を簡単化してください。
解答
ド・モルガンの定理より、A · B = AB。
- F = A(A + B) + B(B + C) を簡単化してください。
解答
吸収則により、A(A + B) = A、B(B + C) = B です。F = A + B。
- コンセンサスの定理 AB + AC + BC = AB + AC を証明してください。
解答
BC = BC(A + A) = ABC + ABC と書きます。すると AB + ABC = AB（吸収則）、AC + ABC = AC（吸収則）です。AB + AC が残ります。