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

１．ブール代数の定義

公理１ 可換則 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の補元

２．ブール代数の公式集

１．可換則

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'

 トランジスタ数＝
６＋６＋６＋２＋２
＝２２

トランジスタ数は増えてしまった！

上記回路に対して、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

となる。

　

（乗法標準形）

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

HW-3　　学籍番号　名前　日付　を書いて　提出すること。

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

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

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

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

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

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

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

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

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

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)
=????????????????????

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

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

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

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

入力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

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

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

15）　以下の真理値表で与えられる回路を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

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

以上