Минимизация функций алгебры логики методом Квайна–Мак-Класки

Данный метод основывается на задании конституент единицы (нуля) в виде условных чисел, называемых номерами соответствующих конститу­ент. Каждой конституенте присваивается определенный индекс, под которым понимается число единиц в двоичном представлении номера конституенты. Например, конституенте соответствует номер 101 (5) и ин­декс 2, а конституенте – номер 111 (7) и индекс 3.

При реализации дан­ного метода минимизируемая функция разлагается на простые импликанты. Функция является импликантой функции , если на всех наборах аргументов , на которых функция j равна единице, функция f также принимает единичное значение. Простой импликантой функции f называется всякое, являющееся импликантой этой функции элементарное произведение , исключение из которого хотя бы одного аргумента уже не позволяет получить импликанту рассматриваемой ФАЛ.

Алгоритм Квайна–Мак-Класки формируется следующим образом.

Для того чтобы два числа m и n являлись номерами двух склеивающихся между собой конституент единицы, необходимо и достаточно, чтобы их индексы отличались на единицу, сами числа отличались на целую степень числа два и число с большим индексом было больше числа с меньшим индексом.

Реализацию алгоритма рассмотрим на примере минимизации ФАЛ

.

На первом этапе минимизации все конституенты записываем в виде чисел. Определяем номера и индексы каждой конституенты единицы

0 I I II I III III IY.

Группируем номера конституент, располагая их в порядке возраста­ния индексов в первом столбце таблицы, отделяя друг от друга горизонтальной чертой группы, имеющей одинаковый индекс (табл. 3.1). Далее производим склеивания различных чи­сел, руководствуясь приведенной выше формулировкой алгоритма Квайна–Мак-Класки. Склеивание возможно только между числами, индексы которых отличаются на единицу. Для выполнения склеиваний необходимо находить пары чисел, различающихся на целую степень числа 2, при этом бóльшему числу обязательно должен соответствовать бóльший индекс. Подлежащие склеиванию пары чисел указаны стрелками (таблица 23).

Таблица 23 – Минимизация ФАЛ методом Квайна–Мак-Класки

При склеивании осуществляется псевдологическое поразрядное умножение чисел на пустое множество, в результате которого несовпа­дающие в числах разряды отмечаются символом «–» прочерк. Например, склеива­ние чисел 0000 и 0001 дает число 000­­_, при склеивании 0000 и 0100 получаем 0_00 и т. д. Результат склеивания впиcывается во второй столбец таблице 23. Данный столбец также разделяется на строки, получаемые при объединении конституент соседних групп, с индексами, отличающимися на единицу.

После склеивания всех групп чисел первого столбца таблицы, переходят ко второму столбцу, вписывая результат склеивания в третий столбец. При объединении чисел второго, третьего и последующих столбцов таблицы следует помнить, что склеивание возможно только между числами, содер­жащими символ «–» в одноименных разрядах. Процесс склеивания продолжается до тех пор, пока образование нового столбца станет невозможным.

По окончании склеивания приступают к построению импликантной таблицы (таблица 24). В данной таблице строки представляют собой про­стые импликанты минимизированной функции, а столбцы конституенты единицы (нуля). В качестве простых импликант выписываются наборы, содержащиеся в последнем столбце таблице 23, и наборы других столбцов этой таблицы, не принимавшие участия в склеивании.

Таблица 24 – Импликантная таблица минимизируемой функции

Простые импликанты	Конституенты единицы
	Ú	Ú
	Ú		Ú
		Ú		Ú	Ú		Ú
				Ú		Ú	Ú	Ú

Если импликанта, содержащаяся в i-й строке таблицы, составляет некоторую часть конституенты j-го столбца, на пересечении i-й строки и j-го столбца ставится символ «Ú». Для отыскания минимальной формы ФАЛ нужно выбрать из импликантной таблицы минимальное число строк таким образом, чтобы для каждого столбца среди выбран­ных строк нашлась хотя бы одна, содержащая в этом столбце символ «Ú».

При задании ФАЛ в форме КСНФ минимизацию осуществляют, используя конституенты нуля. Искомая функция также определяется на основании импликантной таблицы и записывается в виде произведения элементарных дизъюнкций.