第４章　組合せ論理回路　（４） Quine　McCluskeyの方法.

Presentation on theme: "第４章　組合せ論理回路　（４） Quine　McCluskeyの方法."— Presentation transcript:

1 第４章　組合せ論理回路　（４） Quine　McCluskeyの方法

2 論理変数の作る空間 n-cube 1変数の作る空間 ２変数の作る空間 00 01 10 11 0-cube 1-cube 2-cube

3 論理変数の作る空間（続き） ３変数の作る空間

4 Cube の結合 0-cube 110, 111 は 1-cube 11x に含まれる．
0-cube 110 や　1-cube 11x は 2-cube 1xx に含まれる（覆われている）．

5 Q-M法 カルノー図による方法は 系統的な方法 は？ 直感に頼る． ６変数以上であるとやりにくい．
系統的な方法 は？ Q-M法　最良の２次形式を得るアルゴリズミックな手続きを与える． あらゆるcubeを系統的に調べ尽くす．

6 例題 これらの0-cubeからどのようなcubeができるか？ 隣接する項は“１”の数が １だけ違うはずである． “１”の個数でまとめてみる．

7        

8     0000 0010 00x0

9 主項 定義 の付いている項はそれ以上に大きいcubeに含まれている．
　 の付いていない項は，この関数の中でもっと大きなcubeに含まれないcubeである．このような項を主項（prime implicant） という．

10 隣接する項は 　　　だけ違う． “１”の個数の多いほうが値が大きい．

11 a b c d

12 定理　 最小の積和形式は主項の和で表される 証明　もし主項でないものが含まれているならば，それを含む主項で置き換えれば，さらに小さな式になる．

13  ＊  ＊  ＊

14 必須項をリテラルで表す ＊の付いているのが必須項

15 例題

16

17

18  ＊  ＊ ＊   ＊  ＊

19

20 ２次必須項

21 交換可能 定義 交換可能 縮小した主項表で，２つの行 a, b が同じ最小項をカバーするとき，a と b は交換可能であるという．
定義　交換可能 縮小した主項表で，２つの行 a, b が同じ最小項をカバーするとき，a と b は交換可能であるという． Aがbに　　のあるすべてのカラムに　　を持ち，b に　　のないカラムで少なくとも１つの　　を持つときに，a は b を支配するという．    

22 定理 　　a, b はともに縮小した主項表の行とする．a のコストは b のコスト以下であるとする．このとき a が b を支配するかまたは b と交換可能であれば，b を含まない最小の積和形式が存在する．

23

24

25 Don’t care の取り扱い 主項を決定するときには“１”として取り扱い，主項表により必須項を決定するときには無視して，最小項のみとする．

26

27

28 乗法標準形の解 　　を積和形式で作り，ドモルガンの定理によって変換する．