第４章 組合せ論理回路 （４） Quine McCluskeyの方法
論理変数の作る空間 n-cube 1変数の作る空間 ２変数の作る空間 00 01 10 11 0-cube 1-cube 2-cube
論理変数の作る空間（続き） ３変数の作る空間
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） という．
隣接する項は だけ違う． “１”の個数の多いほうが値が大きい．
a b c d
定理 最小の積和形式は主項の和で表される 証明 もし主項でないものが含まれているならば，それを含む主項で置き換えれば，さらに小さな式になる．
＊ ＊ ＊
必須項をリテラルで表す ＊の付いているのが必須項
例題
＊ ＊ ＊ ＊ ＊
２次必須項
交換可能 定義 交換可能 縮小した主項表で，２つの行 a, b が同じ最小項をカバーするとき，a と b は交換可能であるという． 定義 交換可能 縮小した主項表で，２つの行 a, b が同じ最小項をカバーするとき，a と b は交換可能であるという． Aがbに のあるすべてのカラムに を持ち，b に のないカラムで少なくとも１つの を持つときに，a は b を支配するという．
定理 a, b はともに縮小した主項表の行とする．a のコストは b のコスト以下であるとする．このとき a が b を支配するかまたは b と交換可能であれば，b を含まない最小の積和形式が存在する．
Don’t care の取り扱い 主項を決定するときには“１”として取り扱い，主項表により必須項を決定するときには無視して，最小項のみとする．
乗法標準形の解 を積和形式で作り，ドモルガンの定理によって変換する．