カルノー図の例  (2変数)

logic

カルノー図を使った論理式の作成例として、2入力のORゲートを取り上げます。

2入力ORゲートのシンボル
図1: 2入力ORゲートのシンボル
表1: 2入力ORゲートの真理値表
A B Z
0 0 0
0 1 1
1 0 1
1 1 1

ORゲートの真理値表からカルノー図を作成

2行2列+見出しの表を作成する

まず、カルノー図の元になる表を作成します(図2)。カルノー図は、回路の入力値の組み合わせの数に対応する行と列を持つ表を書き、その表のセルに回路の出力値を書きます。2入力ORゲートの入力Aと入力Bは、それぞれ0と1の2通りの値を取るので、カルノー図は2行2列になります。表の上方向と左方向に、変数の見出しを書く部分も作成します。

2行2列+見出しの表を作成
図2: 2行2列+見出しの表を作成

変数の割り当て

ORゲートの入力AとBを、表の行と列に割り当てます。割り当て方は自由ですが、ここでは行方向にAを、列方向にBを割り当てます(図3)。

変数の割り当て
図3: 変数の割り当て

変数の見出しを書く

表の行列の見出し部分に、AとBが取り得る値の組み合わせ(0と1)を書きます(図4)。

AとBの取り得る値を書く
図4: AとBの取り得る値を書く

セルに値を書き込む

ORの真理値表(表1)を参考に、対応するセルに出力Zの値を書き込みます。書き込む値は、A=0,B=0の時Z=0、それ以外のAとBの組み合わせでZ=1です。これでカルノー図は完成です(図5)。

出力の値をセルに書く
図5: 出力の値をセルに書く

このカルノー図のセルの値が1の3箇所に注目して、主加法標準で論理式を作成すると(1)のようになります。

$$Z = A \overline{B} + \overline{A} B + AB\ \ \ \ \ \text{(1)}$$

ORの論理式はZ=A+Bなので、(1)は冗長であり、最適化できます。

論理式の最適化

ここから、論理式(1)の最適化を行います。表のセルをグループ化し、そのグループごとに論理式を最適化します。
まず、図5でセルの1が連続している部分に注目し、○で囲んでグループ化します。グループ化するルールは次の通りです。

  • 1のセルだけを○で囲んでグループ化する
  • 囲んだセルは縦と横を2のべき乗にする
  • 囲んだグループはできるだけ大きくする
  • セルの囲みは、重なってもよい
  • 表の上下、左右の両端はつながっている(リング状)と考える

図5にグループ化のルールを適用すると、図6のように2つの囲み(z1とz2)ができます。

値が1のセルをグループ化
図6: 値が1のセルをグループ化

まず、z1(赤い囲み)に注目します。この部分の主加法標準形の論理式が(2)です。

$$z1 = ( \overline{A} \bullet B ) + ( A \bullet B ) = (\overline{A} + A)B\ \ \ \ \ \text{(2)}$$

ブール代数より、\(\overline{A} + A=1\)です。これは、Aの値が0でも1でも結果は1ということを意味します。つまり、Aはあってもなくてもどちらでもよいので冗長です。よって、z1の囲みは(3)になります。

$$z1 = B\ \ \ \ \ \text{(3)}$$

次に、z2(青い囲み)に注目します。この部分の主加法標準形の論理式が(4)です。

$$z2 = ( A \bullet \overline{B} ) + ( A \bullet B ) = A(\overline{B} + B)\ \ \ \ \ \text{(4)}$$

ブール代数より、\(\overline{B} + B=1\)です。これは、Bの値が0でも1でも結果は1ということを意味します。つまり、Bはあってもなくてもどちらでもよいので冗長です。よって、z2の囲みは(5)になります。

$$z2 = A\ \ \ \ \ \text{(5)}$$

最後に、z1とz2からZを主加法標準形で表したのが(6)です。(6)は、本来のORゲートの論理式と一致します。

$$Z = z1 + z2 = B + A = A + B\ \ \ \ \ \text{(6)}$$

タイトルとURLをコピーしました