論理回路#5 カルノー図による論理式の簡単化

コンピュータアーキテクチャI #5
カルノー図による論理式の簡単化
平成27年5月15日
教科書:p.40~49,p.60~62
本日の講義内容
論理関数の簡単化
 論理演算による方法
– ミスしやすい
– 見通しが悪い
– 項の選び方により,簡単化が行き詰まる

カルノー図による方法
– 減らせる項を視覚的に選ぶことが可能
– 機械的に作業でき,ミスが少ない
– 論理変数が多くなると対応できない
論理関数の簡単化とは

論理式の項数を少なくすること
– ド・モルガンの定理や各種ブール代数の公理・定理を駆使
して項数を減らす

論理式で使われている演算子を統一すること
– 完全系を成すNANDやNORのみで論理式を記述し,必要
な部品の種類を減らす
論理式の簡単化の例(1)

与えられた論理式:
 =  +  +  + 
–
 +  =   +  = 
–
 +  =   +  = 
–
 +  =  +   = 
 =  +  + 
論理式の簡単化の例(2)
与えられた論理式
 =   +  +  
+  +    + 
+   + 
 =  +  +   + 
 =  +  + 
カルノー図とは何か
カルノー図
 論理式を図(表)で表す一つのやり方
 論理変数の数が6程度までの論理式に対応可能
B
A
0
0
1
0
0
0
1
1
2変数のカルノー図
AND(F=A・B)を示すカルノー図
3変数のカルノー図
C
A
B
0
1
0
0
1 1
0
1
1
1
1
1 1
1
0
1
3変数のカルノー図

3変数論理関数:
 =  +    + 
– 対応するA,B,Cの個所に1
を書く
– それ以外のマス目には0を
入れる

式中の積項に含まれない
論理変数には,1を入れる
4変数のカルノー図
CD

00 01 11 10
AB
00
01
11
10
1
1
1
4変数のカルノー図
4変数の論理関数
 =  + 
+  + 

1

3変数の場合と同様の手
順で1を埋めていく
0は入れても入れなくても
良い
カルノー図作成時のルール1

論理変数の数がnのカルノー図
– 2n個のマス目をもつ


各マス目一つは,加法標準形で表された論理式の
「最小項」に対応する
隣り合うマス目は,論理変数1つだけが反転した値に
対応している.
– 2進数の1ビットだけが反転している
– これを「ハミング距離が1」である,という

2ビット反転していれば,「ハミング距離は2」
カルノー図作成時のルール2

カルノー図の上下端,左右端はそれぞれ「隣り合って
いる」と考える
– ハミング距離が1だから

と言うか,1になるように設定する
カルノー図の作成練習1

2進数4ビットで表される10進数(0~15)について,入
力が4の倍数(0を含む)のときだけ1を出力するよう
な論理関数のカルノー図を書け.
隣り合うマス目の意味

隣り合う2つのマス目に“1”が入っている
– 対応する2つの積項中,1つだけビットが反転している論理
変数がある


つまり,2つの積項ではその論理変数は0でも1でも良
い.
0でも1でも良い論理変数なら,わざわざ式中に書く必
要なし.
– 2つの項を,当該論理変数を省いた形でまとめてしまう
隣接する3つのマス目に1!?
C
A
B
0
1
0
0
0
0
0
1
0
1
1
1
0
1
1
0
0
1
3変数のカルノー図

左のようなカルノー図
– 隣接する3つのマス目に1

この3つの積項を1つにまとめら
れるか否か?
– まとめられない
– 0と1の両方を含まないとまとめられ
ない
– まとめるマス目の数は,必ず2n個
カルノー図による簡単化
1. 論理式や真理値表からカルノー図を書く
2. カルノー図中,「1」と記入したマス目をグループ化
する
•
•
一つのグループに入るマス目の数は2n個
1つのグループができるだけ大きくなるようにグループを
作る
3. 各グループ内で値が「0」と「1」の両方を取る論理変
数を除き,常に「0」となる論理変数は否定の形で,
「1」となる論理変数はそのままに,論理積で結ぶ
4. 得られた積項を論理和で結ぶ
練習
次の論理式をカルノー図を用いて簡単化せよ
1. Z = AB + ABC + AB + ABC
2. Z = B ⋅ C ⋅ D + A ⋅ B ⋅ C + A ⋅ B ⋅ C +
A⋅B⋅C⋅D
完全定義論理式と
不完全定義論理式

完全定義論理式
– すべての入力の組合せに対し,0か1の出力がすべて決
まっている論理式

不完全定義論理式
–
–
–
–
決して入力とはならない入力の組合せを持つ論理式
当該入力に対する出力は,0でも1でも良い
カルノー図ではφや*を書いておく
φや*を「ドントケア(Don’t care)」という
ドントケアを含むカルノー図

CD
00
01
11

01
1 1 1 1
11
  1 
AB
10
 =  + 
10
00

次の論理式を考える
(ABCD)=(1110),(1011),
(1100),(1101)は起こりえな
いと想定する
– 上記4パターンの入力に対して
は,ドントケアとなる
ドントケアを含むカルノー図
による簡単化
ドントケアは0としても,1として
考えても良い
CD
00
01
11
10
00
01
1 1 1 1
11
  1 
AB
10

– (1100),(1101),(1110)は1とし
て考える
– (1011)は無視する
– A,C,Dは”0”と”1”が両方含ま
れているので省略可
=
本日のまとめ

カルノー図
– 入力論理変数間のハミング距離が1となるように配置した,
一種の真理値表

カルノー図による論理式の簡単化
– 「1」または「」が記述された,2n個のマス目を矩形にまとめ
てグループ化
– グループ内で0と1の両方を取る入力論理変数を取り除い
た積項を作成
– 作成した積項を論理和で結合
– ドントケア(「」)は0でも1でも都合の良いほうに解釈可
来週の予定

論理式の簡単化演習
– ブール代数を用いる場合
– カルノー図を用いる場合
– 得点アップの機会ですので,予習をしっかりと!