演習問題 :表の縮小による最小化 ラベル • 次の真理値表の最小積和形を求めよ A 0 0 0 0 0 0 0 0 B 0 0 0 0 1 1 1 1 C 0 0 1 1 0 0 1 1 D 0 1 0 1 0 1 0 1 f 1 A 1 1 1 1 1 1 1 1 1 1 B 0 0 0 0 1 1 1 1 C 0 0 1 1 0 0 1 1 D 0 1 0 1 0 1 0 1 f 1が1個 4 = 1が2個 1 1 1が3個 1 1が0個 1が1個 1が2個 1が3個 1 1 0 1 0 0 0 1 1 - 13 = 23+22+20 1が4個 15 = 23+22+21+20 0 1 1 1 主項 p q r s t u f の主項は 最小項 5 13 15 必須 0,4:p 4,5:q ○ 0 4 5 10,11:s 11,15:t ○ 13,15:u ○ ○ 0 0 0 1 1 0 1 0 0 1 0 1 1 1 10 11 13 15 0,4:p ◎ ○ 4,5:q ○ ○ 5,13:r ○ ○ 10,11:s ◎ ○ 11,15:t ○ 必須主項が カバーした 最小項を削除 選択 最小項 主項 ○ ○ ○ 5 13 15 必須 0,4:p 13,15:u ○ ◎ fm = AC D BCD ABC ABD 他の主項に 包含される チェックが無い 主項を削除 10,11:s 選択 必須 5,13:r ◎ ○ 5,13:r ○ ○ 選択 主項 13,15:u AC D, ABC , BC D, A BC , ACD, ABD 主項 23+21+20 0 1 1 0 0 1 1 1 A(8) B(4) C(2) D(1) 0 0 1 1 1 22 10 = 23+21 最小項 ラベル 0,4 4,5 5,13 10,11 11,15 13,15 0 0 0 1 1 1 1 5 = 22+20 11 = 主項 A(8) B(4) C(2) D(1) 1が0個 0 縮小した表で 必須主項を チェック 必須主項が カバーした 最小項を チェック 1 演習問題: 論理数学による主項選択 演習問題 :ドントケアを含む最小化 • 最適な主項の組み合わせは？ 最小項 主項 m1 p ○ q ○ m2 m3 m4 ○ ○ ○ ○ s ○ U = S1S2S3S4 = (p+q)(q+r)(r+s)(s+p) = (pr + q)(pr + s) = pr + qs p と r ラベル 1が0個 1が1個 0 0 0 0 1 1 1 1 1 1 1 = 20 4= 22 5 = 22+20 1が2個 △9 = 23+20 10 = 23+21 △11 = 23+21+20 1が3個 △13 = 23+22+20 14 = 23+22+21 1が4個 △15 = 23+22+21+20 ラベル または A(8) B(4) C(2) D(1) 0 0 0 1 1 0 0 0 1 1 1 0 0 0 0 0 1 1 0 1 1 0 1 0 1 1 0 1 1 0 1 A(8) B(4) C(2) D(1) qとs C 0 0 1 1 0 0 1 1 D 0 1 0 1 0 1 0 1 f 1 1 A 1 1 1 1 1 1 1 1 1 1 B 0 0 0 0 1 1 1 1 C 0 0 1 1 0 0 1 1 D 0 1 0 1 0 1 0 1 f 1 1 - 主項 A(8) B(4) C(2) D(1) 0,1 0 0 0 - 0,4 0 - 0 0 1,5 0 - 0 1 1,9 - 0 0 1 4,5 0 1 0 - 5,13 - 1 0 1 △9,11 1 0 - 1 △9,13 1 - 0 1 10,11 1 0 1 - 10,14 1 - 1 0 △11,15 1 - 1 1 △13,15 1 1 - 1 14,15 1 1 1 - 1が0個 1が1個 1が2個 1が3個 主項 0,1,4,5 0 - 0 - p 1が1個 1,5,9,13 - - 0 1 q △9,11,13,15 1 - - 1 10,11,14,15 1 - 1 - f の主項は AC , C D, AC B 0 0 0 0 1 1 1 1 ラベル 主項 1が0個 1が2個 A 0 0 0 0 0 0 0 0 S1 = p +q S2 = q +r S3 = r +s S4 = s +p ○ r • 次の真理値表の最小積和形を求めよ 最小項 主項 0,1,4,5:p 0 ○ 5 14 15 必須 ○ ◎ ◎ 10,11,14,15:r 選択 4 ◎ ○ ◎ ○ 1,5,9,13:q r 1 fm = AC AC 2 問題: 表の縮小による最小化 • 次の真理値表の最小積和形を求めよ W 0 0 0 0 0 0 0 0 X 0 0 0 0 1 1 1 1 Y Z 0 0 0 1 1 0 1 1 0 0 0 1 1 0 1 1 f 1 1 ラベル 0,2 0,8 2,10 8,10 8,12 10,11 12 13 11,15 13,15 1が0個 1が1個 1が2個 1が3個 最小項 11,15:s ○ 13,15:t 0,2,8,10:u 選択 ラベル f 1 1が0個 1が1個 1 1 1 1 1が2個 1が3個 W(8) X(4) Y(2) Z(1) - 0 - 0 主項 u 必須 ○ Y(2) 0 1 0 1 0 1 - 必須主項が カバーした 最小項を削除 0 0 1 1 1 1 1 1 2 = 22 8= 24 10 = 23+21 12 = 23+22 11 = 23+21 +20 13 = 23+22 +20 最小項 主項 23+ 22+21 +20 0 2 8,12:p 0 0 0 0 0 1 1 1 ○ ○ 必須 ○ ○ ○ ○ 12,13:r ○ 11,15:s ○ ○ ○ 13,15:t 0,2,8,10:u ◎ ◎ ○ ○ 選択 最小項 主項 11 12 13 15 必須 ◎ ○ 12,13:r 選択 fm = ○ ○ 他の主項に 包含される チェックが無い 主項を削除 ○ 0,2,8,10:u ○ ○ 0 1 0 1 0 1 0 1 10 11 12 13 15 10,11:q 13,15:t ○ 0 0 0 0 1 0 1 1 8 11,15:s ◎ ○ ○ 主項 W(8) X(4) Y(2) Z(1) 0 1が4個 15 = 1 主項 p q r s t 10,11:q ○ 12,13:r Y Z 0 0 0 1 1 0 1 1 0 0 0 1 1 0 1 1 Z(1) 0 0 0 0 0 1 1 11 12 13 15 8,12:p X 0 0 0 0 1 1 1 1 W(8) X(4) 0 0 - 0 - 0 1 0 1 1 0 1 1 1 1 1 ラベル 0,2,8,10 主項 W 1 1 1 1 1 1 1 1 縮小した表で 必須主項を チェック 必須主項が カバーした 最小項を チェック 3 ラベル 問題: ドントケアを含む最小化 1が0個 • 次の真理値表の最小積和形を求めよ W 0 0 0 0 0 0 0 0 X 0 0 0 0 1 1 1 1 Y Z 0 0 0 1 1 0 1 1 0 0 0 1 1 0 1 1 f 1 - W 1 1 1 1 1 1 1 1 1 - ラベル Y Z 0 0 0 1 1 0 1 1 0 0 0 1 1 0 1 1 △1 = f 1 1が1個 1が2個 1 1 W(8) X(4) Y(2) Z(1) 1が3個 - 0,4 0 - 0 0 0,8 - 0 0 0 △1,3 0 0 - 1 △1,5 0 - 0 1 4,5 0 1 0 - 4,6 0 1 - 0 4,12 - 1 0 0 8,12 1 - 0 0 △3,7 0 - 1 1 △5,7 0 1 - 1 △6,7 0 1 1 - 6,14 - 1 1 0 12,14 1 1 - 0 0 4 8 12 14 △6 = 22+21 23+22 △7 = 22+21 +20 14 = 23+22 +21 W(8) X(4) Y(2) Z(1) 0 0 0 1 0 0 0 1 0 1 0 0 1 0 0 1 1 1 1 1 0 0 0 0 1 0 1 0 1 1 0 1 0 0 1 1 0 0 1 0 主項 主項 0 最小項 21+20 △5 = 22+20 12 = 0 主項 4 = 22 △3 = 0 1が1個 22 8 = 22 0,1 1が0個 1が2個 X 0 0 0 0 1 1 1 1 0 ラベル 1が0個 1が1個 0,1,4,5 0,4,8,12 △1,3,5,7 4,5,6,7 4,6,12,14 W(8) X(4) Y(2) Z(1) 0 0 0 - - 0 - 0 - 1 1 - 0 1 0 主項 p q r s f の主項は W Y , Y Z , W X , X Z 必須 0,1,4,5:p ○ ○ 0,4,8,12:q ○ ○ ◎ ○ 4,5,6,7:r ○ 4,6,12,14:s ○ 選択 課題7 解答例 ○ ◎ fm = Y Z X Z 4
© Copyright 2024 ExpyDoc
