基本情報技術者 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 Y) NAND (X NAND Y)
  • $X\text{NAND}Y=\neg (X\wedge Y)$ を $Z$ と置くと、全体は $Z\text{NAND}Z=\neg Z=X\wedge Y$ となり、X AND Yを表します。OR ではありません。
• エ: 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$ である点を確認してください。
• AND と OR の変換を取り違えるケース。$(X\text{NAND}Y)\text{NAND}(X\text{NAND}Y)$ は AND、$(X\text{NAND}X)\text{NAND}(Y\text{NAND}Y)$ は OR です。

補足コラム

• 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