AND-OR回路

任意の入出力関係を実現する組合せ回路は， 知識と経験がないと設計できないと思われたかもしれないが， 多少回路規模が大きくてもよいのならば， かなり組織的に設計することができる。 本節と次節で，その組織的構成法について紹介する。

論理回路は一般に複数の入力と複数の出力を持ちうる。 また，その動作は入力に発生するありとあらゆる可能なビットパターンに対する， 出力パターンを示した真理値表（truth table）により完全に記述できる。

Figure 4.4: 真理値表の例（全加算器）

どんな真理値表からスタートしてもよいのだが， 図 4.4に示す全加算器を例にして， $C_o$を出力する論理回路を考えてみよう。 まず，(000)が入ってきたときにのみ1を出力する論理回路を考えよう。 (000)は，厳密には$(0,0,0)$のことであるが，以下このように略記する。 この論理回路の出力を$M_0$とすると，

$$M_0=\mathop{\rm AND}\nolimits (\overline A,\overline B,\overline{C_i})$$ (4.3)

のように，三つの入力のNOTのANDをとったものである。 $\overline A$などは$A$などの否定を表している。 $(A,B,C_i)$が(000)のとき， $(\overline A,\overline B,\overline{C_i})$は (111)となる。 一方，3入力ANDは入力が(111)ときのみ1を出力するから，$(A,B,C_i)$ =(000)のときのみ$M_0$=1となる。 同様な考察で， 図 4.4の各行に対応した$M_0$から$M_7$は次のように 表される。

$$M_0 = \mathop{\rm AND}\nolimits (\overline A,\overline B,\overline{C_i})$$

$$M_1 = \mathop{\rm AND}\nolimits (\overline A,\overline B, C_i)$$

$$M_2 = \mathop{\rm AND}\nolimits (\overline A, B,\overline{C_i})$$

$$M_3 = \mathop{\rm AND}\nolimits (\overline A, B, C_i)$$

$$M_4 = \mathop{\rm AND}\nolimits (A,\overline B,\overline{C_i})$$

$$M_5 = \mathop{\rm AND}\nolimits (A,\overline B, C_i)$$

$$M_6 = \mathop{\rm AND}\nolimits (A, B,\overline{C_i})$$

$$M_7 = \mathop{\rm AND}\nolimits (A, B, C_i)$$ (4.4)

さて，$C_o$は $M_3,\ M_5,\ M_6,\ M_7$のいずれかが1のときのみ 1であるから，これら四つのパターンのORで与えられる。 つまり，

$$C_o=\mathop{\rm OR}\nolimits (M_3,M_5,M_6,M_7)$$ (4.5)

まったく同様に

$$S=\mathop{\rm OR}\nolimits (M_1,M_2,M_4,M_7)$$ (4.6)

となる。

これら$C_o$，$S$を表す式へ， 式(4.4)の $M_0, M_1, \cdots$を代入すれば， 複数の入力のNOT，AND，ORを組み合わせればよいことが理解できよう。

これまでに述べた作業より，ありとあらゆる論理回路は， NOTとANDとORを使うことにより実現できることが理解できよう。 また，NOT，AND，ORの配置は， 真理値表の0，1の配置に合わせて組織的に行えばよいことも理解できよう。 こうした任意の論理回路の実現法をAND-OR回路（AND-OR circuit）と言う。