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

クワイン・マクラスキー法の概要

クワイン・マクラスキー法（QM法）は、ブール関数の簡略化を効率的に行う手法です。この方法は、W. V. クワインによって提案され、E. J. マクラスキーによって発展させられました。そのため、二人の名前が付けられています。QM法は、特にコンピュータによる自動化に適しており、ブール関数が最簡形になっているかどうかを決定することができます。主に次の3つの段階で構成されています。

1. 主項の特定
2. 必須項の特定
3. 最簡形の算出

1. 主項の特定

まず、ブール関数の真理値表からすべての主項を求めます。主項とは、関数が1となる入力を示す数値の集合です。例えば、あるブール関数が与えられた際、最小項をビット列として列挙し、1が立っている部分を確認していきます。ここで、Don't careも考慮に入れ、すべての組み合わせを作成します。次に、ハミング距離が1となる主項の組み合わせを特定し、これをまとめていきます。この操作を反復し、最終的にそれ以上簡略化できない項に印を付けて主項を決定します。

2. 必須項の特定

主項を得た後、必須項を特定するステップに移ります。ここでは、最小項と主項を用いて表を作成します。主項がどの最小項をカバーしているかを示すために、適切なマークを付けていきます。このプロセスを経って、カバーされる最小項が一つだけの場合、その主項は「必須項」となります。この操作を通じて、ある関数に不可欠な項が明確になります。

3. 最簡形の算出

必須項だけではすべての最小項をカバーできないため、さらなる簡略化が必要です。一つの方法として試行錯誤で最簡形を直感的に見つけることがありますが、ペトリック法などの系統的なアプローチを用いることで、より効率的に最簡形を求めることができます。この方法では、得られた表の各列に真理値の変数を割り当て、主項の組み合わせに基づいて最小項をカバーするような形で計算を進めていきます。こうして得られる最簡形が、ブール関数の簡略化の最終的な姿となります。

計算量と実用性

クワイン・マクラスキー法は、6変数以上の関数に対しては手作業での簡略化が難しくなるため、コンピュータによる実施が現実的です。しかし、NP困難な問題であることから、実行時間が入力の大きさに対し指数関数的に増加します。具体的には、n変数の関数においては主項の数が最大で3^nとなるため、高次のブール関数においては非常に困難な計算量を伴います。それ故に、効率的なヒューリスティック手法を併用することが一般的です。

まとめ

クワイン・マクラスキー法は、ブール関数を簡略化する上で非常に有力な手法であり、特にその自動化能力と明確な計算プロセスが企業や研究機関で評価されています。現代の論理設計においては不可欠なツールといえるでしょう。

もう一度検索