カルノー図とは、論理回路などにおいて、選言標準形の論理式を短くするために利用する表のことです。
例えば、以下は、4変数のカルノー図です。
例えば、ORゲート、ANDゲート、NOTゲートを使って、選言標準形で表現されたA・B・C・D+A・B・C・Dとなる4入力の論理回路があったとします。
この論理回路をカルノー図にすると、以下になります。
表の0はLow、1はHighに対応しています。表において、この論理回路の出力がHighになる入力の組み合わせの位置に1を記載しています。
4変数のカルノー図に対して、A・B・C・Dのような4変数の論理式の場合は、以下のように、1箇所に1を記載します。
4変数のカルノー図に対して、A・C・Dのような3変数の論理式の場合は、以下のように、2箇所に1を記載します。
この場合、A・C・Dには、Bがないため、Bは0でも1でも良いということになり、2箇所が1になります。
B・C・Dであれば、以下になります。
4変数のカルノー図に対して、A・Cのような2変数の論理式の場合は、以下のように、4箇所に1を記載します。
この場合、A・Cには、BとDがないため、BとDは0でも1でも良いということになり、4箇所が1になります。
A・Bであれば、以下になります。
B・Cであれば、以下になります。
B・Dであれば、以下になります。
4変数のカルノー図に対して、Aのような1変数の論理式の場合は、以下のように、8箇所に1を記載します。
この場合、Aには、BとCとDがないため、BとCとDは0でも1でも良いということになり、8箇所が1になります。
A・C+A・Bのように、二つの論理式がORゲートで接続されている場合、以下のように1を重ねます。
例えば、論理式がA・B・C・D+A・B・C・Dとなる選言標準形の論理回路があったとします。
この論理式をカルノー図にすると、以下になります。
このカルノー図から、Bは0でも1でも良いことが分かるため、A・C・Dの論理式と同じです。よって、以下になります。
A・B・C・D+A・B・C・D=A・C・D
カルノー図を使って、論理式を短くできました。
つまり、論理式をカルノー図で表現した後、同じカルノー図になる最も短い論理式を探し出して、論理式を短くします。
カルノー図から最も短い論理式を探し出す方法は、上記で説明したカルノー図の作り方を理解すれば、明らかです。
以下は、2変数のカルノー図です。
以下は、3変数のカルノー図です。
ABの順番が00→01→11→10になっています。これは、00→01→11→10→00→…というようにループさせた場合に、一つの遷移時の変化点が1箇所になる順番にしています。
例えば、00→01→10→11→00→…の順番だと、01→10と11→00のときに2箇所変化してしまいます。この順番だと、カルノー図から最も短い論理式を探し出す際に不便になります。
以下は、4変数のカルノー図です。
ABとCDの順番が00→01→11→10になっています。理由は、3変数のカルノー図と同じです。
以下は、5変数のカルノー図です。
5変数以上のカルノー図は、最も短い論理式を探し出す際、表の端以外でも1が隣り合わない場合が出てくるので難易度が上がります。
5変数以上のカルノー図は、表も大きくなり、実用的ではありません。