こんにちは、krです。
今回は「カルノー図とは何なのか？」「カルノー図を使った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$のマス目を「１」にする、$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」という順番になっているわけです。
理解できたっす！
カルノー図を用いて論理式を簡単化
それでは実際にどうやってカルノー図を用いて論理式を簡単化するのか解説していきます。
次のような例題を考えてみましょう。
ステップ１：カルノー図を描く
与えられた論理式を基にカルノー図を描くと次のようになります。
$A$を$\bar{A}$と間違えてしまうことが多いので注意！
ステップ２：隣り合う1同士を囲む
図のように隣り合う1同士を囲んで1つのグループを作ります。
ステップ３：グループごとに簡単化する
ここは少し難しいので頑張ってください！
例えば図のようなグループは元々「$\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}$という計算が行っていることを、図示して瞬時に行えるようにしたものが「カルノー図」です。
最初のうちはあまり理解できないかもしれませんが、すぐに分かるようになるので、今は分からなくても大丈夫です！
ステップ４：簡単化したものを足し合わせる
ステップ３の計算により、$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$が２個消えます。つまり、
$$\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$$
を簡単化せよ。