1. カルノー図とは
カルノー図とは、真理値表を格子として描き直したものです。1953 年にベル研究所のモーリス・カルノーが、スイッチ回路を目で見て簡単化するために考案しました。小さなブール関数を手で最簡化する方法としては今も最速です。代数も、覚えるべき法則も要らず、必要なのは長方形だけです。
図の各マスは真理値表の 1 行にあたります。単なる並べ替え以上のものにしているのは、その行の並べ方です。隣り合うマスは、ちょうど 1 つの変数だけが異なります。
この性質だけで話は済みます。隣り合う 2 つのマスがともに真なら、その間で変化する変数は式を真にしている原因ではありえません。だからその変数は消え、1 つの項が両方のマスを覆います。簡単化とは、できるだけ大きな長方形を描くことになるのです。
2. 列の並びが妙に見える理由
カルノー図の列は 00、01、10、11 とは数えません。00、01、11、10 と進みます。これは反射型グレイコードで、隣り合う値が 1 ビットだけ異なる並べ方です。二進法どおりに数えると 01 の隣が 10 になり、2 ビット違ってしまうため、隣り合うマスから何も読み取れなくなります。
| A \ BC | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | 0 | 1 | 3 | 2 |
| 1 | 4 | 5 | 7 | 6 |
端どうしも隣り合っています。左端と右端の列は 1 変数しか違わず、上端と下端の行も同じなので、グループは片方の端から出て反対側へ続けられます。4 変数の図で四隅が 1 つのグループになるのはこのためです。カルノー図は本当はトーラスの上に描かれており、平らな紙面は便宜にすぎません。
3. 1 をまとめる
図から最簡の積和形を読み取るには、1 のマスをすべて長方形のグループで覆います。規則は 4 つです。
- グループは 1、2、4、8 … 個のマスからなる長方形で、各辺の長さは 2 のべき乗です。
- グループは図の端をまたいで回り込めます。横方向でも縦方向でも、その両方でもかまいません。
- グループどうしは重なってかまいません。二重に覆っても損はありませんが、覆い残しがあると関数が変わってしまいます。
- 各グループはできるかぎり大きくし、そのうえで、すべての 1 を覆えるかぎり少ない数のグループにします。
グループ 1 つが項 1 つになります。読み方は、グループ全体で値の変わらない変数を探すこと。その変数が項に現れ（1 ならそのまま、0 なら否定）、変化する変数はすべて消えます。2 マスのグループでは変数が 1 つ、4 マスでは 2 つ、8 マスでは 3 つ減ります。最簡の式は、これらの項の選言です。
4. 例題
(A ∧ B) ∨ (¬A ∧ C) ∨ (B ∧ C ∧ D) を考えます。図は 4 変数で、行が A と B、列が C と D です。
| AB \ CD | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | 0 | 0 | 1 | 1 |
| 01 | 0 | 0 | 1 | 1 |
| 11 | 1 | 1 | 1 | 1 |
| 10 | 0 | 0 | 0 | 0 |
2 つのグループですべての 1 を覆えます。1 つは A = 0 の 2 行と C = 1 の 2 列が交わる 4 マスの塊です。この中では B と D が変化するので消え、項は ¬A ∧ C になります。もう 1 つは A と B がともに 1 の行全体で、4 列すべてにわたります。C と D が変化するので、残るのは A ∧ B です。
したがって最簡形は (¬A ∧ C) ∨ (A ∧ B) です。元の式の 3 番目の項 B ∧ C ∧ D は消えました。その項が覆っていたマスは、すでに 2 つのグループのどちらかが覆っていたからです。吸収律を目に見える形にすると、これになります。
5. 主項と必須主項
これ以上大きくできないグループを主項（プライムインプリカント）と呼びます。主項を列挙するのは問題の易しい半分で、どれを残すかを選ぶ方が失敗しやすい半分です。
あるマスを覆う主項が 1 つしかないなら、その主項は必須です。そのマスを覆うものが他にない以上、どんな最簡形からも外せません。まず必須主項を取り、残りのマスを、残った主項のうちできるだけ少ない数で覆います。
貪欲に進めること、つまり毎回いちばん大きなグループを取ることは魅力的ですが、いつもうまくいくとは限りません。どの主項も必須でなく、すべてのマスが二重に覆われる循環表では、貪欲な選択が最良解より 1 項多くなることがあります。このサイトの図は代わりに残る選択肢をすべて調べます。4 変数ならその手間はほぼゼロです。
6. 代わりに 0 をまとめる
ここまでの話は 0 についてもそのまま成り立ちます。同じ長方形で 0 を覆い、各グループをリテラルを反転して読み（グループ全体で 1 の変数は否定、0 の変数はそのまま）、グループどうしを ∨ ではなく ∧ でつなぎます。
できあがるのは和積形です。選言の連言で、式が偽になるマスでちょうど偽になり、それ以外では真になります。どちらの形が短いかは関数しだいで、1 の少ない式は積和形が短く、0 の少ない式は和積形が短くなります。決める前に図から両方を読んでみる価値があります。
7. より大きな図と、ドントケア
5 変数や 6 変数は、4 変数の図を 2 枚または 4 枚重ねて描き、隣り合う層の同じ位置のマスを隣接とみなします。可能ではありますが、この方法を目で見て分かるものにしていた隣接関係が、見るものではなく覚えるものになってしまいます。それ以上は、クワイン・マクラスキー法が同じ仕事を表の形で行います。まさにこのグループ化を機械化したもので、このサイトの図の背後でも動いています。
ハードウェア設計ではもう 1 つ考え方が加わります。決して現れない入力の組み合わせがあり（二進化十進数の桁が 1010 になることはありません）、その場合に回路が何を出力しようと設計者は気にしません。そうしたマスは X と記し、グループがより大きくなる方の値として読んでかまいません。この計算機の図は式から作られ、どの割り当てにも値があるので、ドントケアのマスは現れません。
8. 実際に試す
2 変数から 4 変数までの式を計算機に入力すると、真理値表の下に図が描かれ、各グループがそれぞれの色で囲まれ、その下に最簡形が示されます。和積形に切り替えれば、0 がまとめられる様子を見られます。