2015-04-19

AND、ORだけではNOT回路は作れないのか

「コンピュータシステムの理論と実装」読書会のときの疑問を追っかけて考えてみました。

NotとAnd/Orからならすべての論理回路が作れることは分かりました。ではAnd、OrのみからNot回路は作れないのでしょうか?
直感的に「作れない」って感じるんですが、きちんと論理的に説明するのはけっこう難しい気がします。

ではどうやったら説明できるか。

Notは1入力1出力の回路です。まずは入力をaとおきます。最初の入力の可能性としてはa、定数0、定数1のどれかしかありません。
最初の入力から次の出力の可能性は次の表の通りです。やっぱりa,0,1のどれかになってしまいます。

入力1 入力2 And出力 Or出力
a 0 0 a
a 1 a 1
a a a a
0 0 0 0
0 1 0 1
1 1 1 1


つぎに1出力ってことを考えます。And、Orのみで回路を作るならケーブルをまとめる最後の素子はAndまたはOrのどっちかになります。そして回路の最初の入力も次の出力もa,0,1になってるので、最後の出力もやっぱりa,0,1になってしまう。
雑に図解するとこんな感じ。


途中の回路がどんな複雑でもAnd/Orのみなら中間出力も変わらないので、最後の論理素子の入力も変わらない。だから最後までNot aを作ることはできない。


……という説明を考えてみたけど、なんだかすっきりしない。背理法か何かでさっぱりと証明する方法はないのかなー。




追記:ツイートしたら@chiralさんが速攻で返信くれました。だいぶすっきりした!

2015-04-17

#nandris コンピュータシステムの理論と実装 読書会(2) に参加してきました

「コンピュータシステムの理論と実装」は論理回路から順を追ってコンピュータの仕組みを知ろうという教科書です。
Nand回路から初めて論理回路、加算器から機械語、OSや高級言語のコンパイラを経てテトリスを作っちゃおうという、デアゴスティーニでやりそうな構成。

この本の内容はNand2Tetrisというオンライン学習コースで、私はこのTED Talksで知りました。