【論理設計】クワイン・マクラスキー法

今回はクワイン・マクラスキー法について説明する。

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

クワイン・マクラスキー法は多変数論理関数を最簡な論理関数で表すためのアルゴリズムである。

クワイン・マクラスキー法の手順

ⅰ　すべての主項を求める
ⅱ　主項表を作り関数の論理最小項の最小被覆を求める

ここですべての主項を求める手順を述べる

ⅰ　与えられた論理関数のすべての論理最小項のキューブ表現を求める
ⅱ　キューブを、その中の１の個数に従って第一段階のグループ分けをする
ⅲ　第１グループと第２グループのキューブを比較し、併合可能であれば、それらにチェックをつけ、併合し、併合して得られるキューブを次の段階のリストの第一グループに入れる
ⅳ　第２グループと第３グループ、第３グループと第４グループのように進める
ⅴ　次の段階のリストにグループが２つ以上あれば併合を進める
ⅵ　チェックのついていないキューブが主項

最小被覆を求める手順を述べる

ⅰ　主項表からすべての必須行を選択
ⅱ　必須行、関連する列を削除し、主項表を簡約化
ⅲ　すべての行、列が削除されれば終了
ⅳ　簡約化された主項表から必須行（２次必須行という）を選択→２へ