クワイン・マクラスキー法

クワイン・マクラスキー法(—ほう; Quine-McCluskey algorithm/略:QM法)はブール関数を簡単化するための方法である。カルノー図と同様の目的で使われるが、コンピュータによる自動化に適しており、またブール関数が最簡形かどうか決定的に求めることができる。W・V・クワインが提案し、E・J・マクラスキーが発展させた方法なのでこの名がある。

クワイン・マクラスキー法は3段階からなる。

1. 関数の主項をすべて求める
2. 求めた主項を表にまとめ、必須項を求める
3. 最簡形を求める

クワイン・マクラスキー方法

以下の真理値表で表されるブール関数を簡単化する。

X は Don't care を表す。 この関数の選言標準形は、最小項の和をとって(Don't care は無視する)

${\displaystyle f={\overline {A}}B{\overline {C}}{\overline {D}}+A{\overline {B}}{\overline {C}}{\overline {D}}+A{\overline {B}}C{\overline {D}}+A{\overline {B}}CD+AB{\overline {C}}{\overline {D}}+ABCD}${\displaystyle f={\overline {A}}B{\overline {C}}{\overline {D}}+A{\overline {B}}{\overline {C}}{\overline {D}}+A{\overline {B}}C{\overline {D}}+A{\overline {B}}CD+AB{\overline {C}}{\overline {D}}+ABCD}

となる。 もちろんこれはまだ最簡形ではない。まず、すべての1となる最小項をビット列中の1の数(ハミング重み)ごとに表に列挙する。また Don't care の項も加える。

これで最初の準備が整った。1ビットのみが異なっている(ハミング距離が1となる)最小項の組を見つけて、その2つをまとめる。これをすべての最小項の組み合わせについて確かめる。こうしてできた項を再び1の数ごとにまとめ、同じ操作を再帰的に適用する。それ以上まとめることができない項にはしるし(*)をつける。この印を付けた項が主項となる。

主項のなかから必須項をみつける。横軸に最小項(Don't care でないもの)、縦軸に求めた主項を書いた表を作る。主項がカバーする最小項の欄にしるし(X)を書く。ある最小項をカバーする主項が1つしかないとき、その主項を必須項という。

主項のなかから必須項をみつける。横軸に最小項(Don't care でないもの)、縦軸に求めた主項を書いた表を作る。主項がカバーする最小項の欄にしるし(X)を書く。ある最小項をカバーする主項が1つしかないとき、その主項を必須項という。

例では2つ必須項が求まった。表中でしるし(*)をつけてある。必須項はその名のとおり、簡単化した関数に必ず含まれていなければならない項である。

必須項だけでは全ての最小項をカバーできていないので、更なる作業が必要になる。最もシンプルな方法は、試行錯誤して最簡形を見つけることであるが、より系統的な方法として、ペトリック法(en:Petrick's method)がある。このケースでは、次の最簡形を得る。

${\displaystyle {\begin{aligned}f&=B{\overline {C}}{\overline {D}}+A{\overline {D}}+AC\\&=B{\overline {C}}{\overline {D}}+A{\overline {B}}+AC\end{aligned}}}${\displaystyle {\begin{aligned}f&=B{\overline {C}}{\overline {D}}+A{\overline {D}}+AC\\&=B{\overline {C}}{\overline {D}}+A{\overline {B}}+AC\end{aligned}}}

4変数以上のブール関数を扱う際にはカルノー図よりも実用的であるが、クワイン・マクラスキー法が使える範囲にも限りがある。充足可能性問題というNP困難な問題を対象としているため、実行時間が入力長の指数関数的に増加してしまうのである。n変数関数における主項の数の上限は3ⁿとなる。n = 32とおくと、主項の数は6.5 × 10¹⁵を超えることもある。変数の多い関数の簡単化においては最適解を保証しないヒューリスティックな方法が必要になる。

4変数以上のブール関数を扱う際にはカルノー図よりも実用的であるが、クワイン・マクラスキー法が使える範囲にも限りがある。充足可能性問題というNP困難な問題を対象としているため、実行時間が入力長の指数関数的に増加してしまうのである。n変数関数における主項の数の上限は3ⁿとなる。n = 32とおくと、主項の数は6.5 × 10¹⁵を超えることもある。変数の多い関数の簡単化においては最適解を保証しないヒューリスティックな方法が必要になる。

• Petrick's method(英語版)

• 田丸 啓吉『論理回路の基礎(改訂版)』工学図書株式会社、1989年。ISBN 4-7692-0204-0。 

• クワイン・マクラスキー法の解説 (図あり)
• Javaアプレット
• Pythonによる実装
• Quinessence Free Pascalによるフリー実装
• Javaによる文芸的プログラム実装
• ステップごとに実行するJavaアプレット

• 論理学
• デジタル回路
• 数学に関する記事

• ISBNマジックリンクを使用しているページ