Минимизация булевых функций методом Гиперкубов

В этой статье я расскажу про достаточно важную в информатике и теории автоматов тему – минимизацию булевых функций. Этим вопросом задавались пожалуй все, кто изучал или сталкивался с данной тематикой.
Существует немало методов, однако наибольший интерес представляют те, которые могут быть формализованы, а соответственно запрограммированы без особых сложностей. А также работающие с произвольными булевыми выражениями. Идеального метода не придумано, все имеют те или иные слабые и сильные качества. Я остановлюсь на так называемом методе Гиперкубов — Методе Квайна.

Метод, к сожалению, применим только для Совершенных ДНФ, поэтому при большом числе переменных использование затруднено гигантским выражением СДНФ.
Метод заключается в применении известных правил Склеивания и поглощения.

image
image

Перед описанием алгоритма объясню почему метод называется методом гиперкубов.
Возьмем произвольную функцию f, M1(f) – единичное множество. Проще говоря, множество наборов переменныx, на которых функция обращается в верное высказывание.
Гиперкуб – это множество M1(f).
Коньюнктивный одночлен – импликанта, если М1(K) входит в M1(f).
Импликанту называют простой, если не существует другого K2, что M1(K) содержится в M1(K2), говоря простым языком – соответствует самому большому гиперкубу.

Основные этапы данного метода

  • Построить таблицу истинности.
  • Выписать все гиперкубы из M1(f) и импликанты.
  • Взять простые импликанты.
  • Построить таблицу накрытия.
  • Из оставшихся простых импликантов создать тупиковую ДНФ.

Возьмем в качестве примера следующую булеву функцию.

image

Склеиваем и поглощаем.

image
image
image
image
image
image

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

image
image

Дальше склеивать нечего. Выписываем полученные простые импликaнты.

image

Специальная матрица Квайна


Сократим еще, записав данные в следующую матрицу.
Строки такой матрицы отмечаются простыми импликантами булевой функции, а столбцы — членами СДНФ булевой функции.

image

Как видно из таблицы, третий импликант полностью заменяется другими, значит его можно смело откинуть.
Получили тупиковую ДНФ.

image

Рекомендую всем заинтересовавшимся прочитать замечательную книгу К.Г. Самофалова «Прикладная теория цифровых автоматов».


0 комментариев

Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.