カルノー図・ベイチ図による論理式の簡単化
このページでは、カルノー図およびベイチ図を用いて論理式を簡単化する方法を説明します。
カルノー図とベイチ図の違いは変数と数字の書き方のみなので、基本的に同じだと思っていただいてかまいません。
実際に書く場合は、ベイチ図の方が直観的であるため、ベイチ図を用いる方が良いかもしれません。（詳しく分けないでどちらもカルノー図と呼ぶこともあります。）
カルノー図の基本
まずは2変数の場合を考えます。
この図では、変数\(A\)と変数\(B\)の全ての組み合わせを表しています。
赤で囲まれた部分が、変数\(A\)が真（1）の時、青で囲まれた部分が、変数\(B\)が真（1）の時を表しています。
例えば以下のような論理式があったとします。ブール代数の公式からすぐに簡単化できますが、ここではカルノー図を用いて簡単化してみます。
\(f = A \cdot B + A\)
この論理式をOR（+）の部分で分離し、それぞれの項に対応する部分に1を書いていきます。
まずは、内側に何も記載されていないカルノー図を書きます。
次に、論理式の各項に対応する部分に1を書きます。
ここでは、\(A \cdot B\)に対応する部分に1を書きます。（Aであり、Bである部分なので右下の部分です。）
次に、\(A\)に対応する部分に1を書きます。（右側の2つです。）
\(A\)に対応するのは10（右上）と11（右下）の部分ですが、11の部分には1が書かれているので、10の部分にのみ1を書きます。
図が完成しました。
ここで、図をよく見てみると、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変数
ここまで、2変数の場合を考えてきましたが、その程度であれば、図を使うまでもありません。
そこで、今度は3変数の場合を考えてみます。
ここからは、カルノー図派の人にも、ベイチ図派の人にも優しいように、カルノー図とベイチ図の両方の特性を持つ図を用います。
この図では、変数\(A\)と変数\(B\)と変数\(C\)の全ての組み合わせを表しています。
ところで、「なぜ、00, 01, 10, 11の順ではなく、00, 01, 11, 10の順になっているのか？」と思った方もいるかもしれません。
それは、カルノー図を用いて論理式を簡単化する際に、隣り合う符号が1ビットしか違わないようにするためです（このような並びはグレイコードとも呼ばれます）。
この性質は、端と端をつないでループさせた場合にも成り立ちます。
00, 01, 10, 11の順にすると、01→10や、ループでつないだ11→00で2ビット同時に変わる箇所ができてしまいます。
00 → 01 → 10 → 11 → (00)
00, 01, 11, 10の順にすると、ループでつないだ10→00も含めて、どの隣同士も1ビットしか変わりません。
00 → 01 → 11 → 10 → (00)
4変数
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の集合を囲っていくわけですが、どこでも囲っていいわけではありません。
以下のような法則に基づき、囲っていきます。
- 隣り合った1を囲う（1が単体でしか存在できなければ単体で囲う）
- 囲いは長方形にする（L字型などは不可）
- 一つの囲いの1の数は\(2^n\)個（1, 2, 4, 8, 16...個）
- なるべく大きく囲む
- 1は何回でも使える
ここでの「隣り合う」とは端同士も含むことに注意してください。
良い例
以下に、良い例を示します。
普通に囲み、\(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\)
関連ツール
このサイトには、論理式を扱うWebツールがあります。答え合わせなどに活用してください。
- クワイン・マクラスキー法 オンライン計算ツール — 論理式を入力すると最小積和形へ自動で簡単化します。カルノー図が扱いにくくなる5変数以上でも機械的に計算できます。
- 論理式から真理値表 作成ツール — 論理式から真理値表を自動生成します。
- 論理式から回路図 変換ツール — 簡単化した論理式を論理回路図にできます。