NAND 演算があればあらゆる論理演算ができる
NAND とは NOT AND のことで、真理値表は次のようになる。
| x | y | x NAND y |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
見ての通りの、 AND の否定形である。否定にすぎないから、論理学ではそう注目される演算でもないように思う。
しかし電子回路の世界ではこの演算が中心の座を占めるといっても過言ではないらしい。というのも、 NAND 演算はそれ単独で、 AND, OR, NOT の論理を導出できるのである。AND, OR, NOT が使えればあらゆる論理が表現可能であるから、つまるところ NAND があればあらゆる論理が表現可能であるということにほかならない。
例えば、 x NAND x を真理値表に表してみる。 x が同時に 0 と 1 であることはないから、二行で十分となる。するとこれが、 NOT x となっていることは一目瞭然だ。
| x | x NAND x |
|---|---|
| 0 | 1 |
| 1 | 0 |
これを利用して、 x NAND y を否定してあげると、 AND が導ける。
| x | y | x NAND y | (x NAND y) NAND (x NAND y) |
|---|---|---|---|
| 0 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
同じように、 OR はこう表せる。
| x | y | x NAND x | y NAND y | (x NAND x) NAND (y NAND y) |
|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 | 1 |
