ブール代数と組み合せ回路

前回の復習

○２入力NANDゲートのトランジスタレベルの回路図を書けるか？

○ANDの真理値表が書けるか？

○ORの真理値表が書けるか？

○ｎ入力NAND、NORゲートのトランジスタ数は？　

○ｎ入力AND、ORゲートのトランジスタ数は？

１．ブール代数の定義（教科書２．２．１）

• ブール代数の広い定義：　集合Lが与えられ、その任意の元（要素）A、Bに対して、２つの演算・、＋が定義される時、A・B、A+BはLの元であり、次の公理が成立する。

公理１	可換則	A･B=B･A A+B=B+A
公理２	結合則	A･(B･C) = (A･B)･C A+(B+C) = (A+B)+C
公理３	吸収則	A･(A+B) = A A+(A･B) = A
公理４	分配則	A･(B+C) = (A･B)+(A･C) A+(B･C) = (A+B)･(A+C)
公理５	相補則	最小限φと最大限Iが存在し、任意のAに対し A･A'=φ A+A'=I A'（教科書の表記と異なる）はAの補元

• 具体的には２値（’０’と’１’）を取る論理関数はブール代数となる。
  ○集合L：　元は’０’と’１’
  ○２つの演算・、＋をそれぞれ、ANDとORに対応させる。
  ○Aの補元A'を論理関数のAに対するNOTに対応させる。
  ○最大元Iは’１’、最小元φは’０’である。

• 任意の論理関数ｆ（A, B, C, ...）は’０’または’１’の値をとりLに属し、論理関数の集合はブール代数となる。
  すなわち、ブール代数の諸性質は、すべて論理関数に適用できる。

２．ブール代数の公式集

１．可換則
A･B = B･A　　（１−１） A+B = B+A　　（１−２）

２．吸収則
A+0 = A　　（１−３） A+1 = 1　　（１−４） A･0 = 0　　（１−５） A･1 = A　　（１−６）

４．ニ重否定則
A'' = A　　（１−９） NOTゲート２段で、 信号は遅れるが、 元と同じ信号になる。

５．べき等則
A･A = A　　（１−１０） A+A = A　　（１−１１）

３．例題（教科書２．１．４）

• ブール代数公理／定理により式を変換することで、異なる回路を作れる。
• このような、ある出力状態が、その時の入力状態の組み合せによって決定される論理回路を「組み合せ回路」もしくは「組み合せ論理回路」という。

f = (A+B)･(A･B)'　を実現すると		トランジスタ数＝ ６（NOR）＋６（AND）＋２（NOT）＋６（AND） ＝２０
式を変形する、 f = (A+B)･(A･B)' = (A+B)･(A'+B') =A･(A'+B') + B(A'+B') =A･A' + A･B' + B･A' + B･B' = 0 + A･B' + B･A' + 0 = A･B' + B･A'		トランジスタ数＝ ６＋６＋６＋２＋２ ＝２２ トランジスタ数は増えてしまった！

• 回路の変形方法
  ANDやORではなく、NANDやNORを使用する方が回路面積は小さい・

上記回路に対して、NOT２つを挿入	ドモルガンの定理適用（１６トランジスタで実現）

４．シャノンの展開定理（教科書２．３．２）

（加法標準形）

f(X1, X2, ..., Xi, ...Xn) = Xi ･ f(X1, X2, ..., Xi-1, 1, Xi+1, ..., Xn) + Xi ' ･ f(X1, X2, ..., Xi-1, 0, Xi+1, ..., Xn)

したがって、

f(A, B) = A･f(1, B) + A'･f(0, B) = A･(B･f(1,1)+B'･f(1,0) ) + A'･(B･f(0,1) + B'･f(0,0) )
f(A, B) = A･B･f(1,1) + A･B'･f(1,0) + A'･B･f(0,1) + A'･B'･f(0,0)

このような形 （加法標準形：入力信号またはその反転信号をANDし、 そのAND出力をORする形） に展開することができる。 結果的にｆ（A,B)=1の項のみ残る。

したがって、以下のような真理値表が与えられたら、

f(A,B) = A･B･f(1,1) + A･B'･f(1,0) + A'･B･f(0,1) + A'･B'･f(0,0) = A･B' + B'･A

となる。

• ある真理値表が与えられた時、「結果が１となる変数の値０，１のそれぞれの組み合わせについて、その値が１の時はそのまま、０の時はその変数をNOTし、すべての変数のANDをとった項をORで結ぶことで、論理関数を求めることができる。」

（乗法標準形）

f(X1, X2, ..., Xi, ...Xn) = (Xi + f(X1, X2, ..., Xi-1, 0, Xi+1, ..., Xn) ) ･ (Xi ' + f(X1, X2, ..., Xi-1, 1, Xi+1, ..., Xn) )

f(A,B) = (A+B+f(0,0)) ･ (A+B'+f(0,1)) ･ (A'+B+f(1,0)) ･ (A'+B'+f(1,1))

このような形 （乗法標準形：入力信号またはその反転信号をORし、 そのOR出力をANDする形） に展開することができる。 結果的にｆ（A,B)=0の項のみ残る。

• ある真理値表が与えられた時、「結果が０となる変数の値０，１のそれぞれの組み合わせについて、その値が０の時はそのまま、１の時はその変数をNOTし、すべての変数のORをとった項をANDで結ぶことで、論理関数を求めることができる。」

クイズ３　　学籍番号　名前　日付　を書いて　提出すること。

（注意：回路を設計する場合、特に明記しないが、なるべく少ないゲート数で実現せよ。）

A) ２入力NANDゲートのトランジスタレベルの回路図を書け

B) ２入力ANDの真理値表が書け

C) ２入力ORの真理値表が書け

D) ｎ入力NAND、NORゲートのトランジスタ数はいくらか？

E) ｎ入力AND、ORゲートのトランジスタ数はいくらか？

１）　教科書２．３．１の（２．２３）式　f(A, B, C) = A' ･B･C + A･B'･C + A･B･C' + A･B･C
をAND、OR、NOTゲート用いて回路図を実現せよ。総トランジスタ数はいくつか？

２）上記（２．２３）式をNAND、NOR、NOTを用いて実現せよ。総トランジスタ数はいくつか？

３）上記（２．２３）式を以下のように変形する。最後の式はどうなる？

f(A, B, C) = A' ･B･C + A･B'･C + A･B･C' + A･B･C
= (A' ･B･C+A･B･C) + (A･B'･C+A･B･C) + (A･B･C' +A･B･C)
=????????????????????

４）上記３）の結果式を、AND、OR、NOTゲートだけを用いて回路図を実現せよ（AND, OR, NOTの全てを用いる必要はない）。総トランジスタ数はいくつか？

５）上記３）の結果式を、NAND、NOR、NOTゲート用いて回路図を実現せよ（NAND, NOR, NOTの全てを用いる必要はない）。総トランジスタ数はいくつか？

宿題３　　学籍番号　名前　日付　を書いて　提出すること。

（注意：回路を設計する場合、特に明記しないが、なるべく少ないゲート数で実現せよ。）

１）　A･C + B･C' + A･B = A･C + B･C'　をブール代数の公式を用いて、証明せよ。
（左辺を変形してゆき、右辺にする）

２）　以下の真理値表で与えられる論理関数を乗法標準形で表せ。

３）　上記２）の乗法標準形をAND、OR、NOTゲートを用いて回路図を実現せよ（AND, OR, NOTの全てを用いる必要はない）。総トランジスタ数はいくつか？

４）　上記２）の乗法標準形をNAND、NOR、NOTゲートを用いて回路図を実現せよ（NAND, NOR, NOTの全てを用いる必要はない）。総トランジスタ数はいくつか？

５）　以下の真理値表で与えられる回路をNAND、NOR、NOTだけを用いて設計せよ（NAND, NOR, NOTの全てを用いる必要はない）。
（ヒント：この回路は加算器で、３つの入力の１の数を数えて、２桁の２進数（上位：C、下位：S）として出力する回路）
それぞれの出力Cと出力Sに関する論理式を加法標準形で求めて、回路図を作成すればよい。

２つの回路で同じ信号を共通に使用してもよい。

６）　上記５）で設計した回路の総トランジスタ数はいくらか？

以上