問題：カルノー図と等価な論理式は？
【解答】
カルノ―図とは、複雑な論理式を簡単に表記することを目的とした図法です。
ここでは、論理変数をＡ～Ｄの４変数としました。それを図１のように、縦にＡとＢ、横にＣとＤを割り付け（この割付は任意です）、４行４列のマスにしました（３変数ならば４行２列になります）。
重要なのは並べ方です。通常の真理値表での並べ方ではなく、カルノー図では隣のビット変化が１だけのように並べます。これをグレイコードといいます。
また、上端のセルと下端のセル、右端のセルと左端のセルが連続していると考えます。
例えばアのマスは、Ａ＝０、Ｂ＝１、Ｃ＝０、Ｄ＝１、すなわち論理式 Ａ・Ｂ・Ｃ・Ｄ と対応しています。このようにして、すべてのマスにより、４個の論理変数およびその否定の論理積の組合せを示すことができます。
例えば、次の論理式Ｒがあるとします。
Ｒ＝Ａ・Ｂ・Ｃ・Ｄ＋Ａ・Ｂ・Ｃ・Ｄ＋Ａ・Ｂ・Ｃ・Ｄ
＋Ａ・Ｂ・Ｃ・Ｄ＋Ａ・Ｂ・Ｃ・Ｄ＋Ａ・Ｂ・Ｃ・Ｄ
論理式の各項に対応するマスに１を記入します。Ｒの第１項の、Ａ・Ｂ・Ｃ・Ｄ は、Ａ＝０、Ｂ＝０，Ｃ＝０、Ｄ＝１ですから、１行２列の位置に１を記入します（青の部分）。Ｒの項数は６ですので、６個のマスに１が記入されます。
これにより、論理式Ｒがカルノー図として表現されたことになります。また、このカルノー図があれば、論理式Ｒを作成することは容易です。
ここでは、論理関数は全ての論理変数の組み合せに対して１あるいは０の値が定まっているとしています。ところが現実には、論理変数の特定の組み合わせが許されない場合があり，この時は論理変数は不確定になります。そのような項を禁止項（don’t care項）といいます。
禁止項に対応するマスにはφを記入します。この値を勝手に１あるいは０とすることにより、以降のグループ化をもっと適切みできることがあります。
しかし、ここでは禁止項に関しては省略します。
上端と下端、右端と左端がつながっていると考え、上下・左右で２つの１が並ぶとき、それをグループとして囲みます。グループ化をしやすいように、グレイコードの並べ方にしたのです。
このとき、重複がなく、グループの個数が最小にすることが大切です（グループ個数が最終の論理式の項数になります）。
ここでは、５個のグループがありますが、ア、イ、ウの３つのグループにしました。
アのグループを例にします。
上のマス：Ａ＝０、Ｂ＝０、Ｃ＝０、Ｄ＝１ → Ａ・Ｂ・Ｃ・Ｄ
下のマス：Ａ＝０、Ｂ＝１、Ｃ＝０、Ｄ＝１ → Ａ・Ｂ・Ｃ・Ｄ
ですから、アの論理式は次のようにまります。
ア＝Ａ・Ｂ・Ｃ・Ｄ＋Ａ・Ｂ・Ｃ・Ｄ
＝Ａ・（Ｂ＋Ｂ）・Ｃ・Ｄ
＝Ａ・Ｃ・Ｄ
「隣り合う１をグループ化する」ことにより、（Ｂ＋Ｂ）のような組合せが発生するので、論理式が簡素になるのです。グループ化したとき、０と１の両方がある論理変数（ここではＢ）が消されます。
イとウも同様に、次のようになります。慣れると次のような演算をするまでもなく、結果が得られましょう。
イ＝Ａ・Ｂ・Ｃ・Ｄ＋Ａ・Ｂ・Ｃ・Ｄ
＝（Ａ＋Ａ）・Ｂ・Ｃ・Ｄ
＝Ｂ・Ｃ・Ｄ
ウ＝Ａ・Ｂ・Ｃ・Ｄ＋Ａ・Ｂ・Ｃ・Ｄ
＝Ａ・Ｂ・（Ｃ＋Ｃ）・Ｄ
＝Ａ・Ｂ・Ｄ
それで、全体の論理式Ｒは、
Ｒ＝Ａ・Ｃ・Ｄ＋Ｂ・Ｃ・Ｄ＋Ａ・Ｂ＋Ｄ
となります。
先に示したＲと比較すれば、かなり簡素になりました。それだけ回路を作成するのに素子の数や接合点が少なくすることができます。
エの場合、ＡとＢがそれぞれ０と１をとるので、ＡとＢを消すとＣ・Ｄになります。
このように、ある列（行）がすべて１のときは、列（行）の見出しと同じになります。
オの場合，ＢとＤはそれぞれ０と１をとるので消されます。ＡとＣは１だけですからＡ・Ｃになります。
このように、２×２の場合は、０、１の両方になる変数（２個）は消され、１だけならＸ、０だけならＸとすればよいのです。
問題：カルノー図と等価な論理式は？
【解答】 |
