@article{Поттосин Ю. В.2021-06-07,
author = { Поттосин Ю. В.},
title = {Минимизация булевых функций в классе ортогональных дизъюнктивных нормальных форм},
year = {2021},
doi = {10.37661/1816-0301-2021-18-2-33-47},
publisher = {NP «NEICON»},
abstract = {Ортогональные дизъюнктивные нормальные формы (ДНФ) булевых функций имеют широкое применение в логическом проектировании дискретных устройств. Задача ортогонализации ДНФ состоит в том, чтобы для заданной функции получить ДНФ, любые две элементарные конъюнкции которой ортогональны, т. е. их конъюнкция тождественно равна нулю. Предлагается подход к решению данной задачи с помощью средств теории графов. Подход рассчитан на представление функции в виде совершенной ДНФ. Предполагается получение всех интервалов булева пространства, на которых заданная функция имеет значение 1, и рассматривается граф пересечения этих интервалов. Рассматриваются два метода получения минимальной ортогональной ДНФ. Один из них сводит данную задачу к получению наименьшего доминирующего множества в графе путем покрытия его вершин их замкнутыми окрестностями, другой - к получению максимального независимого множества с помощью лексикографического перебора. Показывается, как предлагаемый подход распространяется на не полностью определенные булевы функции.},
URL = {https://www.academjournals.by/publication/18264},
eprint = {https://www.academjournals.by/files/18217},
journal = {Информатика},
}