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

Данный метод основывается на задании минтермов в виде условных чисел – номера. Каждому минтерму присваивается опред-й индекс, под которым понимается число единиц в двоичном представлении номера минтерма.

ДСНФ запишется в виде двоичного числа.

Определяем номер и индекс каждого минтерма.

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

Выполняем склеивание различных чисел из соседних групп

Группируем номера минтермов, располагая их в порядке возраста­ния индексов в первом столбце таблицы, отделяя друг от друга горизонтальной чертой группы, имеющей одинаковый индекс. Далее производим склеивания различных чи­сел. Склеивание возможно только между числами, индексы которых отличаются на единицу. Для выполнения склеиваний необходимо находить пары чисел, различающихся на целую степень числа 2, при этом бóльшему числу обязательно должен соответствовать бóльший индекс.

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

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

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