カルノー図を用いた論理式の簡単化【論理回路】 - 大学の知識で学ぶ電気電子工学

本記事の内容

本記事では、カルノー図について解説しています。

書き方
論理式の簡単化
練習問題

本記事では、$\mathrm{A},\mathrm{B}$ の論理積（AND）、論理和（OR）、$\mathrm{A}$ の否定（NOT）をそれぞれ以下の記号で表します。 $$ \begin{align} \mathrm{X} &= \mathrm{A}\mathrm{B} \tag{AND} \\ \mathrm{X} &= \mathrm{A} + \mathrm{B} \tag{OR} \\ \mathrm{X} &= \bar{\mathrm{A}} \tag{NOT} \end{align} $$

1 論理式の簡単化とカルノー図
2 カルノー図による論理式の簡単化
3 練習問題
4 参考文献

論理式の簡単化とカルノー図

カルノー図（Karnaugh map）は、論理式の簡単化を行うための図で、6変数程度までの論理式を図示することができます。

1.1節では、「論理式の簡単化」とはどのような手続きを指すのかについて解説します。

1.2節から1.4節では、論理式や真理値表が与えられたときのカルノー図の書き方について解説します。

論理式の簡単化とは

複数の論理変数によって、一つの論理変数の真理値が定まるとき、それを論理関数（logic function）といいます。

一般に、論理関数を表す論理式（logical expression）は複数存在します。

論理式の簡単化とは、以下の２条件を満たすような論理式を求めることをいいます。

積項数が最小
リテラル数が最小

ここで、積項（product term）とは、1つ以上の論理変数の論理積を意味し、リテラル数は、各論理変数が出てくる合計回数のことです。

例えば、論理式 $\mathrm{A}\mathrm{B}\mathrm{C} + \mathrm{A}\bar{\mathrm{B}}$ の積項数は2、リテラル数は5です。

論理式の簡単化の例を挙げます。

論理変数 $\mathrm{X}$ が3つの論理変数 $\mathrm{A,B,C}$ を用いて、次式の論理式で表されるとします。

$$ \mathrm{X} = \mathrm{A}\mathrm{B}\mathrm{C} + \mathrm{A}\mathrm{B}\bar{\mathrm{C}} + \mathrm{A}\bar{\mathrm{B}}\mathrm{C} $$

このとき、積項数は3、リテラル数は9です。

上の論理式は、後述のカルノー図を用いることで、次式の論理式に簡単化できます。

$$ \mathrm{X} = \mathrm{A}\mathrm{B}+ \mathrm{A}\mathrm{C} $$

簡単化した論理式の積項数は2、リテラル数は4になります。

カルノー図の書き方（2変数）

2変数 $\mathrm{A},\mathrm{B}$ のカルノー図は下図のように表されます。

各マスは2変数の論理積に対応します。

例として、論理変数 $\mathrm{X}$ を与える論理式が、次式で表されるとします。

$$ \mathrm{X} = \mathrm{A}\mathrm{B}+ \mathrm{A}\bar{\mathrm{B}} $$

$\mathrm{X}$ が $1$ となる論理積に対応するマスに $1$ を、それ以外のマスに $0$ を記入することで、上式の論理式を表すカルノー図は下図で与えられます。

このカルノー図の簡単化を考えてみましょう。

この例では、$1\times 2$ のループを使うことで、出力 $1$ のマスをすべて含めることができます。

ループ内の論理積に注目すると、いずれも論理変数 $\mathrm{A}$ については $1$ で固定されています。

一方で、$\mathrm{B}$ については $0$ と $1$ の両方の真理値を取ります。

したがって、このループに対応する論理積は $\mathrm{A}$ で、求める論理式は出力を $\mathrm{X}$ として、次式で表されます。

$$ \mathrm{X} = \mathrm{A} $$

カルノー図の書き方（3変数）

3変数 $\mathrm{A},\mathrm{B},\mathrm{C}$ のカルノー図は下図のように表されます。

2変数のときと同様、各マスは3変数の論理積に対応します。

ここで、左の列は $00\rightarrow 01\rightarrow 11\rightarrow 10$ のように並ぶことに注意してください。

これは、縦と横に隣り合うマスの論理積について、ただ1つの論理変数の真理値のみが反転するようにしているためです。

同じ長さの2つのビット列を比較したとき、値が異なるビットの個数をハミング距離といいます。カルノー図の縦と横に隣接するマスの論理積のハミング距離は、どれも1になっています。

例として、論理変数 $\mathrm{X}$ を与える論理式が、次式で表されるとします。

$$ \mathrm{X} = \mathrm{A}\bar{\mathrm{B}}\bar{\mathrm{C}} + \mathrm{A}\bar{\mathrm{B}}\mathrm{C} $$

このカルノー図の簡単化を考えてみましょう。

この例では、$1\times 2$ のループを使うことで、出力 $1$ のマスをすべて含めることができます。

青色のループに対応する論理積は $\mathrm{A}\bar{\mathrm{B}}$

ループ内の論理積に注目すると、論理変数 $\mathrm{A},\mathrm{B}$ については、それぞれ $1,0$ で固定されています。

一方で、$\mathrm{C}$ については $0$ と $1$ の両方の真理値を取ります。

したがって、このループに対応する論理積は $\mathrm{A}\bar{\mathrm{B}}$ で、求める論理式は次式で表されます。

$$ \mathrm{X} = \mathrm{A}\bar{\mathrm{B}} $$

カルノー図の書き方（4変数）

4変数 $\mathrm{A},\mathrm{B},\mathrm{C},\mathrm{D}$ のカルノー図は下図のように表されます。

各マスは4変数の論理積に対応します。

ここで、左の列と上の行は $00\rightarrow 01\rightarrow 11\rightarrow 10$ のように並ぶことに注意してください。

これは、3変数のカルノー図と同様に、縦と横に隣り合うマスの論理積について、ただ1つの論理変数の真理値のみが反転するようにしているためです。

例として、論理変数 $\mathrm{X}$ を与える論理式が、次式で表されるとします。

$$ \mathrm{X} = \bar{\mathrm{A}}\mathrm{B}\bar{\mathrm{C}}\bar{\mathrm{D}} + \bar{\mathrm{A}}\mathrm{B}\bar{\mathrm{C}}\mathrm{D} + \bar{\mathrm{A}}\mathrm{B}\mathrm{C}\mathrm{D} + \bar{\mathrm{A}}\mathrm{B}\mathrm{C}\bar{\mathrm{D}} $$

このカルノー図の簡単化を考えてみましょう。

この例では、$1\times 4$ のループを使うことで、出力 $1$ のマスをすべて含めることができます。

青色のループに対応する論理積は $\bar{\mathrm{A}}\mathrm{B}$

ループ内の論理積に注目すると、論理変数 $\mathrm{A},\mathrm{B}$ の取る真理値が、それぞれ $0,1$ で固定されています。

一方で、$\mathrm{C},\mathrm{D}$ については、任意の組み合わせ（$00,01,11,10$ の4通り）を取ります。

したがって、このループに対応する論理積は $\bar{\mathrm{A}}\mathrm{B}$ で、求める論理式は次式で表されます。

$$ \mathrm{X} = \bar{\mathrm{A}}\mathrm{B} $$

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

本節では、カルノー図を用いて論理式を簡単化する方法について解説します。

2.1節では、簡単化の手順を示し、2.2節以降で具体例を用いて、簡単化の方法を解説します。

簡単化の手順

カルノー図を用いた論理式の簡単化の手順は、以下のように記述できます。

カルノー図を用いた論理式の簡単化

すべてのループを記入する
出力が $1$ のマスについて、それを囲うような $2^m\times 2^n\,(m,n=0,1,2)$ のサイズのループを考えられるだけ記入します。ただし、他のループに完全に含まれるようなループは記入しないものとします。
必須のループを求める
ただ1つのループにしか囲まれていない出力 $1$ のマスがある場合、そのマスを囲んでいるループを答えに採用します。
残されたマスを囲むループを選ぶ
手順2で採用したループに含まれていない出力 $1$ のマスについて、手順1で求めたループに少なくとも1つ囲まれるようにループを選びます。このとき、各ループの大きさはなるべく大きく、ループ全体の個数はなるべく少なくします。

具体例として、出力 $\mathrm{X}$ が下図のカルノー図で表される場合について考えてみましょう。

2節で扱うカルノー図（$*$ はドントケアを表し、出力 $0$ の表記は省略した）

ここで、$*$ はドントケア（Don't care）を表し、出力 $0$ の表記は省略しました。

ドントケアは、出力が $0$ と $1$ のどちらでも構わない場合に定義されるものです。

手順１：すべてのループを記入する

まず、出力 $1$ のマスについて、考えられるループをすべて記入します。

このとき、ループ内に出力 $0$ のマスは含まれませんが、ドントケアのマスは含まれてもよいです。

この例では、4つのループを記入することになります。

このとき、他のループにすっぽり収まってしまうループは記入しないことに注意してください。

手順２：必須のループを求める

次に、ただ1つのループにしか囲まれていない出力 $1$ のマスを探し、そのマスを必須のループとします。

今回は、$\bar{\mathrm{A}}\mathrm{B}\mathrm{C}\bar{\mathrm{D}}$ のマスが囲われているループが、必須のループになります。

手順２：必須のループを求める（赤字で記載した出力 $1$ のマスが囲まれているループは、オレンジのループただ1つ）

図のオレンジのループは、最終的な解に必ず含めます。

手順３：残されたマスを囲むループを選ぶ

手順2で求めた必須のループに囲われていない出力 $1$ のマスについて、手順1で求めたループを使って囲います。

今回は $4\times 1$ のループを採用すれば、出力 $1$ のループをすべて網羅することができます。

手順３：残されたマスを囲むループを選ぶ（必須のループに含まれていない出力 $1$ のマスを囲うには、青色のループ1つが必要）

以上より、簡単化された論理式は次式で与えられます。

$$ \mathrm{X} = \bar{\mathrm{C}}\mathrm{D} + \bar{\mathrm{A}}\mathrm{B}\mathrm{C} $$

練習問題

問１

出力 $\mathrm{X}$ が以下のカルノー図で表されるとき、簡単化した論理式を求めてください。

まず、すべてのループを記入します（手順１）。

このとき、カルノー図の四隅を $2\times 2$ のループで囲うことができることに注意してください。

次に、必須のループを求めます（手順２）。

下図の赤字で記載した出力 $1$ のマスは、ただ1つのループのみに囲われたマスで、オレンジ色で記載した3つのループが必須のループになります。

今回は3つの必須のループで出力 $1$ のマスがすべて囲われるので、残されたマスは存在しません。

したがって、手順２で求めた3つの必須のループが最終解になり、求める論理式は次式で表されます。

$$ \mathrm{X} = \bar{\mathrm{A}}\bar{\mathrm{C}} + \bar{\mathrm{A}}\mathrm{D} + \bar{\mathrm{B}}\bar{\mathrm{D}} $$

問２

出力 $\mathrm{X}$ が以下のカルノー図で表されるとき、簡単化した論理式を求めてください。

まず、すべてのループを記入します（手順１）。

次に、必須のループを求めます（手順２）。

下図の赤字で記載した出力 $1$ のマスは、ただ1つのループのみに囲われたマスで、オレンジ色で記載した3つのループが必須のループになります。

最後に、残されたマスを囲むループを選びます（手順３）。

今回は、ループの選び方が２通りあり、それぞれ下図のように表されます。

したがって、求める論理式も2通り存在し、それぞれ次式で表されます。

$$ \mathrm{X} = \begin{cases} \mathrm{B}\bar{\mathrm{C}}\mathrm{D} + \bar{\mathrm{B}}\mathrm{C} + \mathrm{C}\bar{\mathrm{D}} + \bar{\mathrm{A}}\bar{\mathrm{C}}\mathrm{D} \\ \mathrm{B}\bar{\mathrm{C}}\mathrm{D} + \bar{\mathrm{B}}\mathrm{C} + \mathrm{C}\bar{\mathrm{D}} + \bar{\mathrm{A}}\bar{\mathrm{B}}\mathrm{D} \end{cases} $$

問２のように、簡単化した論理式の表現が複数通り存在する場合があります。

問３

出力 $\mathrm{X}$ が以下のカルノー図で表されるとき、簡単化した論理式を求めてください。

まず、すべてのループを記入します（手順１）。

次に、必須のループを求めます（手順２）。

下図の赤字で記載した出力 $1$ のマスは、ただ1つのループのみに囲われたマスで、オレンジ色で記載した3つのループが必須のループになります。

今回は3つの必須のループで出力 $1$ のマスがすべて囲われるので、残されたマスは存在しません。

したがって、手順２で求めた3つの必須のループが最終解になり、求める論理式は次式で表されます。

$$ \mathrm{X} = \mathrm{B} + \bar{\mathrm{C}} + \mathrm{D} $$

別解）出力が $0$ のマスについて論理式を簡単化することを考えます。

上図のような $2\times 1$ のループを囲うことで、$\bar{\mathrm{X}}$ は次式で表されます。

$$ \bar{\mathrm{X}} = \bar{\mathrm{B}}\cdot\mathrm{C}\cdot\bar{\mathrm{D}} $$

ただし、論理積（AND）を $\cdot$ で明示しました。

上式の両辺に否定を取ると、ド・モルガンの法則より、

$$ \mathrm{X} = \bar{\bar{\mathrm{X}}} = \overline{\bar{\mathrm{B}}\cdot\mathrm{C}\cdot\bar{\mathrm{D}}} = \mathrm{B} + \bar{\mathrm{C}} + \mathrm{D} $$

を得ます。

ド・モルガンの法則は、論理変数 $\mathrm{A},\mathrm{B}$ を用いて、$\overline{\mathrm{A}\cdot\mathrm{B}} = \bar{\mathrm{A}} + \bar{\mathrm{B}}$ と表されます。