クワイン・マクラスキー表形式法

前の章では、5変数までのブール関数を最小化するための便利な方法であるK-map法について説明しました。ただし、この方法を使用して、5つを超える変数を持つブール関数を単純化することは困難です。

Quine-McClukeyの表形式の方法は、主要な含意の概念に基づく表形式の方法です。私達はことを知っていますprime implicant は積(または合計)項であり、指定されたブール関数の他の積(または合計)項と組み合わせてさらに減らすことはできません。

この表形式の方法は、次のブールIDを繰り返し使用して、主要な関係者を取得するのに役立ちます。

xy + xy '= x(y + y')= x.1 = x

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

Quine-McClukey表形式メソッドを使用してブール関数を単純化するには、次の手順に従います。

Step 1 −指定された最小項を ascending orderバイナリ表現に存在するものの数に基づいてグループを作成します。だから、at most ‘n+1’ groups ブール関数に「n」ブール変数がある場合、または最小項に相当するバイナリに「n」ビットがある場合。

Step 2 −に存在する最小項を比較します successive groups。1ビットの位置のみに変化がある場合は、それらの2つの最小項のペアを取ります。この記号「_」を異なるビット位置に配置し、残りのビットをそのままにします。

Step 3 −すべてが得られるまで、新しく形成された用語でステップ2を繰り返します。 prime implicants

Step 4 −を策定する prime implicant table。これは、行と列のセットで構成されています。主な含意は行ごとに配置でき、最小の用語は列ごとに配置できます。各プライム含意でカバーされている最小項に対応するセルに「1」を配置します。

Step 5−各列を観察して、本質的な主要な関係者を見つけます。最小項が1つの主要な含意者によってのみカバーされている場合、それはessential prime implicant。これらの重要な主要な含意は、単純化されたブール関数の一部になります。

Step 6−各必須プライム含意の行と、そのエッセンシャルプライム含意でカバーされている最小項に対応する列を削除して、プライム含意テーブルを減らします。縮小プライム含意テーブルに対して手順5を繰り返します。指定されたブール関数のすべての最小項が終了したら、このプロセスを停止します。

私たちにさせて simplify 次のブール関数、$ f \ left(W、X、Y、Z \ right)= \ sum m \ left(2,6,8,9,10,11,14,15 \ right)$(Quine-McClukeyを使用)表形式の方法。

与えられたブール関数は sum of min terms形。4つの変数W、X、Y、Zがあります。指定された最小項は2、6、8、9、10、11、14、および15です。これらの最小項の昇順は、それらに存在するものの数に基づいています。同等のバイナリは2、8、6、9、10、11、14、および15です。次の表にこれらを示します。min terms and their equivalent binary 表現。

GA3
グループ名 最小条件 W バツ Y Z
GA1 2 0 0 1 0
8 1 0 0 0
GA2 6 0 1 1 0
9 1 0 0 1
10 1 0 1 0
11 1 0 1 1
14 1 1 1 0
GA4 15 1 1 1 1

与えられた最小項は、同等のバイナリに存在するものの数に基づいて4つのグループに配置されます。次の表は、可能なことを示していますmerging of min terms 隣接するグループから。

GB3
グループ名 最小条件 W バツ Y Z
GB1 2,6 0 - 1 0
2,10 - 0 1 0
8,9 1 0 0 -
8,10 1 0 - 0
GB2 6,14 - 1 1 0
9,11 1 0 - 1
10,11 1 0 1 -
10,14 1 - 1 0
11,15 1 - 1 1
14,15 1 1 1 -

隣接するグループと1ビットの位置だけが異なる最小項がマージされます。その異なるビットは、この記号「-」で表されます。この場合、3つのグループがあり、各グループには2つの最小項の組み合わせが含まれています。次の表は、可能なことを示していますmerging of min term pairs 隣接するグループから。

グループ名 最小条件 W バツ Y Z
GB1 2,6,10,14 - - 1 0
2,10,6,14 - - 1 0
8,9,10,11 1 0 - -
8,10,9,11 1 0 - -
GB2 10,11,14,15 1 - 1 -
10,14,11,15 1 - 1 -

1ビットの位置のみが異なる最小項ペアの連続するグループがマージされます。その異なるビットは、この記号「-」で表されます。この場合、2つのグループがあり、各グループには4つの最小項の組み合わせが含まれています。ここでは、これらの4分の用語の組み合わせが2行で利用できます。したがって、繰り返される行を削除できます。冗長行を削除した後の縮小テーブルを以下に示します。

グループ名 最小条件 W バツ Y Z
GC1 2,6,10,14 - - 1 0
8,9,10,11 1 0 - -
GC2 10,11,14,15 1 - 1 -

隣接するグループの最小項の組み合わせは、1ビット以上の位置で異なるため、さらにマージすることはできません。上記の表には3つの行があります。したがって、各行は1つの主要な含意を与えます。したがって、prime implicants YZ '、WX'、WYです。

ザ・ prime implicant table 以下に示します。

最小条件/プライム含意 2 6 8 9 10 11 14 15
YZ’ 1 1 1 1
WX’ 1 1 1 1
WY 1 1 1 1

主な含意は行ごとに配置され、最小の用語は列ごとに配置されます。1は、プライム含意行と対応する最小項列の共通セルに配置されます。

最小項2および6は、1つの主要な関係者によってのみカバーされます YZ’。だから、それはessential prime implicant。これは、簡略化されたブール関数の一部になります。ここで、この主要な含意行と対応する最小項列を削除します。縮小されたプライム含意表を以下に示します。

最小条件/プライム含意 8 9 11 15
WX’ 1 1 1
WY 1 1

最小項8および9は、1つの主要な関係者によってのみカバーされます WX’。だから、それはessential prime implicant。これは、簡略化されたブール関数の一部になります。ここで、この主要な含意行と対応する最小項列を削除します。縮小されたプライム含意表を以下に示します。

最小条件/プライム含意 15
WY 1

最小項15は、1人の主要な関係者によってのみカバーされます WY。だから、それはessential prime implicant。これは、簡略化されたブール関数の一部になります。

この問題の例では、3つの主要な関係者がいて、3つすべてが不可欠です。したがって、simplified Boolean function です

f(W,X,Y,Z) = YZ’ + WX’ + WY.