今日の料理

f:id:nisemono_san:20160508163306j:plain

はじめに

最近始めたことの一つに、「Coursera」の「Build a Modern Computer from First Principles: From Nand to Tetris 」というコースを受けはじめたというのがある。最近だと、日本語訳された教科書として『コンピュータシステムの理論と実装 ―モダンなコンピュータの作り方』がある。もしかしたら、ここに書かれることは、この本と被ることがあるかもしれないけれども、とりあえず復習がてら、この辺りについてメモしておくことにする。

論理学からはじめよう

この講義においては、まず最小ユニットである論理ユニットを作ることから始めている。論理ユニットとは、論理学における式を回路的に実現するものである、というように理解している。

とはいえ、いきなりこんなことを言われても、あまりにも前提が多すぎるので、まず論理学の初歩的なおさらいをしよう。

まず、「似非原さんは貧乏であり、まだ、プログラミングができる」という文を考えてみる。

この場合、二つの命題が存在していることがわかる。それは「似非原さんは貧乏である」ということと、「似非原さんはプログラミングができる」という二つの命題がある。これらの命題は、個別にそれぞれの真偽を問うことができる。たとえば「似非原さんはプログラミングができる」という解いにたいして「んなことはないたろう」ということができる。

確かに、命題個別で見た場合、このような判断ができるわけだけれども、この文は「または」で、二つの命題が繋がっていることがポイントとなっている。「または」ということは、「似非原さんはプログラミングができる」ということが嘘だったとしても、「似非原さんは貧乏である」ということが真であるならば、この文全体は真と捉えることができる。

このように考えた場合、ある命題が「真か偽か」は兎も角として、その接続において、それぞれの命題が真か偽であるかに応じてパターンが作れることがわかる。そこで、このような「肯定形の単文(これを単純命題と呼ぶ)」を「P, Q, R」といったなどの文字(これを原子式と呼ぶ)にして、その繋がりにおけるパターンを考察しようということになる。

先の「似非原さんは貧乏である」をPとし、「似非原さんはプログラミングができる」というのをQとしよう。このとき、「P または Q」とすることができる。もっと記号に直すならば、 ${P \lor Q}$ ということになる。そして、これらの記号のことを結合子と呼ぶ。

果して、これで十分なのか

とりあえず、これら式の取りうる真偽のパターンに関しては、他の論理学入門や、そういうサイトに載っているので、ここではそちらにおまかせするとして、基本的な組みあわせとしては、 ${ \land , \lor , \lnot , \to }$ の四つが上げられる。果して、この四つは全ての論理パターンを表現することが可能だろうか。

まず、最初に「全ての論理パターンを表現する」というのはどういうことかについて考えてみる。ここで、抽象的に、「ある真偽値を受け取ったときに、なんらかの真偽値を返す」ものして考える。このとき、とりあえず「あるいは」とか「または」といった接続をカッコに入れて、真理関数という考え方をする。

たとえば、「似非原さんは性格が良くない」という命題を、上のように「Pではない」とすることができる。このとき、論理記号として「 ${\lnot P }$ 」と表現できる。この ${\lnot}$ は、一つしか変数を取らない(この場合は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は ${P \lor \lnot P}$ で実現できるし、f-2はPそれ自身で表現できる。また、f-3は ${\lnot P}$ だし、f-4は ${\lnot (P \lor \lnot P)}$ となる。

直感的に考えるならば、これは一次変数だから手で手当たり次第作っていけば、確認はできる。しかし、4次変数であったり、あるいは5次変数など、変数の数が増えるに従って、手作業で作っていくことは困難になる。

これには、既に「表現定理、関数的完全性の定理」というものが存在している。これは ${\land , \lor , \lnot}$ のみの結合子によって、n変数の真理関数が全て表現できるということがわかっている。これらについて、詳しく知りたければ、『論理学をつくる』を参照にするといい。

このように、すくない結合子でn変数の真理関数をすべて表現できることを、十全であると言う。

もうすこし少くできないものなのか

さて、「表現定理、関数的完全性の定理」についてはわかった。しかし、ここで一つの疑問が浮びあがる。それは、本当に先ほどの三つが本当に最低限なのだろうか、ということである。結論からすれば、もっと減らすことが可能である。

発想としては、この「表現定理、関数的完全性の定理」であげられている三つの結合子の一つについて、他の結合子が表現できればよい。たとえば、実際に ${\lnot( \lnot X \land \lnot Y)}$ として、 ${\lor}$ は表現ができる。すると、実際のところ、結合子は ${\land , \lnot}$ だけでいいということになる。

さらにもうすこし考えてみよう。もし ${\land , \lnot}$ を表現できるような適切な結合子があるのならば、そちらを使ったほうがいいだろう。そこで、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

最後に

ちょこちょこと論理学の勉強はかじっていたりし、論理回路の設計に関係していたことは知っていたけれども、あらためて、実際に頭の中で整理しながら作ってみると、そういうことだったのか、という驚きがあって良かった。また、こういったハードウェアの基礎的な理論について全くしらなかった自分にとっては、とても新鮮でよかった

次の週の授業は半加算器の実装理論のようなので、期待して動画を見たいと思う。また、機会があれば、日本語訳の教科書も手に入れたい。