たとえば
a OR b は
a=1 b=1 なら 1
a=1 b=0 なら 1
a=0 b=1 なら 1
a=0 b=0 なら 0
(a AND b) は a=1 b=1 のときだけ 1
(a AND NOT b) は a=1 b=0 のときだけ 1
(NOT a AND b) は a=0 b=1 のときだけ 1
よって
a OR b = (a AND b) OR (a AND NOT b) OR (NOT a AND b)
つまり a,b がいくつの場合でも、左右の式は同じ値になる
こういう感じの置き換えをやるんだよ
具体的には
a AND b = 「a b NAND だけを使った式」となるように式をつくる
a OR b = 「a b NAND だけを使った式」となるように式をつくる
NOT a = 「a NAND だけを使った式」となるように式をつくる
a = NOT(NOT a)
NOT a = a NAND a
NOT (a AND b) = a NAND b
NOT (a OR b) = (NOT a) AND (NOT b)
まずこういった等式を用意しとくといいぞ
一つ目を使うと NOT を作り出せる
二つ目を使うと NOT を NAND に置き換えられる
三つめを使うと AND を NAND に置き換えられる
四つ目を使うと OR を AND に置き換えられる
a = NOT(NOT a)
NOT a = a NAND a
NOT (a AND b) = a NAND b
NOT (a OR b) = (NOT a) AND (NOT b)
一個目は否定の否定は元に戻る
二個目はさっき確かめた
三つ目は NAND の定義みたいなもん NOT AND で NAND
四つ目はドモルガンの法則
『「aまたはb」がなりたない』っていうのは『aでなく、かつ、bでもない』っていうのと同じでしょって話
たとえば
a AND b を作りたいとするわな。
AND を NAND にしたい。
3が使えそう。だけど NOT がたりない。
だからまず、1を使って
a AND b = NOT(NOT(a AND b))
すると内側に3が使えて
a AND b = NOT(a NAND b)
あとは NOT が邪魔だから 2で NOT を NAND に変える
a AND b = (a NAND b) NAND (a NAND b)