論理式を変形して短くすることを↓
\( f = \bar{X}\bar{Y}Z + X\bar{Y}Z
= \bar{Y}Z \)
「簡単化」といいます。
簡単化には大きく三つ方法があり、
- 式変形
- カルノー図
- クワイン・マクラスキー法
です。今回はその中でも、クワイン・マクラスキー法について解説します。
カルノー図は直感的で理解しやすいので、知っている人も多いと思いますが、4変数くらいまで、頑張っても6変数くらいまでしか通常は使いません。そこで登場するのがクワイン・マクラスキー法です。
クワイン・マクラスキー法なら、
- 7入力以上の式も簡単化できる
- アルゴリズム的に扱えるので、コンピュータのプログラムとして表現しやすい
という特徴があります。（といっても、10入力以上は計算時間などのコストが大きくなりすぎるみたいです）
コンピュータ用の手法だといっても過言ではないので、カルノー図だけ知っていてもいいような気がしますが、手順を覚えたりする必要はないと思うので、「ふーん、こうやってやるんだな」という軽い気持ちで見てもらったらいいと思います。
ちなみに名前の由来はクワイン（W. V. Quine）さんとマクラスキー（E. J. McCluskey）さんが別々に発表したからです。
▼解説動画もあります
例題
4入力 X, Y, Z, W から出力 f が決まり、真理値表が次のようになっていたとします（*はドントケア）。例題は南谷（2009:93）とおなじものです。
| X | Y | Z | W | f |
| 0 | 0 | 0 | 0 | 1 |
| 0 | 0 | 0 | 1 | 1 |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 0 | 1 | 1 | * |
| 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | * |
| 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 |
このとき、f を簡単化しましょう。
クワイン・マクラスキー法は大きく2ステップあります。
- すべての「主項」を求める
- 必要な「主項」を厳選する
主項は、カルノー図でいうと1をループで囲んだものに対応します。
つまり、Step1でとりあえず全てのループをつくり、Step2でそのループの中から必要な分だけ選び出して式にする、という流れです。
Step1
Step1では、まず「主項表」というのを作ります。
真理値表で f の列が 1 か * となっている行のXYZWの値だけ取り出して、「最小項」の欄に記入していきます。
「グループ」は、最小項にふくまれる 1 の数で分けています。0011 のように、二つの 1 が含まれていたらグループ2、1101 のように 1 が 3 つあればグループ 3 という具合です。
ここから、
\( XY + \bar{X}Y = Y \)
という性質を使うことで、項のペアを作り、使うアルファベットの数をどんどん少なくしていきます。
具体的には、隣り合ったグループ（グループ 1 とグループ 2 など）に含まれる2進数の全組み合わせを考えて、\( XY + \bar{X}Y = Y \) の式が適用できないかを考えます。
グループ 0 と グループ 1
例えば、グループ 0 とグループ 1 を考えましょう。
グループ 0 の 0000 と、グループ 1 の 0001, 0010, 1000 を比較します。
0000 と 0001
0000 と 0001 （\(\bar{X}\bar{Y}\bar{Z}\bar{W} と \bar{X}\bar{Y}\bar{Z}W\)）
みたいに、一か所だけ異なってほかは全て同じという2進数があれば、それらはまとめることができ、
000* （\( \bar{X}\bar{Y}\bar{Z} \)）
のように表します。共通した部分はそのままで、異なった部分には「*（アスタリスク）」を入れます。
これで結合できるペアを一つ発見できました。見つけた 000* を、別の新しい表に書きます。
また、結合前の 0000 や 0001 の「星」欄に ☆ をつけて目印を書いておきます。
0000 と 0010
0000 と 0010
も、左から 3 番目だけ異なって、ほかは同じなので、ペアが作れます。
これらのペアを結合すると、
00*0
という二進数ができあがります。この 00*0 も、新しい表に追加しておきます。
また、0000 と 0010 の「星」欄に ☆ を書いておきます（0000 はすでに☆が書かれていますが）。
0000 と 1000
0000 と 1000
も、一番左だけ異なって、それ以外は共通しているので、ペアが作れます。
ペアが結合すると、
*000
という 2 進数になります。*000 も新しい表に追加します。また、0000 と 1000 に ☆ をつけておきます。
その他のグループ
これ以降は、グループ 1 と グループ 2 について、その次はグループ 2 と 3、その次はグループ 3 と 4 について、同じように結合できる 2 進数がないか探します。
グループ同士の 2 進数の全組み合わせを調べます。例えば、グループ 1 と 2 はそれぞれ 3 つの 2 進数がありますので、全部で 9 つの組み合わせについて、ペアを探します。
以後は省略しますが、すべての組み合わせに対して行うと、次のようになります。（新しく主項表その2を作りました）
主項表その2
新しく主項表ができたので、主項表その2 に対しても、また同じようにペアがないか探します。
グループ(0, 1)とグループ(1, 2)からそれぞれ一つずつ取り出して、ペアになるか確認し、ペアができたら主項表その3に追加して、☆をつける…という作業を、主項表その2に対しても全部調べます。
調べた結果がこちら
主項表その3
主項表その3は、もうペアができないので終わりです。
終わったら、☆のついていないものが主項となります。
今回は、0*01、*101、1*11、11*1、00**、*0*0、*01* の 7 つですね。
Step2
Step1で、主項をすべて求めることができました。しかし、これではまだ不要な主項が混じっている可能性があります（カルノー図でも、すべてのループを使わない問題もあったと思います）。
なので、ここからは必要な主項を厳選する作業に入ります。
被覆表をつくる
Step2 では、新しく「被覆表」なるものを作成します。
左端には、Step1 でえられた主項を縦に並べ、上端には、真理値表の f が 1 （* は含まない）となっている 2 進数を横に並べます。
そして、該当する部分に × を記入します（例えば、上の 0*01 の行は、左から一番目が 0 、三番目が 0、四番目が 1 となっている、0001 と 0101 に × を記入）。
Step2 の 3 つの手順
被覆表が書けたら、次の3つの手順を順番に行います。
- ×が 1 つしかない列を見つける。その×がある行は必要な論理式なので解に加えて、その行を削除。また、その行の×が書かれている列をすべて削除
- 行Aの×は、すべて行Bにも含まれているときは、行Aを削除。
- 列Cの×は、すべて列Dにも含まれているときは、列Cを削除。
1、2、3まで進めば、また1に戻って繰り返します。
これで表をどんどん小さくしていくことで、最終的な解に必要な論理式をみつけだすことができます。
手順2において、笹尾（2005:69-70）では「行Aの論理式の文字数は、行Bの論理式の文字数以上でなければいけない」という旨の条件が記載されていますが、南谷（2009）には記載されていませんでした。どちらが正しいかは分かりませんが、今回は南谷（2009）にのっとって説明します。
言葉だけでは分かりにくいと思うので、実際にやってみましょう。
被覆表を解く
被覆表ア
まずは手順1にあるように、「被覆表ア」をみて、×が一つしかない列を探します。
すると、1000 の列は×がひとつしかありません。よって、その×が書かれている行「*0*0」は必要なので、それを覚えておきつつ、*0*0の行は削除します。
また、*0*0は「0000」「0010」「1000」に×があるので、その列も削除します。
被覆表イ
被覆表アから、行や列を削除すると次のようになります。
次は手順2です。「00**」の行は 0001 にしか×がないですが、「0*01」には 0001 と 0101 の二つに×があり、00** の行の×は 0*01 の行の×に含まれている、といえます。
よって、行00**は削除します。
また、同じ理由で「*01*」行にある×は、「1*11」の行にも同じところに×があるので、*01* の行は削除します。
被覆表ウ
行を削除すると、次のようになります。
次は手順3を使います。「0001」の列には 0*01 にしか×がないですが、「0101」の列には 0*01 と *101 の二つに×があり、0001 の列の×は 0101 の列の×に含まれている、といえます。
よって、列 0101 は削除します。
同じ理由で、「1011」の列にある×は、「1111」の列にも同じところに×があるので、1111の列も削除します。
被覆表エ
列を削除すると、次のようになります。
さきほど手順3が終わったので、次は手順1にまた戻ります。
つまり、ふたたび×が一つしかない列を探します。
被覆表エを見ると、「0001」と「1011」の列には×が一つしかありません。よって、その×が書かれている行「0*01」「1*11」は解に含まれます。また、その二つの行を削除します。
また、行0*01の×が書かれている列「0001」と、行1*11の×が書かれている列「1011」も削除します。
被覆表オ
行と列を削除した結果がこちらです。
これ以上は表を小さくできないので、これで終了です。
*101 か 11*1 のどちらかを選択します。
答え
解に含まれるとしていた 2 進数（青いマーカーをつけています）を書きだします。
*0*0、0*01、1*11、[*101または11*1]
こちらの 5 つです（最後の二つはどちらかを選択）。
これらを論理式になおし、＋でつなげたら f を簡単化できたことになります。
よって、解は
\( f = \bar{Y}\bar{W} + \bar{X}\bar{Z}W + XZW + Y\bar{Z}W \)
または
\( f = \bar{Y}\bar{W} + \bar{X}\bar{Z}W + XZW + XYW \)
です。
まとめ
クワイン・マクラスキー法のまとめ
クワイン・マクラスキー法をまとめると、
- 「主項表」をつくり、結合できる2進数のペアをさがす
- 「被覆表」をつくり、3 つの手順を利用して表をちいさくする
という大きく二つのステップを行うことで、論理式を簡単化することができました。
Step2 で行き詰まる場合
Step2 の方法で被覆表を小さくしても、途中でこれ以上表が小さくならない！という場合があります。
具体的には、どの列にも 2 つ以上の×がある場合、3 つの手順をすべて使っても表を小さくすることができません。そうなった表のことを「サイクリックテーブル」といいます。
サイクリックテーブルになった場合は、「分枝限定法」や「ぺトリックの方法」を使うことで、先に進めないという問題を解決することができます。詳しく知りたい人は、YouTube動画や参考文献などをごらんください。YouTube では分枝限定法について触れています。
参考文献
笹尾勤（2005）『論理設計―スイッチング回路理論―（第4版）』近代科学社.
南谷崇（2009）『論理回路の基礎』サイエンス社.
コメント