カルノー図（K-map）— Kマップ簡単化ガイド

カルノー図（Karnaugh map、K-map）は、ブール式を手計算の代数処理にあまり頼らず簡単化するための表です。真理値表の出力値を格子状のマップに配置し、隣り合う $1$ をまとめて、各グループごとにより簡単な項を書きます。

ただし条件があります。Kマップが実用的なのは、通常は変数が2個、3個、4個程度の小さな関数です。変数の数が増えると図が読みにくくなり、普通は別の方法のほうが適しています。

カルノー図が表しているもの

Kマップには真理値表と同じ情報が入っていますが、セルは通常の2進順ではなくグレイコード順に並べます。この並べ方により、隣接するセルはちょうど1つの変数だけが異なるようになります。

この「1変数だけ違う」という点が重要です。隣り合う2つのセルがどちらも $1$ なら、変化している変数は簡単化後の項から消せます。

グループ化で変数が消える仕組み

この見た目のルールは、次のようなブール恒等式に基づいています。

$$XY + X\overline{Y} = X$$

この2つの項は $Y$ だけが異なるので、$Y$ は打ち消され、共通部分の $X$ が残ります。Kマップを使うと、この打ち消しのパターンを表の上で直接見つけられます。

カルノー図の例

次を考えます。

$$F(A,B,C) = \sum m(1,3,4,5,7)$$

これは、ミン項 $1$、$3$、$4$、$5$、$7$ で $F=1$ になることを意味します。

3変数のKマップでは、行に $A$、列に $BC$ を取り、列はグレイコード順 $00$、$01$、$11$、$10$ に並べます。

$$\begin{array}{c|cccc} A \backslash BC & 00 & 01 & 11 & 10 \\ \hline 0 & 0 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 & 0 \end{array}$$

まずは可能な中で最大の正しいグループから作ります。中央の2列にある4つの $1$ は、1つのグループになります。この4セルでは $C=1$ が一定で、$A$ と $B$ は変化するので、このグループは次のように簡単化されます。

$$C$$

まだ覆われていない $1$ が1つあります。ミン項 $4$ で、$(A,B,C)=(1,0,0)$ です。これを隣接するミン項 $5$、つまり $(1,0,1)$ と組にします。

このペアでは、$A=1$ と $B=0$ は一定で、$C$ だけが変化します。したがって、このペアは次のように簡単化されます。

$$A\overline{B}$$

よって、簡単化後の式は

$$F(A,B,C) = C + A\overline{B}$$

となります。この短い式は、元のミン項の一覧と同値です。

正しいKマップのグループのルール

グループの大きさは $1$、$2$、$4$、$8$ のように、2のべき乗でなければなりません。

できるだけ大きい正しいグループを使います。大きいグループほど、通常はより多くの変数を消せます。

マップは端でつながっていることを忘れないでください。左端と右端は隣接しており、上端と下端も隣接しています。

対角線上のセルは隣接ではありません。

より大きい、またはより簡単なグループを作れるなら、重なりは許されます。

カルノー図でよくあるミス

通常の2進順を使ってしまう

行や列を $00$、$01$、$10$、$11$ と並べると、隣接関係が正しくありません。Kマップでは、隣り合うセルが1ビットだけ異なるように、必ずグレイコード順を使います。

3個のセルでグループを作る

3セルのグループは正しくありません。グループの大きさは2のべき乗である必要があります。

端どうしの隣接を見落とす

最もよい簡単化の中には、マップの反対側の端にあるセルを使うものがあります。端でつながるルールを忘れると、必要以上に長い答えになりがちです。

すべての $1$ をちょうど1つのグループに入れようとする

それはルールではありません。同じセルを再利用したほうが、より大きなグループを作れて、最終的な式も短くなることがあります。

カルノー図はいつ使うのか

Kマップは、ブール式の簡単化を視覚的な作業に変えてくれるため、デジタル論理や初学者向けのコンピュータ工学でよく使われます。特に、論理回路を描いたり実装したりする前に、より簡単な積和形を求めたいときに便利です。

また、直感を養うのにも向いています。大きな設計ではソフトウェアを使うとしても、Kマップを学ぶと、なぜあるブール項はまとめられて、別のものはまとめられないのかが見えやすくなります。

似た問題をやってみよう

$F(A,B,C)=\sum m(0,2,4,6,7)$ を自分で簡単化してみてください。マップを描き、まず最大の正しいグループを作り、そのあと各グループで一定のままの変数だけを残します。

もう一歩進めたいなら、don't-care 値を含む問題にも挑戦してみましょう。より大きな正しいグループを作るのに役立つときだけ、それらを使ってください。