クワイン・マクラスキー表形式法
前の章では、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 表現。
| グループ名 | 最小条件 | 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 隣接するグループから。
| グループ名 | 最小条件 | 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.