第4章 組合せ論理回路
論理関数の簡単化を一般化
ブール代数の定理
系統的なアルゴリズムへ
概要






簡単化
標準形、最小項、最大項
Karnaugh 図による簡単化
乗法標準形
組合せ禁止 (don’t care)
Quine-McCluskey の方法
組合せ回路と簡単化

組合せ回路
Z  f ( x1 , x2 ,, xn )
入力 ( x1 , x2 ,, xn ) が決まれば,出力 Z  f
が一意に決まる.
– 信号が一方向に流れている回路

順序回路
– 出力が現在の入力だけでは決まらない.
– 信号にフィードバックがある
論理式の次数

変数が演算を受ける最大回数
– 演算は論理積と論理和 ただし否定を除く
– 最も多くの基本ゲートを通る入力変数の段数
2次回路
3次回路
4次回路
簡単化


最も少ないハードウェアによる回路とは?
ゲートと配線の量を最小化
– ゲートの個数が最小
– 同数の場合には入力の個数が最小


解けない!
スピードを最も重視 → 2次の論理式
– なぜか?
簡単化
2次の論理関数
ゲートの最も少ない形
ゲートの数が同数ならば入力数が最小
論理式の最小化

ブール代数の公式による方法
– 系統的な方法がない - 経験的
– 最も簡単になったかどうかの保証がない

図による方法 (Karnaugh 図)

表による方法 (Q-M 法)
標準形

定義
– リテラル
– 積項
変数またはその補元
リテラルがANDで連なったもの
A  X  D , A  B  D  E, 
– 和項
リテラルがORで連なったもの
AB D, ACD E,
– 正規項
同じ変数が2回以上出てこない項
積和形式/和積形式

積和形式 - 加法標準形
ACD  BCD  ACD  C

和積形式 - 乗法標準形
( A  C  D)(B  C) A
積和
和積
例題 積和形式で表せ

変数以外に否定 → De Morgan の定理

変数以外に否定 → De Morgan の定理
AB  A  B
A B  A  B
最小項/最大項

最小項 (minterm)
– すべての変数が1回ずつ含まれる積項
A B , A B, AB , AB

最大項 (maxterm)
– すべての変数が1回ずつ含まれる和項
A  B , A  B, A  B , A  B
標準形 (定義)

主加法標準形
=(最小項)+(最小項)+・・・
積項がすべて最小項
3変数  ABC  AB C

主乗法標準形
=(最大項)×(最大項)× ・・・
和項がすべて最大項
3変数  ( A  B  C)( A  B  C )

例題
標準形の存在定理(1)
【定理】 任意のn変数論理関数は一つの主
加法標準形で表すことができる.

補題
任意の
について
が成り立つ

補題の証明
–
X 1  0 のとき
左辺 f (0, X1, X 2 ,, X n )
右辺 f (0, X1, X 2 ,, X n )  0  f (1, X1, X 2 ,, X n )  0
–
X 1  1 のとき
左辺 f (1, X1 , X 2 ,, X n )
右辺 f (0, X1, X 2 ,, X n )  1  f (1, X1, X 2 ,, X n ) 1

定理の証明
n  1 の場合は補題から明らか
で n  1 とおけば
f ( X1 )  f (0) X1  f (1) X1
n  n  1 の場合に定理が成り立つとする.
g0 ( X 2 , X 3 ,, X n )  f (0, X 2 , X 3 ,, X n )
g1 ( X 2 , X 3 ,, X n )  f (1, X 2 , X 3 ,, X n )
とおき g0 , g1 に定理( n  n  1 )を適用する.その
結果を次に代入
標準形の意味
f (0,0,,0), f (0,0,,1), , f (1,1,,1)

f (0,0,,0), f (0,0,,1), , f (1,1,,1) は
関数 f の真理値表の値である.

真理値表で1になる項だけが生き残る.

積項の形 → f () の中で 0 に対応する変
数に否定がつく.
X1X 2 X 3
項
X1X 2 X 3
000
X1 X 2 X 3
100
X1 X 2 X 3
001
X1 X 2 X 3
101
X1 X 2 X 3
010
X1X 2 X 3
110
X1X 2 X 3
011
X1X 2 X 3
111
項
X1X 2 X 3
標準形の存在定理(2)
【定理】 任意のn変数論理関数は一つの主
乗法標準形で表すことができる.
最小項による関数の表現

省略記法の導入
行番号が3とは
4
f  1 となる行番号だけを
取り出す
4
4
4

主加法標準形は
– どれか1つの最小項が1になれば f  1 となる.
– 最小項はすべてのリテラルを含む.
最小項=1 → たった一つの入力変数の組
入力の組合せ → 一つの最小項だけが1
ABC  011
A BC  0 11  1
0 11
ABC  011
4
A BC  1
m3
mk は行番号 k の
入力に対して 1
となる最小項
4
4
4
000

主加法標準形
100
101
111
真理値表
– f  1 となる最小項の数え上げ
双対性

最大項
M k は行番号 k の入力に対して 0となる最大項
M k  mk
1
0
0
主乗法標準形
f  0 となる行番号の列挙
ダウンロード

スライド タイトルなし