こんにちは、くるです。
今回は「カルノー図とは何なのか?」「カルノー図を使った2,3,4変数の論理式の簡単化のやり方」について分かりやすく丁寧に解説します!
導入

う~ん…う~ん…
おや?くるる君、何を悩んでいるのですか?


「論理式$ABCD+\bar{A}\bar{B}\bar{C}\bar{D}+ABC\bar{D}+\bar{A}\bar{B}\bar{C}D$を簡単化せよ」って問題が全然分からないんっすよ~…
その問題ならカルノー図を使うのがおすすめですよ。


カルノー図?カルノー図ってなんすか?
カルノー図って?
カルノー図は論理式を簡単化するための道具
カルノー図は簡単に言えば、「論理式を簡単化するための道具」です。
簡単化というのは図のように、論理式をより短い式に変形することです。

論理式を変形する手段として、「ブール代数」がありますが、ブール代数には規則が多く、ブール代数を使った計算は経験がものを言う部分が多いです。
そこで、誰でも簡単に論理式を簡単化するための手段として、「カルノー図」が作られました。
カルノー図の書き方
カルノー図は変数がいくつかによって図の形式が変わります。ここでは2変数、3変数、4変数のときだけを紹介します。
2変数のカルノー図
2変数のカルノー図は最初次の図のようになっています。

「0」は「FALSE」を、「1」は「TRUE」を表しており、各マス目には次のような論理式が対応しています。つまり、$A$の1は「A」を表し、$A$の0は「$\bar{A}$」を表しているということです。

そして、「簡単化する論理式に$AB$があれば、$AB$のマス目を「1」にする、$A\bar{B}$がなければそのまま空白にしておく」というようにカルノー図を作っていきます。
例えば、「論理式$\bar{A}\bar{B}+A\bar{B}+AB$を簡単化せよ」という問題ではカルノー図は次のようになります。

ここをちゃんと理解することが重要です!

3変数のカルノー図
3変数のカルノー図は最初次の図のようになっています。

3変数のカルノー図は変数の数が違う以外は2変数のカルノー図と同じです。
なので、「論理式$\bar{A}\bar{B}\bar{C}+\bar{A}\bar{B}C+ABC$を簡単化せよ」という問題ではカルノー図は次のようになります。


なるほどなるほど
4変数のカルノー図
4変数のカルノー図は最初次の図のようになっています。

4変数のカルノー図も変数の数が違う以外は2変数のカルノー図と同じです。
なので、「論理式$ABCD+\bar{A}\bar{B}\bar{C}\bar{D}+ABC\bar{D}+\bar{A}\bar{B}\bar{C}D$を簡単化せよ」という問題ではカルノー図は次のようになります。

変数が多く、間違えやすいので要チェック!

カルノー図の数字の順番の意味

カルノー図はどうして「00→01→10→11」という順番じゃないのですか?
隣り合う符号同士の符号間距離(ハミング距離)が全て1になるようにしているからです!

符号間距離(ハミング距離)というのは、「2つの符号間でどれだけ数字が違うか」を表すもので、例えば、「00」と「01」の符号間距離は1、「00」と「11」の符号間距離は2です。
カルノー図は隣り合う符号同士の符号間距離が全て1になるようにすることで、うまく論理式の簡単化が出来るようになっています。

これが「00→01→10→11」という順番に変わると、

となってしまいます。このカルノー図ではうまく論理式を簡単化することが出来ないんですよね。
だから、「00→01→11→10」という順番になっているわけです。

理解できたっす!
カルノー図を用いて論理式を簡単化
それでは実際にどうやってカルノー図を用いて論理式を簡単化するのか解説していきます。
次のような例題を考えてみましょう。
ステップ1:カルノー図を描く
与えられた論理式を基にカルノー図を描くと次のようになります。

$A$を$\bar{A}$と間違えてしまうことが多いので注意!

ステップ2:隣り合う1同士を囲む
図のように隣り合う1同士を囲んで1つのグループを作ります。

ステップ3:グループごとに簡単化する
ここは少し難しいので頑張ってください!

例えば図のようなグループは元々「$\bar{A}\bar{B}とA\bar{B}$」という論理式から成り立っています。

$\bar{A}\bar{B}+A\bar{B}=(\bar{A}+A)\bar{B}=\bar{B}$というように簡単化できるのですが、実はこの計算はカルノー図を見れば瞬時に分かるのです。
ではどうすれば分かるのかと言うと、「各変数の0と1の両方が埋まっていたら変数を消去する」です。
例えば、上の図の赤いグループでは$A$の「0」と「1」の行が埋まっており、$B$は「0」の列しか埋まっていません。
そのため、$A$は消去し、$\bar{B}$だけが残るのです。これは先ほどの計算の答えと一致しています。
同じように考えると、次のようなグループは$A$となります。


どうしてこんなことがいえるのかよくわかんないっす…
カルノー図は「論理式を簡単化する計算を図示したもの」と考えましょう!

$\bar{A}\bar{B}+A\bar{B}=(\bar{A}+A)\bar{B}=\bar{B}$という計算が行っていることを、図示して瞬時に行えるようにしたものが「カルノー図」です。
最初のうちはあまり理解できないかもしれませんが、すぐに分かるようになるので、今は分からなくても大丈夫です!
ステップ4:簡単化したものを足し合わせる
ステップ3の計算により、$A$と$\bar{B}$だけが残りました。

よって、
$$\bar{A}\bar{B}+A\bar{B}+AB=A+\bar{B}$$
と簡単化することが出来るといえるのです。
普通にブール代数だけを用いて解くと次のようになります。
$$ \begin{eqnarray} \bar{A}\bar{B}+A\bar{B}+AB &=& \bar{A}\bar{B}+(A\bar{B}+A\bar{B})+AB \\
&=& (\bar{A}\bar{B}+A\bar{B})+(AB+A\bar{B}) \\ &=&
A+\bar{B} \end{eqnarray}$$
3変数のとき
3変数でもやることは2変数のときと変わりません。
例えば、「論理式$\bar{A}\bar{B}\bar{C}+\bar{A}\bar{B}C+ABC$を簡単化せよ」という問題のときカルノー図は次のようになります。

そして、3変数では次のように考えます。


今回の問題では、下の図の右側だけが当てはまります。つまり、$$\bar{A}\bar{B}\bar{C}+\bar{A}\bar{B}C=\bar{A}\bar{B}$$
となり$C$が消去されます。よって、残っている$ABC$を足すと、
$$\bar{A}\bar{B}\bar{C}+\bar{A}\bar{B}C+ABC=\bar{A}\bar{B}+ABC$$
となります。

難しくなってきたっす…
4変数のとき
4変数のときも基本的に2変数のときと考え方は変わりません。
例えば、「論理式$ABCD+\bar{A}\bar{B}\bar{C}\bar{D}+ABC\bar{D}+\bar{A}\bar{B}\bar{C}D$を簡単化せよ」という問題のときカルノー図は次のようになります。

そして、4変数では次のように考えます。$CD$ついては3変数のときと一緒なので、省略します。


今回の問題では$A$, $B$, $C$は消えず、$D$が2個消えます。つまり、
$$\bar{A}\bar{B}\bar{C}\bar{D}+\bar{A}\bar{B}\bar{C}D=\bar{A}\bar{B}\bar{C}$$
$$ABCD+ABC\bar{D}=ABC$$
となるわけです。
よって、$$ABCD+\bar{A}\bar{B}\bar{C}\bar{D}+ABC\bar{D}+\bar{A}\bar{B}\bar{C}D=\bar{A}\bar{B}\bar{C}+ABC$$
が答えです。

あわわわわ…
練習問題
論理式
$$\bar{A}B\bar{C}\bar{D}+\bar{A}B\bar{C}D+\bar{A}BCD+AB\bar{C}\bar{D}+AB\bar{C}D$$
を簡単化せよ。
解答
カルノー図を描くと

となるから、
$$\bar{A}B\bar{C}\bar{D}+\bar{A}B\bar{C}D+\bar{A}BCD+AB\bar{C}\bar{D}+AB\bar{C}D=B\bar{C}+\bar{A}BD$$
となり、簡単化された。
今回はここまで!
お疲れ様でした!

論理式
$$\bar{A}\bar{B}+A\bar{B}+AB$$
を簡単化せよ。