カルノー

熱力学のカルノーじゃありません。（機械でカルノーといったら熱力学のカルノーサイクル）
論理回路のカルノーです。（電気ならたぶんこっち、のはず）

実験でデジタル回路やったときに、計算式を簡単にするためにカルノー図を習いました。

---

たとえば、4桁の2進数 ABCD に値を入れたときの結果を f として、表のような組み合わせになるとします。

fの値	CD
AB	＼	00	01	11	10
	00	1	1	1	1
	01	0	0	0	0
	11	0	0	0	1
	10	0	0	0	1

このとき、f = 1 となる場合に注目すると
ABCD = 0000 : !A･!B･!C･!D
ABCD = 0001 : !A･!B･!C･ D
ABCD = 0011 : !A･!B･ C･ D
……
…略…
……
ABCD = 1010 : A･!B･ C･!D

これを式で表すと次のようになります。
f = !A･!B･!C･!D + !A･!B･!C･D + !A･!B･C･D + !A･!B･C･!D + A･B･C･!D + A･!B･C･!D

ここで 1 が縦・横あるいは四角形にまとまった部分に注目します。

fの値	CD
AB	＼	00	01	11	10
	00	1	1	1	1
	01	0	0	0	0
	11	0	0	0	1
	10	0	0	0	1

1 が横に並んでいる 1 行目(黄色)は AB = 00 ならば CD がどのような値でも常に f = 1 なので、!A･!B
1 が縦に 2 つ並んでいる右下(水色)は A = 1 かつ CD = 10 ならば B がどのような値でも f = 1なので、A･C･!D、これより
f = !A･!B + A･C･!D
と、式が簡単になります。

---

1 のまとまりを探すとき、同じ 1 を複数のまとまりに含めることができます。

fの値	CD
AB	＼	00	01	11	10
	00	1	1	1	1
	01	0	0	0	1
	11	0	0	0	1
	10	0	0	0	1

このような場合、右上の 1（緑色）を AB = 00 のまとまり（黄色＋緑色）と、CD = 10 のまとまり（水色＋緑色）の両方に含めることができるのです。
これにより、式は次のようになります。
f = !A･!B + C･!D

---

1 のまとまりを探すとき、表の上下左右は反対側につながっていると考えることができます。

fの値	CD
AB	＼	00	01	11	10
	00	1	0	0	1
	01	0	0	0	0
	11	0	0	0	0
	10	1	0	0	1

例えばこの表をそのまま式にすると次のようになります。
f = !A･!B･!C･!D + !A･!B･C･!D + A･!B･!C･!D + A･!B･C･!D

このように四隅が 1 となる場合は 1 のまとまりがないように見えますが、表の上下左右がつながっていると考えられることを利用して、次のように見なすことができます。

fの値	CD
AB	＼	10	00	01	11
	10	1	1	0	0
	00	1	1	0	0
	01	0	0	0	0
	11	0	0	0	0

すると 1 のまとまりができ、B = 0 かつ D = 1 ならば A と C のによらず常に f = 1 となるので、次のように式を簡単にできます。
f = !B･!D

---

表の上下左右がつながっていると見なせるので、最初の例は次のようなまとまりとして考えることもできます。

fの値	CD
AB	＼	00	01	11	10
	00	1	1	1	1
	01	0	0	0	0
	11	0	0	0	1
	10	0	0	0	1

しかし、この場合は最初の例からさらに簡単な式にはできません。
縦・横あるいは四角形の 1 まとまりを作るときに、含まれる 1 の数が 2,4,8,…… と 2ⁿ 個でなければ、式を簡単にすることができないのです。

---

追記の際の参考
カルノー図 Yamamoto's laboratory

カルノー図が役立つ具体例
7セグメントLED用デコーダの作成 組込みソフトウェア研究室

（重複して含められることと、2ⁿ 個に関しては、当時は習った覚えがありません。このカルノー図自体、授業で正式に扱ったものというより「実験のまとめをする際に知っていると便利な知識」くらいの感じだったように思います。2020年の今になって改めて調べてみて知ったため、追記という形でこの記事を更新しました）

---

この記事を公開した当時のあとがき

グラフィックソフトのみで54枚(ジョーカー2枚)のカード裏を描くのが面倒だったので、プログラムに任せてしまおう、と考えたのです。

手元にあったカードを見ると、マークの位置は17箇所。
カードの数字でマークを表示する位置が決まります。
17箇所それぞれについて1～10の入力に対しマークを表示するか、しないかの表を作り、
17箇所それぞれについてカルノー図を描き、
17個の式を得ます。(実際は対称性から10個の式で十分)

マーク表示ON/OFFを判定する配列の要素それぞれに式の計算結果を入れ、
マークの座標を入れた要素数17の配列を使って、マークを出力します。