ブール代数 — 法則・定理・簡単化

ブール代数は、真偽値の式を組み合わせたり簡単化したりするための体系です。$AB + A\overline{B}$ のような論理式を簡単にしたいときは、補元則、分配則、吸収則、ド・モルガンの定理などが主な道具になります。

よく使われる記法では、$x + y$ は OR、$xy$ は AND、$\overline{x}$ は NOT $x$ を表します。NOT を $x'$ と書く本もありますが、基本となる規則は同じです。

ブール代数とは何か

通常の代数は数を扱います。ブール代数は、真/偽 または $1/0$ の2つの値しか取らない命題や2値変数を扱います。

そのため、規則も変わります。ブール代数では、

$$x + x = x \quad \text{and} \quad xx = x$$

となります。どちらの恒等式も同じ考え方を表しています。つまり、同じ条件を繰り返しても新しい結果は生まれません。スイッチがすでにオンなら、「オン OR オン」と言っても何も変わらないということです。

実際によく使うブール代数の法則

ブール式を簡単化するときに、特によく出てくる法則は次のとおりです。

恒等則

$$x + 0 = x, \qquad x \cdot 1 = x$$

偽を OR しても何も変わらず、真と AND を取っても何も変わりません。

零則

$$x + 1 = 1, \qquad x \cdot 0 = 0$$

OR に真が含まれていれば、全体の結果は真です。AND に偽が含まれていれば、全体の結果は偽です。

べき等則

$$x + x = x, \qquad x \cdot x = x$$

同じ変数を繰り返しても、式は変わりません。

補元則

$$x + \overline{x} = 1, \qquad x \cdot \overline{x} = 0$$

変数とその否定は、OR ではすべての場合をカバーしますが、AND では同時に成り立ちません。

交換則と結合則

$$x + y = y + x, \qquad xy = yx$$ $$(x + y) + z = x + (y + z), \qquad (xy)z = x(yz)$$

これらにより、結果を変えずに項の順序を入れ替えたり、まとめ方を変えたりできます。

分配則

$$x(y + z) = xy + xz$$ $$x + yz = (x + y)(x + z)$$

2つ目の形はあまり見慣れないかもしれませんが、標準的なブール恒等式であり、因数分解でよく現れます。

吸収則

$$x + xy = x, \qquad x(x + y) = x$$

式が見た目より長く見えるときに、特に役立つ法則です。

ド・モルガンの定理

$$\overline{x + y} = \overline{x}\,\overline{y}, \qquad \overline{xy} = \overline{x} + \overline{y}$$

これらは、否定が OR や AND をまたぐときにどう変形されるかを示します。NOT がかっこを通ると、OR と AND は役割を入れ替えます。

例題: $AB + A\overline{B}$ を簡単化する

まず

$$F = AB + A\overline{B}$$

から始めます。

共通な $A$ をくくり出すと、

$$F = A(B + \overline{B})$$

となります。

次に補元則を使うと、

$$F = A \cdot 1$$

です。

さらに恒等則を使うと、

$$F = A$$

となります。

したがって、$AB + A\overline{B} = A$ です。直感的に見ると、$A = 1$ なら $B = 1$ でも $\overline{B} = 1$ でも、どちらか一方の項は必ず真になります。$A = 0$ なら両方の項が偽です。つまり、この式全体は $A$ だけに依存しています。

ブール代数でよくある間違い

よくある間違いの1つは、通常の代数の感覚をそのままブール代数に持ち込んでしまうことです。たとえば、$x + x = 2x$ はブール代数の規則ではありません。ここで正しい結果は $x$ です。

もう1つの間違いは、記法を確認せずに法則を適用してしまうことです。多くの教科書では、$+$ は算術の足し算ではなく OR を意味し、変数を並べて書くと AND を表します。

また、ド・モルガンの定理では各変数を否定するだけでなく、OR と AND を入れ替える必要があります。この2つはどちらも重要です。

ブール代数はどこで使われるか

ブール代数はデジタル論理の中心にあり、変数はオン/オフや真/偽の状態を表します。回路設計の簡単化、ソフトウェアでの論理条件の整理、検索フィルタやデータベースクエリの考察などに使われます。

変数が2値でない場合や、演算が通常の算術である場合には、ブール代数の法則をそのまま適用することはできません。この2値性こそが、この体系を成り立たせる条件です。

似た簡単化を試してみよう

$(A + B)(A + \overline{B})$ を簡単化してみてください。上の法則を注意深く使えば、最初に見えるよりも大きく簡単になります。さらに一歩進めたいなら、真理値表を作って、簡単化した形がすべての行で一致することを確かめてみましょう。