カルノー図による論理式の簡略化

カルノー図とは

カルノー図はブール代数で構成された論理式を簡略化するのに用います。

主に2~4変数に対して以下のような表を使います。

4変数でのカルノー図の例

セルの並びが00, 01, 11, 10となっているのが重要です。（この並び順を間違えてはいけません！）

これによって隣合っているセル同士で必ず1つの共通項が現れます。

前提知識(ブール代数の公理)

ブール代数を用いた計算では普通の四則演算とは直感的に異なる計算法則が存在します。

以下に示した中で(4)は特に注意が必要です。
また(7)はよく見かけるので覚えてください。

$${(1)　x+y=y+x}$$　　　和の交換法則

$${(2)　xy=yx}$$　　　積の交換法則

$${(3)　x\left(y+z\right)=xy+xz}$$　　　積の分配法則

$${(4)　x+\left(yz\right)=\left(x+y\right)\left(x+z\right)}$$　　　和の分配法則

$${(5)　x+0=x}$$　　　零元

$${(6)　x×1=x}$$　　　単位元

$${(7)　x+\bar{x}=1,　x×\bar{x}=0}$$　　　補元

$${(8)　0\mathrlap{\,/}{=}1}$$

カルノー図から簡略化した式を得る方法

任意のブール式には和積標準形(または乗法標準形)と加法標準形がありますが、これらは複雑で標準形より簡潔な式で表現することを求められる場合が多いです。

そこでカルノー図が大活躍します。

カルノー図での簡略化には「グルーピング」という方法でまとめていきます。

グルーピングのルール

• グルーピングするセルの数字はすべて1

• グルーピングするセルの数は$${2^n}$$個でなるべく広くとる

• カルノー図の左右上下はつながっている

このルールにしたがってグルーピングしたものの共通項を論理積として取り出し、その和を求めると簡略化された等価式となります。

と言ってもよく分からないと思うので以下の例題で確認してみましょう。

例題(1)

先ほど示したカルノー図から簡略化したブール式を取り出してみます。

このカルノー図ではW, X, Y, Zの4変数を扱っています。

上で示したルールに則ると図のようにグルーピングできることがわかります。

グルーピングするセルがダブっていても問題ありません。

グルーピングできたらそれぞれの共通項を取り出します。

共通項とは例えば赤丸の部分について言えば、

$${\bar{W}\bar{X}\bar{Y}\bar{Z},　\bar{W}\bar{X}\bar{Y}Z,　\bar{W}X\bar{Y}\bar{Z},　\bar{W}X\bar{Y}Z}$$

の4つの項があります。これら4つに共通しているのは

$${\bar{W}\bar{Y}}$$

となります。青丸と緑丸についても同様に共通項を取り出すと

• 赤丸：$${\bar{W}\bar{Y}}$$

• 青丸：$${\bar{W}\bar{X}}$$

• 緑丸：$${\bar{X}Y}$$

このように求められるはずです。

なぜこのように共通項だけを取り出せるのかは一度実際に計算してみると良いかもしれません。

例えば青丸の部分は、

$${\bar{W}\bar{X}\bar{Y}\bar{Z}+\bar{W}\bar{X}\bar{Y}Z+\bar{W}\bar{X}YZ+\bar{W}\bar{X}Y\bar{Z}\\=\bar{W}\bar{X}\left(\bar{Y}\bar{Z}+\bar{Y}Z+YZ+Y\bar{Z}\right)\\=\bar{W}\bar{X}\bigl(\bar{Y}\left(\bar{Z}+Z\right)+Y\left(Z+\bar{Z}\right)\bigr)\\=\bar{W}\bar{X}\left(\bar{Y}+Y\right)\\=\bar{W}\bar{X}}$$

 のようにブール代数の公理を用いて計算できます。

ここでカルノー図のセルの並び順が効いてることがわかりますね。

0と1が隣り合うと$${X+\bar{X}=1}$$となりキャンセルできるためグルーピングで共通項だけを取り出すことができます。

以上の結果から簡略化された論理式は、

$${\bar{W}\bar{Y}+\bar{W}\bar{X}+\bar{X}Y}$$

となります。

例題(2)

次は自力でチャレンジしてみましょう。
以下のカルノー図から簡略化した論理式を導き出してください。

グルーピングのルールに則って2つの丸で囲めるはずです。

以下解答です。

以下の図において、

• 赤丸：$${XZ}$$

• 青丸：$${\bar{X}Y\bar{Z}}$$

と求められるはずです。

以上より簡略化された論理式は、

$${XZ+\bar{X}Y\bar{Z}}$$

と求められました。

まとめ

今回はカルノー図について扱いました。

グルーピングのルールをよく理解すれば難しくないと思います。

筆者の大学では試験でカルノー図の読み取りだけでなくカルノー図を書く問題と簡略化された論理式を論理素子で表す問題もセットで出題されていました。

なので書き方と論理素子の扱いもマスターしておくと良いでしょう。

ちなみに5変数以上の場合はクワイン・マクラスキー法というやり方で簡略化します。