4.10. Минимизация логических функций методом Квайна-Мак-Класки

Данный метод основывается на задании конституент единицы в виде условных двоичных чисел, называемых номерами соответствующих конституент. Кроме номера каждой конституенте присваивается определенный индекс, под которым понимается число единиц в двоичном представлении номера конституенты. Например, конституенте ‘a b c’ соответствует номер
101 (5) и индекс 2, конституенте ‘abc’ - номер 111 (7) и индекс 3. В результате реализации этого метода логическая функция разлагается на простые импликанты.

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

Реализацию алгоритма рассмотрим на примере минимизации следующей логической функции:

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

Группируем номера конституент, располагая их в порядке возрастания индексов (см. табл. 4.10).

На следующем этапе производим склеивание различных чисел, руководствуясь приведенной выше формулировкой метода Квайна-Мак-Класки. Подлежащие склеиванию пары чисел в табл. 4.10 указаны стрелками. При склеивании осуществляется псевдологическое умножение чисел на пустое множество, в результате которого несовпадающие в числах разряды отмечаются прочерком. Например, склеивание чисел 0001 и 0101 дает число 0_01, при склеивании 0001 и 0011 получаем 00_1 и т.д. Результат склеивания вписывается во второй столбец табл. 2.2, также разделяемый на строки, получаемые при объединении конституент соседних групп, с индексами отличающимися на единицу.

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

Таблица 4.10

По окончании склеивания приступают к построению импликантной таблицы (см. табл. 4.11). В данной таблице строки представляют собой простые импликанты минимизируемой функции, а столбцы – конституенты единицы. В качестве простых импликант выписываются наборы, содержащиеся в последнем столбце табл. 4.10, и наборы других стобцов этой таблицы, не принимавшие участия в склеивании. Если импликанта, содержащаяся в i-ой строке таблицы, составляет некоторую часть конституеты j-го столбца, на пересечении i-ой строки и j-го столбца ставится символ «+». Для получения минимальной формы логической функции нужно выписать минимальное число строк табл. 4.11, выбранное таким образом, чтобы для каждого столбца среди выбранных строк нашлась хотя бы одна, содержащая в этом столбце символ «+».

Таблица 4.11

На основании табл. 4.11 для рассматриваемой логической функции можно записать: