クワイン・マクラスキー法
クワイン・マクラスキー法（—ほう; Quine–McCluskey algorithm/略:QM法）はブール関数を簡単化するための方法である。カルノー図と同様の目的で使われるが、コンピュータによる自動化に適しており、またブール関数が最簡形かどうか決定的に求めることができる。W・V・クワインが提案し、E・J・マクラスキーが発展させた方法なのでこの名がある。
クワイン・マクラスキー法は3段階からなる。
- 関数の主項をすべて求める
- 求めた主項を表にまとめ、必須項を求める
- 最簡形を求める
例
主項を求める
以下の真理値表で表されるブール関数を簡単化する。
| A | B | C | D | f | |
|---|---|---|---|---|---|
| m0 | 0 | 0 | 0 | 0 | 0 |
| m1 | 0 | 0 | 0 | 1 | 0 |
| m2 | 0 | 0 | 1 | 0 | 0 |
| m3 | 0 | 0 | 1 | 1 | 0 |
| m4 | 0 | 1 | 0 | 0 | 1 |
| m5 | 0 | 1 | 0 | 1 | 0 |
| m6 | 0 | 1 | 1 | 0 | 0 |
| m7 | 0 | 1 | 1 | 1 | 0 |
| m8 | 1 | 0 | 0 | 0 | 1 |
| m9 | 1 | 0 | 0 | 1 | x |
| m10 | 1 | 0 | 1 | 0 | 1 |
| m11 | 1 | 0 | 1 | 1 | 1 |
| m12 | 1 | 1 | 0 | 0 | 1 |
| m13 | 1 | 1 | 0 | 1 | 0 |
| m14 | 1 | 1 | 1 | 0 | x |
| m15 | 1 | 1 | 1 | 1 | 1 |
X は Don't care を表す。 この関数の選言標準形は、最小項の和をとって（Don't care は無視する）
となる。 もちろんこれはまだ最簡形ではない。まず、すべての1となる最小項をビット列中の1の数（ハミング重み）ごとに表に列挙する。これはすべての組み合わせを作り、ハミング距離が1のものだけ残すのと等価である。このとき Don't care の項も加える。
| 1の数 | 最小項 | ビット列表現 |
|---|---|---|
| 1 | m4 | 0100 |
| m8 | 1000 | |
| 2 | m9 | 1001 |
| m10 | 1010 | |
| m12 | 1100 | |
| 3 | m11 | 1011 |
| m14 | 1110 | |
| 4 | m15 | 1111 |
これで最初の準備が整った。1ビットのみが異なっている（ハミング距離が1となる）最小項の組を見つけて、その2つをまとめる。これをすべての最小項の組み合わせについて確かめる。こうしてできた項を再び1の数ごとにまとめ、同じ操作を再帰的に適用する。それ以上まとめることができない項（もうハミング距離が１となる組み合わせがない項）にしるし（*）をつける。この印を付けた項が主項となる。
| 1の数 | 最小項 | ビット列表現 |
|---|---|---|
| 1 | m4 | 0100 |
| m8 | 1000 | |
| 2 | m9 | 1001 |
| m10 | 1010 | |
| m12 | 1100 | |
| 3 | m11 | 1011 |
| m14 | 1110 | |
| 4 | m15 | 1111 |
| 1回目の比較 | ||
|---|---|---|
| 1 | m4,12 | -100* |
| m8,9 | 100- | |
| m8,10 | 10-0 | |
| m8,12 | 1-00 | |
| 2 | m9,11 | 10-1 |
| m10,11 | 101- | |
| m10,14 | 1-10 | |
| m12,14 | 11-0 | |
| 3 | m11,15 | 1-11 |
| m14,15 | 111- | |
| 2回目の比較 | ||
|---|---|---|
| 1 | m8,9,10,11 | 10--* |
| m8,10,12,14 | 1--0* | |
| 2 | m10,11,14,15 | 1-1-* |
必須項を求める
主項のなかから必須項をみつける。横軸に最小項（Don't care でないもの）、縦軸に求めた主項を書いた表を作る。主項がカバーする最小項の欄にしるし（X）を書く。ある最小項をカバーする主項が1つしかないとき、その主項を必須項という。
| 4 | 8 | 10 | 11 | 12 | 15 | ⇒ | A | B | C | D | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| m4,12 * | X | X | ⇒ | — | 1 | 0 | 0 | ||||
| m8,9,10,11 | X | X | X | ⇒ | 1 | 0 | — | — | |||
| m8,10,12,14 | X | X | X | ⇒ | 1 | — | — | 0 | |||
| m10,11,14,15 * | X | X | X | ⇒ | 1 | — | 1 | — |
例では2つ必須項が求まった。表中でしるし（*）をつけてある。必須項はその名のとおり、簡単化した関数に必ず含まれていなければならない項である。
最簡形を求める
必須項だけでは全ての最小項をカバーできていないので、更なる作業が必要になる。最もシンプルな方法は、試行錯誤して最簡形を見つけることであるが、より系統的な方法として、ペトリック法(en:Petrick's method)がある。このケースでは、次の最簡形を得る。
ぺトリック法では、得られた表の横の列に真理値の変数を割り当て、先程とは逆に、同じ最小項をカバーする主項２つのすべての組み合わせの和を作り、それらすべての積を作り、多項式の展開で変形、同じ真理値の積がそれ自身であることを利用して簡単にし、すべての必須項を含む最も短い積の項を選ぶことで最簡項を見つける。この場合は、２つ見つかる。
計算量
（主として人間の把握能力の限界により）4〜6変数[1]程度以上の簡単化はカルノー図では不可能で、コンピュータ・プログラムによりクワイン・マクラスキー法を使うのが現実的となる。しかし、充足可能性問題であるためNP困難であることから、実行時間が入力長に対し指数関数的に増加するという問題がある。具体的には、n変数関数における主項の数の上限が3nとなるため例えば n = 32とおくと、主項の数は6.5 × 1015を超えることもある。そのため変数の多い関数の簡単化においては、最適解は保証されないが現実的な時間内で比較的良質な解を得られる、ヒューリスティックを含む方法に切り替えなければならない。
脚注
- ^ 平面の表で4変数までが一般的だが、3次元のキューブ状に拡張してなんとか6変数までは扱える。しかしそれ以上増やすには、人間が4次元以上を把握する能力が必要であり困難。
参考文献
- 田丸 啓吉『論理回路の基礎（改訂版）』工学図書株式会社、1989年。ISBN 4-7692-0204-0。
関連項目
- Petrick's method（英語版）
外部リンク
- クワイン・マクラスキー法の解説 （図あり）
- Javaアプレット
- Pythonによる実装
- Quinessence Free Pascalによるフリー実装
- Javaによる文芸的プログラム実装
- ステップごとに実行するJavaアプレット