組み合わせ論理回路

ありとあらゆる論理回路は、AND と OR と NOT を使うことにより実現できる。 それは次のような理由による。 論理回路のいくつかの入力といくつかの出力を持つ。 また、その動作は入力に発生するありとあらゆる可能なビットパターンに対する、 出力パターンを表にしたもので、完全に記述できる。 この表は真理値表 (truth table) と呼ばれている。

Figure 4.13: 真理値表の例

図4.13に一例を示すが、この表で $D$ に対応する 論理回路を考えてみよう。 まず、(000) が入ってきた時のみ1を出力する論理回路を考えよう。 (000) は、厳密には (0、0、0) のことであるが、以下このように略記する。 この論理回路の出力を $S_0$ とすると、

$$S_0 = \overline A\cdot\overline B\cdot\overline C$$ (4.9)

のように、三つの入力の NOT の AND をとったものである。 $\overline A$ などは $A$ などの否定を表している。 また、'$\cdot$' は AND を意味し、'$\cdot$' でまとめられた項 すべての AND をとる。 $(A、B、C)$ が (000) のとき、 $(\overline A, \overline B, \overline C)$は (111) となる。 一方、三入力ANDは入力が (111) ときのみ 1 を出力するから、$(A、B、C)$ が (000) のときのみ 1 となる。 同様な考察で、図2.13の各行に対応した $S_0$ から $S_7$ は次のように 表される。

$$S_0 = \overline A\cdot\overline B\cdot\overline C$$ (4.10)

$$S_1 = \overline A\cdot\overline B\cdot C$$ (4.11)

$$S_2 = \overline A\cdot B\cdot\overline C$$ (4.12)

$$S_3 = \overline A\cdot B\cdot C$$ (4.13)

$$S_4 = A\cdot\overline B\cdot\overline C$$ (4.14)

$$S_5 = A\cdot\overline B\cdot C$$ (4.15)

$$S_6 = A\cdot B\cdot\overline C$$ (4.16)

$$S_7 = A\cdot B\cdot C$$ (4.17)

さて、$D$ は $(001), (010), (100), (111)$ のいずれかが 1 のときのみ 1 であるから、これら四つのパターンの OR で与えられる。 つまり、

$$D = S_1+S_2+S_4+S_7$$

$$= \overline A\cdot\overline\cdot B\cdot C+\overline A\cdot B\cdot\overline C+\cdot A\cdot\overline B\cdot\overline C +A\cdot B\cdot C$$ (4.18)

となり、NOT と AND と OR の組み合わせで表現できる。 ここで、OR は '+' で表されている。 AND と同様に、多入力の場合は '+' を複数書く。 AND の記号の '$\cdot$' の方が優先度が高いと定義されているので、まず AND をとり、その OR をとることになる。

まったく同様に

$$E = S_3+S_5+S_6+S_7$$

$$= \overline A\cdot B\cdot C+A\cdot\overline B\cdot C+A\cdot B\cdot\overline C+A\cdot B\cdot C$$ (4.19)

となる。 以上にように、いかなる場合も真理値表の 0、1 に併せて、NOT、AND、OR を配置すればよいことが理解できよう。

電子回路の場合、こうした論理は AND、OR の代わりに NAND や NOR を使って 実現する必要がある。 これには、うまい方法が知られている。 まず、$S_0$ から $S_7$ の代わりに、それらの否定論理である $T_0$ から $T_7$ を使おう。 すると明らかに

$$T_0 = \overline{\overline A\cdot\overline B\cdot\overline C}$$ (4.20)

$$T_1 = \overline{\overline A\cdot\overline B\cdot C}$$ (4.21)

$$T_2 = \overline{\overline A\cdot B\cdot \overline C}$$ (4.22)

$$T_3 = \overline{\overline A\cdot B\cdot C}$$ (4.23)

$$T_4 = \overline{A\cdot\overline B\cdot\overline C}$$ (4.24)

$$T_5 = \overline{A\cdot\overline B\cdot C}$$ (4.25)

$$T_6 = \overline{A\cdot B\cdot\overline C}$$ (4.26)

$$T_7 = \overline{A\cdot B\cdot C}$$ (4.27)

である。 また、 $D=\overline T_1+\overline T_2+\overline T_4+\overline T_7$ となる。 ところが、この式は $D=\overline{T_1\cdot T_2\cdot T_4\cdot T_7}$ と変形できるのである。 つまり、NOT と NAND だけがあれば、いかなる論理も 構成できてしまうのである。

OR(NOT) を NAND にする変形は De Morgan の法則として知られている。 証明は $D$ が 0 になる条件を考えてみれば、容易である。 上式では、OR の演算を使っているが、OR は入力要素の一つでも 1 になると 1 になってしまう。 つまり、ORが 0 になるには、すべての要素が 0 である必要がある。 ところがすべての要素が大もとの入力 $T_1$ から $T_7$ の 否定であるから、大もとの入力 $T_1$ から $T_7$ で考えると、すべての 入力 $T_1$ から $T_7$ が 1 のときだけ $D$ は 0となる。 一方、下式を見ると、すべての入力が 1 の時だけ、AND は 1 になり、NAND は 0 になる。 したがって、いずれの論理も $T_1$ から $T_7$ が 1 のときのみ、出力が 0 となり、同じ動作をすることが理解できよう。

Figure 4.14: NAND-NAND回路

Figure 4.15: 簡略表記による NAND-NAND 回路

これらを回路図にすると図4.14のようになる。 これを、簡略化して図4.15のように表すことがある。 多入力 NAND の入力を一本の線にまとめて表すこの標記法は、実際の回路と 対応がとれず、誤解を招きやすいので、安易な導入は危険であるが、 見やすいのでしばしば利用されている。 ただ、実際にいくつかの論理の出力を一本の線に接続すると、いわゆる 短絡状態を起こす可能性があり、場合によっては論理回路の壊滅的破壊を 招きかねないので、絶対に行ってはならない。 この図を、図4.13の真理値表と比較してみると、きわめて強い 対応がとれていることが理解できよう。 左半平面の NAND 面では、真理値表の入力側の 1 に対して、$A$、$B$、 $C$ との接続が対応し、真理値表の 0 に対して、 $\overline A、 \overline B、\overline C$ との接続が対応している。 また右半平面の NAND 面では、真理値表の出力側の 1 が対応している。 なお、この図の簡略 NAND 記法により表した NAND-NAND 回路の一番上の NAND ゲートは最終出力にいっさい関係しておらず、不要である。 しかし、現在の集積回路の内部では見やすい構造とすることを 旨としているので、不要な回路でも真理値表との対応関係から、 残しておくことが多い。

同様な回路は NOR だけを用いても実現できる。 まず、

$$S_0 = \overline{A+B+C} \cr S_1$$ (4.28)

となる。 これらの式は de Morgan の法則を使って証明できる。 また、例えば、$S_0$ については、OR は (000) の時のみ 0 となること、 したがって、NOR は 1 になることから、理解できよう。 さらに、$D$は$S_0$、$S_3$、$S_5$、$S_6$ のいずれが 選択されても 0 となることから、

$$D = \overline{S_0+S_3+S_5+S_6}$$ (4.29)

と表される。 つまり、NOR-NOR 論理は真理値表の 0 に着目した構成となっている。 この意味で NOR-NOR 論理は NAND-NAND 論理の反転論理 (inversion logic) と 呼ばれる。