ブール代数

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

前回の復習

○２入力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' = 1　　（１－７）

A・A' = ０　　（１－８）

４．ニ重否定則

A'' = A　　（１－９）

NOTゲート２段で、
信号は遅れるが、
元と同じ信号になる。

５．べき等則

A･A = A　　（１－１０）

A+A = A　　（１－１１）

６．分配則

A･(B+C) = (A･B)+(A･C)　　（１－１２）

A+(B･C) = (A+B)･(A+C)　　（１－１３）

７．結合則

２段の方が遅延時間小さい

A･(B･C) = (A･B)･C　　（１－１４）

A+(B+C) = (A+B)+C　　（１－１５）

８．吸収則１

AND-OR／OR-ANDで
同じ信号が入ると
おかしい！

A･(A+B) = A　　（１－１６）

A+(A･B) = A　　（１－１７）

A･(A'+B) = A･B　　（１－１８）

A+(A'･B) = A+B　　（１－１９）

９．ド・モルガンの定理

(A+B)' = A' ･B'　　（１－２０）

(A･B)' = A' + B'　　（１－２１）

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

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

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の項のみ残る。

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

入力A 入力B 出力 f(A, B)
0 0 f(0,0) = 0
0 1 f(0,1) = 1
1 0 f(1,0) = 1
1 1 f(1,1) = 0

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の項のみ残る。

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'　をブール代数の公式を用いて、証明せよ。
（左辺を変形してゆき、右辺にする）

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

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

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

入力A 入力B 入力C 　 出力C 出力S
0 0 0 　 0 0
0 0 1 　 0 1
0 1 0 　 0 1
0 1 1 　 1 0
1 0 0 　 0 1
1 0 1 　 1 0
1 1 0 　 1 0
1 1 1 　 1 1

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