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

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

Термы функции алгебры логики — конъюнктивные для СДНФ и дизъюнктивные для СКНФ — переводят в двоичные эквиваленты, которые разбивают на группы с равным числом единиц (нулей). Затем попарно сравнивают эквиваленты соседних групп для получения термов более низких рангов.

Составляется таблица, в которой строки — исходные термы, столбцы — термы более низких рангов; метки показывают поглощение исходных термов термами низших рангов. После этого минимизация завершается непосредственно по методу Куайна.

По сравнению с методом Куайна уменьшается количество попарных сравнений на склеиваемость, поскольку исходное разбиение на группы с равным числом единиц (нулей) исключает заведомо бесполезные сравнения.

Время работы метода растёт экспоненциально; для функции от n переменных верхняя граница числа основных импликант — 3^n/n, а при n=32 их может быть больше 6,5·10^15, что относится к трансвычислительным задачам. Поэтому функции с большим числом переменных минимизируют эвристическими алгоритмами, фактическим мировым стандартом среди которых является алгоритм эспрессо.

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

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

Метод Куайна—Мак-Класки (англ. 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	1
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	1
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]

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

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

Особенности

Пример

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

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

Примечания

Ссылки

Категории