コンピュータ

論理回路

コンピュータが我々の期待通りに動作することを保証してくれる理論が「論理数学」である。論理数学とは「論理学」を数式化した学問といえるが、ここで述べるのは「2値論理」を扱う「ブール代数(Boolean Algebra)」と呼ばれるものである。ブール代数では、変数および関数値は「真」か「偽」、あるいはこれを数値に対応させた「1」か「0」の「2値」しか取らない。この変数に対し、次のような「論理関数」が定義され、これらの関数と同じ動作をする論理回路を組むことができ、これらの論理回路でコンピュータが構成される。

また、コンピュータが数の計算だけでなく、論理的演算もできることが、コンピュータを単なる「計算機」だけとしてでなく、本来、人間が判断して制御しなければならない処理手順を、人間に代わって「自動処理」するような用途でも活躍する「人工知能」としても仕立て上げている。

ここで述べる論理回路は「組合せ論理回路」と呼ばれるもので、この他に時間とともに状態の変化する「順序論理回路」がある。

ブール代数

ブール代数では、変数および関数値ともに「0｣か「1」しか取り得ないため、その変数が取りうる全ての組合せと、そのときの関数値を表にして表すことができる。この表を論理関数の「真理値表」という。変数が「A、B」の2つであるとき、それぞれの変数が「0｣か「1」しか取らなければ、変数値の全ての組合せは4通りになる。

またブール代数では以下の3つの関数が、基本関数として定義されている。

論理和(OR)

2つの変数A、Bがそれぞれ「0、1」の2値を取るとき、真理値表が表１で与えられる論理関数を論理和とよび、「A+B」として表される。この関数は、2つの変数のいずれかが「1」の場合、関数値が「1」になる。この関数を実現する回路は「OR回路」と呼ばれ、図１に実現回路例と回路記号を示した。

論理積(AND)

2つの変数A、Bがそれぞれ「0、1」の2値を取るとき、真理値表が表２で与えられる論理関数を論理積とよび、「A･B」として表される。この関数は、2つの変数の両方が「1」の場合にのみ、関数値が「1」になる。この関数を実現する回路は「AND回路」と呼ばれ、図２に実現回路例と回路記号を示した。

論理否定(NOT)

変数 A が「0、1」の2値を取るとき、真理値表が表３で与えられる論理関数を論理否定とよび、「」として表される。この関数は、変数が「1」の場合、関数値が「0」となり、変数が「0」の場合、関数値が「1」になる。この関数を実現する回路は「NOT回路」と呼ばれ、図３に実現回路例と回路記号を示した。

基本公式

ブール代数では以下の基本公式が使用でき、1〜5はブール代数の公理から導かれている。

1．	交換律	A･B = B･A	A+B = B+A
2．	結合律	A･(B･C) = (A･B)･C	A+(B+C) = (A+B)+C
3．	吸収律	A･(A+B) = A	A+(A･B) = A
4．	分配律	A･(B+C) = (A･B)+(A･C)	A+(B･C) = (A+B)･(A+C)
5．	補元律	A･ = 0	A+ = 1
6．	べき等律	A･A = A	A+A = A
7．	零元、単位元の性質	A･0 = 0、A･1 = A	A+0 = A、A+1 = 1
8．	ニ重否定律	= A
9．	ド・モルガンの定理	=+	=・

 計算の優先順位

ブール代数の計算の優先順位は、論理否定、論理積、論理和の順であり、「( )」で優先順位を上書きすることができる。

論理回路の合成

上記を応用して、所定の動作をする論理回路を作ることを考えてみよう。論理回路ではブール代数の変数が入力に対応し、関数値が出力に対応する。所定の動作をする論理回路を作る場合は次の手順による。

上記のように論理積の形の最小項を論理和の形で結んで論理関数全体を表す方法を「積和標準形」という。

半加算器

ここで、例として加算器を取り上げてみよう。ここで考える加算器は、一桁の2進数を足し合わせた結果である「和」と、加算の結果、「桁上がり」が生じたか否かを求める装置である。しかし、下位の桁からの「桁上り」は扱わないもので「半加算器」とよばれるものである。下位の桁からの「桁上り」を扱う「全加算器」は、後で述べるように、半加算器を使って作ることができる。

さて、半加算器の「和（S_H）」の出力は表４の真理値表のようにならなければならないことは理解できるであろう。論理回路が従うべき論理関数を、通常その回路の「論理式」とよんでいる。表４に「論理回路の合成」方法を適用して半加算器の論理式を求めると、表で関数（出力）が「1」になっているのは、備考欄が�Aと�Bの行であり、�Aの行は「A」が「0」で、「B」が「1」であるので 「・B」となり、�Bの行は「A」が「1」で、「B」が「0」であるので 「A・」であることから、「和（S_H）」の論理式は、

    S_H = ・B + A・

となる。

表６　S =・B+A･の検算

A	B			･B	A・	･B+A・
0	0	1	1	0	0	0
0	1	1	0	1	0	1
1	0	0	1	0	1	1
1	1	0	0	0	0	0

図５ 半加算器の論理回路

（A) （B)

表７ 全加算器の真理値表

No.	入力			出力
	A	B	C	SF （和）	COF （桁上り)
�@	0	0	0	0	0
�A	1	0	0	1	0
�B	0	1	0	1	0
�C	1	1	0	0	1
�D	0	0	1	1	0
�E	1	0	1	0	1
�F	0	1	1	0	1
�G	1	1	1	1	1

このように導かれた論理式が、与えられた真理値表を満足することは、上のブール代数の公式を用いて、表６のように検算することができる。

「半加算器」の「和（S_H）」は論理式「 S_H = ・B + A・」にしたがって、「OR」、「AND」、「NOT」の3種類の基本論理関数によって図５（A）のように合成することができる。

しかし、真理値表が表４のようになる関数は、これ自身がよく使われる関数であるため、「排他的論理和（Exclusive OR、XOR）」と名づけられており、図４の回路記号が与えられている。「排他的論理和」の演算記号は「」であり、

　S = AB

として表される。

また、表５の「半加算器」の「桁上り（C_OH）」については、表２の「AND」そのものにほかならないことが分かる。すなわち、

　C_OH = A・B

この結果、半加算器の論理回路は、図５（A）または（B)のようになる。

全加算器

半加算器では下位からの桁上りを考慮していなかった。これを考慮したものは「全加算器」とよばれるものであるが、これは入力「A」および「B」と下位桁からの「桁上り（C)」の、3入力の加算器にほかならず、その真理値表は表７のようになる。そこでこの「全加算器」の「和（S_F）」よび「桁上り（C_OF）」の論理式を「積和標準形」で求めてみると、

　S_F = A・・ + ・B・ + ・・C + A・B・C

　C_OF = A・B・ + A・・C + ・B・C + A・B・C

となる。しかし、これらの論理式はまだ簡単化できる余地を残しているため、これを例題として、論理式の簡単化の手法について述べることにする。

論理式の簡単化

論理式の簡単化とは、最小項の項数を最も少なく、それが同じであれば、各最小項の変数の数をもっとも少なくする方法で、理論的には「シャノンの展開定理」にしたがって行うことができる。しかし、この方法による簡単化はかなりの手数を要求するため、ここでは深入りしない。

また論理回路の簡単化は、いわば数学の因数分解に似ており、より効率的に行うためには、感覚的な要素が重要となってくる。そこでここでは、図式的に簡単化の要点を見出せる「ベン図（Venn diagram）」法を紹介する。

ベン図

ベン図では、論理関数の変数の範囲を図形で表す。通常は図６（A)のように円で囲まれた内側で変数「A」を、円の外側でその否定「」を表す。

図６　ベン図
（A）	（B）
（C)	（D)
（E)	（F)
（G）	（H）
（I）	（J）
図７ 全加算器のベン図
（A）　和(SF)
（B)　桁上り(COF)
(C)　簡単化の要点
図８ 半加算器の論理式のベン図
（A)　A･ + ･B
（B)　･ + A･B

2変数の場合は、2つの変数の円を、図６（B)のように互いに重なり合うように描き、それぞれの円の内側で変数を、円の外側でその否定を表すことになる。図（C)の黄色の部分が変数Aで灰色部分がとなる。これは変数Bでも同様で、図（D)の水色の部分がBで、灰色の部分がということになる。

では、論理関数のベン図はどうなるかというと、たとえば「A+B」は、「A」または「B」に属する（「A」か「B」のどちらかに属する）区域であるから、図６（E）の緑色の部分になり、その区域の外側の灰色の部分はということになる。また「A・B」は、「A」かつ「B」に属する（「A」および「B」の双方に属する）区域であり、図（F）の赤色の部分になり、その外側の灰色の部分はということになる。

また図６（G）の黄色の部分は、「A」で、かつ「B」の外側（）ということで、「A・」になり、その外側はその否定になる。

ここで基本公式「3．吸収律　A･(A+B) = A、A+(A･B) = A 」を例題に、論理簡単化について垣間見て見よう。「A･(A+B)」は、図６（E）の「A＋B」と図（C）の「A」の両者に属する区域で、ベン図で表すと図（H）のようになる。これから、「A･(A+B)」は「A+B」を無視して「A」そのものだけで表せることが分かる。

このように、論理式の中に含まれていながら、結果的には無視しうる項を「冗長項」といい、「論理式の簡単化」の１つの目的はこの冗長項を省くことにほかならない。

また、「A+(A･B)」は図（C）の「A」と図（F）の「A・B」のいずれかに属する区域ということで、図（I）のようになり、やはり「A」そのものになることが分かる。 

さらに、論理式の簡単化には、もう１つの狙いがある。それは、隣接した複数の最小項をまとめて、より少ない変数で表現することができないかを探るものである。たとえば、図６（J）の黄色の部分は「A・」で赤の部分は「A・B」である。ここで「A・＋A・B」の論理式を考えると、これも「A」そのものに置き換えることができることが分かる。

これを、式を変形する方法で確認すると、
A・ + A・B = A・(+B)
                = A・１　　　…補元律
                = A          …零元、単位元の性質
となる。

さて、これまで述べた論理式の簡単化の方法を、「全加算器」に適用してみよう。

全加算器の「和（S_F)」を表したものが図７（A）である。表７で関数値が「1」となっている最小項を色付けしてある。簡単化の観点からすると、冗長項、隣接最小項とも見当たらず、余り簡単化は望めない。ここでは、桁上りに対応する変数「C」に着目して、ブール代数の「分配律」をもとに、「C」と「」を含む項に分けて、次のようにまとめてみた。

　S_F = A・・ + ・B・ + ・・C + A・B・C
　　   =・(A・ + ・B) + C・（・ + A・B）

また、全加算器の「桁上り（C_OF)」にベン図を適用したものが図７（B）である。やはり表７で関数値が「1」になっている最小項を色付けしてある。こちらは、隣接した最小項が多く、簡単化の参考になる。

まず、変数「A」の円内に存在する最小項に着目してみると、�C、�F、�Gがある。これらのうちで、�C、�Gは変数「B」に属しており、�F、�Gは変数「C」に属していることが分かる。そこで、これを整理してみると、「桁上り（C_OF)」の最小項は図７（C）の「A･B」、「B・C」、「A・C」の区画に全てが、漏れなく含まれており、次のように式を変形することが可能である。

　C_OF = A・B・ + A・・C + ・B・C + A・B・C
　　　 = A・B + A・C + B・C

結局、簡単化とは、ベン図上の、隣接した最小項をまとめ、より少ない変数で論理式を表すことを考えることにほかならない。この例では 3 変数 4 項の論理式が 2 変数 3 項の式に簡単化されたことになる。

半加算器と全加算器の関係

これまで、加算器として、「半加算器」と「全加算器」があることについて述べた。これらの論理式にどのような関係があるのかは、これまでの説明では明確ではない。この関係を探ろうとすると、「論理式の簡単化」の常套手段に触れられる場面に遭遇することになるので、ここで考えてみよう。

上で、「全加算器」の「和（S_F)」が、

　 S_F = A・・ + ・B・ + ・・C + A・B・C
　　    =・(A・ + ・B) + C・（・ + A・B）

となることを示した。この内、第1項の「・(A・ + ・B)」は変数「A」、「B」を入力とする「半加算器」の「和（S_H1）」が「S_H1 = ・B + A・」であることを思い起こせば、「・S_H1」で表せることが分かる。

そこで、ここでは、次の式の変形を考えてみよう。半加算器の和「S_H1 = ・B + A・」の否定の展開である。

これに「ド・モルガンの定理（de Morgan's theorem）」を適用すると、

さらに「ド・モルガンの定理」を適用し、

これに「ニ重否定律」を適用すると、

さらに「分配律」を適用し、（）をはずすと、

「補元律」、「零元、単位元の性質」を考慮すると、上式は

となる。したがって、「S_F」の第2項は「C・₁」に等しいことが分る。

上は常套手段としての論理の簡単化であったが、ベン図を使うと、より簡単に結論に至ることができる。図８（A）は半加算器の和の論理式「S_H1 = ・B + A・」のベン図であり、図８（B）は「・ + A・B」のベン図である。これから容易に、「・B + A・」と「・ + A・B」が、「否定」関係にあることがわかる。

図９ 半加算器による全加算器の合成

以上から、「全加算器」の「和（S_F)」は、
　S_F = ・S_H1 + C・₁
と表されることが分かった。しかし、これは半加算器の入力を「A」、「B」から「C」、「S_H1」に代えたものである。したがって、全加算器の和（S_F)とは、「A」、「B」を入力とする半加算器の和（S_H1)の出力と下位からの桁上り（C)の両者を入力とした第２の半加算器の和の出力（S_H2)になることが分かる。

さらに、全加算器の桁上りは、

　C_OF = A・B・ + A・・C + ・B・C + A・B・C
　　　　= A・B･( + C) + C･(A・ + ・B) 
　　　　= A・B + C･( A・ + ・B) 
　　　　= C_OH1 + C・S_H1

となり、「A」、「B」を入力とする半加算器の桁上り（C_OH1)と上で述べた第２の加算器からの桁上り（C_OH2)の論理和になることが分かる。これを回路図として表したものが図９である。図で「HA」は半加算器を表している。