ブール論理についての質問

Question

書籍コンピュータシステムの理論と実践の内容の、ブール論理について質問です。

And, Or, NotはそれぞれNandだけから作ることができるとありますが、その意味がいまいちピンとこなくて困っています。

x: 0 0 1 1
y: 0 1 0 1
Or: 0 1 1 1

上の真理値表だと、Orについて以下の式が成り立つことになります。

x Or y = -xy + x-y + x*y

また、書籍には、x Or y について、

x Or y = (x Nand x) Nand (y Nand y)
と表現されています。

どのようにして、Nandのみで上記の式を導出できるのでしょうか？

Answer 1

まずNANDがあればNOTを作ることができます。

###(NOT x) =(x NAND x)

当然、ORはNANDとNOTを組み合わせれば作ることができます。（いわゆるドモルガン律）

###**(x OR y) = (NOT (x NAND y) ) **

上の二つの式を組み合わせれば題意の式が得られます。

###(x OR y) = ( (x NAND y) NAND (x NAND y) )

** = ( (x NAND x) NAND (y NAND y) )**

###以下、2017/8/29追記**
と、ここまで書きましたが、考えてみたら普通に真理値表で全列挙したほうが早そうですね。４通りしかないので途中の変換式の説明よりも全列挙の方が早そうでした。m(_ _)m

Answer 2

x Or y = -xy + x-y + x*y

は x + y -xy じゃないですか？つまり

• x OR y = x + y - xy
• x AND y = xy
• NOT x = 1 - x

で計算できることになります。

そこで、NANDはNOT(X AND Y)と同値なので、以下のように変形していくことができます。
0. (x NAND x) NAND (y NAND y) = NOT(x AND x) NAND NOT(y AND y)
0. = NOT(NOT x AND NOT y)｛∵x*x=x｝
0. = 1 - (1 - x)(1 - y)
0. = 1 - 1 + x + y + xy
0. = x + y + xy
0. = x OR y

仕組みがわかると中学生の代数ですね

Answer 3

下記にわかりやすい解説があります。

NAND回路のみでANDやOR，XORや多数決回路を作る

Answer 4

NAND回路から1入力についてのNOT回路を作成できることは、

0 Nand 0 => 1
1 Nand 1 => 0

からすぐにわかります（2入力ともxかyとすればよい）。

そのため、

(x Nand x) Nand (y Nand y)

は

(Not x) Nand (Not y)

となります。

上記にド・モルガンの法則を適用すると

(Not Not x) Or (Not Not y)

となり、

x Or y

であることが分かります。

これを逆に考えていくと、最初の式となります。