基本情報技術者 2017年 春期 午前（科目A） 問03

NANDによる論理和の表現【午前解説】

正解の理由

解法ステップ

1. NAND の定義を書き出す：$A\text{NAND}B=\neg (A\wedge B)$.
2. 各候補式で自己NANDがあればそれが $\neg$ に相当することを置き換える。
3. デ・モルガンの法則$\neg (\neg X\wedge \neg Y)=X\vee Y$を適用して OR に簡約できるか確認する。
4. 明らかに NOT X や NOT Y になる式は OR にならないので除外する。

選択肢別の誤答解説

• ア: ((X NAND Y) NAND X) NAND Y
  • 簡約すると $\neg Y$ になります。理由：$A=\neg (X\wedge Y)$ と置くと中段が $\neg (X\wedge \neg Y)=\neg (X\wedge \neg Y)$ になり、最終的に全体は $\neg Y$ に帰着します。よって OR ではありません。
• イ: (X NAND X) NAND (Y NAND Y) → 正解
  • $X\text{NAND}X=\neg X$ を用いれば $\neg (\neg X\wedge \neg Y)=X\vee Y$ に等しいため正解です。
• ウ: (X NAND X) NAND (Y NAND Y)
  • 表記はイと同一で論理的には同じ式です。問題の正答として指定されているのはイですが、ウが同一であれば理論上同値になります（表記重複に留意）。
• エ: X NAND (Y NAND (X NAND Y))
  • これを簡約すると $\neg X$ になります。中間部分を計算すると $Y\text{NAND}(X\text{NAND}Y)=\neg (Y\wedge \neg (X\wedge Y))=\neg (Y\wedge \neg X)=\neg Y\vee X$、さらに全体の NAND により最終は $\neg X$ に帰着します。よって OR ではありません。

よくある誤解

• 「NANDを使えばどんな並びでも同じ結果になる」と考える誤り。順序や括弧で結果は大きく変わります。
• 自己NANDがNOTになることを忘れて直接置き換えるミス。$X\text{NAND}X$ が $\neg X$ である点を確認してください。
• 選択肢の表記ミス（同一の式が複数ある）に気づかず、混乱してしまうケース。問題文と選択肢を正確に比較しましょう。

補足コラム

• NOT: $\neg X=X\text{NAND}X$
• AND: $X\wedge Y=(X\text{NAND}Y)\text{NAND}(X\text{NAND}Y)$（NANDを2回使う）
• OR: $X\vee Y=(X\text{NAND}X)\text{NAND}(Y\text{NAND}Y)$（本問の変換）
  電子回路設計でもNANDゲートは安価で高速なため、しばしば基本要素として用いられます。

FAQ