今日の料理
はじめに
最近始めたことの一つに、「Coursera」の「Build a Modern Computer from First Principles: From Nand to Tetris 」というコースを受けはじめたというのがある。最近だと、日本語訳された教科書として『コンピュータシステムの理論と実装 ―モダンなコンピュータの作り方』がある。もしかしたら、ここに書かれることは、この本と被ることがあるかもしれないけれども、とりあえず復習がてら、この辺りについてメモしておくことにする。
論理学からはじめよう
この講義においては、まず最小ユニットである論理ユニットを作ることから始めている。論理ユニットとは、論理学における式を回路的に実現するものである、というように理解している。
とはいえ、いきなりこんなことを言われても、あまりにも前提が多すぎるので、まず論理学の初歩的なおさらいをしよう。
まず、「似非原さんは貧乏であり、まだ、プログラミングができる」という文を考えてみる。
この場合、二つの命題が存在していることがわかる。それは「似非原さんは貧乏である」ということと、「似非原さんはプログラミングができる」という二つの命題がある。これらの命題は、個別にそれぞれの真偽を問うことができる。たとえば「似非原さんはプログラミングができる」という解いにたいして「んなことはないたろう」ということができる。
確かに、命題個別で見た場合、このような判断ができるわけだけれども、この文は「または」で、二つの命題が繋がっていることがポイントとなっている。「または」ということは、「似非原さんはプログラミングができる」ということが嘘だったとしても、「似非原さんは貧乏である」ということが真であるならば、この文全体は真と捉えることができる。
このように考えた場合、ある命題が「真か偽か」は兎も角として、その接続において、それぞれの命題が真か偽であるかに応じてパターンが作れることがわかる。そこで、このような「肯定形の単文(これを単純命題と呼ぶ)」を「P, Q, R」といったなどの文字(これを原子式と呼ぶ)にして、その繋がりにおけるパターンを考察しようということになる。
先の「似非原さんは貧乏である」をPとし、「似非原さんはプログラミングができる」というのをQとしよう。このとき、「P または Q」とすることができる。もっと記号に直すならば、ということになる。そして、これらの記号のことを結合子と呼ぶ。
果して、これで十分なのか
とりあえず、これら式の取りうる真偽のパターンに関しては、他の論理学入門や、そういうサイトに載っているので、ここではそちらにおまかせするとして、基本的な組みあわせとしては、の四つが上げられる。果して、この四つは全ての論理パターンを表現することが可能だろうか。
まず、最初に「全ての論理パターンを表現する」というのはどういうことかについて考えてみる。ここで、抽象的に、「ある真偽値を受け取ったときに、なんらかの真偽値を返す」ものして考える。このとき、とりあえず「あるいは」とか「または」といった接続をカッコに入れて、真理関数という考え方をする。
たとえば、「似非原さんは性格が良くない」という命題を、上のように「Pではない」とすることができる。このとき、論理記号として「」と表現できる。この
は、一つしか変数を取らない(この場合はP)ため、一次変数が取りうるパターンは次のようになる。また話を簡単にするために、真偽について、0を偽に、1を真という風に、真偽値にマッピングするようにする。
P = 1, f-1 = 1, f-2 = 1, f-3 = 0, f-4 = 0 P = 0, f-1 = 1, f-2 = 0, f-3 = 1, f-4 = 0
このとき、f-1はで実現できるし、f-2はPそれ自身で表現できる。また、f-3は
だし、f-4は
となる。
直感的に考えるならば、これは一次変数だから手で手当たり次第作っていけば、確認はできる。しかし、4次変数であったり、あるいは5次変数など、変数の数が増えるに従って、手作業で作っていくことは困難になる。
これには、既に「表現定理、関数的完全性の定理」というものが存在している。これはのみの結合子によって、n変数の真理関数が全て表現できるということがわかっている。これらについて、詳しく知りたければ、『論理学をつくる』を参照にするといい。
このように、すくない結合子でn変数の真理関数をすべて表現できることを、十全であると言う。
もうすこし少くできないものなのか
さて、「表現定理、関数的完全性の定理」についてはわかった。しかし、ここで一つの疑問が浮びあがる。それは、本当に先ほどの三つが本当に最低限なのだろうか、ということである。結論からすれば、もっと減らすことが可能である。
発想としては、この「表現定理、関数的完全性の定理」であげられている三つの結合子の一つについて、他の結合子が表現できればよい。たとえば、実際にとして、
は表現ができる。すると、実際のところ、結合子は
だけでいいということになる。
さらにもうすこし考えてみよう。もしを表現できるような適切な結合子があるのならば、そちらを使ったほうがいいだろう。そこで、Not AND、つまりNANDと呼ばれるものを導入する。これがなんなのか、といえば文字通り、ANDを反対にしたものだが、直接理解しようとするよりも、真理表を見たほうが早い。
P = 0, Q = 0, P nand Q = 1 P = 1, Q = 0, P nand Q = 1 P = 0, Q = 0, P nand Q = 1 P = 1, Q = 1, P nand Q = 0
このNAND、一つで十全のために、シェーファー関数と言われている。シェーファー関数とは、それ一つで十全となるような関数のことである。2変数で十全である関数はNANDと、その兄弟であるNot OR、つまりNORだけであることが知られている。
コーディングして確かめてみる
とはいえ、このように説明されたとしても、本当にNANDだけで全てのn変数の真理値が表現できるのかという疑問が出てくる。そこで、コーディングして、このあたりを確かめてみよう。
NANDの実装
まず、テストケースでNANDにあたるメソッドを定義する。Rubyの場合、true
とfalse
は、TrueClass
とFalseClass
に分かれている。それぞれにnand
というメソッドをオープンクラスで生やし、それをテストしてみる。
nand
の真理表を見た限りでは、p
とq
がtrue
であるときのみfalse
を返せばいいということになる。従って
:
require 'minitest/unit' class TrueClass def nand(q) !q end end class FalseClass def nand(q) true end end class TestNAND < Minitest::Unit::TestCase def test_nand assert_equal true.nand(true) assert true.nand(false) assert false.nand(true) assert false.nand(false) end end if $0 == __FILE__ require 'minitest/autorun' end
ということになるはずだ。
NOTの実装
このnand
を元に、not
を定義しよう。nand
からnot
を定義する場合、P nand P
とすることで、not
を定義することができる。これは、TrueClass
とFalseClass
に共通したものなので、module
として定義し、include
する。
module CustomLogic def not self.nand(self) end end # ... class TestNAND < Minitest::Unit::TestCase def test_not assert_equal true.not, false assert_equal false.not, true end end
ORの実装
では、今度はOR
を実装するにはどうしたらいいだろうか。結論から言ってしまえば、(X NAND X) NAND (Y NAND Y)
ということになる。これを実装すると、次のようになる。
module CustomLogic def or(q) (self.nand(self)).nand(q.nand(q)) end end class TestNAND < Minitest::Unit::TestCase def test_or assert_equal false.or(false), false assert true.or(false) assert false.or(true) assert true.or(true) end end
ANDの実装
最後にand
の実装を行なう。発想としては、nand
を反転させればand
になるわけだから、not(P nand Q)
なのだが、not
をnand
で実装する場合、(P nand P)
とする必要があった。従って、(P nand Q) nand (P nand Q)
とする必要が出てくる。
module CustomLogic def and(q) (self.nand(q)).nand(self.nand(q)) end end class TestNAND < Minitest::Unit::TestCase def test_and assert_equal false.and(false), false assert_equal false.and(true), false assert_equal true.and(false), false assert true.and(true) end end
最後に
ちょこちょこと論理学の勉強はかじっていたりし、論理回路の設計に関係していたことは知っていたけれども、あらためて、実際に頭の中で整理しながら作ってみると、そういうことだったのか、という驚きがあって良かった。また、こういったハードウェアの基礎的な理論について全くしらなかった自分にとっては、とても新鮮でよかった
次の週の授業は半加算器の実装理論のようなので、期待して動画を見たいと思う。また、機会があれば、日本語訳の教科書も手に入れたい。
文献リスト

コンピュータシステムの理論と実装 ―モダンなコンピュータの作り方
- 作者: Noam Nisan,Shimon Schocken,斎藤康毅
- 出版社/メーカー: オライリージャパン
- 発売日: 2015/03/25
- メディア: 単行本(ソフトカバー)
- この商品を含むブログ (3件) を見る

- 作者: 戸田山和久
- 出版社/メーカー: 名古屋大学出版会
- 発売日: 2000/10
- メディア: 単行本
- 購入: 27人 クリック: 330回
- この商品を含むブログ (108件) を見る