4.7 Quine-McCluskey method 明治大学理工学部情報科学科井口幸洋クワイン・マクラスキ法の概要 • 二段論理回路の最適化に使用 • 大きく分けて次の２ステップで構成 – すべての主項を求め、主項表を作る． – 主項表の最小被覆を求める． • 適用範囲は入力変数が１０数個程度まで – より大きな問題は発見的手法で解く（準最適解しか求められない）が、その一部としてこの手法を用いる．すべての主項を求める • 基本は項の併合． • 計算の手間を増やさないように工夫． x1 0 x3x2 0 0 1 0 1 1 1 1 1 1 1 1 0 すべての主項を求める • 基本は項の併合． • 計算の手間を増やさないように工夫．併合できるか？ x1 0 x3x2 0 0 1 0 1 1 1 1 1 1 1 1 0 ＹＥＳすべての主項を求める • 基本は項の併合． • 計算の手間を増やさないように工夫． x1 0 x3x2 0 0 1 0 1 1 1 1 1 1 1 1 0 併合して面積２のループができたすべての主項を求める • 基本は項の併合． • 計算の手間を増やさないように工夫．併合できるか？ x1 0 x3x2 0 0 1 0 1 1 1 1 1 1 1 1 0 NO すべての主項を求める • 基本は項の併合． • 計算の手間を増やさないように工夫．併合できるか？ x1 0 x3x2 0 0 1 0 1 1 1 1 1 1 1 1 0 NO すべての主項を求める • 基本は項の併合． • 計算の手間を増やさないように工夫．併合できるか？ x1 0 x3x2 0 0 1 0 1 1 1 1 1 1 1 1 0 YES すべての主項を求める • 基本は項の併合． • 計算の手間を増やさないように工夫．併合できた x1 0 x3x2 0 0 1 0 1 1 1 1 1 1 1 1 0 すべての主項を求める • 基本は項の併合． • 計算の手間を増やさないように工夫．併合できるか？ x1 0 x3x2 0 0 1 0 1 1 1 1 1 1 1 1 0 NO すべての主項を求める • 基本は項の併合． • 計算の手間を増やさないように工夫．併合できるか？ x1 0 x3x2 0 0 1 0 1 1 1 1 1 1 1 1 0 YES すべての主項を求める • 基本は項の併合． • 計算の手間を増やさないように工夫． x1 0 x3x2 0 0 1 0 1 1 1 包含された項を削除すると主項が残る 1 1 1 0 1 1 すべての主項を求める • 基本は項の併合． • 計算の手間を増やさないように工夫． x1 0 x3x2 0 0 1 0 1 1 1 1 1 1 1 1 0 主項は３つ何回最小項を併合できるか検討したか？すべての主項を求める • 基本は項の併合． • 計算の手間を増やさないように工夫． x1 0 x3x2 0 0 1 0 1 1 1 1 1 1 1 1 0 主項は３つ何回最小項を併合できるか検討したか？ 43 6 4 C2  2 すべての主項を求める • 基本は項の併合． • 計算の手間を増やさないように工夫． x1 0 x3x2 0 0 1 0 1 1 1 1 1 1 1 1 0 今までの比較では明らかに無意味なものがあった。すべての主項を求める • 基本は項の併合． • 計算の手間を増やさないように工夫． x1 0 x3x2 0 0 1 0 1 1 1 1 1 1 1 1 0 今までの比較では明らかに無意味なものがあった。 000: 1の個数0 001: 1の個数1 011: 1の個数2 111: 1の個数3 主項表の作成最小項 0 キューブ x1 x2 x3 0 0 0 1の個数0 1 0 0 1 1の個数1 3 0 1 1 7 1 1 1 1の個数2 1の個数3 １の個数が1個しか異ならないグループに属するキューブ同士を比較すればよい主項表の作成最小項 0 キューブ x1 x2 x3 0 0 0 1 0 0 1 3 0 1 1 7 1 1 1 最小項 0, 1 キューブ x1 x2 x3 0 0 - 主項表の作成最小項 0 キューブ x1 x2 x3 0 0 0 0, 1 キューブ x1 x2 x3 0 0 - 1 0 0 1 1, 3 0 - 1 3 0 1 1 7 1 1 1 最小項主項表の作成最小項 0 キューブ x1 x2 x3 0 0 0 0, 1 キューブ x1 x2 x3 0 0 - 1 0 0 1 1, 3 0 - 1 3 0 1 1 3, 7 - 1 1 7 1 1 1 最小項