学ぶ › トピック 5
クワイン・マクラスキー法を手順どおりに解説
読了時間：約 7 分 · bitGateLab チーム
カルノー図は 4 変数までなら手早く使えますが、目に頼る方法であり、5 変数以上になると実用的ではなくなります。クワイン・マクラスキー法は、同じ仕事を表と機械的な規則で行います。ひらめきは必要なく、必ずすべての主項が見つかり、論理関数を簡単化するプログラムの基礎にもなっています。この記事では、この方法の二つの段階を理解し、必須主項の見つけ方を学び、4 変数の例題を最初から最後まで解きます。
用語：内包項と主項
- F の内包項（インプリカント）とは、それが 1 になれば F も必ず 1 になる積項のことです。F の各最小項は内包項であり、カルノー図の正しいグループもすべて内包項です。
- その中で主項とは、それ以上大きくできない内包項のことです。変数を一つ取り除くと、F が 0 になる行まで覆ってしまいます。カルノー図の最大グループに相当します。
- さらに必須主項とは、ほかのどの主項も覆っていない最小項を少なくとも一つ覆っている主項のことです。どの最小解にも必ず現れます。
この方法は二段階からなります。まず項を組み合わせてすべての主項を見つけ、次に、すべての最小項を覆う最小の主項の組を選びます。
第 1 段階：項を組み合わせる
各項を 2 進数で書き、消去された変数の位置はハイフンで示します。たとえば変数が A、B、C、D のとき、項 0-11 は ACD を意味します（B が消去されています）。
- 最小項を、2 進コードに含まれる 1 の個数でグループに分けます。
- あるグループの各項を、次のグループの各項と比べます。1 ビットだけ異なる場合は、その位置にハイフンを置いて組み合わせ、元の二つの項に使用済みの印を付けます。
- 新しくできたリストで同じことを繰り返します。組み合わせられるのは、ハイフンが同じ位置にある項どうしだけです。
- これ以上何も組み合わせられなくなったとき、一度も印の付かなかった項が主項です。
第 2 段階：主項表
主項ごとに一行、関数の最小項ごとに一列の表を作ります（ドントケア条件には列を設けません）。各主項がどの最小項を覆うかに印を付けます。そのあと、次のようにします。
- 印が一つしかない列を探します。その行の主項は必須です。それを選び、その主項が覆うすべての列を消します。
- 残った列について、それらを覆う最小数の主項を選びます。二つの主項が同じものを覆うなら、どちらでもかまいません。リテラルの少ないほうを優先します。
例題（全手順）。 F(A, B, C, D) = Σm(0, 2, 3, 5, 7, 8, 10, 11, 13, 15) を簡単化します。
手順 1：1 の個数でグループに分ける。
| 1 の個数 | 最小項 |
|---|---|
| 0 | 0 (0000) |
| 1 | 2 (0010), 8 (1000) |
| 2 | 3 (0011), 5 (0101), 10 (1010) |
| 3 | 7 (0111), 11 (1011), 13 (1101) |
| 4 | 15 (1111) |
手順 2：最初の組み合わせ（ペア）。 隣り合うグループどうしを比べます。8 は 3 とも 5 とも組み合わせられません。異なるビットが一つだけではないからです。
| グループ | できたペア |
|---|---|
| 0 と 1 | (0,2) 00-0; (0,8) -000 |
| 1 と 2 | (2,3) 001-; (2,10) -010; (8,10) 10-0 |
| 2 と 3 | (3,7) 0-11; (3,11) -011; (5,7) 01-1; (5,13) -101; (10,11) 101- |
| 3 と 4 | (7,15) -111; (11,15) 1-11; (13,15) 11-1 |
十個の最小項すべてに使用済みの印が付きました。ペアは 13 組です。
手順 3：二度目の組み合わせ（四つ組）。 ハイフンが同じ位置にあり、1 ビットだけ異なるペアどうしを組み合わせます。
- (0,2) と (8,10)、または (0,8) と (2,10)：-0-0、0、2、8、10 を覆います。
- (2,3) と (10,11)、または (2,10) と (3,11)：-01-、2、3、10、11 を覆います。
- (3,7) と (11,15)、または (3,11) と (7,15)：--11、3、7、11、15 を覆います。
- (5,7) と (13,15)、または (5,13) と (7,15)：-1-1、5、7、13、15 を覆います。
13 組のペアはすべて、いずれかの四つ組に使われました。四つの四つ組は、もう互いに組み合わせられません（ハイフンの位置が同じで、しかも 1 ビットだけ異なる相手がないからです）。したがって、主項は次のとおりです。
- P1 = -0-0 = BD
- P2 = -01- = BC
- P3 = --11 = CD
- P4 = -1-1 = BD
手順 4：被覆表。
| 主項 | 0 | 2 | 3 | 5 | 7 | 8 | 10 | 11 | 13 | 15 |
|---|---|---|---|---|---|---|---|---|---|---|
| P1 BD | ✔ | ✔ | ✔ | ✔ | ||||||
| P2 BC | ✔ | ✔ | ✔ | ✔ | ||||||
| P3 CD | ✔ | ✔ | ✔ | ✔ | ||||||
| P4 BD | ✔ | ✔ | ✔ | ✔ |
手順 5：必須主項。 列 0 と列 8 には P1 の印しかないので、P1 は必須です。列 5 と列 13 には P4 の印しかないので、P4 も必須です。この二つを合わせると 0、2、5、7、8、10、13、15 を覆います。
手順 6：残りを覆う。 最小項 3 と 11 が残っています。P2 は両方を覆い、P3 も両方を覆います。どちらを選んでも、同じリテラル数で解が完成します。
結果：F = BD + BD + BC、または F = BD + BD + CD。どちらも三つの項、六つのリテラルからなります。
この関数をカルノー図に描くと、P1 は四隅、P4 は中央のブロック、P2 は行 00 と行 10 の列 11 と列 10（端をまたいでつながる）、P3 は列 11 全体になります。表を使うこの方法は、カルノー図を見なくても同じ結果にたどり着きます。
ドントケア条件と巡回表
ドントケア条件（X）は、第 1 段階では 1 と同じように扱って含めます。より大きな内包項を作る助けになるからです。第 2 段階では除外します。覆う義務がないので、列を設けません。X だけでできた主項は、決して必要になりません。
必須主項を選んだあとで、あるいは最初から、どの列にも印が二つ以上あって、明らかな決め手がないことがあります。このような状況を巡回表と呼びます。これは試しながら解きます。主項を一つ選び、それが覆うものを取り除いて同じことを繰り返し、得られた解どうしを比べます。大きな表には、ありうる被覆をすべて列挙する代数的な手順（ペトリック法）があります。
よくある間違い
- 0-01 と 00-1 のように、ハイフンの位置が異なる項を組み合わせる。1 ビットしか違わないように見えても、これは正しくありません。
- 組み合わせるたびに二つの項へ使用済みの印を付けるのを忘れ、主項でないものを主項として挙げてしまう。
- 被覆表にドントケア条件の列を作る。そうすると、必要もないのに覆わなければならなくなります。
- 必須主項より先に、必須でない主項を選ぶ。まず必須主項を確保し、そのあとで残りを決めましょう。
- コードから項を書き起こすときに間違える。-0-1 では、B は否定つき（値が 0）、D は否定なし（値が 1）で、A と C は消えます。
シミュレータで試してみよう
シミュレータはこの種の手順で関数を簡単化するので、手で行った作業の各段階の確認に使えます。
- 4 変数の真理値表を作り、例題の最小項を 1 にします。
- 第 1 段階と第 2 段階を紙の上で行い、結果を書いておきます。
- ツールが示す最小の式とそのカルノー図を見て、どのグループがどの主項に対応するかを確認します。
- 二通りの解をどちらも同じキャンバス上で回路に変換し、入力を切り替えて、常に同じ出力になることを確かめます。
練習問題
- F(A, B, C, D) = Σm(0, 1, 3, 7, 8, 9, 11, 15) の主項と最小の式を求めてください。
解答
主項：-00-（BC）、-0-1（BD）、--11（CD）。列 0 を覆うのは BC だけ、列 7 を覆うのは CD だけです。どちらも必須で、この二つですべてを覆います。F = BC + CD。主項 BD は不要です。
- F(A, B, C) = Σm(0, 1, 2, 5, 6, 7) を解いてください。必須主項はありますか。
解答
ペアは 00-、0-0、-01、-10、1-1、11- で、どれも四つ組にはなりません。つまり主項は六つです。どの最小項もちょうど二つの主項に覆われるので、必須主項はありません（巡回表）。最小解は二つあります。AB + BC + AC、または AC + BC + AB です。
- F(A, B, C, D) = Σm(2, 3, 7, 9, 11, 13) + d(1, 10, 15) を簡単化してください。
解答
第 1 段階に X を含めると、主項が四つ得られます。-0-1（BD）、-01-（BC）、--11（CD）、1--1（AD）です。表では 1、10、15 の列を作りません。2 を覆うのは BC だけ、7 を覆うのは CD だけ、13 を覆うのは AD だけです。三つとも必須で、3、9、11 も覆います。F = BC + CD + AD。
- 第 1 段階で、1 が一つのグループと 1 が三つのグループを比べないのはなぜですか。
解答
1 が一つのコードと 1 が三つのコードは、少なくとも二つのビットが異なるからです。組み合わせるには、ちょうど一つのビットだけが異なっていなければなりません。