次の3変数の論理式からカルノー図を作成し、論理式の簡略化(論理圧縮)を行います。
$$ Z = \overline{A} \ \overline{B} \ \overline{C} + \overline{A} \ \overline{B} C + AB\overline{C} + A \overline{B} \ \overline{C} + A\overline{B}C \ \ \ \ \ \text{(1)}$$
2行4列+見出しの表を作成する
3変数のうち、2変数を行方向に、1変数を列方向に割り当てることにします。まず2行4列の表を作成します(図1)。表の上方向と左方向に、変数の見出しを書く部分も作ります。
図1: 2行4列+見出しの表
変数の割り当て
変数A,B,Cを行、列に割り当てます。ここでは行方向にAとBを、列方向にCを割り当てます(図2)。割り当てに決まりはありません。行方向にAとCを、列方向にBを割り当てても最終的な結果は同じです。
図2: A,B,Cを行、列に割り当てる
変数の見出しを書く
変数A,B,Cが取り得る値を行、列の見出しに書きます(図3)。行方向はAとBの2変数の組み合わせになります。ここで注意することは、隣同士のセルはAとBの変化を1箇所だけにすることです(Grayコード)。具体的には、00→01→11→10と変化するように見出しを書く必要があります。00→01→10→11と変化させると、01→10の部分で2箇所の値が変化しているので、カルノー図が機能しなくなります。
列方向のCは1変数なので0と1を見出しに書きます。0と1は、どちらを先に書いても良いです。
図3: A,B,Cの取り得る値を書く
セルに値を書き込む
カルノー図を作成する論理式は主加法標準形で書かれているので、論理式の各項の組み合わせに対応するセルに1を書きます(図4)。次に、余ったセルに0を書きます。これで論理式(1)に対応したカルノー図の完成です。
$$ Z = \overline{A} \ \overline{B} \ \overline{C} + \overline{A} \ \overline{B} C + AB\overline{C} + A \overline{B} \ \overline{C} + A\overline{B}C \ \ \ \ \ \text{(1)}$$
図4: 論理式から1の部分を埋める
論理式の最適化
ここから、回路の最適化を行います。カルノー図で1が連続している部分に注目し、○で囲みます。○で囲む時のルールは次の通りです。
- 1の部分を○で囲む
- 囲んだ中はすべて1になっていること
- 囲んだセルは縦と横を2のべき乗にする
- 囲みはできるだけ大きくする
- 表の上下、左右の両端はつながっている
- セルは何度囲んでもよい(囲みが重なってもよい)
“表の上下、左右の両端はつながっている”は、上下と左右は端がなく、リング状につながっていることを意味します。具体的には図5のAB=10の右端は、左端AB=00につながっていると考えます(左右はメルカトル図法の世界地図のようにつながっている)。また、C=1の下側は上側のC=0につながっていると考えます。
図5: 1の部分をできるだけ大きく囲む
ルールに従って1の部分をできるだけ大きく囲むと、図5のように2つの囲み(赤と青)ができます。
まず、赤い囲みに着目します。この部分だけの論理式を主加法標準形で作成すると式(2)になります。
$$ z1 = AB \ \overline{C} + A \overline{B} \ \overline{C} = A \ \overline{C} ( B + \overline{B} )\ \ \ \ \ \text{(2)}$$
ブール代数より、式(2)の\((B + \overline{B})\)部分は1になります。これは、Bの値が0でも1でも結果は1になるということを意味します。つまり、Bはあってもなくてもどちらでもよいので冗長です。このことから、結局赤い囲みは式(3)になります。
$$ z1 = A \ \overline{C} \ \ \ \ \ \text{(3)}$$
次に、青い囲みに着目します。この部分だけの論理式を主加法標準形で作成すると式(4)になります。
\begin{equation}
\begin{split}
z2 &= \overline{A} \ \overline{B} \ \overline{C} + \overline{A} \ \overline{B} \ C + A \overline{B} \ \overline{C} + A \overline{B} \ C \ \ \ \ \ \text{(4)}\\
&= \overline{B} ( \overline{A} \ \overline{C} + \overline{A} C + A \overline{C} + AC) \\
&= \overline{B} ( \overline{A} ( \overline{C} + C ) + A( \overline{C} + C )) \\
&= \overline{B} ( \overline{A} + A) \\
&= \overline{B}
\end{split}
\end{equation}
実際には、このような論理式の展開を行わなくても、図5の青い囲みで0と1の両方が入ってる変数を冗長と考えれば \( z2 = \overline{B} \)ということがわかります。
z1とz2の結果から、最終的な論理式は主加法標準形で次のようになります。
$$ Z = z1 + z2 = A \ \overline{C} + \overline{B} \ \ \ \ \ \text{(5)}$$