2-4. МЕТОД КВАЙНА—МАК-КЛАСКИ

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

1. Нахождение первичных импликант. Все минитермы данной функции сравнивают между собой попарно. Если минитермы таковы, что они имеют вид то выписывается конъюнкция а, являющаяся минитермом ранга. Минитермы -го ранга, для которых произошло склеивание, отмечаются. После построения всех минитермов ранга вновь сравнивают их попарно, выписывают минитермы ранга и отмечают склеивающиеся минитермы ранга и т. д. Этап заканчивается, когда вновь полученные минитермы ранга уже не склеиваются между собой. Все не отмеченные минитермы называются первичными или простыми импликантами.

Пример 2-7.

Минитермы 4-го ранга:

Образуем минитермы 3-го ранга:

Теперь находим минитермы 2-го ранга:

Так как дальнейшее склеивание невозможно, то этап получения простых импликант закончен. Простыми импликантами являются следующие мннитермы:

2. Расстановка меток. Для данной функции

где — простые импликанты, полученные нами на первом этапе. Соотношение (2-12) определяет СДНФ для данной функции. Для нахождения минимального покрытия интервалами максимального ранга необходимо теперь произвести выбрасывание некоторого количества первичных импликант. На этапе расстановки меток составляется таблица, число строк которой равно числу полученных первичных импликант минимизируемой функции. Число столбцов совпадает с числом минитермов ДСНФ. Если в некоторый минитерм ДСНФ входит какой-либо из первичных импликант, то на пересечении соответствующего столбца и строки ставится метка.

Пример 2-7 (продолжение). Составим таблицу с метками для рассматриваемой функции, в которой будет шесть строк и восемь столбцов.

3. Нахождение существенных импликант. Если в каком-либо из столбцов составленной таблицы имеется только одна метка, то первичная импликанта, стоящая в соответствующей строке, называется существенной импликантой. Существенная импликанта не может быть исключена из правой части (2-12), так как без нее не будет получено покрытие всего множества данной функции. Поэтому из таблицы меток исключаются строки, соответствующие существенным импликантам, и столбцы минитермов, покрываемых этими существенными импликантами.

Пример 2-7 (продолжение). Для нашей функции существенной импликантой является

Она покрывает минитермы При переходе к следующему этапу эти мннитермы могут быть вычеркнуты.

4. Вычеркивание лишних столбцов. Исследуется таблица, полученная после третьего этапа. Если в ней есть два столбца, в которых имеются метки в одинаковых строках, то один из них вычеркивается. Это можно сделать в силу того, что покрытие оставшегося столбца будет осуществлять покрытие выброшенного минитерма.

Пример 2-7 (продолжение). После вычеркиваний существенной импликанты и минитермов, которые она покрывает, таблица меток принимает вид:

В данном случае одинаковых столбцов нет.

5. Вычеркивание лишних первичных импликант. Если после выбрасывания некоторых столбцов на четвертом этапе в таблице появляются строки, в которых нет ни одной метки, то первичные импликанты, соответствующие этим строкам, исключаются из дальнейших рассмотрений, так как они не покрывают оставшиеся в рассмотрении минитермы.

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

Пример 2-7 (окончание). Для рассматриваемой функции выбираем покрытие из импликант и , так как они совместно покрывают все оставшиеся после четвертого этапа миннтермы. Минимальная ДНФ для этой функции имеет вид:

Пример 2-8. Найти минимальную формулу для функции

Составляем первичные импликанты.

Минитермы 4-го ранга:

Мипитермы 3-го ранга:

Минитермы 2-го ранга:

Составляем таблицу меток.

Первичные имиликанты являются существенными. Эти существенные импликанты покрывают все множество для данной функции. Таким образом, МДНФ этой функции есть

В методе Квайна есть одно существенное неудобство. Оно связано с необходимостью полного попарного сравнения на этапе- нахождения простых импликант. С ростом числа минитермов, определяющих ДСНФ данной функции, растет число этих сравнений. Этот рост характеризуется факториальной функцией. Поэтому при достаточно большом числе ммнитермов применение метода Квайна становится затруднительным. В 1956 г. Мак-Класки предложил модернизацию первого этапа метода Квайна, дающую существенное уменьшение числа сравнений минитермов.

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

Пример 2-9. Функция задана в ДСНФ минитермами с номерами О, 1, 2, 3, 4, 6, 7, 8, 9, 11, 15. Запишем эти минитермы по группам в двоичном коде.

Нулевая группа: .

Первая группа:

Вторая группа:

Третья группа:

Четвертая группа: 1111.

Сравнивая соседние группы, получаем по группам минитермы 3-го ранга:

Нулевая группа:

Первая группа:

Вторая группа:

Третья группа: .

Теперь находим минитермы 2-го ранга:

Нулевая группа:

Первая группа:

Вторая группа:

Составляем таблицу меток:

Дальнейшая минимизация по методу Мак-Класки совпадает с минимизацией по методу Квайна. Для рассматриваемой функции минимальная ДНФ имеет следующий вид:

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

некотором тупиковой ДНФ рассматриваемой функции. Пусть, например, таблица покрытий некоторой имеет вид:

Отсюда и у функции существует только одна тупиковая ДНФ (конечно, совпадающая с .