Прикладная теория цифровых автоматов

Сравнивая попарно все 0-кубы, получаем множество 1-кубов К₁. Применяя таким же образом к множеству К₁ операцию склеивания, находим множество 2-кубов К₂ и т.д. Этот процесс продолжается до тех пор, пока полученное из множества К_S очередное множество К_S+1 не окажется пустым (или не будет получен n-куб, представляющий функцию – константу «1»). В результате получается комплекс кубов, состоящий из множеств К_S:

К={К₀, К₁,..., К_S}, где s£n-1.

Для выделения из К множества  простых импликант ZÌK при каждой операции склеивания тем или иным способом отмечаются те кубы, которые объединяются в кубы высшей размерности. Очевидно, что неотмеченные кубы и образуют множество простых импликант Z, именуемое сокращенной ДНФ.

На следующем шаге при извлечении экстремалей используется таблица покрытий. Ее строки соответствуют простым импликантам, а столбцы - конституентам «1» (0-кубам) данной функции. В клетке таблицы ставится метка, если простая импликанта, соответствующая данной строке, покрывает вершину, соответствующую данному столбцу клетки. Экстремалям соответствуют те строки таблицы, которые содержат единственную метку в каком-либо столбце. Удаляя строки экстремалей и все столбцы, в которых данные строки имеют метки, получаем сокращенную таблицу покрытий.

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

Алгебраический метод  получения минимального покрытия (алгоритм Петрика)Выбор минимального покрытия на заключительном этапе формализуется с помощью алгебраического метода, предложенного Петриком. Исходная форма для алгоритма – таблица покрытий. Простые импликанты обозначаются символами, например, буквами латинского алфавита. В каждом столбце таблицы записывается дизъюнкция простых импликант, покрывающих соответствующий 0-куб. Покрытию функции соответствует конъюнкция всех записанных дизъюнкций векторов. Упрощая полученное выражение с помощью тождеств булевой алгебры, получаем некоторую ДНФ, каждый член которой соответствует некоторому тупиковому покрытию. Выбирая те из них, которые содержат минимальное количество букв, находим минимальные покрытия.

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

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

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

Найдем минимальную дизъюнктивную  нормальную форму (МДНФ). Задана функция, принимающая значение «1» на y= Ú (1,4,5,6,8,10,12,18,19,20,21,23,24) и имеющая не определенное положение на у = х (0,7,14,15,16,17,28,29,30,31).

Находим сокращенную ДНФ.

Строим таблицу покрытия (см. таблица 3.) и определяем ядро булевой функции.

                                                                                                                                                         Таблица 3

Строим сокращенную таблицу покрытия (см. таблица 4)

                                                                                          Таблица 4

Существует две экстремали – х0х0х и ххх00. Из сокращенной таблицы покрытий, включающей 6, 7, 9, 12, 14  столбцы и 3-8, 10, 12, 14 строки, следует:

(CÚDÚH) (GÚJÚLÚN)(FÚJ)ÙFÙE = (CGÚCJÚCLÚCNÚDGÚDJÚDLÚDNÚHGÚHJÚHLÚHN)ÙFÙE = =FECGÚFECJÚFECLÚFECNÚFEDGÚFEDJÚFEDLÚFEDNÚFEHGÚFEHJÚFEHLÚFEHN

Таким образом, существует двенадцать тупиковых покрытий: