Минимизация булевых функций в классе ортогональных дизъюнктивных нормальных форм
https://doi.org/10.37661/1816-0301-2021-18-2-33-47
Аннотация
Ортогональные дизъюнктивные нормальные формы (ДНФ) булевых функций имеют широкое применение в логическом проектировании дискретных устройств. Задача ортогонализации ДНФ состоит в том, чтобы для заданной функции получить ДНФ, любые две элементарные конъюнкции которой ортогональны, т. е. их конъюнкция тождественно равна нулю. Предлагается подход к решению данной задачи с помощью средств теории графов. Подход рассчитан на представление функции в виде совершенной ДНФ. Предполагается получение всех интервалов булева пространства, на которых заданная функция имеет значение 1, и рассматривается граф пересечения этих интервалов. Рассматриваются два метода получения минимальной ортогональной ДНФ. Один из них сводит данную задачу к получению наименьшего доминирующего множества в графе путем покрытия его вершин их замкнутыми окрестностями, другой - к получению максимального независимого множества с помощью лексикографического перебора. Показывается, как предлагаемый подход распространяется на не полностью определенные булевы функции.
Для цитирования:
Поттосин Ю.В. Минимизация булевых функций в классе ортогональных дизъюнктивных нормальных форм. Информатика. 2021;18(2):33-47. https://doi.org/10.37661/1816-0301-2021-18-2-33-47
For citation:
Pottosin Yu.V. Minimization of Boolean functions in the class of orthogonal disjunctive normal forms. Informatics. 2021;18(2):33-47. (In Russ.) https://doi.org/10.37661/1816-0301-2021-18-2-33-47
Просмотров: 706
Послать статью по эл. почте 