Skip navigation
Please use this identifier to cite or link to this item: https://libeldoc.bsuir.by/handle/123456789/46001
Title: Минимизация булевых функций в классе ортогональных дизъюнктивных нормальных форм
Other Titles: Minimization of Boolean functions in the class of orthogonal disjunctive normal forms
Authors: Поттосин, Ю. В.
Pottosin, Y. V.
Keywords: публикации ученых
булевые функции
дизъюнктивные нормальные формы
графы пересечения
Boolean function
disjunctive normal form
intersection graph
Issue Date: 2021
Publisher: Объединенный институт проблем информатики Национальной академии наук Беларуси, РБ
Citation: Поттосин, Ю. В. Минимизация булевых функций в классе ортогональных дизъюнктивных нормальных форм / Поттосин Ю. В. // Информатика. – 2021. – Т. 18, № 2. – С. 33–47. – DOI: https://doi.org/10.37661/1816-0301-2021-18-2-33-47.
Abstract: Ортогональные дизъюнктивные нормальные формы (ДНФ) булевых функций имеют широкое применение в логическом проектировании дискретных устройств. Задача ортогонализации ДНФ состоит в том, чтобы для заданной функции получить ДНФ, любые две элементарные конъюнкции которой ортогональны, т. е. их конъюнкция тождественно равна нулю. Предлагается подход к решению данной задачи с помощью средств теории графов. Подход рассчитан на представление функции в виде совершенной ДНФ. Предполагается получение всех интервалов булева пространства, на которых заданная функция имеет значение 1, и рассматривается граф пересечения этих интервалов. Рассматриваются два метода получения минимальной ортогональной ДНФ. Один из них сводит данную задачу к получению наименьшего доминирующего множества в графе путем покрытия его вершин их замкнутыми окрестностями, другой – к получению максимального независимого множества с помощью лексикографического перебора. Показывается, как предлагаемый подход распространяется на не полностью определенные булевы функции. The orthogonal disjunctive normal forms (DNFs) of Boolean functions have wide applications in the logical design of discrete devices. The problem of DNF orthogonalization is to get for a given function such a DNF that any two its terms would be orthogonal, i. e. the conjunction of them would be equal identically to zero. An approach to solve the problem using the means of graph theory is suggested. The approach is proposed by representation of the function as perfect DNF. Obtaining all the intervals of the Boolean space where the given function has value 1 is supposed, and the intersection graph of those intervals is considered. Two methods to obtain a minimum orthogonal DNF are considered. One of them reduces the problem toward finding out the smallest dominating set in the graph by covering its vertices with their closed neighborhoods, the other – to obtain the maximum independent set by lexicographic enumeration. It is shown how the suggested approach can be extended on incompletely specified Boolean functions.
URI: https://libeldoc.bsuir.by/handle/123456789/46001
Appears in Collections:Публикации в изданиях Республики Беларусь

Files in This Item:
File Description SizeFormat 
Pottosin_Minimizatsiya.pdf401,65 kBAdobe PDFView/Open
Show full item record


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.