クワイン・マクラスキー法

出典: フリー百科事典『ウィキペディア（Wikipedia）』

クワイン・マクラスキー法（—ほう; Quine-McCluskey algorithm）はブール関数を簡単化するための方法である。カルノー図と同様の目的で使われるが、コンピュータによる自動化に適しており、またブール関数が最簡形かどうか決定的に求めることができる。W・V・クワインが提案し、E・J・マクラスキーが発展させた方法なのでこの名がある。

クワイン・マクラスキー法は3段階からなる。

関数の主項をすべて求める
求めた主項を表にまとめ、必須項を求める
最簡形を求める

[編集] 例

[編集] 主項を求める

以下の真理値表で表されるブール関数を簡単化する。

f
	A	B	C	D	f
m₀	0	0	0	0	0
m₁	0	0	0	1	0
m₂	0	0	1	0	0
m₃	0	0	1	1	0
m₄	0	1	1	0	0
m₅	0	1	1	1	0
m₆	0	1	0	0	1
m₇	0	1	0	1	0
m₈	1	1	0	0	1
m₉	1	1	0	1	0
m₁₀	1	1	1	0	X
m₁₁	1	1	1	1	1
m₁₂	1	0	1	0	1
m₁₃	1	0	1	1	1
m₁₄	1	0	0	0	1
m₁₅	1	0	0	1	X

X は Don't care を表す。

この関数の加法標準形は、最小項の和をとって（Don't care は無視する）

$f = \overline{A} B \overline{C} \overline{D} + A B \overline{C} \overline{D} + A B C D + A \overline{B} C \overline{D} + A \overline{B} C D + A \overline{B} \overline{C} \overline{D} + A \overline{B} \overline{C} D$

となる。

もちろんこれはまだ最簡形ではない。まず、すべての1となる最小項をビット列中の1の数（ハミング重み）ごとに表に列挙する。また Don't care の項も加える。

1の数	最小項	ビット列表現
1	m₆	0100
1	m₁₄	1000
2	m₈	1100
	m₁₂	1010
	m₁₅	1001
3	m₁₀	1110
3	m₁₃	1011
4	m₁₁	1111

これで最初の準備が整った。1ビットのみが異なっている（ハミング距離が1となる）最小項の組を見つけて、その2つをまとめる。これをすべての最小項の組み合わせについて確かめる。こうしてできた項を再び1の数ごとにまとめ、同じ操作を再帰的に適用する。それ以上まとめることができない項にはしるし（*）をつける。この印を付けた項が主項となる。

1の数	最小項	ビット列表現
1	m₆	0100
1	m₁₄	1000
2	m₈	1100
	m₁₂	1010
	m₁₅	1001
3	m₁₀	1110
3	m₁₃	1011
4	m₁₁	1111

1回目の比較
1	m_6,8	-100 *
	m_8,14	1-00
	m_12,14	10-0
	m_14,15	100-
2	m_8,10	11-0
	m_10,12	1-10
	m_12,13	101-
	m_13,15	10-1
3	m_10,11	111-
3	m_11,13	1-11

2回目の比較
m_8,10,12,14	1--0 *
m_12,13,14,15	10-- *
m_10,11,12,13	1-1- *

[編集] 必須項を求める

主項のなかから必須項をみつける。横軸に最小項（Don't care でないもの）、縦軸に求めた主項を書いた表を作る。主項がカバーする最小項の欄にしるし（X）を書く。ある最小項をカバーする主項が1つしかないとき、その主項を必須項という。

	6	8	11	12	13	14
m_6,8 *	X	X					-100
m_8,10,12,14		X		X		X	1--0
m_12,13,14,15				X	X	X	10--
m_10,11,12,13 *			X	X	X		1-1-

例では2つ必須項が求まった。表中でしるし（*）をつけてある。必須項はその名のとおり、簡単化した関数に必ず含まれていなければならない項である。

[編集] 最簡形を求める

式を短くするために主項に番号を振りなおす。m_6,8 = e₁ , m_8,10,12,14 = e₂ , m_12,13,14,15 = e₃ , m_10,11,12,13 = e₄ とおく。

簡単化した後の関数fはすべての最小項をカバーしていなければならない。最小項m₈が含まれる条件はブール代数式で (e₁ + e₂) となる。fがすべての最小項を含むためには、

e 1 (e 1 + e 2) e 4 (e 2 + e 3 + e 4)(e 3 + e 4)(e 2 + e 3)

を満たす必要がある。これを展開すると

e 1 e 2 e 3 e 4 + e 1 e 2 e 4 + e 1 e 3 e 4

となる。最も簡単なのは e₁e₂e₄ または e₁e₃e₄ である。よって最簡形は

$f = e_1 + e_2 + e_4 = B \overline{C} \overline{D} + A \overline{D} + A C$

または

$f = e_1 + e_3 + e_4 = B \overline{C} \overline{D} + A \overline{B} + A C$

である。

[編集] 計算量

4変数以上のブール関数を扱う際にはカルノー図よりも実用的であるが、クワイン・マクラスキー法が使える範囲にも限りがある。充足可能性問題というNP困難な問題を対象としているため、実行時間が入力長の指数関数的に増加してしまうのである。n変数関数における主項の数の上限は3ⁿとなる。n = 32とおくと、主項の数は6.5 × 10¹⁵を超えることもある。変数の多い関数の簡単化においては最適解を保証しないヒューリスティックな方法が必要になる。