下のように、論理式を変形して短くすることを

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）『論理回路の基礎』サイエンス社.