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

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

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

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

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


image

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

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


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


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


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

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

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


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


Рекомендую всем заинтересовавшимся прочитать замечательную книгу К.Г. Самофалова «Прикладная теория цифровых автоматов».
AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 27

    +6
      +1
      Мне тоже карты Карно нравятся. Много удобнее гиперкубов.
      Когда прочитал заголовок статьи, думал о них речь и пойдет…
        +4
        Карты Карно не имеют программной реализации, для минимизации на ЭВМ используют модификацию этого метода — метод Квайна-МакКласки.
      +9
      Универ. 2й курс.
        +11
        Универ. 1й курс.
        • UFO just landed and posted this here
            +5
            Универ. Третий курс (!) псевдоIT-специальности. И это печально.
            • UFO just landed and posted this here
              • UFO just landed and posted this here
                  0
                  Универ. Четвёртый курс. Совсем не IT.
                  0
                  9ый класс!!! Ё мое, мы это в 9ом классе знали!
                    0
                    Это что у вас за школа такая? Или вы сам, факультативно?
                      0
                      Нет, все проходили… а класс в школе с углубленным изучением математики и информатики.
                    0
                    СУНЦ МГУ. 10 класс.
                    0
                    Универ. 2ой курсе ИТ специальности =)
                      +1
                      The Khan Academy — одно из последних видео (и это не может не вызывать гордость за советское образование).
                      +5
                      N сантиметров :)
                        0
                        Универ, 1 курс)
                        +6
                        Уважаемый автор, зачем пересказывать n-юу лекцию по дискретной математике в ВУЗе (2, по-моему, курс математического факультета)?!

                        Не понимаю смысла поста.

                        И что вы понимаете под гиперкубами? Куб четверной размерности или куб любой размерности >= 4?

                        Более того, если «пошла такая пьянка», было бы интересно приложить картинки.

                        Это самое интересное данного метода! Особенно, когда f() -функция > 3 переменных.
                          0
                          Помниться проскакивала тут когда-то статья про минимизацию алгоритмом Рота… По сути из одной гребенки методы, хотя как-то метод Рота вроде бы распространен больше… поправьте меня если я ошибаюсь.
                            0
                            А в чём формулы делали?
                              0
                              Формулы в основном в Tex'е
                            • UFO just landed and posted this here
                                0
                                Луцик!!!
                                  0
                                  Боюсь далеко не все знают «бога» минимизации)
                                    0
                                    кто знает тот поймет ;)
                                  0
                                  ну и где гиперкубы?
                                  а вообще это «метод Викентьева» называется

                                  Only users with full accounts can post comments. Log in, please.