応用情報技術者 2018年 春期 午前2 問21

否定付きANDの等価変形【午前2解説】

正解の理由

解法ステップ

1. 回路を変数で表す
   左側のAND（出力バブル）を N1 とし、右上・右下の各NANDを N2, N3、最終段をYとする。
   N1 = ¬(A ∧ B)
2. 右側の中段出力を式で表す
   N2 = ¬(A ∧ N1) = ¬(A ∧ ¬(A ∧ B))
   N3 = ¬(N1 ∧ B) = ¬(¬(A ∧ B) ∧ B)
3. N2, N3 を簡約する（分配・恒等を利用）
   A ∧ ¬(A ∧ B) = A ∧ (¬A ∨ ¬B) = A ∧ ¬B
   よって N2 = ¬(A ∧ ¬B) = ¬A ∨ B
   同様に N3 = ¬(¬A ∧ B) = A ∨ ¬B
4. 最終出力 Y を求める
   Y = ¬(N2 ∧ N3) = ¬((¬A ∨ B) ∧ (A ∨ ¬B))
   右辺を展開すると (A ∧ B) ∨ (¬A ∧ ¬B) となり、これの否定は排他的論理和（XOR）になる。
   したがって Y = A ⊕ B
5. 回路等価の視覚的／記号的変換
   NAND の出力バブルは De Morgan の法則により「入力側にバブルを付け、AND ↔ OR を入れ替える」ことで移動可能です。この操作を繰り返し、適切に簡約すれば選択肢ウと同等の表現に辿り着きます。

選択肢別の誤答解説

• ア：記号が漠然としており、元図のバブル（否定）が示す論理を満たしていません。単純なAND/ORのどちらかの一段で表現しているため、XORには一致しません。
• イ：ゲート形状が平坦な入力側を持つ（AND系）記号を示していますが、入力側・出力側のバブル配置や分岐の構成が元図と一致せず、等価になりません。
• ウ：元回路をDe Morganで変換・簡約した結果と一致します（問題の正解）。図中の入力バブルとゲート形状の組合せが、与えられたNANDの連結から得られる等価回路を表しています。
• エ：元図における出力バブル（NAND）をそのまま一段のゲートで表しただけのように見え、右側の2段構成と分岐を反映していないため等価ではありません。

よくある誤解

1. 「入力にバブルが付いたANDはNANDになる」
   誤りです。入力にバブルが付いたANDは $(\neg A)\wedge (\neg B)=\neg (A\vee B)$ であり、これはNOR（$\neg (A\vee B)$）に相当します。出力バブルと入力バブルの違いはDe Morganで明確に区別されます。
2. De Morgan の適用を符号（バブル）の移動だけで直感的に扱い、ゲートの種類（AND↔OR）を変換し忘れる
   出力にバブルがあるAND（NAND）は「出力バブルを入力側へ移すとORに入力バブルが付いた形」になる、という点を確実に押さえてください。

補足コラム

• De Morgan の法則（基本形）
  $\neg (X\wedge Y)=\neg X\vee \neg Y$
  $\neg (X\vee Y)=\neg X\wedge \neg Y$
  回路図上では「出力側に付いたバブル」を「両入力側のバブル」に移して、ゲートの種類をAND↔ORの間で交換する操作がこれに対応します。視覚的にバブルを移動させる練習をしておくと、回路の等価変形が速くなります。

FAQ