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で知りました。

独習コンピュータ教程



Nandからテトリスまでつなぎ目無く作っていくというのは、なんとなく冒険心を刺激されるものがありますね。
学習コースでは資料全部、ハードウェアシミュレータのようなツールも全部公開されてるので本当に独習できるんですが、全部英語なのが難点でした。
いつかやろうと思って放置してましたが日本語訳が出たというなら、今でしょッ! ということでちょうどよく開催されていた読書会に参加!

コンピュータシステムの理論と実装 読書会(2) - connpass



第2回は主に論理回路とブール代数でした。ここらへんは情報系工業高校に通った身なので死ぬほどやったところ。すごく懐かしかったです。
論理回路のキモはNand回路が一種類があればAnd、Or、Notがすべて構成できるってこと。さらにそれらを使ってつくるマルチプレクサなども作れます。

書いたHDLをハードウェアシミュレータで動かしてみることもできます。ハードウェアシミュレータ+今後必要なツールはここからダウンロードできます。

The Elements of Computing Systems / Nisan & Schocken



NandかNorから他の論理素子を作れることは分かったけど、別のものを元に論理素子を作ることは出来ないのかな? ということでマルチプレクサからAndとNotを作ってみました。
Andは $out = b \cdot sel$。

Notは $out = \overline{sel} $。

HDLのコードで書くとこんな感じ(HDLでは1,0はtrue,falseで表すらしい)。

CHIP Not {
    IN in;
    OUT out;

    PARTS:
    Mux (a=true, b=false, sel=in, out=out);
}

CHIP And {
    IN a, b;
    OUT out;

    PARTS:
    // Put your code here:
    Mux (a=false, b=a, sel=b, out=out);
}

元になる論理素子からNotが作れればなんとかなりそうですね。
And、OrだけじゃNotは作れないだろうけど、そのことってどうやって証明するんだろうなー。




ブール算術の章は2の補数のところまでで今回は終了。2の補数は2進数でマイナスの数を表す約束事ですが、これを採用すれば足し算回路だけで引き算も表現できるので超重要です。使わないと引き算回路も別に作らないといけなくなって不経済。
1の補数というのもあるのですが、これだと−0と+0が出来てしまって効率的じゃないのです。途中で@yshigeruさんが紹介してくれた式変形が、1の補数から2の補数への変化をわかりやすく表現していて良かったです。

\[ a + \overline{a} = -1 \]
\[ \overline{a} + 1 = -a \]



次回はちょっと長めですがそのぶんゆっくりできるでしょう。興味ある人はどうぞ。
コンピュータシステムの理論と実装 読書会(3) 休日編 - connpass







【おまけ】Nandのみで作ったAnd,Or,NotのHDLコード
NandOnly.hdl