RT - article
SR - Electronic
T1 - Минимизация булевых функций в классе ортогональных дизъюнктивных нормальных форм
JF - Информатика
SP - 2021-06-07
DO - 10.37661/1816-0301-2021-18-2-33-47
A1 - Поттосин Ю. В., 
YR - 2021
UL - https://www.academjournals.by/publication/18264
AB - Ортогональные дизъюнктивные нормальные формы (ДНФ) булевых функций имеют широкое применение в логическом проектировании дискретных устройств. Задача ортогонализации ДНФ состоит в том, чтобы для заданной функции получить ДНФ, любые две элементарные конъюнкции которой ортогональны, т. е. их конъюнкция тождественно равна нулю. Предлагается подход к решению данной задачи с помощью средств теории графов. Подход рассчитан на представление функции в виде совершенной ДНФ. Предполагается получение всех интервалов булева пространства, на которых заданная функция имеет значение 1, и рассматривается граф пересечения этих интервалов. Рассматриваются два метода получения минимальной ортогональной ДНФ. Один из них сводит данную задачу к получению наименьшего доминирующего множества в графе путем покрытия его вершин их замкнутыми окрестностями, другой - к получению максимального независимого множества с помощью лексикографического перебора. Показывается, как предлагаемый подход распространяется на не полностью определенные булевы функции.