Pull to refresh

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

Reading time 2 min
Views 17K
В этой статье я расскажу про достаточно важную в информатике и теории автоматов тему – минимизацию булевых функций. Этим вопросом задавались пожалуй все, кто изучал или сталкивался с данной тематикой.

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

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

Метод заключается в применении известных правил Склеивания и поглощения.


image

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

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


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


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


Построим таблицу истинности для нее:

Выпишем все гиперкубы, лежащие в M1(f) и соответствующие им импликанты:

Выбираем простые импликанты и строим таблицу их накрытия:


Поскольку импликанта yz перекрывается другими, ее можно изъять из выражения. Выходит, что тупиковая ДНФ функции имеет вид:


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

Articles