このページでは、カルノー図およびベイチ図を用いて論理式を簡単化する方法を説明します。
カルノー図とベイチ図の違いは変数と数字の書き方のみなので、基本的に同じだと思っていただいてかまいません。
実際に書く場合は、ベイチ図の方が直観的であるため、ベイチ図を用いる方が良いかもしれません。（詳しく分けないでどちらもカルノー図と呼ぶこともあります。）
カルノー図の基本
まずは２変数の場合を考えます。
この図では、変数\(A\)と変数\(B\)の全ての組み合わせを表しています。
赤で囲まれた部分が、変数\(A\)が真（１）の時、青で囲まれた部分が、変数\(B\)が真（１）の時を表しています。
例えば以下のような論理式があったとします。ブール代数の公式からすぐに簡単化できますが、ここではカルノー図を用いて簡単化してみます。
\(f = A \cdot B + A \)
この論理式をOR(+)の部分で分離し、それぞれの項に対応する部分に1を書いていきます。
まずは、内側に何も記載されていないカルノー図を書きます。
次に、論理式の各項に対応する部分に１を書きます。
ここでは、\(A \cdot B\)に対応する部分に１を書きます。（Aであり、Bである部分なので右下の部分です。）
次に、\(A\)に対応する部分に１を書きます。（右側の２つです。）
すでに、\(A\)に対応する部分は、10(右上)と11(右下)の部分ですが、すでに、11の部分に1が書かれているので、10の部分にのみ1を書きます。
図が完成しました。
ここで、図をよく見てみると、１が書かれている部分が連続していることがわかります。
しかも、1が書かれている部分は\(A\)に対応する部分のみであるため、
\(A \cdot B + A = A\)
となります。
ベイチ図の基本
残念ながらカルノー図は、あまり直観的ではありません。
そこで、\(A\)や\(B\)の領域として表現したものをベイチ図と呼びます。
この図を使うことで、カルノー図よりも直観的に論理式を簡単化することができます。
例えば、
\(f = A \cdot B + \overline A \cdot B \)
という論理式があったとします。
ここでは、\(A \cdot B\)は右下の部分、\(\overline A \cdot B\)は左下の部分に対応するため、すぐに結果が\(B\)であると、判断することができます。
カルノー図（3変数以上）
図の作り方
3変数
ここまで、２変数の場合を考えてきましたが、その程度であれば、図を使うまでもありません。
そこで、今度は３変数の場合を考えてみます。
ここからは、カルノー図派の人にも、ベイチ図派の人にも優しいように、カルノー図とベイチ図の両方の特性を持つ図を用います。
この図では、変数\(A\)と変数\(B\)と変数\(C\)の全ての組み合わせを表しています。
ところで、「なぜ、00, 01, 10, 11の順ではなく、00, 01, 11, 10の順になっているのか？」と思った方もいるかもしれません。
それは、カルノー図を用いて論理式を簡単化する際に、隣同士の値が1ビットしか違わないようにするためです。
そうすると、ループさせた時に、隣同士の値が同じになります。
00, 01, 10, 11の順にすると、隣同士の値が異なる部分があるため、ループさせることができません。
00 01 10 11 00 01 10 11
00, 01, 11, 10の順にすると、隣同士の値が同じになるため、ループさせることができます。
00 01 11 10 00 01 11 10
4変数
４変数の場合は、以下のようになります。
これは、変数\(A\)と変数\(B\)と変数\(C\)と変数\(D\)の全ての組み合わせを表しています。
以下はそれぞれの領域の例です。
例題
例題として、以下の論理式をカルノー図に書いてみてください。
\(f = A \cdot B \cdot C \cdot D + A \cdot B \cdot C \cdot \overline D + A \cdot \overline B \cdot C \cdot D + A \cdot \overline B \cdot C \cdot \overline D\)
上記のようになれば正解です。
図の見方
ここまでで、論理式を見て、カルノー図を書くことができるようになったので、ここからは、どのように論理式に戻すかを説明していきます。
これから、書いた１の集合を囲っていいくわけですが、どこでも囲っていいわけではありません。
以下のような法則に基づき、囲っていきます。
- 隣り合った１を囲う(１が単体でしか存在できなければ囲う)
- なるべく大きく囲む
- 一つの囲いの1の数は \(2^n\)個(1,2,4,8,16...個)
- １は何回でも使える
ここでの"隣り合う"とは端同士も含むことに注意してください。
良い例
以下に、良い例を示します。
普通に囲み、\(f=B \cdot D\)とわかります。
2個のループにしない4個で1つの囲いにし、\(f=\overline B \cdot \overline C\)とわかります。
角同士も一つの囲いとみなし、\(f=\overline B \cdot \overline D\)とわかります。
1が重複していてもよく、\(f=\overline A + B \cdot D\)とわかります。
悪い例
以下に、悪い例を示します。
ひとつの囲いにできるのに分けてしまっています。
\(2^n\)個になっていません。
囲い方はあっていますが緑の部分はなくても良いので、答えは、\(f=A \cdot D + \overline B \cdot \overline D\)になります。(\(A \cdot \overline B\)は必要ないので今回は悪い例にしました。)
例題
例題として、以下の論理式をカルノー図に描き、簡単化してください。
\(f = A \cdot \overline B \cdot C \cdot D + A \cdot \overline B \cdot C \cdot \overline D + \overline A \cdot B \cdot D + A \cdot B\)
上記のようなカルノー図を描くことができ、以下のように簡単化できます。
\(f = A \cdot B + A \cdot C + B \cdot D\)
