前回,ものすごく流していたところを掘り下げていきます。
ブール代数
ここでは今回出てくるものだけを紹介します。
二進数なので0か1で考えます。数値以外にも,0は偽(否定)の意味を持ちます。1は,真を表しています。左の図はベン図,右の表は真理値表といいます。

XOR(排他的論理和)AかBどちらかのみ1であれば1。記号A⊕B
AND (論理積)AかつBが1であれば1。記号 A・B
OR (論理和) Aまたは、Bが1であれば1。記号 A+B
二進数の足し算をブール代数を使って表すことができる?!
A+B=Sとします。最下位ビットをS,繰上りをⅭと表し,筆算すると図1のようになります。


図2ではS,Ⅽそれぞれの値を取り出して,表にしました。先程の真理値表と比べてみてください。表SはXOR,表CはANDの真理値表とそれぞれ同じになっています。つまり,最下位ビットはXOR,上位ビットはANDで表すことができるのです。
これを回路図にすると図3になります。

これが半加算器です。
繰上りについて
コンピューターは入・出力をそれぞれ別で行うため,本当は,半加算器だけではCを出力できません。
筆算をしていて,繰上った数を小さく書き,次の位を計算するときに忘れないようにすることがあるかと思います。図4はそれに似ています。黒い線と点線に挟まれているところが,繰上りを計算するスペースです。Zを下位からの繰り上りの入力,Ⅽを出力とします。


A,B,Zのすべての入力の組み合わせのそれぞれの場合のCの出力は,図5のとおりです。
Ⅽが1になる場合の組み合わせを論理式に表します。ここで,Aの否定は¬A,Bの否定は¬Bと表します。
①C=¬A・B・Z
②C=A・¬B・Z
③C=A・B・¬Z
④C=A・B・Z
C=①=②=③=④だから,
C=(¬A・B・Z )+( A・¬B・Z) + (A・B・¬Z)+(A・B・Z)
分配法則で
C=Z{(¬A・B)+(A・¬B)}+A・B(¬Z+Z)
上の式で(¬Z+Z)が出てきます。これは,「Zである,または,Zでない」なので,ベン図の全体を表します。つまり,1です。
まとめると
C={Z(A⊕B)}+{A・B(1)}


上記の式を回路図にすると図6になります。
よって,CはORで表すことができます。
これを先程の半加算器の略図を使い表すと図7になり,全加算器とになります。これでやっと1ビット+1ビットの繰上りありの足し算ができます。
前回は全加算器を2つ作ったので2ビット+2ビットで繰上りありの足し算ができます。
まとめ
このブログを書いていく中で自分が,なぜ繰上りが論理和で表すことができるのかをよく理解していないことに気づくことができました。やはりアウトプットは大切だと思いました。
今回,図を作成するために,Excel・PowerPointなどを使い方を調べながら活用できました。便利です。もっときれいで分かりやすい図を描けるように,活用していきたいです。
