カルノー図【Karnaugh map】

概要

カルノー図（Karnaugh map）とは、論理式を簡単化するために式の各変数の入力値と対応する出力値を一覧表に記したもの。1953年に米ベル研究所のモーリス・カルノー(Maurice Karnaugh)がベイチ図(Veitch diagram)の改良として考案した。

長い論理式をカルノー図で図示することにより、同じ結果を得ることができる、より短い式を視覚的、感覚的に見出だすことができる。論理回路の設計などにおいて冗長な箇所を削減し、少ない素子で同じ機能を実現するためによく用いられる。

一般的には縦横にマス目の並んだ2次元の表が用いられ、最上段と左端列に各変数の入力値の「0」と「1」のすべての組み合わせを列挙し、それ以外のマスにはそれぞれの入力値のときの論理式の出力値を記載する。簡単のため「1」になる場合のみを書き入れる場合もある（空欄は「0」）。

2変数の場合は上を片方の変数、左をもう一方とするが、3変数以上の場合は変数を2つのグループに分け、上段側に一方の組のすべての値の組み合わせ（例えば、二つの値の組なら「00」「01」「10」「11」）を、左端側にもう一方の組の値の組み合わせを列挙する。

表の大きさは3変数では2×4あるいは4×2、4変数では4×4、5変数では4×8あるいは8×4…というように変数の数が増える毎に2倍になる。一つの次元に3変数（「000」から「111」まで8通り）以上をまとめると複雑すぎて簡略化の役に立たないことが多いため、通常は次元あたり2変数まで、全体で4変数までで考えることが多い。

(2021.6.28更新)