Метод Куайна — Мак-Класки

Метод Куайна—Мак-Класки (англ. Quine–McCluskey method) — табличный метод минимизации булевых функций, предложенный Уиллардом Куайном и усовершенствованный Эдвардом Мак-Класки. Представляет собой попытку избавиться от недостатков метода Куайна.

Алгоритм минимизации

Термы (конъюнктивные в случае СДНФ и дизъюнктивные в случае СКНФ), на которых определена функция алгебры логики (ФАЛ) записываются в виде их двоичных эквивалентов;
Эти эквиваленты разбиваются на группы, в каждую группу входят эквиваленты с равным количеством единиц (нулей);
Производится попарное сравнение эквивалентов (термов) в соседних группах, с целью формирования термов более низких рангов;
Составляется таблица, заголовком строк в которой являются исходные термы, а заголовком столбцов — термы низких рангов;
Расставляются метки, отражающие поглощение термов высших рангов (исходных термов) и далее минимизация производится по методу Куайна.

Особенности

Специфика метода Куайна — Мак-Класки по сравнению с методом Куайна в сокращении количества попарных сравнений на предмет их склеивания. Сокращение достигается за счёт исходного разбиения термов на группы с равным количеством единиц (нулей). Это позволяет исключить сравнения, заведомо не дающие склеивания.

Несмотря на большую возможность практического применения чем у карт Карно когда речь идёт о более чем четыре переменных, метод Куайна—Мак-Класки тоже имеет ограничения области применения, так как время работы метода растёт экспоненциально с увеличением входных данных. Можно показать, что для функции от n переменных верхняя граница количества основных импликант 3ⁿ/n. Если n = 32 их может быть больше чем 6.5 * 10¹⁵. См. также Трансвычислительная задача.

Функции с большим количеством переменных должны быть минимизированы с помощью потенциально не оптимального эвристического алгоритма. На сегодня эвристический алгоритм минимизации эспрессо является фактическим мировым стандартом^[1].

Пример

Шаг 1: находим основные импликанты

Пусть функция задана с помощью следующей таблицы истинности:

#	${y}$	${z}$	${t}$	$f({x},{y},{z},{t})$
0	0	0	0	0
1	0	0	1	0
2	0	1	0	0
3	0	1	1	0
4	1	0	0	1
5	1	0	1	0
6	1	1	0	0
7	1	1	1	0

#	${x}$	${y}$	${z}$	${t}$	$f({x},{y},{z},{t})$
8	1	0	0	0	1
9	1	0	0	1	x
10	1	0	1	0	1
11	1	0	1	1	1
12	1	1	0	0	1
13	1	1	0	1	0
14	1	1	1	0	x
15	1	1	1	1	1

Можно легко записать СДНФ, просто просуммировав минтермы (не обращая внимание на не полностью определённые термы), где функция принимает значение 1.

f={\bar {x}}y{\bar {z}}{\bar {t}}+x{\bar {y}}{\bar {z}}{\bar {t}}+x{\bar {y}}z{\bar {t}}+x{\bar {y}}zt+xy{\bar {z}}{\bar {t}}+xyzt.

Для оптимизации запишем минтермы, включая те, которые соответствуют равнодушным состояниям, в следующую таблицу:

Количество 1	Минтерм	Двоичное представление
1	M4	0100
1	M8	1000
2	M9	1001
	M10	1010
	M12	1100
3	M11	1011
3	M14	1110
4	M15	1111

Теперь можно начинать комбинировать между собой минтермы, то есть проводить операцию склеивания. Если два минтерма отличаются лишь символом, который стоит в одной и той же позиции в обоих, заменяем этот символ на «-», это означает, что данный символ для нас не имеет значения. Термы, не поддающиеся дальнейшему комбинированию, обозначаются «*». При переходе к импликантам второго ранга, трактуем «-» как третье значение. Например: −110 и −100 или −11- могут быть скомбинированы, но не −110 и 011-. (Подсказка: Сначала сравнивай «-».)

 Количество "1"   Минтермы     | Импликанты 1-го уровня | Импликанты 2-го уровня
 ------------------------------|-----------------------|----------------------
 1             m4       0100   | m(4,12)  -100*        | m(8,9,10,11)   10--*
               m8       1000   | m(8,9)   100-         | m(8,10,12,14)  1--0*
 ------------------------------| m(8,10)  10-0         |----------------------
 2             m9       1001   | m(8,12)  1-00         | m(10,11,14,15) 1-1-*
               m10      1010   |-----------------------|
               m12      1100   | m(9,11)  10-1         |
 ------------------------------| m(10,11) 101-         |
 3             m11      1011   | m(10,14) 1-10         |
               m14      1110   | m(12,14) 11-0         |
 ------------------------------|-----------------------|
 4             m15      1111   | m(11,15) 1-11         |
                               | m(14,15) 111-         |

Шаг 2: таблица простых импликант

Когда дальнейшее комбинирование уже невозможно, конструируем таблицу простых импликант. Здесь учитываем только те выходы функции, которые имеют значение, то есть не обращаем внимания на не полностью определённые состояния.

	4	8	9	10	11	12	14	15
m(4,12)	X					X			-100
m(8,9,10,11)		X	X	X	X				10--
m(8,10,12,14)		X		X		X	X		1--0
m(10,11,14,15)				X	X		X	X	1-1-

Принцип выбора импликант такой же как и в методе Куайна. Простые импликанты, которые является ядрами выделены жирным шрифтом. В этом примере, ядра перекрывают все минтермы. Получаем следующий вариант:

f_{x,y,z,t}=y{\bar {z}}{\bar {t}}+x{\bar {y}}+xz.\

Примечания

↑ V.P. Nelson e.a., Digital Circuit Analysis and Design, Prentice Hall, 1995, pag. 234

Ссылки

Савельев А.Я. Основы информатики. — Москва: Издательство МГТУ им. Н.Э. Баумана, 2001. — С. 232—239. — 328 с. — (Информатика в техническом университете). — ISBN 5703815150.

[1] V.P. Nelson e.a., Digital Circuit Analysis and Design, Prentice Hall, 1995, pag. 234

[1]