クワイン・マクラスキー法の基本手順を全解説【論理回路】

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

```math
f = \bar{X}\bar{Y}Z + X\bar{Y}Z = \bar{Y}Z
```

**「簡単化」** といいます。
簡単化には大きく三つ方法があり、

1. 式変形
2. カルノー図
3. クワイン・マクラスキー法

です。今回はその中でも、**クワイン・マクラスキー法**について解説します。

カルノー図は直感的で理解しやすいので、知っている人も多いと思いますが、4変数くらいまで、頑張っても6変数くらいまでしか通常は使いません。そこで登場するのがクワイン・マクラスキー法です。
クワイン・マクラスキー法なら、

- 7入力以上の式も簡単化できる
- アルゴリズム的に扱えるので、コンピュータのプログラムとして表現しやすい

という特徴があります。（といっても、10入力以上は計算時間などのコストが大きくなりすぎるようです）

コンピュータ用の手法だといっても過言ではないので、手順を覚えたりする必要はないと思います。「ふーん、こうやってやるんだな」という軽い気持ちで読んでください。

▼解説動画もあります

https://youtu.be/eTS0cRjPWhM 

## 例題

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. すべての「主項」を求める
2. 必要な「主項」を厳選する

**主項**は、カルノー図でいうと1をループで囲んだものに対応します。
Step1でとりあえず考えられる全てのループを洗い出し、Step2でそのループの中から必要なものだけ選び出して式にする、という流れです。

## Step1

Step1では、まず「**主項表**」というのを作ります。

![1_第一次.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3780256/5d6e5d85-eba0-2161-283a-92b76d4127a4.png)

真理値表で $f$ の列が 1 か * となっている行の $XYZW$ の値だけ取り出して、「最小項」の欄に記入していきます。

「グループ」は、最小項にふくまれる 1 の数で分けています。`0011` のように、二つの 1 が含まれていたらグループ2、`1101` のように 1 が 3 つあればグループ 3 という具合です。

ここから、

```math
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を作りました）

<table>
<thead>
    <tr>
        <td>主項表その1</td>
        <td>主項表その2</td>
    </tr>
</thead>
<tr>
    <td><img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3780256/fa948a7f-1f59-5025-1dfd-864ce722275e.png"></td>
    <td><img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3780256/0ffe6c5f-4dd2-cf90-8fb2-5064dde2ec9c.png"></td>
</tr>
</table>

<!--
2_第一次.png
2_第二次.png
-->

新しく主項表ができたので、主項表その2 に対しても、また同じようにペアがないか探します。
グループ(0, 1)とグループ(1, 2)からそれぞれ一つずつ取り出して、ペアになるか確認し、ペアができたら主項表その3に追加して、☆をつける…という作業を、主項表その2に対しても全部調べます。

調べた結果がこちら

<table>
<thead>
    <tr>
        <td>主項表その1</td>
        <td>主項表その2</td>
        <td>主項表その3</td>
    </tr>
</thead>
<tr>
    <td><img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3780256/7dee505e-c724-73bf-43d7-597238a82dd9.png"></td>
    <td><img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3780256/d7f5ebc6-de47-2a1f-ba9e-e51b2c9b2ecb.png"></td>
    <td><img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3780256/c032342e-e2be-a37e-3cb8-de85373fe24a.png"></td>
</tr>
</table>

<!--
3_第一次.png
3_第二次.png
3_第三次.png
-->

### 主項表その3

主項表その3は、もうペアができないので終わりです。

終わったら、☆の**ついていない**ものが主項となります。
今回は、`0*01`、`*101`、`1*11`、`11*1`、`00**`、`*0*0`、`*01*` の 7 つですね。

## Step2

Step1で、主項をすべて求めることができました。しかし、これではまだ不要な主項が混じっている可能性があります（カルノー図でも、すべてのループを使わない場合があったと思います）。
なので、ここからは必要な主項を厳選する作業に入ります。

### 被覆表をつくる

Step2 では、新しく「**被覆表**」なるものを作成します。

被覆表ア
![被覆表1_修正1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3780256/3f14518b-acae-325c-df79-2bd999f54066.png)

左端には、Step1 で得られた主項を縦に並べ、上端には、真理値表の $f$ が 1 （* は含まない）となっている 2 進数を横に並べます。
そして、行と列がマッチするような2進数のところに × を記入します。例えば、一行目の `0*01` の行は、左から一番目が 0 、三番目が 0、四番目が 1 となっている、`0001` と `0101` に × を記入します。

### Step2 の 3 つの手順

被覆表が書けたら、次の3つの手順を順番に行います。

1. ×が 1 つしかない列を見つける。その×がある行は必要な論理式なので解に加えて、その行を削除。また、その行の×が書かれている列をすべて削除
2. ある行Aの×が、すべて行Bにも含まれているときは、行Aを削除
3. ある列Cの×が、すべて列Dにも含まれているときは、列Cを削除



1、2、3まで進めば、また1に戻って繰り返します。
これで表をどんどん小さくしていくことで、最終的な解に必要な論理式をみつけだすことができます。

:::note info
手順2において、笹尾（2005:69-70）では「行Aの論理式の文字数は、行Bの論理式の文字数以上でなければいけない」という旨の条件が記載されていますが、南谷（2009）には記載されていませんでした。どちらが正しいかは分かりませんが、今回は南谷（2009）にのっとって説明します。
:::

言葉だけでは分かりにくいと思うので、実際にやってみましょう。

### 被覆表を解く

#### 被覆表ア

まずは手順1にあるように、「被覆表ア」をみて、**×が一つしかない列**を探します。

再掲 被覆表ア
![被覆表1_修正1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3780256/3f14518b-acae-325c-df79-2bd999f54066.png)

すると、`1000` の列は×がひとつしかありません。よって、その×が書かれている行 <font color="blue">`*0*0`</font> は必要なので、それを覚えておきつつ、`*0*0` の行は削除します。

また、`*0*0` は `0000` `0010` `1000` に×があるので、その列も削除します。

#### 被覆表イ

被覆表アから、行や列を削除すると次のようになります。

被覆表イ
![被覆表2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3780256/008ce915-c142-f887-1c9e-9a9548fe4e54.png)

次は手順2です。`00**` の行は `0001` にしか×がないですが、`0*01` には `0001` と `0101` の二つに×があり、**`00**` の行の×は `0*01` の行の×に含まれている**、といえます。

よって、行`00**`は削除します。

また、同じ理由で `*01*` 行にある×は、`1*11` の行にも同じところに×があるので、`*01*` の行は削除します。

#### 被覆表ウ

行を削除すると、次のようになります。

被覆表ウ
![被覆表3.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3780256/5cb10c57-cd61-5107-3f04-8e1946dfae0e.png)


次は手順3を使います。`0001` の列には `0*01` にしか×がないですが、`0101` の列には `0*01` と `*101` の二つに×があり、**`0001` の列の×は `0101` の列の×に含まれている**、といえます。

よって、列 `0101` は削除します。

同じ理由で、`1011` の列にある×は、`1111` の列にも同じところに×があるので、`1111` の列も削除します。

#### 被覆表エ

列を削除すると、次のようになります。

被覆表エ
![被覆表4.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3780256/50e2e071-0bea-7b68-8710-79bee1ed64af.png)

さきほど手順3が終わったので、次は手順1にまた戻ります。

つまり、ふたたび**×が一つしかない列**を探します。

被覆表エを見ると、`0001` と `1011` の列には×が一つしかありません。よって、その×が書かれている行 <font color="blue">`0*01` `1*11`</font> は解に含まれます。また、その二つの行を削除します。

また、行 `0*01` の×が書かれている列 `0001` と、行 `1*11` の×が書かれている列 `1011` も削除します。

#### 被覆表オ

行と列を削除した結果がこちらです。

被覆表5
![被覆表5.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3780256/15ae5178-416b-b565-fb4b-f6745cdb6c24.png)

これ以上は表を小さくできないので、これで終了です。

<font color="blue">`*101`</font> か <font color="blue">`11*1`</font> のどちらかを選択します。

### 答え

解に含まれるとしていた 2 進数（<font color="blue">青字</font>）を書きだします。

<font color="blue">`*0*0`、`0*01`、`1*11`、[`*101`または`11*1`]

こちらの 5 つです（最後の二つはどちらかを選択）。
これらを論理式になおし、＋でつなげたら f を簡単化できたことになります。
よって、解は

```math
f = \bar{Y}\bar{W} + \bar{X}\bar{Z}W + XZW + Y\bar{Z}W
```
または
```math
f = \bar{Y}\bar{W} + \bar{X}\bar{Z}W + XZW + XYW
```

です。

## まとめ

### クワイン・マクラスキー法のまとめ

クワイン・マクラスキー法をまとめると、

1. 「主項表」をつくり、結合できる2進数のペアをさがす
2. 「被覆表」をつくり、3 つの手順を利用して表を小さくする

という大きく二つのステップを行うことで、論理式を簡単化することができました。

### Step2 で行き詰まる場合

 Step2 の方法で被覆表を小さくしても、途中でこれ以上表が小さくならない！という場合があります。

具体的には、どの列にも 2 つ以上の×がある場合、3 つの手順をすべて使っても表を小さくすることができません。そうなった表のことを「サイクリックテーブル」といいます。

サイクリックテーブルになった場合は、「分枝限定法」や「ぺトリックの方法」を使うことで、先に進めないという問題を解決することができます。詳しく知りたい人は、YouTube動画や参考文献などをごらんください。YouTube では分枝限定法について触れています。

https://youtu.be/eTS0cRjPWhM 

### 参考文献

笹尾勤（2005）『論理設計―スイッチング回路理論―（第4版）』近代科学社.
南谷崇（2009）『論理回路の基礎』サイエンス社.