カルノー図（Karnaugh map, K-map）とは、ブール代数の論理式を簡略化するために使用される視覚的なツールです。カルノー図は、複雑な論理式や真理値表を簡単に解釈・簡略化する手法を提供し、特にデジタル回路の設計において役立ちます。
カルノー図の基本概念
カルノー図は、論理変数の組み合わせを2次元のグリッド上に配置したもので、各セルは変数の特定の真理値の組み合わせに対応しています。この図を使うことで、論理式の簡略化や最小化が視覚的に行いやすくなります。
カルノー図の特徴
- セルの配置: 各セルは、論理変数のすべての組み合わせ（0または1のすべてのパターン）に対応しています。
- 隣接セルのルール: カルノー図では、隣接するセル同士が1つの変数だけ異なるように配置されています。これにより、隣接するセルをまとめることで、論理式の簡略化が可能になります。
- ブール式の簡略化: 真理値表から得られる結果をカルノー図に配置し、同じ値を持つ隣接セルをグループ化することで、冗長な論理項を削除できます。
カルノー図の例
2変数のカルノー図
2つの変数 (A) と (B) を持つ論理式に対して、カルノー図は次のようになります。 B=0 B=1 A=0 A=1
この2×2のグリッドで、それぞれのセルは次のように割り当てられます：
- (A=0, B=0)
- (A=0, B=1)
- (A=1, B=0)
- (A=1, B=1)
3変数のカルノー図
3つの変数 (A)、(B)、(C) を持つ論理式に対して、カルノー図は4×2のグリッドになります。 BC=00 BC=01 BC=11 BC=10 A=0 A=1
ここでは、各セルは次のような変数の組み合わせを表します：
- (A=0, B=0, C=0)
- (A=0, B=0, C=1)
- (A=0, B=1, C=0)
- (A=0, B=1, C=1)
- (A=1, B=0, C=0)
- (A=1, B=0, C=1)
- (A=1, B=1, C=0)
- (A=1, B=1, C=1)
カルノー図を用いた論理式の簡略化の手順
- 真理値表の作成: 対象となる論理式の真理値表を作成します。
- カルノー図への配置: 真理値表の出力値をカルノー図の各セルに配置します。たとえば、論理式が「1」になるセルには「1」を、論理式が「0」になるセルには「0」を配置します。
- グループ化: 1が隣接するセルをグループ化します。このとき、2の累乗（1、2、4、8…）の個数のセルをまとめることが重要です。グループはできるだけ大きく作り、少ない数でまとめるようにします。
- 簡略化された論理式の導出: 各グループに対応する論理式を導き、それらを組み合わせて簡略化された最小の論理式を求めます。
カルノー図のメリット
- 簡単な視覚化: カルノー図を使うことで、複雑な真理値表や論理式を簡単に視覚的に整理できるため、論理式の簡略化が容易になります。
- 最適化のサポート: 論理回路の設計において、ゲートの数を最小化するために、論理式の最小化を支援します。これにより、回路の効率が向上し、コストやエネルギー消費が削減されます。
カルノー図の限界
- 変数が多い場合の難しさ: 変数の数が増えると、カルノー図のサイズが指数関数的に増加し、視覚的に扱いにくくなるという欠点があります。例えば、4変数や5変数になると、図が非常に大きく複雑になるため、他の最適化手法（クワイン・マクラスキー法など）を使用することが推奨される場合があります。
まとめ
カルノー図は、ブール代数の論理式を簡単に最適化するための強力なツールです。特に、デジタル回路設計において使用され、回路の効率を向上させるために役立ちます。