Panda Noir

JavaScript の限界を究めるブログです。

高校生でもわかる全加算器のつくりかた

何番煎じだよって感じだし、もうすでに一度このブログでとりあげています。でも、高校の教科書ながめていたら高校数学の内容で十分理解できるときがついたので書き直します。

まずはじめに

高校数学で上に向いた弧みたいなのありますよね?あの「〜かつ〜」っていう記号です。あれを×とします。「〜または〜」を+とします。否定は^とします。すると、「AかつB」はA×B、「AまたはB」はA+B、ドモルガンの法則は^(A×B)=^A+^Bとなります。

ここまでいいでしょうか?では、次ぎにいきます。「〜かつ〜」を満たすならば真、「〜かつ〜」を満たさないならば偽とします。例えば「田が含まれていて中がついていない名字のひと」という条件があるとします。すると、山田さんは真、田中さんは偽、上原さんも偽、中山さんも偽となります。では、「田が含まれているもしくは中がついていない名字のひと」となるとどうなるでしょうか?答えは山田さんは真、田中さんは真、上原さんは真、中山さんは偽となります。

この「〜さん」はどうかを調べるのを「〜さんを条件式に入力する」といいます。また、「〜さん」は入力、返ってきたものを出力と呼びます。

まとめると、「「田が含まれているもしくは中がついていない名字のひと」という条件式に田中さんを入力すると、真という値が返ってくる」となります。

本題

では本題の全加算器を作っていきます。まず、入力と出力があります。当然ですね。入力は、足す数字2つと、下の位からの繰り上がりの3つです。ただし、数字は2進法で、1けたとします。こうすることで、数字を真と偽であらわせるからです。これから出る数字は、0=偽、1=真とします。

まずはA+B

まず、足す数字2つについて考えていきましょう。2つの数字をA、Bとします。A、Bの値は2進法なので、1か0です。つまり、A、Bを足した結果は4通りとなります。1つずつみていきましょう。

ではA=0でB=0のとき。これは0+0なので0ですね。A=0、B=1のときは0+1なので1です。A=1、B=0のときは1+0なので1です。A=1、B=1のときは1+1=10です。2進法なので1+1=2ではないです。ここで注意です。あくまでここの+は「〜または〜」の+ではありません。

さて、ここで出力の問題です。出力ももちろん2進法の数字です。しかし、A=1、B=1のとき出力は10となり2けたとなります。どうすればいいのでしょうか?答えは「2つの数字を出力する」です。そうすれば解決です。

では、考えていきましょう。出力は一桁目をS(Sum)、二桁目をC(Carry out)とします。A=0、B=0のときにS=0、C=0となればいい…と考えていくとややこしいので、Sが1(真)となるときとCが1(真)となるときを考えます。ここでさきほどの田中さんの例がでてきます。条件式をつくってSに出力をいれればいいのです。入力はもちろんAとBです。どのように式をたてるといいのかをみていきます。

A=1、B=0のとき、A=0、B=1のときにS=1となりますよね。つまり、「Aが真かつBが偽」もしくは「Aが偽かつBが真」のときとなります。これを式にした(A×^B)+(^A×B)がSの条件式です。ちなみにこの条件式は排他的論理和といいます。

次にCについてみていきます。Cが1となるのはA=1、B=1のときです。みたまんま「Aが真かつBが真」なのでこちらはA×Bとなります。

いよいよA+B+Xです。

さて、あとは同様に下の位からの繰り上げ(以下Xとします)もふくめてやればいいのか…と思いきや、もっと楽にする方法があります。

それはA+Bの結果にXをたすのです。ただ、このままでは問題があります。われわれが作ってきたA+Bをするものは、2桁の数字を入力することができません。

でも安心してください。よく考えると答えが見えてきます。まず、A+Bの一桁目とXを足せば少なくともSの値はわかります。これは筆算をみるとよくわかります。2桁目がなにであろうと1桁目の足し算に影響しませんよね。これでSはわかりました。A+BのSとXを足して終わりです。でもCはどうでしょうか?難しいですね。でも、場合わけすればすぐわかります。まず、Cが1となるのは

  1. A=1、B=1、X=0となるとき
  2. AまたはBが1でXが1のとき
  3. AもBもXも1となるとき

の3つです。ここで、1と3に注目するとA=1、B=1ならXに関係なくC=1となることがわかるでしょうか?つまりA+BのCが1ならCは1となります。つぎにAまたはBが1でXが1のときというのはつまり、A+B+X=10のときとなります。よく考えてみてください。これはつまり、A+Bが1でXが1のときをさしています。A+Bが1桁なのです。ここが重要なのです。つまり、A+Bの1桁目とXを足せばCがわかるということです。

以上をまとめると、A+B+Xの出力は、S=A+B+XのS、C=「A+B+XのCが真またはA+BのCが真」です。これが全加算器です。これをつなげていくと整数どうしならすべてたせます。

終わりに

結局文章だけで小難しくなって高校生に理解できない内容になってしまったかもしれません…すいません