クワインマクラスキー法(QM法)の使い方と論理式の簡単化

クワインマクラスキー法(QM法)とは

論理関数を簡単化する方法の一つです。

出力1を与える論理変数$x_0,x_1,x_2,x_3$の組み合わせのうち、一変数だけ数値が異なる組み合わせをマージを繰り返し、簡単化していきます。

よく、カルノー図を用いた簡単化と比較されることがありますが、下記の利点があります。

１．２．はカルノー図に対して優位な項目になります。(利点)

カルノー図は、ハミング距離が1になるマスを作成し、1または※(ドントケア)が隣接しているマスを丸で囲っていく方法になります。

視覚的で、人間の目からすると分かりやすいですが、計算機からするとこの内容を理解することができません。

また、人間の手で行えるのはせいぜい4変数までです。5変数の場合、5変数目の入力0,1ごとにマスを分けて作成すると、何とか対応することもできますが、試験で行うには時間がかかります。

ところが、QM法にはマスの制約が無いため、5変数以上の場合でも問題なく対応できます。

３．について、何も考えずに簡単化しようとすると、$(x_0,x_1,x_2,x_3)=(0,0,0,0),(1,1,1,1)$の対応まで確認する必要があります。全ての変数が異なっており、両者を満たす項は明らかに生成できそうにありません。

こういった無駄を、クワインマクラスキー法では初めから省くことができます。

クワインマクラスキー法の手順

実際に、問題を解きながら説明していきます。

解答例

出力1の論理変数の組み合わせを表にする。

問題文で与えられた真理値表のうち、出力1を取る組み合わせだけピックアップすれば良いです。

1を取る変数の数	$x_0$	$x_1$	$x_2$	$x_3$
0	0	0	0	0
1	0	0	1	0
1	1	0	0	0
2	0	1	0	1
2	1	0	1	0
3	1	1	0	1
4	1	1	1	1

入力の組み合わせのうち、互いに1文字違いの項目を探し、ドントケアにマージする。

先ほど作成した表のうち、1を取る変数の個数が1つ違いの行同士を比較します。

その結果、変数の取る値が1文字違いの組み合わせをマージしていきます。

これを繰り返すことで、主項は下記になる。$$\begin{array}{}\text{(1)}& \begin{array}{r}{\bar{x}}_1{\bar{x}}_2\overline{x_3},{\bar{x}}_1\overline{x_3},x_1{\bar{x}}_2{x}_3,x_0{x}_1{x}_3\end{array}\end{array}$$

マージ後の主項それぞれに対し、取りうる値を行列表示にする。

• $x_0$は$2^0{x}_0$で表されるため、入力0,1に対し、出力0,1の2通り
• $x_1$は$2^1{x}_0$で表されるため、入力0,1に対し、出力0,2の2通り
• $x_2$は$2^2{x}_0$で表されるため、入力0,1に対し、出力0,4の2通り
• $x_3$は$2^3{x}_0$で表されるため、入力0,1に対し、出力0,8の2通り

これらを出力として足し合わせると、下記の表が生成される。

行列のうち、一つしか1を持たない列に対応する最小項を必須主項にする。

前節で得られた表に対し、必須主項を橙色のセルで塗りつぶす。

対応する必須主項は、$$\begin{array}{}\text{(2)}& \begin{array}{r}{\bar{x}}_1\overline{x_3},x_1{\bar{x}}_2{x}_3,x_0{x}_1{x}_3\end{array}\end{array}$$

ピンク色で塗った${\bar{x}}_1{\bar{x}}_2\overline{x_3}$については、${\bar{x}}_1\overline{x_3}$で包含できるため、これで全ての出力を包含できた。

結果

前節で得られた必須主項を足し合わせ、求める論理関数は

$$\begin{array}{}\text{(3)}& \begin{array}{r}f(x_0,x_1,x_2,x_3)={\bar{x}}_1\overline{x_3}+x_1{\bar{x}}_2{x}_3+x_0{x}_1{x}_3\end{array}\end{array}$$

まとめ

大学によっては、カルノー図ではなく、クワインマクラスキー法を用いての簡単化をわざわざ問うてくることがあります。

カルノー図で簡単化できるから問題ない！と慢心することなく、QM法でもできるようになることをオススメします。