マナビング基本情報技術者
回別一覧 →
総合トップへ

NANDだけで論理和ORを表す式の見分け方

基本情報技術者試験 平成29年度春期 午前 問3 ／ 基礎理論 › 離散数学

過去問にチャレンジ

平成29年度春期 午前 問3

XとYの否定論理積 X NAND Yは，NOT(X AND Y)として定義される。X OR YをNANDだけを使って表した論理式はどれか。

  1. ア

    ((X NAND Y) NAND X) NAND Y

  2. イ

    (X NAND X) NAND (Y NAND Y)

  3. ウ

    (X NAND Y) NAND (X NAND Y)

  4. エ

    X NAND (Y NAND (X NAND Y))

解答・解説を見る

会話形式の解説

講師講師
今回は、NANDだけを組み合わせてOR、つまり論理和を作る問題です。押さえておきたい道具は2つあります。同じ入力どうしのNANDが何になるかと、ド・モルガンの法則です。
受験者受験者
選択肢の式がどれもNANDの入れ子になっていて、読んでいるうちにどこを計算しているのか分からなくなってしまいました。
講師講師
式を1つずつ全部計算する前に、部品の意味を考えてみましょう。X NAND X は NOT(X AND X) ですね。X AND X は何になりますか。
受験者受験者
X AND X は X そのままなので、X NAND X は NOT X になります。同じものどうしのNANDは否定、つまり反転として使えるということですね。
講師講師
そのとおりです。次にORの書き換えです。ド・モルガンの法則を使うと、X OR Y は NOT(NOT X AND NOT Y) と表せます。この形とNANDの定義を見比べるとどうでしょうか。
受験者受験者
NOT(〇 AND △) はそのまま 〇 NAND △ なので、NOT X と NOT Y をNANDでつなげばいいはずです。NOT X は X NAND X、NOT Y は Y NAND Y なので、(X NAND X) NAND (Y NAND Y) の形の選択肢が正解だと思います。
講師講師
正解です。念のため値を代入して確かめておきましょう。X=Y=0 と、X=1, Y=0 の2組で計算してみてください。
受験者受験者
X=Y=0 のときは 1 NAND 1 で 0、X=1, Y=0 のときは 0 NAND 1 で 1 です。どちらもORの値と同じになりました。
講師講師
では、紛らわしい (X NAND Y) NAND (X NAND Y) を見てみましょう。左右が同じ式になっている点に注目してください。
受験者受験者
同じものどうしのNANDなので、X NAND Y を反転していることになります。NOT(NOT(X AND Y)) なのでANDですね。X=1, Y=0 を入れると0になり、ORの1と合いません。
講師講師
よくできました。残りの2つは入れ子が深いので、代入で確かめるのが早いです。3段にNANDを重ねた ((X NAND Y) NAND X) NAND Y に X=Y=0 を入れるとどうなりますか。
受験者受験者
内側の X NAND Y が1、それと X の0をNANDして1、最後に Y の0とNANDしても1です。ORなら0になるはずなので違いますね。
講師講師
そうです。整理すると、この式は NOT Y と同じ働きをします。最後の X NAND (Y NAND (X NAND Y)) も X=Y=0 で計算すると、内側から1、1と進んで、最後の 0 NAND 1 が1になります。こちらも整理すると NOT X と同じ働きの式です。
受験者受験者
X=Y=0 を入れるだけで、ORにならない式を2つ外せるんですね。式の形から考える方法と、代入で確かめる方法の両方を使えば、計算に時間がかかっても落ち着いて解けそうです。
講師講師
最後に補足です。NANDを組み合わせると、どんな論理式でも作れます。これを機能的完全性といいます。NOTは X NAND X、ANDは X NAND Y の結果どうしをもう一度NANDして反転する形、ORは (X NAND X) NAND (Y NAND Y) です。この3つの形を覚えておくと、似た問題にもすぐ対応できます。

まとめ

NANDだけでORを表すには、まず X NAND X が NOT X になる性質を使って各変数を反転します。ド・モルガンの法則により X OR Y は NOT(NOT X AND NOT Y) と書けるので、反転したもの同士をNANDでつないだ (X NAND X) NAND (Y NAND Y) がORになります。(X NAND Y) NAND (X NAND Y) はANDを表し、ほかの2つの式はそれぞれ NOT Y、NOT X と同じ働きをします。迷ったときは X=Y=0 や X=1, Y=0 を代入し、ORの真理値と合うかを確かめると、すばやく絞り込めます。

解答・解説

正解はイです

この問題のテーマ

NANDだけを組み合わせて論理和（OR）を作る問題です。NANDの定義とド・モルガンの法則を使えるかが問われています。

解き方の考え方

まず、同じ入力どうしのNAND（X NAND X）はNOT Xになることを押さえます。ORはド・モルガンの法則で「NOT X と NOT Y の論理積を否定したもの」と書き換えられるので、各変数を自分自身とNANDして反転し、その2つをNANDでつなげばORになります。式を見ただけで判断しにくいときは、X=Y=0 と X=1, Y=0 を代入し、ORの真理値（0と1）と同じになるか確かめます。

選択肢ごとの解説

  1. ×ア  ((X NAND Y) NAND X) NAND Y
    アの3段にNANDを重ねた式に X=Y=0 を代入します。内側の X NAND Y は1、それと X(=0)のNANDも1、最後に Y(=0)とのNANDも1になります。ORなら0になるはずなので一致しません。式を整理すると、この式は NOT Y と同じ働きをします。
  2. ○イ  (X NAND X) NAND (Y NAND Y)
    イの X NAND X は NOT X、Y NAND Y は NOT Y です。この2つをNANDでつなぐと NOT(NOT X AND NOT Y) になり、ド・モルガンの法則から X OR Y に等しくなります。代入で確かめると、X=Y=0 では 1 NAND 1 = 0、X=1, Y=0 では 0 NAND 1 = 1 となり、どちらもORの値と一致します。
  3. ×ウ  (X NAND Y) NAND (X NAND Y)
    ウは X NAND Y の結果を2つ並べてNANDしており、同じ入力どうしのNANDなので X NAND Y を否定したことになります。NOT(NOT(X AND Y)) は X AND Y なので、この式はANDを表します。実際、X=1, Y=0 では0になり、ORの1と一致しません。
  4. ×エ  X NAND (Y NAND (X NAND Y))
    エの入れ子になった式に X=Y=0 を代入すると、内側から順に1、1と計算が進み、最後の 0 NAND 1 で結果は1になります。ORの0と一致しません。X=1, Y=0 でも結果は0で、ORの1と食い違います。整理すると、この式は NOT X と同じ働きをします。

補足

NANDを組み合わせると、どんな論理式も作れます（機能的完全性）。そのため、NOT・AND・ORをNANDで作る形を覚えておくと、似た問題にもすぐ対応できます。

POINT

  • 同じ入力どうしのNAND（X NAND X）は NOT X として使えます。
  • ド・モルガンの法則から、X OR Y は NOT(NOT X AND NOT Y) と書き換えられます。
  • OR は (X NAND X) NAND (Y NAND Y) で作れます。
  • AND は X NAND Y の結果どうしをNANDし、もう一度反転すれば作れます。
  • 論理式の選択肢は、X=Y=0 などの少数の組を代入するだけでも絞り込めます。

※出典：平成29年度春期 基本情報技術者試験 午前 問3