下のように、論理式を変形して短くすることを
f = \bar{X}\bar{Y}Z + X\bar{Y}Z = \bar{Y}Z
「簡単化」 といいます。
簡単化には大きく三つ方法があり、
- 式変形
- カルノー図
- クワイン・マクラスキー法
です。今回はその中でも、クワイン・マクラスキー法について解説します。
カルノー図は直感的で理解しやすいので、知っている人も多いと思いますが、4変数くらいまで、頑張っても6変数くらいまでしか通常は使いません。そこで登場するのがクワイン・マクラスキー法です。
クワイン・マクラスキー法なら、
- 7入力以上の式も簡単化できる
- アルゴリズム的に扱えるので、コンピュータのプログラムとして表現しやすい
という特徴があります。（といっても、10入力以上は計算時間などのコストが大きくなりすぎるようです）
コンピュータ用の手法だといっても過言ではないので、手順を覚えたりする必要はないと思います。「ふーん、こうやってやるんだな」という軽い気持ちで読んでください。
▼解説動画もあります
例題
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を作りました）
| 主項表その1 | 主項表その2 |
 |
 |
新しく主項表ができたので、主項表その2 に対しても、また同じようにペアがないか探します。
グループ(0, 1)とグループ(1, 2)からそれぞれ一つずつ取り出して、ペアになるか確認し、ペアができたら主項表その3に追加して、☆をつける…という作業を、主項表その2に対しても全部調べます。
調べた結果がこちら
| 主項表その1 | 主項表その2 | 主項表その3 |
 |
 |
 |
主項表その3
主項表その3は、もうペアができないので終わりです。
終わったら、☆のついていないものが主項となります。
今回は、0*01、*101、1*11、11*1、00**、*0*0、*01* の 7 つですね。
Step2
Step1で、主項をすべて求めることができました。しかし、これではまだ不要な主項が混じっている可能性があります（カルノー図でも、すべてのループを使わない場合があったと思います）。
なので、ここからは必要な主項を厳選する作業に入ります。
被覆表をつくる
Step2 では、新しく「被覆表」なるものを作成します。
被覆表ア
左端には、Step1 で得られた主項を縦に並べ、上端には、真理値表の $f$ が 1 （* は含まない）となっている 2 進数を横に並べます。
そして、行と列がマッチするような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 も削除します。
被覆表オ
行と列を削除した結果がこちらです。
被覆表5
これ以上は表を小さくできないので、これで終了です。
*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）『論理回路の基礎』サイエンス社.