応用情報技術者 2012年 秋期 午前2 問22

3入力多数決回路【午前2解説】

正解の理由

解法ステップ

1. 真理値表を確認し、出力が1となる行を列挙する：
   (A,B,C) = (0,1,1), (1,0,1), (1,1,0), (1,1,1)。
2. これらを被覆する最小の和形式（和項の和）を作ると、$AB,BC,AC$ の和で表せる。よって
   $Y=AB+BC+AC$。
3. 回路図に戻り、各選択肢が上の式をどのように実現しているかを確認する：
   • 直接 AND を並べて AB, BC, AC を作り、それらを OR で合成している回路が正しい（ア）。
   • 入力・出力に否定（バブルや波線）が付いているものは、否定の補償（追加の反転や適切な組合せ）がされているかをチェックする。補償されていなければ式と合致しない。

選択肢別の誤答解説

• ア（正解）
  • 左端の3つのANDがそれぞれ $AB,BC,AC$ を生成し、右側でこれらをORする構成は $AB+BC+AC$ を直接実現します。よって真理値表と一致します。
• イ
  • 左段のゲートに波線（逆相）があり、これらは基本記号の否定（例えばANDならNAND）を示します。イでは左の3つが NAND 的な動作（$(AB{)}^{\prime }$ など）になっているのに対し、最終段が否定なしの OR であるため、得られる出力は $(AB{)}^{\prime }+(BC{)}^{\prime }+(AC{)}^{\prime }$ のような形になり、$AB+BC+AC$ とは異なります。
  • 補足：NAND や NOR は関数完全で多数決も実現可能ですが、実現するには中間出力の否定を適切に取り扱い（追加の反転や別の接続）る必要があります。与えられた図では否定の補償がされておらず真理値が一致しません。
• ウ
  • 左側が OR 系、最終段が出力にバブル付きの OR（つまり NOR）になっています。左が OR を出し、それを中央で AND に入れたり最終で NOR にしている構成は、出力が元の $AB+BC+AC$ の否定や別の論理式になりがちです。図の結線では最終出力が1となる条件が真理値表の「少なくとも2つが1」には合致しません。
• エ
  • イ と同様に入力側に否定記号があり、最終出力もバブル付き（否定）になっています。個々の否定が適切に組合わされれば正しい多数決を作れますが、図面上の接続は必要な否定の数と位置が合っておらず、結果として期待する $AB+BC+AC$ になりません。

よくある誤解

1. 「NANDやNORは多数決を表現できない」
   • 誤りです。NAND/NORは関数完全で多数決を含む任意の論理関数を実現できます。誤りが起きるのは、図で示された否定（バブル・波線）の効果が回路全体で補償されていない場合です。
2. 「バブルや波線＝ただの装飾」
   • バブル（端点の丸）や波線は論理極性を示します（入力・出力の反転）。これを見落とすと論理式を逆に解釈してしまいます。
3. 「ORした negated terms = OR of original terms」
   • $(AB{)}^{\prime }+(BC{)}^{\prime }+(AC{)}^{\prime }$ は $AB+BC+AC$ ではありません。De Morgan の法則を使えば性質がわかりますが、否定付き項をそのまま合成しても元の和には戻りません。

補足コラム

• 多数決（3入力）の基本式は $Y=AB+BC+AC$。これを NAND のみで実装する一例を示します（代数変形）：
  De Morgan を使うと $$AB+AC+BC=\overline{\overline{AB+AC+BC}}=\overline{(AB{)}^{\prime }(AC{)}^{\prime }(BC{)}^{\prime }}$$ つまり、まず3つの NAND を使って $(AB{)}^{\prime }$, $(AC{)}^{\prime }$, $(BC{)}^{\prime }$ を作り、それらを入力とする3入力 NAND を用意すれば最終的に $AB+AC+BC$ が得られます。2入力ゲートのみの場合は段を追加して組合せれば同様に実現可能です。
• 回路図を見るときは「どこで否定されているか」を常に追跡し、最終出力が本当に元の論理式と一致するかを真理値で確認するのが安全です。

FAQ