Минимизация булевых функций в классе ортогональных дизъюнктивных нормальных форм

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

1. Кузнецов, О. П. Ортогональные системы булевых функций и их применение к анализу и синтезу логических сетей / О. П. Кузнецов // Автоматика и телемеханика. - 1970. - № 10. - С. 117-128.

2. Баранов, С. И. Синтез микропрограммных автоматов / С. И. Баранов. - Л. : Энергия, 1979. - 232 с.

3. Закревский, А. Д. Логический синтез каскадных схем / А. Д. Закревский. - М. : Наука, 1981. - 416 с.

4. Синтез асинхронных автоматов на ЭВМ / А. Д. Закревский [и др.]. - Минск : Наука и техника, 1975. -184 с.

5. Бибило, П. Н. Синтез комбинационных ПЛМ-структур для СБИС / П. Н. Бибило. - Минск : Навука i тэхнша. 1992. - 323 с.

6. Закревский, А. Д. Расчет надежности технической системы при заданных критических наборах событий / А. Д. Закревский, Ю. В. Поттосин // Логическое проектирование. - Минск : Ин-т техн. кибернетики АН Беларуси, 1996. - С. 123-131.

7. Закревский, А. Д. Логические основы проектирования дискретных устройств / А. Д. Закревский, Ю. В. Поттосин, Л. Д. Черемисинова. - М. : Физматлит, 2007. - 592 с.

8. Матросова, А. Ю. О вероятностном моделировании дискретных устройств / А. Ю. Матросова // Автоматика и телемеханика. - 1995. - № 3. - С. 156-164.

9. Гаврилов, М. А. Логическое проектирование дискретных автоматов (языки, методы, алгоритмы) / М. А. Гаврилов, В. В. Девятков, Е. И. Пупырев. - М. : Наука, 1977. - 352 с.

10. Бибило, П. Н. Синтез комбинационных схем методом функциональной декомпозиции / П. Н. Би-било, С. В. Енин. - Минск : Наука и техника, 1987. - 189 с.

11. Кардаш, С. Н. Ортогонализация системы ДНФ булевых функций / С. Н. Кардаш // Информационные технологии и системы 2020 (ИТС 2020) : материалы Междунар. науч. конф., Минск, Беларусь, 18 нояб. 2020 г. - Минск : БГУИР, 2020. - С. 41-42.

12. Поттосин, Ю. В. Методы дискретной математики в проектировании цифровых устройств / Ю. В. Пот-тосин. - Saarbrucken : LAP LAMBERT Academic Publishing, 2017. - 176 c.

13. Поттосин, Ю. В. Ортогонализация системы полностью определенных булевых функций / Ю. В. Пот-тосин, Е. А. Шестаков // Логическое проектирование. - Минск : Ин-т техн. кибернетики НАН Беларуси, 2000. - С. 107-115.

14. Паршина, Н. А. Минимизация частичных булевых функций в классе ортогональных ДНФ / Н. А. Паршина // Новые информационные технологии в исследовании дискретных структур : докл. Второй Всерос. конф. - Екатеринбург : УрО РАН, 1998. - С. 181-184.

15. Поттосин, Ю. В. Ортогонализация системы не полностью определенных булевых функций / Ю. В. Поттосин // Вопросы синтеза логики ЦВМ : в 3 ч. - Каунас : КПИ, 1976. - Ч. III. - С. 39-42.

16. Лекции по теории графов / В. А. Емеличев [и др.]. - М. : Наука, 1990. - 384 с.