第４章組合せ論理回路（４） Quine McCluskeyの方法論理変数の作る空間  n-cube 1変数の作る空間 m0 m1 ２変数の作る空間 m2 10 0-cube 1-cube 2-cube m1 m3 11 m0 m0 00 m1 m0 m1 01 論理変数の作る空間（続き）  ３変数の作る空間 Cube の結合 – 0-cube 110, 111 は 1-cube 11x に含まれる． – 0-cube 110 や 1-cube 11x は 2-cube 1xx に含まれる（覆われている）． Q-M法  カルノー図による方法は – 直感に頼る． – ６変数以上であるとやりにくい．  系統的な方法は？ – Q-M法最良の２次形式を得るアルゴリズミックな手続きを与える． – あらゆるcubeを系統的に調べ尽くす．例題 – これらの0-cubeからどのようなcubeができるか？隣接する項は“１”の数が１だけ違うはずである． “１”の個数でまとめてみる．               0000    0010 00x0 主項  定義 の付いている項はそれ以上に大きい cubeに含まれている． の付いていない項は，この関数の中でもっと大きなcubeに含まれないcubeである．このような項を主項（prime implicant）という． 0 - cube m13  1101    1- cube m13,9  1x01 1- cube m9  1001  隣接する項は – 2 k だけ違う． – “１”の個数の多いほうが値が大きい． a b c d 定理最小の積和形式は主項の和で表される  証明もし主項でないものが含まれているならば，それを含む主項で置き換えれば，さらに小さな式になる．＊＊＊          必須項をリテラルで表す  ＊の付いているのが必須項例題＊＊＊＊＊               ２次必須項交換可能  定義交換可能 – 縮小した主項表で，２つの行 a, b が同じ最小項をカバーするとき，a と b は交換可能であるという． – Aがbに  のあるすべてのカラムに  を持ち， b に  のないカラムで少なくとも１つの  を持つときに，a は b を支配するという．定理 a, b はともに縮小した主項表の行とする． a のコストは b のコスト以下であるとする．このとき a が b を支配するかまたは b と交換可能であれば，b を含まない最小の積和形式が存在する． Don’t care の取り扱い  主項を決定するときには“１”として取り扱い，主項表により必須項を決定するときには無視して，最小項のみとする．乗法標準形の解  f を積和形式で作り，ドモルガンの定理によって変換する．